What fraction of polynomials with integer coefficients are indecomposable?

Question

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$?

Answer 1

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

Answer 2

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.

Now I suspect (though don't have a proof) that the ideal case is generic enough that the remaining degenerate cases contribute lower order terms in the actual probability.