Is a polynomial with 1 very large coefficient irreducible? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:53:00Z http://mathoverflow.net/feeds/question/8182 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8182/is-a-polynomial-with-1-very-large-coefficient-irreducible Is a polynomial with 1 very large coefficient irreducible? Gjergji Zaimi 2009-12-08T12:15:03Z 2009-12-09T14:01:43Z <p>I am asking for some sort of generalization to Perron's criterion which is not dependent on the index of the "large" coefficient. (the criterion says that for a polynomial $x^n+\sum_{k=0}^{n-1} a_kx^k\in \mathbb{Z}[x]$ if the condition $|a_{n-1}|>1+|a_0|+\cdots+|a_{n-2}|$ and $a_0\neq 0$ holds then it is irreducible.) </p> <p>This would answer a second question about the existence of n+1-tuples $(a_0,\dots,a_n)$ of integers for which $\sum_{k=0}^n a_{\sigma(k)}x^k$ is always irreducible for any permutation $\sigma$. What happens if we restrict $|a_i| \le O(n)$ ? $|a_i| \le O(\log n)$ ?</p> http://mathoverflow.net/questions/8182/is-a-polynomial-with-1-very-large-coefficient-irreducible/8187#8187 Answer by Vladimir Dotsenko for Is a polynomial with 1 very large coefficient irreducible? Vladimir Dotsenko 2009-12-08T14:28:00Z 2009-12-08T14:28:00Z <p>Thinking of what Perron's criterion essentially means, I would not really expect anything similar to hold for other coefficient. Basically, if the absolute value of the k-th coefficient is greater than the sum of absolute values of other coefficients, it's easy to show that k zeros of the polynomial are strictly inside the unit circle, and $(n-k)$ --- strictly outside it (by Rouche's theorem). So, easy contradictions are to be expected only for $k=n-1$ (and $k=1$ if we invert $x$). Two other remarks supporting this comment: polynomials $x^n-N^n$ suggest that you should not expect anything for the constant term, and polynomials $(x^2-Nx+1)(x^2+Nx+1)=x^4+(2-N^2)x^2+1$ show that $k=2$ (or $n-2$) would not work...</p> <p>As for the second question, it seems quite likely that such examples exist, even with rather restrictive bounds on coefficients.</p> http://mathoverflow.net/questions/8182/is-a-polynomial-with-1-very-large-coefficient-irreducible/8193#8193 Answer by smalldeviations for Is a polynomial with 1 very large coefficient irreducible? smalldeviations 2009-12-08T15:02:19Z 2009-12-08T15:02:19Z <p>Maybe this should have gone in the comments, but I couldn't see the button.</p> <p>In any case, I'm wondering what you hope to be true. There are some obvious 'bad' examples (i.e. $10^{20} x^{2} - 1$, or $x^{2} - 10^{20}$, or $x^{2} - 2 10^{10} x + 10^{20}$) s.t. some coefficients can be arbitrarily larger than (any function of) the others, while the polynomial remains reducible. This isn't terrible (I can't come up with examples like this for all coefficients and all degrees), but certainly means you can't get a condition which <em>just</em> involves the largest coefficient, without regards to spacing.</p> <p>There are also some 'nice' examples. In the same paper that he proves the criterion you mention above, Perron also proves that a polynomial is irreducible if $a_{n-2}$ is sufficiently larger than the rest. </p> <p>The paper 'irreducibility of polynomials' by Dorwart (from the monthly in 1935 (!)) came up on a quick google search, and may be worth looking at.</p> <p>For the last question, playing around with the various divisibility criteria (and Maple) seems to give many, many examples for moderate degree, but my algebra is not strong enough to turn this into a theorem. Of course, if you are only interested in infinitely many n (not all n, since this only works for n being a prime - 1), the cyclotomic polynomials seem like good examples, with all coefficients 1! Is there any reason that you believe a restriction on the size of the coefficients would do something?</p> http://mathoverflow.net/questions/8182/is-a-polynomial-with-1-very-large-coefficient-irreducible/8211#8211 Answer by jp for Is a polynomial with 1 very large coefficient irreducible? jp 2009-12-08T17:02:51Z 2009-12-08T17:02:51Z <p>To your 2nd question:</p> <p>Taking n+1 different primes $p_0, p_1, \dots, p_n$ you can define $a_i := \prod_{j \ne i} p_j$. By a theorem of Eisenstein ("Eisenstein's irreducibility criterion"), you get that any permutation yields an irreducible polynomial.</p> http://mathoverflow.net/questions/8182/is-a-polynomial-with-1-very-large-coefficient-irreducible/8348#8348 Answer by Vladimir Dotsenko for Is a polynomial with 1 very large coefficient irreducible? Vladimir Dotsenko 2009-12-09T14:01:43Z 2009-12-09T14:01:43Z <p>OK, about your second question. Let's consider the polynomial $x^n+2(x^{n-1}+\ldots+x^2+x)+4$. I claim that this polynomial is almost good for your purposes: if we permute all coefficients except for the leading one, it remains irreducible. Proof: if the constant term becomes 2 after the permutation, use Eisenstein, if not, look at the Newton polygon of this polynomial mod 2 - you can observe that if it is irreducible, it has to have a linear factor, which is easily impossible. </p> <p>[If we allow to permute all coefficients, I would expect that something like $9x^n+6(x^{n-1}+\ldots+x^2+x)+4$ would work for nearly the same reasons...]</p>