Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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