MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

share|cite|improve this question
As far as I checked (didn't check linear terms) Vladimir's example can be simplified to taking the coefficients $p, q, pq, pq, \dots, pq$ for primes $p\ne q$. – j.p. Dec 12 '09 at 17:59
up vote 3 down vote accepted

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.

[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...]

share|cite|improve this answer
Thanks! The suggestion works (I think) with (4,9,25,30,30...,30). The problem with (4,9,6...) is when a_k=4,a_{n-k}=9 for some k, which by looking at the Newton polygon mod2, mod3 gives the polynomial as a product fg where f is degree k and f,g are irreducible mod2, mod3. I couldn't find a contradiction in that case. When we introduce 25 such "symmetric" factorizations are ruled out. I haven't checked when 4,9 or 25 are leading yet (Eisenstein doesn't apply anymore). – Gjergji Zaimi Dec 9 '09 at 16:08
If someone needs a reference for the statement about the Newton polygon (like I did), take a look at the corollary at the bottom of page two in – j.p. Dec 9 '09 at 16:19
@Gjergji: good point - I was thinking along the same line after I walked in the street having written that suggestion. However, what you say about how to mend my example seems to be a good idea. – Vladimir Dotsenko Dec 9 '09 at 18:11
@jp: sorry for not providing a reference - I was in a hurry. An excellent source on many a theorem about polynomials is <a href="… book</a> (for facts I am referring to, see page 53, Dumas' theorem (and a bit before this theorem), but there are lots of other useful things there). – Vladimir Dotsenko Dec 9 '09 at 18:12
okay, I don't know what happened to the long google books url in the previous comment, so let me re-type it in a better way: – Vladimir Dotsenko Dec 9 '09 at 18:15

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

As for the second question, it seems quite likely that such examples exist, even with rather restrictive bounds on coefficients.

share|cite|improve this answer

To your 2nd question:

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.

share|cite|improve this answer
Cute! But it badly fails the desired restriction $|a_i|=O(n)$. – Mark Meckes Dec 8 '09 at 17:59

Maybe this should have gone in the comments, but I couldn't see the button.

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 just involves the largest coefficient, without regards to spacing.

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.

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.

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?

share|cite|improve this answer
Well, I was trying (1,1,..,k) for large enough k, restricting the height makes the search...harder. The cyclotomic polynomials are unfortunately the only family of arbitrarily large degree I know. Then there are values like (1,1,1,0,...,0,0) which for all n have a very small fraction of reducible polynomials. – Gjergji Zaimi Dec 8 '09 at 15:33
How about if the polynomial is monic and has constant term 1, and the total norm of all of the small coefficients is bounded by a constant. – Greg Kuperberg Dec 8 '09 at 19:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.