# Upper bound on smallest prime $p$ needed to tell two numbers $\leq n$ apart modulo $p$

I'm going through this paper:

E. D. Demaine, S. Eisenstat, J. Shallit, and D. A. Wilson. Remarks on separating words. ArXiv e-prints, March 2011.

And on page 2, there is the following lemma:

Lemma 1. If $0 \leq i,j \leq n$ and $i \ne j$, then there is a prime $p \leq 4.4 \log{n}$ such that $i \not\equiv j$ (mod $p$).

They don't show where the $4.4 \log{n}$ comes from and I'm not sure where to look for it. Best I could find is this, but it does not provide the solution.

Could someone point me in the correct direction?

-
It appears that the lemma is actually proved in another paper: [10] J. Shallit and Y. Breitbart. Automaticity I: Properties of a measure of descriptional complexity. J. Comput. System Sci., 53:10–25, 1996. – Old John Jul 29 '12 at 6:01

High Level Idea

Suppose that $j > i$. Let $k = 4.4 \log n$. Then we need to prove that there is a prime number $p < k$ that doesn't divide $j -i$. Assume to the contrary that this is not the case. Then all primes between $2$ and $k$ divide $j -i$. Since all of them are coprime, the product of all primes between $2$ and $k$ divides $j-i$. In particular, we get $$\prod_{\substack{2\leq p \leq k\\p\text{ is prime}}}p \leq j -i \leq n.$$ The product in the LHS is sometimes called “primorial” (see http://en.wikipedia.org/wiki/Primorial ). It is known that it roughly equals $e^k$ and therefore is greater than $n$. We get a contradiction.

An Estimate for the Primorial

Let me informally explain why the primorial of $k$ is approximately $e^k$. The factorial of $k$ is approximately $e^{k\ln k}$. In the factorial we multiply all numbers between 1 and $k$, but in the primorial only primes. The density of primes is $1/\ln k$. Therefore, the primorial is approximately $\left(e^{k\ln k}\right)^{1/\ln k} = e^k$.

Numerical Bounds

Note that this proof implies that for large enough $n$ there is a prime number as desired between $1$ and $(1+ o(1))\ln n$. However, for small $n$ the term $o(1)$ may be relatively large. I computed the value of the primorial numerically in PARI/GP for $k\in{2,\dots, 100000}$ and got that the primorial of $k$ is always at least $\exp(\frac{\ln 2}{2} k)$ (the equality is attained for $k=2$). If this is indeed true for all $k$, as my computation suggests, then there is a desired prime between $1$ and $2\, \log_2 n$.

-
This explains the $\log n$, but not the 4.4, right? – Gerry Myerson Jul 29 '12 at 6:35
Beautiful explanation. The only part that I'm still a bit shaky about is where the 4.4 comes from. From what I see we just need $e^k$ to be bigger than $n$, and in this case that would be $e^{4.4\log{n}} = n^{4.4}$. – Ehsan Kia Jul 29 '12 at 6:36
My proof shows that for large enough $n$ there is a prime number satisfying the requiring properties between 1 and $\ln n (1+ o(1))$. If we want to have a very explicit quantitative result we need to be specific what this $o(1)$ term is. That is, we need to understand how large it can be for small $n$. Maybe it can be as large as $4.4 \log n$, maybe $4.4 \log n$ is just what the authors proved (and in fact a better bound holds). BTW, does $\log n$ mean $\log_2 n$ or $\ln n$ in this paper? – Yury Jul 29 '12 at 6:50
Ah, I see, so the 4.4 comes from the $O(1)$ in the Primorial bound, and that's just from another tighter proof. Thanks. Also I'm not sure, it's not really specified. – Ehsan Kia Jul 29 '12 at 6:56