# Uncommon linear systems of two equations

Dingding Dong  Dong: Department of Mathematics, Harvard University, Cambridge,
MA 02138, USA<EMAIL_ADDRESS>,  Anqi Li  Li: Department of Pure
Mathematics and Mathematical Statistics (Centre for Mathematical Sciences),
University of Cambridge, Cambridge CB30WB, England, UK<EMAIL_ADDRESS>and
Yufei Zhao  Zhao: Department of Mathematics, Massachusetts Institute of
Technology, Cambridge, MA 02139, USA<EMAIL_ADDRESS>
###### Abstract.

A system of linear equations $L$ is common over $\mathbb{F}_{p}$ if, as
$n\to\infty$, any 2-coloring of $\mathbb{F}_{p}^{n}$ gives asymptotically at
least as many monochromatic solutions to $L$ as a random 2-coloring.

The notion of common linear systems is analogous to that of common graphs,
i.e., graphs whose monochromatic density in 2-edge-coloring of cliques is
asymptotically minimized by the random coloring. Saad and Wolf initiated a
systematic study on identifying common linear systems, built upon the earlier
work of Cameron–Cilleruelo–Serra. When $L$ is a single equation, Fox–Pham–Zhao
gave a complete characterization of common linear equations. When $L$ consists
of two equations, Kamčev–Liebenau–Morrison showed that irredundant $2\times 4$
linear systems are always uncommon. In this work, (1) we determine commonness
of all $2\times 5$ linear systems up to a small number of cases, and (2) we
show that all $2\times k$ linear systems with $k$ even and girth (minimum
number of nonzero coefficients of a nonzero equation spanned by the system)
$k-1$ are uncommon, answering a question of Kamčev–Liebenau–Morrison.

Li was supported by the Trinity Studentship in Mathematics. Most of this work
was completed while Li was an undergraduate at MIT. Zhao was supported in part
by NSF CAREER Award DMS-2044606

##  1\. Introduction

One of the major open problems in extremal graph theory is _Sidorenko’s
conjecture_ [23], which roughly states that for bipartite graphs $H$, a random
graph $G$ on $n$ vertices asymptotically minimizes the density of $H$ in $G$
among all $G$ with $n$ vertices and fixed edge density. Sidorenko’s conjecture
has been verified for various classes of bipartite graphs $H$ (e.g. [5, 7, 8,
9, 10, 14, 18, 19, 22, 24] and the references therein), although a complete
proof of Sidorenko’s conjecture still eludes us. A closely related graph
property is the following coloring variant known as _commonness_ : a graph $H$
is _common_ if the random coloring minimizes the density of monochromatic
copies of $H$ in $K_{n}$ among all possible two-colorings of the edges of
$K_{n}$. An early result of Goodman [13] showed that $K_{3}$ is common.
Motivated by this result, Burr and Rosta [6] conjectured that all graphs $H$
are common, which was disproved by Sidorenko (who showed that a triangle with
a pendant edge is uncommon) and Thomason [25] (who showed that $K_{4}$ is
uncommon). In fact, any graph containing a $K_{4}$ is uncommon [15]. We do not
even have a good guess at what a complete characterization of common graphs
might look like.

In this paper, we are interested in an arithmetic analogue (over finite
fields) of this notion of commonness. To motivate the setup, we observe that
for a given set $A\subseteq\mathbb{F}_{p}^{n}$ satisfying $-A=A$, the additive
quadruples in $A$ (that is, $(x,y,z,w)\in A^{4}$ such that $x+y-z-w=0$)
correspond to 4-cycles in the Cayley graph on $A$ (that is, the graph with
vertex set indexed by $\mathbb{F}_{p}^{n}$ where $x\sim y$ if and only if
$x-y\in A$). As such, a natural arithmetic analogue of commonness would be to
ask for which linear equations in $\mathbb{F}_{p}$ is it true that the random
two-coloring of $\mathbb{F}_{p}^{n}$ minimizes the density of monochromatic
solutions to the linear equation. We can similarly define an arithmetic
analogue of Sidorenko’s conjecture. The study of such arithmetic analogues was
first posed by Saad and Wolf [21]. In this paper, we are interested in the
commonness of certain linear _systems_ of equations. Before we formalize this
setup, we begin by introducing some definitions.

######  Definition 1.1.

We say that $L$ is an $m\times k$ linear system if it is a collection of $m$
linear equations $L_{1},\dots,L_{m}$ on $k$ variables with integer
coefficients. In other words, $L$ is a collection of linear equations

$\displaystyle L_{1}\mathbf{x}$
$\displaystyle=a_{1,1}x_{1}+\dots+a_{1,k}x_{k},$ $\displaystyle\vdots$
$\displaystyle L_{m}\mathbf{x}$
$\displaystyle=a_{m,1}x_{1}+\dots+a_{m,k}x_{k},$

with $\\{a_{i,j}\in\mathbb{Z}:i\in[m],j\in[k]\\}$.

We note that there is a one-to-one correspondence between $m\times k$ linear
systems and matrices in $\mathbb{Z}^{m\times k}$; this means we can also
represent $L$ as the matrix

$\displaystyle L=\begin{pmatrix}a_{1,1}&a_{1,2}&\dots&a_{1,k}\\\
\vdots&\vdots&\ddots&\vdots\\\ a_{m,1}&a_{m,2}&\dots&a_{m,k}\\\
\end{pmatrix}\in\mathbb{Z}^{m\times k}.$

We say that an $m\times k$ linear system $L$ is _common over $\mathbb{F}_{p}$_
if for every 2-coloring of $\mathbb{F}_{p}^{n}$, the number of monochromatic
solutions $\mathbf{x}\in\mathbb{F}_{p}^{n}$ to $L\mathbf{x}=0$ is at least
$1-o(1)$ times the expected number of monochromatic solutions given by a
random 2-coloring, asymptotically as $n\to\infty$. Below, we will state an
equivalent definition as a precise inequality.

In the following, we restrict our attention to _irredundant linear systems_.
Roughly speaking, a system $L$ is irredundant if it does not have “repeated”
equations or variables.

######  Definition 1.2.

Let $L$ be a linear system. We say that $L$ is irredundant if:

  1. (1)

the rows of $L$ are linearly independent,

  2. (2)

no column of $L$ is the zero vector,

  3. (3)

the row span of $L$ does not contain vectors of the form
$(0,\dots,0,1,0,\dots,0,-1,0,\dots,0)$.

If $L$ is not irredundant, we say that it is _redundant_.

Such a restriction is without loss of generality: if $L$ is redundant, then by
removing extraneous equations and variables from $L$ we can obtain an
irredundant linear system $L^{\prime}$ such that $L$ is common if and only if
$L^{\prime}$ is common. Therefore, we restrict our attention to irredundant
linear systems for the rest of this paper (see also [16, Section 2] for a
discussion on this). By restricting our attention to irredundant linear
systems, we can also pass to a “functional” analogue of commonness which we
introduce next.

Earlier on, we defined the commonness property of a linear system $L$ in terms
of minimizing the number of monochromatic solutions to $L\mathbf{x}=0$ in a
2-coloring of $\mathbb{F}_{p}^{n}$. It turns out that there is a “functional”
variant of this definition which is more convenient for us to work with. This
is the version of the definition of common and Sidorenko systems that we now
state. We refer the interested reader to [12, Section 2] for a proof of the
equivalence of the functional and set definitions of the properties of being
common and Sidorenko.

######  Definition 1.3.

Let $L$ be an irredundant $m\times k$ linear system and $p$ be prime. For
every $n\in\mathbb{N}$ and $f:\mathbb{F}_{p}^{n}\to\mathbb{R}$, define the
density function

$t_{L}(f)=\mathbb{E}_{\mathbf{x}\in\mathbb{F}_{p}^{n}:L\mathbf{x}=0}f(x_{1})\cdots
f(x_{k}).$

  1. (1)

We say that $L$ is _common_ over $\mathbb{F}_{p}$ if for all $n\in\mathbb{N}$
and $f\colon\mathbb{F}_{p}^{n}\to[0,1]$, we have

$t_{L}(f)+t_{L}(1-f)\geq 2^{1-k}.$

If this does not hold, then we say that $L$ is _uncommon_ over
$\mathbb{F}_{p}$.

  2. (2)

We say that $L$ is _Sidorenko_ over $\mathbb{F}_{p}$ if for all
$n\in\mathbb{N}$ and $f\colon\mathbb{F}_{p}^{n}\to[0,1]$, we have

$t_{L}(f)\geq(\mathbb{E}f)^{k}.$

######  Remark 1.4.

If $L$ is Sidorenko over $\mathbb{F}_{p}$, then it is common over
$\mathbb{F}_{p}$. Indeed, if $L$ is Sidorenko, then
$t_{L}(f)+t_{L}(1-f)\geq(\mathbb{E}f)^{k}+(1-\mathbb{E}f)^{k}\geq 2^{-k+1}$ by
convexity.

Several recent works address the question of characterizing common and
Sidorenko linear systems. When $L$ is itself a single linear equation (i.e.,
$m=1$), the length of $L$ is defined to be the number of its nonzero
coefficients. Fox, Pham and Zhao [12] showed that a linear equation $L$ is
Sidorenko if and only if its coefficients can be partitioned into cancelling
pairs; furthermore, it is common and not Sidorenko if and only if it has odd
length. Their results give a complete characterziation of common and Sidorenko
linear equations.

No complete characterization is known for linear systems of higher rank. Some
partial results in this direction include the following: Versteegen [26]
proved that 4-AP is uncommon – this establishes the arithmetic analogue of
Thomason’s result on the uncommonness of $K_{4}$. Kamčev, Liebenau and
Morrison proved that if a linear system consists of Sidorenko linear equations
aligned in a “tree template”, then it is Sidorenko [17]; they also proved that
any linear system that has an irredundant $2\times 4$ subsystem is uncommon
[16]. Altman [1] explored the notion of local Sidorenko property and showed
that any linear system of two equations, with every $2\times 2$ minor
invertible, is not Sidorenko. On the other hand, Altman [2] also established
that there is a non-Sidorenko linear system that becomes common after adding
sufficiently many free variables, answering a question of [21].

In this paper, we determine commonness of all $2\times 5$ linear systems up to
a small number of cases. As a byproduct, we answer [17, Question 5.2] by
constructing an uncommon $2\times 5$ linear system that contains an additive
quadruple. We also prove [16, Conjecture 6.1] that all $2\times k$ linear
systems, with $k$ even and “girth” (which we define in Definition 1.7) $k-1$,
are uncommon over $\mathbb{F}_{p}$ for all sufficiently large $p$. Before we
formally state our results, we need to introduce some definitions.

######  Definition 1.5.

Let $L$ be an $m\times k$ linear system on variables $x_{1},\dots,x_{k}$, and
$L^{\prime}$ be an $m^{\prime}\times k^{\prime}$ linear system on a subset of
the variables $x_{i_{1}},\dots,x_{i_{k^{\prime}}}$. Write
$\mathbf{x}=(x_{1},\dots,x_{k})$ and
$\mathbf{x}^{\prime}=(x_{i_{1}},\dots,x_{i_{k^{\prime}}})$.

  1. (1)

We say that $L^{\prime}$ is a subsystem of $L$ if $L\mathbf{x}=0$ implies
$L^{\prime}\mathbf{x}^{\prime}=0$.

  2. (2)

Suppose $k^{\prime}=k$ (so $\mathbf{x}^{\prime}=\mathbf{x}$). We say that $L$
and $L^{\prime}$ are isomorphic if we can permute the columns of $L^{\prime}$
so that the obtained matrix has the same row span as that of $L$.

######  Example 1.6.

The four-term arithmetic progression

$\displaystyle L^{\prime}(x_{1},x_{2},x_{3},x_{4})=\begin{pmatrix}1&-2&1&0\\\
0&1&-2&1\end{pmatrix}$

is a subsystem of the five-term arithmetic progression

$\displaystyle L(x_{1},x_{2},x_{3},x_{4},x_{5})=\begin{pmatrix}1&-2&1&0&0\\\
0&1&-2&1&0\\\ 0&0&1&-2&1\end{pmatrix}.$

Finally, we recall that a graph with odd girth is not Sidorenko (see for
instance [11, Theorem 3.1]). In [17], the authors defined a natural notion of
_girth_ for linear systems and proved a parallel result that a linear system
with odd girth is not Sidorenko. We next give the definition of _girth_ for a
linear system.

######  Definition 1.7.

Let $L\in\mathbb{Z}^{m\times k}$ be an $m\times k$ linear system. The girth of
$L$, denoted as $s(L)$, is the minimum possible size of the support of a
nonzero vector in the row span of $L$.

We are now ready to formally state our main results. While odd girth was
enough to guarantee that a linear system $L$ is not Sidorenko, we cannot
expect it alone to give the stronger conclusion that $L$ is uncommon: we have
seen earlier that single, odd-length equations are common. But what if we
restrict our attention to systems of at least two equations? Would we be able
to deduce the uncommonness of such a system from its girth? Our first result
gives a partial answer to this question and shows that all two-equation linear
systems with even number of variables and maximum girth are uncommon.

######  Theorem 1.8.

Suppose $k\geq 4$ is even. Let $L$ be an irredundant $2\times k$ system with
$s(L)=k-1$. Then there exists $p_{L}$ such that $L$ is uncommon over
$\mathbb{F}_{p}$ for all $p\geq p_{L}$.

By combining the proof strategy of Theorem 1.8 and some additional ideas from
[16] and [1], we obtain the following more general result, which is also a
generalization of [16, Corollary 1.2].

######  Theorem 1.9.

Suppose $k\geq 4$ is even. Let $L$ be a linear system, with $s(L)=k-1$, that
has an irredundant $2\times k$ subsystem. Then there exists $p_{L}$ such that
$L$ is uncommon over $\mathbb{F}_{p}$ for all $p\geq p_{L}$.

Next, one can ask about the commonness of $2\times k$ linear systems for $k$
odd. This turns out to be much more subtle than the $k$ even case; even for
$k=5$, there are common $2\times 5$ linear systems with $s(L)=3$ and $s(L)=4$.
In fact, for each $2\times 5$ linear system that is not one of the two unknown
cases, we are able to determine whether it is common over $\mathbb{F}_{p}$ for
all $p$, or it is uncommon over $\mathbb{F}_{p}$ for all sufficiently large
$p$.

######  Theorem 1.10.

Let $L$ be an irredundant $2\times 5$ linear system that is not isomorphic to

$\displaystyle\begin{pmatrix}1&1&-1&-1&0\\\
1&-1&3&0&-3\end{pmatrix}\quad\text{or}\quad\begin{pmatrix}1&1&-1&-1&0\\\
2&-2&3&0&-3\end{pmatrix}.$

  1. (1)

If $L$ is isomorphic to

$\begin{pmatrix}1&0&-1&2&-2\\\ 0&1&2&-1&-2\end{pmatrix}$

or

$\begin{pmatrix}1&-1&1&-1&0\\\ 1&2&-1&0&-2\end{pmatrix}$

or

$\begin{pmatrix}1&1&-1&-1&0\\\ 2&-2&1&0&-1\end{pmatrix}$

or

$\displaystyle\begin{pmatrix}a&b&0&0&c\\\
0&0&a&b&c\end{pmatrix}\qquad\text{with $a,b,c\in\mathbb{Z}\setminus\\{0\\}$}$

or

$\displaystyle\begin{pmatrix}c&-c&d&-d&0\\\
a&b&0&0&-a-b\end{pmatrix}\quad\text{with
$a,b,a+b,c,d\in\mathbb{Z}\setminus\\{0\\}$}$ $\displaystyle\quad\text{such
that }\\{|a/b|,|a/(a+b)|,|b/(a+b)|\\}\cap\\{|c/d|,|d/c|\\}\neq\emptyset,$

then $L$ is common over $\mathbb{F}_{p}$ for all primes $p$.

  2. (2)

If $L$ is not isomorphic to any of the above, then there exists $p_{L}$ such
that $L$ is uncommon over $\mathbb{F}_{p}$ for all $p\geq p_{L}$.

The proofs of uncommonness in Theorem 1.8, Theorem 1.9 and Theorem 1.10
utilize suitably designed _Fourier templates_ which we introduce in Section 3;
these Fourier templates can be thought of as functions with suitably chosen
Fourier coefficients that certificate uncommonness over $\mathbb{F}_{p}$ for
sufficiently large $p$. We are unable to construct a suitable Fourier template
for the two unknown cases in Theorem 1.10, although we believe that our main
constraints are essentially computational barriers which limit the size of the
support of the Fourier templates we are able to consider. It is also plausible
that the systems are actually common, although we are also unable to prove
that.

######  Question 1.11.

Are the two systems not covered by Theorem 1.10 common or uncommon?

There also remains the interesting question of classifying $2\times k$ systems
for $k$ odd and $k\geq 7$, and it is natural to ask if there is a general way
to do this classification for all odd $k$ at once.

######  Question 1.12.

What is the classification of the commonness of $2\times k$ systems for $k\geq
7$ odd?

#####  Outline.

In Section 2, we introduce the Fourier analytic approach to solve problems on
identifying common and Sidorenko linear systems. In Section 3, we define the
notion of a Fourier template and demonstrate its utility by proving (Theorem
3.5) that if we can find an appropriate Fourier template corresponding to a
given linear system $L$, then $L$ is uncommon over all $\mathbb{F}_{p}$ for
sufficiently large $p$. Next, we prove Theorem 1.8 and Theorem 1.9 in Section
4 and Theorem 1.10 in Sections 5 and 6. We begin each of Sections 4 (Section
4.1) and 5 (Section 5.1) with some examples to illustrate the key proof ideas
behind our construction of the relevant Fourier templates.

#####  Acknowledgements.

We thank Yunkun Zhou for providing the proof that the linear system

$\begin{pmatrix}1&1&-1&-1&0\\\ 2&-2&1&0&-1\end{pmatrix}$

is common. We thank Dylan Toh for suggesting the greatly simplified proof of
5.18. We thank Pablo Parrilo for providing suggestions and help on symmetry-
adapted semi-definite programs. We also thank Nitya Mani and Mark
Saengrungkongka for helpful discussions.

##  2\. Preliminaries

###  2.1. Fourier analytic approach

In this section, we discuss the Fourier analytic approach for identifying
common and Sidorenko linear systems. Let $\widehat{\mathbb{F}_{p}^{n}}$ denote
the set of homomorphisms from $\mathbb{F}_{p}^{n}\to\mathbb{C}^{\times}$.
Since every element in $\widehat{\mathbb{F}_{p}^{n}}$ is of the form $x\mapsto
e^{2\pi ir\cdot x/p}$, we have an isomorphism between $\mathbb{F}_{p}^{n}$ and
$\widehat{\mathbb{F}_{p}^{n}}$. For a function
$f:\mathbb{F}_{p}^{n}\to\mathbb{R}$, the Fourier transform of $f$ is the
function $\widehat{f}:\widehat{\mathbb{F}_{p}^{n}}\to\mathbb{C}$ defined by

$\widehat{f}(r)=\mathbb{E}_{x\in\mathbb{F}_{p}^{n}}f(x)\overline{r(x)}$

with inverse Fourier transform

$f(x)=\sum_{r\in\widehat{\mathbb{F}_{p}^{n}}}\widehat{f}(r)r(x).$

Thus, we can rewrite the density function $t_{L}(f)$ as

$\displaystyle t_{L}(f)$
$\displaystyle=\mathbb{E}_{L\mathbf{x}=0}\sum_{r_{1},\dots,r_{k}\in\widehat{\mathbb{F}_{p}^{n}}}\widehat{f}(r_{1})\cdots\widehat{f}(r_{k})r_{1}(x_{1})\cdots
r_{k}(x_{k})$
$\displaystyle=\sum_{r_{1},\dots,r_{k}\in\widehat{\mathbb{F}_{p}^{n}}}\widehat{f}(r_{1})\cdots\widehat{f}(r_{k})\mathbb{E}_{L\mathbf{x}=0}r_{1}(x_{1})\cdots
r_{k}(x_{k}).$

Now observe that $\mathbb{E}_{L\mathbf{x}=0}r_{1}(x_{1})\cdots
r_{k}(x_{k})=\mathbb{E}_{L\mathbf{x}=0}(e^{2\pi i/p})^{r_{1}\cdot
x_{1}+\dots+r_{k}\cdot x_{k}}$ equals 1 if $(r_{1},\dots,r_{k})$ is a linear
combination of the row vectors of $L$ , and equals 0 otherwise. Let
$\vec{\ell}_{1},\dots,\vec{\ell}_{m}\in\mathbb{Z}^{k}$ be the row vectors of
$L$ and $\vec{a}_{1},\dots,\vec{a}_{k}\in\mathbb{Z}^{m}$ the column vectors of
$L$. We know that

$\text{span}(\vec{\ell}_{1},\dots,\vec{\ell}_{m})=\\{(\vec{a}_{1}\cdot
r,\dots,\vec{a}_{k}\cdot r):r\in(\widehat{\mathbb{F}_{p}^{n}})^{m}\\}.$

Hence we have

$\displaystyle t_{L}(f)$
$\displaystyle=\sum_{r\in(\widehat{\mathbb{F}_{p}^{n}})^{m}}\widehat{f}(\vec{a}_{1}\cdot
r)\cdots\widehat{f}(\vec{a}_{k}\cdot r).$ (1)

In particular, when $L$ itself is a linear equation
$L\mathbf{x}=a_{1}x_{1}+\dots+a_{k}x_{k}$, we can rewrite the density function
$t_{L}(f)$ as

$\displaystyle
t_{L}(f)=\sum_{r\in\widehat{\mathbb{F}_{p}^{n}}}\widehat{f}(a_{1}r)\cdots\widehat{f}(a_{k}r).$
(2)

###  2.2. Reduction to critical sets

In this section, we define critical sets of a linear system and then introduce
a reductive step in [16] that will be useful in our proof. The following two
definitions can be found in [16, Section 2.2].

######  Definition 2.1.

For every linear system $L$ with girth $s(L)$, define

$c(L)=\begin{cases}s(L)&s(L)\text{ even}\\\ s(L)+1&s(L)\text{
odd}.\end{cases}$

We say that $B\subseteq[k]$ is a critical set of $L$ if

  1. (1)

$|B|=c(L)$, and

  2. (2)

$L$ has a nonempty subsystem $L^{\prime}$ whose variable set is $\\{x_{i}:i\in
B\\}$.

Let $\mathcal{C}(L)$ denote the collection of critical sets of $L$.

######  Definition 2.2.

Let $L$ be a linear system and $B\subseteq[k]$ be a criticial set of $L$.

  1. (1)

Define

$\displaystyle m_{B}=\max\\{m^{\prime}:$ $\displaystyle\text{ $L$ has an
$m^{\prime}\times c(L)$ subsystem on variable set $\\{x_{i}:i\in B\\}$}\\}.$

  2. (2)

Define $L_{B}$ to be the (unique up to isomorphism) $m_{B}\times c(L)$
subsystem of $L$ on variable set $\\{x_{i}:i\in B\\}$.

The proof of the uniqueness of $L_{B}$ is standard linear algebra, and we
refer the readers to [16, Lemma 2.4].

######  Remark 2.3.

Since no equation of length $<s(L)$ can be a subsystem of $L$, we have the
following:

  * •

When $s(L)$ is even (so $c(L)=s(L)$), every $B\in\mathcal{C}(L)$ has
$m_{B}=1$, and $L_{B}$ must be a length-$c(L)$ equation.

  * •

When $s(L)$ is odd (so $c(L)=s(L)+1$), every $B\in\mathcal{C}(L)$ has
$m_{B}\in\\{1,2\\}$, and $L_{B}$ is either a length-$c(L)$ equation or a
$2\times c(L)$ linear system with girth $s(L)$.

One of the results in [16] states that to conclude a linear system $L$ is
uncommon, it sometimes suffices to study the collection
$\\{L_{B}:B\in\mathcal{C}(L)\\}$.

######  Proposition 2.4 ([16, Theorem 3.1]).

Let $L$ be an $m\times k$ linear system. If there exists
$f:\mathbb{F}_{p}^{n}\to\mathbb{R}$ such that $\mathbb{E}f=0$ and

$\sum_{B\in\mathcal{C}(L)}t_{L_{B}}(f)<0,$

then $L$ is uncommon over $\mathbb{F}_{p}$.

###### Proof.

Consider any $h:\mathbb{F}_{p}^{n}\to[0,1]$ with $\mathbb{E}h=1/2$, and define
$f=h-1/2:\mathbb{F}_{p}^{n}\to[-1/2,1/2]$. Expanding each term, one can check
that

$\displaystyle t_{L}(h)+t_{L}(1-h)$
$\displaystyle=\mathbb{E}_{L\mathbf{x}=0}(1/2+f(x_{1}))\cdots(1/2+f(x_{k}))+\mathbb{E}_{L\mathbf{x}=0}(1/2-f(x_{1}))\cdots(1/2-f(x_{k}))$
$\displaystyle=2^{1-k}+2\sum_{\begin{subarray}{c}\emptyset\neq
B\subseteq[k]\\\ |B|\text{
even}\end{subarray}}2^{|B|-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}f(x_{i})\right]$
$\displaystyle=2^{1-k}+2\sum_{\begin{subarray}{c}B\subseteq[k]\\\ |B|\geq
c(L)\text{
even}\end{subarray}}2^{|B|-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}f(x_{i})\right],$

where the last equality follows from the fact that $\mathbb{E}f=0$, and $L$
does not have nonempty subsystems on at most $c(L)-2$ variables. Thus, if
there is some $f:\mathbb{F}_{p}^{n}\to[-1/2,1/2]$ such that $\mathbb{E}f=0$
and

$\displaystyle\sum_{\begin{subarray}{c}B\subseteq[k]\\\ |B|\geq c(L)\text{
even}\end{subarray}}2^{|B|-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}f(x_{i})\right]<0,$

then by Definition 1.3, $L$ is uncommon over $\mathbb{F}_{p}$.

Observe that

$\displaystyle\sum_{\begin{subarray}{c}B\subseteq[k]\\\ |B|\geq c(L)\text{
even}\end{subarray}}2^{|B|-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}f(x_{i})\right]$
$\displaystyle=\sum_{B\in\mathcal{C}(L)}2^{c(L)-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}f(x_{i})\right]+\sum_{\begin{subarray}{c}B\subseteq[k]\\\ |B|\geq
c(L)+2\text{
even}\end{subarray}}2^{|B|-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}f(x_{i})\right].$

Consider any critical set $B\in\mathcal{C}(L)$ and its corresponding subsystem
$L_{B}$. A linear algebra calculation (see also [16, Lemma 2.6]) shows that
every solution to $L_{B}$ extends to the same number of solutions to $L$. That
is, for every solution $\mathbf{x}^{\prime}$ to $L_{B}\mathbf{x}^{\prime}=0$,
there are $(p^{n})^{k-m-c(L)+m_{B}}$ solutions $\mathbf{x}$ to $L\mathbf{x}=0$
such that $\mathbf{x}$ restricted on the variables $\\{x_{i}:i\in B\\}$ equals
$\mathbf{x}^{\prime}$. Thus we get that

$\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}f(x_{i})\right]=\mathbb{E}_{L_{B}\mathbf{x}^{\prime}=0}\left[\prod_{i\in
B}f(x_{i})\right]=t_{L_{B}}(f).$

Suppose there exists $\widetilde{f}:\mathbb{F}_{p}^{n}\to\mathbb{R}$ with
$\mathbb{E}\widetilde{f}=0$ and
$\sum_{B\in\mathcal{C}(L)}t_{L_{B}}(\widetilde{f})<0$. Taking
$f=\epsilon\widetilde{f}$ with $\epsilon>0$ sufficiently small, we can obtain
$f:\mathbb{F}_{p}^{n}\to[-1/2,1/2]$ with

$\displaystyle\sum_{B\in\mathcal{C}(L)}2^{c(L)-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}\epsilon\widetilde{f}(x_{i})\right]+\sum_{\begin{subarray}{c}B\subseteq[k]\\\
|B|\geq c(L)+2\text{
even}\end{subarray}}2^{|B|-k}\mathbb{E}_{L\mathbf{x}=0}\left[\prod_{i\in
B}\epsilon\widetilde{f}(x_{i})\right]$
$\displaystyle=2^{c(L)-k}\epsilon^{c(L)}\sum_{B\in\mathcal{C}(L)}t_{L_{B}}(\widetilde{f})+O(\epsilon^{c(L)+2}),$

which is negative. Hence $L$ is uncommon over $\mathbb{F}_{p}$. ∎

##  3\. Fourier template

As discussed in Section 2, for linear system $L$ and function
$f:\mathbb{F}_{p}\to\mathbb{R}$, we can write the solution density $t_{L}(f)$
in terms of the Fourier coefficients of $f$. In order to construct a function
$f$ that certifies uncommonness, it is often fruitful to view the problem in
the Fourier space and construct a suitable
$\widehat{f}\colon\widehat{\mathbb{F}_{p}}\to\mathbb{C}$. We will introduce a
notion of a _Fourier template_ which can then be turned into some
$\widehat{f}\colon\widehat{\mathbb{F}_{p}}\to\mathbb{C}$ for all sufficiently
large $p$.

######  Example 3.1.

As an example, to show that the linear equation

$L\mathbf{x}=x_{1}+2x_{2}+3x_{3}+4x_{4}$

is uncommon over $\mathbb{F}_{p}$, we can consider the function
$f:\mathbb{F}_{p}\to\mathbb{R}$ defined by

$\displaystyle\begin{cases}\widehat{f}(1)=\widehat{f}(-1)=-1\\\
\widehat{f}(2)=\widehat{f}(-2)=\widehat{f}(3)=\widehat{f}(-3)=\widehat{f}(4)=\widehat{f}(-4)=1\\\
\widehat{f}(r)=0\qquad\text{otherwise.}\end{cases}$

Notice that $\mathbb{E}f=\widehat{f}(0)=0$. Moreover, for all sufficiently
large $p$, we have

$\displaystyle
t_{L}(f)=\sum_{r\in\widehat{\mathbb{F}_{p}}}\widehat{f}(r)\widehat{f}(2r)\widehat{f}(3r)\widehat{f}(4r)=\widehat{f}(1)\widehat{f}(2)\widehat{f}(3)\widehat{f}(4)+\widehat{f}(-1)\widehat{f}(-2)\widehat{f}(-3)\widehat{f}(-4)=-2<0.$

By taking $\epsilon>0$ sufficiently small such that $\epsilon
f:\mathbb{F}_{p}\to[-1/2,1/2]$ and letting $h=1/2+\epsilon f$, we can obtain a
function $h:\mathbb{F}_{p}\to[0,1]$ such that

$\displaystyle t_{L}(h)+t_{L}(1-h)$
$\displaystyle=\mathbb{E}_{L\mathbf{x}=0}[(1/2+\epsilon
f(x_{1}))\cdots(1/2+\epsilon
f(x_{4}))]+\mathbb{E}_{L\mathbf{x}=0}[(1/2-\epsilon
f(x_{4}))\cdots(1/2-\epsilon f(x_{4}))]$
$\displaystyle=1/8+2\epsilon^{4}\mathbb{E}_{L\mathbf{x}=0}[f(x_{1})\cdots
f(x_{4})]=1/8+2\epsilon^{4}t_{L}(f)<1/8.$

Therefore, $L$ is uncommon over $\mathbb{F}_{p}$ for all sufficiently large
$p$.

The key step in Example 3.1 is to construct an appropriate Fourier transform
$\widehat{f}:\widehat{\mathbb{F}_{p}}\to\mathbb{C}$ such that $t_{L}(f)<0$.
Since $\widehat{f}$ has finite support, this construction works for all
sufficiently large $p$. What we essentially did is creating a finitely
supported map $g:\mathbb{Z}\to\mathbb{C}$ from the integers, defined by $\pm
1\mapsto-1$ and $\pm 2,\pm 3,\pm 4\mapsto 1$, such that the Fourier transform
$\widehat{f}=g$ (which is well-defined for all sufficiently large $p$) gives
us a function $f$ that helps certify uncommonness. This map
$g:\mathbb{Z}\to\mathbb{C}$ is what we call a 1-dimensional Fourier template.

We now formally introduce the definition of Fourier templates.

######  Definition 3.2.

For every $m\times k$ linear system $L$ and $d\in\mathbb{N}$, we say that
$g:\mathbb{Z}^{d}\to\mathbb{C}$ is a $d$-dimensional Fourier template if the
following holds:

  * •

$g$ has finite support,

  * •

$g(-r)=\overline{g(r)}$ for all $r\in\mathbb{Z}^{d}$,

  * •

$g(0)=0$.

######  Definition 3.3.

Let $g:\mathbb{Z}^{d}\to\mathbb{C}$ be a $d$-dimensional Fourier template, and

$L=\begin{pmatrix}\vec{a}_{1}&\vec{a}_{2}&\cdots&\vec{a}_{k}\end{pmatrix}=\begin{pmatrix}a_{1,1}&a_{1,2}&\dots&a_{1,k}\\\
\vdots&\vdots&\ddots&\vdots\\\ a_{m,1}&a_{m,2}&\dots&a_{m,k}\\\
\end{pmatrix}\in\mathbb{Z}^{m\times k}$

be an $m\times k$ linear system. (Here
$\vec{a}_{1},\dots,\vec{a}_{k}\in\mathbb{Z}^{m}$ are the columns of $L$.)

  1. (1)

Define the associated function $g_{L}:\mathbb{Z}^{d\times m}\to\mathbb{C}$ by

$g_{L}(R)=g(R\vec{a}_{1})\cdots
g(R\vec{a}_{k})=\prod_{i=1}^{k}g(R\vec{a}_{i}).$

  2. (2)

Define $\sigma_{L}(g)=\sum_{R\in\mathbb{Z}^{d\times m}}g_{L}(R)$.

######  Remark 3.4.

Notice that $\sigma_{L}(g)$ is well-defined as $g$ has finite support.
Moreover, since

$\sigma_{L}(g)=\sum_{R\in\mathbb{Z}^{d\times
m}}g_{L}(R)=\sum_{R\in\mathbb{Z}^{d\times
m}}g_{L}(-R)=\sum_{R\in\mathbb{Z}^{d\times
m}}\overline{g_{L}(R)}=\overline{\sigma_{L}(g)},$

we always have $\sigma_{L}(g)\in\mathbb{R}$.

We now state and prove the main theorem of this section.

######  Theorem 3.5.

Let $L$ be an $m\times k$ linear system. If there exists a $d$-dimensional
Fourier template $g:\mathbb{Z}^{d}\to\mathbb{C}$ such that

$\sum_{B\in\mathcal{C}(L)}\sigma_{L_{B}}(g)<0,$

then $L$ is uncommon over $\mathbb{F}_{p}$ for all sufficiently large $p$.

When $d=1$, the proof of Theorem 3.5 essentially goes as Example 3.1. When
$d>1$, the main idea is to construct an appropriate Freiman homormophism
$\gamma:\mathbb{Z}^{d}\to\mathbb{Z}$ that projects $\mathbb{Z}^{d}$ onto a
generalized arithmetic progression in $\mathbb{Z}$. We will then build the
certificate $f:\mathbb{F}_{p}\to\mathbb{C}$ by setting
$\widehat{f}(r)=g(\gamma^{-1}(r))$ for all
$r\in\text{im}\gamma\subseteq\widehat{\mathbb{F}_{p}}$.

###### Proof.

Consider any critical set $B\in\mathcal{C}(L)$. Suppose

$L_{B}=\begin{pmatrix}\vec{a}_{1}&\cdots&\vec{a}_{k^{\prime}}\end{pmatrix}=\begin{pmatrix}a_{1,1}x_{1}&\dots&a_{1,k^{\prime}}x_{k^{\prime}}\\\
\vdots&\ddots&\vdots\\\
a_{m^{\prime},1}x_{1}&\dots&a_{m^{\prime},k^{\prime}}x_{k^{\prime}}\end{pmatrix}\in\mathbb{Z}^{m^{\prime}\times
k^{\prime}},$

so that $\vec{a}_{1},\dots,\vec{a}_{k^{\prime}}\in\mathbb{Z}^{m^{\prime}}$ are
the column vectors of $L_{B}$. Recall from Remark 2.3 that we have
$m^{\prime}\in\\{1,2\\}$ and $k^{\prime}=c(L)$.

Pick matrix $Q_{B}\in\mathbb{Z}^{(k^{\prime}-m^{\prime})\times k^{\prime}}$ so
that the rows of $L_{B}$ span the kernel of $Q_{B}$. Then for
$f:\mathbb{F}_{p}\to\mathbb{R}$, we have (recall 1)

$\displaystyle t_{L_{B}}(f)$
$\displaystyle=\sum_{r\in(\widehat{\mathbb{F}_{p}})^{m^{\prime}}}\widehat{f}(\vec{a}_{1}\cdot
r)\cdots\widehat{f}(\vec{a}_{k^{\prime}}\cdot
r)=\sum_{\begin{subarray}{c}\vec{v}\in(\widehat{\mathbb{F}_{p}})^{k^{\prime}}\\\
Q_{B}\vec{v}=0\end{subarray}}\widehat{f}(v_{1})\cdots\widehat{f}(v_{k^{\prime}}).$
(3)

For $M\in\mathbb{N}$, let $[\\![-M,M]\\!]$ denote the subset
$\\{-M,\dots,-1,0,1,\dots,M\\}\subseteq\mathbb{Z}$. Suppose the Fourier
template $g:\mathbb{Z}^{d}\to\mathbb{C}$ vanishes outside
$[\\![-M,M]\\!]^{d}$. Observe that, for $C\in\mathbb{N}$ sufficiently large,
the projection $\gamma:[\\![-M,M]\\!]^{d}\to\mathbb{Z}$ defined by

$\gamma(w_{0},\dots,w_{d-1})=w_{0}+w_{1}C+\dots+w_{d-1}C^{d-1}$

is injective. Moreover, the inverse
$\phi:=\gamma^{-1}:\text{im}\gamma\to[\\![-M,M]\\!]^{d}$ satisfies the
following property: for all $B\in\mathcal{C}(L)$ and
$\vec{v}\in(\text{im}\gamma)^{k^{\prime}}$, we have
$Q_{B}\vec{v}=0\in\mathbb{Z}^{k^{\prime}-m^{\prime}}$ if and only if
$Q_{B}\phi(\vec{v})=0\in\mathbb{Z}^{(k^{\prime}-m^{\prime})\times d}$, where

$\displaystyle\phi(\vec{v})=\begin{pmatrix}\phi(v_{1})\\\ \vdots\\\
\phi(v_{k^{\prime}})\end{pmatrix}\in\mathbb{Z}^{k^{\prime}\times d}.$

Suppose $p$ is sufficiently large. Construct $f:\mathbb{F}_{p}\to\mathbb{R}$
as follows:

  * •

For all $-p/2<r<p/2$ with $r\in\text{im}\gamma$, set $\widehat{f}(r)=g(\phi
r)$.

  * •

Otherwise, set $\widehat{f}(r)=0$.

By 3, we have

$\displaystyle t_{L_{B}}(f)$
$\displaystyle=\sum_{\begin{subarray}{c}v\in(\widehat{\mathbb{F}_{p}})^{k^{\prime}}\\\
Q_{B}\vec{v}=0\end{subarray}}\widehat{f}(v_{1})\cdots\widehat{f}(v_{k^{\prime}})=\sum_{\begin{subarray}{c}v\in(\widehat{\mathbb{F}_{p}})^{k^{\prime}}\\\
Q_{B}\phi(\vec{v})=0\end{subarray}}\widehat{f}(v_{1})\cdots\widehat{f}(v_{k^{\prime}})=\sum_{\begin{subarray}{c}U\in\mathbb{Z}^{k^{\prime}\times
d}\\\ Q_{B}U=0\end{subarray}}g(U_{1})\cdots g(U_{k^{\prime}}),$

where $U_{1},\dots,U_{k^{\prime}}\in\mathbb{Z}^{d}$ are the row vectors for
each $U\in\mathbb{Z}^{k^{\prime}\times d}$. Since $Q_{B}U=0$ if and only if

$\displaystyle U=\begin{pmatrix}\vec{a}_{1}\cdot r_{1}&\dots&\vec{a}_{1}\cdot
r_{d}\\\ \vdots&\ddots&\vdots\\\ \vec{a}_{k^{\prime}}\cdot
r_{1}&\dots&\vec{a}_{k^{\prime}}\cdot r_{d}\end{pmatrix}\text{ for
}r_{1},\dots,r_{d}\in\mathbb{Z}^{m^{\prime}},$

we get that

$\displaystyle t_{L_{B}}(f)$
$\displaystyle=\sum_{\begin{subarray}{c}r_{1},\dots,r_{d}\in\mathbb{Z}^{m^{\prime}}\end{subarray}}g(\vec{a}_{1}\cdot
r_{1},\dots,\vec{a}_{1}\cdot r_{d})\cdots g(\vec{a}_{k^{\prime}}\cdot
r_{1},\dots,\vec{a}_{k^{\prime}}\cdot r_{d})$
$\displaystyle=\sum_{R\in\mathbb{Z}^{d\times m^{\prime}}}g(R\vec{a}_{1})\cdots
g(R\vec{a}_{k^{\prime}})=\sigma_{L_{B}}(g).$

Therefore, if $\sum_{B\in\mathcal{C}(L)}\sigma_{L_{B}}(g)<0,$ then we have

$\sum_{B\in\mathcal{C}(L)}t_{L_{B}}(f)=\sum_{B\in\mathcal{C}(L)}\sigma_{L_{B}}(g)<0$

for all sufficiently large $p$. By Proposition 2.4, $L$ is uncommon over
$\mathbb{F}_{p}$. ∎

Finally, we remark that we can join two Fourier templates $g,\widetilde{g}$ to
form a new Fourier template $h$. Moreover, the joined Fourier template
satisfies $\sigma_{L}(h)=\sigma_{L}(g)\sigma_{L}(\widetilde{g})$.

######  Proposition 3.6.

Let $g:\mathbb{Z}^{d_{1}}\to\mathbb{C}$,
$\widetilde{g}:\mathbb{Z}^{d_{1}}\to\mathbb{C}$ be two Fourier templates.
Define the map $h:\mathbb{Z}^{d_{1}+d_{2}}\to\mathbb{C}$ by

$h(r_{1},r_{2})=g(r_{1})\widetilde{g}(r_{2})\qquad\text{for all
$r_{1}\in\mathbb{Z}^{d_{1}}$, $r_{2}\in\mathbb{Z}^{d_{2}}$.}$

Then $h$ is a $(d_{1}+d_{2})$-dimensional Fourier template. Moreover, for
every linear system $L$, we have

$\sigma_{L}(h)=\sigma_{L}(g)\sigma_{L}(\widetilde{g}).$

###### Proof.

One can check directly from Definition 3.2 that $h$ is a
$(d_{1}+d_{2})$-dimensional Fourier template. Let

$L=\begin{pmatrix}\vec{a}_{1}&\dots&\vec{a}_{k}\end{pmatrix}\in\mathbb{Z}^{m\times
k}$

be an $m\times k$ linear system. For matrix
$R\in\mathbb{Z}^{(d_{1}+d_{2})\times m}$, write

$R=\begin{pmatrix}R_{1}\\\ R_{2}\end{pmatrix}$

where $R_{1}\in\mathbb{Z}^{d_{1}\times m}$ and
$R_{2}\in\mathbb{Z}^{d_{2}\times m}$. We then have
$R\vec{a}_{i}=(R_{1}\vec{a}_{i},R_{2}\vec{a}_{i})$ and
$h(R\vec{a}_{i})=g(R_{1}\vec{a}_{i})\widetilde{g}(R_{2}\vec{a}_{i})$ for every
$i\in[k]$, which gives

$\displaystyle\sigma_{L}(h)$
$\displaystyle=\sum_{R\in\mathbb{Z}^{(d_{1}+d_{2})\times
m}}h_{L}(R)=\sum_{R\in\mathbb{Z}^{(d_{1}+d_{2})\times m}}h(R\vec{a}_{1})\cdots
h(R\vec{a}_{k})$ $\displaystyle=\sum_{R_{1}\in\mathbb{Z}^{d_{1}\times
m}}\sum_{R_{2}\in\mathbb{Z}^{d_{2}\times m}}g(R_{1}\vec{a}_{1})\cdots
g(R_{1}\vec{a}_{k})\widetilde{g}(R_{2}\vec{a}_{1})\cdots\widetilde{g}(R_{2}\vec{a}_{k})$
$\displaystyle=\sum_{R_{1}\in\mathbb{Z}^{d_{1}\times
m}}g(R_{1}\vec{a}_{1})\cdots
g(R_{1}\vec{a}_{k})\sum_{R_{2}\in\mathbb{Z}^{d_{2}\times
m}}\widetilde{g}(R_{2}\vec{a}_{1})\cdots\widetilde{g}(R_{2}\vec{a}_{k})=\sigma_{L}(g)\sigma_{L}(\widetilde{g}).$

∎

##  4\. Proof of Theorem 1.8

###  4.1. Introduction

In this section, we prove Theorem 1.8 and Theorem 1.9. We prove Theorem 1.8 by
showing that, for all $2\times k$ linear systems $L$ with $s(L)=k-1$, there
exists a Fourier template $g$ that satisfies the condition in Theorem 3.5.

The existence of such Fourier template will be given by a probabilistic
argument. Recall that for every $M\in\mathbb{N}$, we let $[\\![-M,M]\\!]$
denote the subset $\\{-M,\dots,-1,0,1,\dots,M\\}\subseteq\mathbb{Z}$. Define
the random Fourier template $f_{M}\colon\mathbb{Z}\to\mathbb{C}$ by

$\begin{cases}f_{M}(r)=\xi_{r}&r\in[\\![-M,M]\\!]\setminus\\{0\\}\\\
f_{M}(r)=0&\text{otherwise,}\end{cases}$

where every $\xi_{r}$ is an independent random unit complex number, subject to
the constraint that $\xi_{r}=\overline{\xi_{-r}}$.

We say that two numbers form a cancelling pair if they sum up to zero. The key
observation is that, for all $a_{1},\dots,a_{t}\in\mathbb{Z}$, we have

$\displaystyle\mathbb{E}[f_{M}(a_{1})\cdots
f_{M}(a_{t})]=\begin{cases}1&a_{1},\dots,a_{t}\in[\\![-M,M]\\!]\setminus\\{0\\}\\\
&\text{and $a_{1},\dots,a_{t}$ can be partitioned into cancelling pairs}\\\
0&\text{otherwise.}\end{cases}$ ($\dagger$)

A result in [12] showed that any even length equation whose coefficients
cannot be partitioned into cancelling pairs is uncommon over sufficiently
large $\mathbb{F}_{p}$. This can be proved using a first moment argument on
the above $f_{M}$: if $L=a_{1}x_{1}+\dots+a_{k}x_{k}$ is such an equation,
then for every $r\in\mathbb{Z}$, we have $\mathbb{E}[f_{M}(a_{1}r)\dots
f_{M}(a_{k}r)]=0$ as $a_{1},\dots,a_{k}$ cannot be partitioned into cancelling
pairs. Thus, for sufficiently large $M$, we have
$\mathbb{E}[\sigma_{L}(f_{M})]=\mathbb{E}[\sum_{r\in\mathbb{Z}}f_{M}(a_{1}r)\dots
f_{M}(a_{k}r)]=0$ while $\mathbb{P}[\sigma_{L}(f_{M})>0]>0$, which means that
there is a choice of $f_{M}$ with $\sigma_{L}(f_{M})<0$.

When $L$ is a $2\times k$ linear system, it turns out that a first moment
argument is not enough. For example, consider the linear system

$\displaystyle L=\begin{pmatrix}1&0&-3&-4\\\ 0&1&1&2\end{pmatrix},$

so that

$\sigma_{L}(f_{M})=\sum_{r_{1},r_{2}\in\mathbb{Z}}f_{M}(r_{1})f_{M}(r_{2})f_{M}(-3r_{1}+r_{2})f_{M}(-4r_{1}+2r_{2}).$

By the above key observation $(\dagger)$, we get that

$\displaystyle\mathbb{E}[\sigma_{L}(f_{M})]$
$\displaystyle=|\\{(r_{1},r_{2})\in\mathbb{Z}^{2}:r_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+2r_{2}\in[\\![-M,M]\\!]\setminus\\{0\\},$
$\displaystyle\hskip 89.626ptr_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+2r_{2}\text{
can be partitioned into cancelling pairs}\\}|$
$\displaystyle=|\\{(r_{1},r_{2})\in\mathbb{Z}^{2}:r_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+2r_{2}\in[\\![-M,M]\\!]\setminus\\{0\\},$
$\displaystyle\hskip 87.63454pt-3r_{1}+2r_{2}=0$ $\displaystyle\hskip
88.2037pt\text{or }r_{1}+r_{2}=-7r_{1}+3r_{2}=0$ $\displaystyle\hskip
88.2037pt\text{or }-2r_{1}+r_{2}=-4r_{1}+3r_{2}=0\\}|$
$\displaystyle=\Theta(M)>0.$

Therefore, to prove Theorem 1.8, a first moment argument is insufficient and
we need a more careful analysis on the distribution of $\sigma_{L}(f_{M})$.

###  4.2. First attempt: second moment method

The most natural next step is to try to extract more information about
$\sigma_{L}(f_{M})$ from higher moments. For the sake of concreteness, we
continue to work with the example

$L=\begin{pmatrix}1&0&-3&-4\\\ 0&1&1&2\end{pmatrix}$

from the previous section.

First we compute the variance of $\sigma_{L}(f_{M})$. Define

$\displaystyle A_{M}$
$\displaystyle=\\{(r_{1},r_{2})\in\mathbb{Z}^{2}:r_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+r_{2}\in[\\![-M,M]\\!]\setminus\\{0\\},$
$\displaystyle\hskip 87.63454ptr_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+r_{2}\text{
cannot be partitioned into cancelling pairs}\\},$ $\displaystyle B_{M}$
$\displaystyle=\\{(r_{1},r_{2})\in\mathbb{Z}^{2}:r_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+r_{2}\in[\\![-M,M]\\!]\setminus\\{0\\},$
$\displaystyle\hskip 87.63454ptr_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+r_{2}\text{
can be partitioned into cancelling pairs}\\}.$

Then we know that

  1. (1)

$\sigma_{L}(f_{M})=\sum_{(r_{1},r_{2})\in A_{M}\cup
B_{M}}f_{M}(r_{1})f_{M}(r_{2})f_{M}(-3r_{1}+r_{2})f_{M}(-4r_{1}+2r_{2})$;

  2. (2)

If $(r_{1},r_{2})\in B_{M}$, then
$f_{M}(r_{1})f_{M}(r_{2})f_{M}(-3r_{1}+r_{2})f_{M}(-4r_{1}+2r_{2})$ is
constant 1;

  3. (3)

If $(r_{1},r_{2})\in A_{M}$, then
$\mathbb{E}[f_{M}(r_{1})f_{M}(r_{2})f_{M}(-3r_{1}+r_{2})f_{M}(-4r_{1}+2r_{2})]=0$.

Thus, we have

$\displaystyle\text{Var}[\sigma_{L}(f_{M})]$
$\displaystyle=\mathbb{E}[(\sum_{(r_{1},r_{2})\in
A_{M}}f_{M}(r_{1})f_{M}(r_{2})f_{M}(-3r_{1}+r_{2})f_{M}(-4r_{1}+2r_{2}))^{2}]$
$\displaystyle=\sum_{(r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime})\in
A_{M}}\mathbb{E}[f_{M}(r_{1})f_{M}(r_{2})f_{M}(-3r_{1}+r_{2})f_{M}(-4r_{1}+2r_{2})$
$\displaystyle\hskip 99.58464pt\cdot
f_{M}(r_{1}^{\prime})f_{M}(r_{2}^{\prime})f_{M}(-3r_{1}^{\prime}+r_{2}^{\prime})f_{M}(-4r_{1}^{\prime}+2r_{2}^{\prime})]$
$\displaystyle\overset{(\dagger)}{=}|\\{((r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime}))\in
A_{M}^{2}:r_{1},r_{2},-3r_{1}+r_{2},-4r_{1}+2r_{2},r_{1}^{\prime},r_{2}^{\prime},-3r_{1}^{\prime}+r_{2}^{\prime},-4r_{1}^{\prime}+2r_{2}^{\prime}$
$\displaystyle\hskip 140.27187pt\text{ can be partitioned into cancelling
pairs}\\}|$
$\displaystyle\geq|\\{((r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime}))\in
A_{M}^{2}:r_{1}^{\prime}=-r_{1},r_{2}^{\prime}=-r_{2}\\}|$
$\displaystyle=\Omega(M^{2}).$

In particular, this implies that
$\mathrm{Var}[\sigma_{L}(f_{M})]=\Omega\left(\mathbb{E}[\sigma_{L}(f_{M})]^{2}\right)$,
so the second moment argument also does not provide a sufficiently strong
anticoncentration statement to give the desired conclusion.

###  4.3. Speculating on higher moments

However, the observation ($\dagger$) suggests a way to compute higher moments.
In particular, the $d$-th moment of $\sigma_{L}(f_{M})$ is number of
$d$-tuples $((r_{1}^{(1)},r_{2}^{(1)})$, …, $(r_{1}^{(d)},r_{2}^{(d)}))\in
A_{M}^{d}$ such that the union of multisets
$\bigcup_{i=1}^{d}\\{\\!\\!\\{r_{1}^{(i)},r_{2}^{(i)},-3r_{1}^{(i)}+2r_{2}^{(i)},-4r_{1}^{(i)}+2r_{2}^{(i)}\\}\\!\\!\\}$
can be partitioned into cancelling pairs.

When $d=2t$ is even, this number is at least

$\binom{2t}{2}\binom{2t-2}{2}\ldots\binom{4}{2}\binom{2}{2}A_{M}^{t}=\frac{(2t)!}{2^{t}t!}(cM)^{2t}.$

Here $\binom{2t}{2}\binom{2t-2}{2}\ldots\binom{4}{2}\binom{2}{2}$ is the
number of ways to pair up $[2t]$ into $t$ pairs $(i_{1},i_{1}^{\prime})$, …,
$(i_{t},i_{t}^{\prime})$, as in each such pairing, we can pick arbitrary
$(r_{1}^{(i_{j})},r_{2}^{(i_{j})})\in A_{M}$ and set
$(r_{1}^{(i^{\prime}_{j})},r_{2}^{(i^{\prime}_{j})})=-(r_{1}^{(i_{j})},r_{2}^{(i_{j})})$
to meet the requirement. It is plausible to guess that this is the dominant
term in the $(2t)$-th moment, and this ansatz suggests that
$\sigma_{L}(f_{M})$ might be close to a normal random variable with mean
$\Theta(M)$ and variance $\Theta(M^{2})$.

However, if we want to prove this by the method of higher moments, then we
need to show that the other ways to partition
$\bigcup_{i=1}^{d}\\{\\!\\!\\{r_{1}^{(i)},r_{2}^{(i)},-3r_{1}^{(i)}+2r_{2}^{(i)},-4r_{1}^{(i)}+2r_{2}^{(i)}\\}\\!\\!\\}$
into cancelling pairs correspond to lower order terms $o(M^{d})$. There are
$\frac{(4d)!}{2^{2d}(2d)!}$ ways to partition this set into pairs; although
most of them cannot be a valid partition into cancelling pairs, such approach
becomes computationally messy very quickly. This motivates us to find another
way to prove that $\sigma_{L}(f_{M})$ is close in distribution to a normal
random variable, with information from low moments only.

###  4.4. Second attempt: Stein’s method

As mentioned earlier, we would like to prove that $\sigma_{L}(f_{M})$ is close
in distribution to a normal random variable without appealing to high moment
calculations. The method of moments fundamentally relies on the fact that a
distribution is uniquely determined by its characteristic function. Another
approach to distributional approximation is _Stein’s method_ in which we
replace the characteristic function with a characterizing operator.

######  Lemma 4.1 (Stein’s lemma).

Define the functional operator $\mathcal{A}$ by
$\mathcal{A}f(x)=f^{\prime}(x)-xf(x)$. If a random variable $Z$ is such that
$\mathbb{E}\mathcal{A}f(Z)=0$ for all absolutely continuous functions $f$ with
$\left\lVert f^{\prime}\right\rVert_{\infty}<\infty$, then
$Z\sim\mathcal{N}(0,1)$.

We say that $\mathcal{A}$ is the _characterizing operator_ of the standard
normal. An immediate consequence of the above is that we can get quantitative
distributional approximation using the characterizing operator.

######  Corollary 4.2 (Another form of Stein’s lemma).

Let $W$ be any random variable and $Z\sim\mathcal{N}(0,1)$. For any family of
functions $\mathcal{H}$, we have that

$\sup_{h\in\mathcal{H}}[|\mathbb{E}h(W)-\mathbb{E}h(Z)|]=\sup_{h\in\mathcal{H}}|\mathbb{E}[f_{h}^{\prime}(W)-Wf_{h}(W)]|,$

where $f_{h}^{\prime}$ is the solution to

$f_{h}^{\prime}(x)-xf_{h}(x)=h(x)-\mathbb{E}h(Z).$

A working mathematician’s form of the above corollary is the following:

######  Definition 4.3 (Wasserstein distance).

For random variables $X\sim\mu$ and $Y\sim\nu$ defined on a probability space
$\Omega$, the _Wasserstein distance_ between $X,Y$ is defined by

$d_{\text{Wass}}(X,Y)=\sup\left\\{\left|\int fd\mu-\int
fd\nu\right|:f\colon\Omega\to\mathbb{R}\text{ is
}1\text{-Lipschitz}\right\\}.$

######  Corollary 4.4 ([20, Theorem 3.1]).

Define

$\mathcal{D}=\left\\{f\in\mathcal{C}^{1}(\mathbb{R}):f^{\prime}\text{ is
absolutely continuous},\,\left\lVert f\right\rVert_{\infty}\leq
1,\,\left\lVert f^{\prime}\right\rVert_{\infty}\leq\sqrt{2/\pi},\,\left\lVert
f^{\prime\prime}\right\rVert_{\infty}\leq 2\right\\}.$

If $W$ is a random variable and $Z\sim\mathcal{N}(0,1)$, then

$d_{\mathrm{Wass}}(W,Z)\leq\sup_{f\in\mathcal{D}}\left|\mathbb{E}[f^{\prime}(W)-Wf(W)]\right|.$

Note that in our previous example, two variables
$f_{M}(r_{1})f_{M}(r_{2})f_{M}(-3r_{1}+r_{2})f_{M}(-4r_{1}+2r_{2})$,
$f_{M}(r_{1}^{\prime})f_{M}(r_{2}^{\prime})f_{M}(-3r_{1}^{\prime}+r_{2}^{\prime})f_{M}(-4r_{1}^{\prime}+2r_{2}^{\prime})$
are independent unless $r_{1},r_{1}^{\prime},r_{2},r_{2}^{\prime}$ satisfy
certain linear relations. This is also the reason why we would expect
Corollary 4.4 to be useful for us: it allows us to quantify the intuitive idea
that a sum of only locally dependent random variables is approximately normal.
More precisely, we have the following consequence of Corollary 4.4, which we
formalize using the notion of dependency graph.

######  Definition 4.5 (Dependency graph).

Given a graph $G=(V,E)$ and a collection of random variables
$\\{X_{i}\\}_{i\in V}$, we say that $G$ is a _dependency graph_ for
$\\{X_{i}\\}_{i\in V}$ if for any disjoint subsets $S,T\subseteq V$ with no
edges between $S$ and $T$, the two random vectors $(X_{i})_{i\in S}$ and
$(X_{i})_{i\in T}$ are independent.

For a graph $G=(V,E)$ and vertex $u\in V$, we use $N_{u}$ to denote the closed
neighborhood of $u$; that is, $N_{u}=\\{v:uv\in E\\}\cup\\{u\\}$.

######  Lemma 4.6.

Let $\\{X_{v}\\}_{v\in V}$ be a family of random variables with dependency
graph $G=(V,E)$. Let $\rho=\sqrt{\mathrm{Var}\left(\sum_{v}X_{v}\right)}$ and
$W=\rho^{-1}\sum_{v\in V}X_{v}$. Suppose $\mathbb{E}X_{v}=0$ for all $v\in V$.
Then for $Z\sim\mathcal{N}(0,1)$ and any $x\in\mathbb{R}$, we have

$\displaystyle|\mathbb{P}[W\leq x]-\mathbb{P}[Z\leq x]|^{2}$
$\displaystyle\leq 2/\pi\cdot\rho^{-3}\sum_{u\in V}\left(3\sum_{v,w\in
N_{u}}\left|\mathbb{E}[X_{u}X_{v}X_{w}]\right|+4\sum_{v\in
N_{u}}|\mathbb{E}[X_{u}X_{v}]|\cdot\mathbb{E}\left[\left|\sum_{w\in N_{u}\cup
N_{v}}X_{w}\right|\right]\right).$

A proof of Lemma 4.6 (which is effectively a modified version of [3, Theorem
3.1]) is provided in Appendix A.

###  4.5. Proof of Theorem 1.8

Suppose $k\geq 4$ is even, and $L$ is a $2\times k$ linear system with
$s(L)=k-1$. To prove Theorem 1.8, by Theorem 3.5, it suffices to construct a
Fourier template $g:\mathbb{Z}\to\mathbb{C}$ such that $\sigma_{L}(g)<0$.

Suppose $L$ takes the form

$\displaystyle L=\begin{pmatrix}a_{1}&\dots&a_{k}\\\
b_{1}&\dots&b_{k}\end{pmatrix}.$

Since $s(L)=k-1$, the column vectors
$(a_{1},b_{1}),\dots,(a_{k},b_{k})\in\mathbb{Z}^{2}$ are pairwise linearly
independent. For any Fourier template $g\colon\mathbb{Z}\to\mathbb{C}$, we
have

$\displaystyle\sigma_{L}(g)=\sum_{r_{1},r_{2}\in\mathbb{Z}}g(a_{1}r_{1}+b_{1}r_{2})\cdots
g(a_{k}r_{1}+b_{k}r_{2}).$

The key idea for proving Theorem 1.8 is to combine Theorem 3.5 with a
probabilistic argument.

######  Proposition 4.7.

Let $L$ be a $2\times k$ linear system with $k\geq 4$ even and $s(L)=k-1$. For
every $M\in\mathbb{N}$, define the random Fourier template
$f_{M}\colon\mathbb{Z}\to\mathbb{C}$ by

$\begin{cases}f_{M}(r)=\xi_{r}&r\in[\\![-M,M]\\!]\setminus\\{0\\}\\\
f_{M}(r)=0&\text{otherwise,}\end{cases}$

where every $\xi_{r}$ is a uniformly random unit complex number, subject to
$\xi_{r}=\overline{\xi_{-r}}$ but independent otherwise. Then
$\mathbb{P}[\sigma_{L}(f_{M})<0]>0$ for all sufficiently large $M$.

Theorem 1.8 then directly follows from Proposition 4.7 and Theorem 3.5.

###### Proof of Theorem 1.8.

Let $L$ be a $2\times k$ linear system with $k\geq 4$ even and $s(L)=k-1$. By
Proposition 4.7, there exists a Fourier template $g:\mathbb{Z}\to\mathbb{C}$
such that $\sigma_{L}(g)<0$. By Theorem 3.5, $L$ is uncommon over
$\mathbb{F}_{p}$ for all sufficiently large $p$. ∎

It remains to show Proposition 4.7.

###### Proof of Proposition 4.7.

Fix a $2\times k$ linear system $L$ with $k\geq 4$ even and $s(L)=k-1$. Choose
$\lambda\in\mathbb{N}$ sufficiently large such that, for all $M\in\mathbb{N}$,
if $a_{1}r_{1}+b_{1}r_{2}$, …, $a_{k}r_{1}+b_{k}r_{2}\in[\\![-M,M]\\!]$, then
$-\lambda M\leq r_{1},r_{2}\leq\lambda M$.

Let $N=\lambda M$. Since $f_{M}$ is always supported on
$[\\![-M,M]\\!]\setminus\\{0\\}$, we have

$\displaystyle\sigma_{L}(f_{M})$
$\displaystyle=\sum_{r_{1},r_{2}\in\mathbb{Z}}f_{M}(a_{1}r_{1}+a_{1}r_{2})\cdots
f_{M}(a_{k}r_{1}+b_{k}r_{2})$
$\displaystyle=\sum_{r_{1},r_{2}\in[\\![-N,N]\\!]}f_{M}(a_{1}r_{1}+a_{1}r_{2})\cdots
f_{M}(a_{k}r_{1}+b_{k}r_{2}).$

For every multiset $S\subseteq\mathbb{Z}$, define the associated random
variable

$X_{S}=\prod_{s\in S}f_{M}(s),$

where the product goes over all $s\in S$ counting multiplicities. Note that
$X_{S}$ has the following properties:

  1. (i)

$X_{S}X_{S^{\prime}}=X_{S\cup S^{\prime}}$.

  2. (ii)

$\displaystyle\begin{cases}X_{S}=1&S\subseteq[\\![-M,M]\\!]\setminus\\{0\\},\,S\text{
can be partitioned into cancelling pairs,}\\\
\mathbb{E}X_{S}=0&\text{otherwise.}\end{cases}$

  3. (iii)

Let $\mathcal{S}$ and $\mathcal{S}^{\prime}$ be two collections of subsets of
$\mathbb{Z}$. If $\pm\bigcup_{S\in\mathcal{S}}S$ and
$\pm\bigcup_{S^{\prime}\in\mathcal{S}^{\prime}}S^{\prime}$ are disjoint, then
the two random vectors $(X_{S})_{{S}\in\mathcal{S}}$ and
$(X_{S})_{{S}\in\mathcal{S}^{\prime}}$ are independent.

For every $(r_{1},r_{2})\in[\\![-N,N]\\!]^{2}$, define the associated multiset

$S_{(r_{1},r_{2})}=\\{\\!\\!\\{a_{1}r_{1}+b_{1}r_{2},\dots,a_{k}r_{1}+b_{k}r_{2}\\}\\!\\!\\}.$

We simply write $X_{(r_{1},r_{2})}$ to denote $X_{S(r_{1},r_{2})}$. Thus, we
have

$\displaystyle\sigma_{L}(f_{M})$
$\displaystyle=\sum_{r_{1},r_{2}\in[\\![-N,N]\\!]}f_{M}(a_{1}r_{1}+a_{1}r_{2})\cdots
f_{M}(a_{k}r_{1}+b_{k}r_{2})=\sum_{r_{1},r_{2}\in[\\![-N,N]\\!]}X_{(r_{1},r_{2})}.$

Consider the partition $[\\![-N,N]\\!]^{2}=A_{N}\cup B_{N}$ defined by

$\displaystyle A_{N}$
$\displaystyle=\\{(r_{1},r_{2})\in[\\![-N,N]\\!]^{2}:S_{(r_{1},r_{2})}\not\subseteq[\\![-M,M]\\!]\setminus\\{0\\}$
$\displaystyle\hskip 120.92421pt\text{or }S_{(r_{1},r_{2})}\text{ cannot be
partitioned into cancelling pairs}\\},$ $\displaystyle B_{N}$
$\displaystyle=\\{(r_{1},r_{2})\in[\\![-N,N]\\!]^{2}:S_{(r_{1},r_{2})}\subseteq[\\![-M,M]\\!]\setminus\\{0\\}$
$\displaystyle\hskip 120.92421pt\text{and }S_{(r_{1},r_{2})}\text{ can be
partitioned into cancelling pairs}\\}.$

For all $(r_{1},r_{2})\in B_{N}$, we always have $X_{(r_{1},r_{2})}=1$.
Therefore we have

$\sigma_{L}(f_{M})=|B_{N}|+\sum_{(r_{1},r_{2})\in A_{N}}X_{(r_{1},r_{2})}.$

We study the distribution of $\sum_{(r_{1},r_{2})\in A_{N}}X_{(r_{1},r_{2})}$
using Lemma 4.6. Let $G$ be a dependency graph for the family of variables
$\\{X_{(r_{1},r_{2})}:(r_{1},r_{2})\in A_{N}\\}$, defined by

$\displaystyle V(G)$ $\displaystyle=A_{N},$ $\displaystyle E(G)$
$\displaystyle=\\{\\{(r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime})\\}:\pm
S_{(r_{1},r_{2})}\cap\pm
S_{(r_{1}^{\prime},r_{2}^{\prime})}\neq\emptyset\\}\subseteq\binom{A_{N}}{2}.$

Recall from Definition 4.5 that $N_{(r_{1},r_{2})}$ denotes the closed
neighborhood of $(r_{1},r_{2})$ in $G$, which in this case equals

$\\{(r_{1}^{\prime},r_{2}^{\prime})\in A_{N}:\pm S_{(r_{1},r_{2})}\cap\pm
S_{(r_{1}^{\prime},r_{2}^{\prime})}\neq\emptyset\\}.$

We will verify the following properties of $\sum_{(r_{1},r_{2})\in
A_{N}}X_{(r_{1},r_{2})}$. In the asymptotic bounds below, we allow the
constants in $O(\cdot)$ and $\Omega(\cdot)$ to depend on $k$, as $L$ is fixed.

######  Claim 4.8.

  1. (1)

$\mathbb{E}[\sum_{u\in A_{N}}X_{u}]=0$, and $\textup{Var}(\sum_{u\in
A_{N}}X_{u})=\Omega(N^{2})$;

  2. (2)

For every $u\in A_{N}$, $\sum_{v\in A_{N}}\mathbb{E}[X_{u}X_{v}]=O(1)$;

  3. (3)

$\sum_{u,v,w\in A_{N}}\mathbb{E}[X_{u}X_{v}X_{w}]=O(N^{2});$

  4. (4)

For every $u,v\in A_{N}$, $\sum_{w_{1},w_{2}\in N_{u}\cup
N_{v}}\mathbb{E}[X_{w_{1}}\overline{X_{w_{2}}}]=O(N)$.

We first prove Proposition 4.7 assuming 4.8. Let $Z\sim\mathcal{N}(0,1)$ be
the normal distribution and $\rho=\sqrt{\text{Var}(\sum_{u\in
A_{N}}X_{u})}=\Omega(N)$ (per 4.8(1)). We know from 4.8(4) that

  1. (5)

For every $u,v\in A_{N}$, by applying the Cauchy–Schwarz inequality, we have

$\displaystyle(\mathbb{E}|\sum_{w\in N_{u}\cup N_{v}}X_{w}|)^{2}$
$\displaystyle\leq\mathbb{E}[|\sum_{w\in N_{u}\cup
N_{v}}X_{w}|^{2}]=\mathbb{E}[(\sum_{w\in N_{u}\cup N_{v}}X_{w})(\sum_{w\in
N_{u}\cup N_{v}}\overline{X_{w}})]$ $\displaystyle=\sum_{w_{1},w_{2}\in
N_{u}\cup N_{v}}\mathbb{E}[X_{w_{1}}\overline{X_{w_{2}}}]=O(N).$

Let $W=\rho^{-1}\sum_{u\in A_{N}}X_{u}$. By Lemma 4.6, for
$Z\sim\mathcal{N}(0,1)$ and all $x\in\mathbb{R}$, we have

$\displaystyle\pi/2\cdot|\mathbb{P}[W\leq x]-\mathbb{P}[Z\leq x]|^{2}$
$\displaystyle\leq\rho^{-3}\sum_{u\in A_{N}}(3\sum_{v,w\in
N_{u}}|\mathbb{E}[X_{u}X_{v}X_{w}]|+4\sum_{v\in
N_{u}}|\mathbb{E}[X_{u}X_{v}]|\cdot\mathbb{E}|\sum_{w\in N_{u}\cup
N_{v}}X_{w}|)$ $\displaystyle\overset{(*)}{\leq}\rho^{-3}(3\sum_{u,v,w\in
A_{N}}\mathbb{E}[X_{u}X_{v}X_{w}]+4\sum_{u,v\in
A_{N}}\mathbb{E}[X_{u}X_{v}]\cdot\mathbb{E}|\sum_{w\in N_{u}\cup
N_{v}}X_{w}|)$ $\displaystyle\leq O(N^{-3})(O(N^{2})+O(N^{1/2})\sum_{u,v\in
A_{N}}\mathbb{E}[X_{u}X_{v}])$ (1)(3)(5) $\displaystyle\leq
O(N^{-3})(O(N^{2})+O(N^{5/2}))=O(N^{-1/2}),$ (2)

where $(\ast)$ is due to the fact that (recall properties (i)(ii) at the
beginning of proof)

$0\leq\mathbb{E}[X_{u}X_{v}],\mathbb{E}[X_{u}X_{v}X_{w}]\leq 1\qquad\text{for
all $u,v,w\in A_{N}$}.$

Since $\sigma_{L}(f_{M})=|B_{N}|+\sum_{v\in A_{N}}X_{v}$, we have

$\mathbb{P}(\sigma_{L}(f_{M})<0)=\mathbb{P}(\sum_{v\in
A_{N}}X_{v}<-|B_{N}|)=\mathbb{P}(W<-|B_{N}|/\rho),$

and therefore

$\displaystyle|\mathbb{P}(\sigma_{L}(f_{M})<0)-\mathbb{P}(Z<-|B_{N}|/\rho)|=O(N^{-1/4}).$

Since $|B_{N}|=O(N)$ and $\rho=\Omega(N)$, we have $|B_{N}|/\rho=O(1)$. Thus
$\mathbb{P}(Z<-|B_{N}|/\rho)=c>0$, and therefore
$\mathbb{P}(\sigma_{L}(f_{M})<0)\geq c-O(N^{-1/4})>0$ for all $N$ sufficiently
large. ∎

It remains to verify 4.8.

###### Proof of 4.8.

(1) For every $u=(r_{1},r_{2})\in A_{N}$, since $S_{(r_{1},r_{2})}$ cannot be
partitioned into cancelling pairs, we have $\mathbb{E}X_{(r_{1},r_{2})}=0$.
Moreover, we have

$\displaystyle\mathbb{E}[(\sum_{u\in A_{N}}X_{u})^{2}]=\sum_{u,v\in
A_{N}}\mathbb{E}[X_{u}X_{v}]=\sum_{u,v\in A_{N}}\mathbb{E}[X_{S_{u}\cup
S_{v}}]$ $\displaystyle=|\\{(u,v)\in A_{N}^{2}:S_{u}\cup
S_{v}\subseteq[\\![-M,M]\\!]\setminus\\{0\\},\,S_{u}\cup S_{v}\text{ can be
partitioned into cancelling pairs}\\}|$
$\displaystyle\geq|\\{((r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime}))\in
A_{N}^{2}:S_{(r_{1},r_{2})}\subseteq[\\![-M,M]\\!]\setminus\\{0\\},r_{1}^{\prime}=-r_{1},r_{2}^{\prime}=-r_{2}\\}|$
$\displaystyle=\Omega(N^{2}).$

This gives $\text{Var}(\sum_{u\in A_{N}}X_{u})=\Omega(N^{2})$.

(2) For all $u=(r_{1},r_{2})\in A_{N}$, we have

$\displaystyle\sum_{v\in A_{N}}\mathbb{E}[X_{u}X_{v}]=\sum_{v\in
A_{N}}\mathbb{E}[X_{S_{u}\cup S_{v}}]$ $\displaystyle\leq|\\{v\in
A_{N}:S_{u}\cup S_{v}\text{ can be partitioned into cancelling pairs}\\}|.$

Recall that $S_{u}$ itself cannot be partitioned into cancelling pairs.
Therefore, if $S_{u}\cup S_{v}$ can be partitioned into cancelling pairs, then
$v=(r_{1}^{\prime},r_{2}^{\prime})$ must satisfy equations of the form

$\displaystyle a_{i^{\prime}}r_{1}^{\prime}+b_{i^{\prime}}r_{2}^{\prime}$
$\displaystyle=-(a_{i}r_{1}+b_{i}r_{2})$ $\displaystyle
a_{j^{\prime}}r_{1}^{\prime}+b_{j^{\prime}}r_{2}^{\prime}$
$\displaystyle=-(a_{j}r_{1}+b_{j}r_{2})$

with $i\neq j$ and $i^{\prime}\neq j^{\prime}$. Since
$(a_{i^{\prime}},b_{i^{\prime}})$ and $(a_{j^{\prime}},b_{j^{\prime}})$ are
linearly independent due to the girth condition $s(L)=k-1$, every such pair of
equations has at most one solution. Moreover, there are at most $k^{4}$ such
pairs. Thus, for every $u\in A_{N}$, we get that

$|\\{v\in A_{N}:S_{u}\cup S_{v}\text{ can be partitioned into cancelling
pairs}\\}|=O(1).$

Proofs of (3)(4) have similar ideas as in (2).

(3) For every triple $(u,v,w)\in A_{N}^{3}$, define a graph $H_{u,v,w}$ on the
multiset $S_{u}\cup S_{v}\cup S_{w}$, such that $s_{1}\sim s_{2}$ in
$H_{u,v,w}$ if and only if $s_{1}+s_{2}=0$. Observe that

$\displaystyle\sum_{u,v,w\in A_{N}}\mathbb{E}[X_{u}X_{v}X_{w}]$
$\displaystyle=\sum_{u,v,w\in A_{N}}\mathbb{E}[X_{S_{u}\cup S_{v}\cup S_{w}}]$
$\displaystyle=|\\{(u,v,w)\in
A_{N}^{3}:S_{u},S_{v},S_{w}\subseteq[\\![-M,M]\\!]\setminus\\{0\\},$
$\displaystyle\hskip 99.58464ptS_{u}\cup S_{v}\cup S_{w}\text{ can be
partitioned into cancelling pairs}\\}|$ $\displaystyle=|\\{(u,v,w)\in
A_{N}^{3}:S_{u},S_{v},S_{w}\subseteq[\\![-M,M]\\!]\setminus\\{0\\},$
$\displaystyle\hskip 99.58464ptH_{u,v,w}\text{ has a perfect matching}\\}|.$

Note that every graph $H_{u,v,w}$ has $|S_{u}\cup S_{v}\cup S_{w}|=3k$
vertices. We prove that, for every perfect matching $\mathcal{M}$ on $3k$
vertices, there are $O(N^{2})$ choices of $(u,v,w)\in A_{N}^{3}$ such that
$S_{u}\cup S_{v}\cup S_{w}\subseteq[\\![-M,M]\\!]\setminus\\{0\\}$ and
$H_{u,v,w}$ contains $\mathcal{M}$ as a subgraph. Since there are finitely
many perfect matchings on $3k$ vertices, we get that

$|\\{(u,v,w)\in
A_{N}^{3}:S_{u},S_{v},S_{w}\subseteq[\\![-M,M]\\!]\setminus\\{0\\},\,H_{u,v,w}\text{
has a perfect matching}\\}|=O(N^{2}).$

Fix a perfect matching $\mathcal{M}$ on $3k$ vertices. Suppose $(u,v,w)\in
A_{N}^{3}$ satisfies $S_{u}\cup S_{v}\cup
S_{w}\subseteq[\\![-M,M]\\!]\setminus\\{0\\}$, and $H_{u,v,w}$ contains
$\mathcal{M}$ as a subgraph. For $U,V\subseteq S_{u}\cup S_{v}\cup S_{w}$, let
$e_{\mathcal{M}}(U,V)$ denote the number of edges in $\mathcal{M}$ whose
vertices intersect both $U$ and $V$. Since none of $S_{u}$, $S_{v}$, $S_{w}$
can be partitioned into cancelling pairs, we must have

$\displaystyle e_{\mathcal{M}}(S_{u},\,S_{v}\cup S_{w})\geq 2,$ $\displaystyle
e_{\mathcal{M}}(S_{v},\,S_{u}\cup S_{w})\geq 2,$ $\displaystyle
e_{\mathcal{M}}(S_{w},\,S_{u}\cup S_{v})\geq 2.$

Up to permuting $u,v,w$, we have the following two cases.

Case 1. $e_{\mathcal{M}}(S_{u},S_{v})\geq 2$. In this case, $\mathcal{M}$
gives $i\neq j$ and $i^{\prime}\neq j^{\prime}$ such that

$\displaystyle a_{i^{\prime}}r_{1}^{\prime}+b_{i^{\prime}}r_{2}^{\prime}$
$\displaystyle=-(a_{i}r_{1}+b_{i}r_{2}),$ $\displaystyle
a_{j^{\prime}}r_{1}^{\prime}+b_{j^{\prime}}r_{2}^{\prime}$
$\displaystyle=-(a_{j}r_{1}+b_{j}r_{2})$

for $u=(r_{1},r_{2})$ and $v=(r_{1}^{\prime},r_{2}^{\prime})$. Since
$(a_{i^{\prime}},b_{i^{\prime}})$ and $(a_{j^{\prime}},b_{j^{\prime}})$ are
linearly independent, $v=(r_{1}^{\prime},r_{2}^{\prime})$ is uniquely
determined by $u=(r_{1},r_{2})$. Since $e_{\mathcal{M}}(S_{w},S_{u}\cup
S_{v})\geq 2$, $\mathcal{M}$ also gives $i^{\prime\prime}\neq
j^{\prime\prime}$ and $i^{\circ},i^{*}$ such that

$\displaystyle
a_{i^{\prime\prime}}r_{1}^{\prime\prime}+b_{i^{\prime\prime}}r_{2}^{\prime\prime}=-(a_{i^{\circ}}r_{1}^{\circ}+b_{i^{\circ}}r_{2}^{\circ}),$
$\displaystyle
a_{j^{\prime\prime}}r_{1}^{\prime\prime}+b_{j^{\prime\prime}}r_{2}^{\prime\prime}=-(a_{i^{*}}r_{1}^{*}+b_{i^{*}}r_{2}^{*})$

for $w=(r_{1}^{\prime\prime},r_{2}^{\prime\prime})$ and
$(r_{1}^{\circ},r_{2}^{\circ}),(r_{1}^{*},r_{2}^{*})\in\\{(r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime})\\}=\\{u,v\\}$.
Since $(a_{i^{\prime\prime}},b_{i^{\prime\prime}})$ and
$(a_{j^{\prime\prime}},b_{j^{\prime\prime}})$ are linearly independent,
$w=(r_{1}^{\prime\prime},r_{2}^{\prime\prime})$ is uniquely determined by
$u=(r_{1},r_{2})$ and $v=(r_{1}^{\prime},r_{2}^{\prime})$. Therefore, the
number of choices for $u,v,w$ is at most the number of choices for
$u=(r_{1},r_{2})$, which is $O(N^{2})$.

Case 2.
$e_{\mathcal{M}}(S_{u},S_{v})=e_{\mathcal{M}}(S_{u},S_{w})=e_{\mathcal{M}}(S_{v},S_{w})=1.$
In this case, $\mathcal{M}$ gives $i\neq j$, $i^{\prime}\neq j^{\prime}$ and
$i^{\prime\prime}\neq j^{\prime\prime}$ such that

$\displaystyle a_{i^{\prime}}r_{1}^{\prime}+b_{i^{\prime}}r_{2}^{\prime}$
$\displaystyle=-(a_{i}r_{1}+b_{i}r_{2}),$ $\displaystyle
a_{i^{\prime\prime}}r_{1}^{\prime\prime}+b_{i^{\prime\prime}}r_{2}^{\prime\prime}$
$\displaystyle=-(a_{j}r_{1}+b_{j}r_{2}),$ $\displaystyle
a_{j^{\prime\prime}}r_{1}^{\prime\prime}+b_{j^{\prime\prime}}r_{2}^{\prime\prime}$
$\displaystyle=-(a_{j^{\prime}}r_{1}^{\prime}+b_{j^{\prime}}r_{2}^{\prime}).$

Since $S_{u}\cup S_{v}\cup S_{w}\subseteq[\\![-M,M]\\!]\setminus\\{0\\}$, none
of the above three equations can be 0.

Now since $|S_{u}|=|S_{v}|=|S_{w}|=k\geq 4$, $\mathcal{M}$ also has at least
one edge within each of $S_{u},S_{v},S_{w}$. Therefore, $\mathcal{M}$ in
particular gives $i^{\prime},k^{\prime},\ell^{\prime}$ distinct,
$i^{\prime\prime},k^{\prime\prime},\ell^{\prime\prime}$ distinct, and $i\neq
j$ such that

$\displaystyle
a_{i^{\prime}}r_{1}^{\prime}+b_{i^{\prime}}r_{2}^{\prime}=-(a_{i}r_{1}+b_{i}r_{2}),$
$\displaystyle
a_{i^{\prime\prime}}r_{1}^{\prime\prime}+b_{i^{\prime\prime}}r_{2}^{\prime\prime}=-(a_{j}r_{1}+b_{j}r_{2}),$
$\displaystyle
a_{k^{\prime}}r_{1}^{\prime}+b_{k^{\prime}}r_{2}^{\prime}=-(a_{\ell^{\prime}}r_{1}^{\prime}+b_{\ell^{\prime}}r_{2}^{\prime}),$
$\displaystyle
a_{k^{\prime\prime}}r_{1}^{\prime\prime}+b_{k^{\prime\prime}}r_{2}^{\prime\prime}=-(a_{\ell^{\prime\prime}}r_{1}^{\prime\prime}+b_{\ell^{\prime\prime}}r_{2}^{\prime\prime}).$

Since

  1. (i)

$(a_{k^{\prime}},b_{k^{\prime}})$ and $(a_{\ell^{\prime}},b_{\ell^{\prime}})$
are linearly independent,

  2. (ii)

$(a_{k^{\prime\prime}},b_{k^{\prime\prime}})$ and
$(a_{\ell^{\prime\prime}},b_{\ell^{\prime\prime}})$ are linearly independent,

  3. (iii)

$a_{i}r_{1}+b_{i}r_{2}$ and $a_{j}r_{1}+b_{j}r_{2}$ are nonzero,

we get that $v=(r_{1}^{\prime},r_{2}^{\prime})$ and
$w=(r_{1}^{\prime\prime},r_{2}^{\prime\prime})$ are uniquely determined by
$u=(r_{1},r_{2})$. Hence the number of choices for $u,v,w$ is at most the
number of choices for $u=(r_{1},r_{2})$, which is $O(N^{2})$.

(4) For every $u=(r_{1},r_{2}),v=(r_{1}^{\prime},r_{2}^{\prime})\in A_{N}$, we
have

$\displaystyle\sum_{\begin{subarray}{c}w_{1},w_{2}\in N_{u}\cup
N_{v}\end{subarray}}\mathbb{E}[X_{w_{1}}\overline{X_{w_{2}}}]=\sum_{\begin{subarray}{c}w_{1},w_{2}\in
N_{u}\cup N_{v}\end{subarray}}\mathbb{E}[X_{w_{1}}X_{-w_{2}}]$
$\displaystyle\leq|\\{(w_{1},w_{2})\in(N_{u}\cup N_{v})^{2}:S_{w_{1}}\cup
S_{-w_{2}}\text{ can be partitioned into cancelling pairs}\\}|.$

Recall that each of $S_{w_{1}},S_{w_{2}}$ cannot be partitioned into
cancelling pairs. Therefore, if $S_{w_{1}}\cup S_{-w_{2}}$ can be partitioned
into cancelling pairs, then
$w_{1}=(r_{1}^{\prime\prime},r_{2}^{\prime\prime})$,
$w_{2}=(r_{1}^{\prime\prime\prime},r_{2}^{\prime\prime\prime})$ must satisfy
two equations

$\displaystyle
a_{i^{\prime\prime}}r_{1}^{\prime\prime}+b_{i^{\prime\prime}}r_{2}^{\prime\prime}$
$\displaystyle=-(a_{i^{\prime\prime\prime}}r_{1}^{\prime\prime\prime}+b_{i^{\prime\prime\prime}}r_{2}^{\prime\prime\prime})$
$\displaystyle
a_{j^{\prime\prime}}r_{1}^{\prime\prime}+b_{j^{\prime\prime}}r_{2}^{\prime\prime}$
$\displaystyle=-(a_{j^{\prime\prime\prime}}r_{1}^{\prime\prime\prime}+b_{j^{\prime\prime\prime}}r_{2}^{\prime\prime\prime})$

with $i^{\prime\prime}\neq j^{\prime\prime}$ and $i^{\prime\prime\prime}\neq
j^{\prime\prime\prime}$. Again, by linear independence of the columns of $L$,
for fixed choices of
$i^{\prime\prime},j^{\prime\prime},i^{\prime\prime\prime},j^{\prime\prime\prime}$,
each one of $w_{1},w_{2}$ will uniquely determine another.

We now look at the number of possible choices for $w_{1}$. Since $w_{1}\in
N_{u}\cup N_{v}$, by Definition 4.5,
$w_{1}=(r_{1}^{\prime\prime},r_{2}^{\prime\prime})$ must also satisfy

$\displaystyle a_{\ell}r_{1}^{\prime\prime}+b_{\ell}r_{2}^{\prime\prime}$
$\displaystyle=a_{\ell^{\circ}}r_{1}^{\circ}+b_{\ell^{\circ}}r_{2}^{\circ}\qquad\text{
or }\qquad
a_{\ell}r_{1}^{\prime\prime}+b_{\ell}r_{2}^{\prime\prime}=-(a_{\ell^{\circ}}r_{1}^{\circ}+b_{\ell^{\circ}}r_{2}^{\circ})$

for some $\ell,\ell^{\circ}$ and
$(r_{1}^{\circ},r_{2}^{\circ})\in\\{(r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime})\\}$.
Given $\ell,\ell^{\circ}$ and $(r_{1}^{\circ},r_{2}^{\circ})$, since we cannot
have $a_{\ell}=b_{\ell}=0$, the number of possible choices for $w_{1}$ is at
most $O(N)$.

Overall, since there are finitely many choices for
$i^{\prime\prime},j^{\prime\prime},i^{\prime\prime\prime},j^{\prime\prime\prime},\ell,\ell^{\circ}$
and
$(r_{1}^{\circ},r_{2}^{\circ})\in\\{(r_{1},r_{2}),(r_{1}^{\prime},r_{2}^{\prime})\\}$,
we get that

$|\\{(w_{1},w_{2})\in(N_{u}\cup N_{v})^{2}:S_{w_{1}}\cup S_{-w_{2}}\text{ can
be partitioned into cancelling pairs}\\}|=O(N).$

∎

###  4.6. Proof of Theorem 1.9

Let $L$ be a linear system with $c=c(L)$. Recall from Remark 2.3 that all
elements in $\\{L_{B}:B\in\mathcal{C}(L)\\}$ are either length-$c$ linear
equations or $2\times c$ systems with girth $c-1$.

Consider the partition $\mathcal{C}(L)=\mathcal{C}_{1}\cup\mathcal{C}_{2}$
defined by

$\displaystyle\mathcal{C}_{1}$
$\displaystyle=\\{B\in\mathcal{C}(L):L_{B}\text{ is length-$c$ linear
equation}\\},$ $\displaystyle\mathcal{C}_{2}$
$\displaystyle=\\{B\in\mathcal{C}(L):L_{B}\text{ is $2\times c$ linear
system}\\}.$

The following lemma is essentially due to Altman [1, Theorem 5.2], although
Altman did not work in the language of Fourier templates. For the sake of
completeness, we provide its proof here.

######  Proposition 4.9.

Let $L$ be a linear system with $s(L)$ odd. Suppose there exists a Fourier
template $g:\mathbb{Z}^{d}\to\mathbb{C}$ such that
$\sum_{B\in\mathcal{C}_{2}}\sigma_{L_{B}}(g)<0$. Then $L$ is uncommon over all
sufficiently large $p$.

###### Proof.

Suppose $\sum_{B\in\mathcal{C}_{2}}\sigma_{L_{B}}(g)<0$ for some Fourier
template $g:\mathbb{Z}^{d}\to\mathbb{C}$. By Theorem 3.5, this gives a
function $f:\mathbb{F}_{p}\to\mathbb{R}$ with $\mathbb{E}f=0$ and
$\sum_{B\in\mathcal{C}_{2}}t_{L_{B}}(f)<0$.

However, to show that $L$ is uncommon over all sufficiently large $p$, we
should take into account subsystems in $\mathcal{C}_{1}$ as well. That is, we
wish to show that there is some function $h:\mathbb{F}_{p}^{n}\to\mathbb{R}$
with $\mathbb{E}h=0$ and $\sum_{B\in\mathcal{C}(L)}t_{L_{B}}(h)<0$, so that we
can utilize Proposition 2.4.

To do so, we take a “tensoring” of $f$ with the indicator function of 0.
Namely, define $h:\mathbb{F}_{p}^{2}\to\mathbb{R}$ by
$h(y,z)=f(y)\mathbf{1}_{z=0}$. Since $f$ has mean 0, so does $h$. Moreover,
for any $B\in\mathcal{C}(L)$, we have (with $c=c(L)$)

$\displaystyle t_{L_{B}}(h)$
$\displaystyle=\mathbb{E}_{\begin{subarray}{c}\mathbf{x}\in(\mathbb{F}_{p}^{2})^{c}\\\
L_{B}\mathbf{x}=0\end{subarray}}h(\mathbf{x}_{1})\cdots h(\mathbf{x}_{c})$
$\displaystyle=\mathbb{E}_{\begin{subarray}{c}\mathbf{y}\in\mathbb{F}_{p}^{c}\\\
L_{B}\mathbf{y}=0\end{subarray}}f(y_{1})\cdots
f(y_{c})\cdot\mathbb{E}_{\begin{subarray}{c}\mathbf{z}\in\mathbb{F}_{p}^{c}\\\
L_{B}\mathbf{z}=0\end{subarray}}\mathbf{1}_{z_{1}=0}\cdots\mathbf{1}_{z_{c}=0}$
$\displaystyle=t_{L_{B}}(f)t_{L_{B}}(\mathbf{1}_{z=0}).$

Observe that if $L_{B}$ is a length-$c$ equation, then it has $p^{c-1}$
solutions $\mathbf{z}\in\mathbb{F}_{p}^{c}$; if $L_{B}$ is a $2\times c$
linear system, then it has $p^{c-2}$ solutions
$\mathbf{z}\in\mathbb{F}_{p}^{c}$. Thus, we have

$\displaystyle
t_{L_{B}}(\mathbf{1}_{z=0})=\begin{cases}p^{1-c}&B\in\mathcal{C}_{1}\\\
p^{2-c}&B\in\mathcal{C}_{2}.\end{cases}$

Therefore, given that $\sum_{B\in\mathcal{C}_{2}}t_{L_{B}}(f)<0$, we have

$\displaystyle\sum_{B\in\mathcal{C}(L)}t_{L_{B}}(h)$
$\displaystyle=\sum_{B\in\mathcal{C}_{1}}t_{L_{B}}(h)+\sum_{B\in\mathcal{C}_{2}}t_{L_{B}}(h)$
$\displaystyle=p^{1-c}\sum_{B\in\mathcal{C}_{1}}t_{L_{B}}(f)+p^{2-c}\sum_{B\in\mathcal{C}_{2}}t_{L_{B}}(f),$

which is negative for $p$ sufficiently large. Thus, by Proposition 2.4, $L$ is
uncommon over all sufficiently large $p$. ∎

We are now ready to prove Theorem 1.9.

###### Proof.

By Proposition 4.9, it suffices to construct a Fourier template
$g:\mathbb{Z}\to\mathbb{C}$ such that

$\sum_{B\in\mathcal{C}_{2}}\sigma_{L_{B}}(g)<0.$

Suppose $\mathcal{C}_{2}(L)=\\{B_{1},\dots,B_{\ell}\\}$, with

$L_{B_{j}}=\begin{pmatrix}a_{j,1}&\dots&a_{j,c}\\\
b_{j,1}&\dots&b_{j,c}\end{pmatrix}\qquad\text{ for every $j\in[\ell]$.}$

Define the random Fourier template $f_{M}:\mathbb{Z}\to\mathbb{C}$ as in
Proposition 4.7. Also, choose $\lambda\in\mathbb{N}$ sufficiently large such
that if $a_{j,1}r_{1}+b_{j,1}r_{2},\dots,a_{j,k}r_{1}+b_{j,k}r_{2}$ lie in
$[\\![-M,M]\\!]\setminus\\{0\\}$ for all $j\in[\ell]$, then $-\lambda M\leq
r_{1},r_{2}\leq\lambda M$.

For every $(r_{1},r_{2})\in[\\![-N,N]\\!]$, define the associated multisets

$\displaystyle S_{(r_{1},r_{2})}^{1}$
$\displaystyle=\\{\\!\\!\\{a_{1,1}r_{1}+b_{1,1}r_{2},\dots,a_{1,k}r_{1}+b_{1,k}r_{2}\\}\\!\\!\\},$
$\displaystyle\vdots$ $\displaystyle S_{(r_{1},r_{2})}^{\ell}$
$\displaystyle=\\{\\!\\!\\{a_{\ell,1}r_{1}+b_{\ell,1}r_{2},\dots,a_{\ell,k}r_{1}+b_{\ell,k}r_{2}\\}\\!\\!\\}.$

We then have

$\sum_{B\in\mathcal{C}_{2}}\sigma_{L_{B}}(f_{M})=\sum_{r_{1},r_{2}\in[\\![-N,N]\\!]}\sum_{j=1}^{\ell}X_{S^{j}_{(r_{1},r_{2})}}.$

Let $\rho$ denote the standard deviation of
$\sum_{r_{1},r_{2}\in[\\![-N,N]\\!]}\sum_{j=1}^{\ell}X_{S^{\ell}_{(r_{1},r_{2})}}$,
and define

$W=\rho^{-1}\sum_{r_{1},r_{2}\in[\\![-N,N]\\!]}\sum_{j=1}^{\ell}X_{S^{\ell}_{(r_{1},r_{2})}}.$

An argument almost identical to Proposition 4.7 shows that

$\mathbb{P}\Big{(}\sum_{B\in\mathcal{C}_{2}}\sigma_{L_{B}}(f_{M})<0\Big{)}>0$

for all $M$ sufficiently large. In particular, there exists Fourier template
$g:\mathbb{Z}\to\mathbb{C}$ such that
$\sum_{B\in\mathcal{C}_{2}}\sigma_{L_{B}}(g)<0$. Finally, by Proposition 4.9,
we know that $L$ is uncommon over $\mathbb{F}_{p}$ for all $p$ sufficiently
large. ∎

##  5\. Proof of Theorem 1.10

###  5.1. Introduction

In this section, we prove Theorem 1.10. Let $L$ be an irredundant $2\times 5$
linear system on variables $x_{1},\dots,x_{5}$. The bulk of Theorem 1.10
considers the case $s(L)=4$. Under the assumption $s(L)=4$, we know that the
elements in $\\{L_{B}:B\in\mathcal{C}(L)\\}$ of $L$ are five length-4 linear
equations, supported on five different 4-subsets of $\\{x_{1},\dots,x_{5}\\}$.

Let $L_{1},\dots,L_{5}$ denote these five equations. By Theorem 3.5, to show
that $L$ is uncommon, it suffices to find a Fourier template
$g\colon\mathbb{Z}^{d}\to\mathbb{C}$ such that
$\sum_{i=1}^{5}\sigma_{L_{i}}(g)<0$. Since each $\sigma_{L_{i}}(g)$ is defined
by both $g$ and the coefficients in $L_{i}$, to simplify our further
discussion, we give special names to the set of coefficients in each $L_{i}$.

######  Setup 5.1.

Suppose $L$ is an irredundant $2\times 5$ linear system with $s(L)=4$. For
every $i=1,\dots,5$, we admit the following notation:

  * •

Let $L_{i}\mathbf{x}:=a_{i,1}x_{1}+\dots+a_{i,5}x_{5}$ be the unique (up to
constant multiplication) equation in the row span of $L$, such that
$a_{i,i}=0$.

  * •

Let $A_{i}=\\{\\!\\!\\{a_{i,j}:j\in[5],\,j\neq i\\}\\!\\!\\}$ be the multiset
of nonzero coefficients in $L_{i}$.

  * •

For every Fourier template $g:\mathbb{Z}^{d}\to\mathbb{C}$, define the
associated function $g_{A_{i}}:\mathbb{Z}^{d}\to\mathbb{C}$ by

$g_{A_{i}}(r):=\prod_{a\in A_{i}}g(ar)$

and the associated sum $\sigma_{A_{i}}(g)$ by

$\sigma_{A_{i}}(g)=\sum_{r\in\mathbb{Z}^{d}}g_{A_{i}}(r),$

so that $g_{A_{i}}=g_{L_{i}}$ and $\sigma_{A_{i}}(g)=\sigma_{L_{i}}(g)$ as in
Definition 3.3.

Suppose we wish to show that $L$ is uncommon, and hope to find some Fourier
template $g$ with $\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$. This is easy if none of
$L_{1},\dots,L_{5}$ is common, as a random Fourier template
$g:\mathbb{Z}\to\mathbb{C}$ has
$\sum_{i=1}^{5}\mathbb{E}[\sigma_{A_{i}}(g)]=0$. However, if some equation
$L_{i_{0}}$ among $L_{1},\dots,L_{5}$ is common, with
$A_{i_{0}}=\\{\\!\\!\\{1,-1,\lambda,-\lambda\\}\\!\\!\\}$, then
$\sigma_{A_{i_{0}}}(g)=\sum_{r}|g(r)|^{2}|g(\lambda r)|^{2}$ must be a
positive contribution to $\sum_{i=1}^{5}\sigma_{A_{i}}(g)$. In this case, we
have to carefully pick some $g$ so that the other terms $\sigma_{A_{i}}(g)$,
$i\neq i_{0}$ are “negative enough” to balance out this positive term. Now, if
some $L_{i_{0}}$ is an additive quadruple
$L_{i_{0}}\mathbf{x}=x_{j_{1}}+x_{j_{2}}-x_{j_{3}}-x_{j_{4}}$, then we have
$A_{i_{0}}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$, and the sum
$\sigma_{A_{i_{0}}}(g)=\sum_{r}|g(r)|^{4}$ would be even harder to balance
out.

This motivates us to classify all the irredundant $2\times 5$ linear systems
$L$ according to the number of common equations and additive quadruples among
$L_{1},\dots,L_{5}$, and prove Theorem 1.10 under each case.

######  Lemma 5.2.

Let $L$ be an irredundant $2\times 5$ linear system, with $s(L)=4$. Then there
cannot be two additive quadruples among $L_{1},\dots,L_{5}$.

###### Proof.

Without loss of generality, suppose $L_{1}$ and $L_{2}$ are both additive
quadruple. Up to isomorphism, $L$ is one of

$\displaystyle\begin{pmatrix}0&1&1&-1&-1\\\
1&0&1&-1&-1\end{pmatrix},\,\begin{pmatrix}0&1&1&-1&-1\\\
1&0&-1&1&-1\end{pmatrix}.$

In either case, we have $s(L)\leq 3$, which is a contradiction. ∎

######  Corollary 5.3.

Let $L$ be an irredundant $2\times 5$ linear system, with $s(L)=4$. Then $L$
satisfies exactly one of the following:

  1. Case A.

None of $L_{1},\dots,L_{5}$ is an additive quadruple, and at least three of
them are uncommon.

  2. Case B.

Exactly one of $L_{1},\dots,L_{5}$ is an additive quadruple, and none of the
others is common.

  3. Case C.

Exactly one of $L_{1},\dots,L_{5}$ is an additive quadruple, and exactly one
among the others is common but not an additive quadruple.

  4. Case D.

At least three of $L_{1},\dots,L_{5}$ are common.

Our strategy of finding the appropriate Fourier template $g$ with
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$ differs in each case listed in Corollary
5.3. Before diving into the proof of Theorem 1.10, we provide some examples
illustrating our main ideas in Cases A, B and C.

In Case A, mostly, we aim to pick a Fourier template $g$ with
$\sigma_{A_{i_{0}}}(g)$ “very negative” for some uncommon $L_{i_{0}}$, while
keeping $\sum_{i\in[5],\,L_{i}\text{ common}}\sigma_{A_{i}}(g)$ relatively
small.

######  Example 5.4 (Case A).

Let $L$ be the linear system

$\begin{pmatrix}1&3&-1&-3&0\\\ 2&3&-3&0&-2\end{pmatrix}.$

We then have

$\displaystyle L_{5}\mathbf{x}$
$\displaystyle=x_{1}+3x_{2}-x_{3}-3x_{4}\qquad\qquad$ $\displaystyle
A_{5}=\\{\\!\\!\\{1,3,-1,-3\\}\\!\\!\\}$ $\displaystyle L_{4}\mathbf{x}$
$\displaystyle=2x_{1}+3x_{2}-3x_{3}-2x_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{2,3,-3,-2\\}\\!\\!\\}$ $\displaystyle L_{3}\mathbf{x}$
$\displaystyle=x_{1}+6x_{2}-9x_{4}+2x_{5}$ $\displaystyle
A_{3}=\\{\\!\\!\\{1,6,-9,2\\}\\!\\!\\}$ $\displaystyle L_{2}\mathbf{x}$
$\displaystyle=x_{1}-2x_{3}+3x_{4}-2x_{5}$ $\displaystyle
A_{2}=\\{\\!\\!\\{1,-2,3,-2\\}\\!\\!\\}$ $\displaystyle L_{1}\mathbf{x}$
$\displaystyle=3x_{2}+x_{3}-6x_{4}+2x_{5}$ $\displaystyle
A_{1}=\\{\\!\\!\\{3,1,-6,2\\}\\!\\!\\}.$

We wish to find a Fourier template $g:\mathbb{Z}\to\mathbb{C}$ such that

$\displaystyle\sum_{r\in\mathbb{Z}}(|g(r)|^{2}|g(3r)|^{2}+|g(2r)|^{2}|g(3r)|^{2}$
$\displaystyle\qquad\quad+g(r)g(6r)g(-9r)g(2r)+g(r)g(-2r)g(3r)g(-2r)+g(3r)g(r)g(-6r)g(2r))$
$\displaystyle=\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0.$

Observe that the first two terms always have nonnegative contribution. This
motivates us to find some $g$ that makes one of the last three terms “very
negative” without making the first two terms “too positive”.

For example, consider the Fourier template $g:\mathbb{Z}\to\mathbb{C}$ defined
by

$\displaystyle\begin{cases}g(2)=g(-2)=g(6)=g(-6)=g(9)=g(-9)=1\\\
g(1)=g(-1)=-100\\\ g(r)=0\quad\text{otherwise.}\end{cases}$

We then have

$\sum_{r\in\mathbb{Z}}g(r)g(6r)g(-9r)g(2r)=g(1)g(6)g(-9)g(2)+g(-1)g(-6)g(9)g(-2)=-200,$

while other terms

$\displaystyle\sum_{r\in\mathbb{Z}}|g(r)|^{2}|g(3r)|^{2}=|g(2)|^{2}|g(6)|^{2}+|g(-2)|^{2}|g(-6)|^{2}=2,$
$\displaystyle\sum_{r\in\mathbb{Z}}|g(2r)|^{2}|g(3r)|^{2}=|g(6)|^{2}|g(9)|^{2}+|g(-6)|^{2}|g(-9)|^{2}=2,$
$\displaystyle\sum_{r\in\mathbb{Z}}g(r)g(-2r)g(3r)g(-2r)=\sum_{r\in\mathbb{Z}}g(3r)g(r)g(-6r)g(2r)=0$

have small absolute value. Altogether, we get that
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)=-196<0$.

We will discuss Case A further in Section 5.2.

In Case B, we continue to work with the Fourier template
$g\colon\mathbb{Z}\to\mathbb{C}$. However, the strategy in Case A fails in the
presence of an additive quadruple, because setting $|g(r)|$ to be big for any
particular $r\in\mathbb{Z}$ will make $|g(r)|^{4}$, the term contributed by
the additive quadruple, blow-up the fastest.

As such, we need to crucially use the fact that we have at least four uncommon
equations, say $A_{1},\ldots,A_{4}$. In Case B, our construction is roughly in
two steps:

  * •

We construct our Fourier template to have support in some
$S\subseteq\mathbb{Z}$ such that there are many nonvanishing terms in
$\sum_{i=1}^{4}\sum_{r\in S}g_{A_{i}}(r)$. We do this by taking $S$ to be a
_multiplicative grid_ , illustrated in the example below.

  * •

Next, we choose each $g(r)$ to be complex numbers with appropriate phases that
align in a way to ensure that $\sum_{i=1}^{4}\sigma_{A_{i}}(g)$ is a complex
vector with negative real part.

The details of this procedure is also illustrated in the example below.

######  Example 5.5 (Case B).

Let $L$ be the $2\times 5$ linear system

$\displaystyle\begin{pmatrix}1&-1&1&-1&0\\\ -2&4&3&0&-9\end{pmatrix}.$

We then have

$\displaystyle L_{5}\mathbf{x}$
$\displaystyle=x_{1}-x_{2}+x_{3}-x_{4}\qquad\qquad$ $\displaystyle
A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$ $\displaystyle L_{4}\mathbf{x}$
$\displaystyle=-2x_{1}+4x_{2}+3x_{3}-9x_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{-2,4,3,-9\\}\\!\\!\\}$ $\displaystyle L_{3}\mathbf{x}$
$\displaystyle=5x_{1}-7x_{2}-3x_{4}+9x_{5}$ $\displaystyle
A_{3}=\\{\\!\\!\\{5,-7,-3,9\\}\\!\\!\\}$ $\displaystyle L_{2}\mathbf{x}$
$\displaystyle=2x_{1}+7x_{3}-4x_{4}-9x_{5}$ $\displaystyle
A_{2}=\\{\\!\\!\\{2,7,-4,-9\\}\\!\\!\\}$ $\displaystyle L_{1}\mathbf{x}$
$\displaystyle=2x_{2}+5x_{3}-2x_{4}-9x_{5}$ $\displaystyle
A_{1}=\\{\\!\\!\\{2,5,-2,-9\\}\\!\\!\\}.$

Again, we wish to find a Fourier template $g:\mathbb{Z}\to\mathbb{C}$ such
that

$\displaystyle\sum_{r\in\mathbb{Z}}(|g(r)|^{4}+g(-2r)g(4r)g(3r)g(-9r)+g(5r)g(-7r)g(-3r)g(9r)$
$\displaystyle\qquad\qquad\qquad+g(2r)g(7r)g(-4r)g(-9r)+g(2r)g(5r)g(-2r)g(-9r))$
$\displaystyle=\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0.$

Since $L$ contains an additive quadruple, we cannot hope to use a construction
similar to Example 5.4, as enlarging $|g(r)|$ for any particular $r$ would
make $\sum_{r\in\mathbb{Z}}|g(r)|^{4}$ the dominant term.

Instead, we build some Fourier template whose support is “almost closed” under
multiplication by any coefficient in $A_{1},\dots,A_{5}$. Consider the
_multiplicative grid_ $G$ defined by

$G=\\{2^{d_{1}}3^{d_{2}}5^{d_{3}}7^{d_{4}}:d_{1},\dots,d_{4}\in\\{0,1,\dots\\}\\}\subseteq\mathbb{N}.$

We can think of $G$ as a four-dimensional grid, with each dimension
corresponding to a prime divisor. Here we include $2,3,5,7$ as they are
precisely the prime divisors of elements in $A_{1}\cup\dots\cup A_{5}$.
Consequently, $G$ has the nice property that $\pm 2G,\pm 3G,\pm 4G,\pm 5G,\pm
7G,\pm 9G\subseteq\pm G$; in other words, $\pm G$ is closed under
multiplication by any coefficient in $A_{1}\cup\dots\cup A_{5}$.

However, a Fourier template must have finite support, and therefore cannot be
nonzero on the whole of $\pm G$. Therefore, we will first build some $g:\pm
G\to\mathbb{C}$, and eventually replace it by its restriction on $\pm G_{D}$ ,
where

$G_{D}=\\{2^{d_{1}}3^{d_{2}}5^{d_{3}}7^{d_{4}}:d_{1},\dots,d_{4}\in\\{0,1,\dots,D\\}\\}$

is a finite truncation of $G$.

Our $g:\pm G\to\mathbb{C}$ will be of the form

$\begin{cases}g(2^{d_{1}}3^{d_{2}}5^{d_{3}}7^{d_{4}})=e((\theta_{1}d_{1}+\theta_{2}d_{2}+\theta_{3}d_{3}+\theta_{4}d_{4})t)\\\
g(-2^{d_{1}}3^{d_{2}}5^{d_{3}}7^{d_{4}})=e(-(\theta_{1}d_{1}+\theta_{2}d_{2}+\theta_{3}d_{3}+\theta_{4}d_{4})t)\end{cases}$

where $\theta_{1},\dots,\theta_{4}\in\mathbb{Q}$ and $t\in\mathbb{R}$. In
other words, $g$ is the composition of $e(\cdot)$ and a “linear map” from the
multidimensional grid $G$ to $\mathbb{R}$. This choice of $g$ will ensure that
the phases of $\sigma_{A_{i}}(g)$ line up in a way to ensure that
$\sum_{i=2}^{5}\sigma_{A_{i}}(g)$ is very negative.

Observe that $|g(r)|=1$ for all $r\in\pm G$. Moreover, for all $x,y\in G$, we
have $g(xy)=g(x)g(y)$ and $g(-xy)=g(-x)g(-y)$. Hence for all $r\in\pm G$, we
have

$\displaystyle g(-2r)g(4r)g(3r)g(-9r)=\begin{cases}g(-2)g(4)g(3)g(-9)\cdot
g(r)^{2}g(-r)^{2}=e((\theta_{1}-\theta_{2})t)&r\in G\\\
g(2)g(-4)g(-3)g(9)\cdot
g(r)^{2}g(-r)^{2}=e((\theta_{2}-\theta_{1})t)&r\in-G.\end{cases}$

Similarly, we have

$\displaystyle g(5r)g(-7r)g(-3r)g(9r)$
$\displaystyle=\begin{cases}e((\theta_{2}+\theta_{3}-\theta_{4})t)&r\in G\\\
e((-\theta_{2}-\theta_{3}+\theta_{4})t)&r\in-G\end{cases}$ $\displaystyle
g(2r)g(7r)g(-4r)g(-9r)$
$\displaystyle=\begin{cases}e((-\theta_{1}-2\theta_{2}+\theta_{4})t)&r\in G\\\
e((\theta_{1}+2\theta_{2}-\theta_{4})t)&r\in-G\end{cases}$ $\displaystyle
g(2r)g(5r)g(-2r)g(-9r)$
$\displaystyle=\begin{cases}e((-2\theta_{2}+\theta_{3})t)&r\in G\\\
e((2\theta_{2}-\theta_{3})t)&r\in-G.\end{cases}$

Therefore, for all $r\in\pm G$, we have

$\displaystyle\sum_{i=1}^{5}\text{Re}(g_{A_{i}}(r))$
$\displaystyle=1+\cos((\theta_{1}-\theta_{2})t)+\cos((\theta_{2}+\theta_{3}-\theta_{4})t)+\cos((-\theta_{1}-2\theta_{2}+\theta_{4})t)+\cos((-2\theta_{2}+\theta_{3})t).$

Setting $\theta_{1}=\theta_{3}=1$, $\theta_{2}=\theta_{4}=0$ and $t=\pi$, we
get that

$\displaystyle\sum_{i=1}^{5}\text{Re}(g_{A_{i}}(r))$
$\displaystyle=1+\cos\pi+\cos\pi+\cos(-\pi)+\cos\pi=-3.$

Finally, we switch our attention from $g$ to its restriction on $\pm G_{D}$.
Consider the Fourier template $g_{D}:\mathbb{Z}\to\mathbb{C}$ defined by

$\displaystyle
g_{D}(r)=\begin{cases}e((\theta_{1}d_{1}+\theta_{2}d_{2}+\theta_{3}d_{3}+\theta_{4}d_{4})t)&r=2^{d_{1}}3^{d_{2}}5^{d_{3}}7^{d_{4}}\in
G_{D}\\\
e(-(\theta_{1}d_{1}+\theta_{2}d_{2}+\theta_{3}d_{3}+\theta_{4}d_{4})t)&r=-2^{d_{1}}3^{d_{2}}5^{d_{3}}7^{d_{4}}\in-
G_{D}\\\ 0&\text{otherwise.}\end{cases}$

Observe that if $r\notin\pm G_{D}$, then $(g_{D})_{A_{i}}(r)=0$ for all
$i\in[5]$. Moreover, for those $r\in\pm G_{D}$ such that
$r,2r,4r,3r,9r,5r,7r\in\pm G_{D}$, we have
$\sum_{i=1}^{5}\text{Re}((g_{D})_{A_{i}}(r))=\sum_{i=1}^{5}\text{Re}(g_{A_{i}}(r))=-3$.
Since

$\lim_{D\to\infty}\frac{|\\{r\in\pm G_{D}:r,2r,4r,3r,9r,5r,7r\in
G_{D}\\}|}{|\pm G_{D}|}=1,$

we get that

$\displaystyle\lim_{D\to\infty}\frac{\sum_{i=1}^{5}\sigma_{A_{i}}(g_{D})}{|\pm
G_{D}|}=\lim_{D\to\infty}\frac{\sum_{r\in\pm
G_{D}}\sum_{i=1}^{5}\text{Re}((g_{D})_{A_{i}}(r))}{|\pm G_{D}|}=-3$

(recall from Remark 3.4 that $\sigma_{A_{i}}(g_{D})$ is always real). Taking
$D$ sufficiently large, we can obtain the desired Fourier template $g_{D}$
with $\sum_{i=1}^{5}\sigma_{A_{i}}(g_{D})<0$.

We discuss Case B further in Section 5.3.

Case B covers the case where exactly one of $L_{1},\dots,L_{5}$ is additive
quadruple, and the other four are uncommon. What if one of the other four
becomes common? The following examples illustrates why the construction in
Case B fails and what the alternate strategy is.

######  Example 5.6 (Case C).

Let $L$ be the $2\times 5$ linear system

$\displaystyle\begin{pmatrix}1&1&-1&-1&0\\\ 1&-1&4&0&-4\end{pmatrix}.$

We then have

$\displaystyle L_{5}\mathbf{x}$
$\displaystyle=x_{1}+x_{2}-x_{3}-x_{4}\qquad\qquad$ $\displaystyle
A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$ $\displaystyle L_{4}\mathbf{x}$
$\displaystyle=x_{1}-x_{2}+4x_{3}-4x_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{1,-1,4,-4\\}\\!\\!\\}$ $\displaystyle L_{3}\mathbf{x}$
$\displaystyle=5x_{1}+3x_{2}-4x_{4}-4x_{5}$ $\displaystyle
A_{3}=\\{\\!\\!\\{3,5,-4,-4\\}\\!\\!\\}$ $\displaystyle L_{2}\mathbf{x}$
$\displaystyle=2x_{1}+3x_{3}-1x_{4}-4x_{5}$ $\displaystyle
A_{2}=\\{\\!\\!\\{2,3,-1,-4\\}\\!\\!\\}$ $\displaystyle L_{1}\mathbf{x}$
$\displaystyle=2x_{2}-5x_{2}-1x_{4}+4x_{5}$ $\displaystyle
A_{1}=\\{\\!\\!\\{2,-5,-1,4\\}\\!\\!\\}.$

The difference between this example and Example 5.5 is that, in addition to
the additive quadruple $L_{5}$, we have another common linear equation
$L_{4}$.

Let us first try the strategy in Example 5.5. Since $2,3,5$ are the prime
divisors of at least one coefficient in $L_{1},\dots,L_{5}$, consider the
multiplicative grid

$G=\\{2^{d_{1}}3^{d_{2}}5^{d_{3}}:d_{1},d_{2},d_{3}\in\\{0,1,\dots\\}\\}$

and some $g:\pm G\to\mathbb{C}$ of the form

$\begin{cases}g(2^{d_{1}}3^{d_{2}}5^{d_{3}})=e((\theta_{1}d_{1}+\theta_{2}d_{2}+\theta_{3}d_{3})t)\\\
g(-2^{d_{1}}3^{d_{2}}5^{d_{3}})=e(-(\theta_{1}d_{1}+\theta_{2}d_{2}+\theta_{3}d_{3})t).\end{cases}$

We wish to find some $\theta_{1},\theta_{2},\theta_{3},t\in\mathbb{R}$ such
that for all $r\in\pm G$, we have

$\displaystyle 0>\sum_{i=1}^{5}\text{Re}(g_{A_{i}}(r))$
$\displaystyle=|g(r)|^{4}+|g(r)|^{2}|g(4r)|^{2}+g(5r)g(3r)g(-4r)g(-4r)$
$\displaystyle\qquad+g(2r)g(3r)g(-r)g(-4r)+g(-2r)g(5r)g(r)g(-4r)$
$\displaystyle=2+\cos((-4\theta_{1}+\theta_{2}+\theta_{3})t)+\cos((-\theta_{1}+\theta_{2})t)+\cos((-3\theta_{1}+\theta_{3})t).$

However, since there are no $\alpha,\beta\in\mathbb{R}$ with
$\cos\alpha+\cos\beta+\cos(\alpha+\beta)<-2$, we cannot find solutions
$\theta_{1},\theta_{2},\theta_{3},t\in\mathbb{R}$ to the above inequality.

This motivates us to pursue a different route. Instead of letting
$\sum_{i=1}^{5}\text{Re}(g_{A_{i}}(r))$ be constant for every $r\in\pm G$, we
choose some $g:\pm G\to\mathbb{C}$ that is “periodic” in the multiplicative
grid, so that $\sum_{i=1}^{5}\text{Re}(g_{A_{i}}(r))$ sums up to a negative
number within every period.

We construct some $g:\pm G_{L}\to\mathbb{C}$ so that for all
$d_{1},d_{2},d_{3}\in\\{0,1,\dots\\}$, we have
$g(2^{d_{1}}3^{d_{2}}5^{d_{3}})=g(2^{d_{1}+4}3^{d_{2}+2}5^{d_{3}+2})$. More
precisely, consider

$\displaystyle\begin{cases}g(2^{d_{1}}3^{d_{2}}5^{d_{3}})=h(\text{Mod}(d_{1},4),\text{Mod}(d_{2},2),\text{Mod}(d_{3},2))\\\
g(-2^{d_{1}}3^{d_{2}}5^{d_{3}})=\overline{h(\text{Mod}(d_{1},4),\text{Mod}(d_{2},2),\text{Mod}(d_{3},2))},\end{cases}$

where $h:\mathbb{Z}_{4}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\to\mathbb{C}$
is defined by

$\begin{matrix}[l]&h(0,0,0)=0.25+0.42i&h(1,0,0)=0&h(2,0,0)=-0.35+0.35i&h(3,0,0)=1-i\\\
&h(0,0,1)=0.35-0.35i&h(1,0,1)=-1-i&h(2,0,1)=0.48+0.12i&h(3,0,1)=0\\\
&h(0,1,0)=-0.35+0.35i&h(1,1,0)=-1-i&h(2,1,0)=0.48+0.12i&h(3,1,0)=0\\\
&h(0,1,1)=-0.25-0.42i&h(1,1,1)=0&h(2,1,1)=0.35-0.35i&h(3,1,1)=1-i.\end{matrix}$

One can check that, for all $r\in G$, we have

$\displaystyle\sum_{j=0}^{3}\sum_{k,\ell=0}^{1}\left(\sum_{i=1}^{5}g_{A_{i}}(2^{j}3^{k}5^{\ell}r)\right)$
$\displaystyle=\sum_{\begin{subarray}{c}j\in\mathbb{Z}_{4}\\\
k,\ell\in\mathbb{Z}_{2}\end{subarray}}(|h(j,k,\ell)|^{4}+|h(j,k,\ell)|^{2}|h(j+2,k,\ell)|+h(j,k,\ell+1)h(j,k+1,\ell)\overline{h(j+2,k,\ell)}^{2}$
$\displaystyle\qquad\quad+h(i+1,j,k)h(i,j+1,k)\overline{h(i,j,k)}\overline{h(i+2,j,k)}+\overline{h(i+1,j,k)}h(i,j,k+1)h(i,j,k)\overline{h(i+2,j,k)})$
$\displaystyle=-0.249573+0.723675i.$

Similarly, for all $r\in-G$, we have

$\sum_{j=0}^{3}\sum_{k,\ell=0}^{1}\left(\sum_{i=1}^{5}g_{A_{i}}(2^{j}3^{k}5^{\ell}r)\right)=-0.249573-0.723675i.$

As before, let $g_{D}:\mathbb{Z}\to\mathbb{C}$ be the restriction of $g$ on
the finite truncation $\pm G_{D}$, so that $g_{D}$ is a Fourier template.
Since

$\lim_{D\to\infty}\frac{|\\{r\in\pm
G_{D}:\\{1,2,4,8\\}\times\\{1,3\\}\times\\{1,5\\}\times r\subseteq\pm
G_{D}\\}|}{|\pm G_{D}|}=1,$

we get that

$\lim_{D\to\infty}\frac{\sum_{i=1}^{5}\sigma_{A_{i}}(g_{D})}{|\pm
G_{D}|/16}=-0.249573<0.$

Taking $D$ sufficiently large, we can obtain the desired Fourier template
$g_{D}$ with $\sum_{i=1}^{5}\sigma_{A_{i}}(g_{D})<0$.

In general, to prove Theorem 1.10 under Case C, we will repeatedly use and
generalize the above function $h$. At this point, it might not be intuitive
why the values of $h(i,j,k)$ are chosen in this way, and how they can be
generalized. We will discuss this further in Section 5.4, which hopefully will
explain more to the readers.

The above three cases form the majority of the proof of Theorem 1.10. Case D
does not have many possibilities, as each linear system under Case D can be
parameterized by one single variable; we will prove Theorem 1.10 under Case D
in Section 5.5. In Section 5.6, we will show Theorem 1.10 for $2\times 5$
linear systems with girth $s(L)\leq 3$. Finally, in Section 5.7, we show
commonness of the several linear systems indicated in Theorem 1.10.

Having illustrated some of our proof strategies, we now begin the proof of
Theorem 1.10.

###  5.2. Proof of Theorem 1.10 under Case A

In this section, we prove Theorem 1.10 under Case A listed in Corollary 5.3.

######  Definition 5.7.

Suppose $L$ is an irredundant $2\times 5$ system with $s(L)=4$. Recall 5.1.

  * •

For $i\in[5]$ and $\lambda\in\mathbb{Q}\setminus\\{0\\}$, we say that $L_{i}$
is $\lambda$-common if $A_{i}$ is of the form $\\{\\!\\!\\{a,-a,\lambda
a,-\lambda a\\}\\!\\!\\}$.

  * •

For $a,b\in\mathbb{Q}$, we say that $a,b$ are _$L$ -coincidental_ if there
exist $\lambda\in\\{\pm a/b,\pm b/a\\}$ and $i\in[5]$ such that $L_{i}$ is
$\lambda$-common.

Suppose $L$ is a linear system that falls under Case A listed in Corollary
5.3. We show that $L$ is always uncommon. This follows from combining the
following two statements:

  1. (1)

(Lemma 5.8) If $L$ falls under Case A in Corollary 5.3, then there exists
$A_{i}$ that cannot be partitioned into two $L$-coincidental pairs.

  2. (2)

(Lemmas 5.10 and 5.9) If for some $i\in[5]$, $A_{i}$ cannot be partitioned
into two $L$-coincidental pairs, then $L$ is uncommon.

Note that, if $A_{i}$ cannot be partitioned into two $L$-coincidental pairs,
then one of the following occurs:

    1. (a)

there exists $a\in A_{i}$ that is not $L$-coincidental with any element in
$A_{i}\setminus\\{a\\}$,

    2. (b)

there exists $a\in A_{i}$ that is $L$-coincidental with every element in
$A_{i}\setminus\\{a\\}$, while no two of the three elements in
$A_{i}\setminus\\{a\\}$ are $L$-coincidental.

In particular, Lemma 5.9 shows that $L$ is uncommon when (a) occurs, and Lemma
5.10 shows that $L$ is uncommon when (b) occurs.

The detailed statements are as follows.

######  Lemma 5.8.

Suppose $L$ is an irredundant $2\times 5$ linear system that falls under Case
A in Corollary 5.3. Assume 5.1. Then there exists $i\in[5]$ such that $A_{i}$
cannot be partitioned into two $L$-coincidental pairs.

######  Lemma 5.9.

Suppose $L$ is an irredundant $2\times 5$ linear system that falls under Case
A in Corollary 5.3. Assume 5.1. If there exists $i\in[5]$ and $a\in A_{i}$
such that $a$ is not $L$-coincidental with any element in
$A_{i}\setminus\\{a\\}$, then there exists a Fourier template
$g:\mathbb{Z}^{d}\to\mathbb{C}$ such that $\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$.

######  Lemma 5.10.

Suppose $L$ is an irredundant $2\times 5$ linear system that falls under Case
A in Corollary 5.3. Assume 5.1. Moreover, suppose:

  1. (1)

for every $i\in[5]$ and every $a\in A_{i}$, there is some $b\in
A_{i}\setminus\\{a\\}$ such that $a,b$ are $L$-coincidental.

  2. (2)

there exists $i_{0}\in[5]$,
$A_{i_{0}}=\\{\\!\\!\\{a_{0},b_{0},c_{0},d_{0}\\}\\!\\!\\}$ such that:

     * •

$a_{0}$ is $L$-coincidental with each of $b_{0},c_{0},d_{0}$,

     * •

$b_{0},c_{0},d_{0}$ are pairwise not $L$-coincidental.

Then there exists a Fourier template $g:\mathbb{Z}\to\mathbb{C}$ such that
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$.

The proof of Lemma 5.10 is effectively a generalization of Example 5.4.

###### Proof of Lemma 5.10.

Consider the Fourier template $g:\mathbb{Z}\to\mathbb{C}$ defined by

$\displaystyle\begin{cases}g(a_{0})=g(-a_{0})=1\\\
g(b_{0})=g(-b_{0})=g(c_{0})=g(-c_{0})=g(d_{0})=g(-d_{0})=-C\\\
g(r)=0\quad\text{otherwise.}\end{cases}$

We then have $\sigma_{A_{i_{0}}}(g)=-2C^{3}$. Moreover, because of condition
(1) in the lemma statement, there is no $i\in[5]$ such that $A_{i}$ has all
elements lying in $\\{\pm b_{0},\pm c_{0},\pm d_{0}\\}$. Therefore, for all
$i\in[5]$, we either have $\sigma_{A_{i}}(g)=-2C^{3}$ or
$|\sigma_{A_{i}}(g)|=O(C^{2})$. This gives $\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$
when $C>0$ is sufficiently large. ∎

The proof of Lemma 5.9 has more case discussions than Lemma 5.10, although the
underlying principle is identical. Similarly, the proof of Lemma 5.8 is
routine. As such, we defer the proofs of these lemmas to Section B.1.

###  5.3. Proof of Theorem 1.10 under Case B

In this section, we prove Theorem 1.10 under Case B of Corollary 5.3. In this
case, we always assume the following setup:

######  Setup 5.11.

Suppose

$\displaystyle L_{5}\mathbf{x}$ $\displaystyle=x_{1}+x_{2}-x_{3}-x_{4}$
$\displaystyle A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$ $\displaystyle
L_{4}\mathbf{x}$ $\displaystyle=ax_{1}+bx_{2}+cx_{3}+dx_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{a,b,c,d\\}\\!\\!\\}$ $\displaystyle L_{3}\mathbf{x}$
$\displaystyle=(a+c)x_{1}+(b+c)x_{2}-cx_{4}+dx_{5}\qquad$ $\displaystyle
A_{3}=\\{\\!\\!\\{a+c,b+c,-c,d\\}\\!\\!\\}$ $\displaystyle L_{2}\mathbf{x}$
$\displaystyle=(a-b)x_{1}+(b+c)x_{3}+bx_{4}+dx_{5}$ $\displaystyle
A_{2}=\\{\\!\\!\\{a-b,b+c,b,d\\}\\!\\!\\}$ $\displaystyle L_{1}\mathbf{x}$
$\displaystyle=(b-a)x_{3}+(a+c)x_{3}+ax_{4}+dx_{5}$ $\displaystyle
A_{1}=\\{\\!\\!\\{b-a,a+c,a,d\\}\\!\\!\\}$

with $a,b,c,d\in\mathbb{Z}\setminus\\{0\\}$, and none of $L_{1},\dots,L_{4}$
is common. By replacing $a,b,c,d$ by their negations if necessary, we may
suppose that at least two of $a,b,c,d$ are positive.

We aim to show that $L$ is always uncommon. As in Example 5.5, the proof
strategy is in two steps:

  1. (1)

First, we construct an appropriate “multiplicative grid” $G_{L}$ which is the
support of the Fourier template $g$.

  2. (2)

Next, we set the values of $g(r)$ for $r\in G_{L}$ to be some complex numbers
so that the phases align in a way for $\sum_{i=1}^{5}\sigma_{A_{i}}(g)$ to be
negative. We will in fact choose $g$ to be the finite truncation of some
$h:\pm G_{L}\to\mathbb{C}$ where each $h_{A_{i}}$ is periodic (in some
suitable sense that we will define) on $G_{L}$. Most of the times $h$ will
look like the functions in Example 5.5, given by the composition of $e(\cdot)$
with a linear map from $G_{L}\to\mathbb{R}$.

As such, we begin by defining the “multiplicative grid” $G_{L}$ associated to
a $2\times 5$ linear system $L$ as follows.

######  Definition 5.12.

Let $L$ be a $2\times 5$ linear system with $s(L)=4$.

  * •

Let $P_{L}=\\{p_{1},\dots,p_{\ell}\\}=\\{p:p\text{ is a prime divisor of some
element in }A_{1}\cup\dots\cup A_{5}\\}$.

  * •

Let $G_{L}=\\{p_{1}^{d_{1}}\cdots
p_{\ell}^{d_{\ell}}:d_{1},\dots,d_{\ell}\in\\{0,1,\dots\\}\\}$.

For a function $h:\pm G_{L}\to\mathbb{C}$, $i\in[5]$ and
$\vec{u}=(u_{1},\dots,u_{\ell})\in\mathbb{N}^{\ell}$, we say that $h_{A_{i}}$
is _$\vec{u}$ -periodic_ if for all $r\in G_{L}$, we have

$h_{A_{i}}(r)=h_{A_{i}}(p_{1}^{u_{1}}\cdots p_{\ell}^{u_{\ell}}\cdot r).$

######  Remark 5.13.

We note that while a more natural definition for $\vec{u}$-periodicity is
$h(r)=h(p_{1}^{u_{1}}\cdots p_{\ell}^{u_{\ell}}\cdot r)$ – and some of our
constructions satisfy this stronger periodicity condition – we do need the
more general notion of periodicity in Definition 5.12 for the construction
given in Example 5.5.

Now, we construct a function $h\colon\pm G_{L}\to\mathbb{C}$ such that
$h_{A_{1}},\dots,h_{A_{5}}$ are $\vec{u}$-periodic on $G_{L}$ and has the
“phase cancellation” property on a period. That is,

$\mathrm{Re}\sum_{\begin{subarray}{c}0\leq d_{1}\leq u_{1}-1\\\ \vdots\\\
0\leq d_{\ell}\leq
u_{\ell}-1\end{subarray}}\sum_{i=1}^{5}h_{A_{i}}(p_{1}^{d_{1}}\ldots
p_{\ell}^{d_{\ell}}\cdot r)<0.$ (4)

It turns out that the above is enough to guarantee the existence of a Fourier
template $g\colon\mathbb{Z}\to\mathbb{C}$ such that
$\mathrm{Re}(\sigma_{A_{i}}(g))<0$. We have seen some version of this idea in
Example 5.5.

######  Lemma 5.14.

Let $L$ be a $2\times 5$ system with $s(L)=4$ and suppose $G_{L}$ is the
associated multiplicative grid as in Definition 5.12. Condier $h\colon\pm
G_{L}\to\mathbb{C}$ such that $h(-r)=\overline{h(r)}$ for all $r\in G_{L}$.
Suppose $h_{A_{1}},\dots,h_{A_{5}}$ are $\vec{u}$-periodic for some
$\vec{u}\in\mathbb{N}^{\ell}$, such that 4 holds. Then there exists a Fourier
template $g\colon\mathbb{Z}\to\mathbb{C}$ such that
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$.

We defer the formal proof of Lemma 5.14 to Section B.2. However, the main idea
is just the last part of Example 5.5. Roughly speaking, we “tessellate” enough
copies of $h$ on a sufficiently large truncation $\pm G_{D}$, where
$G_{D}=\\{p_{1}^{d_{1}}\cdots
p_{\ell}^{d_{\ell}}:d_{1},\dots,d_{\ell}\in\\{0,1,\dots,D\\}\\}\subseteq
G_{L}$. Then, we will define the Fourier template $g:\pm G_{D}\to\mathbb{C}$
by

$g(r)=h(r)\qquad\text{for every }r\in\pm G_{D}$

(so the support of $g$ is $\pm G_{D}\subseteq\mathbb{Z}$, which is finite). By
choosing $D$ large, we can ensure that the terms involved in the “wrap
around”/boundary terms in $\sum_{i=1}^{5}\sigma_{A_{i}}(g)$ is much smaller
than the number of main terms coming from terms in 4, and so the overall sum
stays negative.

As such, in what follows, we restrict our attention to constructing periodic
functions on $\pm G_{L}$ that sum to a negative value in its period. Depending
on the properties of $A_{1},\ldots,A_{5}$, we construct $h$ as a suitable
product formed from four special “primitive functions”:
$h_{1},h_{2},h_{3},h_{4}$.

######  Definition 5.15.

Let $A$ be a multiset of size 4. We say that $A$ is cancelling if $A$ is of
the form $\\{\\!\\!\\{a_{1},a_{2},b_{1},b_{2}\\}\\!\\!\\}$ such that
$a_{1},a_{2},-b_{1},-b_{2}\in\mathbb{N}$, with $a_{1}a_{2}=b_{1}b_{2}$.

We already know that $A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$. For each
$A_{i}$ among $A_{1},A_{2},A_{3},A_{4}$, we know that $A_{i}$ satisfies one of
the following:

  1. (i)

$A_{i}$ has four positive elements,

  2. (ii)

$A_{i}$ has three positive and one negative elements,

  3. (iii)

$A_{i}$ has two positive and two negative elements, but is not cancelling,

  4. (iv)

$A_{i}$ is cancelling (but not an additive quadruple).

Observe that if $A_{i}$ meets (i) or (ii), then we can pick very simple
functions $h:\pm G_{L}\to\mathbb{C}$ to make $h_{A_{i}}$ negative.

######  Observation 5.16.

There exist functions $h_{1},h_{2}:\pm G_{L}\to\mathbb{C}$, defined by

$\begin{cases}h_{1}(r)=e(1/8)&r\in G_{L}\\\ h_{1}(r)=e(-1/8)&r\in-
G_{L}\end{cases}\qquad\begin{cases}h_{2}(r)=i&r\in G_{L}\\\ h_{2}(r)=-i&r\in-
G_{L}\end{cases}$

such that, for all 4-multisets $A$, $(h_{1})_{A}$ and $(h_{2})_{A}$ are both
constant on $G_{L}$ with the following values:

$\displaystyle(h_{1})_{A}$ $\displaystyle=\begin{cases}-1&\text{$A$ has four
positive elements}\\\ i\text{ or }-i&\text{$A$ has three positive and one
negative elements}\\\ 1&\text{$A$ has two positive and two negative
elements,}\end{cases}$ $\displaystyle(h_{2})_{A}$
$\displaystyle=\begin{cases}-1&\text{$A$ has three positive and one negative
elements}\\\ 1&\text{$A$ has two positive and two negative
elements.}\end{cases}$

However, if some $A_{i}$, $i\in[4]$ has an equal number of positive and
negative elements, then we have $(h_{1})_{A_{i}}=(h_{2})_{A_{i}}=1$, so new
constructions are needed when this occurs.

We first discuss the case when all of $A_{1},\dots,A_{4}$ meets (iii). The
construction for this case generalizes that in Example 5.5.

######  Proposition 5.17.

Let $L$ be a $2\times 5$ system that falls under Case B in Corollary 5.3. Let
$G_{L}$ be the associated multiplicative grid as given by Definition 5.12.
Suppose $A_{5}$ is an additive quadruple, and each of $A_{1},\ldots,A_{4}$
contains an equal number of positive and negative elements, but is not
cancelling.

Then there exists a function $h_{3}\colon\pm G_{L}\to\mathbb{C}$ with
$h(-r)=\overline{h(r)}$ such that each $(h_{3})_{A_{i}}$, $i\in[5]$ is
constant on $G_{L}$. Furthermore,
$\mathrm{Re}\sum_{i=1}^{5}(h_{3})_{A_{i}}(r)<0$ for every $r\in\pm G_{L}$.

In the proof of Proposition 5.17, we will need the following fact, whose proof
we put in Section B.2. 5.18 is the driving force behind the idea of getting
the phases of $h_{A_{i}}(r)$ to align and produce a negative real value.

######  Fact 5.18.

For all
$\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}\in\mathbb{Q}\setminus\\{0\\}$,
there exists $t\in\mathbb{R}$ such that
$1+\cos(\gamma_{1}t)+\cos(\gamma_{2}t)+\cos(\gamma_{3}t)+\cos(\gamma_{4}t)<0$.

The proof of Proposition 5.17 generalizes what we saw in Example 5.5.

###### Proof of Proposition 5.17.

Recall that

$P_{L}=\\{p_{1},\dots,p_{\ell}\\}=\\{p:p\text{ is a prime divisor of some
element in }A_{1}\cup\dots\cup A_{5}\\}.$

For some $\theta_{1},\dots,\theta_{\ell}\in\mathbb{Q}$ and $t\in\mathbb{R}$ to
be chosen later, define $h_{3}:\pm G_{L}\to\mathbb{C}$ by

$\begin{cases}h_{3}(p_{1}^{d_{1}}\cdots
p_{\ell}^{d_{\ell}})=e((\theta_{1}d_{1}+\dots+\theta_{\ell}d_{\ell})t)\\\
h_{3}(-p_{1}^{d_{1}}\cdots
p_{\ell}^{d_{\ell}})=e(-(\theta_{1}d_{1}+\dots+\theta_{\ell}d_{\ell})t).\end{cases}$

Observe that, since each of $A_{1},\dots,A_{5}$ contains two positive and two
negative elements, $(h_{3})_{A_{1}}$, …, $(h_{3})_{A_{5}}$ are constant on
$G_{L}$. In particular. we have $(h_{3})_{A_{5}}=1$. Because none of
$A_{1},\ldots,A_{4}$ are cancelling, by some elementary linear algebra, we can
choose $\theta_{1},\dots,\theta_{\ell}\in\mathbb{Q}$ so that

$\text{Re}\sum_{i=1}^{5}(h_{3})_{A_{i}}(r)=1+\cos(\gamma_{1}t)+\cos(\gamma_{2}t)+\cos(\gamma_{3}t)+\cos(\gamma_{4}t)\qquad\text{
with
}\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}\in\mathbb{Q}\setminus\\{0\\}.$

By 5.18, we can choose $t\in\mathbb{R}$ so that
$1+\cos(\gamma_{1}t)+\cos(\gamma_{2}t)+\cos(\gamma_{3}t)+\cos(\gamma_{4}t)<0$.
This ensures that 4 holds. ∎

It is clear that the construction in Proposition 5.17 fails when some $A_{i}$,
$i\in[4]$ is cancelling, because then $h_{A_{i}}$ becomes identically 1, and
we can no longer leverage 5.18 to do the phase cancellation. To handle this
final case, we can leverage the discrepancy between the largest exponents of
primes that divide various elements of $A_{i}$; that is, $h$ is a function of
these largest exponents, for which we use the following notation.

######  Definition 5.19.

  1. (1)

For prime number $p$ and $r\in\mathbb{Z}\setminus\\{0\\}$, define
$v_{p}(r)=\max\\{d\in\\{0,1,\dots\\}:p^{d}\mid|r|\\}$.

  2. (2)

For prime number $p$ and multiset $A$, define
$V_{p}(A)=\\{\\!\\!\\{v_{p}(a):a\in A\\}\\!\\!\\}$.

Next, we demonstrate our construction through two examples.

######  Example 5.20.

Let $L$ be the $2\times 5$ linear system

$\begin{pmatrix}1&1&-1&-1&0\\\ 1&-3&-4&0&12\end{pmatrix}.$

We then have

$\displaystyle L_{5}\mathbf{x}$
$\displaystyle=x_{1}+x_{2}-x_{3}-x_{4}\qquad\qquad$ $\displaystyle
A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$ $\displaystyle L_{4}\mathbf{x}$
$\displaystyle=x_{1}-3x_{2}-4x_{3}+12x_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{1,-3,-4,12\\}\\!\\!\\}$ $\displaystyle L_{3}\mathbf{x}$
$\displaystyle=-3x_{1}-7x_{2}+4x_{4}+12x_{5}$ $\displaystyle
A_{3}=\\{\\!\\!\\{-3,-7,4,12\\}\\!\\!\\}$ $\displaystyle L_{2}\mathbf{x}$
$\displaystyle=4x_{1}-7x_{3}-3x_{4}+12x_{5}$ $\displaystyle
A_{2}=\\{\\!\\!\\{4,-7,-3,12\\}\\!\\!\\}$ $\displaystyle L_{1}\mathbf{x}$
$\displaystyle=-4x_{2}-3x_{3}+x_{4}+12x_{5}$ $\displaystyle
A_{1}=\\{\\!\\!\\{-4,-3,1,12\\}\\!\\!\\}.$

Note that in this context we have that
$G_{L}=\\{2^{d_{1}}3^{d_{2}}7^{d_{3}}:d_{1},d_{2},d_{3}\in\\{0,1,\dots\\}\\}$.
By Lemma 5.14, to show that $L$ is uncommon, it suffices to find a
$\vec{u}$-periodic function $h\colon\pm G_{L}\to\mathbb{C}$ with
$h(-r)=\overline{h(r)}$ such that 4 holds.

Note that $v_{2}(3)=0,v_{2}(4)=2,v_{2}(12)=2$ and
$v_{3}(3)=1,v_{3}(4)=0,v_{3}(12)=1$. It turns out to be advantageous to
consider the largest exponent of 2 and 3, which are the primes that “witness”
the cancelling structure in $A_{4}$. In particular, sending
$A_{i}\mapsto\\{\\!\\!\\{(v_{2}(r),v_{3}(r)):r\in A_{i}\\}\\!\\!\\}$ for each
$i$, we have:

$\displaystyle
A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}\mapsto\\{\\!\\!\\{(0,0),(0,0),(0,0),(0,0)\\}\\!\\!\\}$
$\displaystyle
A_{4}=\\{\\!\\!\\{1,-3,-4,12\\}\\!\\!\\}\mapsto\\{\\!\\!\\{(0,0),(0,1),(2,0),(2,1)\\}\\!\\!\\}$
$\displaystyle
A_{3}=\\{\\!\\!\\{-3,-7,4,12\\}\\!\\!\\}\mapsto\\{\\!\\!\\{(0,1),(0,0),(2,0),(2,1)\\}\\!\\!\\}$
$\displaystyle
A_{2}=\\{\\!\\!\\{4,-7,-3,12\\}\\!\\!\\}\mapsto\\{\\!\\!\\{(2,0),(0,0),(1,0),(2,1)\\}\\!\\!\\}$
$\displaystyle
A_{1}=\\{\\!\\!\\{-4,-3,1,12\\}\\!\\!\\}\mapsto\\{\\!\\!\\{(2,0),(0,1),(0,0),(2,1)\\}\\!\\!\\}.$

Consider the following function $h\colon\pm G_{L}\to\mathbb{C}$ given by

$h(r)=\begin{cases}-1&\text{if
}\left\lfloor\frac{v_{2}(r)}{2}\right\rfloor\equiv v_{3}(r)\equiv 1\pmod{2}\\\
1&\text{otherwise}\end{cases}$

Then, since $h(2^{4}\cdot 3^{2}\cdot r)=h(r)$ for every $r$, we know that
every $h_{A_{i}}$ is $\vec{u}$-periodic with $\vec{u}=(4,2,1)$. Moreover, we
have

$\displaystyle\sum_{\begin{subarray}{c}0\leq d_{1}\leq 3\\\ 0\leq d_{2}\leq
1\\\
r=2^{d_{1}}3^{d_{2}}\end{subarray}}(|h(r)|^{4}+h(r)h(-3r)h(-4r)h(12r)+h(-3r)h(-7r)h(4r)h(12r)$
$\displaystyle\qquad\qquad\qquad+h(4r)h(-7r)h(-3r)h(12r)+h(-4r)h(-3r)h(r)h(12r))$
$\displaystyle=8-8-8-8-8=-24<0.$

Therefore, $h$ satisfies the condition in Lemma 5.14.

######  Example 5.21.

Let $L$ be the $2\times 5$ linear system

$\begin{pmatrix}1&1&-1&-1&0\\\ 6&24&-144&0&-1\end{pmatrix}.$

We then have

$\displaystyle L_{5}\mathbf{x}$
$\displaystyle=x_{1}+x_{2}-x_{3}-x_{4}\qquad\qquad\qquad$ $\displaystyle
A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$ $\displaystyle L_{4}\mathbf{x}$
$\displaystyle=6x_{1}+24x_{2}-144x_{3}-x_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{6,24,-144,-1\\}\\!\\!\\}$ $\displaystyle L_{3}\mathbf{x}$
$\displaystyle=-138x_{1}-120x_{2}+144x_{4}-x_{5}$ $\displaystyle
A_{3}=\\{\\!\\!\\{-138,-120,144,-1\\}\\!\\!\\}$ $\displaystyle
L_{2}\mathbf{x}$ $\displaystyle=-18x_{1}-120x_{3}+24x_{4}-x_{5}$
$\displaystyle A_{2}=\\{\\!\\!\\{-18,-120,24,-1\\}\\!\\!\\}$ $\displaystyle
L_{1}\mathbf{x}$ $\displaystyle=18x_{2}-138x_{3}+6x_{4}-x_{5}$ $\displaystyle
A_{1}=\\{\\!\\!\\{18,-138,6,-1\\}\\!\\!\\}$

Note that in this context we have
$G_{L}=\\{2^{d_{1}}3^{d_{2}}5^{d_{3}}23^{d_{4}}:d_{1},d_{2},d_{3},d_{4}\in\mathbb{N}\\}$.
By Lemma 5.14, to show that $L$ is uncommon, it suffices to find a
$\vec{u}$-periodic function $h\colon\pm G_{L}\to\mathbb{C}$ such that 4 holds.

In this case, note that $v_{2}(6),v_{2}(24),v_{2}(144)\geq 1$ and
$v_{2}(6)+v_{2}(24)=v_{2}(144)$, and so the cancelling structure in $A_{4}$ is
“witnessed” by the prime 2. This stands in contrast to Example 5.20, where two
primes were needed to “witness” this cancelling structure. At present it turns
out to be advantageous to isolate the largest exponent of 2 that divide each
of the elements of $A_{i}$. In particular, sending
$A_{i}\mapsto\\{\\!\\!\\{v_{2}(r):r\in A_{i}\\}\\!\\!\\}$ for each $i$, we
have:

$\displaystyle
A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}\mapsto\\{\\!\\!\\{0,0,0,0\\}\\!\\!\\}$
$\displaystyle
A_{4}=\\{\\!\\!\\{6,24,-144,-1\\}\\!\\!\\}\mapsto\\{\\!\\!\\{1,3,4,0\\}\\!\\!\\}$
$\displaystyle
A_{3}=\\{\\!\\!\\{-138,-120,144,-1\\}\\!\\!\\}\mapsto\\{\\!\\!\\{1,3,4,0\\}\\!\\!\\}$
$\displaystyle
A_{2}=\\{\\!\\!\\{-18,-120,24,-1\\}\\!\\!\\}\mapsto\\{\\!\\!\\{1,3,3,0\\}\\!\\!\\}$
$\displaystyle
A_{1}=\\{\\!\\!\\{18,-138,6,-1\\}\\!\\!\\}\mapsto\\{\\!\\!\\{1,1,1,0\\}\\!\\!\\}$

We will choose an appropriate $\phi\colon\mathbb{N}\to\\{\pm 1\\}$ and show
that $h(r)=\phi(v_{2}(r))$ has the desired properties. We will choose $\phi$
to be periodic, and then it will follow that $h$ is periodic on $G_{L}$ as
well. Consider

$\phi(v)=\begin{cases}-1&\text{if }v\equiv 0,1\pmod{4},\\\ 1&\text{if }v\equiv
2,3\pmod{4}.\end{cases}$

Then, since $h(2^{4}\cdot r)=h(r)$ for every $r$, we know that every
$h_{A_{i}}$ is $\vec{u}$-periodic with $\vec{u}=(4,1,1,1)$. Moreover, for
$r=2^{d_{1}}$ with $d_{1}=0,1,2,3$, the values of each $h_{A_{i}}(r)$ varies
as follows:

  * •

$h_{A_{5}}=1$, as

$\phi(0)^{4}=\dots=\phi(3)^{4}=1.$

  * •

$h_{A_{4}},h_{A_{3}}=-1$, as

$\phi(1)\phi(3)\phi(0)^{2}=\phi(2)\phi(0)\phi(1)^{2}=\phi(3)\phi(1)\phi(2)^{2}=\phi(0)\phi(2)\phi(3)^{2}=-1.$

  * •

$h_{A_{1}}=h_{A_{2}}=1$ when $d_{1}\in\\{0,2\\}$ and $h_{A_{1}}=h_{A_{2}}=-1$
when $d_{1}\in\\{1,3\\}$, as

$\phi(1)\phi(0)=\phi(3)\phi(2)=1,\qquad\phi(2)\phi(1)=\phi(0)\phi(3)=-1.$

Altogether, we have

$\displaystyle\sum_{\begin{subarray}{c}0\leq d_{1}\leq 3\\\
r=2^{d_{1}}\end{subarray}}(|h(r)|^{4}+h(6r)h(24r)h(-144r)h(r)+h(-138r)h(-120r)h(144r)h(-r)$
$\displaystyle\qquad\qquad\qquad+h(-18r)h(-120r)h(24r)h(-r)+h(18r)h(-138r)h(6r)h(-r))$
$\displaystyle=4-4-4+0+0=-4<0.$

Therefore, $h$ satisfies the condition in Lemma 5.14.

The general result, whose proof we put in Section B.2, is the following.

######  Proposition 5.22.

Suppose $L$ is an irredundant $2\times 5$ linear system that falls under Case
B in Corollary 5.3 and suppose that for some $i\in[4]$, $A_{i}$ is a
cancelling pair. Then there exists a Fourier template
$g\colon\mathbb{Z}\to\mathbb{C}$ such that
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$.

The proof of Proposition 5.22 proceeds in two steps. First, in Corollary B.6
we make precise the notion of “witnessing the cancelling structure” in the
above examples, by classifying the types of cancelling sets that can occur.
Second, we handle each case in the series of Proposition B.10–Proposition
B.13. The main ideas on how to handle each case generalize those in Example
5.20 and Example 5.21.

We summarize some of the properties of the above constructions in the
following table.

Table 1. Periodic sums of $(h_{j})_{A}$ on $G_{L}$ | $h_{1}$ | $h_{2}$ | $h_{3}$ | $h_{4}$
---|---|---|---|---
$A$ has four positive elements | $-1$ |  |  |
$A$ has three positive and one negative elements | $\pm i$ | $-1$ |  |
$A$ has two positive and two negative elements but is not cancelling | 1 | 1 | $e^{i\gamma t}$ |
$A$ is cancelling but not additive quadruple | 1 | 1 | 1 | $-1$
Relevant results | 5.16 | 5.16 | 5.17 | 5.22

Finally, we put together 5.16, Proposition 5.17 and Proposition 5.22 to
complete the proof of case B.

######  Proposition 5.23.

Suppose $L$ is an irredundant $2\times 5$ linear system that falls under Case
B in Corollary 5.3. Then there exists a Fourier template
$g:\mathbb{Z}^{d}\to\mathbb{C}$ such that $\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$.

Roughly speaking, depending on the structures of $A_{1},\dots,A_{5}$ that
appear in the linear system $L$ – in particular, which rows in Table 1 these
$A_{i}$ belong to – we choose some subset of $h_{j}$ as described in Table 1
such that the product of each row restricted to chosen $h_{j}$ sums up to
negative. Then we take the Fourier template $g_{j}$ to be the finite
truncation of $h_{j}$, and finally take $g$ to be the joined Fourier template
from the $g_{j}$.

In the proof of Proposition 5.23, we will need the following analogue of 5.18
(also proved in Section B.2).

######  Fact 5.24.

For all $\gamma_{1},\gamma_{2}\in\mathbb{Q}\setminus\\{0\\}$, there exists
$t\in\mathbb{R}$ such that $1+\cos(\gamma_{1}t)+\cos(\gamma_{2}t)<0$.

###### Proof of Proposition 5.23.

If at least one of $A_{1},\dots,A_{4}$ is cancelling then we can conclude by
Proposition 5.22. It remains to handle the case when none of
$A_{1},A_{2},A_{3},A_{4}$ is cancelling.

  1. (1)

Suppose two of $A_{1},A_{2},A_{3},A_{4}$ contains four positive elements and
the other two contain three positive and one negative elements. Then we can
apply Lemma 5.14 and 5.16 with $h_{1}:\pm G_{L}\to\mathbb{C}$.

  2. (2)

Suppose all four of $A_{1},A_{2},A_{3},A_{4}$ contain three positive and one
negative element. Then we can apply Lemma 5.14 and 5.16 with $h_{2}:\pm
G_{L}\to\mathbb{C}$.

  3. (3)

Suppose each of $A_{1},\ldots,A_{4}$ contain two positive and two negative
elements. Then we can apply Lemma 5.14 and Proposition 5.17 with $h_{3}:\pm
G_{L}\to\mathbb{C}$.

  4. (4)

Suppose that two of $A_{1},\ldots A_{4}$ (say $A_{i_{1}},A_{i_{2}}$) contain
three positive and one negative elements, and the other two contain two
positive and two negative elements (say $A_{i_{3}},A_{i_{4}}$). We construct
two functions $h_{3}$ and $h_{3}h_{2}$, and it will be clear in a moment why
we do so.

We set $h_{3}$ to be the function that we constructed in Proposition 5.17, but
with $\theta_{i}$ and $t$ chosen according to 5.24. More precisely, recall
that

$P_{L}=\\{p_{1},\dots,p_{\ell}\\}=\\{p:p\text{ is a prime divisor of some
element in }A_{1}\cup\dots\cup A_{5}\\}.$

For some $\theta_{1},\dots,\theta_{\ell}\in\mathbb{Q}$ and $t\in\mathbb{R}$ to
be chosen later, define $h_{3}\colon\pm G_{L}\to\mathbb{C}$ by

$\begin{cases}h_{3}(p_{1}^{d_{1}}\cdots
p_{\ell}^{d_{\ell}})=e((\theta_{1}d_{1}+\dots+\theta_{\ell}d_{\ell})t)\\\
h_{3}(-p_{1}^{d_{1}}\cdots
p_{\ell}^{d_{\ell}})=e(-(\theta_{1}d_{1}+\dots+\theta_{\ell}d_{\ell})t)\end{cases}$

Observe that $(h_{3})_{A_{i_{1}}},(h_{3})_{A_{i_{2}}},(h_{3})_{A_{5}}$ are
constant on $G_{L}$, and $(h_{3})_{A_{5}}=1$. Since $A_{i_{1}}$ and
$A_{i_{2}}$ are not cancelling, we are able to choose
$\theta_{1},\dots,\theta_{\ell}\in\mathbb{Q}$ so that

$(h_{3})_{A_{5}}+\text{Re}((h_{3})_{A_{i_{1}}})+\text{Re}((h_{3})_{A_{i_{2}}})=1+\cos(\gamma_{1}t)+\cos(\gamma_{2}t),\quad\gamma_{1},\gamma_{2}\in\mathbb{Q}\setminus\\{0\\}.$

Using 5.24, we can choose $t\in\mathbb{R}$ so that
$1+\cos(\gamma_{1}t)+\cos(\gamma_{2}t)<0$.

Now consider $h_{3}h_{2}$. Since
$(h_{2})_{A_{i_{1}}},(h_{2})_{A_{i_{2}}},(h_{2})_{A_{i_{5}}}=1$ and
$(h_{2})_{A_{i_{3}}}=(h_{2})_{A_{i_{4}}}=-1$ (as summarized in Table 1), we
have either

$\mathrm{Re}\sum_{i=1}^{5}h_{3}(r)<0\quad\text{or}\quad\mathrm{Re}\sum_{i=1}^{5}h_{3}(r)h_{2}(r)<0$

for every $r\in\pm G_{L}$. Applying Lemma 5.14 gives the result.

∎

###  5.4. Proof of Theorem 1.10 under Case C

In this section, we prove Theorem 1.10 under Case C listed in Corollary 5.3.

Suppose $L$ falls under Case C in Corollary 5.3. We show that, if $L$ is not
isomoprhic to

$\displaystyle\begin{pmatrix}1&1&-1&-1&0\\\
1&-1&3&0&-3\end{pmatrix}\quad\begin{pmatrix}1&1&-1&-1&0\\\
2&-2&3&0&-3\end{pmatrix}$

then $L$ is common if it is isomorphic to

$\begin{pmatrix}1&1&-1&-1&0\\\ 2&-2&1&0&-1\end{pmatrix}$

and uncommon otherwise.

Suppose $L$ is an irredundant $2\times 5$ linear system under Case C listed in
Corollary 5.3. In this case, we always assume the following setup:

######  Setup 5.25.

Suppose

$\displaystyle L_{5}\mathbf{x}$ $\displaystyle=x_{1}+x_{2}-x_{3}-x_{4}$
$\displaystyle A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$ $\displaystyle
L_{4}\mathbf{x}$ $\displaystyle=bx_{1}-bx_{2}+ax_{3}-ax_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{1,-1,\frac{a}{b},-\frac{a}{b}\\}\\!\\!\\}$ $\displaystyle
L_{3}\mathbf{x}$ $\displaystyle=(a+b)x_{1}+(a-b)x_{2}-ax_{4}-ax_{5}\qquad$
$\displaystyle
A_{3}=\\{\\!\\!\\{\frac{a+b}{b},\frac{a-b}{b},-\frac{a}{b},-\frac{a}{b}\\}\\!\\!\\}$
$\displaystyle L_{2}\mathbf{x}$
$\displaystyle=2bx_{1}+(a-b)x_{3}-bx_{4}-ax_{5}$ $\displaystyle
A_{2}=\\{\\!\\!\\{2,\frac{a-b}{b},-1,-\frac{a}{b}\\}\\!\\!\\}$ $\displaystyle
L_{1}\mathbf{x}$ $\displaystyle=2bx_{2}-(a+b)x_{3}-bx_{4}+ax_{5}$
$\displaystyle A_{1}=\\{\\!\\!\\{2,-\frac{a+b}{b},-1,\frac{a}{b}\\}\\!\\!\\}$

with $a,b\in\mathbb{N}$ coprime, and none of $L_{1},L_{2},L_{3}$ is common.

In order to build some intuition for this case, we revisit Example 5.6 and
reframe the construction in a manner which generalizes easily.

######  Example 5.26 (Take two of Example 5.6).

We recall the setup. Let $L$ be the linear system

$\begin{pmatrix}1&1&-1&-1&0\\\ 1&-1&4&0&-4\end{pmatrix}.$

We then have

$\displaystyle L_{5}\mathbf{x}$
$\displaystyle=x_{1}+x_{2}-x_{3}-x_{4}\qquad\qquad$ $\displaystyle
A_{5}=\\{\\!\\!\\{1,1,-1,-1\\}\\!\\!\\}$ $\displaystyle L_{4}\mathbf{x}$
$\displaystyle=x_{1}-x_{2}+4x_{3}-4x_{5}$ $\displaystyle
A_{4}=\\{\\!\\!\\{1,-1,4,-4\\}\\!\\!\\}$ $\displaystyle L_{3}\mathbf{x}$
$\displaystyle=5x_{1}+3x_{2}-4x_{4}-4x_{5}$ $\displaystyle
A_{3}=\\{\\!\\!\\{3,5,-4,-4\\}\\!\\!\\}$ $\displaystyle L_{2}\mathbf{x}$
$\displaystyle=2x_{1}+3x_{3}-1x_{4}-4x_{5}$ $\displaystyle
A_{2}=\\{\\!\\!\\{2,3,-1,-4\\}\\!\\!\\}$ $\displaystyle L_{1}\mathbf{x}$
$\displaystyle=2x_{2}-5x_{2}-1x_{4}+4x_{5}$ $\displaystyle
A_{1}=\\{\\!\\!\\{2,-5,-1,4\\}\\!\\!\\}.$

We have the corresponding multiplicative grid

$G_{L}=\\{2^{d_{1}}3^{d_{2}}5^{d_{3}}:d_{1},d_{2},d_{3}\in\\{0,1,\dots\\}\\},$

and the goal is to construct a $\vec{u}$-periodic $h\colon\pm
G_{L}\to\mathbb{C}$ with $h(-r)=\overline{h(r)}$ and the property 4:

$\mathrm{Re}\sum_{\begin{subarray}{c}0\leq d_{1}\leq u_{1}-1\\\ 0\leq
d_{2}\leq u_{2}-1\\\ 0\leq d_{3}\leq
u_{3}-1\end{subarray}}\sum_{i=1}^{5}h_{A_{i}}(2^{d_{1}}3^{d_{2}}5^{d_{3}}\cdot
r)<0.$

$1$$3$$5$$3\cdot
5$$0.25+0.42i$$0.35-0.35i$$-0.35-0.35i$$-0.25-0.42i$$4$$4\cdot 3$$4\cdot
5$$4\cdot 3\cdot 5$$-0.35-0.35i$$0.48+0.12i$$0.48+0.12i$$0.35-0.35i$$2$$2\cdot
3$$2\cdot 5$$2\cdot 3\cdot 5$$0$$-1-i$$-1-i$$0$$8$$8\cdot 3$$8\cdot 5$$8\cdot
3\cdot 5$$1-i$$0$$0$$1-i$ Figure 1. An illustration of the “orbits” of $h$.
The pink/dotted arrow represents the action of multiplying by 4, the
green/solid arrow represents the action of multiply by 3 and the blue/dashed
arrow represents the action of multiplying by 5.

Figure 1 illustrates our construction. In particular, we chose
$\vec{u}=(4,2,2)$, which means that $h(2^{4}\cdot 3^{2}\cdot 5^{2}\cdot
r)=h(r)$ for every $r\in G_{L}$. The left column denotes the value of $h(r)$
when $r=2^{i}3^{j}5^{k}$ with $i\in\\{0,2\\}$ and $j,k\in\mathbb{Z}_{2}$;
right left column denotes the value of $h(r)$ when $r=2^{i}3^{j}5^{k}$ with
$i\in\\{1,3\\}$ and $j,k\in\mathbb{Z}_{2}$. And as always, we take
$h(-r)=\overline{h(r)}$ for every $r\in G_{L}$.

The key observation is that, since $h_{A_{1}}(r),h_{A_{2}}(r),h_{A_{4}}(r)$
are nonvanishing only if $h(r)$, $h(4r)$ are both nonzero, we have
$h_{A_{1}}(r)=h_{A_{2}}(r)=h_{A_{4}}(r)=0$ if $r$ is any of the yellow/shaded
elements. This gives

$\displaystyle\sum_{r\text{ yellow}}\sum_{i=1}^{5}h_{A_{i}}(r)$
$\displaystyle=\sum_{r\text{ yellow}}\left(h_{A_{5}}(r)+h_{A_{3}}(r)\right)$
$\displaystyle=2|1-i|^{4}+2|-1-i|^{4}+2(-1-i)^{2}(1+i)^{2}+2(1-i)^{2}(-1+i)^{2}$
$\displaystyle=0.$

We draw attention to the fact that multiplication by 3 and 5 create orbits of
length two. This fact, coupled with the choice of values of $h$ on the
yellow/shaded elements, is essential in ensuring that the contributions from
$h_{A_{3}}$ cancels out the contributions of $h_{A_{5}}$ on the yellow/shaded
elements. In effect the only contribution to the sum
$\sum_{\begin{subarray}{c}0\leq d_{1}\leq 3\\\ 0\leq d_{2}\leq 1\\\ 0\leq
d_{3}\leq
1\end{subarray}}\sum_{i=1}^{5}h_{A_{i}}(2^{d_{1}}3^{d_{2}}5^{d_{3}})$ comes
from $\sum_{i=1}^{5}h_{A_{i}}(r)$ when $r$ are the white elements on the left.
This final part is a computation:

$\text{Re}\sum_{r\text{
white}}\sum_{i=1}^{5}h_{A_{i}}(r)=0.474101+0.474026-0.2401-0.4788-0.4788=-0.249573.$

To summarize, we can think of our construction as a combination of two
components:

  * •

A function
$f\colon\mathbb{Z}_{4}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\to\mathbb{C}$
represented by the table of values in Figure 1.

  * •

A function $\phi\colon
G_{L}\to\mathbb{Z}_{4}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ with the
“orbit structure” given by:

    * $\circ$

$\phi(4r)=\phi(r)+(2,0,0)$,

    * $\circ$

$\phi(3r)=\phi(r)+(0,1,0)$,

    * $\circ$

$\phi(5r)=\phi(r)+(0,0,1)$,

    * $\circ$

$\phi(2r)=\phi(r)+(1,0,0)$ when $\phi(r)_{1}\in\\{0,2\\}$.

The Fourier template in Example 5.6 can therefore be thought of as
$h=f\circ\phi$. The combination of these two elements ensure that the
yellow/shaded cells cancel in contribution to give a net zero contribution to
the sum

$\mathrm{Re}\sum_{\begin{subarray}{c}0\leq d_{1}\leq u_{1}-1\\\ \vdots\\\
0\leq d_{\ell}\leq
u_{\ell}-1\end{subarray}}\sum_{i=1}^{5}h_{A_{i}}(p_{1}^{d_{1}}\ldots
p_{\ell}^{d_{\ell}}\cdot r),$

while the white cells contribute a negative value. Using such a framework, we
can generalize our construction to handle other systems $L$ in Case C. In the
first step, we show how to extend Figure 1 to a larger table, which gives us
more flexibility with constructing the function $\phi$ in the second step.
This is the content of the following Proposition 5.27.

######  Proposition 5.27.

Suppose $L$ is an irredundant $2\times 5$ linear system that falls under Case
C in Corollary 5.3. Assume 5.25. If there exists $m\geq 2$ and
$\phi:G_{L}\to\mathbb{Z}_{2m}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ such
that

$\displaystyle\phi(\frac{a}{b}\cdot r)$ $\displaystyle=\phi(r)+(m,0,0)$
$\displaystyle\phi(\frac{|a-b|}{b}\cdot r)$ $\displaystyle=\phi(r)+(0,1,0)$
$\displaystyle\phi(\frac{a+b}{b}\cdot r)$ $\displaystyle=\phi(r)+(0,0,1)$
$\displaystyle\phi(2r)$ $\displaystyle=\phi(r)+(1,0,0)\text{ when
$\phi(r)_{1}\in\\{0,m\\}$,}$

Then there exists a Fourier template $g:\mathbb{Z}\to\mathbb{C}$ such that
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$.

Vaguely speaking, we can think of Proposition 5.27 as “extending” the table in
Table 1 by duplicating more columns of yellow/shaded cells in Figure 1 and
leaving the white cells intact.

###### Proof.

Suppose such $\phi$ exists. We first consider the case $a-b>0$. In this case,
define $h=\phi\circ f:G_{L}\to\mathbb{C}$, where
$f:\mathbb{Z}_{2m}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\to\mathbb{C}$ is
given by

$\displaystyle(0,0,0)\mapsto 0.25+0.42i\qquad$
$\displaystyle(1,0,0),\dots,(m-1,0,0)\mapsto 0$ $\displaystyle(0,0,1)\mapsto
0.35-0.35i\qquad$ $\displaystyle(1,0,1),\dots,(m-1,0,1)\mapsto-1-i$
$\displaystyle(0,1,0)\mapsto-0.35+0.35i\qquad$
$\displaystyle(1,1,0),\dots,(m-1,1,0)\mapsto-1-i$
$\displaystyle(0,1,1)\mapsto-0.25-0.42i\qquad$
$\displaystyle(1,1,1),\dots,(m-1,1,1)\mapsto 0$
$\displaystyle(m,0,0)\mapsto-0.35+0.35i\qquad$
$\displaystyle(m+1,0,0),\dots,(2m-1,0,0)\mapsto 1-i$
$\displaystyle(m,0,1)\mapsto 0.48+0.12i\qquad$
$\displaystyle(m+1,0,1),\dots,(2m-1,0,1)\mapsto 0$
$\displaystyle(m,1,0)\mapsto 0.48+0.12i\qquad$
$\displaystyle(m+1,1,0),\dots,(2m-1,1,0)\mapsto 0$
$\displaystyle(m,1,1)\mapsto 0.35-0.35i\qquad$
$\displaystyle(m+1,1,1),\dots,(2m-1,1,1)\mapsto 1-i.$

Take $\vec{u}=(u_{1},\dots,u_{\ell})\in\mathbb{N}^{\ell}$ such that
$\phi(p_{1}^{u_{1}}\dots p_{\ell}^{u_{\ell}}r)=\phi(r)$. Then
$h_{A_{1}},\dots,h_{A_{5}}$ are $\vec{u}$-periodic. Moreover, we have

$\displaystyle\sum_{\begin{subarray}{c}0\leq d_{1}\leq u_{1}-1\\\ \cdots\\\
0\leq d_{\ell}\leq
u_{\ell}-1\end{subarray}}\sum_{i=1}^{5}h_{A_{i}}(p_{1}^{d_{1}}\ldots
p_{\ell}^{d_{\ell}}\cdot
r)=\sum_{i,j,k\in\mathbb{Z}_{2m}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}}$
$\displaystyle|f(i,j,k)|^{4}+|f(i,j,k)|^{2}|f(i+m,j,k)|^{2}$
$\displaystyle+f(i,j,k+1)f(i,j+1,k)\overline{f(i+m,j,k)}^{2}$
$\displaystyle+f(i+1,j,k)f(i,j+1,k)\overline{f(i,j,k)f(i+m,j,k)}$
$\displaystyle+f(i+1,j,k)\overline{f(i,j,k+1)f(i,j,k)}f(i+m,j,k).$

A quick observation is that, if $i\notin\\{0,m\\}$, then one of $f(i,j,k)$ and
$f(i+m,j,k)$ equals 0, so the second, fourth and fifth terms above vanish.
Moreover, the first and third terms sum up to

$\displaystyle
2|1-i|^{4}+2|-1-i|^{4}+2(-1-i)^{2}(1+i)^{2}+2(1-i)^{2}(-1+i)^{2}=0.$

Therefore, the above sum reduces to

$\displaystyle\sum_{i,j,k\in\\{0,m\\}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}}$
$\displaystyle|f(i,j,k)|^{4}+|f(i,j,k)|^{2}|f(i+m,j,k)|^{2}$
$\displaystyle+f(i,j,k+1)f(i,j+1,k)\overline{f(i+m,j,k)}^{2}$
$\displaystyle+f(i+1,j,k)f(i,j+1,k)\overline{f(i,j,k)f(i+m,j,k)}$
$\displaystyle+f(i+1,j,k)\overline{f(i,j,k+1)f(i,j,k)}f(i+m,j,k)$

which equals $-0.249573+0.723675i$. Hence $h$ has property 4. By Lemma 5.14,
this gives Fourier template $g:\mathbb{Z}\to\mathbb{C}$ such that
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$.

Similarly, when $a-b<0$ (so $h(\frac{a-b}{b}\cdot
r)=\overline{h(\frac{|a-b|}{b}\cdot r)}$ for $r\in G_{L}$), we define
$h=\phi\circ f^{\prime}:G_{L}\to\mathbb{C}$ where
$f^{\prime}:\mathbb{Z}_{2m}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\to\mathbb{C}$
is given by

$\displaystyle f^{\prime}(i,j,k)=\begin{cases}f(i,j,k)&j=0\\\
\overline{f(i,j,k)}&j=1.\end{cases}$

A similar argument shows that $h_{A_{1}},\dots,h_{A_{5}}$ are
$\vec{u}$-periodic, with property 4. By Lemma 5.14, this gives Fourier
template $g:\mathbb{Z}\to\mathbb{C}$ such that
$\sum_{i=1}^{5}\sigma_{A_{i}}(g)<0$. ∎

In Lemma 5.29, we show how to construct the corresponding function
$\phi\colon\mathbb{Z}_{2m}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ for all
but five specific linear systems under Case C in Corollary 5.3. Combining this
with Proposition 5.27 proves that all systems that fall under Case C, barring
these five exceptions, are uncommon.

To do so, we first extend the function
$v_{p}(\cdot):\mathbb{Z}\setminus\\{0\\}\to\mathbb{Z}$ introduced in
Definition 5.19 to one whose domain is the set of all nonzero rational
numbers.

######  Definition 5.28.

For every prime number $p$, define the function
$v_{p}(\cdot):\mathbb{Q}\setminus\\{0\\}\to\mathbb{Z}$ as follows:

  1. (1)

for all $r\in\mathbb{Z}\setminus\\{0\\}$, define
$v_{p}(r)=\max\\{d\in\\{0,1,\dots\\}:p^{d}\mid|r|\\}$;

  2. (2)

for all $r\in\mathbb{Q}\setminus\mathbb{Z}$, define
$v_{p}(r)=v_{p}(x)-v_{p}(y)$, where $r=x/y$ and
$x,y\in\mathbb{Z}\setminus\\{0\\}$.

######  Lemma 5.29.

Suppose $L$ is a linear system that falls under Case C in Corollary 5.3. Then,
unless $L$ is isomorphic to one of the following five linear systems

$\displaystyle\begin{pmatrix}1&1&-1&-1&0\\\
1&-1&3&0&-3\end{pmatrix}\quad\begin{pmatrix}1&1&-1&-1&0\\\
2&-2&3&0&-3\end{pmatrix}$ $\displaystyle\begin{pmatrix}1&1&-1&-1&0\\\
2&-2&1&0&-1\end{pmatrix}\quad\begin{pmatrix}1&1&-1&-1&0\\\
3&-3&1&0&-1\end{pmatrix}\quad\begin{pmatrix}1&1&-1&-1&0\\\
3&-3&2&0&-2\end{pmatrix},$

there exists $m\geq 2$ and
$\phi:G_{L}\to\mathbb{Z}_{2m}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ that
meets the condition in Proposition 5.27.

###### Proof.

We work under 5.25. One can check that, if $L$ is not isomorphic to one of the
above five systems, then one of the following occurs:

  * •

There exist odd primes $p_{1},p_{2},p_{3}$ such that

$\displaystyle v_{p_{1}}(a/b)\neq 0,$ $\displaystyle
v_{p_{1}}(|a-b|/b)=v_{p_{1}}((a+b)/b)=0,$ $\displaystyle
v_{p_{2}}(|a-b|/b)\neq 0,$ $\displaystyle
v_{p_{2}}(a/b)=v_{p_{2}}((a+b)/b)=0,$ $\displaystyle v_{p_{3}}((a+b)/b)\neq
0,$ $\displaystyle v_{p_{3}}(a/b)=v_{p_{3}}(|a-b|/b)=0.$

In this case, we define
$\phi:G_{L}\to\mathbb{Z}_{4}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ by

$\phi(r)=(2\left\lfloor\frac{v_{p_{1}}(r)}{v_{p_{1}}(a/b)}\right\rfloor+v_{2}(r),\left\lfloor\frac{v_{p_{1}}(r)}{v_{p_{2}}(|a-b|/b)}\right\rfloor,\left\lfloor\frac{v_{p_{3}}(r)}{v_{p_{3}}((a+b)/b)}\right\rfloor),$

so that $\phi$ meets the condition in Proposition 5.27.

E.g., when $a=10$ and $b=1$, we define

$\phi(r)=(2v_{5}(r)+v_{2}(r),\left\lfloor v_{3}(r)/2\right\rfloor,v_{11}(r)).$

  * •

There exist odd primes $p_{2},p_{3}$ such that

$\displaystyle v_{p_{2}}(|a-b|/b)\neq 0,$ $\displaystyle
v_{p_{2}}(a/b)=v_{p_{2}}((a+b)/b)=0,$ $\displaystyle v_{p_{3}}((a+b)/b)\neq
0,$ $\displaystyle v_{p_{3}}(a/b)=v_{p_{3}}(|a-b|/b)=0.$

Moreover, we have $m:=|v_{2}(a/b)|\geq 2$.

In this case, we define
$\phi:G_{L}\to\mathbb{Z}_{2m}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ by

$\phi(r)=(v_{2}(r),\left\lfloor\frac{v_{p_{1}}(r)}{v_{p_{2}}(|a-b|/b)}\right\rfloor,\left\lfloor\frac{v_{p_{3}}(r)}{v_{p_{3}}((a+b)/b)}\right\rfloor),$

so that $\phi$ meets the condition in Proposition 5.27.

E.g., in Example 5.6, when $a=4$ and $b=1$, we define

$\phi(r)=(v_{2}(r),v_{3}(r),v_{5}(r)).$

  * •

There exist odd primes $p_{1},p_{2}$ such that

$\displaystyle v_{p_{1}}(a/b)\neq 0,$ $\displaystyle