What bounds can we establish on coefficients of Swinnerton-Dyer polynomials? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T08:41:38Z http://mathoverflow.net/feeds/question/106907 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106907/what-bounds-can-we-establish-on-coefficients-of-swinnerton-dyer-polynomials What bounds can we establish on coefficients of Swinnerton-Dyer polynomials? swinnly 2012-09-11T12:46:51Z 2013-06-17T09:54:57Z <p>The maximum coefficient of the n<sub>th</sub> <a href="http://mathworld.wolfram.com/Swinnerton-DyerPolynomial.html" rel="nofollow">Swinnerton-Dyer polynomial</a> seems to grow very fast with n. These are the maximum absolute values of the first 6 polynomials,</p> <ol> <li>2</li> <li>10</li> <li>960</li> <li>13950764</li> <li>255690851718529024</li> <li>1771080720430629161685158978892152599456</li> </ol> <p>What bounds can we establish on the absolute value of coefficients in the n<sub>th</sub> Swinnerton-Dyer polynomial? A very trivial bound appears to be $B(n) = 2^{2^n} n \sqrt{p_n}$ but this doesn't take into account cancellation of any of the terms. Is it possible to do better?</p> http://mathoverflow.net/questions/106907/what-bounds-can-we-establish-on-coefficients-of-swinnerton-dyer-polynomials/133757#133757 Answer by Fredrik Johansson for What bounds can we establish on coefficients of Swinnerton-Dyer polynomials? Fredrik Johansson 2013-06-14T15:52:45Z 2013-06-17T09:54:57Z <p>There is a missing exponent in your trivial bound. Letting $u_n = \sum_{k=1}^n \sqrt{p_k}$, we have</p> <p>$$B_0(n) \equiv \max_i \; \left| [x^i] S_n \right|$$ $$\le B_1(n) \equiv \max_i \; [x^i] (x+u_n)^{2^n} = \max_i {2^n \choose i} u_n^i$$ $$\le B_2(n) \equiv { 2^n \choose 2^{n-1} } u_n^{2^n}$$ $$\le B_3(n) \equiv 2^{2^n} (n \sqrt{p_n})^{2^n}.$$</p> <p>Of course, in the last step we can get a better bound by estimating $u_n$ less crudely. It should also be possible to find an analytic bound for $B_1(n)$ that is less crude than $B_2(n)$ (regardless, $B_1(n)$ is easy to evaluate numerically).</p> <p>For reference, I have computed numerical approximations of the actual value $B_0(n)$ up to $n = 20$ (correct up to rounding in the last digit):</p> <pre><code>0: 1 1: 2 2: 10 3: 960 4: 13950764 5: 2.55690851718529e+17 6: 1.77108072043063e+39 7: 8.57834471403602e+86 8: 4.69693103314689e+187 9: 3.24515842436673e+401 10: 8.31078370973184e+853 11: 4.18601441612784e+1793 12: 1.37441368638541e+3755 13: 7.32398012717744e+7815 14: 4.7364530607185e+16172 15: 8.41442697691365e+33355 16: 6.50154879984207e+68684 17: 2.98829955473397e+141188 18: 7.8161464597922e+289271 19: 2.1050522533847e+591950 20: 2.92232330678161e+1209132 </code></pre> <p>Here is a comparison of the bounds:</p> <p><img src="http://fredrikj.net/math/sdpoly.png"/></p> <p>It appears that $B_3$, $B_2$ and $B_1$ asymptotically overestimate the number of bits in $B_0$ less than by a respective factor 2.20, 2.02 and 1.76.</p> <p>As you say, it should possible to do better by taking into account the cancellation that occurs. Perhaps by expressing the coefficients in terms of elementary symmetric polynomials? A lower bound would also be interesting.</p>