3
$\begingroup$

Choose integers $q \ge 1$, $1 \le z_1,z_2 \le q$, and let $x_1,x_2$ be randomly chosen positive integers with the restriction that $x_1 \equiv z_1 \pmod q$ and $x_2 \equiv z_2 \pmod q$. What is the probability that $x_1$ and $x_2$ are coprime?

My initial intuition, analogous to the usual case in which $q=1$, was to note that first, if $\gcd(z_1,z_2,q)>1$ then the probability is $0$; second, for some prime $p$ divides $q$ but does not divide $\gcd(z_1,z_2)$ then the probability that $p$ divides $\gcd(z_1,z_2,q)$ is trivially $0$; and third that if $p$ does not divide $q$ then the probability that it divides $x_1$ and $x_2$ is the same as for any randomly chosen integers. Putting these together and using the usual assumption that divisibility by distinct primes is independent we get that so long as $\gcd(z_1,z_2,q)=1$ the probability is $$\prod_{p \nmid q} \left( 1-\frac 1 {p^2} \right) = \frac 6 {\pi^2} \prod_{p|q} \left( 1-\frac 1 {p^2} \right).$$ This corresponds to the heuristic given here. I then attempted to make this rigorous, since the above assumption is not strictly justified. Let $$f(N)=\frac {q^2} {N^2} \sum_{\substack{x_1,x_2 \le N \\ x_i \equiv z_i \pmod q \\ \gcd(x_1,x_2)=1}} 1 = \frac {q^2} {N^2} \sum_{\substack{x_1,x_2 \le N \\ x_i \equiv z_i \pmod q}} \sum_{d|\gcd(x_1,x_2)} \mu(d) = \frac {q^2} {N^2} \sum_{d=1}^N \mu(d) \sum_{\substack{j_1,j_2 \le N/d \\ j_i d \equiv z_i \pmod q}} 1 $$ where $\mu(n)$ is the Mobius function. Now consider the number of positive integers $x$ at most $N$ congruent to $z$ modulo $q$ divisible by $d$. If $d|\gcd(q,z)$, then this is $\frac Nq+O(1)$, if $d|q$ and $d \nmid z$, then it is $0$, and if $d \nmid q$ then it is $\frac N {qd}+O(1)$. Therefore we have $$f(N)= \frac {q^2} {N^2} \sum_{d=1}^N \mu(d) \left( [d|\gcd(q,z_1)] \left(\frac Nq+O(1)\right) + [d \nmid q] \left( \frac N {qd} + O(1) \right) \right) \left( [d| \gcd(q,z_2)]\left(\frac Nq+O(1)\right) + [d \nmid q] \left( \frac N {qd} + O(1) \right) \right)$$ where $[\cdot]$ are Iverson brackets, equal to $1$ if the condition within is satisfied and equal to $0$ otherwise (sorry about the too-long line). Multiplying this out and noting that it is impossible to have $d|q$ and $d \nmid q$ simultaneously, we have $$f(N)=\frac {q^2} {N^2} \sum_{d=1}^N \mu(d) \left( [d|\gcd(z_1,z_2,q)] \left( \frac {N^2} {q^2} +O \left( \frac N d \right) \right) + [d\nmid q] \left( \frac {N^2} {q^2 d^2} + O \left(\frac N {qd} \right) \right) \right)$$ and since $\gcd(z_1,z_2,q)=1$ this becomes $$1+\sum_{d \nmid q} \frac {\mu(d)} {d^2} + O\left( \frac qN \log N \right) = 1 + \frac 6 {\pi^2} - \sum_{d|q} \frac {\mu(d)} {d^2} +O \left( \frac q N \log N \right) = 1+\frac 6 {\pi^2} - \prod_{p | q} \left( 1-\frac 1 {p^2} \right) + O \left( \frac q N \log N \right)$$ since we can absorb the remainder of the convergent series, which is $O\left( \frac 1N \right)$, into the error term. This is fairly close to the expected result but definitely different.

My initial reaction to this finding was oh, I guess that heuristic was a little wrong then. However, upon testing for actual numbers (although admittedly only up to $N \sim 100000$ because my computer is slow and I'm too lazy to write fast algorithms) the initial heuristic actually gives a significantly better approximation, particularly for "more composite" numbers, for which the difference is larger. For example, for $q=72$, $n=100000$, we have $f(N)\approx 0.91195632$, an estimate from the initial heuristic of approximately $0.91189065$ (about $.007 \%$ error), and an estimate from the derived formula of approximately $0.94126044$ (about $3 \%$ error). While neither is large, since the estimates are close to each other and where they differ more the first is generally more correct I'm curious. (The first is also aesthetically more pleasing at least to me, but that's mostly beside the point.) In particular, all of the constants that go into the error bound should be relatively small, of order $1$, which for these values mean that the error should be at most on the order of $.008$, which the error of the derived formula is not. Nonetheless I can't find a flaw in the proof.

Is there a flaw in the derivation? If so is the heuristic correct? Or is the derived formula correct and the error is acceptable and I'm losing track of some error term, and the fact that the heuristic is closer a coincidence? (Or are both wrong and it's something else?)

Thanks!

$\endgroup$
3
$\begingroup$

"Now consider the number of positive integers $x$ at most $N$ congruent to $z$ modulo $q$ divisible by $d$ ... if $d \nmid q$ then it is $\frac N {qd}+O(1)$." This statement is incorrect, since $d\nmid q$ does not imply that $\gcd(d,q)=1$. For example, if $q=10$ and $d=6$, then the number of such integers is $\frac N{30}+O(1)$, not $\frac N{60}+O(1)$.

In general, you should replace $\frac N{qd}$ with $\frac N{\mathop{\rm lcm}[q,d]}$ (and then you don't have to consider $d\mid q$ separately). That should lead you to a rigorous derivation of your heuristic, which I believe gives the correct answer.

$\endgroup$
  • $\begingroup$ Thanks! I'm still working on getting the formula from here but I think that was the problem. $\endgroup$ – Laertes Jun 11 '17 at 16:18

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.