Chandra-Furst-Lipton

1 Multidimensional corners

Let \(G\) be a finite abelian group whose size we will denote \(N\). Let \(d \ge 2\) a natural number.

Definition 1.1 Forgetting a coordinate
#

For an index \(i : [d]\), we define

\begin{align} \operatorname{forget}_i : G^d & \to G^{\{ j : [d] \mid j \ne i\} } \\ x & \mapsto j \mapsto x_j \end{align}
Definition 1.2 Forbidden pattern

We say a tuple \((a_1, \dots , a_d) : (G^d)^d\) is a forbidden pattern with tip \(v : G^d\) if

\[ a_{i, j} = v_j \]

for all \(i, j\) distinct. We also simply say \((a_1, \dots , a_d)\) is a forbidden pattern if it is a forbidden pattern with tip \(v\) for some \(v\).

Definition 1.3 Multidimensional corner
#

A multidimensional corner in \(d\) dimensions is a tuple of the form \((x, x + ce_1, \dots , x + ce_d)\) for some \(x : G^d\) and \(c : G\), where \(ce_i\) is the vector of all zeroes except in position \(i\) where it is \(c\). Such a corner is said to be trivial if \(c = 0\).

Definition 1.4 Corner-free number

The \(d\)-dimensional corner-free number of \(G\), denoted \(r_d(G)\) is the size of the largest set \(A\) in \(G^d\) such that \(A\) doesn’t contain a non-trivial corner.

Definition 1.5 Corner-coloring number

The \(d\)-dimensional corner-coloring number of \(G\), denoted \(\chi _d(G)\), is the smallest number of colors one needs to color \(G^d\) such that no non-trivial \(d\)-dimensional corner is monochromatic.

Lemma 1.6 Lower bound on the corner-coloring number
\[ r_d(G) \chi _d(G) \ge N^d \]
Proof

Find a coloring of \(G^d\) in \(\chi _d(G)\) colors without non-trivial monochromatic \(d\)-dimensional corners. The coloring partitions \(G^d\) into \(\chi _d(G)\) sets of size at most \(r_d(G)\).

Lemma 1.7 Upper bound on the corner-coloring number
\[ r_d(G) \chi _d(G) \le 2d N^d \log N \]
Proof

Find \(A\) a corner-free set of density \(\alpha = r_d(G)/N^d\). If we pick \(m {\gt} d\log N/\alpha \) translates of \(A\) randomly, then the expected number of elements not covered by any translate is

\[ N^d(1 - \alpha )^m \le \exp (dN - m\alpha ) {\lt} 1 \]

Namely, there is some collection of \(m\) translates of \(A\) that covers all of \(G^d\). Since being corner-free is translation-invariant, this cover by translates gives a coloring in \(m\) colors without non-trivial monochromatic corners. So

\[ \chi _d(G) \le m \le 2d \log N/\alpha = 2d N^d \log N/r_d(G) \]

if we set eg \(m = \left\lfloor d\log N/\alpha \right\rfloor + 1\).