Boolean Cube of Primes - MathOverflow

Boolean Cube of Primes

2010-09-04T17:11:00Z

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.

Answer by M.S for Boolean Cube of Primes

2010-09-09T17:02:35Z

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^{k-1}-1)N^{5/8}< q_k< N+A(2^{k-1}-1)N^{5/8})+A(N+A(2^{k-1}-1)N^{5/8})^{5/8}< N+A(2^{k}-1)N^{5/8}$

in which $q_k=p_{n+s_{k-1}}$

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)/log2-1$,for a large $N$

Answer by gowers for Boolean Cube of Primes

2010-09-09T21:49:37Z

The argument that gives you cubes in dense sets shows roughly speaking (via repeated applications of Cauchy-Schwarz) that the number of k-dimensional 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 so-called W-trick (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 W-trick 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.

Answer by jcsp for Boolean Cube of Primes

2011-06-02T20:48:40Z

Elsholtz and Woods have shown that $m\leq (\frac{9}{2}+o(1))\frac{\log n}{\log\log n}$.