Boolean Cube of Primes - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T03:14:41Z http://mathoverflow.net/feeds/question/37739 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37739/boolean-cube-of-primes Boolean Cube of Primes Avishay Tal 2010-09-04T17:11:00Z 2011-06-02T20:48:40Z <p>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.</p> http://mathoverflow.net/questions/37739/boolean-cube-of-primes/38199#38199 Answer by M.S for Boolean Cube of Primes M.S 2010-09-09T17:02:35Z 2010-09-09T21:51:50Z <p>According to ingham's theorem $p_{n+1}-p_n&lt; p_n+Ap_n^{5/8}$ in which $A$ is constant number.</p> <p>Now let $p_n$ be largest prime less than or equal than $N$ so</p> <p>$p_n\le N&lt; p_{n+1}&lt; p_n+Ap_n^{5/8}\le N+AN^{5/8}$,</p> <p>let $p_{n+1}= q_1$,then:</p> <p>$N&lt; q_1&lt; N+AN^{5/8}$,with above method we have below inequalities:</p> <p>$N+AN^{5/8}&lt; q_2&lt; (N+AN^{5/8})+A(N+AN^{5/8})^{5/8}&lt; N+A(2^{2}-1)N^{5/8}$ in which</p> <p>$q_2=p_{n+s_1}$</p> <p>$N+3AN^{5/8}&lt; q_3&lt; (N+3AN^{5/8})+A(N+3AN^{5/8})^{5/8}&lt; N+A(2^{3}-1)N^{5/8}$ </p> <p>in which $q_3=p_{n+s_2}$</p> <p>if we continue so:</p> <p>$N+A(2^{k-1}-1)N^{5/8}&lt; q_k&lt; N+A(2^{k-1}-1)N^{5/8})+A(N+A(2^{k-1}-1)N^{5/8})^{5/8}&lt; N+A(2^{k}-1)N^{5/8}$ </p> <p>in which $q_k=p_{n+s_{k-1}}$</p> <p>then after k step we reach to $2N$ so $N+A(2^{k}-1)N^{5/8}\le 2N&lt; N+A(2^{k+1}-1)N^{5/8}$</p> <p>we have $m\ge k>(log(N^{3/8}/{A}+1)/log2-1$,for a large $N$</p> http://mathoverflow.net/questions/37739/boolean-cube-of-primes/38233#38233 Answer by gowers for Boolean Cube of Primes gowers 2010-09-09T21:49:37Z 2010-09-09T21:49:37Z <p>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 &delta; as a subset of $\mathbb{Z}_{2n}$ of density &delta;/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. </p> <p>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.</p> http://mathoverflow.net/questions/37739/boolean-cube-of-primes/66768#66768 Answer by jcsp for Boolean Cube of Primes jcsp 2011-06-02T20:48:40Z 2011-06-02T20:48:40Z <p>Elsholtz and Woods have shown that $m\leq (\frac{9}{2}+o(1))\frac{\log n}{\log\log n}$.</p>