Approximately Symmetric Forms Far From Being Exactly Symmetric
Luka Milićević†

00footnotetext: † Mathematical Institute of the Serbian Academy of Sciences
and Arts
† Email<EMAIL_ADDRESS>
  * Abstract

a Let $V$ be a finite-dimensional vector space over $\mathbb{F}_{p}$. We say
that a multilinear form $\alpha\colon V^{k}\to\mathbb{F}_{p}$ in $k$ variables
is $d$-_approximately symmetric_ if the partition rank of difference
$\alpha(x_{1},\dots,x_{k})-\alpha(x_{\pi(1)},\dots,x_{\pi(k)})$ is at most $d$
for every permutation $\pi\in\operatorname{Sym}_{k}$. In a work concerning the
inverse theorem for the Gowers uniformity $\|\cdot\|_{\mathsf{U}^{4}}$ norm in
the case of low characteristic, Tidor conjectured that any $d$-approximately
symmetric multilinear form $\alpha\colon V^{k}\to\mathbb{F}_{p}$ differs from
a symmetric multilinear form by a multilinear form of partition rank at most
$O_{p,k,d}(1)$ and proved this conjecture in the case of trilinear forms. In
this paper, somewhat surprisingly, we show that this conjecture is false. In
fact, we show that approximately symmetric forms can be quite far from the
symmetric ones, by constructing a multilinear form
$\alpha\colon\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$
which is 3-approximately symmetric, while the difference between $\alpha$ and
any symmetric multilinear form is of partition rank at least
$\Omega(\sqrt[3]{n})$.

## §1 Introduction

For a function $f\colon G\to\mathbb{C}$ on a finite abelian group $G$, Gowers
uniformity norms $\|\cdot\|_{\mathsf{U}^{k}}$, introduced by Gowers in [6] are
given by the formula

$\|f\|_{\mathsf{U}^{k}}^{2^{k}}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a_{1},\dots,a_{k},x\in
G}{\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}}\,_{a_{1}}\dots\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}\,_{a_{k}}f(x),$

where ${\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}}\,_{a}$ stands for the discrete multiplicative derivative
operator defined by ${\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}}\,_{a}f(x)=f(x+a)\overline{f(x)}$. Gowers introduced these norms
in order to obtain a quantitative proof of Szemerédi’s theorem on arithmetic
progressions, and they serve as a measure of the higher order quasirandomness
of functions defined on finite abelian groups. A basic illustration of this
phenomenon is given by the following fact: whenever
$A\subset\mathbb{Z}/N\mathbb{Z}$ is a set of size $\delta N$ such that
$\|\mathbbm{1}_{A}-\delta\|_{\mathsf{U}^{k}}=o(1)$, then $A$ has
$(1+o(1))\delta^{k+1}N^{2}$ arithmetic progressions of length $k+1$. This
motivates the study of functions which have large uniformity norms. The
results which describe such functions $f\colon
G\to\mathbb{D}=\\{z\in\mathbb{C}\colon|z|\leq 1\\}$ are referred to as the
_inverse theorems for uniformity norms_ and typically have the following form:
given the group $G$ and order $k$, there is some algebraically structured
family of functions $\mathcal{Q}$, depending on $G$ and $k$, such that
whenever $f\colon G\to\mathbb{D}$ is a function with the norm bound
$\|f\|_{\mathsf{U}^{k}}\geq c$, then one may find an obstruction function
$q\in\mathcal{Q}$ such that $\Big{|}\mathop{\mathbb{E}}_{x\in
G}f(x)\overline{q(x)}\Big{|}\geq\Omega_{c,k}(1)$. One also requires that
$\mathcal{Q}$ is roughly minimal in the sense that an approximate version of a
converse holds; namely whenever $\Big{|}\mathop{\mathbb{E}}_{x\in
G}f(x)\overline{q(x)}\Big{|}\geq c$ holds for a function $f\colon
G\to\mathbb{D}$ and obstruction $q\in\mathcal{Q}$, then we also have the norm
bound $\|f\|_{\mathsf{U}^{k}}\geq\Omega_{c,k}(1)$.

The family of obstruction functions can be taken to be nilsequences (which we
will not define here) when $G=\mathbb{Z}/N\mathbb{Z}$, as shown by Green, Tao
and Ziegler [5], and phases of non-classical polynomials (which we shall
define later) when $G=\mathbb{F}_{p}^{n}$, which follows from results of
Bergelson, Tao and Ziegler [1] and Tao and Zielger [20]. Another approach to
these questions is via the theory of nilspaces developed in papers by Szegedy
[19], Camarena and Szegedy [2], and Candela, González-Sánchez and Szegedy [3].
(See also detailed treatments of this theory in [9], [10], [11].)

The inverse theorems mentioned above are either ineffective or give poor
bounds and, given the applications, it is of interest to make the proofs
quantitative. For general $k$, this was achieved by Manners [14] for the case
when $G=\mathbb{Z}/N\mathbb{Z}$ and by Gowers and the author in [8] for the
case when $G=\mathbb{F}_{p}^{n}$, provided $p\geq k$, which is known as the
_high-characteristic case_ , when the family of obstruction functions reduces
to polynomials in the usual sense. Previously, quantitative bounds were
obtained in the inverse question for $\|\cdot\|_{\mathsf{U}^{3}}$ norm by
Green and Tao [4] for abelian groups of odd order and by Samorodnitsky when
$G=\mathbb{F}_{2}^{n}$ in [18] (see also a very recent work of Jamneshan and
Tao [12]).

On the other hand, in the so-called _low characteristic case_ , where $p<k$,
the bounds are still ineffective. However, even in that case [8] gives a
strong partial result.

######  Theorem 1.1 (Gowers and Milićević [8]).

Suppose that $f\colon\mathbb{F}^{n}_{p}\to\mathbb{D}$ is a function such that
$\|f\|_{\mathsf{U}^{k}}\geq c$. Then there exists a multilinear form
$\alpha\colon\underbrace{\mathbb{F}^{n}_{p}\times\mathbb{F}^{n}_{p}\times\dots\times\mathbb{F}^{n}_{p}}_{k-1}\to\mathbb{F}_{p}$
such that

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a_{1},\dots,a_{k-1}}{\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}}\,_{a_{1}}\dots\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}\,_{a_{k-1}}f(x)\omega^{\alpha(a_{1},\dots,a_{k-1})}\Big{|}\geq\Big{(}\exp^{(O_{k}(1))}(O_{k,p}(c^{-1}))\Big{)}^{-1}.$
(1)

From now on, we focus on $G=\mathbb{F}_{p}^{n}$ in the rest of the
introduction. Before proceeding with the discussion, we need to recall the
notion of the partition rank of a multilinear form introduced by Naslund in
[17]. It is defined to be the least number $m$ such that a multilinear form
$\alpha\colon G^{d}\to\mathbb{F}_{p}$ can be expressed as

$\alpha(x_{1},\dots,x_{d})=\sum_{i\in[m]}\beta_{i}(x_{j}\colon j\in
I_{i})\gamma_{i}(x_{j}\colon j\in[d]\setminus I_{i}),$

where $\beta_{i}\colon G^{I_{i}}\to\mathbb{F}_{p}$ and $\gamma_{i}\colon
G^{[d]\setminus I_{i}}\to\mathbb{F}_{p}$ are multilinear maps for $i\in[m]$.
We may think of partition rank as a measure of distance between two
multilinear forms; the smaller the partition rank of their difference is, the
closer they are. As an illustration of this principle in the context of
Theorem 1.1, we have the following lemma.

######  Lemma 1.2.

Suppose that a function $f\colon G\to\mathbb{D}$ and a multilinear form
$\alpha\colon G^{k-1}\to\mathbb{F}_{p}$ satisfy

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a_{1},\dots,a_{k-1}}{\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}}\,_{a_{1}}\dots\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}\,_{a_{k-1}}f(x)\omega^{\alpha(a_{1},\dots,a_{k-1})}\Big{|}\geq
c.$

Let $\beta\colon G^{k-1}\to\mathbb{F}_{p}$ be another multilinear form such
that $\operatorname{prank}(\alpha-\beta)\leq r$. Then

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,a_{1},\dots,a_{k-1}}{\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}}\,_{a_{1}}\dots\Delta\\!\\!\\!\\!\\!\hbox{\raisebox{1.29167pt}{\tiny\
\textbullet}}\,_{a_{k-1}}f(x)\omega^{\beta(a_{1},\dots,a_{k-1})}\Big{|}\geq
cp^{-2r}.$

Returning to the discussion of the inverse theorems for uniformity norms in
finite vector spaces, the deduction of the inverse theorem when $p\geq k$
proceeds by studying the multilinear form $\alpha$ provided by the Theorem
1.1. The symmetry argument of Green and Tao [4] and the good bounds for the
analytic versus partition rank problem [13], [15] show that $\alpha$ is _$r$
-approximately symmetric_ for some $r=\exp^{(O_{k}(1))}(O_{k,p}(c^{-1}))$, by
which we mean that the partition rank of the multilinear form
$(x_{1},\dots,x_{k-1})\mapsto\alpha(x_{1},\dots,x_{k-1})-\alpha(x_{\pi(1)},\dots,x_{\pi(k-1)})$
is at most $r$ for all $\pi\in\operatorname{Sym}_{k-1}$. To finish the proof
of the inverse theorem, at the very last step we invoke the assumption $p\geq
k$, which allows us to define the symmetric multilinear map $\sigma\colon
G^{k-1}\to\mathbb{F}_{p}$ by

$\sigma(a_{1},\dots,a_{k-1})=\frac{1}{(k-1)!}\sum_{\pi\in\operatorname{Sym}_{k-1}}\alpha(a_{\pi(1)},\dots,a_{\pi(k-1)}),$

which satisfies $\operatorname{prank}(\sigma-\alpha)\leq(k-1)!r$ since
$\alpha$ is $r$-approximately symmetric. Lemma 1.2 allows us to replace
$\alpha$ by $\sigma$. As it turns out, when $p\geq k$ the polarization
identity shows that all symmetric forms are iterated discrete additive
derivatives111Similarly to discrete multiplicative derivative, for $a\in G$ we
define discrete additive derivative operator $\Delta_{a}$ by expression
$\Delta_{a}f(x)=f(x+a)-f(x)$ for a function $f\colon G\to H$ from $G$ to
another abelian group $H$. of polynomials, showing that the function $x\mapsto
f(x)\omega^{\alpha(x,\dots,x)}$ has large $\|\cdot\|_{\mathsf{U}^{k-1}}$ norm,
which completes the proof.

Low characteristic obstacles. Let us now define non-classical polynomials
which are the relevant obstructions in the low characteristic case. A function
$f\colon\mathbb{F}_{p}^{n}\to\mathbb{T}=\mathbb{R}/\mathbb{Z}$ is a non-
classical polynomial of degree at most $d$ if
$\Delta_{a_{1}}\dots\Delta_{a_{d+1}}f(x)=0$ for all
$a_{1},\dots,a_{d+1},x\in\mathbb{F}_{p}^{n}$. (See [20] for further details,
including alternative description of non-classical polynomials.)
The first obvious question is, given that the family of obstruction functions
is richer when $p<k$ due to emergence of non-classical polynomials, how could
we get from multilinear forms in (1) to a non-classical polynomial? It turns
out that, as in the case of classical polynomials, the iterated discrete
additive derivative of a non-classical polynomial (applied the right number of
times) is a symmetric multilinear form and it is possible to give
characterizations of the forms that arise in this way. The following lemma of
Tidor [21], building upon earlier work of Tao and Ziegler, achieves this goal.

######  Lemma 1.3 (Tidor [21]).

Let $\alpha\colon G^{k-1}\to\mathbb{F}_{p}$ be a multilinear form. Then
$\alpha$ is the discrete additive derivative of order $k-1$ of a non-classical
polynomial of degree $k-1$ if and only if $\alpha$ is symmetric and

$\alpha(\underbrace{x,\dots,x}_{p},y,a_{p+2},\dots,a_{k-1})=\alpha(x,\underbrace{y,\dots,y}_{p},a_{p+2},\dots,a_{k-1}).$
(2)

We say that a multilinear form is _strongly symmetric_ if it is symmetric and
obeys the additional condition (2), as in the lemma above. Therefore, we may
again pass from a multilinear form $\alpha$ to the desired obstruction,
provided we can show some additional properties of $\alpha$.

In fact, in his work on the inverse question for $\|\cdot\|_{\mathsf{U}^{4}}$
norm in the case of low characteristic [21], Tidor first showed that one may
assume that $\alpha$ is symmetric and then use that information to prove
strong symmetry. Given all this, Tidor formulated the following conjecture,
which he proved for the case of trilinear maps.

######  Conjecture 1.4 (Tidor [21]).

Let $\alpha\colon G^{k}\to\mathbb{F}_{p}$ be an $r$-approximately symmetric
multilinear form. Then there exists a symmetric multilinear form $\sigma\colon
G^{k}\to\mathbb{F}_{p}$ such that $\operatorname{prank}(\sigma-\alpha)\leq
O(r^{O(1)})$ (where the implicit constants may depend on $p$ and $k$).

The main result of this paper is that, despite its formulation being rather
natural, the conjecture above is false.

######  Theorem 1.5.

Given a sufficiently large positive integer $n$ there exists a multilinear
form
$\alpha\colon\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$
which is 3-approximately symmetric and
$\operatorname{prank}(\sigma-\alpha)\geq\Omega(\sqrt[3]{n})$ for all symmetric
multilinear forms $\sigma$.

Regarding the approach to a quantitative inverse theorem for uniformity norms
in the case of low characteristic, this means that one needs to work more
closely with the assumption (1). In fact, it is possible to overcome the
additional difficulties identified in this paper, and to prove a quantitative
inverse theorem for uniformity norms in the case of low characteristic, which
we do in a forthcoming paper.

######  Theorem 1.6 (Milićević [16]).

Suppose that $f\colon\mathbb{F}^{n}_{2}\to\mathbb{D}$ be a function such that
$\|f\|_{\mathsf{U}^{k}}\geq c$. Then there exists a non-classical polynomial
$q\colon\mathbb{F}_{2}^{n}\to\mathbb{T}$ of degree at most $k-1$ such that

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x}f(x)\exp\Big{(}2\pi
iq(x)\Big{)}\Big{|}\geq\Big{(}\exp^{(O_{k}(1))}(O_{k,p}(c^{-1}))\Big{)}^{-1}.$

Counterexample overview. The multilinear form
$\alpha\colon\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$
that will serve us as a counterexample will have the crucial properties that
it is symmetric in the first three variable, while satisfying the identity

$\alpha(x,y,z,w)+\alpha(w,y,z,x)=\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)$

for some bilinear map $\rho$ of high rank222In the case of bilinear forms, the
partition rank becomes just the usual notion of rank from linear algebra.. It
is easy to see that such a form $\alpha$ is necessarily 3-approximately
symmetric. On the other hand, to prove that $\alpha$ is far from symmetric
multilinear forms we use bilinear regularity method, used in [7], which
consists of passing to subspaces where the rank of bilinear maps is large and
then relying on the high-rank property to obtain equidistribution of values of
the relevant bilinear maps. Using the usual graph-theoretic regularity method
(i.e. Szemerédi regularity lemma and related tools) would give much worse
bounds in Theorem 1.5.

Acknowledgements. This work was supported by the Serbian Ministry of
Education, Science and Technological Development through Mathematical
Institute of the Serbian Academy of Sciences and Arts.

## §2 Preliminaries

For the rest of the paper, fix a positive integer $n$ and set
$G=\mathbb{F}_{2}^{n}$. In this preliminary section we setup the notation for
an action of the symmetry group $\operatorname{Sym}_{4}$ on $G^{4}$, we recall
the notion and properties of the rank of bilinear maps and we discuss the
bilinear regularity method needed for the proof of Theorem 1.5.

Action of $\operatorname{Sym}_{4}$. We define a natural action of
$\operatorname{Sym}_{4}$ on $G^{4}$ given by permuting the coordinates, which
is similar to the left regular representation of the group
$\operatorname{Sym}_{4}$. For a permutation $\pi\in\operatorname{Sym}_{4}$ we
misuse the notation and write $\pi\colon G^{4}\to G^{4}$ for the map defined
by $\pi(x_{1},x_{2},x_{3},x_{4})=(x_{\pi^{-1}(1)},$ $x_{\pi^{-1}(2)},$
$x_{\pi^{-1}(3)},$ $x_{\pi^{-1}(4)})$. This defines an action on $G^{4}$;
indeed, given two permutations $\pi,\sigma\in\operatorname{Sym}_{4}$ and
$x_{1},\dots,x_{4}\in G$ we have

$\displaystyle\sigma(\pi(x_{1},x_{2},x_{3},x_{4}))=$
$\displaystyle\sigma(x_{\pi^{-1}(1)},x_{\pi^{-1}(2)},x_{\pi^{-1}(3)},x_{\pi^{-1}(4)})$
$\displaystyle=$
$\displaystyle(x_{\pi^{-1}(\sigma^{-1}(1))},x_{\pi^{-1}(\sigma^{-1}(2))},x_{\pi^{-1}(\sigma^{-1}(3))},x_{\pi^{-1}(\sigma^{-1}(4))})$
$\displaystyle=$
$\displaystyle(x_{(\sigma\pi)^{-1}(1)},x_{(\sigma\pi)^{-1}(2)},x_{(\sigma\pi)^{-1}(3)},x_{(\sigma\pi)^{-1}(4)})$
$\displaystyle=$ $\displaystyle(\sigma\pi)(x_{1},\dots,x_{4}).$

Hence, given a multilinear form $\alpha\colon G^{4}\to\mathbb{F}_{2}$ and a
permutation $\pi$ inducing the map $\pi\colon G^{4}\to G^{4}$, we may compose
the two maps and the composition $\alpha\circ\pi$ would also be a multilinear
form. For example if $\pi=(1\,\,2\,\,3)$ in the cycle notation, then
$\alpha\circ\pi(x_{1},x_{2},x_{3},x_{4})=\alpha(x_{3},x_{1},x_{2},x_{4})$.
With this notation, our main result can be expressed as follows: there exists
a multilinear form $\alpha\colon G^{4}\to\mathbb{F}_{2}$ such that
$\alpha+\alpha\circ\pi$ is of low partition rank for all
$\pi\in\operatorname{Sym}_{4}$ and $\alpha$ differs from any symmetric
multilinear form by a multilinear form of large partition rank.

Rank of bilinear maps. Let $U,V$ be finite-dimensional vector spaces over
$\mathbb{F}_{2}$. Let $\beta\colon U\times V\to\mathbb{F}_{2}$ be a bilinear
form. Fix a scalar product on $V$ and let $B\colon U\to V$ be the map such
that $\beta(x,y)=B(x)\cdot y$ for all $x\in U$ and $y\in V$. We define the
rank of $\beta$ to be the rank of $B$. The following lemma gives a few other
characterizations of the rank and shows that the rank is well-defined (this
follows from part (i)).

######  Lemma 2.1 (Alternative characterizations of rank).

Let $\beta\colon U\times V\to\mathbb{F}_{2}$ be a bilinear form.

  * (i)

We have $\mathop{\mathbb{E}}_{x\in U,y\in
V}(-1)^{\beta(x,y)}=2^{-\operatorname{rank}\beta}$.

  * (ii)

Whenever $\beta(x,y)=\sum_{i\in[s]}u_{i}(x)v_{i}(y)$ for linear forms
$u_{1},\dots,u_{s}\colon U\to\mathbb{F}_{2}$ and $v_{1},\dots,v_{s}\colon
V\to\mathbb{F}_{2}$ such that $u_{1},\dots,u_{s}$ are linearly independent and
$v_{1},\dots,v_{s}$ are linearly independent, then
$s=\operatorname{rank}\beta$.

  * (iii)

The rank is the least number $s$ such that
$\beta(x,y)=\sum_{i\in[s]}u_{i}(x)v_{i}(y)$ for linear forms
$u_{1},\dots,u_{s}\colon U\to\mathbb{F}_{2}$ and $v_{1},\dots,v_{s}\colon
V\to\mathbb{F}_{2}$.

###### Proof.

Proof of (i). If $\beta(x,y)=B(x)\cdot y$ for all $x\in U,y\in V$, then

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in U,y\in
V}(-1)^{\beta(x,y)}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in U,y\in V}(-1)^{B(x)\cdot
y}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
U}\mathbbm{1}(B(x)=0)=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in U}\mathbbm{1}(x\in\ker B)=|\ker B|/|U|.$

By the rank-nullity theorem $|\ker B|/|U|=1/|\operatorname{Im}B|$. The rank of
$\beta$ is defined as the dimension of the image space $\operatorname{Im}B$,
hence

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in U,y\in
V}(-1)^{\beta(x,y)}=2^{-\operatorname{rank}\beta},$

as desired.

Proof of (ii). We claim that the linear map $u\colon U\to\mathbb{F}_{2}^{s}$
is surjective. If it was not surjective, the subspace
$\operatorname{Im}u\leq\mathbb{F}_{2}^{s}$ would be proper and there would
exist a non-zero vector $\lambda\in(\operatorname{Im}u)^{\perp}$. But then
$\lambda_{1}u_{1}+\dots+\lambda_{s}u_{s}$ would be identically zero, which
would be in contradiction with the assumption that $u_{1},\dots,u_{s}$ are
independent. In particular, the linear map $u\colon U\to\mathbb{F}_{2}^{s}$
takes all values in $\mathbb{F}_{2}^{s}$ an equal number of times (namely
$|\ker u|=p^{-s}|U|$ times). Using the same property for $v_{1},\dots,v_{s}$
and claim (i) of the lemma we conclude that

$2^{-\operatorname{rank}\beta}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in U,y\in
V}(-1)^{\beta(x,y)}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in U,y\in
V}(-1)^{\sum_{i\in[s]}u_{i}(x)v_{i}(y)}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a,b\in\mathbb{F}_{2}^{s}}(-1)^{a\cdot
b}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{a\in\mathbb{F}^{s}_{2}}\mathbbm{1}(a=0)=2^{-s},$

proving that $s=\operatorname{rank}\beta$.

Proof of (iii). Let $d=\dim U$. Clearly, such a decomposition exists, as we
may simply take a basis $e_{1},\dots,e_{d}$ of $U$, giving coordinates
$x_{1},\dots,x_{d}$ of vectors $x\in U$, and consider

$\beta(x,y)=\sum_{i\in[d]}x_{i}\beta(e_{i},y).$

On the other hand, if we have a decomposition with smallest possible $s$ then
$u_{1},\dots,u_{s}$ need to be linearly independent. To see that, note that if
have linear dependence, then (after a possible reordering of the forms) we
have $u_{1}=\sum_{j\in[2,s]}\mu_{j}u_{j}$, so

$\beta(x,y)=\sum_{j\in[2,s]}u_{j}(x)(v_{j}(y)+\mu_{j}v_{1}(y)),$

which has $s-1$ terms in the sum, which is a contradiction. Hence
$u_{1},\dots,u_{s}$ are linearly independent, and analogously, so are
$v_{1},\dots,v_{s}$. The claim follows from the part (ii).∎

Let us also record two very simple but useful facts about bilinear forms of
low rank.

######  Lemma 2.2.

Let $\beta\colon U\times V\to\mathbb{F}_{2}$ be a bilinear form of rank $r$.
Then there exists a subspace $U^{\prime}\leq U$ of codimension at most $r$ in
$U$ such that $\beta|_{U^{\prime}\times V}=0$.

###### Proof.

By the definition of rank, $r$ is the rank of the linear map $B\colon U\to V$
that satisfies $\beta(x,y)=B(x)\cdot y$ for all $x\in U,y\in V$ for a given
scalar product on $V$. By the rank-nullity theorem, the kernel
$U^{\prime}=\operatorname{ker}B\leq U$ has codimension $r$. Hence, when $x\in
U^{\prime},y\in V$ we have $\beta(x,y)=B(x)\cdot y=0$, as desired.∎

######  Lemma 2.3.

Let $\beta\colon U\times V\to\mathbb{F}_{2}$ be a bilinear form of rank $r$.
Let $U^{\prime}\leq U$ be a subspace of codimension $d$ inside $U$. Then
$\beta|_{U^{\prime}\times V}$ has rank at least $r-d$.

###### Proof.

Let $s$ be the rank of $\beta|_{U^{\prime}\times V}$. By part (iii) of Lemma
2.1 we have linear forms $u_{1},\dots,u_{s}\colon U^{\prime}\to\mathbb{F}_{2}$
and $v_{1},\dots,v_{s}\colon V\to\mathbb{F}_{2}$ such that
$\beta(x,y)=\sum_{i\in[s]}u_{i}(x)v_{i}(y)$ holds for all $x\in U^{\prime}$
and $y\in V$. We may extend each $u_{i}$ to a linear form $\tilde{u}_{i}\colon
U\to\mathbb{F}_{2}$. Let
$\beta^{\prime}(x,y)=\beta(x,y)+\sum_{i\in[s]}\tilde{u}_{i}(x)v_{i}(y)$. The
map $\beta^{\prime}$ is a bilinear form on $U\times V$ which vanishes on
$U^{\prime}\times V$. We claim that $\beta^{\prime}$ has rank at most $d$.
Since we also have that
$\beta(x,y)=\beta^{\prime}(x,y)+\sum_{i\in[s]}\tilde{u}_{i}(x)v_{i}(y)$, it
follows that $\beta$ can be written as a sum of at most $s+d$ terms of the
form $u^{\prime}(x)v^{\prime}(y)$ for suitable linear forms $u^{\prime}\colon
U\to\mathbb{F}_{2}$ and $v^{\prime}\colon V\to\mathbb{F}_{2}$ and so by part
(iii) of Lemma 2.1 we have $r\leq s+d$ as desired. We now return to showing
that $\operatorname{rank}\beta^{\prime}\leq d$.
Since $U^{\prime}$ has codimension $d$ inside $U$, we may find linearly
independent elements $e_{1},\dots,e_{d}\in U$ such that $U=\langle
e_{1},\dots,e_{d}\rangle\oplus U^{\prime}$. We thus obtain linear forms
$\varphi_{1},\dots,\varphi_{d}\colon U\to\mathbb{F}_{2}$ and a linear map
$\pi\colon U\to U^{\prime}$ such that for each $x\in U$ we have
$x=\sum_{i\in[d]}\varphi_{i}(x)e_{i}+\pi(x)$. Using this decomposition, for
arbitrary $x\in U,y\in V$ we see that

$\beta^{\prime}(x,y)=\beta^{\prime}\Big{(}\sum_{i\in[d]}\varphi_{i}(x)e_{i}+\pi(x),y\Big{)}=\sum_{i\in[d]}\varphi_{i}(x)\beta^{\prime}(e_{i},y)+\beta^{\prime}(\pi(x),y)=\sum_{i\in[d]}\varphi_{i}(x)\beta^{\prime}(e_{i},y).$

Part (iii) of Lemma 2.1 implies that $\operatorname{rank}\beta^{\prime}\leq
d$.∎

Bilinear regularity method. In the proof that our example has the desired
properties we need the algebraic regularity method for bilinear maps. This
method was used in [7]. The following lemma, in the spirit of Corollary 5.2 of
[7], essentially shows that for a given bilinear map we may pass to a subspace
on which it behaves quasirandomly (which in the bilinear setting simply means
that the restriction of the bilinear map has high rank).

######  Lemma 2.4 (Bilinear regularity lemma).

Let $m\geq 1$ be a positive integer. Let $U$ be a finite-dimensional vector
space over $\mathbb{F}_{2}$ and let $\rho,\beta_{1},\dots,\beta_{r}\colon
U\times U\to\mathbb{F}_{2}$ be bilinear forms such that
$\operatorname{rank}\rho\geq(4r+1)m$. Then there exist a subspace
$U^{\prime}\leq U$ of codimension at most $2rm$ and bilinear forms
$\alpha_{1},\dots,\alpha_{s}\colon U^{\prime}\times
U^{\prime}\to\mathbb{F}_{2}$, where $s\leq r$, such that every non-zero linear
combination of $\alpha_{1},\dots,\alpha_{s}$ and $\rho|_{U^{\prime}\times
U^{\prime}}$ has rank at least $m$, while every bilinear map among
$\beta_{1},\dots,\beta_{r}$ equals a linear combination of
$\alpha_{1},\dots,\alpha_{s}$ and $\rho$ on $U^{\prime}\times U^{\prime}$.

###### Proof.

Let us first set $s=r$, $U^{\prime}=U$ and $\alpha_{i}=\beta_{i}$. We shall
modify the number $s$, subspace $U^{\prime}$ and maps
$\alpha_{1},\dots,\alpha_{s}$ throughout the proof. At each step of the proof
the number of forms $s$ will decrease by 1, while the dimension of
$U^{\prime}$ will increase by at most $2m$. Note that every bilinear map among
$\beta_{1},\dots,\beta_{r}$ equals some $\alpha_{i}$ on $U^{\prime}\times
U^{\prime}$ so we just need to make sure that ranks of all non-zero linear
combinations of $\alpha_{i}$ and $\rho$ are sufficiently large. Suppose on the
contrary that there is a linear combination of maps
$\alpha_{1},\dots,\alpha_{s}$ and $\rho|_{U^{\prime}\times U^{\prime}}$ such
that

$\operatorname{rank}\Big{(}\lambda_{1}\alpha_{1}+\dots+\lambda_{s}\alpha_{s}+\mu\rho|_{U^{\prime}\times
U^{\prime}}\Big{)}<m.$

Since by Lemma 2.3 we have $\operatorname{rank}\rho|_{U^{\prime}\times
U^{\prime}}\geq\operatorname{rank}\rho-2(\dim U-\dim U^{\prime})\geq m$, there
exists a non-zero $\lambda_{j}$. Reordering $\alpha_{i}$ if necessary, we may
assume that $\lambda_{s}=1$. Thus, by Lemma 2.1(iii) there exist linear forms
$v_{1},\dots,v_{m},v^{\prime}_{1},\dots,v^{\prime}_{m}\colon
U^{\prime}\to\mathbb{F}_{2}$ such that

$\alpha_{s}(x,y)=\lambda_{1}\alpha_{1}(x,y)+\dots+\lambda_{s-1}\alpha_{s-1}(x,y)+\mu\rho(x,y)+v_{1}(x)v^{\prime}_{1}(y)+\dots+v_{m}(x)v^{\prime}_{m}(y).$

We may replace $U^{\prime}$ by $U^{\prime}\cap\\{x\in U^{\prime}\colon(\forall
i\in[m])v_{i}(x)=v^{\prime}_{i}(x)=0\\}$ and remove the form $\alpha_{s}$ from
the sequence. The property that every bilinear map among
$\beta_{1},\dots,\beta_{r}$ equals a suitable linear combination on
$U^{\prime}\times U^{\prime}$ is preserved and the procedure must terminate
after at most $r$ steps.∎

The next lemma is an algebraic counting lemma, similar to Lemma 5.3 of [7].

######  Lemma 2.5 (Bilinear counting lemma).

Suppose that
$\alpha\colon\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{r}$
is a bilinear map with the property that the form $\lambda\cdot\alpha$ has
rank at least $m$ for all non-zero vectors $\lambda\in\mathbb{F}_{2}^{r}$. Let
$C$ be a coset of a subspace of $\mathbb{F}_{2}^{n}$ of codimension $d$. Let
$\varepsilon>0$. If $m>4r+8d+4\log_{2}\varepsilon^{-1}$ then $\alpha|_{C\times
C}$ takes every value in $\mathbb{F}_{2}^{r}$ at least
$(1-\varepsilon)2^{-r}|C|^{2}$ times. In particular, if $m>4r+8d+4$ then
$\alpha|_{C\times C}$ is surjective.

The reason for calling this lemma an algebraic counting lemma is that it is
closely related to the more traditional counting results. For example, we can
easily deduce that for any $\nu_{1},\nu_{2},\nu_{3}\in\mathbb{F}_{2}^{r}$ the
number of triples $x,y,z\in\mathbb{F}_{2}^{n}$ such that
$\alpha(x,y)=\nu_{1}$, $\alpha(y,z)=\nu_{2}$ and $\alpha(z,x)=\nu_{3}$ is
approximately $2^{-3r}\cdot 2^{3n}$ as long as $\alpha$ is sufficiently
quasirandom. In the graph-theoretic language, this corresponds to counting
triangles. Similarly, Lemma 2.4 is related to Szemerédi regularity lemma.

###### Proof.

Suppose that the restriction $\alpha|_{C\times C}$ takes the value
$u\in\mathbb{F}_{2}^{r}$ at most $(1-\varepsilon)2^{-r}|C|^{2}$ times. Then we
have

$\displaystyle(1-\varepsilon)2^{-r-2d}\geq$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}\mathbbm{1}_{C}(x)\mathbbm{1}_{C}(y)\mathbbm{1}(\alpha(x,y)=u)=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}\mathbbm{1}_{C}(x)\mathbbm{1}_{C}(y)\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\lambda\in\mathbb{F}_{2}^{r}}(-1)^{\lambda\cdot(\alpha(x,y)-u)}$
$\displaystyle=$ $\displaystyle
2^{-r}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}\mathbbm{1}_{C}(x)\mathbbm{1}_{C}(y)+2^{-r}\sum_{\lambda\in\mathbb{F}_{2}^{r}\setminus\\{0\\}}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}\mathbbm{1}_{C}(x)\mathbbm{1}_{C}(y)(-1)^{\lambda\cdot(\alpha(x,y)-u)}$
$\displaystyle=$ $\displaystyle
2^{-r-2d}+2^{-r}\sum_{\lambda\in\mathbb{F}_{2}^{r}\setminus\\{0\\}}(-1)^{-\lambda\cdot
u}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}\mathbbm{1}_{C}(x)\mathbbm{1}_{C}(y)(-1)^{\lambda\cdot\alpha(x,y)}.$

Using the triangle inequality, we see that

$2^{-r}\sum_{\lambda\in\mathbb{F}_{2}^{r}\setminus\\{0\\}}\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}\mathbbm{1}_{C}(x)\mathbbm{1}_{C}(y)(-1)^{\lambda\cdot\alpha(x,y)}\bigg{|}\geq\varepsilon
2^{-r-2d},$

so by averaging we obtain a non-zero $\lambda$ such that

$\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}\mathbbm{1}_{C}(x)\mathbbm{1}_{C}(y)(-1)^{\lambda\cdot\alpha(x,y)}\bigg{|}\geq\varepsilon
2^{-r-2d}.$

By the two-dimensional Gowers-Cauchy-Schwarz inequality, the left hand side
can be bounded above by the box norm of $(-1)^{\lambda\cdot\alpha}$, so

$\varepsilon^{4}2^{-4r-8d}\leq\Big{\|}(-1)^{\lambda\cdot\alpha}\Big{\|}_{\square}^{4}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,y\in\mathbb{F}_{2}^{n}}(-1)^{\lambda\cdot\alpha(x,y)},$

which equals $2^{-\operatorname{rank}(\lambda\cdot\alpha)}$ by Lemma 2.1(i).
Hence $\varepsilon^{4}2^{-4r-8d}\leq 2^{-m}$ so $m\leq
4r+8d+4\log_{2}\varepsilon^{-1}$, which is a contradiction.∎

## §3 Example

Recall that $n$ is a fixed positive integer, which we think of as large, and
that $G=\mathbb{F}_{2}^{n}$. Let $e_{1},\dots,e_{n}$ be the standard basis of
$G$. Our example will be the multilinear form $\phi\colon
G^{4}\to\mathbb{F}_{2}$ defined as

$\phi(x,y,z,w)=\sum_{1\leq i<j\leq
n}\Big{(}x_{i}y_{j}z_{j}w_{i}+x_{j}y_{i}z_{j}w_{i}+x_{j}y_{j}z_{i}w_{i}\Big{)},$

where the coordinates of vectors are taken with the respect to the fixed basis
$e_{1},\dots,e_{n}$. We first show that $\phi$ is approximately symmetric.

######  Lemma 3.1.

The multilinear form $\phi$ satisfies $\phi=\phi\circ(1\,\,2)$,
$\phi=\phi\circ(1\,\,3)$ and

$\phi(x,y,z,w)=\phi\circ(1\,\,4)(x,y,z,w)+\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)$

where

$\rho(x,y)=\sum_{i\in[n]}x_{i}y_{i}.$

###### Proof.

For each $i$ and $j$ the expression
$x_{i}y_{j}z_{j}w_{i}+x_{j}y_{i}z_{j}w_{i}+x_{j}y_{j}z_{i}w_{i}$ is symmetric
in $x,y$ and $z$ and hence the equalities $\phi=\phi\circ(1\,\,2)$ and
$\phi=\phi\circ(1\,\,3)$ follow immediately. For the remaining transposition
$(1\,\,4)$ we perform some algebraic manipulation

$\displaystyle\phi(x,y,z,w)+\phi(w,y,z,x)=$ $\displaystyle\sum_{1\leq i<j\leq
n}\Big{(}(x_{i}y_{j}z_{j}w_{i}+x_{j}y_{i}z_{j}w_{i}+x_{j}y_{j}z_{i}w_{i})+(w_{i}y_{j}z_{j}x_{i}+w_{j}y_{i}z_{j}x_{i}+w_{j}y_{j}z_{i}x_{i})\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{1\leq i<j\leq
n}\Big{(}x_{j}y_{i}z_{j}w_{i}+x_{j}y_{j}z_{i}w_{i}+x_{i}y_{i}z_{j}w_{j}+x_{i}y_{j}z_{i}w_{j}\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{1\leq i<j\leq
n}\Big{(}x_{j}y_{i}z_{j}w_{i}+x_{i}y_{j}z_{i}w_{j}\Big{)}+\sum_{1\leq i<j\leq
n}\Big{(}x_{j}y_{j}z_{i}w_{i}+x_{i}y_{i}z_{j}w_{j}\Big{)}$ $\displaystyle=$
$\displaystyle\Big{(}\sum_{i,j\in[n]\colon
i\not=j}x_{j}y_{i}z_{j}w_{i}\Big{)}+\Big{(}\sum_{i,j\in[n]\colon
i\not=j}x_{j}y_{j}z_{i}w_{i}\Big{)}$ $\displaystyle=$
$\displaystyle\Big{(}\sum_{i,j\in[n]\colon
i\not=j}x_{j}y_{i}z_{j}w_{i}\Big{)}+\Big{(}\sum_{i,j\in[n]\colon
i\not=j}x_{j}y_{j}z_{i}w_{i}\Big{)}+2\cdot\Big{(}\sum_{i\in[n]}x_{i}y_{i}z_{i}w_{i}\Big{)}$
$\displaystyle=$
$\displaystyle\Big{(}\sum_{i,j\in[n]}x_{j}y_{i}z_{j}w_{i}\Big{)}+\Big{(}\sum_{i,j\in[n]}x_{j}y_{j}z_{i}w_{i}\Big{)}$
$\displaystyle=$
$\displaystyle\Big{(}\sum_{j\in[n]}x_{j}z_{j}\Big{)}\Big{(}\sum_{i\in[n]}y_{i}w_{i}\Big{)}+\Big{(}\sum_{j\in[n]}x_{j}y_{j}\Big{)}\Big{(}\sum_{i\in[n]}z_{i}w_{i}\Big{)}$
$\displaystyle=$ $\displaystyle\rho(x,z)\rho(y,w)+\rho(x,y)\rho(z,w),$

as desired.∎

Since the transpositions $(1\,\,2),(1\,\,3)$ and $(1\,\,4)$ generate the whole
symmetric group $\operatorname{Sym}_{4}$ we immediately deduce that $\phi$ is
3-approximately symmetric.

######  Corollary 3.2.

For any permutation $\pi\in\operatorname{Sym}_{4}$ we have
$\operatorname{prank}\Big{(}\phi+\phi\circ\pi\Big{)}\leq 3$.

###### Proof.

Let $V$ be the vector space consisting of the multilinear forms on $G^{4}$ of
the shape
$\lambda_{1}\rho(x,y)\rho(z,w)+\lambda_{2}\rho(x,z)\rho(y,w)+\lambda_{3}\rho(x,w)\rho(y,z)$
for some scalars $\lambda_{1},\lambda_{2},\lambda_{3}\in\mathbb{F}_{2}$. Since
$\rho$ is a symmetric bilinear form it follows that $V$ is invariant under the
action of $\operatorname{Sym}_{4}$. The lemma above shows in particular that
$\phi+\phi\circ\pi\in V$ whenever $\pi$ is one of the transpositions
$(1\,\,2),(1\,\,3)$ and $(1\,\,4)$. Let $\pi\in\operatorname{Sym}_{4}$ now be
an arbitrary permutation. The transpositions $(1\,\,2),(1\,\,3)$ and
$(1\,\,4)$ generate $\operatorname{Sym}_{4}$ so we can write
$\pi=\tau_{1}\circ\tau_{2}\circ\dots\circ\tau_{r}$ for some
$\tau_{1},\dots,\tau_{r}\in\\{(1\,\,2),(1\,\,3),(1\,\,4)\\}$. Then we have

$\displaystyle\phi\circ\pi+\phi=$
$\displaystyle\sum_{i\in[r]}\Big{(}\phi\circ\tau_{i}\circ\tau_{i+1}\circ\dots\circ\tau_{r}+\phi\circ\tau_{i+1}\circ\tau_{i+2}\circ\dots\circ\tau_{r}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{i\in[r]}\Big{(}\phi\circ\tau_{i}+\phi\Big{)}\circ\tau_{i+1}\circ\dots\circ\tau_{r}$

which is a sum of $r$ forms, each of which is a member of $V$. Hence
$\phi+\phi\circ\pi\in V$ for all $\pi\in\operatorname{Sym}_{4}$. Since the
partition rank of forms in $V$ is at most 3, the proof is complete.∎

In the rest of this section, we show that the map $\phi$ is necessarily far
from any symmetric multilinear form.

######  Theorem 3.3.

Let $r\geq 1$ be a positive integer. Assume that $n\geq(1000r)^{3}$. For any
symmetric multilinear form $\sigma\colon G^{4}\to\mathbb{F}_{2}$ we have
$\operatorname{prank}(\phi-\sigma)>r$.

###### Proof.

Let $\sigma\colon G^{4}\to\mathbb{F}_{2}$ be a symmetric multilinear form.
Suppose on the contrary that $\operatorname{prank}(\phi-\sigma)\leq r$. Then
we may find linear forms $u^{1}_{1},\dots,$ $u^{1}_{r},$ $\dots,$
$u^{4}_{1},\dots,u^{4}_{r}$, bilinear forms $\gamma^{1}_{1},\dots,$
$\gamma^{1}_{r},\dots,$ $\gamma^{3}_{1},\dots,\gamma^{3}_{r}$ and
$\tilde{\gamma}^{1}_{1},\dots,$ $\tilde{\gamma}^{1}_{r},\dots,$
$\tilde{\gamma}^{3}_{1},\dots,\tilde{\gamma}^{3}_{r}$, and trilinear forms
$\theta^{1}_{1},\dots,$ $\theta^{1}_{r},\dots,$
$\theta^{4}_{1},\dots,\theta^{4}_{r}$ (we set some of the forms to be 0 to
have a single parameter $r$ instead of a separate count for each sequence of
forms) on the space $G$ such that

$\displaystyle\phi(x,y,z,w)=\sigma(x,y,z,w)+$
$\displaystyle\sum_{i\in[r]}u^{1}_{i}(x)\theta^{1}_{i}(y,z,w)+\sum_{i\in[r]}u^{2}_{i}(y)\theta^{2}_{i}(x,z,w)$
$\displaystyle\hskip
142.26378pt+\sum_{i\in[r]}u^{3}_{i}(z)\theta^{3}_{i}(x,y,w)+\sum_{i\in[r]}u^{4}_{i}(w)\theta^{4}_{i}(x,y,z)$
$\displaystyle+$
$\displaystyle\sum_{i\in[r]}\gamma^{1}_{i}(x,y)\tilde{\gamma}^{1}_{i}(z,w)+\sum_{i\in[r]}\gamma^{2}_{i}(x,z)\tilde{\gamma}^{2}_{i}(y,w)+\sum_{i\in[r]}\gamma^{3}_{i}(x,w)\tilde{\gamma}^{3}_{i}(y,z)$

holds for all $x,y,z,w\in G$. Let us pass to the subspace $U=\\{x\in
G\colon(\forall d\in[4])(\forall i\in[r])u^{d}_{i}(x)=0\\}$ which has
codimension at most $4r$. When $x,y,z,w\in U$ then

$\phi(x,y,z,w)=\sigma(x,y,z,w)+\sum_{i\in[r]}\gamma^{1}_{i}(x,y)\tilde{\gamma}^{1}_{i}(z,w)+\sum_{i\in[r]}\gamma^{2}_{i}(x,z)\tilde{\gamma}^{2}_{i}(y,w)+\sum_{i\in[r]}\gamma^{3}_{i}(x,w)\tilde{\gamma}^{3}_{i}(y,z).$

In the rest of proof we deal with bilinear forms primarily so we simply use
the word rank instead of partition rank as the usual notion of rank is
equivalent to the partition rank, as remarked earlier. We now gather all $6r$
bilinear forms $\gamma^{1}_{1},\dots,\tilde{\gamma}^{3}_{r}$ above into a
single sequence and apply the bilinear regularity lemma. Let $m\geq 1$ be an
integer to be chosen later. Assume that $n\geq 24rm+8r+m$ so that
$\operatorname{rank}\rho|_{U\times U}\geq 24rm+m$ (recall that
$\operatorname{rank}\rho=n$). Lemma 2.4 allows us to find a subspace
$U^{\prime}\leq U$ of codimension at most $12rm$ inside $U$, a positive
integer $s\leq 6r$, bilinear forms $\alpha_{1},\dots,\alpha_{s}\colon
U^{\prime}\times U^{\prime}\to\mathbb{F}_{2}$ such that every map among
$\gamma^{1}_{1},\dots,\tilde{\gamma}^{3}_{r}$ equals a linear combination of
$\alpha_{1},\dots,\alpha_{s}$ and $\rho|_{U^{\prime}\times U^{\prime}}$ on
$U^{\prime}\times U^{\prime}$ and all non-zero linear combinations of
$\alpha_{1},\dots,\alpha_{s}$ and $\rho|_{U^{\prime}\times U^{\prime}}$ have
rank at least $m$.
Expressing maps $\gamma^{1}_{1},\dots,\tilde{\gamma}^{3}_{r}$ in terms of
these bilinear forms, we conclude that whenever $x,y,z,w\in U^{\prime}$

$\displaystyle\phi(x,y,z,w)=\sigma(x,y,z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda^{\prime}_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda^{\prime\prime}_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)$
$\displaystyle+\rho(x,y)\beta_{1}(z,w)+\rho(x,z)\beta_{2}(y,w)+\rho(x,w)\beta_{3}(y,z)+\rho(y,z)\beta_{4}(x,w)+\rho(y,w)\beta_{5}(x,z)+\rho(z,w)\beta_{6}(x,y)$
(3)

where
$\lambda_{ij},\lambda^{\prime}_{ij},\lambda^{\prime\prime}_{ij}\in\mathbb{F}_{2}$
are suitable coefficients and $\beta_{1},\dots,\beta_{6}\colon
U^{\prime}\times U^{\prime}\to\mathbb{F}_{2}$ are suitable bilinear forms.

We now use the approximate symmetry properties of $\phi$ in order to deduce
that the coefficients
$\lambda_{ij},\lambda^{\prime}_{ij},\lambda^{\prime\prime}_{ij}$ are symmetric
in $i$ and $j$ and that forms $\alpha_{i}$ are essentially symmetric. This
will eventually allows us to simplify the expression in (3). The identity
$\phi+\phi\circ(1\,\,2)=0$ will be used to prove the following claim.

######  Claim 3.4.

Assume $m\geq 40(s+1)$.

  * (i)

There exists a subspace $V^{1}\leq U^{\prime}$ such that $\dim V^{1}\geq\dim
U^{\prime}-2s^{2}-5s$ and for each $j\in[s]$ the bilinear form
$\sum_{i\in[s]}\lambda_{ij}\alpha_{i}$ is symmetric on $V^{1}\times V^{1}$.

  * (ii)

For all $i,j\in[s]$, $\lambda^{\prime}_{ij}=\lambda^{\prime\prime}_{ji}$.

###### Proof.

Using the fact that $\phi+\phi\circ(1\,\,2)=0$ and (3) we get

$\displaystyle 0=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}(\alpha_{i}(x,y)+\alpha_{i}(y,x))\alpha_{j}(z,w)+\sum_{i,j\in[s]}(\lambda^{\prime}_{ij}+\lambda^{\prime\prime}_{ji})\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}(\lambda^{\prime\prime}_{ij}+\lambda^{\prime}_{ji})\alpha_{i}(x,w)\alpha_{j}(y,z)$
$\displaystyle\hskip
56.9055pt+\rho(x,z)(\beta_{2}(y,w)+\beta_{4}(y,w))+\rho(x,w)(\beta_{3}(y,z)+\beta_{5}(y,z))+\rho(y,z)(\beta_{4}(x,w)+\beta_{2}(x,w))$
$\displaystyle\hskip
113.81102pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{3}(x,z))+\rho(z,w)(\beta_{6}(x,y)+\beta_{6}(y,x))$
(4)

for all $x,y,z,w\in U^{\prime}$.

Proof of (i). Let $j\in[s]$ be given. Since any non-zero linear combination of
$\rho|_{U^{\prime}\times U^{\prime}},\alpha_{1},\dots,\alpha_{s}$ has rank at
least $m>4(s+2)$ by Lemma 2.5 we can find $z,w\in U^{\prime}$ such that
$\rho(z,w)=0$, $\alpha_{i}(z,w)=0$ for all $i\not=j$ and $\alpha_{j}(z,w)=1$.
Using this choice of $z,w$ in (4) we obtain

$\displaystyle\sum_{i\in[s]}\lambda_{ij}(\alpha_{i}(x,y)+\alpha_{i}(y,x))=\sum_{i\in[s]}\alpha_{i}(x,z)\Big{(}\sum_{\ell\in[s]}(\lambda^{\prime}_{i\ell}+\lambda^{\prime\prime}_{\ell
i})\alpha_{\ell}(y,w)\Big{)}+\sum_{i\in[s]}\alpha_{i}(x,w)\Big{(}\sum_{\ell\in[s]}(\lambda^{\prime\prime}_{i\ell}+\lambda^{\prime}_{\ell
i})\alpha_{\ell}(y,z)\Big{)}$ $\displaystyle\hskip
56.9055pt+\rho(x,z)(\beta_{2}(y,w)+\beta_{4}(y,w))+\rho(x,w)(\beta_{3}(y,z)+\beta_{5}(y,z))+\rho(y,z)(\beta_{4}(x,w)+\beta_{2}(x,w))$
$\displaystyle\hskip
113.81102pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{3}(x,z))+\rho(z,w)(\beta_{6}(x,y)+\beta_{6}(y,x))$

for all $x,y\in U^{\prime}$. By Lemma 2.1(iii) we conclude that
$\sum_{i\in[s]}\lambda_{ij}(\alpha_{i}(x,y)+\alpha_{i}(y,x))$ has rank at most
$2s+5$, so by Lemma 2.2 we may find a subspace $U^{\prime}_{j}\leq U^{\prime}$
with $\dim U^{\prime}_{j}\geq\dim U^{\prime}-2s-5$ such that
$\sum_{i\in[s]}\lambda_{ij}(\alpha_{i}(x,y)+\alpha_{i}(y,x))=0$ when $x,y\in
U^{\prime}_{j}$. We may take $V^{1}=\cap_{j\in[s]}U^{\prime}_{j}$.

Proof of (ii). Let $i,j\in[s]$ be given. This time we find elements
$x,y,z,w\in U^{\prime}$ such that $\alpha_{1},\dots,\alpha_{s}$ and $\rho$ are
equal to 0 at all 6 points in the set
$\\{(x,y),(x,z),(x,w),(y,z),(y,w),(z,w)\\}$, with the two exceptions being
$\alpha_{i}(x,z)=\alpha_{j}(y,w)=1$. Once we have such elements $x,y,z,w$ we
use them in (4) which reduces to just
$\lambda^{\prime}_{ij}+\lambda^{\prime\prime}_{ji}=0$, proving that
$\lambda^{\prime}_{ij}=\lambda^{\prime\prime}_{ji}$, which is what we are
after. To obtain such a quadruple of elements $x,y,z,w$, provided $m>4(s+2)$,
we first apply Lemma 2.5 to obtain $(x,z)\in U^{\prime}\times U^{\prime}$ such
that $\rho(x,z)=0$, $\alpha_{\ell}(x,z)=0$ when $\ell\not=i$ and
$\alpha_{i}(x,z)=1$. Then we define a subspace

$\tilde{U}=\\{u\in U^{\prime}\colon\rho(x,u)=\rho(z,u)=0\land(\forall
i\in[s])\alpha_{i}(x,u)=\alpha_{i}(u,x)=\alpha_{i}(z,u)=\alpha_{i}(u,z)=0\\}.$

Provided $m>4(s+2)+8(4s+2)$, we may use Lemma 2.5 one more time to find
$(y,w)\in\tilde{U}\times\tilde{U}$ such that $\rho(y,w)=0$,
$\alpha_{\ell}(y,w)=0$ when $\ell\not=j$ and $\alpha_{j}(y,w)=1$, completing
the proof.∎

Next, we use the second symmetry condition $\phi+\phi\circ(1\,\,3)=0$ in a
similar manner to prove the following claim. We remark that we make use of
Claim 3.4 in the proof.

######  Claim 3.5.

Assume $m\geq 100(s^{2}+s+1)$.

  * (i)

There exists a subspace $V^{2}\leq V^{1}$ such that $\dim V^{2}\geq\dim
V^{1}-2s^{2}-5s$ and $\sum_{i\in[s]}\lambda^{\prime}_{ij}\alpha_{i}$ is
symmetric for all $j\in[s]$ on $V^{2}\times V^{2}$.

  * (ii)

For all $i,j\in[s]$, $\lambda_{ij}=\lambda^{\prime\prime}_{ji}$.

###### Proof.

The identity $\phi+\phi\circ(1\,\,3)=0$ coupled with (3) gives

$\displaystyle 0=$
$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\lambda^{\prime\prime}_{ji}\alpha_{i}(y,x)\alpha_{j}(z,w))+\sum_{i,j\in[s]}\lambda^{\prime}_{ij}(\alpha_{i}(x,z)+\alpha_{i}(z,x))\alpha_{j}(y,w)$
$\displaystyle\hskip
56.9055pt+\sum_{i,j\in[s]}(\lambda^{\prime\prime}_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)+\lambda_{ji}\alpha_{i}(x,w)\alpha_{j}(z,y))$
$\displaystyle+$
$\displaystyle\rho(x,y)(\beta_{1}(z,w)+\beta_{4}(z,w))+\rho(x,w)(\beta_{3}(y,z)+\beta_{6}(z,y))+\rho(y,z)(\beta_{4}(x,w)+\beta_{1}(x,w))$
$\displaystyle\hskip
56.9055pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{5}(z,x))+\rho(z,w)(\beta_{6}(x,y)+\beta_{3}(y,x))$
(5)

for all $x,y,z,w\in U^{\prime}$.

Proof of (i). Let $j\in[s]$ be given. Similarly to the previous claim, we
apply Lemma 2.5 to find $y,w\in V^{1}$ such that $\rho(y,w)=0$,
$\alpha_{i}(y,w)=0$ for $i\not=j$ and $\alpha_{j}(y,w)=1$. Identity (5) for
this choice of $y,w$ and Lemma 2.1(iii) show that the rank of the bilinear map
$\Big{(}\sum_{i\in[s]}\lambda^{\prime}_{ij}(\alpha_{i}|_{V^{1}\times
V^{1}}(x,z)+\alpha_{i}|_{V^{1}\times V^{1}}(z,x))\Big{)}$ is at most $2s+5$.
Lemma 2.2 provides us with a subspace $V^{2}_{j}\leq V^{1}$ with $\dim
V_{j}^{2}\geq V^{1}-2s-5$ on which
$\sum_{i\in[s]}\lambda^{\prime}_{ij}\alpha_{i}$ is symmetric. To finish the
proof, take $V^{2}=\cap_{j\in[s]}V^{2}_{j}$.

Proof of (ii). Using the part (i) of Claim 3.4 we see that whenever
$x,y,z,w\in V^{1}$

$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\lambda^{\prime\prime}_{ji}\alpha_{i}(y,x)\alpha_{j}(z,w))=$
$\displaystyle\sum_{j\in[s]}\Big{(}\sum_{i\in[s]}\lambda_{ij}\alpha_{i}(x,y)\Big{)}\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda^{\prime\prime}_{ji}\alpha_{i}(y,x)\alpha_{j}(z,w)$
$\displaystyle=$
$\displaystyle\sum_{j\in[s]}\Big{(}\sum_{i\in[s]}\lambda_{ij}\alpha_{i}(y,x)\Big{)}\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda^{\prime\prime}_{ji}\alpha_{i}(y,x)\alpha_{j}(z,w)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}+\lambda^{\prime\prime}_{ji})\alpha_{i}(y,x)\alpha_{j}(z,w).$

From (5) we obtain

$\displaystyle 0=$
$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}+\lambda^{\prime\prime}_{ji})\alpha_{i}(y,x)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda^{\prime}_{ij}(\alpha_{i}(x,z)+\alpha_{i}(z,x))\alpha_{j}(y,w)$
$\displaystyle\hskip
56.9055pt+\sum_{i,j\in[s]}(\lambda^{\prime\prime}_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)+\lambda_{ji}\alpha_{i}(x,w)\alpha_{j}(z,y))$
$\displaystyle+$
$\displaystyle\rho(x,y)(\beta_{1}(z,w)+\beta_{4}(z,w))+\rho(x,w)(\beta_{3}(y,z)+\beta_{6}(z,y))+\rho(y,z)(\beta_{4}(x,w)+\beta_{1}(x,w))$
$\displaystyle\hskip
56.9055pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{5}(z,x))+\rho(z,w)(\beta_{6}(x,y)+\beta_{3}(y,x))$
(6)

for all $x,y,z,w\in V^{1}$. We now proceed as in the proof of Claim 3.4(ii).
Let $i,j\in[s]$ be given. Since $m\geq 100(s^{2}+s+1)$, we may find elements
$x,y,z,w\in V^{1}$ such that $\alpha_{1},\dots,\alpha_{r}$ and $\rho$ are
equal to 0 at all 6 points in the set
$\\{(y,x),(x,z),(x,w),(y,z),(y,w),(z,w)\\}$, with the two exceptions being
$\alpha_{i}(y,x)=\alpha_{j}(z,w)=1$. (Note that this time we use the point
$(y,x)$ instead of $(x,y)$.) Evaluating (6) at $(x,y,z,w)$ gives
$\lambda_{ij}=\lambda^{\prime\prime}_{ji}$.∎

It remains to use the third symmetry condition
$\phi+\phi\circ(1\,\,4)=\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)$.

######  Claim 3.6.

Assume $m\geq 200(s^{2}+s+1)$. Then $\lambda_{ij}=\lambda^{\prime}_{ji}$ for
all $i,j\in[s]$.

###### Proof.

The identity $\phi+\phi\circ(1\,\,4)=\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)$
implies that

$\displaystyle 0=$
$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\lambda^{\prime}_{ji}\alpha_{i}(y,x)\alpha_{j}(w,z))+\sum_{i,j\in[s]}(\lambda^{\prime}_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\lambda_{ji}\alpha_{i}(z,x)\alpha_{j}(w,y))$
$\displaystyle\hskip
56.9055pt+\sum_{i,j\in[s]}\lambda^{\prime\prime}_{ij}(\alpha_{i}(x,w)+\alpha_{i}(w,x))\alpha_{j}(y,z)$
$\displaystyle+\rho(x,y)(\rho(z,w)+\beta_{1}(z,w)+\beta_{5}(w,z))+\rho(x,z)(\rho(y,w)+\beta_{2}(y,w)+\beta_{6}(w,y))$
$\displaystyle\hskip
56.9055pt+\rho(y,z)(\beta_{4}(x,w)+\beta_{4}(w,x))+\rho(y,w)(\beta_{5}(x,z)+\beta_{1}(z,x))+\rho(z,w)(\beta_{6}(x,y)+\beta_{2}(y,x))$
(7)

for all $x,y,z,w\in U^{\prime}$. Using Claim 3.4(i) and Claim 3.5(i) we see
that whenever $x,y,z,w\in V^{2}$

$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+$
$\displaystyle\lambda^{\prime}_{ji}\alpha_{i}(y,x)\alpha_{j}(w,z))$
$\displaystyle=$
$\displaystyle\sum_{j\in[s]}\Big{(}\sum_{i\in[s]}\lambda_{ij}\alpha_{i}(x,y)\Big{)}\alpha_{j}(z,w)+\sum_{i\in[s]}\alpha_{i}(y,x)\Big{(}\sum_{j\in[s]}\lambda^{\prime}_{ji}\alpha_{j}(w,z)\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{j\in[s]}\Big{(}\sum_{i\in[s]}\lambda_{ij}\alpha_{i}(y,x)\Big{)}\alpha_{j}(z,w)+\sum_{i\in[s]}\alpha_{i}(y,x)\Big{(}\sum_{j\in[s]}\lambda^{\prime}_{ji}\alpha_{j}(z,w)\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}+\lambda^{\prime}_{ji})\alpha_{i}(y,x)\alpha_{j}(z,w).$

Using this identity, the expression in (7) becomes

$\displaystyle 0=$
$\displaystyle\sum_{i,j\in[s]}(\lambda_{ij}+\lambda^{\prime}_{ji})\alpha_{i}(y,x)\alpha_{j}(z,w)+\sum_{i,j\in[s]}(\lambda^{\prime}_{ij}+\lambda_{ji})\alpha_{i}(z,x)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda^{\prime\prime}_{ij}(\alpha_{i}(x,w)+\alpha_{i}(w,x))\alpha_{j}(y,z)$
$\displaystyle+\rho(x,y)(\rho(z,w)+\beta_{1}(z,w)+\beta_{5}(w,z))+\rho(x,z)(\rho(y,w)+\beta_{2}(y,w)+\beta_{6}(w,y))$
$\displaystyle\hskip
56.9055pt+\rho(y,z)(\beta_{4}(x,w)+\beta_{4}(w,x))+\rho(y,w)(\beta_{5}(x,z)+\beta_{1}(z,x))+\rho(z,w)(\beta_{6}(x,y)+\beta_{2}(y,x))$

for all $x,y,z,w\in V^{2}$. Let $i,j\in[s]$ be fixed now. We complete the
argument as in the proofs of the previous two claims. Since $m$ is
sufficiently large, using Lemma 2.5 we may find elements $x,y,z,w\in V^{2}$
such that $\alpha_{1},\dots,\alpha_{s}$ and $\rho$ are equal to 0 at all 6
points in the set $\\{(y,x),(z,x),(w,x),(y,z),(y,w),(z,w)\\}$, with the two
exceptions being $\alpha_{i}(y,x)=\alpha_{j}(z,w)=1$. It follows that
$\lambda_{ij}=\lambda^{\prime}_{ji}$, as required.∎

It follows from Claims 3.4(ii), 3.5(ii) and 3.6 that

$\lambda_{ij}=\lambda^{\prime}_{ji}=\lambda^{\prime\prime}_{ij}=\lambda_{ji}$

so $\lambda_{ij}=\lambda^{\prime}_{ij}=\lambda^{\prime\prime}_{ij}$ and
$\lambda$ is symmetric. Thus, returning to equality (3) we see that whenever
$x,y,z,w\in U^{\prime}$ then

$\displaystyle\phi(x,y,z,w)=\sigma(x,y,z,w)+\psi(x,y,z,w)$
$\displaystyle+\rho(x,y)\beta_{1}(z,w)+\rho(x,z)\beta_{2}(y,w)+\rho(x,w)\beta_{3}(y,z)$
$\displaystyle+\rho(y,z)\beta_{4}(x,w)+\rho(y,w)\beta_{5}(x,z)+\rho(z,w)\beta_{6}(x,y)$

where $\psi\colon U^{\prime}\times U^{\prime}\times U^{\prime}\times
U^{\prime}\to\mathbb{F}_{2}$ is the multilinear form defined as

$\psi(x,y,z,w)=\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z).$

######  Claim 3.7.

Multilinear form $\psi|_{V^{1}\times V^{1}\times V^{1}\times V^{1}}$ is
symmetric.

###### Proof.

Before we proceed with the proof, we observe a few useful identities that hold
for any $a,b,c,d\in V^{1}$. Using Claim 3.4(ii) and the fact that $\lambda$ is
symmetric we have

$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(a,b)\alpha_{j}(c,d)=\sum_{j\in[s]}\Big{(}\sum_{i\in[s]}\lambda_{ij}\alpha_{i}(a,b)\Big{)}\alpha_{j}(c,d)=$
$\displaystyle\sum_{j\in[s]}\Big{(}\sum_{i\in[s]}\lambda_{ij}\alpha_{i}(b,a)\Big{)}\alpha_{j}(c,d)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(b,a)\alpha_{j}(c,d)$ (8)

and

$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(a,b)\alpha_{j}(c,d)=$
$\displaystyle\sum_{j,i\in[s]}\lambda_{ji}\alpha_{j}(a,b)\alpha_{i}(c,d)=\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(c,d)\alpha_{j}(a,b).$
(9)

Additionally, from these two identities we deduce

$\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(a,b)\alpha_{j}(c,d)=\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(c,d)\alpha_{j}(a,b)=\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(d,c)\alpha_{j}(a,b)=\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(a,b)\alpha_{j}(d,c).$
(10)

Returning to the claim, it suffices to prove
$\psi=\psi\circ(1\,\,2)=\psi\circ(1\,\,3)=\psi\circ(1\,\,4)$ on $V^{1}\times
V^{1}\times V^{1}\times V^{1}$. Fix $x,y,z,w\in V^{1}$. Using the idenities
(8), (9) and (10) above we obtain

$\displaystyle\psi(y,x,z,w)=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(y,x)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(y,z)\alpha_{j}(x,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(y,w)\alpha_{j}(x,z)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)$
$\displaystyle=$ $\displaystyle\psi(x,y,z,w).$

Next, we have

$\displaystyle\psi(z,y,x,w)=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(z,y)\alpha_{j}(x,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(z,x)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(z,w)\alpha_{j}(y,x)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(y,z)\alpha_{j}(x,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(z,w)\alpha_{j}(x,y)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)$
$\displaystyle=$ $\displaystyle\psi(x,y,z,w).$

Finally, we have

$\displaystyle\psi(w,y,z,x)=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(w,y)\alpha_{j}(z,x)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(w,z)\alpha_{j}(y,x)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(w,x)\alpha_{j}(y,z)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(y,w)\alpha_{j}(x,z)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(z,w)\alpha_{j}(x,y)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)$
$\displaystyle=$
$\displaystyle\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,y)\alpha_{j}(z,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,z)\alpha_{j}(y,w)+\sum_{i,j\in[s]}\lambda_{ij}\alpha_{i}(x,w)\alpha_{j}(y,z)$
$\displaystyle=$ $\displaystyle\psi(x,y,z,w).\qed$

Thus, we may consume $\psi$ into $\sigma$ and without loss of generality
$\phi$ takes the shape

$\displaystyle\phi(x,y,z,w)=\sigma(x,y,z,w)+$
$\displaystyle\rho(x,y)\beta_{1}(z,w)+\rho(x,z)\beta_{2}(y,w)+\rho(x,w)\beta_{3}(y,z)$
$\displaystyle+$
$\displaystyle\rho(y,z)\beta_{4}(x,w)+\rho(y,w)\beta_{5}(x,z)+\rho(z,w)\beta_{6}(x,y)$
(11)

for $x,y,z,w\in V^{1}$.

We use the symmetry properties of $\phi$ for the second time in order to
elucidate the structure of forms $\beta_{1},\dots,\beta_{6}$. Equality
$\phi=\phi\circ(1\,\,2)$ implies that

$\displaystyle 0=$ $\displaystyle\phi(x,y,z,w)+\phi(y,x,z,w)$ $\displaystyle=$
$\displaystyle\rho(x,z)(\beta_{2}(y,w)+\beta_{4}(y,w))+\rho(x,w)(\beta_{3}(y,z)+\beta_{5}(y,z))+\rho(y,z)(\beta_{4}(x,w)+\beta_{2}(x,w))$
$\displaystyle\hskip
56.9055pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{3}(x,z))+\rho(z,w)(\beta_{6}(x,y)+\beta_{6}(y,x))$

for $x,y,z,w\in V^{1}$. If we fix $(z,w)\in V^{1}\times V^{1}$ such that
$\rho(z,w)=1$ (such a point exists by Lemma 2.5 if $m\geq 100(s^{2}+s+1)$), we
see that the rank of the map $(x,y)\mapsto\beta_{6}(x,y)+\beta_{6}(y,x)$ on
$V^{1}\times V^{1}$ is at most 4. Similarly, if we fix $(x,z)\in V^{1}\times
V^{1}$ such that $\rho(x,z)=1$ (respectively $(x,w)\in V^{1}\times V^{1}$ such
that $\rho(x,w)=1$), we obtain that the rank of $\beta_{2}+\beta_{4}+\mu\rho$
for scalar $\mu=\beta_{3}(x,z)+\beta_{5}(x,z)$ (respectively
$\beta_{3}+\beta_{5}+\mu^{\prime}\rho$ for scalar
$\mu^{\prime}=\beta_{2}(x,w)+\beta_{4}(x,w)$) is at most 3 on $V^{1}\times
V^{1}$. Using Lemma 2.2 we find a suitable subspace $W^{1}\leq V^{1}$ of $\dim
W^{1}\geq\dim V^{1}-10$ such that $\beta_{6}|_{W^{1}\times W^{1}}$ is
symmetric and

$\beta_{2}|_{W^{1}\times W^{1}}+\beta_{4}|_{W^{1}\times
W^{1}},\beta_{3}|_{W^{1}\times W^{1}}+\beta_{5}|_{W^{1}\times
W^{1}}\in\langle\rho|_{W^{1}\times W^{1}}\rangle.$ (12)

Proceeding further, equality $\phi=\phi\circ(1\,\,3)$ and the fact that
$\beta_{6}|_{W^{1}\times W^{1}}$ is symmetric imply that for $x,y,z,w\in
W^{1}$ we have

$\displaystyle 0=$ $\displaystyle\phi(x,y,z,w)+\phi(z,y,x,w)$ $\displaystyle=$
$\displaystyle\rho(x,y)(\beta_{1}(z,w)+\beta_{4}(z,w))+\rho(x,w)(\beta_{3}(y,z)+\beta_{6}(z,y))+\rho(y,z)(\beta_{4}(x,w)+\beta_{1}(x,w))$
$\displaystyle\hskip
56.9055pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{5}(z,x))+\rho(z,w)(\beta_{6}(y,x)+\beta_{3}(x,y))$
$\displaystyle=$
$\displaystyle\rho(x,y)(\beta_{1}(z,w)+\beta_{4}(z,w))+\rho(x,w)(\beta_{3}(y,z)+\beta_{6}(y,z))+\rho(y,z)(\beta_{4}(x,w)+\beta_{1}(x,w))$
$\displaystyle\hskip
56.9055pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{5}(z,x))+\rho(z,w)(\beta_{6}(x,y)+\beta_{3}(x,y)).$

Again, fixing suitable pairs of $x,y,z,w\in W^{1}$ with $\rho=1$ (using Lemma
2.5, assuming $m\geq 200(s^{2}+s+1)$), we see that the ranks of
$(x,z)\mapsto\beta_{5}(x,z)+\beta_{5}(z,x)$, $\beta_{1}+\beta_{4}+\mu\rho$ and
$\beta_{3}+\beta_{6}+\mu^{\prime}\rho$ for suitable scalars
$\mu,\mu^{\prime}\in\mathbb{F}_{2}$ are at most 4,3 and 3 respectively. After
passing to a suitable subspace $W^{2}\leq W^{1}$ of $\dim W^{2}\geq\dim
W^{1}-10$ using Lemma 2.2, we obtain that $\beta_{5}|_{W^{2}\times W^{2}}$ is
symmetric and

$\beta_{1}|_{W^{2}\times W^{2}}+\beta_{4}|_{W^{2}\times
W^{2}},\beta_{3}|_{W^{2}\times W^{2}}+\beta_{6}|_{W^{2}\times
W^{2}}\in\langle\rho|_{W^{2}\times W^{2}}\rangle.$ (13)

Finally, equality
$\phi(x,y,z,w)=\phi(w,y,z,x)+\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)$ and
symmetry of maps $\beta_{6}|_{W^{2}\times W^{2}}$ and $\beta_{5}|_{W^{2}\times
W^{2}}$ give

$\displaystyle\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)=\phi(x,y,z,w)+\phi(w,y,z,x)$
$\displaystyle\hskip
56.9055pt=\rho(x,y)(\beta_{1}(z,w)+\beta_{5}(w,z))+\rho(x,z)(\beta_{2}(y,w)+\beta_{6}(w,y))+\rho(y,z)(\beta_{4}(x,w)+\beta_{4}(w,x))$
$\displaystyle\hskip
113.81102pt+\rho(y,w)(\beta_{5}(x,z)+\beta_{1}(z,x))+\rho(z,w)(\beta_{6}(x,y)+\beta_{2}(y,x))$
$\displaystyle\hskip
56.9055pt=\rho(x,y)(\beta_{1}(z,w)+\beta_{5}(z,w))+\rho(x,z)(\beta_{2}(y,w)+\beta_{6}(y,w))+\rho(y,z)(\beta_{4}(x,w)+\beta_{4}(w,x))$
$\displaystyle\hskip
113.81102pt+\rho(y,w)(\beta_{5}(z,x)+\beta_{1}(z,x))+\rho(z,w)(\beta_{6}(y,x)+\beta_{2}(y,x))$

for all $x,y,z,w\in W^{2}$. Applying the same argument for the third time,
after fixing suitable pairs of $x,y,z,w\in W^{1}$ with $\rho=1$ (using Lemma
2.5, this time assuming $m\geq 300(s^{2}+s+1)$) we see that the ranks of
$(x,w)\mapsto\beta_{4}(x,w)+\beta_{4}(w,x)$, $\beta_{1}+\beta_{5}+\mu\rho$ and
$\beta_{2}+\beta_{6}+\mu^{\prime}\rho$ for suitable scalars
$\mu,\mu^{\prime}\in\mathbb{F}_{2}$ are at most 4,3 and 3 respectively. We
thus find a subspace $W^{3}\leq W^{2}$ of $\dim W^{3}\geq\dim W^{2}-10$ using
Lemma 2.2, such that $\beta_{4}|_{W^{3}\times W^{3}}$ is symmetric and

$\beta_{1}|_{W^{3}\times W^{3}}+\beta_{5}|_{W^{3}\times
W^{3}},\beta_{2}|_{W^{3}\times W^{3}}+\beta_{6}|_{W^{3}\times
W^{3}}\in\langle\rho|_{W^{3}\times W^{3}}\rangle.$ (14)

Using facts (12), (13) and (14), writing $\beta=\beta_{6}$ and restricting all
maps to the product $W^{3}\times W^{3}$, we obtain
$\beta_{2},\beta_{3}\in\beta+\langle\rho\rangle$, from which we further get
$\beta_{4}\in\beta_{2}+\langle\rho\rangle=\beta+\langle\rho\rangle$ and
$\beta_{5}\in\beta_{3}+\langle\rho\rangle=\beta+\langle\rho\rangle$, which
finally implies
$\beta_{1}\in\beta_{4}+\langle\rho\rangle=\beta+\langle\rho\rangle$. Hence,
all $\beta_{i}$ belong to $\beta+\langle\rho\rangle$. In conclusion, we obtain
scalars $\lambda_{1},\lambda_{2},\lambda_{3}\in\mathbb{F}_{2}$ such that

$\displaystyle\phi(x,y,z,w)=\sigma(x,y,z,w)+$
$\displaystyle\rho(x,y)\beta(z,w)+\rho(x,z)\beta(y,w)+\rho(x,w)\beta(y,z)$
$\displaystyle+$
$\displaystyle\rho(y,z)\beta(x,w)+\rho(y,w)\beta(x,z)+\rho(z,w)\beta(x,y)$
$\displaystyle+$
$\displaystyle\lambda_{1}\rho(x,y)\rho(z,w)+\lambda_{2}\rho(x,z)\rho(y,w)+\lambda_{3}\rho(x,w)\rho(y,z)$

holds for all $x,y,z,w\in W^{3}$.

Since $\rho$ and $\beta$ are symmetric on $W^{3}\times W^{3}$, the multilinear
form

$\rho(x,y)\beta(z,w)+\rho(x,z)\beta(y,w)+\rho(x,w)\beta(y,z)+\rho(y,z)\beta(x,w)+\rho(y,w)\beta(x,z)+\rho(z,w)\beta(x,y)$

is readily seen to be symmetric, so it can be consumed into $\sigma$, and on
$W^{3}\times W^{3}\times W^{3}\times W^{3}$ we may assume that

$\displaystyle\phi(x,y,z,w)=\sigma(x,y,z,w)+\lambda_{1}\rho(x,y)\rho(z,w)+\lambda_{2}\rho(x,z)\rho(y,w)+\lambda_{3}\rho(x,w)\rho(y,z).$
(15)

Let us use the symmetry conditions for $\phi$ for the final time in order to
understand the relationship between scalars $\lambda_{1},\lambda_{2}$ and
$\lambda_{3}$. Note that the codimension of the subspace $W^{3}$ inside
$U^{\prime}$ is at most $2s^{2}+5s+30$, so by Lemma 2.3 we have
$\operatorname{rank}\rho|_{W^{3}\times W^{3}}\geq 2$ (assuming $m\geq
100(s^{2}+s+1)$). The equality $\phi=\phi\circ(1\,\,2)$ gives

$(\lambda_{2}+\lambda_{3})(\rho(x,z)\rho(y,w)+\rho(x,w)\rho(y,z))=0$

for all $x,y,z,w\in W^{3}$. Since $\operatorname{rank}\rho|_{W^{3}\times
W^{3}}\geq 2$, the map $\rho|_{W^{3}\times W^{3}}$ is non-zero, so we can find
$(y,w)\in W^{3}\times W^{3}$ such that $\rho(y,w)=1$. The equality above then
shows that $(\lambda_{2}+\lambda_{3})\rho|_{W^{3}\times W^{3}}$ has rank at
most 1. However, using the fact that the rank of $\rho|_{W^{3}\times W^{3}}$
is at least 2 again, we deduce $\lambda_{2}=\lambda_{3}$.
Similarly, the condition $\phi=\phi\circ(1\,\,3)$ implies

$(\lambda_{1}+\lambda_{3})(\rho(x,y)\rho(z,w)+\rho(x,w)\rho(y,z))=0$

for all $x,y,z,w\in W^{3}$. Using the same rank bound
$\operatorname{rank}\rho|_{W^{3}\times W^{3}}\geq 2$ allows us to deduce
$\lambda_{1}=\lambda_{3}$.
Putting these equalities together we see that
$\lambda_{1}=\lambda_{2}=\lambda_{3}$ and equality (15) then becomes

$\phi(x,y,z,w)=\sigma(x,y,z,w)+\lambda_{1}\Big{(}\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)+\rho(x,w)\rho(y,z)\Big{)}$

so $\phi=\phi\circ(1\,\,4)$ on $W^{3}\times W^{3}$. The third symmetry
condition tells us that

$\rho(x,y)\rho(z,w)+\rho(x,z)\rho(y,w)=0$

for all $x,y,z,w\in W^{3}$, which is a contradiction as the rank of
$\rho|_{W^{3}\times W^{3}}$ is at least 2. To complete the proof of the
theorem it remains to choose $m=20000(r^{2}+r+1)$ (recall that $s\leq 6r$) so
that all conditions on $m$ are satisfied.∎

## References

  * [1] V. Bergelson, T. Tao and T. Ziegler, _An inverse theorem for the uniformity seminorms associated with the action of $\mathbb{F}^{\infty}_{p}$_, Geometric and Functional Analysis 19 (2010), 1539–1596.
  * [2] O.A. Camarena and B. Szegedy, _Nilspaces, nilmanifolds and their morphisms_ , arXiv preprint (2010), `arXiv:1009.3825`.
  * [3] P. Candela, D. González-Sánchez, B. Szegedy, _On higher-order Fourier analysis in characteristic $p$_, arXiv preprint (2021), `arXiv:2109.15281`.
  * [4] B. Green and T. Tao, _An inverse theorem for the Gowers $U^{3}(G)$-norm_, Proceedings of the Edinburgh Mathematical Society 51 (2008), 73–153.
  * [5] B. Green, T. Tao and T. Ziegler, _An inverse theorem for the Gowers $U^{s+1}[N]$-norm_, Annals of Mathematics 176 (2012), 1231–1372.
  * [6] W.T. Gowers, _A new proof of Szemerédi’s theorem_ , Geometric and Functional Analysis 11 (2001), 465–588.
  * [7] W.T. Gowers and L. Milićević, _A quantitative inverse theorem for the $U^{4}$ norm over finite fields_, arXiv preprint (2017), `arXiv:1712.00241`.
  * [8] W.T. Gowers and L. Milićević, _An inverse theorem for Freiman multi-homomorphisms_ , arXiv preprint (2020), `arXiv:2002.11667`.
  * [9] Y. Gutman, F. Manners and P. Varjú, _The structure theory of Nilspaces I_ , Journal d’Analyse Mathématique 140 (2020), 299–369.
  * [10] Y. Gutman, F. Manners and P. Varjú, _The structure theory of Nilspaces II: Representation as nilmanifolds_ , Transactions of the American Mathematical Society 371 (2019), 4951–4992.
  * [11] Y. Gutman, F. Manners and P. Varjú, _The structure theory of Nilspaces III: Inverse limit representations and topological dynamics_ , Advances in Mathematics 365 (2020), 107059.
  * [12] , A. Jamneshan and T. Tao, _The inverse theorem for the $U^{3}$ Gowers uniformity norm on arbitrary finite abelian groups: Fourier-analytic and ergodic approaches_, arXiv preprint (2021), `arXiv:2112.13759`.
  * [13] O. Janzer, _Polynomial bound for the partition rank vs the analytic rank of tensors_ , Discrete Analysis, paper no. 7 (2020), 1–18.
  * [14] F. Manners, _Quantitative bounds in the inverse theorem for the Gowers $U^{s+1}$-norms over cyclic groups_, arXiv preprint (2018), `arXiv:1811.00718`.
  * [15] L. Milićević, _Polynomial bound for partition rank in terms of analytic rank_ , Geometric and Functional Analysis 29 (2019), 1503–1530.
  * [16] L. Milićević, _Quantitative inverse theorem for $\mathsf{U}^{k}$ norm in $\mathbb{F}_{2}^{n}$_, _in preparation_.
  * [17] E. Naslund, _The partition rank of a tensor and $k$-right corners in $\mathbb{F}_{q}^{n}$_, Journal of Combinatorial Theory, Series A 174 (2020), article 105190.
  * [18] A. Samorodnitsky, _Low-degree tests at large distances_ in _STOC’07-Proceedings of the 39 th Annual ACM Symposium on Theory of Computing_, ACM, New York (2007), 506–515.
  * [19] B. Szegedy, _On higher order Fourier analysis_ , arXiv preprint (2012), `arXiv:1203.2260`.
  * [20] T. Tao and T. Ziegler, _The inverse conjecture for the Gowers norm over finite fields in low characteristic_ , Annals of Combinatorics 16 (2012), 121–188.
  * [21] J. Tidor, _Quantitative bounds for the $U^{4}$-inverse theorem over low characteristic finite fields_, arXiv preprint (2021), `arXiv:2109.13108`.


# Owings-like results for infinitely many
colours or finite monochromatic sets

David J. Fernández-Bretón  Escuela Superior de Física y Matemáticas
Instituto Politécnico Nacional
Av. Instituto Politécnico Nacional s/n Edificio 9, Col. San Pedro Zacatenco,
Alcaldía Gustavo A. Madero, 07738, CDMX, Mexico<EMAIL_ADDRESS>https://dfernandezb.web.app ,  Eliseo Sarmiento Rosales  Escuela Superior de
Física y Matemáticas
Instituto Politécnico Nacional
Av. Instituto Politécnico Nacional s/n Edificio 9, Col. San Pedro Zacatenco,
Alcaldía Gustavo A. Madero, 07738, CDMX, Mexico<EMAIL_ADDRESS>and
Germán Vera  Escuela Superior de Física y Matemáticas
Instituto Politécnico Nacional
Av. Instituto Politécnico Nacional s/n Edificio 9, Col. San Pedro Zacatenco,
Alcaldía Gustavo A. Madero, 07738, CDMX, Mexico.

###### Abstract.

Inspired by Owings’s problem, we investigate whether, for a given an Abelian
group $G$ and cardinal numbers $\kappa,\theta$, every colouring
$c:G\longrightarrow\theta$ yields a subset $X\subseteq G$ with $|X|=\kappa$
such that $X+X$ is monochromatic. (Owings’s problem asks this for
$G=\mathbb{Z}$, $\theta=2$ and $\kappa=\aleph_{0}$; while Hindman proved it
false for the same $G$ and $\kappa$ but $\theta=3$.) We completely settle the
question (in the affirmative whenever $G$ is infinite) for finite $\kappa$ and
$\theta$, and also (in the negative) for $\kappa$ and $\theta$ both infinite.
We also show that, in the case where $\theta$ is infinite but $\kappa$ is
finite, the answer depends both on the cardinality of $G$ and in its algebraic
structure.

##  1\. Introduction

Let $S$ be a commutative semigroup (additively denoted), and let
$\kappa,\theta$ be two cardinal numbers. We will use the following (flavour of
Hungarian) notation: we let the symbol

$S\rightarrow(\kappa)_{\theta}^{\cdot+\cdot}$

denote the (Ramsey-theoretic) statement that, for every colouring
$c:S\longrightarrow\theta$, there exists a subset $X\subseteq G$ with
$|X|=\kappa$ and $X+X$ monochromatic, where we define

$X+X=\\{x+y\big{|}x,y\in X\\}=\\{x+y\big{|}x,y\in X\text{ are
distinct}\\}\cup\\{2x\big{|}x\in X\\};$

the notation $G\nrightarrow(\kappa)_{\theta}^{\cdot+\cdot}$ will of course
denote the negation of $G\rightarrow(\kappa)_{\theta}^{\cdot+\cdot}$. An old
1974 problem of J. Owings [7] asks whether
$\mathbb{N}\longrightarrow(\aleph_{0})_{2}^{\cdot+\cdot}$. Shortly after this
problem appeared, N. Hindman [1] seemed to make progress toward a solution by
showing that $\mathbb{N}\nrightarrow(\aleph_{0})_{3}^{\cdot+\cdot}$.
Surprisingly, in spite of Hindman’s result and of other serious efforts at
tackling Owings’s original problem, this remains open.

Another line of inquiry was recently open by considering Owings type questions
for other infinite groups111In this paper, all groups will be Abelian and will
be written in additive notation, i.e., $+$ denotes the group operation, $-x$
denotes the inverse of the element $x$, and $0$ denotes the identity element.,
especially the additive group of the real numbers $\mathbb{R}$. Hindman,
Leader and Strauss [2] showed that it is consistent to have a finite $\theta$
such that $\mathbb{R}\nrightarrow(\aleph_{0})_{\theta}^{\cdot+\cdot}$ (more
concretely, if $|\mathbb{R}|=\aleph_{n}$ then one can take $\theta=9\cdot
2^{4+n}$). On the other hand, Leader and Russell [6] proved that, if $V$ is
any $\mathbb{Q}$-vector space of dimension at least $\beth_{\omega}$, then
$V\rightarrow(\aleph_{0})_{\theta}^{\cdot+\cdot}$ for every finite $\theta$. A
natural question that arises after consideration of these results is whether
one can consistently show a positive result for the real line. Such a result
was achieved by a set of six authors [4], who established that, if the
existence of an $\omega_{1}$-Erdős cardinal is consistent, then so is the
statement that $\mathbb{R}\longrightarrow(\aleph_{0})_{\theta}^{\cdot+\cdot}$
holds for every finite $\theta$. Later on, J. Zhang [10] removed the need for
using large cardinals in the previous result, showing that it is consistent to
have $|\mathbb{R}|=\aleph_{\omega+1}$ and
$\mathbb{R}\longrightarrow(\aleph_{0})_{\theta}^{\cdot+\cdot}$ for every
finite $\theta$; furthermore, in this paper the statement
$\mathbb{R}\longrightarrow(\aleph_{0})_{2}^{\cdot+\cdot}$ is shown to be a
$\mathnormal{\mathsf{ZFC}}$ theorem.

As can be seen from the previous summary, questions about the statement
$G\longrightarrow(\kappa)_{\theta}^{\cdot+\cdot}$ have been studied
extensively for infinite $\kappa$ and finite $\theta$; in this setting, some
surprising results have been obtained, while at the same time many questions
remain open. In this paper we set to study the remaining combinations of
$\kappa$ and $\theta$. Section 2 deals with the case where both $\kappa$ and
$\theta$ are assumed to be finite, and Section 3 deals with the case where
both $\kappa$ and $\theta$ are infinite; in both cases we get a complete
answer to the relevant question (affirmative in the first case for any
infinite group $G$, and negative in the second case for any group). Finally,
in Section 4 we tackle the case where $\theta$ is infinite but $\kappa$ is
finite; surprisingly, we obtain examples of groups where the answer is
positive and a class of groups where it is negative.

## Acknowledgements

This work is part of the third author’s PhD dissertation, conducted under the
supervision of the remaining two authors. The first two authors were partially
supported by internal grants SIP-20230355 and SIP-20232086, respectively, from
the Instituto Politécnico Nacional. The third author is grateful to Conahcyt
for their financial support by means of PhD scholarship 744225.

##  2\. Finitely many colours, finite monochromatic sets

In this section we will show that, if $G$ is any infinite group, then for all
$n,r\in\mathbb{N}$ the statement $G\rightarrow(n)_{r}^{\cdot+\cdot}$ holds.
The proof is similar to that of the main result in [6]. We begin with a lemma.

######  Lemma 1.

Let $G$ be an infinite group. Then, there exists a sequence of elements of
$G$, $(g_{n}\big{|}n\in\mathbb{N})$, with the property that, whenever there is
an equality

$\sum_{i=1}^{n}\varepsilon_{i}g_{k_{i}}=\sum_{j=1}^{m}\delta_{j}g_{l_{j}}$

where $k_{1}<\cdots<k_{n}$, $l_{1}<\cdots<l_{m}$, and
$\varepsilon_{i},\delta_{j}\in\\{1,2,3,4\\}$, then it must be the case that
$n=m$, $k_{i}=l_{i}$ for all $i\in\\{1,\ldots,n\\}$, and
$\varepsilon_{i}=\delta_{i}$ for all $i<n$.

###### Proof.

Notice that if $G=\mathbb{Z}$, then the sequence $g_{n}=5^{n}$ satisfies the
given condition. Consequently, if an arbitrary infinite group $G$ contains at
least one element $g\in G$ of infinite order, then we can easily find the
elements $g_{n}$ within the cyclic subgroup $\langle g\rangle$, which is
isomorphic to $\mathbb{Z}$.

We may thus assume that all elements of $G$ have finite order, and hence that
all finitely generated subgroups of $G$ are finite. This allows us to begin
with an arbitrary $g_{0}\in G$ and then recursively pick $g_{n}\in
G\setminus\langle g_{i}\mid i<n\rangle$, which is always possible because $G$
is infinite whereas the subgroup $\langle g_{i}\mid i<n\rangle$ is finite. It
is readily checked that the sequence $(g_{n}\mid n\in\mathbb{N})$ obtained
this way satisfies the desired conclusion. ∎

The previous lemma essentially provides us with a sequence of elements $g_{n}$
such that each $g\in G$ of the form $\sum_{i=1}^{n}\varepsilon_{i}g_{k_{i}}$,
with $k_{1}<\cdots<k_{n}$ and $\varepsilon_{i}\in\\{1,2,3,4\\}$, can be
represented uniquely as such an expression on the $g_{n}$.

In order to handle the notation for expressions such as the one considered in
the previous paragraph, we introduce the following notation: given a finite
sequence of integers
$\vec{\varepsilon}=(\varepsilon_{1},\ldots,\varepsilon_{m})$, and a finite
sequence of group elements $\vec{g}=(g_{1},\ldots,g_{n})$, the notation
$\vec{\varepsilon}*\vec{g}$ will denote the element

(1)
$\vec{\varepsilon}*\vec{g}=\sum_{i=1}^{\min\\{n,m\\}}\varepsilon_{i}g_{i}.$

######  Theorem 2.

If $G$ is an infinite group, and $n,r\in\mathbb{N}$ are arbitrary, then the
statement $G\rightarrow(n)_{r}^{\cdot+\cdot}$ holds.

###### Proof.

Following ideas from [6], consider the following $r+1$ sequences of integers:

$\displaystyle\vec{\varepsilon_{0}}$ $\displaystyle=$
$\displaystyle(\underbrace{4,\ldots,4}_{r\text{ times}})$
$\displaystyle\vec{\varepsilon_{1}}$ $\displaystyle=$
$\displaystyle(\underbrace{4,\ldots,4}_{r-1\text{ times}},2,2)$
$\displaystyle\vdots$ $\displaystyle\vec{\varepsilon_{i}}$ $\displaystyle=$
$\displaystyle(\underbrace{4,\ldots,4}_{r-i\text{
times}},\underbrace{2,\ldots,2}_{2i\text{ times}})$ $\displaystyle\vdots$
$\displaystyle\vec{\varepsilon_{r}}$ $\displaystyle=$
$\displaystyle(\underbrace{2,\ldots,2}_{2r\text{ times}})$

We now take a sequence of elements of $G$, $(g_{k}\big{|}k\in\mathbb{N})$, as
guaranteed by Lemma 1. Define a new colouring
$d:[\mathbb{N}]^{2r}\longrightarrow C$, where $C$ is the set of all possible
$(r+1)$-tuples of elements of $\\{0,\ldots,r-1\\}$, by the formula

$d(n_{1},\ldots,n_{2r})=(c(\vec{\varepsilon_{0}}*(g_{n_{1}},\ldots,g_{n_{2r}})),c(\vec{\varepsilon_{1}}*(g_{n_{1}},\ldots,g_{n_{2r}})),\ldots,c(\vec{\varepsilon_{r}}*(g_{n_{1}},\ldots,g_{n_{2r}})))$

whenever $n_{1}<\ldots<n_{2r}$. The set $C$ of colours is finite, and so by
Ramsey’s theorem [8], there exists an infinite subset $Y\subseteq\mathbb{N}$
such that $[Y]^{2r}$ is $d$-monochromatic, say on colour
$(t_{0},\ldots,t_{r})$. Since each of the $t_{i}$ is one of $r$ possible
values in the set $\\{0,\ldots,r-1\\}$, there must be $i\neq j$ such that
$t_{i}=t_{j}=t$. Pick $(r-j)+n(j-i)+2i$ elements from the set $Y$, denoted
$a_{1},\ldots,a_{r-j},b_{1},\ldots,b_{n(j-i)},c_{1},\ldots,c_{2i}\in Y$ with
$a_{1}<\cdots<a_{r-j}<b_{1}<\cdots<b_{n(j-i)}<c_{1}<\cdots<c_{2i}$ and define
elements $x_{1},\ldots,x_{n}\in G$ by the formula

$x_{k}=2g_{a_{1}}+\cdots+2g_{a_{r-j}}+2g_{b_{(k-1)(j-i)+1}}+\cdots+2g_{b_{k(j-i)}}+g_{c_{1}}+\cdots+g_{c_{2i}}$

so that

$\displaystyle 2x_{k}$ $\displaystyle=$ $\displaystyle
4g_{a_{1}}+\cdots+4g_{a_{r-j}}+4g_{b_{(k-1)(j-i)+1}}+\cdots+4g_{b_{k(j-i)}}+2g_{c_{1}}+\cdots+2g_{c_{2i}}$
$\displaystyle=$
$\displaystyle\vec{\varepsilon_{i}}*(a_{1},\ldots,a_{r-j},b_{(k-1)(j-i)+1},\ldots,b_{k(j-i)},c_{1},\ldots,c_{2i})$

and thus $c(2x_{k})=t_{i}=t$. Also, the reader may gladly verify that, for
$k<l$, the element $x_{k}+x_{l}$ equals

$\displaystyle=$ $\displaystyle
4g_{a_{1}}+\cdots+4g_{a_{r-j}}+2g_{b_{(k-1)(j-i)+1}}+\cdots+2g_{b_{k(j-i)}}+2g_{b_{(l-1)(j-i)+1}}+\cdots$
$\displaystyle+2g_{b_{l(j-i)}}+2g_{c_{1}}+\cdots+2g_{c_{2i}}$ $\displaystyle=$
$\displaystyle\vec{\varepsilon_{j}}*(a_{1},\ldots,a_{r-j},b_{(k-1)(j-i)+1},\ldots,b_{k(j-i)},b_{(l-1)(j-i)+1},\ldots,b_{l(j-i)},c_{1},\ldots,c_{2i})$

so that $c(x_{k}+x_{l})=t_{j}=t$. Hence, if we define
$X=\\{x_{1},\ldots,x_{n}\\}$, we have $|X|=n$ and $X+X$ is $c$-monochromatic
(in colour $t$). ∎

##  3\. Infinitely many colours, no infinite monochromatic set

In this section, we will see that
$G\nrightarrow(\aleph_{0})_{\aleph_{0}}^{\cdot+\cdot}$ holds for all abelian
groups $G$. In other words, for any given group, we can construct a colouring,
using infinitely many colours, such that there are no infinite monochromatic
sets of the form $X+X$.

To begin with, we mention a really useful fact about Abelian groups that stems
from the theory of divisible groups: any Abelian group can be embedded in a
direct sum $\bigoplus_{\alpha<\kappa}G_{\alpha}$, where each $G_{\alpha}$ is a
copy of either $\mathbb{Q}$, or a Prüfer group $\mathbb{Z}[p^{\infty}]$ for
some prime number $p$ (for the details, see e.g. [9, Th. 9.23 and 9.14]);
furthermore if $G$ is uncountable then the index set $\kappa$ of the direct
sum can be assumed to be $|G|$. Hence each element of a group can be thought
of as a member of some such direct sum; in order to uniformize notation and
not worry about the precise nature of the summand $G_{\alpha}$, we introduce
the following definition.

######  Defininion 3.

We define $\mathbb{G}=\mathbb{Q}[\sqrt{2}]/\mathbb{Z}$.

Note that, according to Definition 3, $\mathbb{G}$ is a countable subgroup of
the 1-dimensional torus $\mathbb{T}=\mathbb{R}/\mathbb{Z}$. Furthermore, each
$\mathbb{Z}[p^{\infty}]$, as well as $\mathbb{Q}$, embeds222Each Prüfer group
$\mathbb{Z}[p^{\infty}]$ may in fact be defined as the subgroup of
$\mathbb{T}/\mathbb{Z}$ generated by the equivalence classes of
$\frac{1}{p^{n}}$, where $n$ ranges over all natural numbers, and thus
$\mathbb{Z}[p^{\infty}]$ is a subgroup of
$\mathbb{Q}/\mathbb{Z}\subseteq\mathbb{G}$. On the other hand, mapping each
$q\in\mathbb{Q}$ to the equivalence class of $q\sqrt{2}$ embeds $\mathbb{Q}$
into $\mathbb{G}$. into $\mathbb{G}$. Hence from now on, an uncountable
(Abelian) group $G$ will always be thought of as a subgroup of
$\bigoplus_{\alpha<\kappa}\mathbb{G}$, where $\kappa=|G|$; elements of
$\mathbb{G}\subseteq\mathbb{R}/\mathbb{Z}$ will usually be denoted by either
of its representatives modulo $\mathbb{Z}$. Given such an element
$g=(g_{\alpha}\big{|}\alpha<\kappa)\in G$, we define the support of $g$ by

$\operatorname{supp}(g)=\\{\alpha<\kappa\big{|}g_{\alpha}\neq 0\\}.$

After proving the following lemma, we will be in shape to prove the main
theorem of this section.

######  Lemma 4.

For each $y\in\mathbb{T}=\mathbb{R}/\mathbb{Z}$, the equation $2x=y$ has at
most two solutions in $\mathbb{T}$. In particular, the same statement holds if
we replace $\mathbb{T}$ with $\mathbb{G}$.

###### Proof.

Suppose that $x_{1},x_{2}$ are two solutions to the equation $2x=y$. Then
$2x_{1}=2x_{2}$, so that $x_{1}-x_{2}$ is either zero, or an element of order
two. Since there is exactly one element of order two in $\mathbb{T}$ (namely
the equivalence class of $\frac{1}{2}$), the lemma follows. ∎

######  Theorem 5.

For every group $G$, there exists a colouring $c:G\longrightarrow C$, with $C$
countably infinite, such that for every infinite subset $X\subseteq G$ the set
$X+X$ is not monochromatic.

###### Proof.

Since the result is obvious for a (finite or infinite) countable $G$ (for in
this case it suffices to colour each element of $G$ with a different colour),
it suffices to consider the case $G=\bigoplus_{\alpha<\kappa}\mathbb{G}$,
where $\kappa$ is an uncountable cardinal (if we show that
$G\nrightarrow(\aleph_{0})_{\aleph_{0}}^{\cdot+\cdot}$ then the same statement
holds of any subgroup $H\leq G$ by simply considering the restriction of the
witnessing colouring to $H$). Let $C$ be the set of finite sequences of
nonzero elements of $\mathbb{G}$, and (noting that $C$ is countable) define
the colouring $c:G\longrightarrow C$ by the formula

$c(g_{\alpha}\big{|}\alpha<\kappa)=(g_{\alpha_{1}},\ldots,g_{\alpha_{m}}),$

where $\alpha_{1},\ldots,\alpha_{m}$ are the elements of
$\operatorname{supp}(g)$ enumerated increasingly. In other words, $c(g)$ is
the (finite) sequence of nonzero entries of $g$.

Suppose that $X\subseteq G$ is an infinite set such that $X+X$ is
$c$-monochromatic, say on colour $(x_{1},\ldots,x_{n})$. Given two distinct
elements $g,h\in X$, we note that
$\operatorname{supp}(g)\bigtriangleup\operatorname{supp}(h)\subseteq\operatorname{supp}(g+h)\subseteq\operatorname{supp}(g)\cup\operatorname{supp}(h)$,
and so $|\operatorname{supp}(g)\bigtriangleup\operatorname{supp}(h)|\leq n$.
Morevoer,
$|\operatorname{supp}(g)|\leq|\operatorname{supp}(h)|+|\operatorname{supp}(g)\setminus\operatorname{supp}(h)|\leq|\operatorname{supp}(h)|+|\operatorname{supp}(g)\bigtriangleup\operatorname{supp}(h)|\leq|\operatorname{supp}(h)|+n$.
This implies that the set of natural numbers
$\\{|\operatorname{supp}(g)|\big{|}g\in X\\}$ is bounded by
$n+|\operatorname{supp}(h)|$ where $h\in X$ is any fixed element, and so by
the pigeonhole principle $X$ contains an infinite subset in which
$|\operatorname{supp}(g)|$ is constant. We may thus assume that there exists
an infinite set $X$ and a fixed number $s$ such that $X+X$ is
$c$-monochromatic and $(\forall g\in X)(|\operatorname{supp}(g)|=s)$; suppose
furthermore that we have picked such a set $X$ with $s$ as small as possible.
Once again we let $(x_{1},\ldots,x_{n})$ denote the colour in which $X+X$ is
$c$-monochromatic. Note that, if $(y_{1},\ldots,y_{s})$ is the sequence of
nonzero elements of some $g\in X$, then for each $i\leq s$ it must be the case
that $2y_{i}$ equals either $0$, or some $x_{j}$ for $j\leq n$. By Lemma 4,
there are only finitely many (in fact, at most $2^{s}$) possible choices for
the sequence $(y_{1},\ldots,y_{s})$, and so by the pigeonhole principle we may
assume (by passing to some infinite subset of $X$ if necessary) that there is
a fixed sequence $(y_{1},\ldots,y_{s})$ that is the sequence of nonzero
entries of all $g\in X$. This, in particular, implies that two distinct
elements of $X$ cannot have the same support set, and so
$\\{\operatorname{supp}(g)\big{|}g\in X\\}$ is an infinite family of sets of
size $s$. Hence, by333This statement is commonly known as the $\Delta$-system
lemma or the sunflower lemma. For a proof, see [5, p. 421]. [5, p. 107,
statement 1], we may pass to an infinite subset of $X$ and assume that there
is a fixed set $R\subseteq\kappa$ such that, for any two distinct $g,h\in X$,
$\operatorname{supp}(g)\cap\operatorname{supp}(h)=R$. Further applications of
the pigeonhole principle allow us to assume that, for all $g\in X$, the
sequence of $R$-entries $(g_{\alpha_{1}},\ldots,g_{\alpha_{r}})$, where
$r=|R|$ and $\alpha_{1}<\ldots<\alpha_{r}$ are the elements of $R$, is
constant.

We claim that for each $\alpha\in R$, it must be the case that
$\alpha\in\operatorname{supp}(g+h)$ for any two $g,h\in X$. If not, then we
must have $g_{\alpha}+h_{\alpha}=0$, but since we are assuming
$g_{\alpha}=h_{\alpha}$ this implies either $g_{\alpha}=h_{\alpha}=0$, a
contradiction, or $g_{\alpha}=h_{\alpha}=\frac{1}{2}$. However, this allows us
to “ignore” the $\alpha$-th entry: for each $g\in X$, let $\tilde{g}$ denote
the element with the same entries as $g$, except in the $\alpha$-th entry,
where $\tilde{g}_{\alpha}=0$. Then the set $\tilde{X}=\\{\tilde{g}\big{|}g\in
X\\}$ is another infinite set, with $\tilde{X}+\tilde{X}$ monochromatic (in
the same colour as $X+X$) and all elements $\tilde{g}$ satisfying
$|\operatorname{supp}(\tilde{g})|=s-1$, contradicting the minimality of $s$.
Hence, this second case also leads to a contradiction, and we conclude that
$2g_{\alpha}=2h_{\alpha}=g_{\alpha}+h_{\alpha}\neq 0$. Therefore,
$R=\operatorname{supp}(g)\cap\operatorname{supp}(h)\subseteq\operatorname{supp}(g+h)$,
which implies that
$\operatorname{supp}(g+h)=\operatorname{supp}(g)+\operatorname{supp}(h)$. This
itself is a contradiction, as it implies
$n=|c(g+h)|=|\operatorname{supp}(g+h)|=r+2(s-r)$, while simultaneously
$n=|c(2g)|=|\operatorname{supp}(2g)|\leq|\operatorname{supp}(g)|=s$, since
$\operatorname{supp}(2g)\subseteq\operatorname{supp}(g)$. The last two
(in)equalities show that $2s-r\leq s$, implying $s\leq r$ and so any two
elements of $X$ must have the same support, which we had already established
as impossible. ∎

##  4\. Infinitely many colours, finite monochromatic sets

In this section we consider a countably infinite $\theta$ and a finite
$\kappa$. This is a special case because some groups satisfy the statement
$G\nrightarrow(\kappa)_{\theta}^{\cdot+\cdot}$ while others do not.

######  Theorem 6.

Let $G$ be a group satisfying one of the following properties:

  1. (1)

either $G$ is countable, or

  2. (2)

$G$ is a torsion group without elements of order $4$, or

  3. (3)

$G$ has no elements of order $2$.

Then $G\nrightarrow(2)_{\aleph_{0}}^{\cdot+\cdot}$

###### Proof.

The case where $G$ is countable is straightforward (simply give a different
colour to each element of $G$, as we did in the proof of Theorem 5), so we
begin by assuming that $G$ is uncountable, and thus a subgroup of
$\bigoplus_{\alpha<\kappa}\mathbb{G}$ where $\kappa=|G|$. If $C$ is the
(countable) set of finite sequences of nonzero elements of $\mathbb{G}$, we
define $c:G\longrightarrow C$ by letting $c(g)$ be the (finite) sequence of
nonzero entries of $g$.

Suppose there were two distinct elements
$g=(g_{\alpha}\big{|}\alpha<\kappa),h=(h_{\alpha}\big{|}\alpha<\kappa)$ such
that $\\{g,h\\}+\\{g,h\\}=\\{2g,2h,g+h\\}$ were $c$-monochromatic. We begin by
showing that we can assume that none of the entries $g_{\alpha},h_{\alpha}$
has order $4$. In case $G$ is a torsion group without elements of order $4$,
simply note that, in case some $g_{\alpha}$ had order $4$, there would be some
integer multiple of $g$ of order $4$, contradicting the hypothesis about $G$.
If, on the other hand, $G$ (is not necessarily a torsion group, but it) lacks
elements of order $2$, we argue as follows: suppose that some entries of $g$,
or of $h$, have order a power of $2$, and let $k$ be sufficiently large that
both $2^{k}g$ and $2^{k}h$ are still nonzero, but do not have any entry left
with order a power of $2$ (such a $k$ exists because, by hypothesis, the
orders of $g$ and $h$ cannot be powers of $2$, and they only have finitely
many nonzero entries). If $2^{k}g=2^{k}h$, then either $g-h$ is zero, or an
element whose order divides $2^{k}$; the assumption that $G$ lacks elements of
order two makes the latter case impossible, and hence we must have $g=h$, a
contradiction. Therefore $2^{k}g\neq 2^{k}h$ and the set
$\\{2(2^{k}g),2(2^{k}h),2^{k}g+2^{k}h\\}$ still is $c$-monochromatic.

So we may assume that there exist two distinct elements
$g=(g_{\alpha}\big{|}\alpha<\kappa),h=(h_{\alpha}\big{|}\alpha<\kappa)$ such
that none of the entries $g_{\alpha},h_{\alpha}$ has order $4$, and
furthermore the set $\\{2g,2h,g+h\\}$ is $c$-monochromatic, say on colour
$(x_{1},\ldots,x_{n})$. We show, by induction on $\alpha$, that
$g_{\alpha}=h_{\alpha}$ for all $\alpha<\kappa$, hence $g=h$, leading us to a
contradiction.

Suppose, then, that $g_{\xi}=h_{\xi}$ for all $\xi<\alpha$. If
$g_{\alpha}=h_{\alpha}=0$ we are done, so assume without loss of generality
that $g_{\alpha}\neq 0$. If $h_{\alpha}=0$, then the value $g_{\alpha}$ is one
of the non-zero entries of $g+h$, and so there is an $i\leq n$ such that
$x_{i}=g_{\alpha}$. Since $c(g+h)=c(2g)$, the element $2g$ has the exact same
sequence of non-zero entries as $g+h$, so there must be some $g_{\beta}$, with
$\beta\geq\alpha$, such that $2g_{\beta}=x_{i}=g_{\alpha}$. This implies in
particular that $o(g_{\alpha})\neq 2$, since otherwise $g_{\beta}$ would have
order $4$, a contradiction. Hence $2g_{\alpha}\neq 0$ and so $2g_{\alpha}$ is
the $i$-th nonzero entry of both $2g$ and $g+h$, implying that
$2g_{\alpha}=g_{\alpha}+h_{\alpha}$, and therefore $h_{\alpha}=g_{\alpha}\neq
0$.

From the previous paragraph, we can conclude that both $g_{\alpha}$ and
$h_{\alpha}$ are nonzero. One possibility is that
$g_{\alpha}=h_{\alpha}=\frac{1}{2}$, in which case we are done; so we may
assume without loss of generality that $o(g_{\alpha})\neq 2$. Then, again,
this means that $2g_{\alpha}\neq 0$ and therefore
$x_{i}=2g_{\alpha}=g_{\alpha}+h_{\alpha}$, implying that
$g_{\alpha}=h_{\alpha}$. In all of the possible cases we have been able to
conclude that $g_{\alpha}=h_{\alpha}$, and we are done. ∎

It is unclear to the authors if simply requiring that $G$ lacks elements of
order $4$ (cf. question 8) is enough to ensure that
$G\nrightarrow(2)_{\aleph_{0}}^{\cdot+\cdot}$. For example, within the group
$(\mathbb{Z}/4\mathbb{Z})\times(\mathbb{Z}/4\mathbb{Z})\times\mathbb{Z}$,
consider the subgroup $G$ generated by $\\{(1,0,1),(2,0,0),(0,2,0)\\}$, which
contains elements of order $2$ but lacks elements of order $4$. The elements
$g=(1,0,1)$ and $h=(3,2,1)$ both belong to $G$ and are such that the set
$\\{2g,2h,g+h\\}$ is monochromatic for the colouring described in the proof of
Theorem 6. However, $G$ is isomorphic to
$\tilde{G}=\mathbb{Z}\times(\mathbb{Z}/2\mathbb{Z})\times(\mathbb{Z}/2\mathbb{Z})$,
and $\tilde{G}$ does not contain two distinct elements $g,h$ such that
$\\{2g,2h,g+h\\}$ is monochromatic for said colouring. So it is possible that,
in order to establish a more general result, one might need to carefully
choose the embedding of $G$ into $\bigoplus\mathbb{G}$.

To finish the paper, we exhibit an uncountable group with lots of elements of
order $4$ for which the positive result follows. Recall that the cardinal
numbers $\beth_{\alpha}(\theta)$ are defined recursively by
$\beth_{0}(\theta)=\theta$,
$\beth_{\alpha+1}(\theta)=2^{\beth_{\alpha}(\theta)}$, and
$\beth_{\alpha}(\theta)=\sup\\{\beth_{\xi}(\theta)\big{|}\xi<\alpha\\}$ if
$\alpha$ is a limit ordinal.

######  Proposition 7.

Let $\theta$ be an arbitrary infinite cardinal. Let
$\kappa=\beth_{\omega}(\theta)$, and consider the group
$G=\bigoplus_{\alpha<\kappa}(\mathbb{Z}/4\mathbb{Z})$. Then, for every finite
$n$, we have $G\rightarrow(n)_{\aleph_{0}}^{\cdot+\cdot}$.

###### Proof.

In order to fix notation, denote by $e_{\alpha}$ the element of $G$ whose
$\alpha$-th entry equals $1$, with all other entries equal to $0$. Hence each
element of $G$ is a finite $\mathbb{Z}$-linear combination of the
$e_{\alpha}$. Fixing an $n\in\mathbb{N}$, we define $\varepsilon_{0}=1$,
$\delta_{0}=2$, $\varepsilon_{1}=3$, $\delta_{1}=0$, and we proceed to define
$2^{n}$ finite sequences of integers of length $2n$, as follows: for each
$f:\\{1,\ldots,n\\}\longrightarrow\\{0,1\\}$ let

$\vec{s_{f}}=(\varepsilon_{f(1)},\delta_{f(1)},\ldots,\varepsilon_{f(n)},\delta_{f(n)}).$

Given an arbitrary colouring $c:G\longrightarrow\theta$, we define another
colouring $d:[\kappa]^{n}\longrightarrow\theta$ by

$d(\alpha_{1},\ldots,\alpha_{n})=c(2e_{\alpha_{1}}+\cdots+2e_{\alpha_{n}})$

whenever $\alpha_{1}<\cdots<\alpha_{n}$. By the Erdős–Rado theorem [3, Theorem
9.6], there exists an infinite set $Y$ such that $[Y]^{n}$ is
$d$-monochromatic, say on colour $k$. Pick $2n$ distinct elements
$\alpha_{1},\ldots,\alpha_{2n}\in Y$, with $\alpha_{1}<\cdots<\alpha_{2n}$,
and for each $f:\\{1,\ldots,n\\}\longrightarrow\\{0,1\\}$ let
$x_{f}=\vec{s_{f}}*\vec{\alpha}$, where
$\vec{\alpha}=(\alpha_{1},\ldots,\alpha_{2n})$. The reader will gladly verify
that, if $f,g:\\{1,\ldots,n\\}\longrightarrow\\{0,1\\}$ are distinct, then

$\displaystyle
2x_{f}=2e_{\alpha_{1}}+2e_{\alpha_{3}}+\cdots+2e_{\alpha_{2n-1}},$
$\displaystyle
x_{f}+x_{g}=2e_{\alpha_{1+i_{0}}}+2e_{\alpha_{3+i_{1}}}+\cdots+2e_{\alpha_{2n-1+i_{n}}},$

where $i_{j}=|f(j)-g(j)|$, so that
$c(2x_{f})=d(\alpha_{1},\alpha_{3},\ldots,\alpha_{2n-1})=k$ and
$c(x_{f}+x_{g})=d(\alpha_{2},\alpha_{4},\ldots,\alpha_{2n})=k$. Hence if we
let $X=\\{x_{f}\big{|}f:\\{1,\ldots,n\\}\longrightarrow\\{0,1\\}\\}$, then
$|X|=2^{n}$ and $X+X$ is monochromatic in colour $k$. Since the values of
$2^{n}$, as $n$ varies, can be arbitrarily large, the conclusion is that one
can get such sets $X$ of any possible finite size, and we are done. ∎

Note, in particular, that for every colouring of the group from Proposition 7
there are arbitrarily large (but finite) subsets $X$ such that $X+X$ is
monochromatic. For a fixed size of the required monochromatic set, however, it
is very likely that the group from the previous proposition is overkill in
terms of size. For example, upon fixing $n$ and $\theta$, one only needs to
take $\kappa=\beth_{n}(\theta)^{+}$ for the argument in the proof of
Proposition 7 to work and be able to obtain a monochromatic set $X+X$ with
$|X|=2^{n}$ (the key point here being the application of the Erdős–Rado
theorem). Obtaining more precise information along this lines seems to be an
interesting question that we leave open.

######  Question 8.

Let $G$ be an uncountable group without elements of order $4$. Is it the case
that $G\nrightarrow(2)_{\aleph_{0}}^{\cdot+\cdot}$?

######  Question 9.

Is it possible to characterize (in terms of $|G|$, $|\\{x\in
G\big{|}4x=0\\}|$, and possibly $|\\{x\in G\big{|}2x=0\\}|$) precisely those
Abelian groups $G$ satisfying (whether for all $n$, or for some specific one)
$G\rightarrow(n)_{\theta}^{\cdot+\cdot}$?

## References

  * [1] N. Hindman, Partitions and sums of integers with repetition. J. Combin. Theor. Ser. A 27 no.1 (1979), 19–32.
  * [2] N. Hindman, I. Leader and D. Strauss, Pairwise sums in colourings of the reals. Abh. Math. Semin. Univ. Hambg. 87 (2017), 275–287.
  * [3] T. Jech, Set theory. The Third Millenium Edition, Revised and Expanded. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2003.
  * [4] P. Komjáth, I. Leader, P. Russell, S. Shelah, D. Soukup, and Z. Vidnyánszky, Infinite monochromatic sumsets for colourings of the reals. Proc. Amer. Math. Soc. 147 (2019), 2673–2684.
  * [5] P. Komjáth and V. Totik, Problems and Theorems in Classical Set Theory. New York, Springer, 2006.
  * [6] I. Leader and P. Russell, Monochromatic Infinite Sumsets. New York J. Math. 26 (2020), 467–472.
  * [7] J. Owings, Problem E2494. Amer. Math. Monthly 81 (1974), 902.
  * [8] F.P. Ramsey, On a problem of formal logic. Proc. London Math. Soc., s2-30 (1930), 264–286.
  * [9] J. Rotman, The theory of groups. Allyn and Bacon Inc., Boston, Massachusetts, 1973.
  * [10] J. Zhang, Monochromatic sumset without the use of large cardinals. Fund. Math. 250 (2020), 243–252.