Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c \ln(n)/(n^{c-1}).$$

Hint: As a consequence of the prime number theorem, exactly $n/ \ln(n) \pm o(n/\ln(n))$ many numbers from $\{ 1, \ldots, n \}$ are prime.

Conclusion: we can compress $n$ bits to $O(\log(n))$ bits and get a quite small false-positive rate.

My question is how can i proove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c \ln(n)/(n^{c-1})$$?

  • $\begingroup$ Since the difficulty appears to be in the mathematical part, I feel this question would be more at home on Mathematics. However, given the application to compression, I think the question may be acceptable here too. I'm open to migrating the question because it's a better fit elsewhere, or leaving the question here because it's been asked here and it isn't strongly off-topic. $\endgroup$ – Gilles 'SO- stop being evil' May 6 '12 at 23:21
  • 2
    $\begingroup$ This is cross-posted on Mathematics. $\endgroup$ – Kaveh May 7 '12 at 8:15

The probability $P$ that a uniformly chosen random prime between $1$ and $n^c$ satisfies $a \equiv b \mod{p}$ is the number of primes in this range that satisfy $a \equiv b \mod{p}$ divided by the total number of primes in this range. Writing $[C] = 1$ if $C$ is true and $[C] = 0$ if $C$ is false, and $\pi(x)$ for the number of primes less than $x$: $$P = \dfrac{\sum\limits_{p\le n^c} [p\text{ prime}] [p \mid (a-b)]}{\pi(n^c)}$$

Since $|a-b| \le 2^n$, there are at most $n$ distinct primes that divide $a-b$. The prime number theorem directly gives an upper bound for the denominator. Thus: $$ P \le \dfrac{n}{n^c/\ln(n^c) + o(n^c/\ln(n^c))} = \dfrac{c \ln(n)}{n^{c-1}} (1+o(1))$$

You won't get an exact bound from an asymptotic version of the prime number theorem. An exact bound, if I am not mistaken, is $\pi(x) \gt \dfrac{x}{\ln(x)}$ for $x \ge 11$. Using this bound, we see that if $n^c \ge 11$ then $$ P \le \dfrac{c \ln(n)}{n^{c-1}} $$

Application: we can compress $a \le 2^n$ (which takes $n$ bits to represent exactly) approximately by storing $a \mod p$ for several random prime numbers $p_i$. If we use $k$ primes chosen independently of the value of $a$, then the representation requires $k \, \lceil c\,\log_2(n) \rceil = O(k \log(n))$ bits to store the values modulo every chosen prime. The probability of a collision on each prime is at most $c \ln(n) / n^{c-1} = O(\ln(n)/n^{c-1})$. To evaluate how the precision increases with $k$ would require further analysis.

| cite | improve this answer | |

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.