What Are Some Naturally-Occurring High-Degree Polynomials? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T09:23:13Z http://mathoverflow.net/feeds/question/27324 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials What Are Some Naturally-Occurring High-Degree Polynomials? I. J. Kennedy 2010-06-07T07:24:38Z 2013-05-10T00:53:31Z <p>To construct J. H. Conway's <a href="http://en.wikipedia.org/wiki/Look-and-say_sequence" rel="nofollow">look-and-say sequence</a>, 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.</p> <pre><code>1 11 21 1211 111221 312211 (previous entry was three 1's, two 2's and one 1) ... </code></pre> <p>Conway provides his usual fantastical analysis in <em>The Weird and Wonderful Chemistry of Audioactive Decay</em> [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. </p> <p>Now, when I was in high school we were taught the quadratic formula and told there <strong>is</strong> 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)?</p> <p>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.</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27325#27325 Answer by Charles Matthews for What Are Some Naturally-Occurring High-Degree Polynomials? Charles Matthews 2010-06-07T07:38:01Z 2010-06-07T07:38:01Z <p>Cyclotomic polynomials (http://en.wikipedia.org/wiki/Cyclotomic_polynomial), which when n is composite are rather more complicated than you might guess.</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27328#27328 Answer by Wadim Zudilin for What Are Some Naturally-Occurring High-Degree Polynomials? Wadim Zudilin 2010-06-07T07:50:19Z 2010-06-07T10:38:30Z <p>From Fernando Rodriguez-Villegas' <a href="http://arxiv.org/abs/math/0701362" rel="nofollow">preprint</a>:</p> <p>"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 <a href="http://mathoverflow.net/questions/26336/" rel="nofollow">my question</a> -- 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.</p> <p>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$ (!)"</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27329#27329 Answer by gowers for What Are Some Naturally-Occurring High-Degree Polynomials? gowers 2010-06-07T07:51:22Z 2010-06-07T07:51:22Z <p>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: <a href="http://www.nersc.gov/homes/dhbailey/dhbpapers/pslq-cse.pdf" rel="nofollow">http://www.nersc.gov/homes/dhbailey/dhbpapers/pslq-cse.pdf</a></p> <p>"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 </p> <p>$0 = 4913 + 2108t^2 − 604t^3 − 977t^4 + 8t^5 + 44t^6 + 392t^7 − 193t^8 − 40t^9 + 48t^{10} − 12t^{11} + t^{12}.$ </p> <p>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." </p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27331#27331 Answer by John Stillwell for What Are Some Naturally-Occurring High-Degree Polynomials? John Stillwell 2010-06-07T08:45:53Z 2010-06-07T09:53:25Z <p>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.</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27333#27333 Answer by coudy for What Are Some Naturally-Occurring High-Degree Polynomials? coudy 2010-06-07T09:19:11Z 2010-06-07T09:19:11Z <p>For practical matters, smooth functions (exp, sin, atan...) are often computed numerically using polynomials of high order.</p> <p>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.</p> <p>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 ?). </p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27337#27337 Answer by Nurdin Takenov for What Are Some Naturally-Occurring High-Degree Polynomials? Nurdin Takenov 2010-06-07T10:18:23Z 2010-06-07T10:18:23Z <p>Some high degree polynomials appears in Delsarte scheme for estimating kissing numbers in $R^n$. Here is the excerpt from the <a href="http://www.ams.org/notices/200408/fea-pfender.pdf" rel="nofollow">Florian Pfender and Gunter M. Ziegler. Kissing numbers, sphere packings, and some unexpected proofs</a>:</p> <blockquote> <p>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}$$</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27495#27495 Answer by Will Jagy for What Are Some Naturally-Occurring High-Degree Polynomials? Will Jagy 2010-06-08T18:23:48Z 2010-06-08T18:29:54Z <p>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.$</p> <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.</p> <p>I found a cute way to incorporate this into a problem about polynomials in three variables, <a href="http://mathoverflow.net/questions/12486/integers-not-represented-by-2-x2-x-y-3-y2-z3-z" rel="nofollow">http://mathoverflow.net/questions/12486/integers-not-represented-by-2-x2-x-y-3-y2-z3-z</a> </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/50636#50636 Answer by David Roberts for What Are Some Naturally-Occurring High-Degree Polynomials? David Roberts 2010-12-29T09:19:36Z 2010-12-29T09:19:36Z <p>If you accept polynomials in more than one variable...</p> <p>There is a polynomial inequality in 26 variables that describes the set of primes (<a href="http://en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations" rel="nofollow">Wikipedia</a> - 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 <a href="http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27328#27328" rel="nofollow">Wadim's answer</a>. In the other direction there is an order 4 polynomial inequality that will do the job, but in 58 variables.</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/54480#54480 Answer by Micah Milinovich for What Are Some Naturally-Occurring High-Degree Polynomials? Micah Milinovich 2011-02-06T02:18:17Z 2011-02-06T02:18:17Z <p>There is a rational function that arises <em>naturally</em> as a weight function in G. Chinta's "Mean values of biquadratic zeta functions" Invent. Math. 160 (2005), no.1, 145-164. </p> <p>He writes out the numerator and denominator explicitly at the end of the paper (and it takes 3 pages),</p> <p><a href="http://www.sci.ccny.cuny.edu/~chinta/publ/biquad.pdf" rel="nofollow">http://www.sci.ccny.cuny.edu/~chinta/publ/biquad.pdf</a></p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/85112#85112 Answer by Junyan Xu for What Are Some Naturally-Occurring High-Degree Polynomials? Junyan Xu 2012-01-07T06:37:00Z 2012-01-07T06:37:00Z <p>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. <a href="http://www.inf.u-szeged.hu/~pszabo/Pub/45survey.pdf" rel="nofollow">http://www.inf.u-szeged.hu/~pszabo/Pub/45survey.pdf</a>, page 17).</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/128877#128877 Answer by none for What Are Some Naturally-Occurring High-Degree Polynomials? none 2013-04-27T00:12:58Z 2013-04-27T00:12:58Z <p>Don't people compute eigenvalues of very large matrices all the time? Those are the roots of the characteristic polynomial...</p> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/130218#130218 Answer by Vladimir Reshetnikov for What Are Some Naturally-Occurring High-Degree Polynomials? Vladimir Reshetnikov 2013-05-10T00:45:15Z 2013-05-10T00:53:31Z <p>I was recently amazed by an answer to <a href="http://math.stackexchange.com/questions/386207/what-is-the-role-of-mathematical-intuition-and-common-sense-in-questions-of-irra" rel="nofollow">this question</a>.</p> <p>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 <a href="http://math.stackexchange.com/a/387124/76458" rel="nofollow">here</a>). I'm not sure if the root is expressible in radicals.</p>