show/hide this revision's text 4 Misread the question

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$. Of the others of degree $d$, x$ (Edit: If 0 coefficients are allowed; see below.) An $O(3^d/\sqrt{d})$ 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(3^d/d)$ 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.

for n in xrange(3^degree): if n%3 == 1xrange(2^degree): continue # Skip if no constant term int(n)>>k)%2

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 14div by C( 3): 1126div by C( 5): 244div by C( 6): 1126div by C(10): 244div by C(15): 19div by C(30): 19irreducible: 13310other reducible: 378total: 16384
(The total does not add up because a polynomial can be divisible by more than one cyclotomic polynomial.)
show/hide this revision's text 3 Posted Sage code

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

maxdegree = 10maxcyclo = 200displayother = 7R.<x> = ZZ[]cyclos = {}for k in xrange(1,maxcyclo+1):    c = cyclotomic_polynomial(k,x)    if c.degree() <= maxdegree: cyclos[k] = cdef tally(key):    if not key in counts: counts[key] = 0    counts[key] += 1for degree in xrange(1,maxdegree+1):    counts = {}    total = 0    for n in xrange(3^degree):        if n%3 == 1: continue      # Skip if no constant term        total += 1        p = x^degree        for k in xrange(degree):            choice = (int(n)/int(3^k))%3            p += (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.
show/hide this revision's text 2 addendum

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$. Of the others of degree $d$, $O(3^d/\sqrt{d})$ 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$, $O(3^d/d)$ 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.

I 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.
show/hide this revision's text 1