# Probability of coprime polynomials

Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let $f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ as polynomials in the indeterminate $x$ over the field ${\mathbb F}_2$ of two elements. Let $P(N)$ be the probability that $f_1$ and $f_2$ are coprime. What can be said about $P(N)$, in particular its asymptotics as $N \to \infty$?

By explicit enumeration in Maple, the first few values are \eqalign{P \left( 1 \right) &={\frac {9}{16}},P \left( 2 \right) ={\frac {56}{ 81}},P \left( 3 \right) ={\frac {45}{64}},P \left( 4 \right) ={\frac { 489}{625}},P \left( 5 \right) ={\frac {1019}{1296}},\cr P \left( 6 \right) &={\frac {1895}{2401}},P \left( 7 \right) ={\frac {3299}{4096} },P \left( 8 \right) ={\frac {5308}{6561}},P \left( 9 \right) ={\frac {2023}{2500}},P(10) = \frac{11954}{14641}\cr} Random sampling seems to indicate $P(100) \approx 0.83$. The sequence $(N+1)^4 P(N)$ does not appear to be in the OEIS.

EDIT: That sequence is now in the OEIS as A245488. $P(100) = 86648767/101^4 \approx 0.8326776196$.

(Edited in response to Julian Rosen's comments)

As $N\to\infty$, one could guess that $P(N)$ approaches $$\prod_{p} \Bigl(1 - \Bigl(\frac{\gcd(a_p,b_p)}{a_p b_p}\Bigr)^2\Bigr),$$ where the product is over all irreducibles $p(x)\in\mathbf{F}_2[x]$ of degree at least $2$, and $a_p$ and $b_p$ denote the orders of $x$ and $x+1$ in the multiplicative group of $\mathbf{F}_2[x]/(f(x))$, respectively. This is because this group is cyclic, so the intersection of subgroups of orders $a_p$ and $b_p$ has order $\gcd(a_p,b_p)$. Then the number of pairs $(m,n)$ with $1\le m\le a_p$ and $1\le n\le b_p$ for which $p\mid x^m+(1+x)^n$ is $\gcd(a_p,b_p)$, so if $N$ is large compared to $a_p$ and $b_p$ then the proportion of the pairs $(m,n)$ with $0\le m,n\le N$ for which $p\mid x^m+(1+x)^n$ will approach $\gcd(a_p,b_p)/(a_pb_p)$. Hence the probability that $p$ divides both $x^{m_1}+(1+x)^{n_1}$ and $x^{m_2}+(1+x)^{n_2}$ approaches the square of $\gcd(a_p,b_p)/(a_pb_p)$, which yields the claimed formula.

However, as Julian Rosen points out, I'm implicitly assuming the independence of divisibility by distinct primes $p$, which isn't valid. So my formula should be modified somehow. On the other hand, I computed the displayed product over $p$'s of degree up to $15$, and got $0.8321...$, matching Robert Israel's computations. So maybe my formula is a reasonable approximation to the truth.

• For $p(x)\in\mathbb{F}_2[x]$ a prime, the condition $p|x^m+(1+x)^n$ is equivalent to some congruence condition on $m$ and $n$ modulo a divisor of $N(p)-1$. These moduli are not coprime for different $p$, so I don't think the conditions are independent. – Julian Rosen Oct 24 '13 at 23:57
• That makes sense, but I can't find a small example where the conditions are dependent. Perhaps this is because the congruence conditions aren't "random", but instead have the form $m\equiv k m_0$, $n\equiv k n_0$ for a single fixed choice of $m_0$ and $n_0$? – Michael Zieve Oct 25 '13 at 0:37
• Write $p_1=x^4+x+1$, $p_2=x^4+x^3+1$, $p_3=x^2+x+1$. If $p_1p_2|x^m+(x+1)^n$, then $m\equiv n\equiv 0\mod{15}$, so necessarily $p_3|x^m+(1+x)^n$. – Julian Rosen Oct 25 '13 at 0:50
• Nice! Any ideas how to modify the probability computation then? – Michael Zieve Oct 25 '13 at 1:02
• I can't think of a way to modify the computation to account for the correlation. I think we can show that the product is a lower bound on the true probability, though. – Julian Rosen Oct 25 '13 at 1:31

This seems to be a hard and interesting problem. Here's a heuristic on the correct answer, but I have little hope that it can be made into a proof. Below let $D$ denote a polynomial in ${\Bbb F}_2[x]$ and let $\mu(D)$ denote the Mobius function. We will only be interested in $D$ that are coprime to $x(1+x)$. For such $D$ consider the group generated by $x$ and $1+x$ in $({\Bbb F}_2[x]/D)^*$; denote this by $\langle x,1+x\rangle_D$ and its order by $|\langle x,1+x\rangle_D|$. The conjectured probability is $$\sum_{D, (D,x(1+x))=1} \frac{\mu(D)}{|\langle x, 1+x \rangle_D|^2}.$$

To see why this is, note that we can identify whether $(f,g)=1$ by summing $\sum_{D|f, D|g} \mu(D)$. Thus the problem asks for $$\sum_{D, (D,x(1+x))=1} \mu(D) \Big( \frac{1}{(N+1)^2} \sum_{0 \le a, b\le N; D|x^a+(1+x)^b} 1\Big)^2.$$

The probability that $D$ divides $x^a+(1+x)^b$ is the same as the probability that $D$ divides $x^m (1+x)^n +1 = x^m (1+x)^n -1$. Since $x^m (1+x)^n$ ranges uniformly over the elements of $\langle x,1+x \rangle_D$, this probability is clearly $1/|\langle x,1+x\rangle_D|$. This justifies heuristically the conjecture. The argument could be made precise by splitting $a$ and $b$ into intervals of size the order of $x$ in $({\Bbb F}_2[x]/D)^*$ and the order of $1+x$ there. The trouble is that there will be an error of size $O(1/N)$ in doing so, and this cannot be controlled as the sum over $D$ includes exponentially many terms.

It seems plausible that the sum over $D$ in the conjecture converges, but I don't see any way to prove this. It would be interesting to compute it numerically. One can get something rigorous by doing the above analysis with only those $D$ whose irreducible factors have degree below $\log N$ say. In this way one obtains an upper bound for the desired probability.

The probability that two random polynomials of large degree in F_2[t] are coprime is $\zeta(2)^{-1}$, or 1/2. Your polynomials are not quite random; neither one is divisible by x or x+1. The probability that two polynomials, both prime to x(x+1), are coprime, is obtained by removing the two corresponding local factors of the Euler product for $\zeta(2)$; in other words, without that restriction, there would be a common factor of x 1/4 of the time, and a common factor of (1+x) 1/4 of the time. So the probability that two polynomials, both coprime to x(x+1), are coprime to each other is (4/3)(4/3)(1/2) = 8/9. This is not quite what you get. What happens when you try it with the variables ranging from 1 to N instead of 0 to N?

Update: Mike Zieve's answer is better than mine, so am I supposed to downvote mine, or what?

• Interesting. Could you also include derivation for $\zeta(2)^{-1}$ or a reference? – Michael Oct 24 '13 at 16:26
• There's something going on with the other primes. For example, $x^m$ and $(1+x)^n$ both run through all non-zero residue classes mod $(1+x+x^2)$, so the probability that $1+x+x^2$ divides $x^m + (1+x)^n$ is $\frac{1}{3}$, rather than $\frac{1}{4}$. It seems like the corrected Euler factor at $(1+x+x^2)$ should be $1-\left(\frac{1}{3}\right)^2$. – Julian Rosen Oct 24 '13 at 19:22
• The system won't let you downvote your own answer. Silly, isn't it! – David E Speyer Oct 24 '13 at 23:25
• "$\zeta(2)^{-1}$, or $1/2$"? – Greg Martin Oct 25 '13 at 7:34