14
$\begingroup$

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

$\endgroup$

3 Answers 3

11
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 24, 2013 at 23:57
  • $\begingroup$ 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$? $\endgroup$ Oct 25, 2013 at 0:37
  • 1
    $\begingroup$ 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$. $\endgroup$ Oct 25, 2013 at 0:50
  • $\begingroup$ Nice! Any ideas how to modify the probability computation then? $\endgroup$ Oct 25, 2013 at 1:02
  • $\begingroup$ 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. $\endgroup$ Oct 25, 2013 at 1:31
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Interesting. Could you also include derivation for $\zeta(2)^{-1}$ or a reference? $\endgroup$
    – Michael
    Oct 24, 2013 at 16:26
  • 2
    $\begingroup$ 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$. $\endgroup$ Oct 24, 2013 at 19:22
  • $\begingroup$ The system won't let you downvote your own answer. Silly, isn't it! $\endgroup$ Oct 24, 2013 at 23:25
  • 4
    $\begingroup$ "$\zeta(2)^{-1}$, or $1/2$"? $\endgroup$ Oct 25, 2013 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.