1 Multidimensional corners
Let \(G\) be a finite abelian group whose size we will denote \(N\). Let \(d \ge 2\) a natural number.
For an index \(i : [d]\), we define
We say a tuple \((a_1, \dots , a_d) : (G^d)^d\) is a forbidden pattern with tip \(v : G^d\) if
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\).
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\).
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.
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.
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)\).
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
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
if we set eg \(m = \left\lfloor d\log N/\alpha \right\rfloor + 1\).