Irreducible polynomials with constrained coefficients - MathOverflow

Irreducible polynomials with constrained coefficients

2009-12-06T06:18:34Z

Over at the Cafe, after reading about TWF 285, I asked more-or-less

About how many polynomials with coefficients in $\{\pm 1\}$ and of degree $d$ are irreducible?

and that's what I want to ask here.

The first no-go analysis: since if $P$ is reducible, then it is reducible mod $3$, we get that the number of reducible such is $O(\frac{d-1}{d}3^d)$; but that's clearly too large already to help much; reducing mod $2$ we can't distinguish polynomials anymore!

Answer by Greg Kuperberg for Irreducible polynomials with constrained coefficients

2009-12-06T07:54:21Z

I tested this question with Sage, and the experiment suggests a clear pattern of asymptotics. Most polynomials are irreducible. Of the reducible ones, a third are of course divisible by $x$ (Edit: If 0 coefficients are allowed; see below.) An $O(1/\sqrt{d})$ fraction are each divisible by $x+1$ and $x-1$. That's because if $p$ is such a polynomial, then $p(x) \bmod x+1$ is understood as a random walk in the integers, and the same for $x-1$. Of the others of degree $d$, an $O(1/d)$ fraction are divisible by certain quadratic polynomials such as $x^2+x+1$. The remainder $p(x) \bmod x^2+x+1$ can be interpreted as a random walk in the triangular lattice in the plane. Addendum: Actually, the only polynomials that can behave this way are cyclotomic polynomials. Divisibility by any specific non-cyclotomic polynomial is exponentially rare.

It could be very hard to prove a picture like this, although I don't really know. There is a similar picture for integer matrices with bounded entries: There is a sequence of explanations for why they might be singular, beginning with that two rows might be proportional. It is still a big open problem to prove that these explanations give you the correct asymptotics for the number of singular matrices of this type, although there are great partial results by Tao-Vu and Rudelson-Vershynin.

Since the sage code was requested, here is an improved version:

maxdegree = 16
maxcyclo = 400
displayother = 11

R.<x> = ZZ[]
cyclos = {}
for k in xrange(1,maxcyclo+1):
    c = cyclotomic_polynomial(k,x)
    if c.degree() <= maxdegree: cyclos[k] = c

def tally(key):
    if not key in counts: counts[key] = 0
    counts[key] += 1

for degree in xrange(1,maxdegree+1):
    print
    counts = {}
    total = 0
    for n in xrange(2^degree):
        total += 1
        p = x^degree
        for k in xrange(degree):
            choice = (int(n)>>k)%2
            p += (2*choice-1)*x^k
        cdiv = False
        for k in cyclos:
            if not p%cyclos[k]:
                tally('div by C(%2d)' % k)
                cdiv = True
        if cdiv: continue
        f = factor(p)
        if len(f) > 1:
            if degree <= displayother: print p,'=',f
            tally('other reducible')
        else: tally('irreducible')
    counts['total'] = total
    print '\nDegree',degree
    for key in sorted(counts): print '%s: %d' % (key,counts[key])

It is clearly true that the fraction of these polynomials that are divisible by a cyclotomic polynomial of degree $c$ decays as a power law, in fact as $O(1/d^{c/2})$. It is also clearly true that the fraction divisible by any other fixed polynomial decays exponentially. However, the more careful experiment found more exceptional factorizations than I thought. There are a lot of polynomials whose roots are close to the unit circle even though they are not on the unit circle. For instance $x^3+x+1$ is like this and comes in 8 versions (such as also $x^3-x^2+1$). If the number of these near misses grows fast enough, then the asymptotics that I suggested has to be adjusted, and the statistical problem is probably then even more difficult.

Per JSE's remark above, I misunderstood the original question to mean that the coefficients are in $\{-1,0,1\}$. If $0$ is not allowed, then congruence conditions develop that make it much more likely for a random polynomial to be irreducible. I replaced the code to reflect the actual question, although if anyone is interested the old code is still there in the edit history. (I personally think that the ternary question is at least as interesting.) In particular, if the degree is one less than a prime, then as Mark Meckes suggests below, the polynomial $p$ can only be divisible by a cyclotomic polynomial by being a cyclotomic polynomial.

Here is some typical output from the code:

Degree 14
div by C( 3): 1126
div by C( 5): 244
div by C( 6): 1126
div by C(10): 244
div by C(15): 19
div by C(30): 19
irreducible: 13310
other reducible: 378
total: 16384

(The total does not add up because a polynomial can be divisible by more than one cyclotomic polynomial.)

Answer by Mark Meckes for Irreducible polynomials with constrained coefficients

2009-12-06T21:53:26Z

I considered a related question in Theorem 6 of this paper. Although it's formulated differently (in terms of random circulant matrices), my result estimates the fraction of $\pm 1$ polynomials of degree $d$ which are divisible by some cyclotomic polynomial of order dividing $d+1$. If $d$ is odd, this fraction is of the order $d^{-1/2}$. If $d$ is even, I derived two different upper bounds which imply that the fraction is smaller than in the even case; in particular, if $d+1$ is prime then $\pm \sum_{k=0}^d x^k$ are (pretty obviously) the only such polynomials.

This is clearly all closely related to the observations in Greg's answer.

Edit: Corrected a few effects of typing without thinking/reading.

Answer by tdnoe for Irreducible polynomials with constrained coefficients

2009-12-07T07:34:52Z

Sequence http://www.research.att.com/~njas/sequences/A087481 lists the number of such irreducible polynomials up to degree 18.

Answer by Bjorn Poonen for Irreducible polynomials with constrained coefficients

2009-12-27T00:29:12Z

Your problem is hard, but here are some things that can actually be proved!

Let $S_d$ be the set of polynomials of degree $d$ with all $d+1$ coefficients in ${\pm 1}$.

1) $|S_d| \gg 2^d/d$ as $d \to \infty$ through even integers.

Proof: By Theorem 2 in a paper by Brillhart, Filaseta, and Odlyzko, $f$ will be irreducible if

(a) $f(2)$ is prime,

(b) $f(1) \ne 0$, and

The condition that $d$ is even guarantees (b). To guarantee (c), restrict attention to $f$ whose first $100$ coefficients are $+1$, and use Rouch\'e's theorem to show that $f$ has the same number of zeros satisfying $|z|<3/2$ as does $x^d+x^{d-1}+\cdots+1$, i.e., all $d$ of them. The values of these $f$ at $2$ are the odd integers in a certain interval, so the prime number theorem gives the required number of $f$ satisfying (a). $\square$

2) The Generalized Riemann Hypothesis implies that there are infinitely many $d$ for which every $f$ in $S_d$ is irreducible.

Proof: GRH implies that there are infinitely many primes $p$ for which $2$ is a primitive root. If $d+1$ is such a prime, then $x^d+x^{d-1}+\cdots+1$ is irreducible mod $2$, so every $f \in S_d$ will be irreducible over $\mathbf{Z}$. $\square$

3) There exist infinitely many $d$ for which at least $50\%$ of the polynomials in $S_d$ are irreducible.

Proof: Let $d=2^n-1$ for any $n \ge 1$. If $f \in S_d$, then $f(x+1) \equiv x^d \pmod{2}$. Thus $f(x+1)$ is Eisenstein at $2$ half of the time. $\square$

A final remark: It is conjectured that the fraction of irreducible polynomials among those of degree $d$ with 0,1 coefficients tends to $1$ as $d \to \infty$: see this paper by Konyagin. The same is likely true for your problem, as Greg suggests, but it also seems that the best you can hope for at the moment are partial results such as the ones above.