Fix $c\in(0,1)$, and let $N$ be a (large) positive integer. Given a set $A=\{0=a_1<\dots<a_n=N\}$ of density $\alpha:=n/N>c$ with $\gcd(A)=1$, I want to find a prime dividing as few differences $a_j-a_i\ (1\le i<j\le n)$ as possible -- but at least one of them. What can be done in this direction (without assuming anything about the multiplicative structure of $N$)? Just as an example, can one guarantee that there exists a prime dividing at least one and at most $O(\sqrt N)$ of the differences $a_j-a_i$ Ideally, I'd like to have a prime dividing just $O(1)$ of the differences, but, I suspect, this is out of reach.

closeto $c$ with, say, $c<1/3$. Second, for my purposes $\sqrt N$ is pretty much indistinguishable from`$N^{5/8}$`

, or even, say,`$N^{0.9}$`

; can you prove that there exists $p$ dividing at least one and at most`$O(N^{5/8})$`

differences? – Seva Jun 5 '11 at 15:02