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+loglog(1/delta)=log k+loglog n,$ or roughly $k=loglog n - loglog(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 $loglog n$ estimate for the dimension should be right, up to a constant.
No comments:
Post a Comment