428
$\begingroup$

In this MO post, I ran into the following family of polynomials: $$f_n(x)=\sum_{m=0}^{n}\prod_{k=0}^{m-1}\frac{x^n-x^k}{x^m-x^k}.$$ In the context of the post, $x$ was a prime number, and $f_n(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 $E_{x^n}$).

Anyway, while I was investigating asymptotic behavior of $f_n(x)$ in Mathematica, I got sidetracked and (just for fun) looked at the set of complex roots when I set $f_n(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 $n=60$-ish, the "circle" of solutions started 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\rightarrow \infty$? 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\left|z\right|^{-1}:z\in\mathbb{C}\text{ and }f_n(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 $\mathbb{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(f_n)$ up to $n=30$. I think we can see from this that $f_n$ should converge to some function on the unit disk as $n\rightarrow \infty$. 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 $f_n(x)$). The folowing claims aren't proven yet, but I've checked each up to $n=100$, and they seem inductively consistent. Here denote $\displaystyle f_n(x)=\sum_{m}a_{n,m}x^m$, so that $a_{n,m}\in \mathbb{Z}$ are the coefficients in the simplified expansion of $f_n(x)$.

  • First, I found $\text{deg}(f_n)=\text{deg}(f_{n-1})+\lfloor \frac{n}{2} \rfloor$. The solution to this recurrence relation is $$\text{deg}(f_n)=\frac{1}{2}\left({\left\lceil\frac{1-n}{2}\right\rceil}^2 -\left\lceil\frac{1-n}{2}\right\rceil+{\left\lfloor \frac{n}{2} \right\rfloor}^2 + \left\lfloor \frac{n}{2} \right\rfloor\right)=\left\lceil\frac{n^2}{4}\right\rceil.$$

  • If $f_n(x)$ has $r$ more coefficients than $f_{n-1}(x)$, the leading $r$ coefficients are the same as the leading $r$ coefficients of $f_{n-2}(x)$, pairwise.

  • When $n>m$, $a_{n,m}=a_{n-1,m}+\rho(m)$, where $\rho(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 $n\leq m$ the $\rho(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 $a_{n,m}$, $$a_{n,m}= \left\{ \begin{array}{ll} a_{n-2,m+\left\lceil\frac{n-2}{2}\right\rceil^2-\left\lceil\frac{n}{2}\right\rceil^2} & : \text{deg}(f_{n-1}) < m \leq \text{deg}(f_n)\\ a_{n-1,m}+\rho(m) & : m \leq \text{deg}(f_{n-1}) \text{ and } n > m \\ ? & : m \leq \text{deg}(f_{n-1}) \text{ and } n \leq m \end{array} \right. $$ but I can't figure out the last part yet.


EDIT: Someone pointed out to me that if we write $\lim_{n\rightarrow\infty}f_n(x)=\sum_{m=0}^\infty b_{m} x^m$, 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... :)

  • 22
    Not a proper answer, but possibly relevant: have you seen http://math.ucr.edu/home/baez/roots/ ?2012-10-04
  • 0
    @StevenStadnicki Wow, super cool. Perhaps some fractal theory plays into this!2012-10-04
  • 3
    Before I looked at this, 31 views and already 11 upvotes and 5 favorites. Hmm, I guess it is interesting :) I will make it 12 and 6.2012-10-04
  • 0
    This clockwise rotation you mention in 3. is strange. How does this go together with the apparent symmetry under complex conjugation?2012-10-04
  • 1
    Does the asymmetric rotation go away if you ask mathematica to compute with more precision? Conversely, if you ask it to compute with less precision, does it appear earlier?2012-10-04
  • 0
    @Hurkyl I am not sure. The only rotation takes place after about $n>60$, which is when the solutions start taking a pretty long time to compute. I did, however, have the target precision turned up several times higher than the default when I made the .gif. Also I made several .gifs of $n=2\text{ to }25$ while testing my code, all of which came out identically, even with increased precision.2012-10-04
  • 0
    Did you try plotting with a finer grained pixel grid and outputting the picture at a different scale? It might be an effect that comes about because the pixels are relatively big compared to the number of roots you have.2012-10-04
  • 2
    The rotating is absurd since you should have something symmetrical about the real axis, and I don't see the thickness of the shape when I plot the polynomials. Those should be software artifacts. But there does seem to be a quadratically increasing density of roots along the unit circle, with strange shapes at the roots of unity.2012-10-04
  • 7
    I don't know about an egg, but that round bulge on the left hand side makes the whole thing eerily eye-like. (You know, an anatomical eye in profile.) I would be really interested to know what gives rise to that feature.2012-10-04
  • 0
    @mercio You are right about the rotation - this can't be because of the expected symmetry. (Embarassing- I should have seen that.) I let the solver run again overnight at max precision and posted the results above. There is still a lot of weird behavior though!2012-10-04
  • 0
    @AlexanderGruber For reasons that will become clear after you read my answer, I've wondered about the answers to 5 and 6. I asked this exact question: http://math.stackexchange.com/questions/7539/finding-all-complex-zeros-of-a-high-degree-polynomial2012-10-05
  • 0
    I have seen something similar. John Baez studied the set of all roots of polynomials of a particular type here: http://math.ucr.edu/home/baez/roots/ You see similar circular shape, but since it's a different set of polynomials, he got a different picture. I was never able to get his code to run very well.2012-10-06
  • 0
    A couple of years ago I considered another set of polynomials with a related question, how the behave/occurence of roots could be characterized, when the degree of the polynomials grows to infinity. I've got some intuition and insight of it after rearranging in 4 groups and sorting the roots. Maybe this is of interest for your current question too, see the third subpage of http://go.helms-net.de/math/divers/ZerosOfGpFunctions.htm2012-10-07
  • 14
    I enjoy this question **very** much so far!! Keep it up!2012-10-09
  • 0
    Alex, that's a very nice plot. As I mention in my answer, if you consider the expansion of the sum, the constant coefficient becomes unbounded. It's the same with the 1st power and so on. I think you need to divide by $n+1$ to get a convergent series but I'm not sure. That is, maybe consider computing approximation to $$\lim_{n\to\infty}\frac{1}{n+1}\sum_{m=0}^n \begin{bmatrix}n\\m\end{bmatrix}_x$$ I'm not sure how this will change your plot, except that I think it'll make it more even on the unit disk.2012-10-10
  • 0
    Also, I think it's not going to be as pretty but you can probably plot both $f_n$ and this limiting function that I mentioned just on the unit disk and not outside. Maybe you can even plot the difference of the two? My intuition is that the binomial coefficients converge to the products of $(1-x^k)$ only within the unit disk, and so the limiting sum should probably be only valid on the unit disk.2012-10-10
  • 0
    My academic advisor worked on the 1/(q;q)_\infty polynomials you are talking about. http://www.math.drexel.edu/~rboyer/papers/boyer_goh_ams_apr_2007.pdf2013-10-24
  • 0
    @DanielParry Cool! Do you think he would be interested in this problem? Perhaps I could talk to him about it sometime.2013-10-25
  • 0
    I will forward this to him and I have done some work in this area of roots polynomials derived from q-series as well. (Paper posted below). The general rule of thumb I have experienced is that the asymptotic structure of \ln f_n(x), more or less, determines the limiting structure of the roots. www.combinatorics.org/ojs/index.php/eljc/article/view/v18i2p302013-12-03
  • 0
    Is there any way to find the most upvoted question on the site, because this looks like it could be it?2014-12-05
  • 0
    @user45195 Yeah, you can sort the questions list [by votes](http://math.stackexchange.com/questions?sort=votes). This question isn't #1, but it's on the first page (ranked 15th I think?). It's among the highest non-"soft" questions, depending on what one counts as as "soft."2014-12-05
  • 0
    Makes me think of investigation of eigenvalues of random matrices (normalized), they tend to get eigenvalues evenly distributed on the unit circle.2015-03-18
  • 0
    @Graphth I didn't know one can see the number of favourites and upvotes on a question. Can you tell me how can one do that?2017-10-27

7 Answers 7