2

1

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.

flag
if you take $A$ to be the full set ${1,\dots,N}$, your best bet is to take the largest prime $p<N$. Now, that'll give you $N-p$ difefrences, so you wish to know if the gaps between primes are bounded by $\sqrt N$. The record seems to still be at $N^{5/8}$, so good luck! – fedja Jun 5 2011 at 13:09
@fedja: your comment is somewhat "orthogonal" to what I have in mind. First, if the density of $A$ is close to $1$ then I am happy, anyway, for a different reason; so, what I am really interested in is the case where the density is close to $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 2011 at 15:02
OK, I'll think of this. I just responded to what was written, not to what you had in mind :). – fedja Jun 5 2011 at 15:08
Have you tried applying traditional sum-product estimates to the set of differences? Either the set has additive structure, so that the set of differences of differences is small, so there must a prime not dividing many differences by pigeonholing, or the set of differences has a large product set. It feels like a large product set implies (in some loose sense) that there can't be too many primes which divide too many elements of your original set. – Thomas Bloom Jun 5 2011 at 18:35
(continued) I don't have the time now to check the details, but perhaps some quantitative version of this argument combined with the latest sum-product technology could give good results for this question? – Thomas Bloom Jun 5 2011 at 18:35

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.