For a large enough $n$, and a parameter $ m $ I'm looking for a subset of the prime numbers in the range $[n,2n]$ with a unique structure. I am looking for a prime $p$ and a set of $m$ positive (not necessary different) integers: $\Delta_1,\Delta_2,\ldots,\Delta_m$ such that the following set consists only of prime numbers in the range $[n,2n]$: $$\{{ p+\sum_{i=1}^{m} a_i \cdot \Delta_i} \mid a_i \in \{0,1\} \}$$ For example, for $n=10$ and $m=2$ there is such a set with parameters: $$p=11,\quad \Delta_1 = 2,\quad \Delta_2 = 6$$ And the set is: $$\{11,13,17,19\} $$ The question is how large can $m$ be asymptotically? Note that an arithmetic progression of $m+1$ primes is a cube with all $m$ deltas having the same value. I've managed to prove that $m$ could be $\frac{\log\log(n)}{2}$ though I'm sure my bound is far from tight.

$\begingroup$ The existence of such $p$ and $\Delta_i$ for each $m$ certainly follows from the GreenTao theorem. I don't know anything about the asymptotics of that though. $\endgroup$– Robin ChapmanSep 4, 2010 at 17:19

$\begingroup$ For a specific choice of Delta's you have here 2^m integers from [n.2n] so you can "estimate" the probability that they are all promes by (1/logn)^{2^m}. If m is fixed maybe this gives the correct asymptotic value of the expected number of such cubes of primes by the recent GreenTaoZiegler theory. This gives you also a guess for the correct value of m but I suppose that transforming this guess to lower and upper bounds is beyond present technology. How do you get the log log n/2 result? $\endgroup$– Gil KalaiSep 4, 2010 at 18:05

$\begingroup$ Gil: I do not know Avishay's argument but log log n is the size Szemeredi obtains for a cube in a set of positive density in [1,..,n]. $\endgroup$– Péter KomjáthSep 4, 2010 at 18:55

$\begingroup$ As the problem is currently stated, the $2^m$ choices do not necessarily give distinct integers, and so for example an arithmetic progression of length $k$ corresponds to the situation where $m=k1$ and the $\Delta$ values are equal. (I do assume that each $\Delta_i$ is required to be strictly positive, since otherwise $m$ is trivially unbounded.) If $2^m$ distinct primes are what is asked for, then an arithmetic sequence of length $k$ only gives $m=\lfloor \log_2 k \rfloor$. $\endgroup$– Tracy HallSep 4, 2010 at 19:52

$\begingroup$ @Tracy: one may consider an arithmetic progression of primes of length say $k = 2^{m+1}$ with common difference $D$. Then set $\Delta_i = 2^{i1}D$. Clearly then any choice of $a_i$ gives a prime. $\endgroup$– dvitekSep 5, 2010 at 6:04
3 Answers
The argument that gives you cubes in dense sets shows roughly speaking (via repeated applications of CauchySchwarz) that the number of kdimensional cubes in a set of density delta is at least something around $\delta^{2^k}n^{k+1}$, which is the number you would get in a random set. (I am in fact giving the result for the integers mod n, but one can think of a subset of the first n integers of density δ as a subset of $\mathbb{Z}_{2n}$ of density δ/2. So this says that the best dimension should be that k for which $\delta^{2^k}$ is around $n^{(k+1)}.$ Taking logs twice, that says (ignoring constants) that $k+\log\log(1/\delta)=\log k+\log\log n,$ or roughly $k=\log\log n  \log\log(1/\delta).$ If $\delta=1/\log n,$ then that second term is not making much difference.
The worst case is for random sets. Although the primes are not random, one can make them more random, and denser, by applying the socalled Wtrick (roughly speaking, you restrict to an arithmetic progression that contains no multiples of small primes, thereby increasing the chances that a number in that progression is prime). But this does not increase the density by enough to have a significant effect on the estimate you might get for k. If you're interested in $2^k$, then the question becomes more delicate and the Wtrick might get you a useful, if smallish, improvement. But basically it looks to me as though your $\log\log n$ estimate for the dimension should be right, up to a constant.
According to ingham's theorem $p_{n+1}p_n< p_n+Ap_n^{5/8}$ in which $A$ is constant number.
Now let $p_n$ be largest prime less than or equal than $N$ so
$p_n\le N< p_{n+1}< p_n+Ap_n^{5/8}\le N+AN^{5/8}$,
let $p_{n+1}= q_1$,then:
$N< q_1< N+AN^{5/8}$,with above method we have below inequalities:
$N+AN^{5/8}< q_2< (N+AN^{5/8})+A(N+AN^{5/8})^{5/8}< N+A(2^{2}1)N^{5/8}$ in which
$q_2=p_{n+s_1}$
$N+3AN^{5/8}< q_3< (N+3AN^{5/8})+A(N+3AN^{5/8})^{5/8}< N+A(2^{3}1)N^{5/8}$
in which $q_3=p_{n+s_2}$
if we continue so:
$N+A(2^{k1}1)N^{5/8}< q_k< N+A(2^{k1}1)N^{5/8})+A(N+A(2^{k1}1)N^{5/8})^{5/8}< N+A(2^{k}1)N^{5/8}$
in which $q_k=p_{n+s_{k1}}$
then after k step we reach to $2N$ so $N+A(2^{k}1)N^{5/8}\le 2N< N+A(2^{k+1}1)N^{5/8}$
we have $m\ge k>(log(N^{3/8}/{A}+1)/log21$,for a large $N$

$\begingroup$ Uhh, what? You may have p_{n+1} < p_n + a fractional power of p_n by Ingham's result, but it is not clear why you want the inequality on A and k, especially with the RHS to be 2N. Even less clear is the derivation. Can you try something different that is more clear? Gerhard "Ask Me About System Design" Paseman, 2010.09.09 $\endgroup$ Sep 9, 2010 at 17:43

$\begingroup$ I correct myself regarding the 2N part. However, the issue of lack of clarity remains. Unless you specify A, you will need more to assume that all prime gaps occurring between p_n and 2p_n are uniformly small with respect to p_n^(5/8). Gerhard "Ask Me About System Design" Paseman, 2010.09.09 $\endgroup$ Sep 9, 2010 at 17:50

$\begingroup$ Thank you for your attempt at clarity. Two points: You can simplify the analysis some by replacing A(f(p_n,A))^5/8 by A(2*p_n)^5/8, and then absorb 2^(5/8) into the constant A. Second, there is no suggestion of how the numbers q_k are related to the 2^k primes asked for by the original poster. They may be k of the 2^k primes, but your argument does not show that they are. There may be 2^k primes near the k primes you have selected, but it is not guaranteed that they are spaced in the desired way. Gerhard "Ask Me About System Design" Paseman, 2010.09.09 $\endgroup$ Sep 9, 2010 at 19:29

$\begingroup$ in above answer first we reach to $N< P_{n+1}< N+AN^[5/8}$,so we have at least one prime between this intervals,second,we use this method to reach to other intervals,by induction,notice that $q_2$ may is not equal to $p_{n+2} i.e $q_2=p_{n+s_1} in which $s_1\ge 2$ $\endgroup$– M.SSep 9, 2010 at 21:46

$\begingroup$ I don't understand your answer, in particular, I don't understand what is the cube that you're building? You didn't mentioned the deltas at all. $\endgroup$ Sep 15, 2010 at 12:24
Elsholtz and Woods have shown that $m\leq (\frac{9}{2}+o(1))\frac{\log n}{\log\log n}$.