One More Discriminant

Unfortunately, we're not done yet. I didn't point it out at the time, but the discriminant appeared in one more place. Remember how in The Pattern we had an exact equation for chains 5a and 5b?

u =		[ (1/2) + (11/442) root 221 ] [ (15 + root 221)/2 ]n
	+	[ (1/2) − (11/442) root 221 ] [ (15 − root 221)/2 ]n

In that context, u and v varied, w = 5 was constant, and the solutions were unnormalized. I can't explain the next step better than I did before.

See how the solutions loop around through the tree? At the center of the loop (n = 0) is a solution that when normalized has u = 5, …

That solution has discriminant 9u² − 4 = 221, and that gives us one more connection to establish.

Fortunately, we already have most of the tools we'll need, but I do need to say a bit more about the theory of recurrence relations. So, suppose we have a recurrence relation with some characteristic polynomial. For each root x of the polynomial, the sequence xⁿ is a solution of the recurrence relation, and, ignoring some complications about multiple roots, every solution of the recurrence relation is a linear combination of those basic solutions. The weights can be computed from the roots and the initial conditions.

Here's a fact that I've used in other places but won't need in this essay. The basic solutions xⁿ grow exponentially because the variable is n, not x, so in a linear combination, the solution with the largest root rapidly dominates the rest. That's why the largest root is the most important.

• By “largest” I mean “largest in absolute value”. Roots can be negative or complex!
• By “grow exponentially” I mean “shrink exponentially” when |x| < 1.

Anyway, now we can parse the exact equation: the roots are (15 ± root 221)/2 and the weights are (1/2) ± (11/442) root 221. We can also answer some questions. Why do the weights contain the discriminant? Because they're computed from the roots and the initial conditions, and the roots contain the discriminant. And why do the roots contain the discriminant? Because they're the roots of the quadratic equation

x² − 3ux + 1 = 0,

and the discriminant b² − 4ac of that quadratic equation is … 9u² − 4.

That seems like it ought to mean that we're done, but no. What it means is that the appearance of the discriminant in the exact equation for chains 5a and 5b wasn't some kind of coincidence. For every value of u, the quadratic equation above and the equation for the value of expansion(u) have the same discriminant, even though they're different equations. The question now is why those two equations have the same discriminant. For comparison, here's the equation for the value of expansion(5) from Group Elements and Matrices.

5z² − 9z − 7 = 0

For a better comparison, let's generalize. The characteristic polynomial

x² − 3ux + 1

originally came from the Markov equation, which as far as I know doesn't generalize, but later (in Chains and Denominators, specifically The Recurrence Relation) we saw that it's also the characteristic polynomial of the recurrence relation for the subsequence s₋₁ of the denominators of expansion(u), and that does generalize to arbitrary expansions.

x² − (tr G) x + (det G)

Then we can write that out in terms of matrix entries, turn it into a quadratic equation, …

x² − (a + d)x + (ad − bc) = 0

… and compare it to the equation for the value of an arbitrary expansion.

cz² − (a − d)z − b = 0

So, yes, the equations are different. For reference, here's the generalized version of the discriminant (again).

D = (tr G)² − 4 det G

Next I want to introduce a new element and prove that the roots of the characteristic polynomial are equal to the eigenvalues of the matrix G. In fact, I want to prove it twice.

The first proof is simple but kind of disappointing. All we need to know is that the determinant of a matrix is the product of the eigenvalues, and the trace is the sum.

	x2 − (tr G) x + (det G)
=	x2 − (λ+ + λ−)x + (λ+λ−)
=	(x − λ+)(x − λ−)

A quick note about names: for any matrix, the polynomial with the eigenvalues as roots is called the minimal polynomial and the polynomial with the eigenvalues as roots with correct multiplicity is called the characteristic polynomial. So, here, the characteristic polynomial of the recurrence relation is also both the minimal polynomial and the characteristic polynomial of the matrix.

The second proof is kind of long, so I'll just sketch it out. Consider the subsequence s₋₁ of the denominators of the expansion. On the one hand, we know that the growth of the subsequence is controlled by the roots of the characteristic polynomial. On the other hand, it turns out that the growth of the subsequence is also controlled by the eigenvalues of G, so the two must be identical.

How does it turn out that way? Well, remember equations (1) and (2) in The Recurrence Relation? Instead of using them to do algebra, we can just regard them as a single matrix equation. That equation says that if we multiply the row vector (r₋₁ r₋₂) by G (on the right, of course), we get the row vector (r_L−1 r_L−2). In other words, multiplying by G advances the solution vector by L. So, if we multiply by G repeatedly, we can compute the whole subsequence s₋₁, and if we decompose the solution vector into eigenvectors, we can see that the growth is controlled by the eigenvalues.

That matrix equation seems strange, so let's take a minute to see how it fits into the scheme of things. So far we've seen a lot of matrices, but really only one nontrivial matrix equation, the result at the end of Group Elements and Matrices. In the separate essay A Nice Correspondence I generalized that result into what I'm now calling the first property of the prefix function P.

P(A & B) = P(A)P(B)

Let's look at two other special cases of that property.

• The second rows of the matrices are pairs of denominators, so if we restrict the equation to the second row and let P(B) be G, we find that multiplying a pair of denominators by G (on the right) advances the pair by adding a suffix. That's the result above, only better since it doesn't require a repeating expansion.
• The first columns of the matrices are numerator-denominator pairs, so if we restrict the equation to the first column and let P(A) be G, we find that multiplying a numerator-denominator pair by G (on the left) advances the pair by adding a prefix. That seems strange and wonderful, and maybe it is, but it's also a lot like something we've seen before. If we divide the numerators by the denominators, then we see that multiplying by G maps z = p/q to

  (ap + bq)/(cp + dq) = (az + b)/(cz + d) = G(z),

  just like the group element that adds the same prefix. I talked about matrices that added prefixes back in The Random Thoughts, but I thought they had to be converted to group elements first!

All that's left now is to show that the eigenvalues of the matrix G and the value of the expansion have the same discriminant, but that's easy. Suppose we have an eigenvector that's a column vector. Because c ≠ 0, the second component can't be zero, so we can rescale the eigenvector to make the second component 1. If we call the first component z, then the eigenvector equation Mv = λv looks like this.

az	+ b	= λz
cz	+ d	= λ

On the one hand, we can divide the first equation by the second and see that z is a fixed point of G(z). On the other hand, we can just look at the second equation and see that z and λ are related by a linear equation with integer coefficients and therefore have the same discriminant. In particular, the eigenvalue λ₊ is related to the fixed point z₊, which is the value of the expansion. Q.E.D.

As confirmation, here are the fixed points and eigenvalues from Group Elements and Matrices.

z	= (1/2c)	[ (a − d) ± root D ]
λ	= (1/2)	[ (a + d) ± root D ]

That's the end of the random thoughts and the end of giant thread, but be sure to check the table of contents at left for other closely related essays, for example Properties of Rotations.