19
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Looks like you want the coefficents to be in {-1,0,1}, not {-1,1}, right? $\endgroup$
    – JSE
    Dec 6, 2009 at 20:33
  • $\begingroup$ No, the constraint is copied from the linked n-Cafe post; there are $2^d$ such polynomials, which is why having at most $O(3^d(d-1)/d)$ reducible polynomials isn't helpful in estimating the number of irreducibles in the constrained set! $\endgroup$ Dec 6, 2009 at 21:08

4 Answers 4

20
$\begingroup$

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

(c) all complex zeros of $f$ have absolute value less than $3/2$.

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.

$\endgroup$
1
  • $\begingroup$ oooh, nice! I've actually been away for a couple weeks, and didn't bring any cookies with me... I'm tempted to make this "The answer"; although I'm not sure a "the answer" is appropriate for my question anymore. Thanks! in any case. $\endgroup$ Jan 4, 2010 at 22:28
14
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Could you post a link to the sage worksheet? Now I'm all curious. $\endgroup$ Dec 6, 2009 at 15:19
  • $\begingroup$ Oh, yes, I certainly agree there's a large family of interesting questions here. $\endgroup$ Dec 7, 2009 at 19:30
  • $\begingroup$ Although I bet most of them are open. I'm not sure how much more there is to say about the question for now. $\endgroup$ Dec 7, 2009 at 22:44
  • $\begingroup$ Actually there are some things that can be proved - I've put them in a separate answer. $\endgroup$ Dec 27, 2009 at 1:20
3
$\begingroup$

Sequence http://www.oeis.org/A087481 lists the number of such irreducible polynomials up to degree 18.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Shouldn't the decay depend on the degree of the cyclotomic polynomial rather than on its order? $\endgroup$ Dec 6, 2009 at 22:03
  • $\begingroup$ Greg: maybe the errors I just corrected will clarify that in part. One of the two upper bounds I mentioned without stating does directly involve the degrees as you suggest. $\endgroup$ Dec 7, 2009 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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