# What Are Some Naturally-Occurring High-Degree Polynomials?

To construct J. H. Conway's look-and-say sequence, begin by putting down a 1 as the first entry. The other entries are found by saying the previous entry aloud, and writing what you hear.

1
11
21
1211
111221
312211  (previous entry was three 1's, two 2's and one 1)
...


Conway provides his usual fantastical analysis in The Weird and Wonderful Chemistry of Audioactive Decay [Eureka 46, 5-18], where he demonstrates several otherworldly properties of this sequence. One was this: the ratio of the lengths of consecutive entries has a limit, $\lambda$. Furthermore, $\lambda$ is the root of a polynomial of degree 71.

Now, when I was in high school we were taught the quadratic formula and told there is a cubic formula, but you don't have to learn it. Why? "You won't be needing it." And mostly I've found that to be true. Am I wrong, or do high-degree polynomials rarely occur (in uncontrived settings)?

What are some other examples of useful roots of polynomials of high degree? Power series and the like can obviously produce useful polynomials of arbitrarily large degree, but I'm looking for surprises such as the degree-71 polynomial at the heart of the look-and-say sequence above.

-
I would classify the question as wiki. Higher degree polynomials occur quite often; for example, see the comment of Jonas Meyer to mathoverflow.net/questions/21003. – Wadim Zudilin Jun 7 '10 at 7:36
OK, agreed. I converted to wiki. – I. J. Kennedy Jun 7 '10 at 7:56
What happens in other bases? (I guess Conway did a general analysis and that one always gets polynomials with degree depending on the basis.) One could also look at more exotic number systems (eg. the "Fibonacci base" or the "factorial base"). – Roland Bacher Jun 7 '10 at 7:58
Well, the title and your question don't fit quite well: do you like polynomials or the roots? In my response, I more worry about the polynomial, since the roots might be helpful but nobody will solve the algebraic relation. – Wadim Zudilin Jun 7 '10 at 7:59
@Roland, Wadim's point is that no number greater than 3 can occur in the example sequence. So the base is irrelevant. – TonyK Jun 7 '10 at 11:18

From Fernando Rodriguez-Villegas' preprint:

"Chebyshev in his work on the distribution of prime numbers used the following fact $$u_n:=\frac{(30n)!n!}{(15n)!(10n)!(6n)!}\in\mathbb Z, \qquad n = 0, 1, 2, \dots$$ (see also my question -- WZ). This is not immediately obvious (for example, this ratio of factorials is not a product of multinomial coefficients) but it is not hard to prove. The only proof I know proceeds by checking that the valuations $v_p(u_n)$ are non-negative for every prime $p$; an interpretation of $u_n$ as counting natural objects or being dimensions of natural vector spaces is far from clear.

As it turns out, the generating function $$u(\lambda):=\sum_{n=0}^\infty u_n\lambda^n$$ is algebraic over $\mathbb Q(\lambda)$; i.e. there is a polynomial $F\in\mathbb Q[x,y]$ such that $$F(\lambda,u(\lambda))=0.$$ However, we are not likely to see this polynomial explicitly any time soon as its degree is $483,840$ (!)"

-
I should add that the roots of this monstrous polynomial will shed light on the integrality of $u_n$ without $p$-order study. – Wadim Zudilin Jun 7 '10 at 7:53
Many interesting polynomials are related to minimizing Mahler's measure (in connection with Lehmer's conjecture). But they are less astronomic, so I won't do a separate post. – Wadim Zudilin Jun 7 '10 at 8:03

Some high-degree polynomials have been discovered using integer-relation algorithms applied to the powers of interesting constants. Here is a quotation from Section 3 of a paper of David Bailey, which can be found here: http://www.nersc.gov/homes/dhbailey/dhbpapers/pslq-cse.pdf

"One of the ﬁrst results of this sort was the identiﬁcation of the constant B3 = 3.54409035955 · · · [1]. B3 is the third bifurcation point of the logistic map $x_{k+1} = rx_k(1 − x_k )$, which exhibits period doubling shortly before the onset of chaos. To be precise, B3 is the smallest value of the parameter r such that successive iterates $x_k$ exhibit eight-way periodicity instead of four-way periodicity. Computations using a predecessor algorithm to PSLQ found that B3 is a root of the polynomial

$0 = 4913 + 2108t^2 − 604t^3 − 977t^4 + 8t^5 + 44t^6 + 392t^7 − 193t^8 − 40t^9 + 48t^{10} − 12t^{11} + t^{12}.$

Recently, B4 = 3.564407268705 · · ·, the fourth bifurcation point of the logistic map, was identiﬁed using PSLQ by British physicist David Broadhurst [5]. Some conjectural reasoning had suggested that B4 might satisfy a 240-degree polynomial, and some further analysis had suggested that the constant α = −B4 (B4 − 2) might satisfy a 120-degree polynomial. In order to test this hypothesis, Broadhurst applied a PSLQ program to the 121-long vector $(1, α, α^2 , · · · , α^{120})$. Indeed, a relation was found, although 10,000 digit arithmetic was required. The recovered integer coeﬃcients descend monotonically from $257^{30} ≈ 1.986 × 10^{72}$ to one."

-
I can only comment that David Broadhurst is not only a physicist but also a very strong mathematician! – Wadim Zudilin Jun 7 '10 at 8:19
Incidentally, $4913=17^3$. – Fan Zheng May 10 at 21:01

The high-degree polynomial $x^{65537}-1$ is interesting because its nontrivial roots can be expressed in terms of square roots, and thus (in principle) the regular 65537-gon is constructible by ruler and compass. It is the largest known constructible $n$-gon with a prime number of sides. The roots, however, occupy several megabytes when written out in full.

-
>(in principle) Actually, there's a book here in Goettingen which describes the construction. It's very heavy. Some poor soul got a PhD for this, I think. – Łukasz Grabowski Sep 30 '10 at 21:25
Yes, there is a book, by Johann Gustav Hermes, in the mathematics library at Göttingen. However, the experts I've spoken to doubt that Hermes really solved the equation. – John Stillwell Sep 30 '10 at 21:51
@JohnStilwell I know this is an old comment, but could you please expand on it? I find this very interesting, and would be nice to mention something about it next time it comes up in lecture. (I know of no works criticizing Hermes's construction) – Andrés Caicedo May 11 '13 at 17:17
@Andres: I was in Göttingen in 2002 (so my memory is fading a bit) and I was shown the book of Hermes' calculations by the number theorist S. J. Patterson. It is a very meticulous hand written book, but Patterson's opinion was that Hermes does not reach a clear solution of the equation. I wrote a little more about this, see tech.groups.yahoo.com/group/Hyacinthos/message/10294 – John Stillwell May 12 '13 at 6:35
Thank you, John. (It would be nice if they digitized the book so others can see it.) – Andrés Caicedo May 14 '13 at 22:22

If you accept polynomials in more than one variable...

There is a polynomial inequality in 26 variables that describes the set of primes (Wikipedia - from where I also sourced the rest of this answer). By a result of Matiyasevich there is another polynomial inequality in 10 variables that also describes the primes, but whose order in on the order of $10^{45}$, which dwarfs Wadim's answer. In the other direction there is an order 4 polynomial inequality that will do the job, but in 58 variables.

-

I was recently amazed by an answer to this question.

I encountered another curious fact while working with hypergeometric functions. The following absolute value of a complex-valued $_4F_3$ function: $$\left|_4F_3\left(\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5};\frac{1}{2},\frac{3}{4},\frac{5}{4};\sqrt{\phi }\right)\right|$$ where $\phi$ is the golden ratio, is actually an algebraic number with the minimal polynomial of degree 80 and a coefficient exceeding $10^{55}$ (see its explicit form here). I'm not sure if the root is expressible in radicals.

-

Some high degree polynomials appears in Delsarte scheme for estimating kissing numbers in $R^n$. Here is the excerpt from the Florian Pfender and Gunter M. Ziegler. Kissing numbers, sphere packings, and some unexpected proofs:

Theorem 3 (Delsarte, Goethals and Seidel [11]). If $$f(t)=\sum_{k=0}^d > c_k G_k^{(n)}(t)$$ is a nonnegative combination of Gegenbauer polynomials, with $c_0 > 0$ and $c_k ≥ 0$ otherwise, and if $f (t) ≤ 0$ holds for all $t \in [−1, 1/2 ]$ , then the kissing number for $R^n$ is bounded by $$\kappa(n)\leq \frac{f(1)}{c_0}$$

For example for $n=24$ polynomial $f_{24}(t)=(t-\frac{1}{2})(t-\frac{1}{4})^2 t^2 (t+\frac{1}{4})^2 (t+\frac{1}{2})^2(t+1)$ gives the precise number for kissing number in $R^{24}$ - 196 560.

-

Cyclotomic polynomials (http://en.wikipedia.org/wiki/Cyclotomic_polynomial), which when n is composite are rather more complicated than you might guess.

I think the point here is that polynomials play an implicit part all over algebra; and in algebraic geometry. The case of a quadratic equation is somewhat misleading, if useful on its own ground. It is possible to reason about polynomials without knowing exactly what the solutions look like. It is possible to solve numerically for roots of polynomial equations, without having a formula; and indeed the formulae we know for degree 3 and 4 are not necessarily useful for numerical work.

Fairly concrete examples are seen in the theory of Laplace transforms, where differential operators become, thanks to the transform, operators of multiplication by polynomials. Here engineering applications that have on the face of it no connection to polynomials may be studied by means of them, and the complexity of the polynomial reflects that of the problem you start with.

-
All these examples do not really answer in the sense that cyclic polynomials, orthogonal polynomials etc form sequences and high dimensional polynomials in engineering applications (perhaps you think of formulae for numerical integrations) occur also only because we want fast convergencey or high precision and they have also analogues of low degree. Conway's example falls in some sense "out of the sky" and known "extraterrestrial" examples of such high degree are perhaps quite rare. – Roland Bacher Jun 7 '10 at 7:52
Not, I think, a view explicit in the question; but of course the only way to find another John Conway would be cloning technology. High-degree polynomials do occur outside "contrived settings". For some problems such as class field towers (Golod-Shafarevich) they are there, and the question would be why anyone would write them down. – Charles Matthews Jun 7 '10 at 8:10
Thanks for that comment, Roland. It captures the spirit of my question, which I failed to convey adequately. – I. J. Kennedy Dec 27 '10 at 4:43
This answer is not so bad. The cyclotomic polynomial of degree 105 is the first one with a coefficient not in {-1,0,1}. – dvitek Feb 6 '11 at 16:00

For practical matters, smooth functions (exp, sin, atan...) are often computed numerically using polynomials of high order.

Calculators compute the exponential function in the range [0,1] by evaluating a 12 degree polynomial whose coefficients are chosen so as to get 8 or 10 digits correct. These approximating polynomials can be found in formulas handbooks (e.g. "Methods and Programs for Mathematical Functions". Also the EDM lists a few in its appendices). They do a better job, at the given precision 10^(-8), than the standard Taylor polynomials.

Also have a look at your favorite language mathematical library, to see how standard functions (sin, exp, Atan...) are implemented (someone may suggest a link ?).

-

My favorite is Theorem 9.2 on page 180 of "Primes of the form $x^2 + n y^2$ " by David A. Cox. In short, there is a polynomial $f_n(z)$ in one variable, integer coefficient and monic irreducible of degree $h(-4 n)$, such that if an odd prime $p$ does not divide $n$ or the discriminant of $f_n(z),$ then $p$ is represented by the positive binary quadratic form $x^2 + n y^2$ if and only if both $( -n | p) = 1$ and $f_n(z)$ has a root $\pmod p.$

Note that this does not duplicate the effect of calculating genera, that process divides up the primes by very simple congruences. The theorem comes into play with primes that are represented by some form in the principal genus, therefore automatically if there is only one genus. A prime is represented by at most one class $a x^2 + b x y + c y^2$ (and its opposite $a x^2 - b x y + c y^2$ if distinct) among forms of a given discriminant. There are similar theorems for odd discriminants and $x^2 + x y + k y^2,$ in case this $k > 0$ is even it is the same theorem, for utterly trivial reasons.

I found a cute way to incorporate this into a problem about polynomials in three variables, Integers not represented by $2 x^2 + x y + 3 y^2 + z^3 - z$

It is this problem I had with me when arriving at MO, in the same sense that Grace Slick arrived at Jefferson Airplane with "Somebody to Love" and "White Rabbit." I found all such problems for class number 3, and I'm guessing Kevin Buzzard's methods could finish all of them. I would like to know whether the same problem produces interesting phenomena in class number 5.

Meanwhile, Kaltofen and Yui made a serious effort to find such polynomials with small coefficients in "Explicit Construction of the Hilbert Class Fields of Imaginary Quadratic Fields by Integer Lattice Reduction," with table B5 giving three pages of polynomials.

-
A very nice example, Will! Your reference reminded me about mathoverflow.net/questions/22001/… and about other monstrous polynomials, called modular polynomials (or modular equations). I expect that some of MOthematicians could argue about how natural are those monsters... – Wadim Zudilin Jun 9 '10 at 2:39
Right. On page 298 of Cox he gives $H_{-71}(X)$ with giant coefficients. There are some nice examples in Kaltofen and Yui, but nothing I could use for my problem with class number 5. Blair Spearman sent me one appropriate polynomial for h=5, but the numbers still got too big to see any patterns. – Will Jagy Jun 9 '10 at 4:20

There is a rational function that arises naturally as a weight function in G. Chinta's "Mean values of biquadratic zeta functions" Invent. Math. 160 (2005), no.1, 145-164.

He writes out the numerator and denominator explicitly at the end of the paper (and it takes 3 pages),

The problem of packing $n$ equal circles into a unit square, or equivalently, finding the largest possible minimal distance between $n$ points in a unit square, produces some high-degree polynomials (the minimal polynomials of the radii of circles). For example, for $n=11$ the minimal polynomial has degree 18, and for $n=13$ it has degree 40 (cf. http://www.inf.u-szeged.hu/~pszabo/Pub/45survey.pdf, page 17).