Irreducible polynomials with constrained coefficients - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:33:28Z http://mathoverflow.net/feeds/question/7969 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7969/irreducible-polynomials-with-constrained-coefficients Irreducible polynomials with constrained coefficients some guy on the street 2009-12-06T06:18:34Z 2009-12-27T00:29:12Z <p>Over at the Cafe, after reading about TWF 285, I <a href="http://golem.ph.utexas.edu/category/2009/12/this%5Fweeks%5Ffinds%5Fin%5Fmathematic%5F46.html#c029973" rel="nofollow">asked</a> more-or-less </p> <blockquote> <p>About how many polynomials with coefficients in $\{\pm 1\}$ and of degree $d$ are irreducible?</p> </blockquote> <p>and that's what I want to ask here.</p> <p>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!</p> http://mathoverflow.net/questions/7969/irreducible-polynomials-with-constrained-coefficients/7978#7978 Answer by Greg Kuperberg for Irreducible polynomials with constrained coefficients Greg Kuperberg 2009-12-06T07:54:21Z 2009-12-06T22:31:27Z <p>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$ (<strong>Edit:</strong> 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.</p> <p>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.</p> <p><hr /></p> <p>Since the sage code was requested, here is an improved version:</p> <pre><code>maxdegree = 16 maxcyclo = 400 displayother = 11 R.&lt;x&gt; = ZZ[] cyclos = {} for k in xrange(1,maxcyclo+1): c = cyclotomic_polynomial(k,x) if c.degree() &lt;= 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)&gt;&gt;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) &gt; 1: if degree &lt;= 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]) </code></pre> <p>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.</p> <p><hr /></p> <p>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.</p> <p>Here is some typical output from the code:</p> <pre><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 </code></pre> <p>(The total does not add up because a polynomial can be divisible by more than one cyclotomic polynomial.)</p> http://mathoverflow.net/questions/7969/irreducible-polynomials-with-constrained-coefficients/8037#8037 Answer by Mark Meckes for Irreducible polynomials with constrained coefficients Mark Meckes 2009-12-06T21:53:26Z 2009-12-07T00:45:30Z <p>I considered a related question in Theorem 6 of <a href="http://front.math.ucdavis.edu/0902.2472" rel="nofollow">this paper</a>. 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.</p> <p>This is clearly all closely related to the observations in Greg's answer.</p> <p><b>Edit:</b> Corrected a few effects of typing without thinking/reading.</p> http://mathoverflow.net/questions/7969/irreducible-polynomials-with-constrained-coefficients/8086#8086 Answer by tdnoe for Irreducible polynomials with constrained coefficients tdnoe 2009-12-07T07:34:52Z 2009-12-07T07:34:52Z <p>Sequence <a href="http://www.research.att.com/~njas/sequences/A087481" rel="nofollow">http://www.research.att.com/~njas/sequences/A087481</a> lists the number of such irreducible polynomials up to degree 18.</p> http://mathoverflow.net/questions/7969/irreducible-polynomials-with-constrained-coefficients/9838#9838 Answer by Bjorn Poonen for Irreducible polynomials with constrained coefficients Bjorn Poonen 2009-12-27T00:29:12Z 2009-12-27T00:29:12Z <p>Your problem is hard, but here are some things that can actually be proved!</p> <p>Let $S_d$ be the set of polynomials of degree $d$ with all $d+1$ coefficients in ${\pm 1}$.</p> <p>1) $|S_d| \gg 2^d/d$ as $d \to \infty$ through even integers.</p> <p>Proof: By Theorem 2 in <a href="http://www.cms.math.ca/cjm/v33/cjm1981v33.1055-1059.pdf" rel="nofollow">a paper by Brillhart, Filaseta, and Odlyzko</a>, $f$ will be irreducible if</p> <p>(a) $f(2)$ is prime,</p> <p>(b) $f(1) \ne 0$, and</p> <p>(c) all complex zeros of $f$ have absolute value less than $3/2$.</p> <p>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|&lt;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$</p> <p>2) The Generalized Riemann Hypothesis implies that there are infinitely many $d$ for which every $f$ in $S_d$ is irreducible.</p> <p>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$</p> <p>3) There exist infinitely many $d$ for which at least $50\%$ of the polynomials in $S_d$ are irreducible.</p> <p>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$</p> <p>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 <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa88/aa8844.pdf" rel="nofollow">this paper by Konyagin</a>. 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.</p>