15
$\begingroup$

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


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

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

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

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Joseph O'Rourke Apr 30 '15 at 10:59
7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Presumably $\: \log C/C \:$ should be replaced with $\: (\log C)/C \;$. $\;\;\;\;$ $\endgroup$ – user5810 Apr 27 '15 at 8:07
  • $\begingroup$ I changed the notation in a different way to make clear that indeed this is the intent. Thanks for pointing out the confusing notation. $\endgroup$ – user9072 Apr 27 '15 at 8:57
  • $\begingroup$ 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? $\endgroup$ – Joseph O'Rourke Apr 27 '15 at 12:00
  • 1
    $\begingroup$ @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. $\endgroup$ – user9072 Apr 27 '15 at 12:18
  • 1
    $\begingroup$ Thanks, quid. Your calculations are remarkably accurate. Nice analysis. $\endgroup$ – Joseph O'Rourke Apr 27 '15 at 12:21
1
$\begingroup$

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.

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