# What fraction of polynomials with integer coefficients are indecomposable?

It is well-known that "most" integers are composite: the Prime Number Theorem tells us that only about $$1/\log(N)$$ of the integers in the interval $$1 \ldots N$$ are prime. For polynomials, the opposite is true; "most" polynomials are irreducible. More formally, let $$p(x)$$ be a polynomial of degree $$d$$ whose coefficients are integers selected uniformly at random from $$[-t, t]$$. It is known that for any fixed $$t$$, the probability that $$p(x)$$ is irreducible (over the integers) tends to 1 as $$d \rightarrow \infty$$; in fact the probability that $$p(x)$$ is reducible is exponentially small in $$d$$.

Recall that $$p(x)$$ is decomposable if there exist polynomials $$f(x), g(x)$$ both with integer coefficients and degree $$> 1$$ such that $$p(x) = f(g(x))$$; otherwise $$p(x)$$ is called indecomposable. Let $$p(x)$$ be generated randomly as in my reducibility example. What is the probability that $$p(x)$$ is indecomposable (over the integers) as a function of $$d$$ and $$t$$?

• Notice that $\deg(f\circ g)=\deg(f)\deg(g)$. Thus anything of prime degree can not be decomposed in your sense. – Lubin May 29 at 20:48
• What is the correct definition? Of course Wikipedia is no arbiter of mathematical authority, but the definition in the post is what Wikipedia has. – LSpice May 29 at 22:07
• Note that if $p$ is decomposable, $p'$ is reducible by the Chain Rule. Of course the coefficients of $p'$ are not uniform; nevertheless I would suspect that the probability of $p'$ being irreducible also goes to $1$ as $d \to \infty$. – Robert Israel May 30 at 5:53
• The statement about irreducibility is not quite correct: You can obtain probability tending to 1 only if you condition on the event that the constant coefficient is not 0. – Arno Fehm May 30 at 6:12
• and even then I thought the claimed statement about irreduciblity is only conjectured, but not yet proven for all $t$. – Arno Fehm May 30 at 6:18

Note that as soon as $$p$$ is decomposable, its Galois group $${\rm Gal}(p/\mathbb{Q})\leq S_d$$ is imprimitive (in fact it is contained in a wreath product), in particular it is not $$A_{d}$$ or $$S_{d}$$. Many of the results for random polynomials that give irreducibility with high probability also give Galois group $$S_d$$ (or sometimes $$S_d$$ or $$A_d$$) with high probability. See for example this paper by Bary-Soroker and Kozma, which gives group $$S_d$$ or $$A_d$$ with probability tending to 1 (for e.g. coefficients uniformly distributed in $$\{1,\dots,210\}$$), or this paper of Bary-Soroker, Koukoulopoulos and Kozma which gives group $$S_d$$ or $$A_d$$ (again for certain ranges of coefficients) with probability at least $$1-d^{-c}$$ for a constant $$c>0$$.
By looking at the constant term, it's easy to show the probability is bounded by $$\frac{d - \phi(d) - 2}{2t}$$, albeit pretty weak. $$\phi(d) = \{1 \leq q \leq d: q \nmid d\}$$.
Let $$h = f \circ g$$ and $$h(x) = c_\ell x^d + \ldots + c_0$$, $$f(x) = a_p x^p + \ldots + a_0$$ and $$g(x) = b_q x^q + \ldots + b_0$$, where $$d = pq$$, $$p, q > 1$$.
Then we get $$c_0 = a_p b_0^p + a_{p - 1} b_0^{p - 1} + \ldots a_0$$. So if $$c_0$$ and $$b_0$$ are fixed, the number of tuples $$(a_0, \ldots, a_p)$$ that satisfy the constant term equation is at most $$1/(2t)$$ times the total number of tuples (i.e., with components lying in $$[-t, t]$$): for fixed $$(a_1, \ldots, a_p)$$, there is only a single admissible choice of $$a_0$$. Since there are $$d - \phi(d) - 2$$ choices of $$(p, q)$$ pairs, this gets the stated bound.
Now one can similarly obtain $$d$$ additional equations for higher order terms, like $$c_1$$, $$c_2$$, etc, which yield similar linear constraints for $$(a_0, \ldots, a_p)$$. As long as all these constraints are linearly independent, each constraint would contribute an additional $$1/(2t)$$ factor. So in such ideal case, you would get $$(d - \phi(d) - 2)(2t)^{-d}$$. In fact since the number of equations is $$d$$, greater than the number of variables $$a_0, \ldots, a_p$$, it's highly likely there will be no solutions.