Superconductor

The virial theorem in the workplace

There's a theorem from mathematical physics that may have an application in the workplace. This is the virial theorem, and its workplace analogy may explain why every job has its annoying parts.

One version of the virial theorem roughly says that for a finite collection of point particles interacting gravitationally, the time average of the kinetic energy is half the time average of the potential energy, or

<K> = - <U> / 2

The virial theorem is useful to astronomers because you can use it get a good idea of masses of distant objects, which you can't really observe, from their kinetic energy, which you can observe. The reason that we think that dark matter exists is basically from observations like those plus the virial theorem.

Driving in to work today, I had the thought that an appropriate analogy for the virial theorem the workplace might be that the bad parts of a job are always proportional to the good parts of a job. In my experience, this seems to have always been true.You probably have some relationship like this, for example:

<Bad> = - <Good> / 2

When I was an officer in the US Army, there were lots of good aspects of the job. There's nothing in the world as rewarding as working with soldiers, for example, and getting paid to work with explosives and fire guns is also lots of fun. To make up for this, however, there's also the fact that the military is really part of the government, so you're really part of a large, mind-numbingly bureaucratic organization.

Or when I used to do what's probably best called applied physics research, it was great fun working with things like lasers and electron microscopes. To make up for this, however, there's the never-ending battle that you have to fight to get funding for those expensive gadgets.

Or when I did mergers and acquisitions consulting, it was great fun getting a look inside lots of different companies in lots of different industries and seeing how they worked. The pay wasn't bad, either. To make up for this, however, there were the 20-hour days and the backstabbing from other consultants (particularly the lawyers) involved in the M&A projects that you had to keep a constant eye out for.

So although I'm not sure that you can write down a set of assumptions that lets you rigorously prove an analogy for virial theorem for the workplace, it certainly seems to be true. If there's a job out there for which it doesn't hold, I'd definitely like to hear about it.

The converse of the Nagell-Lutz theorem

The Nagell-Lutz tells us that rational points of finite order have integer coordinates, but it doesn't tell us that points with integer coordinates have finite order. As a reminder, here's the statement of the Nagell-Lutz theorem.

Let y² = x³ + ax + b be an elliptic curve with integer coefficients and let D = 4 a³ + 27 b². Then if P = (x_P,y_P) is a rational point of finite order then P has integer coordinates and either y_P = 0 or y_P²|D.

Here are some examples of points with integer coordinates that don't have finite order.

The point P = (1,2) is on the elliptic curve

y² = x³ + 3

but (1,2) isn't a point of finite order. We have that

2P = (-23/16,-11/64)

for example. Since 2P doesn't have integer coordinates, it's not a point of finite order, so P isn't either.

For another example, consider the elliptic curve

y² = x³ + 17

There are 16 points with integer coordinates on this curve. These are the following

(-2,±3)

(-1,±4)

(2,±5)

(4,±9)

(8,±23)

(43,±282)

(52,±375)

(5234,±378661)

Although we can find a few cases where adding these points gives another point with integer coordinates, like

(-2,3) + (-1,4) = (4,9)

most cases don't. We have that

(-1,4) + (-1,4) = (137/64, -2651/512)

for example.

Even worse, we have that

(5234,378661)  + (5234,378661)  = (187618163896928/143384152921, -1/4)

None of these points actually have finite order although they have integer coordinates. So points of finite order have to have integer coordinates, but not all points with integer coordinates have finite order.

An example of bad reduction mod p

Elliptic curves are a natural construction over the complex numbers, but curves over the complex numbers aren’t very useful in computing. For that, we need elliptic curves that are defined over a finite field. It turns out that an elliptic curve over the integers can be reduced to one over a finite field in most cases. In particular, if we have an elliptic curve defined by

y² = x³ + ax + b

which has discriminant

D = -4a³ - 27 b²

then we want to look at what happens if reduce everything modulo a prime p. As long as p isn’t a factor of D, everything works fine. If p is a factor of D, however, then we get a singular curve when we reduce mod p. For example, the curve

y² = (x - 3)(x - 8)(x + 11)

= x³ – 97x + 264

has no repeated roots over the complex numbers, which is reflected in its non-zero discriminant

D = 1768900

= 2² 5² 7² 19²

But because 19 is a factor of D, this curve becomes singular when we reduce everything modulo 19. In particular, we find that this curve becomes

y² = x³ – 97x + 264

≡ x³ + 17x + 17 (mod 19)

 ≡ (x + 11)² (x + 16) (mod 19)

The cubic part of the curve has multiple roots so it's singular over GF(19). Modulo 19 this curve also has discriminant

D = -4(17)² – 27(17)³

= -27455

≡ 0 (mod 19)

which also tells us that this curve is singular over GF(19).

Convergence of power series

Some thoughts on the convergence of power series - with pictures.

Consider the three functions

f₁(x) = 1 / (1 - x²)

f₂(x) = 1 / (1 + x²)

f₃(x) = √(1 + x²)

If we expand each of these in a power series around x = 0 we find that

f₁(x) = Σ x²ⁿ

f₂(x) = Σ (-1)ⁿx²ⁿ

f₃(x) = Σ (-1)ⁿx²ⁿ Binomial(1/2,n)

and that each converges for -1 < x < 1.

In the case of f₁, it's easy to see why that's the case. Here's the graph of f₁, and it behaves badly at -1 and 1.

In the case of f₂, it's not immediately obvious why reaching -1 and 1 causes problems. Here's the graph of f₂, and it certainly doesn't behave badly at all at these points.

On the other hand, the graph of what we get by summing the first few terms in the power series for f₂ looks like this, which does behave badly at -1 and 1.

This is easy to explain. If we look at |f₂| as a function of a complex variable, we see that f₂ has poles at i and –i, and the location of those poles limits the radius of convergence of the power series.

In the case of f₃, it's slightly more complicated. Here's what f₃ looks like. It also doesn't behave badly at -1 or 1.

Here's what |f₃| looks like as a function of a complex variable, and there aren't any poles there to cause problems. What's going on here?

What's causing problems in this case are the branch cuts that you need to define for f₃. Here's a graph of the imaginary part of f₃. Note that it's the locations of the branch cuts that limit the radius of convergence of the power series.

I don't recall being taught about branch cuts limiting the radius of convergence of a power series when I was in school. Like many other things, I'm not sure why this was overlooked.

Points of order three on elliptic curves

In an earlier post, we saw how it’s easy to tell which points on an elliptic curve y² = x³ + ax + b have order 2. What about order 3? That’s not much harder. If we have 3P = O then 2P =  –P, and we can use what we know about points of order 2 to find out what happens for points of order 3.

Let’s write

P₁= (x₁,y₁)

and

P₂ = 2P₁ = (x₂,y₂)

so that

 –P₁ = (x₁, –y₁)

From the earlier post on point doubling we have that

x₂ = (x₁⁴  – 2ax₁²  – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)]

If 2P₁ =  –P₁ then we have that

x₂ = x₁

or

(x₁⁴ – 2ax₁² – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)] = x₁

or

(x₁⁴ – 2ax₁² – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)] - x₁ = 0

so that

x₁⁴ – 2ax₁² – 8bx₁ + a² – 4x₁⁴ – 4ax₁² – 4bx₁ = 0

or that

3x₁⁴ + 6ax₁² + 12bx₁ – a² = 0

Example

For the elliptic curve y² = x³ + 1 we have that the x-coordinates of the points of order 3 need to have the property that

3x⁴ + 6ax² + 12bx – a² = 0

with a = 0 and b = 1 this means that we have

3 x⁴ + 12x  = 3x (x³ + 4) = 0

the only rational solution of which is x = 0. Thich corresponds to the points (0,1) and (0,-1) on the elliptic curve. Here’s what this looks like:

Another point of view

From the formula for doubling a point we get that

x₂ = m² – 2x₁

where

m = y′ = (3x₁² + a) / (2y₁)

And because x₂ = x₁ we can write

x₁ = m² – 2x₁

or that

m² = 3x₁

Now if we have that

y² = x³ + ax + b

then we have that

2 y y′ = 3x² + a

and that

2 y y′′  + 2 (y′)² = 6x

so that

y′′ = (6x – 2 (y′)²) / (2y)

This means that we have y′′ = 0 when

6x – 2 (y′)² = 0

or

(y′)² = 3x

or

m² = 3x

As we saw above, this happens at a point of order 3, so at a point of order 3 we have that y′′ = 0.

Using Pari for elliptic curves

I recently tried Pari, a piece of software that’s designed for doing number-theoretical calculations – like those you need to do in cryptography. After using it for a few hours, I have to say that I’m very impressed by it. It has lots of built-in functions for doing calculations involving elliptic curves, and because lots of the technology that we use at Voltage involves elliptic curves, I found that very useful.

On the other hand, Pari seems to assume that you already know a lot about things before you start using it. Here’s an example of defining the elliptic curve y² = x³ + 1 and finding all of the points of finite order on the curve:

 

The ellinit() function initializes a data structure for an elliptic curve, but what it tells you when it does this probably isn’t useful to most people. Here's how the Pari User's Guide explains the output of ellinit():

a1-a6,b2-b8,c4-c6: coefficients of the elliptic curve

area: volume of the complex lattice defining E

disc: discriminant of the curve

j: j-invariant of the curve

omega: [ω₁,ω₂], periods forming the basis of the complex lattice defining E (ω₁ is the real period and ω₂ belongs to Poincare's half-plane).

eta: quasi-periods [η₁,η₂] such that η₁ω₂ - η₂ω₁ = 2πi.

roots: roots of the associated Weierstrass equation

tate: [u²,u,v] in the notation of Tate

w: Mestre's w (this is technical)

The elltors() function finds all of the points of finite order. Its output is slightly more user-friendly, but it’s probably not obvious to most people what it’s telling you.

So overall, I’d have to say that I’m very impressed with Pari, and I’ll probably be using it a lot in the future. On the other hand, I can’t really recommend it for most people. If you feel comfortable reading Silverman’s The Arithmetic of Elliptic Curves, you’ll probably find it very useful. You'll also understand how to interpret the output of ellinit(). Otherwise, you might find its output a bit cryptic and tricky to interpret.

Visualizing complex multiplication

Here's an attempt to create a way to visualize elliptic curves with complex multiplication. With any luck, it will also give some insight into why the term "complex multiplication" is used.

An endomorphism of an elliptic curve is a homomorphism that maps points on the curve to other points on the curve. The multiplication-by-n maps

φ_n: P→ nP

all do this. For most elliptic curves, those are all the endomorphisms that exist, but some elliptic curves have other endomorphisms. Curves like those are said to have complex multiplication, and if we look at a few examples, it's not hard to see why it's called this.

Example 1

For the elliptic curve

y² = x³ + x

the mapping given by

φ(x,y) = (-x,iy)

is an endomorphism that’s not a multiplication-by-n map. It also has the property that

φ²(P) = φ∘φ(P) = (x,-y) = -P

Because φ² acts roughly like multiplication by -1, we can think of φ as acting roughly like multiplication by the complex number  i.

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = 1.85407 – 1.85407 i

and

ω₂ = 1.85407 + 1.85407 i

Note that ω₂ = iω₂.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

Here's what multiplication by i does to a typical point in this lattice:

 

Note that this lattice has the property that iL = L, so the same multiplication by i that maps points on the elliptic curve to other points on the curve also maps points in the lattice to other points in the lattice.

Example 2

For the elliptic curve

y² = x³ + 1

we have that the mapping given by

φ(x,y) = (ξx,y)

where

ξ = e^2πi/3, a complex cube root of 1 that's also a root of x² + x + 1 = 0

is an endomorphism that’s not a multiplication-by-n map. It also has the property that

φ³(x,y) = φ∘φ∘φ(x,y) = (x,y)

Because φ³ acts roughly like multiplication by 1, we can think of φ as acting roughly like multiplication by the complex number ξ.

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = 2.10327 -1.21433 i

and

ω₂ = 2.42865 i

Note that we have that ω₂ = ξω₁.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

Here's what multiplication by ξ does to a typical point in this lattice:

Note that this lattice has the property that ξL = L, so the same multiplication by ξ that maps points on the elliptic curve to other points on the curve also maps points in the lattice to other points in the lattice.

Example 3

Consider the elliptic curve

y² = x³ - 4320 x + 96768

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = -0.296858 i

and

ω₂ = 0.419821

Note that ω₂ = √2iω_1.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

In this lattice, if we multiply a point z by (√2i)² we get the point -2z. This looks something like this: 

This will also be reflected in the points on the elliptic curve, so this curve has complex multiplication by √2i. In this case, however, it's not at all obvious what the endomorphism is that's not a multiplication-by-n map.

Making change

My wife went out for pizza last week and came back with an incredible story. She ordered two pizzas on-line and went to the store to pick them up. When she arrived at the pizza store their computer was down. When she paid with cash, she was surprised to see the cashier pull out a calculator that she used to calculate the change due from my wife's purchase. The cashier explained that they had to use a calculator to figure out how much change to give a customer and that they would get fired if they were caught making change without the use of the calculator.

I'd guess that the pizza store didn't just make the use of calculators mandatory for no reason. They almost certainly did this because their employees couldn't do it accurately without a calculator.

It's somewhat popular these days to criticize the exit exam that California high school students have to pass to graduate. Opponents like to say that it forces teachers to teach just the material that's covered on the test, and that this reduces the overall quality of education. Supporters of the exam maintain that it's just testing basic skills and that its requirements are quite reasonable. If pizza stores have to require their employees to use calculators to make change accurately, I'd guess that the exit exam isn't testing enough.

The fact that people can pass the exit exam and still can't make change accurately may account for the following joke:

Question: What is 2+2?

Answer: A question on the California high-school exit exam

Another example of rational points on an elliptic curve

Here's another example of finding rational points of finite order on an elliptic curve.

Suppose that we have the elliptic curve y² = x³ - 2x + 1. In this case we have that D = 5, so that the possibilities for the y-coordinate of a rational point of finite order are limited to 0, ±1 by the Nagell-Lutz theorem. A quick check of these possibilities shows that we have the following points:

P₁ = (1,0)

P₂ = (0,1)

P₃ = (0,-1)

Here's what this looks like:

These points form this subgroup of the points on the curve:

Rational points on y² = x³ - 2x + 1

+	O	P1	P2	P3
O	O	P1	P2	P3
P1	P1	O	P3	P2
P2	P2	P3	P1	O
P3	P3	P2	O	P1

We can also think of the elliptic curve y² = x³ - 2x + 1 as being parameterized by the Weierstrass ℘-function with periods ω₁ and ω₂ where we have approximately

ω₁ = -2.01891 i

and

ω₂ = 2.96882

All of the points on y² = x³ - 2x + 1 that have the property 4P = O come from the complex numbers shown here: 

 
Of these 16 points, these are the ones that we get the subgroup of rational points of finite order from (z₁ corresponds to P₁, etc., and z₀ corresponds to O):

Why use projective coordinates?

Projective coordinates are often used to represent points on an elliptic curve. This is useful for two reasons. It provides an easy way to represent the point O on an elliptic curve using the same coordinate system that all of the other points use. It also may be more efficient to do operations on projective coordinates than on the usual, or affine, coordinates.

Projective coordinates represent ratios of numbers instead of just numbers. So the number 4 could be represented as either 4 = 4/1 or as 4 = 8/2, which we would write as (4,1) and (8,2) in projective coordinates. Clearly, there's not a unique way to represent affine points in projective coordinates.

To encode the point at infinity, we just set the last coordinate to 0, using division of anything by 0 to indicate infinity.

If we have to numbers x₁ and x₂ we can write them in projective coordinates as

x₁ = X₁/Z₁

or

(X₁,Z₁)

and

x₂ = X₂/Z₂

or

(X₂,Z₂)

If we want to calculate x₁/x₂ we can use the projective coordinates to find that

x₁/x₂ = (X₁/Z₁) / (X₂/Z₂)

= X₁Z₂ / X₂Z₁

which we can write as

(X₁Z₂,X₂Z₁)

in projective coordinates.

Note that this means that we've actually calculated x₁/x₂ without using any division operations at all. The tradeoff is that it takes more operations to implement projective operations. In this example, we've calculated x₁/x₂ without using any division operations, but at the cost of using two multiplications instead of one division. But if division operations are significantly more expensive that other operations, this can be a useful way to avoid using the more expensive operation.

There are actually more than one way to define projective coordinates in a useful way for points on elliptic curves. The most common way writes an affine point

P = (x,y)

as the projective point

P' = (X,Y,Z)

where

x = X/Z

and

y = Y/Z

This form of projective coordinates also has the advantage that division operations on coordinates can be implemented without using any division operations. Whether or not it's actually preferable to using affine coordinates depends on exactly how fast additions, subtractions, multiplications and divisions are on a particular platform.

The discriminant of an elliptic curve

 

If you're a fan of using high-powered techniques to solve easy problems, you can replace the first step with this.

Pokemon combinatorics

Collectable card games are incredibly popular. The cards for these games are typically sold in packages of several cards. The manufacturers print several sheets of cards, and include cards from the different sheets in these packages with different frequencies. They might include four cards from sheet A, two cards from sheet B and a single card from sheet C, calling the cards from sheet A “common,” the ones from sheet B “uncommon” and the cards from sheet C “rare.” Your ability to complete a collection of the entire set of cards is clearly limited by your ability to collect all of the rare cards.

How many packages of cards can you expect to have to buy before you complete a set?

A solution to this problem was described by Paul Erdős and Alfréd Rényi in 1961. Here’s roughly how their solution goes.

Suppose that we already have k different rare cards out of a total set of n possible cards. The next time we buy a pack of cards the probability to not get a new rare card is k/n so the probability that we need to buy exactly p packs of cards to get another new rare card is

(k/n)^p-1 (1 - k/n)

so the expected number of packs of cards that we’ll need to buy to a new rare card is

Σ_p≥1 (k/n)^p-1 (1 - k/n) p = 1 / (1 - k/n)

= n / ( n - k)

So the expected number of packs of cards that we’ll need to buy to get all n rare cards is

Σ_k=0:n-1 n / ( n - k) = n/n + n/(n - 1) + … + n/2 + n/1

= n (1/n + 1/(n - 1) + … + 1/2 + 1/1)

= n H_n

So you should expect to buy packs equal to about H_n times the number of rare cards to get a complete set. If there are 50 rare cards in a set, for example, you should expect to buy about H₅₀ (approximately 4.5) times 50, or about 225 packs to get a complete set.

Here's how H_n grows as a function of n:

So for the number of rare cards in a typical set of collectable cards, a good rule of thumb is that you can expect to have to buy a number of packs of cards equal to between four and five times the number of rare cards to complete your set.

Marginally interesting

 

Here's a picture of a notable page from a relatively unknown book. Apparently the right margin was just big enough to hold this:

Cubum autem in duos cubos, aut quadrato-quadratum in duos quadrato-quadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos eiusdem nominis fas est dividere cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

Elliptic curves - connected or not

The graphs of some elliptic curves have one component like this one, the graph of y² = x³ + 1.

 

Others have two components like this one, the graph of y² = x³ – 2x + 1.

It turns out to be easy to tell these two cases apart. If the elliptic curve is defined by the equation y² = x³ + ax + b and we write D = -4 a³ - 27 b², then if D > 0 then the graph of the elliptic curve has two components and if D < 0 then the graph has one component. Here’s why.

D is the discriminant of the cubic f(x) = x³ + ax + b. So if we write

x₃ + ax + b = (x – x₁)(x – x₂)(x – x₃)

then we have that

D = (x₁ – x₂)²(x₁ – x₃)²(x₂ – x₃)²

Whether the graph of y² = f(x) has one or two components is determined by how many real roots f(x) has. If there is a single real root then the graph crosses the x-axis once and the graph has a single component, like we get with y² = x³ + 1. If there are three real roots then the graph then the graph crosses the x-axis three times and the graph has two disconnected components, like we get with y² = x³ – 2x + 1.

If f(x) has three real roots then D is clearly positive. What about the case of a single real root and a complex conjugate pair of roots?

Let’s write the roots of f(x) as

x₁ = a + bi

x₂ = a - bi

x₃ = c

where a, b and c are real. We can then write

D = (x₁ – x₂)²(x₁ – x₃)²(x₂ – x₃)²

= ((a + bi)– (a – bi))²(a + bi – c)²(a - bi – c)²

= (2bi)²((a - c) + bi)²((a – c) – bi)²

= -4b²((a - c)² + b²)

which is always negative, just like we wanted.

Rational points on elliptic curves

If you look at the rules for adding points on an elliptic curve, you'll see that the coordinates of P₃ = P₁ + P₂ are rational functions of the coordinates of P₁and P₂. This means that if P₁and P₂ have rational coordinates then P₃ also does because its coordinates are rational functions of these rational coordinates.

It turns out that rational points on an ellipic curve also have other interesting properties. In particular, rational points of finite order have to have integer coordinates and the y-coordinate of these points has to either be 0 or divide the discriminant of the cubic that defines the elliptic curve. This is the Nagell-Lutz theorem, which is the following:

Let y² = x³ + ax + b be an elliptic curve with integer coefficients and let D = 4 a³ + 27 b². Then if P = (x_P,y_P) is a rational point of finite order then P has integer coordinates and either y_P = 0 or y_P²|D.

Example

Suppose that we have the elliptic curve y² = x³ + 1. In this case we have that D = -27, so that the possibilities for the y-coordinate of a rational point of finite order are limited to 0, ±1, ±3. A quick check of these possibilities shows that we have the following points, and the Nagell-Lutz theorem tells us that that's all of them:

P₁ = (-1,0)

P₂ = (0,1)

P₃ = (0,-1)

P₄ = (2,3)

P₅ = (2,-3)

Here's what this looks like:

 

It's also easy to check that these points plus O form a subgroup of the points on the curve. If you add any two of these points together you always get another of of these points. Here's this subgroup:

Rational points on y² = x³ + 1

+	O	P1	P2	P3	P4	P5
O	O	P1	P2	P3	P4	P5
P1	P1	O	P5	P4	P3	P2
P2	P2	P5	P3	O	P1	P4
P3	P3	P4	O	P2	P5	P1
P4	P4	P3	P1	P5	P2	O
P5	P5	P2	P4	P1	O	P3

We can also think of the elliptic curve y² = x³ + 1 as being parameterized by the Weierstrass ℘-function with periods ω₁ and ω₂ where we have approximately

ω₁ = 2.10327 + 1.21433 i

and

ω₂ = 2.42865 i

All of the points on y² = x³ + 1 that have the property 6P = O come from the complex numbers shown here: 

   

Of these 36 points, these are the ones that we get the subgroup of rational points of finite order from (z₁ corresponds to P₁, etc., and z₀ corresponds to O):

   

Degenerate elliptic curves

Suppose that we have an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

Many mathematicians require that the right hand side of that equation have no repeated roots and insist that you really don't have an elliptic curve if this happen. The benefit of doing this is that it saves a few words. If you don't do that then you need to be careful to say something like a "non-singular elliptic curve" instead of just an "elliptic curve" in most contexts. Because this post is about the cases where you have repeated roots, I won't follow this convention here.

What happens if we do have repeated roots?

Two repeated roots

For an example of this, consider the elliptic curve

y² = 4 (x - 1)² (x + 2)

= 4 x³ - 12 x + 8

or where

g₂ = 12

and

g₃ = -8

This corresponds to the Weierstrass ℘-function with periods

ω₁ = -π i / √3

and

ω₂ = ∞

or really only being having one period instead of two. If we plot the magnitude of this ℘-function, this is fairly obvious. Here's what that looks like.

Three repeated roots

There's essentially only one way to get three repeated roots, and that's the case when we have an elliptic curve that looks like

y² = 4 x³

or that

g₂ = g₃ = 0

If that happens, the ℘-function shows no periodic nature at all. Here's what a plot of its magnitude looks like in this case:

 

From the post a few days ago, we can see that in this case we have to have

℘(z) = z^-2

which explains the shape of this graph. We also have to have

℘′(z) = -2 z^-3

When we think of (x, y) as coming from (℘(z), ℘′(z)), we see that we have

y² = 4 x³

when this happens.

More interesting elliptic curve stuff

It turns out that we can easily tell some things about an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

Suppose that we get this elliptic curve from the Weierstrass ℘-function with periods ω₁ and ω₂. Then it turns out that we we can also write this elliptic curve as

y² = 4 (x - x₁)(x - x₂)(x - x₃)

where

x₁ = ℘(ω₁ / 2)

x₂ = ℘(ω₂ / 2)

and

x₃ = ℘((ω₁ + ω₂) / 2)

For an example of this, consider the elliptic curve

y² = 4 (x - 1)(x - 2)(x + 3)

= 4 x³ - 28 x + 24

which we get from the Weierstrass ℘-function with periods approximately

ω₁ = -1.48441 i

and

ω₂ = 2.01891

In this case, we find that 

℘(ω₁ / 2) = -3

℘(ω₂ / 2) = 2

and

℘((ω₁ + ω₂) / 2) = 1

Adding points on an elliptic curve

An interesting identity that can be proven for the Weierstrass ℘-function is that

det

℘(z1) ℘′(z1) 1 ℘(z2) ℘′(z2) 1 ℘(z1+z2) -℘′(z1+z2) 1

=

0

If we think about this for a while, we see that this is explains why addition of points on elliptic curves works the way it does. Here's why.

A fact that's usually covered in high-school algebra classes is that

det	x1 y1 1 x2 y2 1 x3 y3 1	=	0

if and only if the three points (x₁,y₁), (x₂,y₂) and (x₃,y₃) are colinear.

Now from the point of view of the correspondence that we saw in the previous post that identified the complex number z with the point (℘(z),℘′(z)) on an elliptic curve, let's write

P₁ = (℘(z₁), ℘′(z₁))

P₂ = (℘(z₂), ℘′(z₂))

and

P₃ = (℘(z₁+z₂), ℘′(z₁+z₂))

So the property of the ℘-function that's shown above tells us that although the points P₁, P₂ and P₃ aren't colinear, if we reflect P₃ across the x-axis to get -P₃, then we get three points that are.

So to find P₃ from P₁ and P₂, we need to first find the third point where the line that connects P₁ and P₂ intersects the elliptic curve. This point will be -P₃. Once we find that point, we reflect it across the x-axis to get P₃.

If we do this, we add the point P₁ that we get from z₁ to the point P₂ that we get from z₂ and get the point P₁ + P₂ = P₃ that we get from z₁ + z₂. In other words, adding points on an elliptic curve is really just adding complex numbers, but hidden by the mapping that takes z to the point (℘(z),℘′(z)) on the elliptic curve.

An example

For an example of how this works, let's look at the elliptic curve

y² = 4 x³ - 4x + 4

which we get from the Weierstrass ℘-function with periods approximately

ω₁ = -2.19658 i

and

ω₂ = 2.35354 + 1.09829 i

We have these two points on the curve

P₁ = (-1,2) = (℘(z₁),℘′(z₁)) for z₁ = 0.291202 + 1.09829 i

P₂ = (0,3) = (℘(z₂),℘′(z₂)) for z₂ = 0.73997 + 1.09829 i

for which we find that

P₃ = P₁ + P₂ = (1,-2) = (℘(z₃),℘′(z₃)) for z₃ = 1.03117

We also find that we have that

z₃ ≡ z₁ + z₂ (mod ω₁, ω₂)

just like we would expect to see.

Parameterizing elliptic curves

Here's an example of parameterizing an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

using the Weierstrass ℘-function.

Consider the elliptic curve

y² = 4 (x - 1)(x - 2)(x + 3)

= 4 x³ - 28 x + 24

This is a handy elliptic curve to use because we can easily see where its graph crosses the x-axis, etc. Identifying this with

℘′(z)² = 4 ℘(z)³ - g₂ ℘(z) - g₃

we have that

g₂ = 28

and

g₃ = -24

To plot the graph of this elliptic curve when it's parameterized as (℘(z), ℘′(z)) we first need to find the periods ω₁ and ω₂, which we can find from g₂ and g₃. Those turn out to be approximately

ω₁ = 1.48441 i

and

ω₂ = 2.01891

Here's what the magnitude of the corresponding ℘-function looks like over a few of its periods (graphed using Mathematica, as usual).

If we then plot the graph of (℘(z), ℘′(z)) as z goes along the real line from 0.7 to 1.4,  we get the following graph, which is the graph of y² = 4 x³ - 28 x + 24:

 

Another example

Doing the same thing for

g₂ = 4

and

g₃ = -4

and plotting the graph of (℘(z), ℘′(z)) as z goes along the real line from 0.7 to 4.0 we get this, which is the graph of y² = 4 x³ - 4 x + 4:

That's definitely another elliptic curve.

Why elliptic curves make sense

The way in which we can add points on an elliptic curve is often presented in a way that doesn't explain at all why adding points in that way makes sense. Adding points can roughly be summarized like this:

1. Draw a line through the two points that you want to add together
2. Find the third place where this line intersects the elliptic curve
3. Reflect that point across the x-axis and call the resulting point the sum of the first two points

Doing this actually makes perfect sense, but seeing why requires looking at a particular elliptic function called the Weierstrass ℘-function.

An elliptic function is a function of a complex variable that's doubly periodic: it has two periods instead of one. This means that we have both

f(z ) = f(z + ω₁)

and

f(z) = f(z + ω₂)

for complex numbers ω₁ and ω₂. 

It turns out that the function defined by

℘(z ) = z^-2 + Σ [ (z - ω)^-2 - ω^-2]

where the sum is over all ω = n₁ω₁ + n₂ω₂ not equal to zero, is an elliptic function with periods ω₁ and ω₂, and this particular elliptic function is called the Weierstrass ℘-function.

If we write

G_k = Σ ω^-2k

where the sum is over all ω = n₁ω₁ + n₂ω₂ not equal to zero, we find that we can write

℘(z) = z^-2 + 3 G₂ z² + 5 G₃ z⁴ + ...

and

℘′(z) = -2 z^-3 + 6 G₂ z + 20 G₃ z³ + ...

and that we can use these to find that we have that

℘′(z)² = ℘(z)³ - 60 G₂ ℘(z) - 140 G₃

For historical reasons it's traditional to write

g₂ = 60 G₂

and

g₃ = 140 G₃

so that we have that

℘′(z)² = ℘(z)³ - g₂ ℘(z) - g₃

If we write

 y = ℘′(z)

and

x = ℘(z)

we then have

y² = 4 x³ - g₂ x - g₃

which is just a quick change of variable away from the form that we usually see for an elliptic curve:

y² = x³ + a x + b

So it looks like we can parametrize an elliptic curve using the ℘-function just like we can parametrize a circle

x² + y² = 1

as

cos²t + sin²t = 1

using the usual trigonometric functions.

And just like understanding the properties of the trig functions tells us how to understand what's happening on a circle, understanding the ℘-function tells us how to understand what's happening on an elliptic curve. Like the addition of points.

More on that tomorrow.

Linear recursions and geometric series

As I mentioned in a previous post, one way to look at a linear recursion is as a matrix. When you do this, it's natural to think about the eigenvalues and eigenvectors of that matrix, and the eigenvectors turn out to be the initial conditions for the recursion that get it to greate a geometric series. We can use this fact to create an nth order recursion that creates n different geometric series of our choice, with the particular series being created determined by the initial conditions of the recursion. So if we pick any two numbers, it's possible to find a single second-order linear recursion that we can make create a geometric series with our chosen numbers as the ration of consecutive terms. Which ratio we get is determined by the initial conditions for the recursion.

Suppose that we write the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

as

xn-k+1 ... ... xn

=

0 1 ... 0 1 a0 a1 ... ak-1

xn-k ... ... xn-1

If λ is a solution to

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then

1 λ ... λk-1

is an eigenvector that corresponds to the eigenvalue λ, and this eigenvector is also the initial state that turns the recursion into a geometric series: if we have

x₀ = 1, x₁ = λ, x₂ = λ², …, x_k-1 = λ^k-1

then we’ll always have x_n = λⁿ.

This means that for an nth order recursion, we can pick any n values λ_i (which are exactly these eigenvalues), and find initial conditions for the recursion such that x_n = λ_iⁿ. The eigenvectors are the initial conditions that do this, and they get the recursion to create a geometric series with the ratio between successive terms being the eigenvalue which corresponds to the eigenvector. It's also easy to write down the recursion that does this for us. In particular, if the eigenvalues are the roots of

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

does this for us.

An example

Suppose that we want to find a second-order recursion that will create either the series

x_n = (-2)ⁿ

or

x_n = 3ⁿ

This corresponds to having

λ₁ = -2

and

λ₂ = 3

for the zeroes of

(x - λ₁) (x - λ₂) = (x + 2) (x - 3)

= x² - x - 6

so that the recursion

x_n+2 = x_n+1 + 6 x_n

will do this for us.

The initial conditions

x₀ = 1

and

x₁ = -2

give

x_n = (-2)ⁿ

and the initial conditions

x₀ = 1

and

x₁ = 3

give

x_n = 3ⁿ

The Fibonacci sequence, the golden ratio and Egyptian fractions

It turns out that there's a way to use the Fibonacci sequence to write the golden ratio in terms of Egyptian fractions. Here's how.

If we write the Fibonacci sequence as

f(n + 2) = f(n + 1) + f(n)

then we can write

f(n) = (aⁿ – bⁿ) / (a – b)

where

a = (1 + √5) / 2

and

b = (1 – √5) / 2

Using this form of f(n) it's easy to show that

f(n)² – f_n+1 f_n-1 = (-1)^n-1

which we can rewrite as

f_n+1 / f_n = f_n / f_n-1 + (-1)^n-1 / (f_n f_n-1)

But we also have that

f_n / f_n-1 = f_n-1 / f_n-2 + (-1)^n-2 / (f_n-1 f_n-2)

so that

f_n+1 / f_n = f_n-1 / f_n-2 + (-1)^n-2 / (f_n-1 f_n-2) + (-1)^n-1 / (f_n f_n-1)

If we keep making similar substitutions, we find that we get that

f_n+1 / f_n = f₂ / f₁ + 1 / f₁ f₂ - 1 / f₂ f₃ + … + (-1)^n-1 / f_n-1 f_n-2

The golden ratio a is the limit of f_n+1 / f_n as n gets large, so we have that

a = f₂ / f₁ + 1 / f₁ f₂ - 1 / f₂ f₃ + 1 / f₃ f₄ + …

= 1 + 1 - ¹⁄₂ + ¹⁄₆ - ¹⁄₁₅ + ...

Each of the terms in this sum happen to be fractions of the form ¹⁄_n for some integer n, which are exactly the so-called Egyptian fractions. Apparently, the classical Egyptians used only fractions of that form, plus the single additional fraction ²⁄₃, to represent all rational numbers.

If you try to actually do a few computations with Egyptian fractions, you'll probably come to the same conclusion that I did: that representing rational numbers this way is probably one of the greatest technical blunders of all time.

In any event, the above representation for the golden ratio that we got from the Fibonacci sequence is actually a way to represent it as a sum of Egyptian fractions. Yet another aspect of the Fibonacci sequence that I didn't expect.

The limits of provable security

I've never quite understood the objections that people have to cryptographic schemes that are provably secure. If you have a proof of security then one of two things must be true: either the scheme is secure or there's a flaw in the proof. There's no other possible case.

All of the technologies that Voltage's products use have such proofs. The Boneh-Franklin IBE, the Boneh-Boyen IBE and our format-preserving encryption technology all have such proofs that have been published in peer-reviewed research journals. Because of this, I often don't understand the questions that I sometimes get about the security of our technologies.

Here's a situation that I've seen more than once. Someone asks about the security of our FPE technology, for example. We'll point them to the paper by cryptographers John Black and Phil Rogaway that has a proof for the security of the scheme. The next question is essentially, "But why should I believe that it's secure?" At that point, I'm never quite sure what to say next. If you have a proof in front of you, then either the proof is correct or there's an error in the proof. If this proof is of the security of a cryptographic scheme, then either the scheme is secure or there's an error in the proof. As mentioned above, there's no other possible alternative.

My recent experiences have led me to believe that there's a fundamental problem with this approach, and that's because many people really aren't comfortable with the idea of a proof. I've seen many cases recently where people essentially accept P and NOT P at the same time and don't seem bothered by doing this.

Every time I see this, I start thinking about the logical implications of it. After all, if you accept both P and NOT P then you can prove that absolutely anything is true. "If 2 = 3 then all cats are dogs" is absolutely true, for example. But because many people either don't understand this or don't believe this, I've come to the conclusion that proofs of security really aren't that useful. They may help specialists make sure that their work is correct, but to non-specialists they really don't say anything useful.

More patterns in the Fibonacci and Lucas sequences

More observations about the Fibonacci and Lucas sequences.

As before, suppose that we have a second-order linear recursion given by

x_n+2 = A x_n+1 + B x_n

and we write

x² – A x – B = (x – a) (x – b)

where

a = (1 + √(A² + 4 B)) / 2

and

b = (1 – √(A² + 4 B)) / 2

For a Fibonacci-like sequence we have that

f(n) = (aⁿ – bⁿ) / (a – b)

and for a Lucas-like sequence we have that

g(n) = aⁿ + bⁿ

Now if we look at

(a + b)ⁿ = aⁿ + … + bⁿ

we see that all but the first and last terms are divisible by ab so that

(a + b)ⁿ ≡ aⁿ + bⁿ (mod ab)

We can write

x² – A x – B = (x – a) (x – b)

= x² – (a + b) x + ab

so that

A = - (a + b)

and

B = ab

This means that we can write

g(n) = aⁿ + bⁿ

≡ (a + b)ⁿ (mod ab)

Or that

g(n) ≡ Aⁿ (mod B)

which looks like an interesting relationship.

Similarly, we can write

f(n) = (aⁿ – bⁿ) / (a – b)

= a^n-1 + … + b^n-1

≡ a^n-1 + b^n-1 (mod ab)

≡ g(n - 1) (mod ab)

≡ A^n-1 (mod B)

or that

f(n) ≡ A^n-1(mod B)

which also seems to be an interesting relationship.

Another form of the Lucas sequence

As before, let’s write the nth tem of the Lucas seqence as

g(n) = aⁿ + bⁿ

Just like in the previous post, let's write

z = (n / 2) log (a / b)

so that

2 cos iz = 2 cos [ (i n / 2) log (a / b) ]

=  e ^{(n/2) log (a/b)} + e ^{- (n/2) log (a/b)}

= (a / b) ^n/2 + (a / b) ^-n/2

= (aⁿ + bⁿ) / (ab) ^n/2

Solving for

g(n) = aⁿ + bⁿ

we find that

g(n) = 2 (ab) ^n/2 cos [ (in / 2) log (a / b) ]

which is very similar to the form of the Fibonacci sequence that we found earlier that involved the sine function:

f(n) = - [ 2 i (ab) ^n/2 / (a – b) ] sin [ (in / 2) log (a / b) ]

If we have the recursion

g(n + 2) = g(n + 1) - g(n)

for example, with

g(0) = 2

and

g(1) = 1

we find that we get

g(2) = -1

g(3) = -2

g(4) = -1

g(5) = 1

g(6) = 2

where the sequence 2, 1, -1, -2, -1, 1 starts over again.

Because we can write this sequence as

g(n) = aⁿ + bⁿ

where

a = (1 + i √3) / 2

and

b = (1 - i √3) / 2

we can use the fact that

g(n) = 2 (ab) ^n/2 cos [ (in / 2) log (a / b) ]

to find that

g(n) = 2 cos( n π / 3)

much like we did in one of the previous posts.

Because we have

f(n) = - [ 2 i (ab) ^n/2 / (a - b) ] sin [ (in / 2) log (a / b) ]

and

g(n) = 2 (ab) ^n/2 cos [ (in / 2) log (a / b) ]

it seems reasonable to look for a relationship that's much like the complex exponential, where

e^iz = cos z + i sin z

perhaps something that contains lots of HTML entities for Greek letters like

ε^{ι n} = g(n) + ι f(n)

It doesn't quite look like anything nice and clean is possible, although if we write

ι = a - b

then it looks like we can write

g(n) + ι f(n) = 2 aⁿ

and

g(n) - ι f(n) = 2 bⁿ

That may be as close as we can get. 

Fibonacci, Lucas and Pell sequences

Even more stuff that I stumbled across while thinking about the Fibonacci sequence while trying to get into the right frame of mind to think about harder things.

Suppose that we have a recursion defined by

f(n + 2) = A f(n + 1) + B f(n)

We can write this as

f(n) = α aⁿ + β bⁿ

where 

a = (A + √(A² + 4 B) / 2

and

b = (A - √(A² + 4 B) / 2

If we have that

f(0) = 0

and

f(1) = 1

like with we do with the Fibonacci sequence, then we find that

α = 1 / (a – b)

and

β = -1 / (a – b)

so that

f(n) = (aⁿ – bⁿ) / (a – b)

Suppose that we want to get other interesting forms of f(n) like where

α = 1

and

β = 1

so that

f(n) = aⁿ + bⁿ

It’s easy to show that we can get this when

f(0) = 2

and

f(1) = A

which gives what’s called the Lucas sequence when A = 1.

It’s also easy to show that if we want to make sure that we have

f(n) = (aⁿ + bⁿ) / (a + b)

then we need to have

f(0) = 2 / A

and

f(1) = 1

If we want to have integer values, making A = 2 is a reasonable way to try to do this. This gives us the Pell sequence, which is defined by the recursion

f(n + 2) = 2 f(n + 1) + f(n)

Finally, that if we want to make sure that we have

f(n) = aⁿ - bⁿ

or

α = 1

and

β = -1

then we find that we get this when

f(0) = 0

and

f(1) = a – b = √(A² + 4B)

We can get this to be an integer, for example, if we have that

A = 3

and

B = 4

or from the recursion

f(n + 2) = 3 f(n + 1) + 4 f(n)

with

f(1) = 5

That seems to cover the interesting cases, or at least the ones that I had time to think about today.

In any event, this might give us some idea of how Lucas and Pell came to think about the sequences that now carry their names.

The polar decomposition of the Fibonacci sequence

If we think about the matrix form of the Fibonacci recursion:

f(n + 1) f(n + 2)

=

0 1 1 1

f(n) f(n + 1)

a natural question to ask is what the polar decomposition of the matrix

A

=

0 1 1 1

tells us about the recursion and the sequence that it generates.

To get the polar decomposition of the matrix A we write it as

A = PU

where P is positive definite and U is unitary. 

Writing a matrix in its polar decomposition is much like writing a complex number as

z = r e^iθ

where the positive definite part of the polar decomposition corresponds to the magnitude of the complex number and the unitary part of the polar decomposition corresponds to the rotational part of the complex number.

In the case of the Fibonacci recursion we find that

P

=

(1/√5)

2 1 1 3

and

U

=

(1/√5)

-1 2 2 1

so that

P2

=

1 1 1 2

P3

=

(1/√5)

3 4 4 7

P4

=

2 3 3 5

etc., and that U² = I.

 

In general, I'd guess that for a nth-order linear recursion, we'll always have that Uⁿ = I. That shouldn't be too hard to show.

As we saw before, A has eigenvalues

a = (1 + √5) / 2

and

b = (1 - √5) / 2

while in this case we find that P has eigenvalues a and -b while U has eigenvalues 1 and -1.

I'm not sure how useful this polar decomposition will be, but I feel fairly sure that I'll find a use for it some day.

Not quite the Fibonacci sequence

If instead of the recursion that we use to get the Fibonacci sequence:

f(n + 2) = f(n + 1) + f(n)

what happens if we change the sign of the coefficient of f(n) to get the recursion

f(n + 2) = f(n + 1) - f(n)

instead?

With the initial conditions

f(0) = 0

and

f(1) = 1

we get

f(0) = 0

f(1) = 1

f(2) = 1

f(3) = 0

f(4) = -1

f(5) = -1

f(6) = 0

f(7) = 1

at which point it's obvious that we'll just keep cycling through the pattern 0, 1, 1, 0, -1, -1 again. This probably means that the corresponding function of a real variable f(x) probably has an interesting graph. What does this look like?

We have that

f(x) = (a^x - b^x) / (a - b)

where

a = (1 + i √3) / 2

and

b = (1 - i √3) / 2

which means that we also have that

ab = 1

a - b =  i √3

and

(a / b) = (-1 + i √3) / 2 = exp ( 2 π i / 3 )

so that

|a / b| = 1

and

arg (a / b) = 2 π / 3

and that 

log (a / b) = log( |a / b| ) + i arg (a / b) = 2 π i / 3

We can substitute these into the expression from yesterday's post:

f(n) = - [ 2 i (ab) ^n/2 / (a – b) ] sin [ (i n / 2) log (a / b) ]

to find that

f(n) = (2 / √3) sin ( n π / 3)

so that the graph of f(x) just looks like this:

That's not quite as interesting as the graphs that we got from the Fibonacci sequence, is it?

Another form of the Fibonacci sequence

Another possibly-interesting observation about the Fibonacci sequence that I came across recently. 

As before, let’s write the nth tem of the Fibonacci seqence as

f(n) = (aⁿ – bⁿ) / (a - b)

where

a = (1 + √5) / 2

and

b = (1 – √5) / 2

Now we have that

e ^iz = cos z + i sin z

so that

e ^z = cos iz + i sin iz

and

e ^-z = cos iz – i sin iz

Combining these, we get that

 - 2 i sin iz = e ^z - e ^-z

Now for the step that seems like magic (although it’s really the result of working backwards to get things to work out the way we want them to), write

z = (n / 2) log (a / b)

Using this definition of z we find that

- 2 i sin iz = - 2 i sin [ (i n / 2) log (a / b) ]

=  e ^{(n/2) log (a/b)} – e ^{- (n/2) log (a/b)}

= (a / b) ^n/2 – (a / b) ^-n/2

= (aⁿ – bⁿ) / (ab) ^n/2

Solving for

f(n) = (aⁿ – bⁿ) / (a - b)

we find that

f(n) = - [ 2 i (ab) ^n/2 / (a – b) ] sin [ (in / 2) log (a / b) ]

I'd never seen that form for the Fibonacci sequence before. I'm not sure how useful this is, but I found it a bit surprising.

More uses for eigenvalues and eigenvectors

It turns out that looking at eigenvalues and eigenvectors may be useful for more than thinking about linear recursions like the Fibonnaci sequence. They're also be useful when thinking about special relativity. In this case we have that the coordinates (x',t') in a frame of reference moving at velocity v relative to a stationary frame of reference are related to the coordinates (x,t) in the stationary frame of reference by

x' t'

=

γ

1 -v -v 1

x t

where γ = 1 / √(1 - v²) and speed of light is normalized to c = 1.

Now the matrix

γ

1 -v -v 1

has eigenvectors

 

-1 1

and

1 1

which correspond to the eigenvalues γ(1 + v) and γ(1 - v) respectively. One interpretation for this is that the natural coordinates system to use has  

-1 1

and

1 1

for its basis instead of

1 0

and

0 1

If we had use those coordinates, lots of physics would be much simpler. On the other hand, that would also make it more difficult to actually make any measurements. Maybe our current system isn't really so bad after all.

More on the Fibonacci sequence

Another observation based on thinking about the Fibonacci sequence. This one relates to what you get when you write the action of a linear recursion as a matrix and what the eigenvalues and eigenvectors of this matrix tell us.

Another way to write a linear recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

is as

xn-k+1 ... ... xn

=

0 1 ... 0 1 a0 a1 ... ak-1

xn-k ... ... xn-1

Because we have a matrix, it’s natural to think about the eigenvalues and eigenvectors of the matrix and what they mean. In this case, finding these is actually fairly easy.

If λ is a solution to

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then we have that

0 1 ... 0 1 a0 a1 ... ak-1

1 λ ... λk-1

=

λ λ2 ... λk

or that

1 λ ... λk-1

is an eigenvector that corresponds to the eigenvalue λ. This eigenvector is also the initial state that turns the recursion into a geometric series: if we have

x₀ = 1, x₁ = λ, x₂ = λ², …, x_k-1 = λ^k-1

then we’ll always have x_n = λⁿ.

In the case of the Fibonacci recursion, for example, we have that 

a = (1 + √5) / 2  

and

b  = (1 - √5) / 2

are the eigenvalues of the matrix

0 1 1 1

and correspond to the eigenvectors

1 a

and

1 b

respectively. These are the initial conditions that get the Fibonacci recursion to produce a geometric series. If we have x₀ = 1 and x₁ = a, for example, then we’ll always have x_n = aⁿ.

Visualizing the Fibonacci sequence

Here are few interesting things I came across recently when I was thinking about the Fibonacci sequence. In particular, it involves visualizing the Fibonacci sequence.

The Fibonacci sequence is defined by the recurrence

f(n) = f(n - 1) + f(n - 2)

where

f(0) = 0

and

f(1) = 1

It's easy to show that we can also write

f(n) = (aⁿ – bⁿ) / (a - b) 

where

a = (1 + √5) / 2

and

b = (1 - √5) / 2

It's also easy to see the behavior of f(n) for negative values of n: we have that

f(-n) = (-1)ⁿ⁺¹ f(n)

What happens if we think of f as a function of a real variable instead of an integer variable?

In this case we have the function

f(x) = (a^x – b^x) / (a - b)

This turns out to be a complex-valued function that happens to have a real part of zero at integer values. If we graph f(x) for 0 ≤ x ≤ 5, it looks like this (the complex value z = x + i y is plotted as (x, y)): 

If we graph f(x) for -5 ≤ x ≤ 0, it looks like this:

 

In that graph we can easily see how the fact f(-n) = (-1)ⁿ⁺¹ f(n) is reflected.

To see what the graph for both positive and negative values of x look like together, here's the graph of f(x) for -4 ≤ x ≤ 5:

 

 

What about derivatives of f(x)? 

It's fairly easy to see that 

f⁽ⁿ⁾(x) = (α_n a^x - β_n b^x) / (a - b) 

where

α_n = (log a)ⁿ

and

β_n = (log b)ⁿ

so that the graph of f⁽ⁿ⁾ looks somewhat similar to the graph of f.

Here's how the graphs of f, f' and f'' look, for example:

 
If we look at how the differences between Fibonacci numbers behave, like

Δf(n) = f(n + 1) - f(n) = f(n - 1)

we might expect to see this reflected in f', but there doesn't appear to be a nice, clean relationship like

f'(x) = f(x - 1)

I'm not even sure how close you can get in this particular case.

Ideal lattices

Ideal lattices have been mentioned a lot recently, particularly in association with Gentry's homomorphic encryption scheme. Exactly what is an ideal lattice?

Let's suppose that we know what a vector space is. With a vector space over the real numbers, for example, we have a set of vectors called a basis, and all of the sums of real multiples of the basis elements form the vector space. If we look at sums of integer multiples of the basis elements, that's a lattice. We can think of the basis as generating a lattice, and to call it a set of generators in that context.

An ideal is a generalization of the idea of "even numbers" or "multiples of 3." A bit more precisely, a set is an ideal if it fulfills two conditions. First, if we add elements in the ideal, we get something else that's also in the ideal. If you add two even numbers you get another even number, for example. We also have the property that if we multiply something in the ideal by something outside the ideal, we get something back in the ideal. That's just like what we get when we multiply any integer by an even integer and get another even integer.

If we have an ideal, we can use its generators as the basis for a lattice, so for every ideal there’s a lattice that we can associate with it in a fairly natural way. Suppose that we look at polynomials with integer coefficients, for example. In this case, if we have the ideal generated by 1 and x, the lattice with basis 1 and x corresponds to this ideal in a natural way.

Not every lattice corresponds to an ideal in the same way, however. If we consider the lattice which has 1 and 2x as its basis, we find that there's no ideal that corresponds to this lattice. The element x, which we can get by multiplying x (from outside the lattice) by 1 (from inside the lattice), isn’t an element of the lattice. This means that this example doesn’t meet the conditions necessary for an ideal, so there’s no ideal that corresponds to the lattice.

Since not every lattice corresponds to an ideal in this way, those that do are interesting, and these are what are called ideal lattices. They’re the framework used to create Gentry’s homomorphic encryption scheme, which is probably the most interesting use of ideal lattices discovered so far.

The Tate pairing

Suppose that P and Q are points on an elliptic curve and that the order of P is n. Let f_P be a rational function equivalent to n(P) – n(O) and D_Q be the divisor (Q) – (O). Then the Tate pairing of P and Q is e(P, Q) = f_P(D_Q).

We know how to get f_P and how to evaluate it at a divisor, but the fact that evaluating f_P at the divisor (Q) – (O) would require evaluating f_P at the point O causes trouble. But if R is another point not equal to O, it turns out that we get the same answer when we evaluate f_P at (Q + R) – (R) as we do when we evaluate f_P at (Q) – (O). This means that we can find e(P, Q) by doing the following:

1. Find f_P as we described previously.
2. Pick a random R.
3. Calculate e(P, Q) = f_P(Q + R) / f_P(R).

That’s all there is to it. When I first heard about the use of the Tate pairing in Boneh-Franklin identity-based encryption, for example, I used this very approach to implement the Tate pairing in Mathematica, and it was good enough for that purpose. There are lots of ways to make this calculation more efficient, but for small values of n, what we’ve described is fairly simple to implement.

Evaluating a rational function at a divisor

To evaluate the pairings that we need in pairing-based cryptography, we need to evaluate the rational function that we get from a divisor at another divisor. To understand how to do this, we need to understand what it means to evaluate a rational function at a divisor. This turns out to actually be fairly straightforward.

Suppose that we have a divisor

D = S n_i(P_i)

and want to evaluate a rational function f at D to get f(D). We do this by calculating 

f(D) = P f(P_i)^(n_i)

In the case of the divisors that we’re interested in, we’ll get a rational function of two variables x and y, and we’ll need to think of a point on an elliptic curve as being a point P = (x, y) to evaluate the rational function at the point.

For example, suppose that

P₁ = (-1, 0)

P₂ = (1,1)

D = 2(P₁) – 2(P₂)

and

f(x, y) = (x + y – 1) / (y – 2).

Then we can find

f(D) = f(P₁)² f(P₂)^-2

= f(P₁)² / f(P₂)²

Using P₁ = (-1, 0) we find that

f(P₁) = (-1 + 0 -1) / (0 – 2)

= 1

Using P₂ = (1, 1) we find that

f(P₂) = (1 + 1 – 1) / (1 – 2)

= -1

Combining these, we find that

f(D) = f(P₁)² / f(P₂)²

= 1² / (-1)²

= 1

Getting a rational function from n(P) - n(O)

In a previous post we saw how to add divisors like (P₁) – (O) and (P₂) – (O) and reduce the sum to the form (Q) – (O). Suppose that P is a point of order n and see what happens when we use this approach to evaluate

n(P) – n(O) = (P) – (O) + …+ (P) – (O)

We can do this by first finding

(P) – (O) + (P) – (O) = (2P) – (O) + div(f₁)

where we’ve written f₁ = u₁ / v₁ where u₁ is the line through P and P, and v₁ is the vertical line through 2P and -2P.

Next, we can find

3((P) – (O)) = (P) – (O) + (2P) – (O) + div(f₁)

= (3P) – (O) + div(f₁f₂)

where we’ve written f₂ = u₂ / v₂ where u₂ is the line through P and 2P and v₂ is the vertical line through 3P and -3P.

We can continue this process until we get to

n((P) – (O)) = (nP) – (O) + div(f₁…f_n-1)

= (O) – (O) + div(f₁…f_n-1)

= div(f₁…f_n-1)

Note that by doing this, we’ve found a way to write n(P) – n(O) as the divisor of the rational function f_P = f₁…f_n-1. To calculate the pairings that we need for pairing-based cryptographic algorithms, we want to evaluate f_P, and we can get this f_P through the process that’s described above. That’s almost enough to define how to evaluate the Tate pairing. The rest of what’s needed will be the topic of tomorrow’s post.

Divisors on elliptic curves

Divisors on elliptic curves are important in pairing-based cryptography. They’re useful because the structure that an elliptic curve provides lets you reduce sums of divisors down to simpler sums.

Suppose that we have several divisors

D₁ = (P₁) – (O)

D₂ = (P₂) – (O)

…

D_n = (P_n) – (O)

We can always add the divisors D₁ through D_n to get

D = D₁ + …+ D_n

= (P₁) + … + (P_n) + n(O)

but this gets unwieldy very quickly.

In particular, for cryptographic applications, we want to use a value of n that has at least 160 bits, and we certainly don’t want to think about manipulating a divisor that has 2¹⁶⁰ terms. Fortunately, elliptic curves provide the structure needed to make a calculation like this feasible because they provide a way to reduce a sum of the form (P₁) – (O) + (P₂) – (O) to another divisor of the form (Q) – (O), which keeps the number of terms manageable. Here’s how we can do this.

Suppose that P₁ and P₂ are two points on an elliptic curve and that P₃ = P₁ + P₂. Let u be the line through P₁, P₂ and –P₃, and let v be the line through P₃ and –P₃.The following picture shows how this looks.

Now let's think of points on the elliptic curve as poles and zeroes that define a divisor, so that u has zeroes at P₁, P₂ and –P₃ plus a pole of order 3 at O and v has zeroes at P₃ and –P₃ plus a pole of order 2 at O. This means that we can write

div(u) = (P₁) + (P₂) + (–P₃) – 3(O)

and

div(v) = (P₃) + (–P₃) – 2(O)

Now note that we look at div(u) – div(v) we find that

div(u) – div(v) = (P₁) + (P₂) + (–P₃) – 3(O) – ((P₃) + (–P₃) – 2(O))

= (P₁) + (P₂) – (P₃) – (O)

= [(P₁) – (O)] + [(P₂) – (O)] – [(P₃) - (O)]

or that

[(P₁) – (O)] + [(P₂) – (O)] = (P₃) - (O) + div(u/v)

So if D₁ = (P₁) – (O) and D₂ = (P₂) – (O), this gives us a way to find D₁ + D₂ in a way that keeps the sum in the form (Q) – (O). If we apply this trick again and again, this gives a way to calculate a sum like D = D₁ + …+ D_n, and to do it in a way that keeps the number of terms in the sum small.

As we do this, we’ll accumulate a product of rational functions from the div(u / v) contributions, and in a future post we’ll see how to use that to get a way to evaluate the divisors that we need in pairing-based cryptography.

Exactly how do you find the rational functions u and v?

Suppose that you have u: y = mx + b, or y – mx – b = 0. If that’s the case, you have u(x, y) = y – mx – b.

Suppose that you have v: x = c, or x – c = 0. If that’s the case, you have v(x, y) = x – c.

Divisors

Certain functions called pairings are an important part of the mathematical machinery that make pairing-based cryptographic algorithms possible. Pairings, in turn, are based on the idea of a divisor. These divisors aren’t those you see in elementary number theory, where 4 is a divisor of 12, for example. Instead, they’re a way of keeping track of the zeroes and poles of a rational function.

The zeroes and poles of a rational function define the rational function up to multiplication by a constant. So if we know that we have a rational function with a zero of order two at x = 1 and a pole of order one at x = 2, then the function has to look like

f(x) = c (x – 1)² / (x – 2)

A divisor is a way to keep track of the zeroes and poles of a rational function by using a notation that looks much like addition of integers. We write the divisor of f as

div(f) = 2(1) – (2) – (¥)

What’s in the parentheses tells us where we have a zero or pole and the coefficient in front of the parentheses tells us the order of the zero or pole. Positive numbers indicate a zero; negative numbers indicate a pole. Note that this particular rational function also has a pole at x = ¥, and the divisor that we write for it reflects this.

So if we write

div(f₁) = (3) - (¥)

that tells us that f₁is a rational function with a zero at x = 3 and a pole at x = ¥, so that, up to a constant factor, f₁ looks like

f₁(x) = x – 3

We can add divisors by adding the coefficients of like terms, so that if

div(g) = (3) - 2(1) + (¥)

which corresponds to

g(x) = (x – 3) / (x – 1)²

then we can add div(f) and div(g) to get

div(f) + div(g) = 2(1) – (2) - (¥) + (3) - 2(1) + (¥)

= (3) – (2)

which corresponds to the rational function

h(x) = (x – 3) / (x – 2)

Clearly, adding divisors corresponds to multiplying rational functions, and if we define subtraction in the natural way, it corresponds to dividing rational functions. So we can write

div(f) + div(g) = div(fg)

and

div(f) – div(g) = div(f / g).

Note that the divisor div(1) acts much like 0 does in the integers. In the integers, adding or subtracting 0 doesn't change the value of an integer. The divisor div(1) behaves the same way:

div(f) + div(1) = div(f)

and

div(f) - div(1) = div(f)

The notation for divisors isn’t quite the same as addition, because we can’t simplify divisors by reducing (1) – (1) to div(1), for example.

Tomorrow: divisors on elliptic curves.

Picturing the central limit theorem

The central limit theorem tells us that if we add data that contains random errors then we tend to get a sum that's normally distributed, independent of the distribution of the original data. I was wondering how many errors you need to add together to get something that looked close to a normal distribution, so I created some random data from a uniform distribution in Mathematica that represents such errors. I then and plotted one of these errors, the distribution of the sum of two of these errors and the distribution of the sum of three of these errors. Here's what I got.

One random error.

The distribution of the sum of two random errors.

The distribution of the sum of three random errors.

It certainly looks like you're fairly close to a normal distribution after adding together only three errors. I was surprised to see how quickly this happened.

The Chinese remainder theorem

Supose that n₁, n₂, …, n_k are positive integers that are have no common factors. Then the Chinese remainder theorem (CRT) tells us that for any integers a₁, a₂, …, a_k there is an integer x that satisfies the following system of congruences:

x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

…

x ≡ a_k (mod n_k)

and that all solutions are congruent modulo the product N = n₁n₂…n_k. The CRT is particularly useful to know if you’re doing some of the number-theoretical calculations that you do in cryptography.

It turns out that the algorithm that’s used to get a solution the CRT is really just Lagrange interpolation in disguise. With Lagrange interpolation we find a solution to be

f(x) = d₁(x) y₁ + d₂(x) y₂ + … + d_k(x) y_k.

With the CRT we find a solution to be

x = d₁(n₁) a₁ + d₂(n₂) a₂ + … + d_k(n_k) a_k (mod N).

In both cases the ds have the property that d_i(n_j) = 1 if i = j and 0 if i ≠ j. They’re calculated differently, but their role in the calculation is really the same: to force a value of 1 in one particular case and a value of 0 in all other cases.

In the case of the CRT, here's how we do this. We first notice that N and N/n_i are relatively prime. There's essentially only one trick that you can use when things are relative prime, and that's to use the fact that we can find u_i and v_i such that u_i n_i + v_i N/n_i = 1. If we write d_i(n_j) = v_i N/n_j  modulo n_j, then this acts just we want it to.

We have u_i n_i + v_i N/n_i = 1, so that we have v_i N/n_i ≡ 1 (mod n_i), or that d_i(n_i) = 1.

And because n_j | (N/n_i) when i ≠ j, we also have that d_i(n_j) = v_i N/n_j ≡ 0 (mod n_i ) when  i ≠ j.

As I mentioned in the previous post about Lagrange interpolation, when I was in school, every teacher that I had presented Lagrange interpolation as a nasty formula involving lots of complicated expressions. The same thing was true for me with the CRT. Every time I saw this in a class, it was always presented as a nasty formula involving lots of complicated expressions. Nobody ever pointed out that it’s really the same thing as Lagrange interpolation.

I have to wonder why this was taught this way. If you understand what either Lagrange interpolation or the CRT is trying to do, it’s easy to reconstruct the complicated expressions that you need to calculate. If you don’t understand what they’re trying to do, you end up trying to memorize some complicated expressions and hoping that you get it right. I hope that things are taught differently these days. Its easy for me learn patterns and apply them in other places. It’s hard for me to memorize lots of stuff, particularly when I don’t understand exactly what I’m memorizing. I'm probably not alone in this, and I hope that the way things are taught today reflects this.

Lagrange interpolation

Lagrange interpolation is another thing that I wish that I’d had explained better to me when I was in school. There’s actually a connection between this and something that’s related to cryptography, but I won’t have a chance to mention that until tomorrow’s post. I only have enough patience to type and correct a little bit of math each day, and getting to the crypto connection would definitely take more than my entire daily supply of patience.

Lagrange interpolation is a way to create a polynomial that fits a sequence of data points (x₁,y₁),…(x_n,y_n). The way to do this is to create polynomials δ_i(x) that have the property that δ_i(x_j) = 1 if i = j and 0 if i ≠ j. If we have these, then we know that the polynomial

f(x) = δ₁(x) y₁ + δ₂(x) y₂ + … + δ_n(x) y_n

has to fit the data points that we’re given. At x = x₁, all of the terms of f(x) are equal to 0 except δ₁(x₁) y₁, which happens to reduce to y₁, at x = x₂, all of the terms of f(x) are equal to 0 except δ₂(x₂) y₂, which happens to reduce to y₂, etc.

Now let

p(x) = (x – x₁) (x - x₂) … (x - x_n),

and p_i(x) be p(x) with the factor (x – x_i) left out. This p_i(x_j) is almost what we want. We have that p_i(x_j) = 0 if i ≠ j but we don’t have that p_i(x_j) = 1 when i = j.

That’s easy to fix, though. If we divide p_i(x_j) by p_i(x_i) then we’re done. That forces a value of 1 when i = j and a value of 0 when i ≠ j. So if we define δ_i(x) = p_i(x_j) / p_i(x_i) then this gives us what we want, and the polynomial

f(x) = δ₁(x) y₁ + δ₂(x) y₂ + … + δ_n(x) y_n 

has to fit the data points that we’re given.

Lagrange interpolation seems fairly simple once you see what you’re trying to do: you’re just creating polynomials that are forced to fit your data because of the way they’re constructed. When I was in school, however, it was never explained to me that way. Instead, it was just written down as a big, complicated expression involving lots of sums and products and it was left to the students to figure out what was really going on. And because it was presented that way, the connection to the topic of tomorrow’s post wasn’t obvious at all.

Things that I didn't need to memorize

There are several things that I wish that I'd learned in school that nobody got around to teaching me. I had to figure these out on my own, and I still don't quite see why these things were overlooked by the teachers or professors that I had. Here's an example of this, and it has to do with trigonometry. It turns out that there's a quick and easy way to get the double-angle formulas for sines and cosines, or how to find sin 2x or cos 2x in terms of sin x and cos x. The easy way to do this is by looking at how the complex exponential works.

We know that

e^ix = cos x + i sin x

so we can write

e^2ix = cos 2x + i sin 2x.

We can also write

e^2ix = e^ix e^ix = (cos x + i sin x) (cos x + i sin x)

= cos²x - sin²x + 2i sin x cos x.

When we compare the real and imaginary parts of these two different ways of writing e^2ix we find that

cos 2x =  cos²x - sin²x

and

sin 2x =  2 sin x cos x

which are the double-angle formulas from trigonometry. You can use the same trick, of course, to get similar expressions for cos 3x, sin 3x, etc.

For me, it's much more useful to know a way to get these formulas if I need them instead of just memorizing them. But since nobody ever showed me how to do this when I was in school and I wasn't clever enough to figure it out on my own, I was stuck memorizing stuff that I really didn't need to memorize. Looking back, I wonder why I was never taught the easier way.

The two-envelope problem in risk management

Does it make sense to never change your information security strategy? That's a possible consequence of the so-called two-envelope paradox. This is a problem in probability theory that has confused students of probability theory for over 50 years. It goes like this.

Suppose that you're given two envelopes and you're told that one envelope contains twice as much money as the other. You then open one of the envelopes and see how much money it contains. Based on this information, you decide to either keep the contents of the first envelope or to switch its contents for the contents of the second, unopened envelope.

It might seem that it always pays to switch.

Suppose you find $2 in the first envelope. You know that the other envelope either contains $1, which happens with probability 0.5, or it contains $4, which also happens with probability 0.5. So you can calculate the expected value of the second envelope as $1 x 0.5 + $4 x 0.5 = $2.5. Because this is greater than $2, it always pays to switch.

There's a problem with this argument, of course, but it's fairly subtle. Even specialists in probability theory don't agree what the problem actually is, although they all agree that there's a problem with the argument.

Now let's suppose that we can't find a flaw in the above argument and we apply it to our information security strategy. Let's suppose that we have some initial set of technology, policies and procedures that end up giving us some exposure to risk that we'll denote R, and if we change to a different set of technology, policies and procedures, we might either increase the risk to 2R or decrease it to R/2. If we apply the same reasoning that we applied above, we find that it never pays to change, because the alternative always has a greater than the risk than what we have now. This clearly doesn't make sense, but it's what you might get if you do a risk analysis that isn't as careful as it could be.

The bottom line is probably that probability is a complicated and subtle concept, which means that risk management, which relies on it, also is.

Bayesian Scouting

I recently heard some interesting statistics about Scouting. Apparently, even though only one in four boys join Scouting, three out of four of adults holding leadership positions in the business world (representing five percent of jobs) were in Scouting. When I heard this, my first thought was to apply Bayes' theorem. After all, we're given P(S|L), so I was curious to apply Bayes' theorem to find P(L|S), or to use the available information to find what the chances of a Scout ending up a future leader are.

We have that P(S) = 1/4, P(L) = 1/20, P(S|L) = 3/4, and calculate P(L|S) = P(S|L) P(L) / P(S) = 3/20. A similar calculation tells us that P(L| not S) = 1/60, so that it seems that boys who join Scouting are nine times more likely to end up as leaders than boys who don't.

I haven't seen that number before, so I'd guess that the Scouting organization isn't as big a fan of Bayes' theorem as I am.

Twin primes and RSA

I just noticed an interesting quirk in how the RSA algorithm works if you use twin primes for the p and q that are used to calculate the modulus N = pq. Twin primes are those that differ by 2, so instead of writing p and q, let’s write p and p + 2 so that N = p (p + 2) and we have that f(N) = (p -1) (p +1) = p² – 1.

Now let’s pick our public key to be e = p. Then we need that the private key d has the property that ed = 1 (mod f(N)). Note that d = p satisfies this because p² = 1 (mod p² – 1). So if we have that the modulus is the product of twin primes, then we can find a case where the public key and the private key are the same.

I doubt that this is the first time that someone’s though of this, but it was new to me.

Uses for the Axiom of Choice

The Axiom of Choice is one of those things that causes a lot of trouble if you think about it for too long. It says that if you have a collection of non-empty sets then you can choose a member of each set in the collection. This sounds perfectly plausible, but it turns out that you can either assume that the Axiom of Choice holds or that it doesn't hold and without causing any logical inconsistencies. I've never really cared much about the Axiom of Choice myself. The only thing that it's done for me is create a really bizarre memory from graduate school.

When I was in graduate school, there was a fellow graduate student named Mike who was fascinated with the Axiom of Choice. It was definitely his favorite topic of discussion, although I never quite understood why. Mike told me once how he once was on a date that he could tell just wasn't going well. Apparently he and the woman that he had asked out ended up having absolutely nothing in common. After a while, he decided that he was going to stop trying to find common interests and instead decided to talk about things that interested him. In this case, it was the Axiom of Choice. According to Mike, this caused a sudden and dramatic change in his date, who couldn't keep her hands off him for the rest of the night.

I don't know if this story is true or not, but it certainly is one of the more unusual applications for the Axiom of Choice that I've heard of. Another interesting use may be in economics.

According to a paper by Christopher Ayres, all of the foundations of economic theory rely of the Axiom of Choice. Because the Axiom of Choice seems to be something that you can either accept or not accept without really affecting anything, I'm not sure how much Ayres' results will withstand a careful look, but I'm sure that I can think of at least one person who'd be interested in reading his paper. Of at least he would have been several years ago.