“The Egg:” Bizarre behavior of the roots of a family of polynomials.

In this MO post, I ran into the following family of polynomials: fn(x)=nm=0m1k=0xnxkxmxk.
In the context of the post, x was a prime number, and fn(x) counted the number of subspaces of an n-dimensional vector space over GF(x) (which I was using to determine the number of subgroups of an elementary abelian group Exn).

Anyway, while I was investigating asymptotic behavior of fn(x) in Mathematica, I got sidetracked and (just for fun) looked at the set of complex roots when I set fn(x)=0. For n=24, the plot looked like this: (The real and imaginary axes are from 1 to 1.)

n=24

Surprised by the unusual symmetry of the solutions, I made the same plot for a few more values of n. Note the clearly defined “tails” (on the left when even, top and bottom when odd) and “cusps” (both sides).

40 and 70100

You can see that after approximately n=60, the “circle” of solutions starts to expand into a band of solutions with a defined outline. To fully absorb the weirdness of this, I animated the solutions from n=2 to n=112. The following is the result:

n=2 to 112

Pretty weird, right!? Anyhow, here are my questions:

  1. First, has anybody ever seen anything at all like this before?
  2. What’s up with those “tails?” They seem to occur only on even n, and they are surely distinguishable from the rest of the solutions.
  3. Look how the “enclosed” solutions rotate as n increases. Why does this happen? [Explained in edits.]
  4. Anybody have any idea what happens to the solution set as n?
    Thanks to @WillSawin, we now know that all the roots are contained in an annulus that converges to the unit circle, which is fantastic. So, the final step in understanding the limit of the solution sets is figuring out what happens on the unit circle. We can see from the animation that there are many gaps, particularly around certain roots of unity; however, they do appear to be closing.

    • The natural question is, which points on the unit circle “are roots in the limit”? In other words, what are the accumulation points of {z|z|1:zC and fn(z)=0}?
    • Is the set of accumulation points dense? @NoahSnyder’s heuristic of considering these as a random family of polynomials suggests it should be- at least, almost surely.
  5. These are polynomials in Z[x]. Can anybody think of a way to rewrite the formula (perhaps recursively?) for the simplified polynomial, with no denominator? If so, we could use the new formula to prove the series converges to a function on the unit disc, as well as cut computation time in half. [See edits for progress.]
  6. Does anybody know a numerical method specifically for finding roots of high degree polynomials? Or any other way to efficiently compute solution sets for high n? [Thanks @Hooked!]

Thanks everyone. This may not turn out to be particularly mathematically profound, but it sure is neat.


EDIT: Thanks to suggestions in the comments, I cranked up the working precision to maximum and recalculated the animation. As Hurkyl and mercio suspected, the rotation was indeed a software artifact, and in fact evidently so was the thickening of the solution set. The new animation looks like this:

Working precision to 10^-50.

So, that solves one mystery: the rotation and inflation were caused by tiny roundoff errors in the computation. With the image clearer, however, I see the behavior of the cusps more clearly. Is there an explanation for the gradual accumulation of “cusps” around the roots of unity? (Especially 1.)


EDIT: Here is an animation Arg(fn) up to n=30. I think we can see from this that fn should converge to some function on the unit disk as n. I’d love to include higher n, but this was already rather computationally exhausting.

Avoid this if you've been taking any hallucinogenic drugs.

Now, I’ve been tinkering and I may be onto something with respect to point 5 (i.e. seeking a better formula for fn(x)). The folowing claims aren’t proven yet, but I’ve checked each up to n=100, and they seem inductively consistent. Here denote fn(x)=man,mxm, so that an,mZ are the coefficients in the simplified expansion of fn(x).

  • First, I found deg(fn)=deg(fn1)+n2. The solution to this recurrence relation is deg(fn)=12(1n221n2+n22+n2)=n24.

  • If fn(x) has r more coefficients than fn1(x), the leading r coefficients are the same as the leading r coefficients of fn2(x), pairwise.

  • When n>m, an,m=an1,m+ρ(m), where ρ(m) is the number of integer partitions of m. (This comes from observation, but I bet an actual proof could follow from some of the formulas here.) For nm the ρ(m) formula first fails at n=m=6, and not before for some reason. There is probably a simple correction term I’m not seeing – and whatever that term is, I bet it’s what’s causing those cusps.

Anyhow, with this, we can make almost make a recursive relation for an,m,
an,m={an2,m+n222n22:deg(fn1)<mdeg(fn)an1,m+ρ(m):mdeg(fn1) and n>m?:mdeg(fn1) and nm
but I can’t figure out the last part yet.


EDIT:
Someone pointed out to me that if we write limnfn(x)=m=0bmxm, then it appears that f_n(x)=\sum_{m=0}^n b_m x^m + O(x^{n+1}). The b_m there seem to me to be relatively well approximated by the \rho(m) formula, considering the correction term only applies for a finite number of recursions.

So, if we have the coefficients up to an order of O(x^{n+1}), we can at least prove the polynomials converge on the open unit disk, which the Arg animation suggests is true. (To be precise, it looks like f_{2n} and f_{2n+1} may have different limit functions, but I suspect the coefficients of both sequences will come from the same recursive formula.) With this in mind, I put a bounty up for the correction term, since from that all the behavior will probably be explained.


EDIT: The limit function proposed by Gottfriend and Aleks has the formal expression \lim_{n\rightarrow \infty}f_n(x)=1+\prod_{m=1}^\infty \frac{1}{1-x^m}.
I made an Arg plot of 1+\prod_{m=1}^r \frac{1}{1-x^m} for up to r=24 to see if I could figure out what that ought to ultimately end up looking like, and came up with this:

enter image description here

Purely based off the plots, it seems not entirely unlikely that f_n(x) is going to the same place this is, at least inside the unit disc. Now the question is, how do we determine the solution set at the limit? I speculate that the unit circle may become a dense combination of zeroes and singularities, with fractal-like concentric “circles of singularity” around the roots of unity… 🙂

Answer

First, has anybody ever seen anything at all like this before?

Yes, and in fact the interesting patterns that arise here are more than just a mathematical curiosity, they can be interpreted to have a physical context.

Statistical Mechanics

In a simple spin system, say the Ising model, a discrete set of points are arranged on a grid. In physics, we like to define the energy of the system by the Hamiltonian, which gives the energy of any particular microstate. In this system, if the spins are aligned they form a bond. This favorable and the energy is negative. If they are misaligned, the energy is positive. Let’s consider a simple system of two points, adjacent to each other. Furthermore, let each site point up (1) or down (-1). For an Ising-like system we would write the Hamiltonian as:


H = – \sum_{ij} J \sigma_i \sigma_j

where \sigma_i is the spin of the ith point and the summation runs over all pairs of adjacent sites. J is the strength of the bond (which we can set to one for our example).

In our simple system we have only four possible states:

0 - 0     H = -J
1 - 0     H =  0
0 - 1     H =  0
1 - 1     H = -J

Now we can write the partition function \mathcal{Z}, a term which encompasses all information of the Hamiltonian from the perspective of statistical mechanics:


\mathcal{Z} = \sum_s \exp (H(s)/kT)

Here the summation runs over all possible (micro)states of the system. The partition function is really useful as it is related to the free energy A = -kT \ln{\mathcal{Z} }. When the partition function goes to zero, the free energy explodes and this signifies a phase change – a physically interesting event.

What about our simple system?


\mathcal{Z} = 2 \exp({\beta J}) + 2 = 2x + 2

You’ll notice that I changed x=\exp({\beta J}) to make things a little neater. You may also notice that \mathcal{Z} looks like polynomial. Which means if we want to find the interesting events in the system we find the zeros of the partition function \mathcal{Z}=0. This zero will correspond to a particular temperature T. In this case the only temperature we get is a complex one …

Complex Temperatures?

Before you discount the idea that a temperature not on the real number line is impossible (and that T<0 is strange as well), let's see where this takes us. If we continue the to add sites to our simple little system, our polynomial will get a bit more complicated and we will find more roots on the complex plane. In fact, as we take ever more roots the points appear to form a pattern, much like the pattern you've shown above.

For a finite spin system, you'll never find a zero on the real axis, however...

Anybody have any idea what happens to the solution set as n→∞?

At the thermodynamic limit (which corresponds to an infinite number of sites) the points become dense on the plane. At this limit the points can touch the real axis (corresponding to a phase change in the system). For example, in the 2D Ising model the points do touch the real axis (and make a beautiful circle on the complex plane) where the system undergoes a phase transition from ordered to disordered.

Prior work

The study of these zeros (from a physics perspective) is fascinating and started with the seminal papers by Yang and Lee:

Yang, C. N.; Lee, T. D. (1952), "Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation", Physical Review 87: 404–409, doi:10.1103/PhysRev.87.404

Lee, T. D.; Yang, C. N. (1952), "Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model", Physical Review 87: 410–419, doi:10.1103/PhysRev.87.410

Which are surprisingly accessible. For a good time, search for images of Yang-Lee zeros. In addition you can extend the fugacity to the complex plane, these are called the Fisher zeros and make even more complex patterns!

Attribution
Source : Link , Question Author : Alexander Gruber , Answer Author : Hooked

Leave a Comment