3
$\begingroup$

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?

  • 0
    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.2012-07-29

1 Answers 1

5

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

  • 0
    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.2012-07-29