What Are Some Naturally-Occurring High-Degree Polynomials?

Question

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.

Answer 1

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$ (!)"

Answer 2

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 first results of this sort was the identification 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}$$

Or, if $x=-t(t - 2)$,

$$0 = 4913 + 527 x^2 - 188 x^3 + 47 x^4 - 12 x^5 + x^6$$

which is a sextic with a non-solvable Galois group. Recently, B4 = 3.564407268705 · · ·, the fourth bifurcation point of the logistic map, was identified 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 coefficients descend monotonically from $257^{30} ≈ 1.986 × 10^{72}$ to one."

Answer 3

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.

Answer 4

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

There is a polynomial inequality in 26 variables that describes the set of primes:

(source: Wikipedia). By a result of Matiyasevich there is another polynomial inequality in 10 variables that also describes the primes, but whose order is approximately $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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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 ?).

Answer 9

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).

Answer 10

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.

Answer 11

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),

http://www.sci.ccny.cuny.edu/~chinta/publ/biquad.pdf

Answer 12

Don't people compute eigenvalues of very large matrices all the time? Those are the roots of the characteristic polynomial...

Answer 13

There are, apparently, two convex bicyclic pentagons with rational-degree angles. One is the regular pentagon. Thrle other is given here, with angles measuring 140°, 120°, 80°, 80°, 20° in rotational order. If the long side, opposite the 140°angpe, is the unit length, then the other sides are the positive roots of

$3x^3-3x+1=0,$

and the two longest diagonals (connecting each 80°angle with the opposing 120° one) measures the negative root except for sign.

Answer 14

Let $y^2 = x^3 + Ax + B$ be an elliptic curve over a field $F$ of characteristic not 2 or 3.

This paper of Skalba gives three degree 26 rational functions $X_1, X_2, X_3$ such that for any $t \in F$, exactly one of $X_1(t), X_2(t), X_3(t)$ represents the $x$ coordinate of a point on the curve. This is super useful for hashing into elliptic curves, which you sometimes need to do in cryptographic applications.

The rational functions are

where the $n_{a,b}, d_{a,b}$ are some constants.