nt.number theory - Irreducible polynomials with constrained coefficients

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