Counting Irreducible polynomials: Van Der Waerden, Mahler measure, Chela

We want to understand statistics of “random” integer polynomials. How do we choose the polynomials?

There are several ways to order polynomials — by degree, discriminants, heights of the coefficients etc etc.

Here we fix the degree and focus on the ordering by the coefficient heights.

If we take $f(x) =x^{d}+a_{d-1} x^{d-1}+\cdots+a_{1} x+a_{0}$ , where $|a_i| \le N$ are chosen uniformly, how do the statistics behave?

1. For instance, what fraction of the polynomials are irreducible?
2. If the coefficients are chosen uniformly from $0, 1$ or say some bounded set, how likely is it to get a reducible polynomial?
3. What is distribution of Galois groups for a random polynomial? In general how do the invariants of the number fields distribute?

Van Der Waerden:

The main ideas is the relation between the height and a measure of complexity called Mahler measure.

$\displaystyle M(f)=|a| \prod_{\left|\alpha_{i}\right| \geq 1}\left|\alpha_{i}\right|=|a| \prod_{i=1}^{d} \max \left\{1,\left|\alpha_{i}\right|\right\}$ where

$\displaystyle f(z)=a\left(z-\alpha_{1}\right)\left(z-\alpha_{2}\right) \cdots\left(z-\alpha_{d}\right) .$

We can see that ${M(f)}$ as an integral on the unit circle –“geometric mean” of ${f(e^{i \theta})}$ .

$\displaystyle M(f)=\exp \left(\frac{1}{2 \pi} \int_{0}^{2 \pi} \ln \left(\left|f\left(e^{i \theta}\right)\right|\right) d \theta\right) = \lim_{\tau \rightarrow 0} \left(\frac{1}{2 \pi} \int_{0}^{2 \pi}\left|f\left(e^{i \theta}\right)\right|^{\tau} d \theta\right)^{1 / \tau}$

It’s easy to see that the multiplicativity property

$\displaystyle M(fg) = M(f) M(g)$

Different measures of complexity: a) Height

$\displaystyle f=a_{0}+a_{1} x+a_{2} x^{2}+\cdots+a_{d} x^{d},$ the height ${H(f)}$ is defined to be the largest magnitude of the coefficients:

$\displaystyle H(f)=\max _{i}\left|a_{i}\right|$

b) Mahler measure

c) Length of ${f}$ is defined to be

$L(f) = \sum_{i=0}^{d}\left|a_{i}\right|$

All of these measures are comparable up to factors that only depend on the degree. That is we have

$\displaystyle {d \choose {\lfloor d / 2\rfloor} }^{-1} H(f) \leq M(f) \leq \sqrt{d+1}H(f)$

$\displaystyle L(f) \leq 2^{d} M(f) \leq 2^{d} L(f)$

$\displaystyle H(f) \leq L(f) \leq(d+1) H(f)$

Main ideas of Van Der Waerden :

Van Der Waerden now counts reducible polynomials by counting all possible products ${f(x)g(x)}$ such that ${P(x) =f(x)g(x)}$ is of height bounded by ${N}$ .

Using the Mahler measure we have

$\displaystyle M(f)M(g) =M(P) \le c_d N$ . Thus for each values of ${m}$ and ${n}$ with ${mn \le c_d N}$ , we can count all the polynomials with ${M(f)=m}$ and ${M(g)=n}$ .

For each value of ${m}$ , and fixing degree of ${f}$ to be ${k}$ , we get the bound

$\displaystyle 2 k(2 m+1)^{k-1}(2 n+1)^{d-k} \ll_{k, d} m^{k-1} N^{d-k} \ll_{d} m^{k-1} c^{d-k} \ll_{d} N^{k-1}\left(\frac{N}{m}\right)^{d-k}$

and hence summing over ${m}$ get

$\displaystyle \ll_{d} 2\sum_{m=1}^{N} m^{k-1}\left(\frac{N}{m}\right)^{d-k}=2 N^{d-k} \sum_{m=1}^{N} \frac{1}{m^{d-2 k+1}}$

So we see that the number of reducible polynomial with a factor of degree ${k \le d/2 }$ is at most

$\displaystyle 2 N^{d-k} \sum_{m=1}^{N} \frac{1}{m^{d-2 k+1}}$ .

This quantity is

${\ll_d N^{d-k}}$ or ${\ll_{d} N^{d-k} \log N}$

according to ${k < d/2}$ and ${k=d/2}$ respectively.

Summing over the degrees ${1\le k \le d/2}$ , we get that the number of reducible polynomials is ${O_{d}(N^{d-1}).}.$

This already show that the fraction of reducible polynomials of degree ${d}$ goes to ${0}$ as ${N \rightarrow \infty}$ . I

n fact, we see that the probability of the polynomial being reducible is ${O(\frac{1}{N})}$ for ${d >2}$ . This is the best bound we can expect because polynomial with vanishing constant coefficients already contribute ${\frac{1}{2N+1}.}$

Note that for ${d=2}$ , the contribution for ${k=1}$ gives ${N\log N}$ and hence the probability is slightly larger ${\frac{\log N}{N}}$ . In fact counting ${(x+a)(x+b)}$ such that the product has height atmost ${N}$ , we get that ${|ab| \le N}$ and hence the reducible polynomials contribute $\sum_{a=1}^{\sqrt N} \frac{N}{a} \asymp N\log N$

Chela’s improved results: Chela gets more precise estimates on the reducible polynomials. In fact, the number of reducible polynomials of degree ${d>2}$ is given by

$\displaystyle 2^{d}\left(\zeta(d-1)-\frac{1}{2}+\frac{\alpha_{d}}{2^{d-1}}\right)N^{d-1} \left( 1+ o(1) \right)$

where ${\alpha_d}$ is the volume of the region

$\displaystyle \left|x_{1}\right| \leq 1, i=1, \ldots, d-1,\left|\sum_{i=1}^{d-1} x_{i}\right| \leq 1$

For ${d=2}$ , the number of reducible quadratic polynomials is given by

$\displaystyle 2 N \ln (N)+(2 \gamma +o(1))N$

Main ideas: Reduce the counting to polynomials which have a linear factor because rest of them contribute ${O(N^{d-2}}$ . Now count polynomials with a fixed linear factor ${X+a}$ . There will be overcounting of polynomials with multiple linear factors, but such polynomials have a degree ${2}$ factor and hence contribute only ${N^{d-2}}$ .

For instance ${a=0}$ counts polynomials with no constant terms– ${\sim (2N)^{d-1}}$

The cases ${|a|=1, |a| =N}$ and ${1<|a|<N}$ have to be dealt separately.

If ${1<|a|<N}$ , writing conditions for ${(x+a)g(x)}$ to have at most atmost ${N}$ , you get a bound ${~\frac{2N}{|a|}^{d-1}}$

and thus summing over ${a}$ , we get

$\displaystyle 2^dN^{d-1} \sum_{a=2}^{N-1} \frac{1}{|a|^{d-1}} =2^d N^{d-1} \left (\zeta(d-1) -1 + o(1)\right)$

${|a|=N}$ , it’s easy to see that the contribution is small.

Finally ${|a|=1}$ corresponds to counting with the lattice points inside

$\displaystyle \{ (a_0, a_1, \cdots, a_{d-1}) : a_{d-1}+\cdots+a_{0} =0 , |a_i| \le N \}$

which by rescaling by ${N}$ can be seen to be approximately the volume of the region

$\displaystyle \left|x_{1}\right| \leq 1, i=1, \ldots, d-1,\left|\sum_{i=1}^{d-1} x_{i}\right| \leq 1.$

Putting all these together we get the count

$\displaystyle 2^{d}\left(\zeta(d-1)-\frac{1}{2}+\frac{\alpha_{d}}{2^{d-1}}\right)N^{d-1} \left( 1+ o(1) \right).$

(Added Later) Rivin’s idea: To capture reducibility in terms of algebraic relations on the coefficients and then counting points on the corresponding variety.

For instance if a degree ${k}$ polynomial ${g(x)}$ is a factor of ${P(x) = (x-\alpha_1)(x-\alpha_2) \cdot (x-\alpha_d)}$ , then the constant term ${c_g}$ of ${g(x)}$ divides constant term of ${P(x)}$ and is a product of a subset of ${k}$ roots ${\alpha_i}$ . Hence we have the equation

$\displaystyle \prod_{1 \leq i_{1} \leq \cdots \leq i_{k} \leq d}\left(\alpha_{i_{1}} \alpha_{i_{2}} \ldots \alpha_{i_{k}}-c_g\right)=0$ For each choice of the constant term ${c_g}$ and ${c_P}$ , the above gives a polynomial relations between the coefficient of ${P}$ . Apply Schwarz-Zippel type of ideas one bound the number of solutions to the polynomial relations. (To apply Schwarz-Zippel you might have to embed ${[-N, N]}$ inside a finite field ${F_p}$ for ${p \asymp N.}$ ) We get a bound ${N^{d-2}}$ for each constant term ${c_g|c_P}$ , and summing over ${c_P}$ we get ${N^{d-1}\log N}$ . (Note that this bound is weaker, but this idea allows us to count other statistics of the polynomials like probability of having a given Galois group)

Remarks:

1. What about other models of ordering the polynomials?
2. What happens if we change how we pick the coefficients? In the case of where each coefficient is picked uniformly from a small set like say ${0}$ and ${1}$ . 3. What about non-uniform distributions on ${[-N, N]}$ ? 4. What if we fix some of the coefficients?

Resources:

Van der Waerden, B. L. Die Seltenheit der reduziblen Gleichungen und der Gleichungen mit Affekt. Monatsh. Math. Phys., 43(1):133?147, 1936
Mahler, K. An Application of Jensen?s Formula to Polynomials. Mathematika, vol. 7, no. 2, 1960, pp. 98?100., doi:10.1112/S0025579300001637.
Chela, R. Reducible polynomials. J. Lond. Math. Soc. 38 (1963), 183?188.
Rivin, I. Galois Groups of Generic Polynomials.

Share this:

Related

Leave a comment Cancel reply