# Random Diophantine polynomials: Percent solvable?

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

• How do you generate the data? – Igor Rivin Apr 26 '15 at 23:46
• @IgorRivin: Generate $d+1$ random coefficients within $\pm c_\max$: independent, uniform. Then solve the polynomials, see if any integer solutions. – Joseph O'Rourke Apr 26 '15 at 23:48
• Right, I have no problem with generating the coefficients, it's figuring out whether they have solutions that troubles me. – Igor Rivin Apr 26 '15 at 23:50
• @Igor: Doesn't the rational root theorem give all possible integer solutions pretty quickly? en.wikipedia.org/wiki/Rational_root_theorem – Pace Nielsen Apr 27 '15 at 0:00
• @PaceNielsen Ah, very true. – Igor Rivin Apr 27 '15 at 0:02

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

• Brilliant! "The proportion of polynomials having a large integer root is very small." Here are integer roots for $d{=}5$, $10^4$ trials: 1, 2, 0, -2, -1, 0, -1, 0, 1, -1, 0, 0, -1, 1, -1, -2, -1, 1, -1, 1, 0, 1, -1, 0, 1, 0, 1, -1, 1, -1, 0, 0, 0, 0, 1, -1, 0, -1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, -1, 0, 0, 1, 0, 1, 0, 0, 0, 0, -1, 1, -1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, -1, 1, 0, 0, 0, -1, 2, 0, -2, 0, -1, -1, -1, 0, 1, 1, 0, 1, -1, 0, 1, -1, 0, -1, 0, -1, 0, 1, -1, -1, -1, 0, 1, 1, 0, 1, 0, 0, 0, -1 – Joseph O'Rourke Apr 30 '15 at 10:59

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

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.

• Presumably $\: \log C/C \:$ should be replaced with $\: (\log C)/C \;$. $\;\;\;\;$ – user5810 Apr 27 '15 at 8:07
• I changed the notation in a different way to make clear that indeed this is the intent. Thanks for pointing out the confusing notation. – user9072 Apr 27 '15 at 8:57
• Another data point for $C=50$: $9.1$%. Your formulas predict about $9.2$%. May I ask: What are you estimating for the $O(\sqrt{C})$ term? – Joseph O'Rourke Apr 27 '15 at 12:00
• @JosephO'Rourke the problem of estimating this is known as Dirichlet divisor problem and there are better estimates than what I gave. See mathworld.wolfram.com/DirichletDivisorProblem.html for an overview. I think the extual error term should be only slightly larger than a fourth root of $C$, what is known is order $C^a$ with $a=131/416$. I do not know right now what is known regarding the implied constants. For the weak error term I give $6$ would work IIRC. – user9072 Apr 27 '15 at 12:18
• Thanks, quid. Your calculations are remarkably accurate. Nice analysis. – Joseph O'Rourke Apr 27 '15 at 12:21

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.