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

2more comments