3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Commented Jun 10, 2016 at 13:30
  • 1
    $\begingroup$ You pull back the $k$-AP-free set free by this map. $\endgroup$
    – Boris Bukh
    Commented Jun 10, 2016 at 13:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .