The Multidimensional version of Szemerédi's theorem given by Theorem 10.2 in Tim Gower's paper from 2007 has the following statement.

Let $\delta>0$ and $k\in\mathbb{N}$. Then if $N$ is sufficiently large, every subset $A$ of the $k$-dimensional grid $\{1,2,\ldots,N\}^k$ of size at least $\delta N^k$ contains a set of points of the form $\{a\}\cup\{a+de_i:1\leq i\leq k\}$ where $e_1,e_2,\ldots,e_k$ is the standard basis of $\mathbb{R}^k$ and $d$ is a nonzero integer.

What is the biggest construction of a set $A\subseteq \{1,2,\ldots,N\}^k$ known for which there is no subset of the form $\{a\}\cup\{a+de_i:1\leq i\leq k\}$, much like Behrend's construction provides a large set with no length $3$ arithmetic progressions?


1 Answer 1


Take Rankin's generalization of Behrend's construction[1] of sets free of $k$-term arithmetic progressions and lift it to the corner-free set in the usual way, say via the map $(a_1,\dotsc,a_k)\mapsto \sum ia_i$. As far as I know, this is the best known construction.

[1] Robert A. Rankin. Sets of integers containing not more than a given number of terms in arithmetical progression. Proc. Roy. Soc. Edinburgh Sect. A, 65:332–344, 1962.

  • $\begingroup$ Thanks, I will look into Rankin's generalization. For clarification, isn't the map you specified from a corner-free set to a set without a $k$-term progression? How can I lift a set without a $k$-term AP to a corner-free set? $\endgroup$ Jun 10, 2016 at 13:30
  • 1
    $\begingroup$ You pull back the $k$-AP-free set free by this map. $\endgroup$
    – Boris Bukh
    Jun 10, 2016 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.