Random Diophantine polynomials: Percent solvable?

Question

Suppose one generates a random polynomial of degree $d$ with integer coefficients uniformly distributed within $[-c_\max,c_\max]$. For example, for $d=8$, $|c_\max|=100$, here is one random polynomial: $$ -46 x^8-19 x^7+14 x^6-75 x^5+94 x^4+18 x^3-48 x^2+29 x-61=0 \;. $$

Q. What is the probability that such a random $(d,c_\max)$-polynomial has at least one integer solution?

Here is a bit of data, based on $10^5$ polynomials for each $d=1,\ldots,10$ with $|c_\max|=100$:

---

         

---

I.e., For $d=1$, about $5.5$% have integer solutions, while for $d=10$, about $0.8$% have integer solutions. The above displayed degree-$8$ example has the solution $x=-1$, and in addition these $7$ non-integer roots: $$ -1.54767,\\ -0.0337862 \pm 0.794431 i,\\ 0.196632 \pm 1.19591 i,\\ 0.904467 \pm 0.323333 i \;. $$

If the constant coefficient is $0$, then of course $x=0$ is a solution. So $\frac{1}{2 c_\max+1}$ is a lower bound, in the above chart, $\frac{1}{201} \approx 0.5$%.

Answer 1

The case of degree $1$ has been handled by quid. This turns out to be an exceptional case, and for all degrees $d\ge 2$ one can show that there is a constant $K(d)$ such that the number of degree $d$ polynomials with coefficient bounded by $C$ and having an integer root is $$ \sim K(d) (2C+1)^d. $$ Moreover, for large $d$, the constant $K(d)$ is approximately equal to $$ 1+ 2 \frac{\sqrt{6}}{\sqrt{\pi d}}. $$ In this approximation, the term $1$ gives the contribution of polynomials having $0$ as a root, and the second term $\sqrt{6/\pi d}$ accounts for polynomials having a root at $1$ (and another similar contribution from those having a root at $-1$). For large $d$, the effect of having roots at integers larger than $1$ in size is substantially smaller.

For $d=10$ and $C=100$ this approximation is about $0.93\%$ which is a little higher than your data, but for $d=9$ it is much closer (the approximation being $0.96\%$). Perhaps the Monte-Carlo simulations haven't fully stabilized?

Clearly the number of polynomials having a root at $0$ is $(2C+1)^d$. Now suppose that $k\ge 1$ is a positive integer, and consider polynomials having a root at $k$ (naturally the same holds for $-k$). Write $f(x)=a_dx^d+\ldots+a_0 = (x-k) (b_{d-1}x^{d-1} + \ldots +b_0)$. Note that $kb_0$ must lie in $[-C,C]$ giving us about $(2C+1)/k$ choices for $b_0$. Next if $b_0$ is fixed, then $-kb_1+b_0$ must lie in $[-C,C]$ giving us about $(2C+1)/k$ choices for $b_1$. Proceeding in this manner, we get at most $(2C+1)/k$ choices for each $b_j$, with the additional constraint that the final $b_{d-1}$ must also be constrained to be in $[-C,C]$. It follows that there are at most $(2C+1)^d/k^d$ possible polynomials having a root at $k$. This upper bound summed over $k$ converges for $d\ge 2$ (but not for $d=1$), and shows that the proportion of polynomials having a large integer root is very small. Thus at any rate the number of polynomials having an integer root is at most $(1+2\zeta(d)) (2C+1)^d$, and by similar reasoning we may see that the number of polynomials having two integer roots is at most $O((2C+1)^{d-1+\epsilon})$.

By our work above, the number of polynomials having an integer root is essentially the sum of those polynomials having a root at $k$ over integers $|k|\le K$ for some slowly growing $K$. Now for a given $k\ge 1$, for the polynomial to have a root at $k$ means that given $a_1$, $\ldots$, $a_d$ (all chosen in $[-C,C]$) we must have the sum $a_1k+a_2k^2+\ldots +a_d k^d$ lying in $[-C,C]$ (which then uniquely determines $a_0$). But now we may write $a_j=Cx_j$, and then the $x_j$ behave like independent random variables chosen uniformly from $[-1,1]$ and then we are asking for the probability that $x_1 k+x_2k^2+\ldots +x_d k^d$ also lies in $[-1,1]$. Clearly this probability must be some constant $K(d,k)$ (which by our earlier work is at most $1/k^d$), and therefore our claimed asymptotic holds with $$ K(d) = 1+ 2\sum_{k=1}^{\infty} K(d,k). $$

Lastly we come to the approximation for $K(d)$ for large $d$. Note that the contribution of terms $k\ge 2$ is $O(2^{-d})$ is extremely small. It remains to understand $K(d,1)$ -- the probability that the sum of $d$ independent random variables chosen uniformly from $[-1,1]$ also lies in $[-1,1]$. For large $d$, the sum of $d$ independent random variables is approximately normal with mean $0$, and variance $d/3$. From this our approximation follows. By using Parseval, one can also see that $$ K(d,1) = \int_{-\infty}^{\infty} \Big(\frac{\sin (\pi x)}{\pi x}\Big)^{d+1} dx, $$ from which we can calculate, for example, that $K(10,1)=0.4109\ldots$ which is pretty close to the approximation $0.437\ldots$.

Answer 2

This problem is closely related to Hilbert's irreducibility theorem.

Serre has proven an effective version of this in his book "Lectures on the Mordell-Weil theorem". See in particular sections 9 and 13.

This implies that $100\%$ of polynomials of degree $d$ are irreducible over $\mathbb{Q}$, for fixed $d > 1$.

In particular $0\%$ of such polynomials have a rational root, hence $0\%$ have an integer root.

Serre's result gives stronger quantitative information, for example this quantity decays like $c_{max}^{\varepsilon - 1/2}$ as $c_{max} \to \infty$.

Answer 3

Not sure this is good enough for an answer, but for $d=1$:

The polynomial $ax+ b = 0 $ has an integral root if an only if $a\mid b$. Let us ignore the case $b=0$ for now, and restrict to $a,b > 0$.

The number of couples $(a,b)$ with $1 \le a,b \le C$ such that $a\mid b$ can be expressed as $\sum_{1 \le n\le C} \tau(n)$ where $\tau(n)$ is the number of divisors of $n$.

It is known that $\sum_{1 \le n\le C} \tau(n) = C \log C + (2 \gamma - 1 ) C + O (\sqrt{C}) $ where $\gamma$ is the Euler–Mascheroni constant.

Thus among all $C^2$ polynomials with $1\le a,b \le C$ there are $C \log C + (2 \gamma - 1 ) C + O (\sqrt{C}) $ with an integral root, so the fraction is asymptotically $\frac{\log C}{C}$.

And among all $2C(2C+1)$ polynomials wit degree $1$ with $-C \le a,b \le C$ there are $4(C \log C + (2 \gamma - 1 ) C + O (\sqrt{C})) + 2C+1$ with an integral root; the first term for the four combinations of signs and non-zero coefficients and then the $2C+1$ with constant term $0$ (or perhaps one should only count $2C$ not to count the zero-polynomials.)

So the asymptotic fraction is $\frac{\log C}{C} $. This is not close for $C=100$, but taking the lower order terms into account it is not that bad.

Doing the actual calculation for $C=100$ one gets $2128$ non-zero polynomials with an integral root, for a fraction of around $5.29$ percent, quite close to the simulation.

Answer 4

My answer to this question suggests that asymptotically the percentage decays with $N$ (standard sieve methods probably say like square root of $N,$ the truth being more like $1/N$), and asymptotically the number should not depend on the degree.