3
$\begingroup$

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

$\endgroup$
7
  • 3
    $\begingroup$ Notice that $\deg(f\circ g)=\deg(f)\deg(g)$. Thus anything of prime degree can not be decomposed in your sense. $\endgroup$ – Lubin May 29 at 20:48
  • 2
    $\begingroup$ What is the correct definition? Of course Wikipedia is no arbiter of mathematical authority, but the definition in the post is what Wikipedia has. $\endgroup$ – LSpice May 29 at 22:07
  • 3
    $\begingroup$ 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$. $\endgroup$ – Robert Israel May 30 at 5:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Arno Fehm May 30 at 6:12
  • 1
    $\begingroup$ and even then I thought the claimed statement about irreduciblity is only conjectured, but not yet proven for all $t$. $\endgroup$ – Arno Fehm May 30 at 6:18
6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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