# Excluding affine configurations over a finite field

Dion Gijswijt

###### Abstract

Let $a_{i1}x_{1}+\cdots+a_{ik}x_{k}=0$, $i\in[m]$ be a balanced homogeneous
system of linear equations with coefficients $a_{ij}$ from a finite field
$\mathbb{F}_{q}$. We say that a solution $x=(x_{1},\ldots,x_{k})$ with
$x_{1},\ldots,x_{k}\in\mathbb{F}_{q}^{n}$ is _generic_ if every homogeneous
balanced linear equation satisfied by $x$ is a linear combination of the given
equations.

We show that if the given system is _tame_ , subsets
$S\subseteq\mathbb{F}_{q}^{n}$ without generic solutions must have
exponentially small density. Here, the system is called tame if for every
implied system the number of equations is less than half the number of used
variables. Using a subspace sampling argument this also gives a
‘supersaturation result’: there is a constant $c$ such that for $\epsilon>0$
sufficiently small, every subset $S\subseteq\mathbb{F}_{q}^{n}$ of size at
least $q^{(1-\epsilon)n}$ contains $\Omega(q^{(k-m-\epsilon c)n})$ solutions
as $n\to\infty$. For $q<4$ the tameness condition can be left out.

Our main tool is a modification of the slice rank method to leverage the
existence of many solutions in order to obtain high rank solutions.

##  1 Introduction

Let $\mathbb{F}_{q}$ be a finite field. Consider a balanced homogeneous system
of linear equations

$\displaystyle a_{11}x_{1}+$ $\displaystyle\cdots$ $\displaystyle+a_{1k}x_{k}$
$\displaystyle=0$ $(\star)$ $\displaystyle\ \ \vdots$ $\displaystyle
a_{m1}x_{1}+$ $\displaystyle\cdots$ $\displaystyle+a_{mk}x_{k}$
$\displaystyle=0$

with coefficient matrix $A=(a_{ij})\in\mathbb{F}_{q}^{m\times k}$ and variable
vectors $x_{1},\ldots,x_{k}\in\mathbb{F}_{q}^{n}$. By _balanced_ , we mean
that $a_{i1}+\cdots+a_{ik}=0$ for all $i\in[m]$. In other words, the equations
give affine dependencies between the $k$ variable vectors. We will always
assume that the equations are linearly independent, i.e.,
$\operatorname{rank}(A)=m$. Note that for any $v\in\mathbb{F}_{q}^{n}$ we
obtain a trivial solution by setting $x_{i}=v$ for all $i\in[k]$.

If $x=(x_{1},\ldots,x_{k})$ is a solution to $(\star)$, we say that a set
$S\subseteq\mathbb{F}_{q}^{n}$ contains the solution $x$ if
$x_{1},\ldots,x_{k}\in S$. For $n\to\infty$, we are interested in asymptotic
upper bounds on the maximum size of a subset $S\subseteq\mathbb{F}_{q}^{n}$
that contains no ‘non-degenerate’ solutions to $(\star)$. In particular, we
will be interested in the case that $S$ can be shown to have exponentially
small density in $\mathbb{F}_{q}^{n}$. In this context there are at least
three natural notions of non-degeneracy that have previously been studied. A
solution $x=(x_{1},\ldots,x_{k})$ to $(\star)$ is said to be

  * (a)

_non-trivial_ if $x_{i}\neq x_{j}$ for some $i,j\in[k]$;

  * (b)

_a $(\star)$-shape111This terminology was introduced in [MT19b]._ if
$x_{1},\ldots,x_{k}$ are pairwise distinct;

  * (c)

_generic_ 222This terminology was introduced in [DdBG21] if $x$ only satisfies
affine relations $\mu_{1}x_{1}+\cdots+\mu_{k}x_{k}=0$ that are linear
combinations of the equations in $(\star)$.

Clearly, every $(\star)$-shape is a non-trivial solution. Every generic
solution is a $(\star)$-shape, except when an equation of the form
$x_{j_{1}}-x_{j_{2}}=0$ is implied by $(\star)$ (in which case no
$(\star)$-shape exists in $\mathbb{F}_{q}^{n}$.)

The question of how large a set without non-degenerate solutions can be, may
be asked more generally for abelian groups instead of $\mathbb{F}_{q}^{n}$.
Especially for $\mathbb{Z}/n\mathbb{Z}$ (or intervals in $\mathbb{Z}$) this is
a central problem in additive number theory which includes famous results like
Szemeredi’s theorem on arithmetic progressions [Sze75]. Here we will solely
focus on the case that the variables take values in $\mathbb{F}_{q}^{n}$. It
is worth mentioning that $(\star)$ always has a generic solution in
$\mathbb{F}_{q}^{k-m-1}$. Hence, we have $|S|=o(q^{n})$ for any
$S\subseteq\mathbb{F}_{q}^{n}$ without generic solutions to $(\star)$ as a
direct consequence of the multi-dimensional density Hales-Jewett theorem
[FK91].

The system $(\star)$ is called333The notions ‘moderate’ and ‘temperate’ were
introduced in [MT19b] and [DdBG21], respectively.

  * •

_moderate_ if there is a $\delta>0$ such that $|S|=O(q^{(1-\delta)n})$ for any
set $S\subseteq\mathbb{F}_{q}^{n}$ that does not contain a $(\star)$-shape,

  * •

_temperate_ if there is a $\delta>0$ such that $|S|=O(q^{(1-\delta)n})$ for
any set $S\subseteq\mathbb{F}_{q}^{n}$ that does not contain a generic
solution to $(\star)$.

It follows that a temperate system is also moderate, provided the system does
not imply an equation of the form $x_{j_{1}}-x_{j_{2}}=0$. In this paper we
will show that under certain natural restrictions on $(\star)$, the system
$(\star)$ is temperate.

Below, we mention some recent work on finding such exponential bounds for each
of the three notions of non-degeneracy. In all cases, the main tool is the
slice-rank method or a variation thereof.

#### Non-trivial solutions

Perhaps the simplest and most studied system is the single equation
$x_{1}-2x_{2}+x_{3}=0$ where the solutions are precisely the $3$-term
arithmetic progressions. In this case, the notions ‘non-trivial’,
‘$(\star)$-shape’ and ‘generic’ coincide (for $q$ odd444If $q$ is even, the
problem is not interesting. Indeed, $x_{1},x_{2},x_{1}$ is a ‘nontrivial’ 3-AP
for any $x_{1}\neq x_{2}$ and, moreover, no 3-AP $x_{1},x_{2},x_{3}$ exists
with $x_{1}$, $x_{2}$, and $x_{3}$ pairwise distinct.). A set
$S\subseteq\mathbb{F}_{3}^{n}$ with no nontrivial $3$-term progressions is
known as a _cap set_. Based on the ground-breaking result of Croot, Lev, and
Pach [CLP17], it was shown in [EG17] that $|S|\leq 3\cdot 2.756^{n}$ for any
cap set $S\subseteq\mathbb{F}_{3}^{n}$. More generally, the authors show that
any set $S\subseteq\mathbb{F}_{q}^{n}$ without non-trivial solutions to a
given balanced equation $a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}=0$ has exponentially
small density in $\mathbb{F}_{q}^{n}$. In [Kov21] the proof is adapted to
upper bound sets in $(\mathbb{F}_{q}^{2})^{n}$ without right isosceles
triangles.

The method used in [EG17], was recast by Tao into a more elegant, symmetric
form introducing the concept of _slice rank_ [Tao16b, Tao16a]. Using the slice
rank method, it is straightforward to generalize the cap set theorem to
general balanced systems (see for example Theorem 1.1 in [Sau21a] and also
Proposition 4.12 in [BCC+17]). To describe the upper bound, let

$m_{q,n,d}=|\\{\alpha\in\\{0,1,\ldots,q-1\\}^{n}:\alpha_{1}+\cdots+\alpha_{n}\leq
d\\}|$

denote the number of monomials in $n$ variables of degree at most
$d\in\mathbb{R}_{\geq 0}$ in which each variable has exponent at most $q-1$.
Using the fact that for integer $d$, the number of monomials of degree $d$ is
the coefficient of $t^{d}$ in $(1+t+\dots+t^{q-1})^{n}$, one obtains the
following upper bound.

######  Lemma 1.

Let $\delta\in(0,1)$. Then

$m_{q,n,\delta(q-1)n}\leq c_{q,\delta}^{n},$

where $c_{q,\delta}=\inf_{0<t\leq 1}(1+t+\cdots+t^{q-1})t^{-\delta(q-1)}$.
Moreover, $c_{q,\delta}<q$ for $\delta<\tfrac{1}{2}$.

The slice rank method then yields the following result.

######  Theorem 2.

Let $S\subseteq\mathbb{F}_{q}^{n}$ have no nontrivial solution to $(\star)$.
Then

$|S|\leq k\cdot m_{q,n,(q-1)nm/k}\leq k\cdot c_{q,m/k}^{n}.$

If $k\geq 2m+1$, we have $c_{q,m/k}<q$.

The factor $k$ in the theorem can be removed by the ‘power trick’ since
$S_{1}\times S_{2}$ has no nontrivial solution when the same holds for each
$S_{i}\subseteq\mathbb{F}_{q}^{n_{i}}$. The cap set theorem corresponds to the
case $(m,k)=(1,3)$. The theorem implies that if $k\geq 2m+1$, every set
$S\subseteq\mathbb{F}_{q}^{n}$ without non-trivial solutions to $(\star)$ has
exponentially small density. When $k\leq 2m$, the slice-rank method breaks
down since for $d\geq(q-1)n/2$ we have $m_{q,n,d}\geq\tfrac{1}{2}q^{n}$, so
the obtained upper bound is trivial.

For $k\geq 4$ and any prime $p\geq k$, it is unknown whether every
$S\subseteq\mathbb{F}_{p}^{n}$ without non-trivial $k$-term progressions,
i.e., without non-trivial solutions to the system

$\displaystyle x_{1}-2x_{2}+x_{3}$ $\displaystyle=0$ $\displaystyle\vdots$
$\displaystyle x_{k-2}-2x_{k-1}+x_{k}$ $\displaystyle=0$

has exponentially small density for $n\to\infty$.

####  $(\star)$-shapes

In the case that $(\star)$ consists of the single equation
$x_{1}+\cdots+x_{p}=0$ with coefficients in $\mathbb{F}_{p}$, where $p\geq 3$
is a prime number, the maximum size of a set $S\subseteq\mathbb{F}_{p}^{n}$
without $(\star)$-shape is closely related to the Erdős-Ginzburg-Ziv constant
$\mathfrak{s}(\mathbb{F}_{p}^{n})$ for the abelian group $\mathbb{F}_{p}^{n}$.
The slice rank method does not (for $p\geq 5$) yield solutions with all
$x_{i}$ distinct. However, using a variant called _partition rank_ , Naslund
[Nas20] showed that $S\subseteq\mathbb{F}_{p}^{n}$ has exponentially small
density if $S$ does not contain a solution to $x_{1}+\cdots+x_{p}=0$ with the
$x_{i}$ pairwise distinct. Combining the slice rank method with other
techniques, the exponent in the upper bound was further improved in [FS18,
Sau21b].

Mimura and Tokushige were the first to explicitly study moderate systems, in
part motivated by analogous results over the integers by Ruzsa [Ruz93]. In
[MT19a, MT19b, MT20] they showed that several specific systems and families of
systems are moderate. Perhaps the simplest example is the case where $(\star)$
consists of a single balanced equation in $k\geq 3$ variables. A more general
theorem containing these specific examples was proved in [DdBG21]. There, it
is shown that if the coefficient matrix $A$ has many pairs of linearly
dependent columns, the system will be moderate. On the opposite end, it was
shown in [Sau21a] that for $k\geq 3m$, systems in which all $m\times m$ minors
of $A$ are nonzero, are moderate.

#### Generic solutions

It is implicit in [Sau21a] that if $(\star)$ consists of a single equation,
the system is temperate. A more general result is shown in [DdBG21]. There,
two columns of $A$ are said to be equivalent if they are scalar multiples of
one another. It is shown that $(\star)$ is temperate if either (i) for each
equivalence class the columns sum to zero, or (ii) the number of classes is
equal to $m+1$. If $(\star)$ consists of a single equation, then there is only
one equivalence class and we are in case (i).

In [GN15], Geelen and Nelson proved a result in extremal matroid theory that
is an analogue of the Erdős-Stone theorem for graphs. The theorem states that
for a fixed set $N$ of point in the projective space $\mathrm{PG}(m-1,q)$, the
maximum size $\mathrm{ex}_{q}(N,n)$ of a subset $A\subseteq\mathrm{PG}(n-1,q)$
not containing a copy of $N$ satisfies
$\frac{\mathrm{ex}_{q}(N,n)}{|\mathrm{PG}(n-1,q)|}\to 1-q^{1-\chi(N)}$ as
$n\to\infty$, where $\chi(N)$ is the critical number of $N$.

In the case that $N$ is affine ($\chi(N)=1$), this only gives an upper bound
$o(q^{n})$ on the Turán number $\mathrm{ex}_{q}(N,n)$. However, for the binary
case it was shown in [BQ00] that in fact $\mathrm{ex}_{2}(N,n)=O(2^{\alpha
n})$ for some $\alpha<1$ when $N$ is affine. This is equivalent to the
statement that for $q=2$ the system $(\star)$ is always temperate.

### Main results

We show that under certain conditions, the system $(\star)$ is temperate. Our
main result is the following.

######  Theorem A.

The balanced system $(\star)$ is temperate if the coefficient matrix $A$ is
tame.

Here, the matrix $A$ is called _tame_ if every system implied by $(\star)$
that has $m^{\prime}$ independent equations, uses at least $2m^{\prime}+1$
variables. The precise definition of _tame_ can be found in Section 3. We note
that if $(\star)$ implies the equation $x_{1}-x_{2}=0$, then without loss of
generality, $A$ has the following form:

$A=\left(\begin{array}[]{c|cc}1&-1&0\cdots 0\\\
\hline\cr\begin{array}[]{c}0\\\\[-4.30554pt] \vdots\\\
0\end{array}&\lx@intercol\hfil B\hfil\lx@intercol\end{array}\right)$

Then $(\star)$ is temperate if and only if the system with coefficient matrix
$B$ is temperate. Hence, we may assume that $(\star)$ does not imply an
equation of the form $x_{j_{1}}-x_{j_{2}}=0$.

The systems that were shown to be moderate or temperate in [DdBG21, Sau21a,
MT19b, MT19a, MT20] have tame coefficent matrices. Hence these results are
implied by Theorem A (albeit with possibly much worse exponents).

Over the fields $\mathbb{F}_{2}$ and $\mathbb{F}_{3}$, the tameness condition
is not necessary.

######  Theorem B.

The balanced system $(\star)$ is temperate if $q\in\\{2,3\\}$.

The number of solutions of affine rank $\leq r$ to $(\star)$ in the space
$\mathbb{F}_{q}^{n}$ is $O(q^{rn})$. In particular, the total number of
solutions is $O(q^{(k-m)n})$. As part of the proof of Theorem A we show a
supersaturation result for solutions of a fixed affine rank. Applied to to
Theorem A and B, we obtain the following corollary.

######  Corollary C.

Suppose that the coefficient matrix of $(\star)$ is tame or that $q<4$. Then
there exist $\delta>0$ and $C>0$ such that for all positive
$\delta^{\prime}<\delta$ the following holds: if
$S\subseteq\mathbb{F}_{q}^{n}$ has size $|S|\geq q^{(1-\delta^{\prime})n}$,
then $S$ contains $\Omega(q^{(k-m-C\delta^{\prime})n})$ solutions to
$(\star)$.

Theorems A and B can also be expressed in terms of excluding affine
configurations.

######  Corollary D.

Let $z_{1},\ldots,z_{k}\in\mathbb{F}_{q}^{d}$ be distinct. Suppose that $q<4$
or that for every $i\in[k]$ the set $\\{z_{1},\ldots,z_{k}\\}$ is the union of
two affinely independent subsets containing $z_{i}$. Then every subset
$S\subseteq\mathbb{F}_{q}^{n}$ containing no affine copy of
$(z_{1},\ldots,z_{k})$ has exponentially small density in $\mathbb{F}_{q}^{n}$
(as $n\to\infty$).

### Outline paper and proof

In Section 2, we set up our notation and preliminaries.

In Section 3, we introduce _tame_ matrices. We give a good characterization
for being tame using the matroid union theorem and show that any tame $m\times
k$ matrix can be extended to a tame $m^{\prime}\times(2m^{\prime}+1)$ matrix.
This allows us to restrict the proof of Theorem A to the case $k=2m+1$. The
main result in this section is Proposition 16, which shows that for any
solution $x$ of rank $r$ that is not generic ($r<(2m+1)-m$), there are two
disjoint affine bases of $\\{x_{i}:i\in[2m+1]\\}$. This is a crucial part of
the proof of Theorem A, and the place where tameness of $A$ is used.

In Section 4 we show a super saturation result for solutions of a given affine
rank. If for some $\delta>0$ the condition $|S|\geq q^{(1-\delta)n}$ forces
solutions of affine rank $\geq r$, then for $\delta^{\prime}<\delta$ the
condition $|S|\geq q^{(1-\delta^{\prime})n}$ forces $S$ to have
$\Omega(q^{r-c\delta^{\prime}}n)$ solutions of affine rank $\geq r$ (for some
constant $c$). This is used in the proof of Theorem A.

In Section 5 we prove our main theorem: Theorem A. It uses ideas from the
slice rank method (in particular the Croot-Lev-Pach lemma), the super
saturation result and Proposition 16. The main idea is to assume for
contradiction that $r<(2m+1)-m$ is the maximum affine rank for which we can
force solutions in $S$. We take the indicator function of the solution set
$f:S^{k}\to\mathbb{F}_{q}$ and two suitable disjoint sets $I,J\subseteq[k]$ of
size $r$. Summing $f$ against a suitable random $g:S^{[k]\setminus(I\cup
J)}\to\mathbb{F}_{q}$, we obtain a function $M(f):S^{I}\times
S^{J}\to\mathbb{F}_{p}$ that can be interpreted as an $|S|^{r}\times|S|^{r}$
matrix. Using the CLP lemma, the rank of $M(f)$ can be shown to be ‘small’. On
the other hand, Proposition 16 implies that $M(f)$ is the sum of low rank
matrices and an almost diagonal matrix that is ‘large’ by the super saturation
result, resulting in a contradiction.

In Section 6 we prove Theorem B. The proof only uses the cap set theorem and
an induction trick to lift it to a multi-dimensional variant.

In Section 7 we briefly discuss the relation with affine configurations of
points and show Corollary D.

Finally, in Section 8 we conclude with Corollary C and an open problem.

##  2 Preliminaries and notation

We denote the set of nonnegative integers by $\mathbb{N}$. For any positive
integer $n$, we denote $[n]=\\{1,\ldots,n\\}$. Throughout the paper, $q$ will
denote a (fixed) prime power and $\mathbb{F}_{q}$ denotes the field of order
$q$. By $\mathbb{F}$ we will denote an arbitrary field. For a linear space
$\mathbb{F}^{n}$ we denote by $e_{1},\ldots,e_{n}$ the standard basis vectors.
We will use the following basic lemma from linear algebra.

######  Lemma 3.

Let $S$ be a set and let $V\subseteq\mathbb{F}^{S}$ be a linear subspace of
dimension $d\in\mathbb{N}$. Then there is a subset $T\subseteq S$ of size
$|T|=d$ such that $f\mapsto f\raisebox{-2.15277pt}{$|$}_{T}$ is an isomorphism
between $V$ and $\mathbb{F}^{T}$.

### Asymptotic notation

The asymptotic notations $O(\cdot)$, $o(\cdot)$, $\Omega(\cdot)$ used in this
paper will always be with respect to the dimension $n$ of the space
$\mathbb{F}_{q}^{n}$. The notation $g(n)=\Omega(f(n))$ refers to the ‘Knuth
big omega notation’ common in computer science. In most cases, the function
$g$ is implicit. For instance, by the statement ‘For all
$S\subseteq\mathbb{F}_{q}^{n}$ with property $P$ we have $|S|=\Omega(g(n))$.’
we mean that there exist a constant $C>0$ and an integer $n_{0}$ such that for
all $n\geq n_{0}$ and every $S\subseteq\mathbb{F}_{q}^{n}$ with property $P$
we have $|S|\geq Cg(n)$.

### Mulivariate polynomials

For $\alpha\in\mathbb{N}^{n}$ we denote by
$x^{\alpha}=x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ the monomial in
variables $x_{1},\ldots,x_{n}$ of _degree_
$|\alpha|:=\alpha_{1}+\cdots+\alpha_{n}$. More generally, if
$\alpha=(\alpha_{1},\ldots,\alpha_{k})$, where
$\alpha_{1},\ldots,\alpha_{k}\in\mathbb{N}^{n}$, then we write

$|\alpha|:=|\alpha_{1}|+\cdots+|\alpha_{k}|=\sum_{i=1}^{k}\sum_{j=1}^{n}\alpha_{ij}\quad\text{and}\quad
x^{\alpha}:=x_{1}^{\alpha_{1}}\cdots
x_{k}^{\alpha_{k}}=\prod_{i=1}^{k}\prod_{j=1}^{n}x_{ij}^{\alpha_{ij}}.$

Since $x^{q}=x$ for all $x\in\mathbb{F}_{q}$, we will restrict our polynomials
to only have monomials in which all variables occur with exponent at most
$q-1$. We write $\mathbb{F}_{q}[x_{1},\ldots,x_{n}]^{\prime}$ for the linear
space spanned by the monomials $x^{\alpha}$,
$\alpha\in\\{0,1,\ldots,q-1\\}^{n}$. For $d\in\mathbb{R}$ we define
$M_{n,d}=\\{\alpha\in\\{0,1,\ldots,q-1\\}^{n}:|\alpha|\leq d\\}$ and
$m_{n,d}=|M_{n,d}|$.

The following key lemma is due to Croot, Lev and Pach (see [CLP17]).

######  Lemma 4 (CLP lemma).

Let $f\in\mathbb{F}_{q}[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}]^{\prime}$ have
degree at most $d$. Then the $q^{n}\times q^{n}$-matrix $M$ given by
$M_{ab}:=f(a,b)$ for all $a,b\in\mathbb{F}_{q}^{n}$, has rank at most
$2m_{q,n,d/2}$.

Since we will use similar arguments later, we give the proof here.

###### Proof.

Write $f=\sum_{\alpha,\beta}c_{\alpha\beta}x^{\alpha}y^{\beta}$ where the sum
is over all $\alpha,\beta\in\\{0,\ldots,q-1\\}^{n}$ that satisfy
$|\alpha|+|\beta|\leq d$, and the $c_{\alpha\beta}\in\mathbb{F}_{q}$ are
constants. Since each term has $|\alpha|\leq d/2$ or $|\beta|\leq d/2$, we can
group the terms accordingly (if both $|\alpha|,|\beta|\leq d/2$ we can choose
either group) and obtain

$f(x,y)=\sum_{|\alpha|\leq d/2}x^{\alpha}f_{\alpha}(y)+\sum_{|\beta|\leq
d/2}y^{\beta}g_{\beta}(x)$

for certain $f_{\alpha}\in\mathbb{F}_{q}[y_{1},\ldots,y_{n}]^{\prime}$ and
$g_{\beta}\in\mathbb{F}_{q}[x_{1},\ldots,x_{n}]^{\prime}$. Each of the terms
$x^{\alpha}f_{\alpha}(y)$ and $y^{\beta}g_{\beta}(x)$ corresponds to a rank
$1$ matrix (as it is the product of a function of $x$ and a function of $y$).
Hence, $M$ has rank at most $2m_{q,n,d/2}$. ∎

### Balanced linear systems

We will consider systems of linear equations of the form

$\displaystyle a_{11}x_{1}+$ $\displaystyle\cdots$ $\displaystyle+a_{1k}x_{k}$
$\displaystyle=0$ $(\star)$ $\displaystyle\ \ \vdots$ $\displaystyle
a_{m1}x_{1}+$ $\displaystyle\cdots$ $\displaystyle+a_{mk}x_{k}$
$\displaystyle=0$

where the coefficients $a_{ij}$ are elements of a field $\mathbb{F}$ and
$x_{1},\ldots,x_{k}\in\mathbb{F}^{n}$ are variable vectors. We will use the
shorthand notation $x=(x_{1},\ldots,x_{k})\in\mathbb{F}^{n\times k}$,
$A=(a_{ij})\in\mathbb{F}^{m\times k}$ and write the system of linear equations
as555We can think of $x=(x_{1},\ldots,x_{k})$ as an $n\times k$ matrix. Then
$Ax^{\mathsf{T}}=0$, where we take the usual matrix product and $0$ denotes
the $m\times k$ zero matrix, corresponds to system $(\star)$.
$Ax^{\mathsf{T}}=0$. If $\sum_{j\in[k]}a_{ij}=0$ for all $i\in[m]$, we say
that the matrix $A$ is _row-balanced_ and that the system $Ax^{\mathsf{T}}=0$
is a _balanced_ system.

### Matroid terminology

Let $A\in\mathbb{F}^{m\times k}$. For a subset $U\subseteq[k]$, we denote by
$r_{A}(U)$ the rank of the submatrix of $A$ formed by the columns indexed by
$U$. We have $r_{A}(U)=|U|$ if and only if the columns of $A$ indexed by $U$
are linearly independent. We say that $U$ is a _basis_ of $A$ if
$|U|=r_{A}(U)=\operatorname{rank}(A)$. Note that any set $I\subseteq[k]$ with
$r_{A}(I)=|I|$ is a subset of a basis.

The pair $M=([k],\mathcal{I})$ where
$\mathcal{I}=\\{I\subseteq[k]:r_{A}(I)=|I|\\}$ is a linear matroid with
collection of independent sets $\mathcal{I}$ and rank function $r_{A}$. The
following proposition follows directly by applying the matroid union theorem
to two copies of $M$ (see for instance Corollary 42.1b in [Sch03]). It gives a
min-max formula for the maximum size of the union of two sets of linearly
independent columns of the matrix $A$.

######  Proposition 5.

Let $A\in\mathbb{F}^{m\times k}$. Then

$\max\\{|I\cup J|:I,J\subseteq[k],\ r_{A}(I)=I,\ r_{A}(J)=J\\}\ =\
\min\\{k-|U|+2r_{A}(U):U\subseteq[k]\\}.$

### Affine rank and generic solutions

Given vectors $x_{1},\ldots,x_{k}\in\mathbb{F}^{n}$, their _affine rank_
$\operatorname{arank}\\{x_{1},\ldots,x_{k}\\}$ is the maximum number of
affinely independent vectors in $\\{x_{1},\ldots,x_{k}\\}$. In other words,

$\operatorname{arank}\\{x_{1},\ldots,x_{k}\\}=\operatorname{rank}(X),\text{
where }X=\begin{pmatrix}1&\cdots&1\\\
x_{1}&\cdots&x_{k}\end{pmatrix}\in\mathbb{F}^{(n+1)\times k}.$

For $x=(x_{1},\ldots,x_{k})$ we will also denote
$\operatorname{arank}(x)=\operatorname{arank}(x_{1},\ldots,x_{k})=\operatorname{arank}\\{x_{1},\ldots,x_{k}\\}$.

######  Definition 6.

For $(x_{1},\ldots,x_{k})\in(\mathbb{F}^{n})^{k}$, let

$\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k})=\\{(\mu_{1},\ldots,\mu_{k})\in\mathbb{F}_{q}^{k}:\mu_{1}x_{1}+\cdots+\mu_{k}x_{k}=0,\quad\mu_{1}+\cdots+\mu_{k}=0\\}.$

So the elements of
$\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k})$ correspond to
the affine relations between $x_{1},\ldots,x_{k}$.

######  Definition 7.

If $x=(x_{1},\ldots,x_{k})$ is a solution to $Ax^{\mathsf{T}}=0$, we say that
$(x_{1},\ldots,x_{k})$ is a _generic_ solution if
$\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k})=\operatorname*{rowspace}(A)$.

######  Lemma 8.

Let $\mathbb{F}$ be a field and let $x_{1},\ldots,x_{k}\in\mathbb{F}^{n}$.
Then

$\operatorname{arank}(x_{1},\ldots,x_{k})+\dim(\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k}))=k.$

###### Proof.

Let $A\in\mathbb{F}^{(n+1)\times k}$ be the matrix

$A=\begin{pmatrix}1&\cdots&1\\\ x_{1}&\cdots&x_{k}\end{pmatrix}.$

For $I\subseteq[k]$ the vectors $x_{i},\ i\in I$ are affinely independent if
and only if the columns of $A$ indexed by $I$ are linearly independent. So
$\operatorname{rank}(A)=\operatorname{arank}(x_{1},\ldots,x_{k})$. Since
$\ker(A)=\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k})$, the
result follows from the rank-nullity theorem. ∎

######  Lemma 9.

Let $A\in\mathbb{F}^{m\times k}$ be a row-balanced matrix of rank $m$. Let
$x=(x_{1},\ldots,x_{k})$ be a solution to $Ax^{\mathsf{T}}=0$. Then
$\operatorname{arank}(x_{1},\ldots,x_{k})\leq k-m$. Equality holds if and only
if $(x_{1},\ldots,x_{k})$ is a generic solution of $Ax^{\mathsf{T}}=0$.

###### Proof.

Since $Ax^{\mathsf{T}}=0$, the row space of $A$ is contained in
$\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k})$. Therefore we
have
$m=\operatorname{rank}(A)\leq\dim(\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k}))$,
so it follows from Lemma 8 that

$\operatorname{arank}(x_{1},\ldots,x_{k})=k-\dim(\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k}))\leq
k-m.$

Clearly we have equality if and only if the row space of $A$ is equal to
$\operatorname{Ann}_{\operatorname{bal}}(x_{1},\ldots,x_{k})$, which is
equivalent to $x$ being a generic solution. ∎

######  Lemma 10.

Let $A\in\mathbb{F}^{m\times k}$ be a balanced matrix of rank $m$. Then
$Ax^{\mathsf{T}}=0$ has a generic solution in $\mathbb{F}^{k-m-1}$.

###### Proof.

By permuting the $k$ columns of $A$, and performing elementary row-operations,
we may assume that $A$ is of the form $A=\begin{pmatrix}I&B\end{pmatrix}$. Let
$z_{m+1},\ldots,z_{k}\in\mathbb{F}^{k-m-1}$ be affinely independent (e.g.
$z_{k}=0$, $z_{m+i}=e_{i}$ for $i\in[k-m-1]$) and set
$z_{i}=-\sum_{j\in[k-m]}B_{ij}z_{j}$ for $i\in[m]$. Then
$z=(z_{1},\ldots,z_{k})$ is a solution to $Ax^{\mathsf{T}}=0$ and
$\operatorname{arank}(z)=k-m$. So by Lemma 9, $z$ is a generic solution to
$Ax^{\mathsf{T}}=0$. ∎

######  Lemma 11.

Let $A\in\mathbb{F}^{m\times k}$ be a row-balanced matrix of rank $m$. Let
$x=(x_{1},\ldots,x_{k})$ be a solution to $Ax^{\mathsf{T}}=0$ such that
$\operatorname{arank}(x)=k-m$. Let $U\subseteq[k]$ have size $|U|=m$. Then

$\text{$U$ is a basis of $A$}\iff\operatorname{arank}\\{x_{i}:i\in[k]\setminus
U\\}=k-m.$

###### Proof.

Let $r=r_{A}(U)$ be the rank of the submatrix induced by the columns in $U$.
By applying row operations to $A$ (and permuting columns in $U$) we may assume
that this submatrix is equal to

$\begin{pmatrix}I_{r}&B\\\ 0&0\end{pmatrix}$

where $I_{r}$ is the $r\times r$ identity matrix.

If $U$ is a basis of $A$, then $r=m$ and the system $Ax^{\mathsf{T}}=0$
expresses for every $j\in U$ the vector $x_{j}$ as an affine combination of
$\\{x_{i}:i\in[k]\setminus U\\}$. So
$\operatorname{arank}\\{x_{i}:i\in[k]\setminus
U\\}=\operatorname{arank}\\{x_{i}:i\in[k]\\}=k-m$.

If $U$ is not a basis of $A$, then $r<m$ and hence the equation
$a_{m1}x_{1}+\cdots+a_{mk}x_{k}$ gives an affine relation between the vectors
in $\\{x_{i}:i\in[k]\setminus U\\}$ as $a_{mj}=0$ for all $j\in U$. So
$\operatorname{arank}\\{x_{j}:j\in[k]\setminus U\\}<k-m$. ∎

##  3 Tame matrices

To show that a system $Ax^{\mathsf{T}}=0$ is temperate, we will rely on the
slice rank method not only for the system $Ax^{\mathsf{T}}=0$ itself, but also
for implied systems. For this reason, we want the number of variables in an
implied system to be more than twice the number of equations. If this is the
case, we say that $A$ is _tame_.

######  Definition 12.

Let $A\in\mathbb{F}^{m\times k}$ be a matrix of rank $m$. We say that $A$ is
_tame_ if, by elementary row-operations and column permutations, we cannot
bring $A$ into the form $\left(\begin{smallmatrix}A^{\prime}&0\\\
B&C\end{smallmatrix}\right)$ where $A^{\prime}\in\mathbb{F}^{m^{\prime}\times
k^{\prime}}$ and $k^{\prime}\leq 2m^{\prime}$.

######  Lemma 13.

Let $A\in\mathbb{F}^{m\times k}$ be a matrix of rank $m$. Then, the following
are equivalent:

  * (i)

$A$ is tame.

  * (ii)

For all $U\subsetneq[k]$ we have $2r_{A}(U)\geq 2m+1-k+|U|$.

  * (iii)

For all $i\in[k]$ the set $[k]\setminus\\{i\\}$ contains two disjoint bases of
$A$.

###### Proof.

$\textup{(ii)}\Rightarrow\textup{(i)}$. Assume (ii) holds, and suppose that
$A$ is not tame. Using elementary row-operations and permuting columns, we can
bring $A$ into the form $\tilde{A}=\left(\begin{smallmatrix}A^{\prime}&0\\\
B&C\end{smallmatrix}\right)$ where $A^{\prime}\in\mathbb{F}^{m^{\prime}\times
k^{\prime}}$ with $k^{\prime}\leq 2m^{\prime}$. Since $r_{A}$ is preserved
under elementary row-operations, the matrix $\tilde{A}$ also satisfies (ii).
However, taking $U=\\{k^{\prime}+1,\ldots,k\\}$ we obtain a contradiction.
Indeed, since $C$ has rank at most $m-m^{\prime}$, we have
$r_{\tilde{A}}(U)\leq m-m^{\prime}$ and therefore

$2r_{\tilde{A}}(U)\leq 2m-2m^{\prime}\leq 2m-k^{\prime}=2m-k+|U|.$

$\textup{(i)}\Rightarrow\textup{(ii)}$. Suppose that (ii) does not hold and
let $U\subsetneq[k]$ be such that $2r_{A}(U)\leq 2m-k+|U|$. Set
$k^{\prime}=k-|U|$ and $m^{\prime}=m-r_{A}(U)$. Then

$k^{\prime}=k-|U|\leq 2m-2r_{A}(U)=2m^{\prime}.$

By permuting columns of $A$, we may assume that
$U=\\{k^{\prime}+1,\ldots,k\\}$. By performing elementary row-operations, we
can bring $A$ into the form $\left(\begin{smallmatrix}A^{\prime}&0\\\
B&C\end{smallmatrix}\right)$, where $C$ is a $|U|\times r_{A}(U)$ matrix. Then
$A^{\prime}$ is an $m^{\prime}\times k$ matrix with $k^{\prime}\leq
2m^{\prime}$.

$\textup{(ii)}\Rightarrow\textup{(iii)}$. Let $i\in[k]$. For every
$U\subseteq[k]\setminus\\{i\\}$ we have $2r_{A}(U)\geq 2m+1-k+|U|$, or
equivalently,

$(k-1)-|U|+2r_{A}(U)\geq 2m.$

By Proposition 5 there exist $I,J\subseteq[k]\setminus\\{i\\}$ such that
$|I\cup J|=2m$ and $r_{A}(I)=|I|$ and $r_{A}(J)=|J|$. Hence, $I$ and $J$ are
two disjoint bases of $A$.

$\textup{(iii)}\Rightarrow\textup{(ii)}$. Let $U\subsetneq[k]$ and let
$i\in[k]\setminus U$. Let $B,B^{\prime}\subseteq[k]\setminus\\{i\\}$ be two
disjoint bases. Then

$|U\cap(B\cup B^{\prime})|\geq|U|-(k-1-|B\cup B^{\prime}|)=|U|-k+1+2m.$

It follows that

$2r_{A}(U)\geq 2\max\\{|U\cap B|,|U\cap B^{\prime}|\\}\geq|U\cap B|+|U\cap
B^{\prime}|\geq|U|-k+1+2m.$

∎

######  Remark 14.

Note that Lemma 13 gives a good characterization of tame matrices in the
following sense: if a matrix is not tame, this can be certified by giving a
set $U\subsetneq[k]$ that violates the inequality in (ii), and if a matrix is
tame, this can be certified by giving two disjoint bases contained in
$[k]\setminus\\{i\\}$ for every $i\in[k]$ as in (iii). In fact, since finding
a maximum size set that is the union of two independent sets can be done in
polynomial time by the matroid union algorithm, we can check in polynomial
time if a given matrix is tame by checking (iii).

######  Lemma 15.

Let $A\in\mathbb{F}^{(m+1)\times(2m+1)}$ have rank $m+1$, and let $A^{\prime}$
be obtained by deleting the last row of $A$. Suppose that $A^{\prime}$ is
tame. Then, there are bases $B_{1},B_{2}$ of $A$ such that $B_{1}\cup
B_{2}=[2m+1]$.

###### Proof.

Let $U\subseteq[2m+1]$. If $|U|=2m+1$, then $r_{A}(U)=m+1$. If $|U|=2\ell+1$
for some $\ell\in\\{0,\ldots,m-1\\}$, we have $r_{A}(U)\geq
r_{A^{\prime}}(U)\geq\ell+1$ by Lemma 13 since $A^{\prime}$ is tame. If
$|U|=2\ell+2$ and $u\in U$, we have $r_{A}(U)\geq
r_{A}(U\setminus\\{u\\})\geq\ell+1$. So we see that

$2r_{A}(U)\geq|U|\quad\text{for all $U\subseteq[2m+1]$}.$

It now follows by Proposition 5 that there are $I_{1},I_{2}\subseteq[2m+1]$
with $r_{A}(I_{1})=|I_{1}|$, $r_{A}(I_{2})=|I_{2}|$, and $|I_{1}\cup
I_{2}|=2m+1$. Extending for $i=1,2$ the set $I_{i}$ to a basis $B_{i}$ of $A$
completes the proof. ∎

The following proposition will be of key importance in the proof of Theorem A.

######  Proposition 16.

Let $A\in\mathbb{F}^{m\times(2m+1)}$ be a balanced, tame matrix of rank $m$.
Let $x$ be a solution to $Ax^{\mathsf{T}}=0$ with
$\operatorname{arank}(x)=r\leq m$. Then there exist disjoint subsets
$I_{1},I_{2}\subseteq[2m+1]$ of size $r$, such that
$\operatorname{arank}\\{x_{i}:i\in I_{1}\\}=\operatorname{arank}\\{x_{i}:i\in
I_{2}\\}=r$.

###### Proof.

Let $m^{\prime}=2m+1-r\geq m+1$. We can extend $A$ with additional rows to
obtain a balanced matrix $A^{\prime}\in\mathbb{F}^{m^{\prime}\times(2m+1)}$ of
rank $m^{\prime}$ such that $A^{\prime}x^{\mathsf{T}}=0$ (extend the rows of
$A$ to a basis of $\operatorname{Ann}_{\operatorname{bal}}(x)$.) Note that we
add $m+1-r\geq 1$ rows in total.

Let $A^{\prime\prime}$ be the submatrix of $A^{\prime}$ consisting of the
first $m+1$ rows (so $A$ with one row added). By Lemma 15 there exist subsets
$J_{1},J_{2}\subseteq[2m+1]$ of size $m+1$ such that $J_{1}\cup J_{2}=[2m+1]$
and $r_{A^{\prime\prime}}(J_{1})=r_{A^{\prime\prime}}(J_{2})=m+1$. Clearly, we
then also have: $r_{A^{\prime}}(J_{1})=r_{A^{\prime}}(J_{2})=m+1$. It follows
that there are bases $B_{1}$ and $B_{2}$ of $A^{\prime}$ such that $B_{1}\cup
B_{2}=[2m+1]$. Since $|B_{1}|=|B_{2}|=2m+1-r$, it follows that
$I_{1}:=[2m+1]\setminus B_{1}$ and $I_{2}:=[2m+1]\setminus B_{2}$ are disjoint
sets of size $r$. By Lemma 11, $\operatorname{arank}\\{x_{i}:i\in
I_{1}\\}=r=\operatorname{arank}\\{x_{i}:i\in I_{2}\\}$. ∎

### Extending tame matrices

In this subsection we show the following proposition.

######  Proposition 17.

Let $A\in\mathbb{F}^{m\times k}$ be tame and row-balanced with $k>2m+1$. Then
$A$ can be extended to a tame, row-balanced matrix
$A^{\prime}\in\mathbb{F}^{m^{\prime}\times(2m^{\prime}+1)}$ such that if
$x^{\prime}=(x_{1},\ldots,x_{k^{\prime}})$ is a generic solution to
$A^{\prime}(x^{\prime})^{\mathsf{T}}=0$, then $x=(x_{1},\ldots,x_{k})$ is a
generic solution to $Ax^{\mathsf{T}}=0$.

Before proving the proposition, we need a number of lemmas.

######  Lemma 18.

Let $A\in\mathbb{F}^{m\times k}$ be tame. Suppose that $k\geq 2m+2$. Then
there exist $i\in[k-1]$ such that for all
$\alpha,\beta,\gamma\in\mathbb{F}\setminus\\{0\\}$ the matrix

$A^{\prime}=\begin{pmatrix}A&0\\\ \alpha e_{i}^{\mathsf{T}}+\beta
e_{k}^{\mathsf{T}}&\gamma\end{pmatrix}\in\mathbb{F}^{(m+1)\times(k+1)}$

is tame.

###### Proof.

For $U\subseteq[k-1]$ define $f(U)=2r_{A}(U)-2m-1+k-|U|$. Since $A$ is tame,
it follows by Lemma 13 that $f(U)\geq 0$ for every $U\subseteq[k-1]$. Let

$\mathcal{T}=\\{U\subseteq[k-1]:f(U)=0\\}.$

Note that $[k-1]\in\mathcal{T}$ since $r_{A}([k-1])\leq m$. So $\mathcal{T}$
is nonempty.

Claim. Let $U,V\in\mathcal{T}$. Then $U\cup V,U\cap V\in\mathcal{T}$.

Proof of claim. By the submodularity of $r_{A}$ we have $f(U\cap V)+f(U\cup
V)\leq f(U)+f(V)=0$. Since $f(U\cap V)\geq 0$ and $f(U\cup V)\geq 0$, we have
$f(U\cap V)=f(U\cup V)=0$. $\scriptstyle\blacksquare$

Let $I\subseteq[k-1]$ be the unique inclusionwise minimal subset of
$\mathcal{T}$. Since $\emptyset\not\in\mathcal{T}$ as $k>2m+1$, the set $I$ is
nonempty. Let $i\in I$. So $i\in U$ for all $U\in\mathcal{T}$. We will show
that for this choice of $i$ the matrix $A^{\prime}$ is tame for all
$\alpha,\beta,\gamma\in\mathbb{F}\setminus\\{0\\}$.

Let $U\subsetneq[k+1]$ be arbitrary. By Lemma 13, it suffices to show that

$2r_{A^{\prime}}(U)\geq 2(m+1)+1-(k+1)+|U|.$

Suppose that for some $j\in\\{i,k,k+1\\}$ we have $j\in U$. If $k+1\in U$ we
choose $j=k+1$. Note that $U\setminus\\{j\\}\subsetneq[k]$. Since
$\alpha,\beta,\gamma\neq 0$, we have $r_{A^{\prime}}(U)\geq
1+r_{A}(U\setminus\\{j\\})$. Since $A$ is tame, we obtain

$\displaystyle 2r_{A^{\prime}}(U)$ $\displaystyle\geq
2+2r_{A}(U\setminus\\{j\\})$ $\displaystyle\geq 2+2m+1-k+|U\setminus\\{j\\}|$
$\displaystyle=2(m+1)+1-(k+1)+|U|$

as desired.

Therefore, we may assume that $U\cap\\{i,k,k+1\\}=\emptyset$. So
$U\subseteq[k-1]$ and $U\not\in\mathcal{T}$. It follows that $f(U)\geq 1$, and
therefore

$\displaystyle 2r_{A^{\prime}}(U)$ $\displaystyle\geq 2r_{A}(U)$
$\displaystyle\geq 1+(2m+1-k+|U|)$ $\displaystyle=2(m+1)+1-(k+1)+|U|.$

∎

Note that if $\mathbb{F}\neq\mathbb{F}_{2}$, we can choose elements
$\alpha,\beta,\gamma\in\mathbb{F}\setminus\\{0\\}$ such that
$\alpha+\beta+\gamma=0$. Hence, if $A$ is row-balanced, we can take
$A^{\prime}$ to be row-balanced as well. For $\mathbb{F}=\mathbb{F}_{2}$ this
does not work. In fact the row-balanced tame matrix
$\begin{bmatrix}1&1&1&1\end{bmatrix}\in\mathbb{F}_{2}^{1\times 4}$ cannot be
extended to a row-balanced tame matrix $A^{\prime}\in\mathbb{F}_{2}^{2\times
5}$. For this reason, we need the following lemma.

######  Lemma 19.

Let $A\in\mathbb{F}_{2}^{m\times k}$ be tame. Suppose that $k\geq 2m+2$. Then
there exists $i\in[k-1]$ such that the matrix
$A^{\prime\prime}\in\mathbb{F}_{2}^{(m+3)\times(k+5)}$ given by

$A^{\prime\prime}:=\begin{pmatrix}A&0&0&0&0&0\\\
e_{i}^{\mathsf{T}}+e_{k}^{\mathsf{T}}&1&0&1&0&0\\\
e_{i}^{\mathsf{T}}&1&1&0&1&0\\\ e_{k}^{\mathsf{T}}&1&1&0&0&1\end{pmatrix}.$

is tame.

Note that if $A$ has rank $m$ and is row-balanced, then $A^{\prime\prime}$ has
rank $m+3$ and is row balanced.

###### Proof.

Let $i$ be as in the conclusion of Lemma 18. So the submatrix

$A^{\prime}=\begin{pmatrix}A&0\\\
e_{i}^{\mathsf{T}}+e_{k}^{\mathsf{T}}&1\end{pmatrix}$

of $A^{\prime\prime}$ induced by the first $k+1$ columns and $m+1$ rows is
tame. We will use the shorthand notations $r^{\prime}=r_{A^{\prime}}$ and
$r^{\prime\prime}=r_{A^{\prime\prime}}$. By Lemma 13 we know that

$2r^{\prime}(U)\geq 2(m+1)+1-(k+1)+|U|\quad\text{for all $U\subsetneq[k+1]$}.$

Let $U\subsetneq[k+5]$ be arbitrary. To show that $A^{\prime\prime}$ is tame,
it suffices to show that

$2r^{\prime\prime}(U)\geq 2(m+1)+1-(k+1)+|U|$

since $2(m+3)+1-(k+5)=2(m+1)+1-(k+1)$.

By permuting the first $k-1$ columns, we may assume without loss of generality
that $i=k-1$. Let $U_{1}=U\cap[k-2]$ and $U_{2}=U\setminus
U_{1}=U\cap\\{k-1,\ldots,k+5\\}$. First consider the case that $|U_{2}|\leq
6$. Note that the submatrix of $A^{\prime\prime}$ induced by the last three
rows and the last seven columns represent all $7$ vectors in
$\mathbb{F}_{2}^{3}\setminus\\{0\\}$. Since any set of $t\leq 6$ vectors in
$\mathbb{F}_{2}^{3}\setminus\\{0\\}$ spans a subspace of dimension at least
$t/2$, we see that $r^{\prime\prime}(U)\geq r^{\prime}(U_{1})+|U_{2}|/2$.
Hence,

$\displaystyle 2r^{\prime\prime}(U)$ $\displaystyle\geq
2r^{\prime}(U_{1})+|U_{2}|$ $\displaystyle\geq 2(m+1)+1-(k+1)+|U_{1}|+|U_{2}|$
$\displaystyle=2(m+1)+1-(k+1)+|U|.$

Now consider the remaining case that $|U_{2}|=7$. Since $k+4$ and $k+5$ belong
to $U$, we have $r^{\prime\prime}(U)\geq 2+r^{\prime}(U\cap[k+1])$. Since $U$
does not contain $[k+1]$ (as $U\not=[k+5])$, we have

$\displaystyle 2r^{\prime\prime}(U)$ $\displaystyle\geq
2r^{\prime}(U\cap[k+1])+4$ $\displaystyle\geq 2(m+1)+1-(k+1)+|U\cap[k+1]|+4$
$\displaystyle=2(m+1)+1-(k+1)+|U|.$

∎

We are now ready to prove Proposition 17.

###### Proof.

It suffices to show that $A$ can be extended to a row-balanced, tame
$k^{\prime}\times m^{\prime}$ matrix $A^{\prime}$ such that the following two
properties hold:

  * •

$k^{\prime}-2m^{\prime}=(k-2m)-1$,

  * •

if $x^{\prime}=(x_{1},\ldots,x_{k^{\prime}})$ satisfies
$A^{\prime}(x^{\prime})^{\mathsf{T}}=0$ and
$\operatorname{arank}\\{x^{\prime}\\}=k^{\prime}-m^{\prime}$, then
$x=(x_{1},\ldots,x_{k})$ satisfies $Ax^{\mathsf{T}}=0$ and
$\operatorname{arank}(x)=k-m$.

Indeed, repeating this step $k-2m-1$ times results in a
$(k-m-1)\times(2(k-m-1)+1)$ matrix with the required properties. Note that we
used the characterization of generic solutions from Lemma 9.

Let us first consider the case that $\mathbb{F}\neq\mathbb{F}_{2}$. Let
$\alpha,\beta,\gamma\in\mathbb{F}\setminus\\{0\\}$ be such that
$\alpha+\beta+\gamma=0$. Let $m^{\prime}=m+1$ and $k^{\prime}=k+1$. By Lemma
18, there exists $i\in[k-1]$ such that the matrix
$A^{\prime}\in\mathbb{F}^{m^{\prime}\times k^{\prime}}$ given by

$A^{\prime}=\begin{pmatrix}A&0\\\ \alpha e_{i}+\beta
e_{k}&\gamma\end{pmatrix}$

is tame. Since $\alpha+\beta+\gamma=0$, the matrix $A^{\prime}$ is balanced.
Now suppose $x^{\prime}=(x_{1},\ldots,x_{k+1})$ satisfies
$A^{\prime}(x^{\prime})^{\mathsf{T}}=0$ and
$\operatorname{arank}(x^{\prime})=(k+1)-(m+1)$. Let $x=(x_{1},\ldots,x_{k})$.
Clearly, $Ax^{\mathsf{T}}=0$. Since $\gamma\neq 0$, the vector $x_{k+1}$ is an
affine combination of $x_{1},\ldots,x_{k}$, so
$\operatorname{arank}(x_{1},\ldots,x_{k})=\operatorname{arank}(x_{1},\ldots,x_{k+1})=k-m$
as required.

Now let us consider the case that $\mathbb{F}=\mathbb{F}_{2}$. By Lemma 19, we
obtain the tame, row-balanced matrix
$A^{\prime}\in\mathbb{F}_{2}^{m^{\prime}\times k^{\prime}}$ with
$m^{\prime}=m+3$ and $k^{\prime}=k+5$ given by

$A^{\prime}:=\begin{pmatrix}A&0&0&0&0&0\\\ e_{i}+e_{k}&1&0&1&0&0\\\
e_{i}&1&1&0&1&0\\\ e_{k}&1&1&0&0&1\end{pmatrix},$

where $i\in[k-1]$. Let $x^{\prime}=(x_{1},\ldots,x_{k^{\prime}})$ satisfy
$A^{\prime}(x^{\prime})^{\mathsf{T}}=0$ and
$\operatorname{arank}(x^{\prime})=k^{\prime}-m^{\prime}$. Let
$x=(x_{1},\ldots,x_{k})$. Clearly, we have $Ax^{\mathsf{T}}=0$. Since
$x_{k+3}$, $x_{k+4}$ and $x_{k+5}$ are affinely dependent on
$x_{1},\ldots,x_{k+2}$, we have
$\operatorname{arank}(x^{\prime})\leq\operatorname{arank}(x_{1},\ldots,x_{k+2})\leq\operatorname{arank}(x)+2$.
We obtain

$\operatorname{arank}(x)\geq\operatorname{arank}(x^{\prime})-2=(k+5)-(m+3)-2=k-m.$

Note that by Lemma 9 we also have $\operatorname{arank}(x)\leq k-m$, so we
have $\operatorname{arank}(x)=k-m$ as required. ∎

##  4 Super saturation

In this section we prove a super saturation result (Proposition 22) that is
essential to the proof of our main theorem. The proof is based on a standard
subspace sampling argument (see for instance Exercise 10.1.9 of [TV06] or
[Fra21]). We begin by stating some preliminaries.

For $d,n\in\mathbb{N}$ the _Gaussian binomial coefficient_
${\genfrac{[}{]}{0.0pt}{}{n}{d}}_{q}$ is given by

${\genfrac{[}{]}{0.0pt}{}{n}{d}}_{q}=\begin{cases}\prod_{i=0}^{d-1}\frac{1-q^{n-i}}{1-q^{d-i}}&\text{if
}d\leq n\\\ 0&\text{if }d>n\end{cases}.$

The following fact is well-known.

######  Lemma 20.

Let $k\leq d\leq n$ be nonnegative integers. Then the number of
$d$-dimensional linear subspaces of $\mathbb{F}_{q}^{n}$ containing a given
$k$-dimensional linear subspace is ${\genfrac{[}{]}{0.0pt}{}{n-k}{d-k}}_{q}$.

###### Proof.

Let $V\subseteq\mathbb{F}_{q}^{n}$ be a $k$-dimensional linear subspace and
let $b_{1},\ldots,b_{k}$ be a basis of $V$. The number of $d-k$-tuples
$(b_{k+1},\ldots,b_{d})$ such that $b_{1},\ldots,b_{d}$ are linearly
independent vectors in $\mathbb{F}_{q}^{n}$, is equal to
$(q^{n}-q^{k})(q^{n}-q^{k+1})\cdots(q^{n}-q^{d-1})$. Indeed, for
$i=k+1,\ldots,d$ we can choose $b_{i}$ arbitrarily in
$\mathbb{F}_{q}^{n}\setminus\mathrm{span}(b_{1},\ldots,b_{i-1})$. Thus, we
obtain a $d$-dimensional subspace $W:=\mathrm{span}(b_{1},\ldots,b_{d})$
containing $V$.

Each subspace $W\supseteq V$ of dimension $d$ is thus obtained
$(q^{d}-q^{k})\cdots(q^{d}-q^{d-1})$ times, since there are that many ways to
extend $b_{1},\ldots,b_{k}$ to a basis $b_{1},\ldots,b_{d}$ of $W$. We
conclude that the number of $d$-dimensional subspaces containing $V$ is equal
to

$\frac{(q^{n}-q^{k})\cdots(q^{n}-q^{d-1})}{(q^{d}-q^{k})\cdots(q^{d}-q^{d-1})}={\genfrac{[}{]}{0.0pt}{}{n-k}{d-k}}_{q}.$

∎

Note that Lemma 20 implies that the number of $d$-dimensional affine subspaces
of $\mathbb{F}_{q}^{n}$ that contain a given subset
$S\subseteq\mathbb{F}_{q}^{n}$ of affine rank $r$, is equal to
${\genfrac{[}{]}{0.0pt}{}{n-r+1}{d-r+1}}_{q}$. Indeed, by shifting, we may
assume that $0\in S$ and then $\dim\operatorname{span}(S)=r-1$.

We will need the following bounds on the Gaussian binomial coefficients.

######  Lemma 21.

Let $d\leq n$ be nonnegative integers. Then

$q^{d(n-d)}\leq{\genfrac{[}{]}{0.0pt}{}{n}{d}}_{q}\leq 4q^{d(n-d)}.$

###### Proof.

The lower bound follows directly from the fact that for all
$i\in\\{0,\ldots,d-1\\}$ we have

$\frac{q^{n-i}-1}{q^{d-i}-1}\geq\frac{q^{n-i}}{q^{d-i}}=q^{n-d}.$

The upper bound follows from the fact that for all $i\in\\{0,\ldots,d-1\\}$ we
have

$\frac{q^{n-i}-1}{q^{d-i}-1}\leq q^{n-d}(1+\frac{1}{q^{d-i}-1})\leq
q^{n-d}(1+\frac{1}{2^{d-i}-1})$

and the fact that

$\prod_{i=0}^{d-1}(1+\frac{1}{2^{d-i}-1})\ =\
2\prod_{i=2}^{d}(1+\frac{1}{2^{i}-1})\ \leq\
2e^{\sum_{i=2}^{d}\frac{1}{2^{i}-1}}\ \leq\
2e^{\frac{1}{3}\sum_{i=0}^{d-2}\frac{1}{2^{i}}}\ \leq\ 2e^{\frac{2}{3}}\leq
4.$

∎

######  Proposition 22.

Let $A\in\mathbb{F}_{q}^{m\times k}$ be a row-balanced matrix of rank $m$. Let
$r$ be a positive integer and let $\delta\in(0,1]$. Suppose that for all
$n\geq n_{0}$ and all $S\subseteq\mathbb{F}_{q}^{n}$ of cardinality $|S|\geq
q^{(1-\delta)n}$ the set $S$ contains a solution to $Ax^{\mathsf{T}}=0$ of
affine rank $\geq r$.

Let $\delta^{\prime}\in(0,\delta)$. Define

$n_{1}=\lceil\max(\tfrac{\delta}{\delta^{\prime}}n_{0},\tfrac{2+\delta}{\delta-\delta^{\prime}})\rceil,\qquad\epsilon=\delta^{\prime}\cdot\frac{r-1+2\delta}{\delta},\qquad
C=\frac{q^{2}-2}{4q^{2}}q^{-\frac{(r-1+\delta)(2+\delta)}{\delta}}.$

Then for every $n\geq n_{1}$ and $S\subseteq\mathbb{F}_{q}^{n}$ of size
$|S|\geq q^{(1-\delta^{\prime})n}$, the set $S$ contains at least
$Cq^{rn-\epsilon n}$ solutions to $Ax^{\mathsf{T}}=0$ of affine rank at least
$r$.

###### Proof.

Let $N=\lceil\frac{n\delta^{\prime}+2}{\delta}\rceil$. Note that $N\leq n$ by
definition of $n_{1}$. Let $S\subseteq\mathbb{F}_{q}^{n}$ have cardinality
$|S|\geq q^{(1-\delta^{\prime})n}$. Let us call an $N$-dimensional affine
subspace $V$ of $\mathbb{F}_{q}^{n}$ _rich_ if $|V\cap S|>2q^{(1-\delta)N}$.
If $V$ is rich, then $S\cap V$ contains a solution of affine rank at least $r$
since $N\geq n_{0}$. In fact, since $(S\setminus T)\cap V\geq q^{(1-\delta)N}$
for every set $T$ of size at most $\lceil q^{(1-\delta)N}-1\rceil$, the set
$S\cap V$ must contain at least $\lceil q^{(1-\delta)N}\rceil$ solutions of
rank at least $r$.

Consider the partition of $\mathbb{F}_{q}^{n}$ into the $q^{n-N}$ cosets of a
given $N$-dimensional linear subspace. Let $P$ be the proportion of cosets
that are rich. Then

$Pq^{n-N}q^{N}+(1-P)q^{n-N}2q^{(1-\delta)N}\geq|S|\geq
q^{(1-\delta^{\prime})n}.$

Rearranging and dividing by $q^{n}$ gives

$P\geq\frac{q^{-\delta^{\prime}n}-2q^{-\delta N}}{1-2q^{-\delta N}}.$

Since $\delta N\geq\delta^{\prime}n+2$, it follows that

$P\geq\tfrac{q^{2}-2}{q^{2}}q^{-\delta^{\prime}n}.$

Let $M$ be the number of pairs $(V,x)$ where $V\subseteq\mathbb{F}_{q}^{n}$ is
rich and $x=(x_{1},\ldots,x_{k})$ is a solution of affine rank at least $r$
with $x_{1},\ldots,x_{k}\in V\cap S$. Then

$M\geq P\cdot q^{n-N}{\genfrac{[}{]}{0.0pt}{}{n}{N}}_{q}\cdot
q^{(1-\delta)N},$

since there are $P\cdot q^{n-N}{\genfrac{[}{]}{0.0pt}{}{n}{N}}_{q}$ rich
subspaces $V$ and for each such $V$ there are at least $q^{(1-\delta)N}$
solutions in $V\cap S$ of rank at least $r$. Conversely, every solution of
affine rank at least $r$ is contained in at most
${\genfrac{[}{]}{0.0pt}{}{n-r+1}{N-r+1}}_{q}$ rich affine subspaces $V$. We
conclude that the number of solutions of affine rank at least $r$ in $S$ is at
least

$\displaystyle\frac{P\cdot q^{n-N}\cdot
q^{(1-\delta)N}{\genfrac{[}{]}{0.0pt}{}{n}{N}}_{q}}{{\genfrac{[}{]}{0.0pt}{}{n-r+1}{N-r+1}}_{q}}$
$\displaystyle\geq$ $\displaystyle\tfrac{1}{4}P\cdot q^{rn-N(r-1+\delta)}$
$\displaystyle\geq$
$\displaystyle\frac{q^{2}-2}{4q^{2}}q^{n(r-\delta^{\prime})-N(r-1+\delta)}$
$\displaystyle\geq$
$\displaystyle\frac{q^{2}-2}{4q^{2}}q^{-(r-1+\delta)\frac{1+\delta}{\delta}}\cdot
q^{n(r-\delta^{\prime})-n\frac{\delta^{\prime}}{\delta}(r-1+\delta)}$
$\displaystyle=$ $\displaystyle Cq^{nr-\epsilon n},$

where we used Lemma 21, the lower bound on $P$, and the fact that
$N\leq\frac{\delta^{\prime}n}{\delta}+\tfrac{2+\delta}{\delta}$ in the three
inequalities, respectively. ∎

######  Remark 23.

The obtained value of $\epsilon$ is in general not optimal. In the ‘cap set
case’ (i.e. the system is $x_{1}-2x_{2}+x_{3}=0$ and $r=2$), we can take
$\delta=1-\log_{3}(2.7552)$ and obtain
$\epsilon=(2+1/\delta)\delta^{\prime}\approx 14.9\delta^{\prime}$. However,
using the bound on the arithmetic triangle removal proved in [FL17], one can
show that we can take $\epsilon=(1+1/\delta)\delta^{\prime}\approx
13.9\delta^{\prime}$ as was shown in [PRN05].

##  5 Proof of Theorem A

In this section, we will prove Theorem A. By Proposition 17, we may restrict
ourselves to the case $k=2m+1$:

######  Theorem 24.

Let $A\in\mathbb{F}_{q}^{m\times(2m+1)}$ be a tame, row-balanced matrix. Then
the system $Ax^{\mathsf{T}}=0$ is temperate.

We will need the following lemma.

######  Lemma 25.

Let $M$ be an $n\times n$ matrix with $N$ nonzero elements such that every row
and every column has at most $k$ nonzero elements. Then
$\operatorname{rank}(M)\geq\frac{N}{k^{2}}$.

###### Proof.

Let $I\subseteq[n]$ be a maximal set of linearly independent columns of $M$.
Let $J$ be the set of rows $j$ for which there is a column $i\in I$ with
$M_{ij}\neq 0$. Then $|J|\leq k|I|$ and the support of $M$ must be contained
in the rows indexed by $J$ by maximality of $I$. On the other hand, the rows
in $J$ together contain at most $k|J|\leq k^{2}|I|$ nonzero entries. So $N\leq
k^{2}|I|$. ∎

The remainder of this section is devoted to proving Theorem 24. It suffices to
show the following for all $r\in[m+1]$:

$\mathbf{P}(r):\ \parbox[t]{346.89731pt}{There exists a $\delta_{r}>0$ such
that for all sufficiently large $n$, every subset
$S\subseteq\mathbb{F}_{q}^{n}$ with $|S|\geq q^{(1-\delta_{r})n}$ contains a
solution $x$ to $A{x}^{\mathsf{T}}=0$ with $\operatorname{arank}(x)\geq r$.}$

The proof is by induction on $r$. The base case $r=1$ is trivial since for any
$v\in S$ a solution of affine rank $1$ is given by $x=(v,\ldots,v)$. Hence, we
can take $\delta_{1}=1$.

Now let $r\leq m$ and assume that $\mathbf{P}(r)$ is true. We show that
$\mathbf{P}(r+1)$ is true. Let $d=n(q-1)\tfrac{m}{2m+1}$. By Theorem 2, there
is an $\epsilon\in(0,1)$ such that $m_{q,n,d}=o(q^{(1-\epsilon)n})$ and
$m_{q,rn,rd}=o(q^{rn-\epsilon n})$.

By Proposition 22, there is a $\delta_{r+1}\in(0,\delta_{r})$ such that every
subset $S\subseteq\mathbb{F}_{q}^{n}$ with $|S|\geq q^{(1-\delta_{r+1})n}$
contains $\Omega(q^{rn-\epsilon n})$ solutions to $Ax^{\mathsf{T}}=0$ of
affine rank at least $r$. We take $\delta_{r+1}$ such that moreover
$\delta_{r+1}\leq\epsilon$.

Now suppose, for the sake of contradiction, that for infinitely many $n$ there
is a subset $S\subseteq\mathbb{F}_{q}^{n}$ of size $|S|\geq
q^{(1-\delta_{r+1})n}$ such that $S$ contains no solution to
$Ax^{\mathsf{T}}=0$ of affine rank at least $r+1$. Consider such pairs
$(n,S)$.

Let $T=\\{x\in S^{2m+1}:Ax^{\mathsf{T}}=0\\}$ be the set of all solutions in
$S$. By assumption, every $x\in T$ has affine rank at most $r$. Let
$T_{1}:=\\{x\in T:\operatorname{arank}(x)=r\\}$. We have
$|T_{1}|=\Omega(q^{rn-\epsilon n})$ by our choice of $\epsilon$. For every
$x\in T_{1}$ there exist, by Proposition 16, disjoint sets
$I,J\subseteq[2m+1]$ of size $|I|=|J|=r$ such that
$\operatorname{arank}\\{x_{i}:i\in I\\}=\operatorname{arank}\\{x_{i}:i\in
J\\}=r$. Since there are no more than $\binom{2m+1}{r}\binom{2m+1-r}{r}$
possibilities for $(I,J)$, we may assume without loss of generality that

$T_{2}:=\\{x\in
T_{1}:\operatorname{arank}\\{x_{1},\ldots,x_{r}\\}=\operatorname{arank}\\{x_{r+1},\ldots,x_{2r}\\}=r\\}$

has size
$|T_{2}|\geq\binom{2m+1}{r}^{-1}\binom{2m+1-r}{r}^{-1}|T_{1}|=\Omega(q^{rn-\epsilon
n})$.

To emphasise the partition
$[2m+1]=\\{1,\ldots,r\\}\cup\\{r+1,\ldots,2r\\}\cup\\{2r+1,\ldots 2m+1\\}$ of
the variables and to simplify notation, we will define $t:=2m+1-2r$ and denote
elements from $S^{2m+1}$ by 3-tuples $(x,y,z)$, where $x,y\in S^{r}$ and $z\in
S^{t}$.

We will construct a random linear map from $\mathbb{F}_{q}^{S^{2m+1}}$ to
$\mathbb{F}_{q}^{S^{r}}\times\mathbb{F}_{q}^{S^{r}}$ and interpret the
elements of $\mathbb{F}_{q}^{S^{r}}\times\mathbb{F}_{q}^{S^{r}}$ as
$|S|^{r}\times|S|^{r}$ matrices. We will give an upper bound on the rank of
the resulting matrix that is lower than the expected rank for large $n$, thus
yielding a contradiction.

Recall that $d=n(q-1)\tfrac{m}{2m+1}$. Let

$V=\\{g:S\to\mathbb{F}_{q}:\sum_{z\in S}g(z)z^{\alpha}=0\quad\forall\alpha\in
M_{q,n,d}\\}.$

Since $|S|\geq q^{(1-\delta_{r+1})n}\geq q^{(1-\epsilon)n}$ and
$m_{q,n,d}=o(q^{(1-\epsilon)n})$, we have $\dim(V)\geq|S|-m_{q,n,d}>0$ (for
$n$ large enough). By Lemma 3, there is a subset $S^{\prime}\subseteq S$ of
size $|S^{\prime}|=\dim(V)$ such that every $h:S^{\prime}\to\mathbb{F}_{q}$
extends to a unique $g\in V$. Let $W=V^{\otimes
t}\subseteq\\{g:S^{t}\to\mathbb{F}_{q}\\}$ be the linear span of the functions
$z\mapsto g_{1}(z_{1})\cdots g_{t}(z_{t})$, where $g_{1},\ldots,g_{t}\in V$.
Then for every $g\in W$

$\sum_{z\in S^{t}}g(z)z_{1}^{\alpha_{1}}\cdots z_{t}^{\alpha_{t}}=0\text{ if
$|\alpha_{i}|\leq d$ for some $i\in[t]$}$ (1)

and every $h:(S^{\prime})^{t}\to\mathbb{F}_{q}$ extends to a unique $g\in W$.

We choose $h:(S^{\prime})^{t}\to\mathbb{F}_{q}$ uniformly at random and let
$g\in W$ be the extension of $h$. For any $f:S^{2m+1}\to\mathbb{F}_{q}$ we
define the random $S^{r}\times S^{r}$ matrix $M(f)$ as follows:

$M(f)_{x,y}:=\sum_{z\in S^{t}}f(x,y,z)g(z).$

For any subset $X\subseteq S^{2m+1}$ we denote by
$\mathbf{1}_{X}:S^{2m+1}\to\mathbb{F}_{q}$ the $0$–$1$ characteristic function
of $X$.

######  Claim.

The matrix $M(\mathbf{1}_{T})$ has rank at most $2m_{q,rn,rd}$.

Proof of claim. We can write

$\mathbf{1}_{T}(x,y,z)=\prod_{i=1}^{m}\prod_{\ell=1}^{n}\left[1-\left(\sum_{j=1}^{r}a_{i,j}x_{j,\ell}+\sum_{j=1}^{r}a_{i,j+r}y_{j,\ell}+\sum_{j=1}^{t}a_{i,j+2r}z_{j,\ell}\right)^{q-1}\right].$

So $\mathbf{1}_{T}$ is given by a polynomial of degree at most $mn(q-1)$.
Expanding the polynomial, we get

$\mathbf{1}_{T}(x,y,z)=\sum_{(\alpha,\beta,\gamma)\in
L}c_{\alpha\beta\gamma}x^{\alpha}y^{\beta}z^{\gamma}$

where $L:=\\{\ell\in\\{0,1,\ldots,q-1\\}^{[n]\times[2m+1]}:|\ell|\leq
mn(q-1)\\}$, and the $c_{\alpha\beta\gamma}\in\mathbb{F}_{q}$ are certain
coefficients. Thus, we have

$M(\mathbf{1}_{T})_{x,y}=\sum_{\alpha,\beta}c^{\prime}_{\alpha,\beta}x^{\alpha}y^{\beta},$

where

$c^{\prime}_{\alpha,\beta}=\sum_{\gamma:(\alpha,\beta,\gamma)\in
L}c_{\alpha,\beta,\gamma}\sum_{z\in S}g(z)z^{\gamma}.$

If $|\gamma|\leq td$, then $|\gamma_{i}|\leq d$ for some $i\in[t]$, and hence
$\sum_{z\in S}g(z)z^{\gamma}=0$ by definition of $g$. It follows that
$c^{\prime}_{\alpha,\beta}=0$ if $|\alpha|+|\beta|\geq mn(q-1)-td=2rd$. So
$M(\mathbf{1}_{T})$ is given by a polynomial of degree at most $2rd$ in the
$rn$ variables $x_{ji}$ and the $rn$ variables $y_{ji}$ (where
$(j,i)\in[r]\times[n]$). Hence, it follows from the CLP lemma that
$M(\mathbf{1}_{T})$ has rank at most $2m_{q,rn,rd}$. $\blacksquare$

We will now show the following claim.

######  Claim.

The matrix $M(\mathbf{1}_{T})$ has expected rank $\Omega(q^{rn-\epsilon n})$.

Proof of claim. Let $T_{3}=\\{(x,y,z)\in T_{2}:z\in(S^{\prime})^{t}\\}$. For
any fixed $b\in\mathbb{F}_{q}^{n}$ and any $i\in[t]\\}$ we have
$|\\{(x,y,z)\in T_{2}:z_{i}=b\\}|=O(q^{(r-1)n})$. Since $|S\setminus
S^{\prime}|\leq m_{q,n,d}=o(q^{(1-\epsilon)n})$, it follows that

$|T_{2}\setminus T_{3}|=o(q^{rn-\epsilon
n}),\qquad|T_{3}|=\Omega(q^{rn-\epsilon n}).$ (2)

Let $R=\\{(x,y)\in S^{r}\times S^{r}:\exists z\in S^{t},(x,y,z)\in T_{3}\\}$.
Since for each pair $(x,y)$ there are at most $q^{rt}$ possibilities for $z$
(as each $z_{i}$ is in the affine span of $\\{x_{i}:i\in[r]\\}$), it follows
that $|R|\geq\frac{|T_{3}|}{q^{rt}}=\Omega(q^{rn-\epsilon n})$. Let $(x,y)\in
R$. Then

$M(\mathbf{1}_{T_{3}})_{x,y}=\sum_{z\in
S^{t}}\mathbf{1}_{T_{3}}(x,y,z)g(z)=\sum_{z\in(S^{\prime})^{t}:(x,y,z)\in
T_{3}}h(z).$

Since $h$ was chosen uniformly at random and
$\\{z\in(S^{\prime})^{t}:(x,y,z)\in T_{3}\\}$ is nonempty, this sum is nonzero
with probability $\tfrac{q-1}{q}$. So the expected size of the support of
$M(\mathbf{1}_{T_{3}})$ is $\tfrac{q-1}{q}|R|$.

For every $x$, there are at most $q^{r(r-1)}$ values of $y$ for which
$(x,y)\in R$ since $y_{1},\ldots,y_{r}$ are in the affine hull of
$x_{1},\ldots,x_{r}$. Conversely, for every $y$ there are at most $q^{r(r-1)}$
values of $x$ for which $(x,y)\in R$. So by Lemma 25 we have

$\operatorname{rank}M(\mathbf{1}_{T_{3}})\geq\tfrac{q-1}{q}|R|/(q^{2r(r-1)})=\Omega(q^{rn-\epsilon
n}).$ (3)

Recall that for any $(x,y,z)\in T\setminus T_{2}$ we have
$\operatorname{arank}(x)\leq r-1$ or $\operatorname{arank}(y)\leq r-1$. Hence,
the number of possibilities for $x$ (resp. $y$) is $O(q^{(r-1)n})$ and
therefore

$\operatorname{rank}M(\mathbf{1}_{T\setminus T_{2}})=O(q^{(r-1)n}).$ (4)

Using the fact that $\operatorname{rank}M(\mathbf{1}_{T_{2}\setminus
T_{3}})\leq|T_{2}\setminus T_{3}|=o(q^{rn-\epsilon n})$, we conclude that

$\operatorname{rank}M(\mathbf{1}_{T})\geq\operatorname{rank}M(\mathbf{1}_{T_{3}})-\operatorname{rank}M(\mathbf{1}_{T_{2}\setminus
T_{3}})-\operatorname{rank}M(\mathbf{1}_{T\setminus
T_{2}})=\Omega(q^{rn-\epsilon n}).$

$\blacksquare$

Since $m_{q,rn,rd}=o(q^{rn-\epsilon n})$, the two claims yield a contradiction
for large enough $n$. This concludes the proof of Theorem 24.

######  Remark 26.

In the proof, we took $r=1$ as the base case. However the case $r=2$ also
follows directly from Theorem 2, so we could have taken $r=2$ as a base case
as well.

##  6 Proof of Theorem B

In this section we consider the special case that the finite field is
$\mathbb{F}_{q}$, where $q\in\\{2,3\\}$. It turns out that in this case, every
balanced system is temperate, by a much simpler argument. The case $q=2$ is
implicit in [BQ00, Lemma 21] in the context of extremal matroid theory.

If $b_{0},b_{1},\ldots,b_{d}\in\mathbb{F}_{q}^{n}$ and $b_{1},\ldots,b_{d}$
are linearly independent, then
$V=\\{b_{0}+\alpha_{1}b_{1}+\cdots+\alpha_{d}b_{d}:\alpha_{1},\ldots,\alpha_{d}\in\mathbb{F}_{q}\\}$
is a _$d$ -dimensional affine subspace_ of $\mathbb{F}_{q}^{n}$. A
$1$-dimensional subspace is also called a _line_.

The main ingredient of the proof of Theorem B is the following lemma.

######  Lemma 27.

Fix $q\in\\{2,3\\}$. Let $d\in\mathbb{Z}_{\geq 1}$. Then there exist
$n_{d}\in\mathbb{Z}_{\geq 1}$, $C_{d}>0$ and $\delta_{d}\in(0,1]$ such that
for all $n\geq n_{d}$, every $S\subseteq\mathbb{F}_{q}^{n}$ of size $|S|\geq
C_{d}q^{(1-\delta_{d})n}$ contains an affine $d$-dimensional subspace.

The case $q=3$, the _multidimensional cap set problem_ , was proved in [FP19]
by using the arithmetic triangle removal lemma from [FL17]. A more direct
proof (but with slightly worse bounds) due to Jop Briët [Bri] (personal
communication) is given below.

###### Proof.

If $q=3$, we can take $n_{1}=1$, $C_{1}=3$, and $\delta_{1}=1-\log_{3}(2.756)$
by the cap set theorem. If $q=2$, we can take $n_{1}=1$, $C_{1}=2$, and
$\delta_{1}=1$.

Now let $t\geq 2$ and suppose that the statement is true for $d=1,\ldots,t-1$.
We define

$C_{t}:=q(C_{1}+C_{t-1}),\quad\delta_{t}:=\frac{\delta_{1}\delta_{t-1}}{2+\delta_{1}+\delta_{t-1}},\quad
n_{t}:=\left\lceil\max\left(\frac{2+\delta_{1}+\delta_{t-1}}{\delta_{t-1}}n_{1},\frac{2+\delta_{1}+\delta_{t-1}}{2+\delta_{1}}n_{t-1}\right)\right\rceil.$

Note that $0<\delta_{t}\leq 1$. Let $n\geq n_{t}$ and let
$S\subseteq\mathbb{F}_{q}^{n}$ have size $|S|\geq C_{t}q^{(1-\delta_{t})n}$.
We define

$m=\left\lfloor\frac{\delta_{t-1}}{2+\delta_{1}+\delta_{t-1}}n\right\rfloor,\qquad
k=\left\lceil\frac{2+\delta_{1}}{2+\delta_{1}+\delta_{t-1}}n\right\rceil=n-m.$

By the choice of $n_{t}$ we have $m\geq n_{1}$ and $k\geq n_{t-1}$. For any
$x\in\mathbb{F}_{q}^{k}$ we denote $S_{x}:=\\{y\in\mathbb{F}_{q}^{m}:(x,y)\in
S\\}$. Let $T=\\{x\in\mathbb{F}_{q}^{k}:|S_{x}|\geq
C_{1}q^{(1-\delta_{1})m}\\}$. We have

$|S|=\sum_{x\in T}|S_{x}|+\sum_{x\not\in
T}|S_{x}|\leq|T|q^{m}+C_{1}q^{k+(1-\delta_{1})m}.$

Since $\delta_{1}m+1\geq\delta_{t}n$, we have $(1-\delta_{t})n+1\geq
k+(1-\delta_{1})m$. Similarly, we have $(1-\delta_{t})n+1\geq
3m+(1-\delta_{t-1})k$. It follows that

$|S|\geq C_{t}q^{(1-\delta_{t})n}\geq
C_{1}q^{k+(1-\delta_{1})m}+C_{t-1}q^{3m+(1-\delta_{t-1})k}.$

Hence, it follows that

$|T|\geq\frac{|S|-C_{1}q^{k+(1-\delta_{1})m}}{q^{m}}\geq
q^{2m}C_{t-1}q^{(1-\delta_{t-1})k}.$

For every $x\in T$, there is a line $\ell$ contained in $S_{x}$. Since the
number of lines in $\mathbb{F}_{q}^{m}$ is less than $q^{2m}$, there is a
subset $T^{\prime}\subseteq T$ of size $|T^{\prime}|\geq|T|q^{-2m}$ and a line
$\ell\subseteq\mathbb{F}_{q}^{m}$ such that $\ell\subseteq S_{x}$ for all
$x\in T^{\prime}$. Since $|T^{\prime}|\geq C_{t-1}q^{(1-\delta_{t-1})k}$ there
is a $t-1$-dimensional subspace $V\subseteq T^{\prime}$. Hence $\\{(x,y):x\in
V,y\in\ell\\}$ is a $t$-dimensional subspace contained in $S$. ∎

We restate Theorem B.

######  Theorem 28.

Let $q\in\\{2,3\\}$ and let $A\in\mathbb{F}_{q}^{m\times k}$ be a row-balanced
matrix of rank $m$. Then $Ax^{\mathsf{T}}=0$ is temperate.

###### Proof.

Let $d=k-m-1$. Then $\mathbb{F}_{q}^{d}$ contains a generic solution $y$ to
$Ax^{\mathsf{T}}=0$ by Lemma 10. So $y$ has affine rank $m-k$.

Now let $n\geq n_{d}$ and let $S\subseteq\mathbb{F}_{q}^{n}$ have size
$|S|\geq C_{d}q^{(1-\delta_{d})n}$. Then $S$ contains a $d$-dimensional affine
subspace
$V=\\{b_{0}+\alpha_{1}b_{1}+\cdots+\alpha_{d}b_{d}:\alpha_{1},\ldots,\alpha_{d}\in\mathbb{F}_{q}\\}$.
Setting $x_{i}=b_{0}+y_{i1}b_{1}+\cdots+y_{id}b_{d}$, we obtain a solution to
$Ax^{\mathsf{T}}=0$ where $x$ has affine rank $k-m$ and $x_{1},\ldots,x_{k}\in
S$. ∎

##  7 Affine copies

Given a balanced matrix $A\in\mathbb{F}_{q}^{m\times k}$ of rank $m$, there is
a generic solution $z=(z_{1},\ldots,z_{k})$ to $Ax^{\mathsf{T}}=0$ in
$\mathbb{F}_{q}^{k-m-1}$ by Lemma 10. Conversely, if
$z=(z_{1},\ldots,z_{k})\in(\mathbb{F}_{q}^{r})^{k}$, then $z$ is a generic
solution to $Ax^{\mathsf{T}}=0$, where $A\in\mathbb{F}_{q}^{m\times k}$ has
rows that are a basis of $\operatorname{Ann}_{\operatorname{bal}}(z)$. Instead
of saying that $S\subseteq\mathbb{F}_{q}^{n}$ has a generic solution to
$Ax^{\mathsf{T}}=0$, we can equivalently say that $S$ contains an affine copy
of $z$. Thus, we can reformulate Theorem A and Theorem B and obtain Corollary
C.

######  Definition 29.

Let $z_{1},\ldots,z_{k}\in\mathbb{F}_{q}^{r}$ and
$x_{1},\ldots,x_{k}\in\mathbb{F}_{q}^{n}$. We say that
$x=(x_{1},\ldots,x_{k})$ is an _affine copy_ of $z=(z_{1},\ldots,z_{k})$ if
there is an injective linear map $L:\mathbb{F}_{q}^{r}\to\mathbb{F}_{q}^{n}$
and a vector $a\in\mathbb{F}_{q}^{n}$ such that $x_{i}=L(z_{i})+a$ for all
$i\in[k]$.

Note that if $x$ is an affine copy of $z$, then any translate of $x$ is an
affine copy of any translate of $z$.

######  Lemma 30.

Let $z=(z_{1},\ldots,z_{k})\in(\mathbb{F}_{q}^{r})^{k}$. Let
$A\in\mathbb{F}_{q}^{m\times k}$ be such that the rows form a basis of
$\operatorname{Ann}_{\operatorname{bal}}(z)$. Let $n\geq r$ and let
$x=(x_{1},\ldots,x_{k})\in(\mathbb{F}_{q}^{n})^{k}$. Then $x$ is an affine
copy of $z$ if and only if $x$ is a generic solution to $Ax^{\mathsf{T}}=0$.

###### Proof.

By translating, we may assume without loss of generality that $z_{k}=0$ and
$x_{k}=0$. Note that $z=(z_{1},\ldots,z_{k})$ is a generic solution to
$Ax^{\mathsf{T}}=0$.

Suppose that $x$ is an affine copy of $z$. Then $x_{i}=L(z_{i})$ for all
$i\in[k]$, where $L:\mathbb{F}_{q}^{r}\to\mathbb{F}_{q}^{n}$ is an injective
linear map. It is easy to verify that
$\operatorname{Ann}_{\operatorname{bal}}(x)=\operatorname{Ann}_{\operatorname{bal}}(z)$.
So $x$ is a generic solution to $Ax^{\mathsf{T}}=0$.

Conversely, suppose that $x$ is a generic solution to $Ax^{\mathsf{T}}=0$.
Define
$L:\operatorname{span}\\{z_{1},\ldots,z_{k-1}\\}\to\operatorname{span}\\{x_{1},\ldots,x_{k-1}\\}$
by

$L(\sum_{i\in[k-1]}\lambda_{i}z_{i}):=\sum_{i\in[k-1]}\lambda_{i}x_{i}.$

This is a well-defined injective linear map, since

$\displaystyle\sum_{i\in[k-1]}\lambda_{i}z_{i}=0$
$\displaystyle\iff(\lambda_{1},\ldots,\lambda_{k-1},-\sum_{i\in[k-1]}\lambda_{i})\in\operatorname{Ann}_{\operatorname{bal}}(z)$
$\displaystyle\iff(\lambda_{1},\ldots,\lambda_{k-1},-\sum_{i\in[k-1]}\lambda_{i})\in\operatorname{Ann}_{\operatorname{bal}}(x)$
$\displaystyle\iff\sum_{i\in[k-1]}\lambda_{i}x_{i}=0.$

Since $n\geq r$, we can extend $L$ to an injective linear map
$\mathbb{F}_{q}^{r}\to\mathbb{F}_{q}^{n}$. So $x$ is an affine copy of $z$. ∎

We can now prove Corollary D as a direct consequence of Theorem A and Theorem
B.

###### Proof of Corollary D.

Let $A\in\mathbb{F}_{q}^{m\times k}$ be a matrix such that the rows form a
basis of $\operatorname{Ann}_{\operatorname{bal}}(z_{1},\ldots,z_{k})$. So
$z=(z_{1},\ldots,z_{k})$ is a generic solution to $Ax^{\mathsf{T}}=0$. If
$q\not\in\\{2,3\\}$, then the premise of Corollary D implies by Lemma 11 that
for every $i\in[k]$ the matrix $A$ has two disjoint bases in
$[k]\setminus\\{i\\}$. Hence, by Lemma 13, the matrix $A$ is tame.

By Lemma 30, it follows directly from Theorem A and Theorem B that there is a
$\delta>0$ such that any subset $S\subseteq\mathbb{F}_{q}^{n}$ without affine
copy of $z$ has size $|S|=O(q^{(1-\delta)n})$. ∎

##  8 Concluding remarks

An advantage of considering generic solutions over $(\star)$-shapes, is that
they can be used to obtain not just one, but many solutions given a
sufficiently large set $S\subseteq\mathbb{F}_{q}^{n}$. In particular, we
obtain Corollary C which we restate here.

######  Corollary 31.

Suppose that the coefficient matrix $A$ of $(\star)$ is tame. Then there exist
$\delta>0$ and $C>0$ such that for all positive $\delta^{\prime}<\delta$ the
following holds: if $S\subseteq\mathbb{F}_{q}^{n}$ has size $|S|\geq
q^{(1-\delta^{\prime})n}$, then $S$ has $\Omega(q^{(k-m)n-C\delta^{\prime}n})$
solutions to $(\star)$.

###### Proof.

This follows directly from Theorem 5 and Proposition 22. ∎

We conclude with an open problem for which we think both a positive and a
negative answer would be very interesting.

######  Open problem 32.

Is it true that $(\star)$ is temperate for all balanced matrices $A$?

A positive answer would be a very strong result, since we do not even know if
the system corresponding to $4$-term progressions is temperate. As a final
note, we remark that the situation where $A$ is tame, corresponds to a strict
subset of systems of linear forms of Cauchy-Schwarz complexity $1$ (see:
[GW10]). Perhaps this class would be a good candidate for proving a
generalisation.

## References

  * [BCC+17] Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans.  On cap sets and the group-theoretic approach to matrix multiplication.  Discrete Analysis, 2017(3):1–27, 2017.
  * [BQ00] Joseph E. Bonin and Hongxun Qin.  Size functions of subgeometry-closed classes of representable combinatorial geometries.  Discrete Mathematics, 224(1-3):37–60, 2000.
  * [Bri] Jop Briët.  personal communication.
  * [CLP17] Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach.  Progression-free sets in $\mathbb{Z}_{4}^{n}$ are exponentially small.  Annals of Mathematics, 185(1):331–337, 2017.  doi:10.4007/annals.2017.185.1.7.
  * [DdBG21] Josse van Dobben de Bruyn and Dion Gijswijt.  On the size of subsets of $\mathbb{F}_{q}^{n}$ avoiding solutions to linear systems with repeated columns, 2021.  Preprint.  URL: https://arxiv.org/abs/2111.09879.
  * [EG17] Jordan S. Ellenberg and Dion Gijswijt.  On large subsets of $\mathbb{F}_{q}^{n}$ with no three-term arithmetic progression.  Annals of Mathematics, 185(1):339–343, 2017.  doi:10.4007/annals.2017.185.1.8.
  * [FK91] Hillel Furstenberg and Yitzhak Katznelson.  A density version of the Hales-Jewett theorem.  Journal d’Analyse Mathématique, 57(1):64–119, 1991.
  * [FL17] Jacob Fox and LászlóMiklós Lovász.  A tight bound for green’s arithmetic triangle removal lemma in vector spaces.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1612–1617. SIAM, 2017.
  * [FP19] Jacob Fox and Huy Tuan Pham.  Popular progression differences in vector spaces ii.  Discrete analysis, 2019.
  * [Fra21] Robert Fraser.  Three-term arithmetic progressions in subsets of $f_{q}^{\infty}$ of large fourier dimension.  Annales Fennici Mathematici, 46(2):1007–1030, 2021.
  * [FS18] Jacob Fox and Lisa Sauermann.  Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions.  The Electronic Journal of Combinatorics, pages P2–14, 2018.
  * [GN15] Jim Geelen and Peter Nelson.  An analogue of the Erdős-Stone theorem for finite geometries.  Combinatorica, 35(2):209–214, 2015.
  * [GW10] William T Gowers and Julia Wolf.  The true complexity of a system of linear equations.  Proceedings of the London Mathematical Society, 100(1):155–176, 2010.
  * [Kov21] Vjekoslav Kovač.  Popular differences for right isosceles triangles.  The Electronic Journal of Combinatorics, 28(4), 2021.
  * [MT19a] Masato Mimura and Norihide Tokushige.  Avoiding a star of three-term arithmetic progressions, 2019\.  Preprint.  URL: https://arxiv.org/abs/1909.10507.
  * [MT19b] Masato Mimura and Norihide Tokushige.  Avoiding a shape, and the slice rank method for a system of equations, 2019.  Preprint.  URL: https://arxiv.org/abs/1909.10509.
  * [MT20] Masato Mimura and Norihide Tokushige.  Solving linear equations in a vector space over a finite field II, 2020\.  Preprint.  URL: http://www.cc.u-ryukyu.ac.jp/~hide/sol2.pdf.
  * [Nas20] Eric Naslund.  Exponential bounds for the Erdős-Ginzburg-Ziv constant.  Journal of Combinatorial Theory, Series A, 174:105185, 2020.
  * [PRN05] Cosmin Pohoata and Oliver Roche-Newton.  Four-term progression free sets with three-term progressions in all large subsets.  Random Structures & Algorithms, 1905.
  * [Ruz93] Imre Z. Ruzsa.  Solving a linear equation in a set of integers I.  Acta arithmetica, 65(3):259–282, 1993.
  * [Sau21a] Lisa Sauermann.  Finding solutions with distinct variables to systems of linear equations over $\mathbb{F}_{p}^{n}$, 2021.  Preprint.  URL: https://arxiv.org/abs/2105.06863.
  * [Sau21b] Lisa Sauermann.  On the size of subsets of $\mathbb{F}_{p}^{n}$ without $p$ distinct elements summing to zero.  Israel Journal of Mathematics, 243(1):63–79, 2021.
  * [Sch03] Alexander Schrijver.  Combinatorial optimization: polyhedra and efficiency, volume 24.  Springer Science & Business Media, 2003.
  * [Sze75] Endre Szemerédi.  On sets of integers containing no $k$ elements in arithmetic progression.  Acta Arith, 27(299-345):5, 1975.
  * [Tao16a] Terence Tao.  Notes on the “slice rank” of tensors, 2016.  Blog post.  URL: https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/.
  * [Tao16b] Terence Tao.  A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, 2016.  Blog post.  URL: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/.
  * [TV06] Terence Tao and Van H Vu.  Additive combinatorics, volume 105.  Cambridge University Press, 2006.


#  Extension of Irreducibility results on Generalised Laguerre Polynomials
$L_{n}^{(-1-n-s)}(x)$

Saranya G. Nair  Department of Mathematics
BITS Pilani, K K Birla Goa Campus, Goa- 403726<EMAIL_ADDRESS>and  T. N. Shorey  National Institute of Advanced Studies, IISc Campus
Bangalore, 560012<EMAIL_ADDRESS>
###### Abstract.

We consider the irreducibility of Generalised Laguerre Polynomials for
negative integral values given by
$L_{n}^{(-1-n-s)}(x)=\displaystyle\sum_{j=0}^{n}\binom{n-j+s}{n-j}\frac{x^{j}}{j!}.$
For different values of $s,$ this family gives polynomials which are of great
interest. It was proved earlier that for $0\leq s\leq 60,$ these polynomials
are irreducible over $\mathbb{Q}.$ In this paper we improve this result upto
$s\leq 88.$

2010 Mathematics Subject Classification: Primary 11A41, 11B25, 11N05, 11N13,
11C08, 11Z05.
Keywords: Irreducibility, Laguerre Polynomials, Primes, Newton Polygons.

Nair and Shorey

##  1\. Introduction

For a positive integer $n$ and real number $\alpha,$ the Generalised Laguerre
Polynomial (GLP) is defined as

(1) $\displaystyle
L_{n}^{(\alpha)}(x)=\displaystyle\sum_{j=0}^{n}\frac{(n+\alpha)(n-1+\alpha)\cdots(j+1+\alpha)}{j!(n-j)!}(-x)^{j}.$

These polynomials were discovered around 1880 and they have been extensively
studied in various branches of mathematics and mathematical physics. The
algebraic properties of GLP were first studied by Schur [8],[9] where he
established the irreducibility of $L_{n}^{(\alpha)}(x)$ for
$\alpha\in\\{0,1,-n-1\\},$ gave a formula for the discriminant
$\Delta_{n}^{(\alpha)}$ of
$\mathcal{L}_{n}^{(\alpha)}(x)=n!L_{n}^{(\alpha)}(x)$ by

$\displaystyle\Delta_{n}^{(\alpha)}=\displaystyle\prod_{j=1}^{n}j^{j}(\alpha+j)^{j-1}$

and calculated their assosciated Galois groups. For an account of results
obtained on GLP, we refer to [3],[7].

Let $f(x)\in\mathbb{Q}[x]$ with deg $f=n$. By irreducibility of a polynomial,
we shall always mean its irreducibility over $\mathbb{Q}.$ We observe that if
a polynomial of degree $n$ has a factor of degree $k<n,$ then it has a factor
of degree $n-k.$ Therefore given a polynomial of degree $n$, we always
consider factors of degree $k$ where $1\leq k\leq\frac{n}{2}$. If the argument
$\alpha$ of (1) is a negative integer, we see that the constant term of
$L_{n}^{(\alpha)}(x)$ vanishes if and only if $n\geq|\alpha|=-\alpha$ and then
$L_{n}^{(\alpha)}(x)$ is reducible. Therefore we assume that $\alpha\leq-n-1.$
We write $\alpha=-n-s-1$ where $s$ is a non-negative integer. We have

(2) $\displaystyle
L_{n}^{(-n-s-1)}(x)=\displaystyle\sum_{j=0}^{n}(-1)^{n}\frac{(n+s-j)!}{(n-j)!s!}\frac{x^{j}}{j!}.$

Borrowing the notation from [11], we consider the following polynomial

$\displaystyle
g(x):=g(x,n,s)=(-1)^{n}L_{n}^{(-n-s-1)}=\displaystyle\sum_{j=0}^{n}\binom{n+s-j}{n-j}\frac{x^{j}}{j!}=\displaystyle\sum_{j=0}^{n}b_{j}\frac{x^{j}}{j!}$

where $b_{j}=\binom{n+s-j}{n-j}$ for $0\leq j\leq n.$ Thus
$b_{n}=1,b_{0}=\binom{n+s}{s}=\frac{(n+1)\cdots(n+s)}{s!}$. We observe that
$g(x)$ is irreducible if and only if $L_{n}^{(-n-s-1)}(x)$ is irreducible. The
aim of this paper is to discuss the irreducibility of $g(x)$. We consider more
general polynomial

$\displaystyle
G(x):=G(x,n,s)=\displaystyle\sum_{j=0}^{n}a_{j}b_{j}\frac{x^{j}}{j!}$

such that $a_{j}\in\mathbb{Z}$ for $0\leq j\leq n$ with $|a_{0}|=|a_{n}|=1.$
If $a_{j}=1$ for $0\leq j\leq n,$ we have $G(x)=g(x).$ We write

$\displaystyle
g_{1}(x):=n!g(x)=n!\displaystyle\sum_{j=0}^{n}\binom{n+s-j}{n-j}\frac{x^{j}}{j!}$

and

$\displaystyle G_{1}(x)=n!G(x)$

so that $g_{1}$ and $G_{1}$ are monic polynomials with integer coefficients of
degree $n.$ The irreducibility of $g_{1}(x)$ and $G_{1}(x)$ implies the
irreducibility of $g(x)$ and $G(x)$ respectively. We begin with the following
result by Sinha and Shorey [11] on $G(x)$.

######  Lemma 1.1.

Let $s\leq 92.$ Then $G(x)=G(x,n,s)$ has no factor of degree $k\geq 2$ except
when
$(n,k,s)\in\\{(4,2,7),(4,2,23),(9,2,19),(9,2,47),(16,2,14),(16,2,34),(16,2,89),\\\
(9,3,47),(16,3,19),(10,5,4)\\}.$

We re-state Lemma 1.1 as follows:
Let $s\leq 92.$ Assume that $G(x)$ has a factor of degree greater than or
equal to $2$. Then
$(n,k,s)\in\\{(4,2,7),(4,2,23),(9,2,19),(9,2,47),(16,2,14),(16,2,34),(16,2,89),(9,3,47),\\\
(16,3,19),(10,5,4)\\}.$ We check that $g(x)$ is irreducible when
$n\in\\{4,9,10,16\\}.$ Therefore by Lemma 1.1 with $G(x)=g(x)$ we have

######  Lemma 1.2.

Let $n\geq 3$ and $s\leq 92$. Then $g_{1}(x)$ is either irreducible or linear
factor times an irreducible polynomial.

The irreducibility of $g_{1}(x)$ was proved by Schur [8] for $s=0,$ by Hajir
[2] for $s=1$, by Sell [10] for $s=2$ and by Hajir [3] for $3\leq s\leq 8.$ We
shall prove

######  Theorem 1.

$g_{1}(x)$ is irreducible for $9\leq s\leq 88.$

Nair and Shorey [6] and Jindal, Laishram and Sarma [5] already proved the
irreducibility of $g_{1}(x)$ in the range of $9\leq s\leq 22$ and $23\leq
s\leq 60$ respectively. But our proof of Theorem 1 is new. The proofs of [6]
and [5] depend on the method of Hajir in [3] whereas our proof depends on
Lemma 1.2 which is a direct consequence of Lemma 1.1. We could not cover the
cases of $88\leq s\leq 92$ due to computational limitations.

At this point, we pause with a digression concerning notation. In order to
dispell possible confusion in the reader concerning notation, it is worth
pointing out that the notation $L_{n}^{<s>}(x)$ (resp.,
$\mathcal{L}_{n}^{<s>}(x)$) was used by the authors in [3], [5] and [7] to
denote the polynomial $g(x,n,s)$ (resp, $g_{1}(x,n,s)$).

##  2\. Preliminaries

From now onwards we shall assume that $s\geq 9.$ For a real number $\alpha,$
we write $\left[\alpha\right]$ to be the largest integer not exceeding
$\alpha.$

Let $f(x)=\displaystyle\sum_{j=0}^{m}d_{j}x^{j}\in\mbox{$\mathbb{Z}$}[x]$ with
$d_{0}d_{m}\neq 0$ and let $p$ be a prime. For an integer $x,$ let
$\nu(x)=\nu_{p}(x)$ be the highest power of $p$ dividing $x$ and we write
$\nu(0)=\infty.$ Let S be the following set of points in the extended plane

$S=\\{(0,\nu(d_{m})),(1,\nu(d_{m-1})),(2,\nu(d_{m-2})),\ldots,(m,\nu(d_{0}))\\}.$

Consider the lower edges along the convex hull of these points. The left most
endpoint is $(0,\nu(d_{m}))$ and the right most endpoint is $(m,\nu(d_{0}))$.
The endpoints of each edge belong to S and the slopes of the edges increase
strictly from left to right. The polygonal path formed by these edges is
called the Newton polygon of $f(x)$ with respect to the prime $p$ and we
denote it by $NP_{p}(f)$. The endpoints of the edges of $NP_{p}(f)$ are called
the vertices of $NP_{p}(f)$. We begin with a very useful result, due to
Filaseta [1], giving a criterion on the factorisation of a polynomial in terms
of the maximum slope of the edges of its Newton polygon.

######  Lemma 2.1.

Let $l,k,m$ be integers with $m\geq 2k>2l\geq 0$. Suppose
$h(x)=\displaystyle\sum_{j=0}^{m}b_{j}x^{j}\in\mbox{$\mathbb{Z}$}[x]$ and $p$
be a prime such that $p\nmid b_{m}$ and $p\mid b_{j}$ for $0\leq j\leq m-l-1$
and the right most edge of $NP_{p}(h)$ has slope $<\frac{1}{k}$. Then for any
integers $a_{0},a_{1},\ldots,a_{m}$ with $p\nmid a_{0}a_{m}$, the polynomial
$f(x)=\displaystyle\sum_{j=0}^{m}a_{j}b_{j}x^{j}$ cannot have a factor with
degree in $[l+1,k]$.

The next result is Lemma 4.2 of [12] with $a=0.$

######  Lemma 2.2.

Let $a_{0},a_{1},\cdots,a_{n}$ denote arbitrary integers and

$h(x)=\displaystyle\sum_{j=0}^{n}a_{j}\frac{x^{j}}{j!}.$

Assume that $h(x)$ has a factor of degree $k\geq 1.$ Suppose that there exists
a prime $p>k$ such that $p$ divides $n(n-1)\cdots(n-k+1).$ Then $p$ divides
$a_{0}a_{n}.$

For a positive integer $l$ and a prime $p,$ let $\nu_{p}(l)$ be the maximal
power of $p$ dividing $l.$

######  Lemma 2.3.

Let $p$ be a prime. For any integer $l\geq 1$, write $l$ in base $p$ as
$l=l_{t}p^{t}+l_{t-1}p^{t-1}+\dots+l_{1}p+l_{0}$ where $0\leq l_{i}\leq p-1$
for $0\leq i\leq t$ and $l_{t}>0$. Then

$\displaystyle\nu_{p}(l!)=\frac{l-\sigma_{p}(l)}{p-1}$

where $\sigma_{p}(l)=l_{t}+l_{t-1}+\dots+l_{1}+l_{0}$.

This is due to Legendre. For a proof, see [4, Ch.17, p 263]. As a consequence
we have

(3)
$\displaystyle\nu_{p}\left(\binom{m}{t}\right)=\frac{\sigma_{p}(t)+\sigma_{p}(m-t)-\sigma_{p}(m)}{p-1}.$

######  Lemma 2.4.

Assume that $g_{1}(x)$ is a linear factor times an irreducible polynomial. Let
$p$ be a prime dividing $n$ and $s<p^{2}.$ Then

$\displaystyle d+\left[\frac{s}{p}\right]\geq p$

where $d\equiv\frac{n}{p}(\mod p)$ for $1\leq d<p.$

The assertion of Lemma 2.4 was proved in [5, Corollary 3.2] under the
assumption of $p$ dividing $n_{1}$ where

(4) $\displaystyle n=n_{0}\cdot n_{1}\ {\rm with}\ \gcd(n_{0},n_{1})=1$

and

(5) $\displaystyle
n_{1}=\displaystyle\prod_{p|\gcd(n,\binom{n+s}{s})}p^{\text{ord}_{p}(n)}.$

Therefore $n_{0}$ is the largest divisor of $n$ which is coprime to
$\binom{n+s}{s}.$ Thus the assumption $p$ dividing $n_{1}$ in [5, Corollary
3.2] is replaced by $p$ dividing $n$ in Lemma 2.4 when $g_{1}(x)$ is linear
factor times an irreducible polynomial.

###### Proof.

We apply Lemma 2.2 with $h(x)=g_{1}(x)$ and $k=1$ to conclude that

(6) $\displaystyle p|\frac{(n+1)\cdots(n+s)}{s!}.$

If $\nu_{p}(n)>s,$ then
$\nu_{p}\left(\frac{(n+1)\cdots(n+s)}{s!}\right)\leq\nu_{p}(\frac{s!}{s!})\leq
0$ contradicting (6). Therefore $\nu_{p}(n)\leq s<p^{2}$ and hence
$1\leq\nu_{p}(n)<2.$ We write,

$\displaystyle n=pD\ \text{where}\ \gcd(D,p)=1$

and $s=ps_{1}+s_{0}$ where $1\leq s_{1}<p,0\leq s_{0}<p$. Then
$n+s=p(D+s_{1})+s_{0}$ which implies that
$\sigma_{p}(n+s)=\sigma_{p}(D+s_{1})+s_{0}$. Now we argue as in [5, Lemma 3.1]
for deriving from (3) and (6) that

$\displaystyle 1\leq\nu_{p}\left(\binom{n+s}{s}\right)=$
$\displaystyle\frac{\sigma_{p}(n)+\sigma_{p}(s)-\sigma_{p}(n+s)}{p-1}$
$\displaystyle=$
$\displaystyle\frac{\sigma_{p}(D)+s_{1}+s_{0}+-\sigma_{p}(D+s_{1})-s_{0}}{p-1}$
$\displaystyle=$
$\displaystyle\frac{\sigma_{p}(D)+s_{1}-\sigma_{p}(D+s_{1})}{p-1}$
$\displaystyle=$ $\displaystyle\nu_{p}\left(\binom{D+s_{1}}{s_{1}}\right)$
$\displaystyle=$
$\displaystyle\nu_{p}\left(\frac{(D+1)\cdots(D+s_{1})}{s_{1}!}\right)$
$\displaystyle=$ $\displaystyle\nu_{p}((D+1)\cdots(D+s_{1}))$ $\displaystyle=$
$\displaystyle\nu_{p}(D+j)\ \text{for \ exactly one}\ j\ \text{with}\ 1\leq
j\leq s_{1}$

since $s_{1}<p.$ Hence $D+\left[\frac{s}{p}\right]=D+s_{1}\geq D+j\equiv 0$
(mod $p$). Since $\gcd(D,p)=1$, we observe from (3) that $D=\frac{n}{p}\equiv
d$ (mod $p$) where $1\leq d<p$ by looking at $p-$ adic representation of $n.$
Hence $d+\left[\frac{s}{p}\right]\geq p$ where $d\equiv\frac{n}{p}$ (mod $p$)
for $1\leq d<p.$ ∎

Next, we prove

######  Lemma 2.5.

Assume that $g_{1}(x)$ is linear factor times an irreducible polynomial. Then
for $n\leq 127$ and $s\leq 103,$ $g_{1}(x)$ is irreducible.

This result is proved in [6, Lemma 2.10] without the assumption that
$g_{1}(x)$ is linear factor times an irreducible polynomial. But Lemma 2.5
suffices for our purpose. We give here a proof of this particular case, as it
involves considerably less computations.

###### Proof.

Let $n\leq 127$ and $s\leq 103.$ Since $g_{1}(x)$ is linear factor times an
irreducible polynomial, we see that $n_{0}=1.$ Assume that $n\geq s+2.$ Then
$\max(\frac{n+s}{2},n-1)=n-1$ and we derive from [3, Lemma 4.1] that
$g_{1}(x)$ is irreducible if $n$ is prime. Now we check that $g_{1}(x)$ is
irreducible for all pairs $(n,s)$ with $n$ composite and $n\geq s+2.$ Next we
assume that $n<s+2.$ Then $\max(\frac{n+s}{2},n-1)=\frac{n+s}{2}$. We
determine all pairs $(n,s)$ such that $n<s+2$ and there exists a prime $p$
satisfying $\frac{n+s}{2}<p\leq n$. Then $g_{1}(x)$ is irreducible for all
these pairs $(n,s)$ by [3, Lemma 4.1]. For the remaining pairs $(n,s)$ with
$n<s+2,$ we check that $g_{1}(x)$ is irreducible. ∎

We close this section by stating the following result which is Lemma 3.6 from
[5] with $i=1$.

######  Lemma 2.6.

Let $p|n(s+1)$ and $\nu_{p}\left(\binom{n+s}{s}\right)=u.$ Then $g_{1}(x)$
cannot have a factor of degree $1$ if any of the following condition holds:

  * (i)

$u=0$

  * (ii)

$u>0$, $p>2$ and
$\max\left\\{\frac{u+1}{p},\frac{\nu_{p}(n+s-z_{0})-\nu_{p}(n)}{z_{0}+1}\right\\}<1$,
where $z_{0}\equiv n+s$ (mod $p$) with $1\leq z_{0}<p.$

##  3\. Proof of Theorem 1

For $c>1$ and $s\geq c^{2}$, we consider the following set given by

$\displaystyle H_{s,c}=\\{n\in\mathbb{N},n>127\ \text{and for
}p|n,p^{\nu_{p}(n)}\leq s\ \text{and if}\ p>sc^{-1}\ \text{then}\
d+\left[\frac{s}{p}\right]\geq p\\}$

where $1\leq d<p$ and $d\equiv\frac{n}{p}$ (mod $p$). Since $p\geq
sc^{-1}\geq\sqrt{s},$ we derive from Lemmas 2.4 and 2.5 that it suffices to
prove the irreducibility of $g_{1}(x)=g_{1}(x,n,s)$ with $n\in H_{s,c}.$ We
partition $H_{s,c}$ as $H_{s,c,1}$ and $H_{s,c,2}$ given by

$\displaystyle H_{s,c,1}=\\{n\in H_{s,c}\ \text{such that}\
P(n)\leq[sc^{-1}]\\}$

and

$\displaystyle H_{s,c,2}=\\{n\in H_{s,c}\ \text{such that}\
P(n)>[sc^{-1}]\\}.$

Let $9\leq s\leq 88$. By taking $c\in\\{3,3.42,5.5,7.7\\}$ we compute
$H_{s,c,1}$ and $H_{s,c,2}$ and hence $H_{s,c}$ for $9\leq s\leq 88.$ We give
some details regarding the computations of $H_{s,c}$ below. For example, for
$s=80,$ and $c=7.7$, the cardinality of $H_{s,c}$, $|H_{s,c}|=1538$ and for
$s=85,$ and $c=7.7$, the cardinality of $H_{s,c}$, $|H_{s,c}|=2466.$ The
following table gives the $c$ values which we have chosen for each $s$ to
compute the set $H_{s,c}$.

$s$ | $c$
---|---
$9\leq s\leq 11$ | $3$
$12\leq s\leq 35$ | $3.42$
$36\leq s\leq 60$ | $5.5$
$61\leq s\leq 88$ | $7.7$

For each $n\in H_{s,c}$, we apply Lemma 2.6 to derive that $g_{1}(x)=g(x,n,s)$
is irreducible except for $(n,s)\in T$ where

$\displaystyle T=$
$\displaystyle\\{(272,17),(144,21),(144,23),(144,25),(144,26),(312,26),(600,26),(216,29),(216,31),$
$\displaystyle(720,31),(240,35),(1440,35),(288,40),(288,41),(216,42),(216,44),(216,47),(288,47),$
$\displaystyle(288,48),(216,49),(144,51),(288,51),(144,53),(216,53),(288,53),(4320,55),(216,59),$
$\displaystyle(216,63),(288,63),(432,63),(672,63),(180,71),(192,71),(216,71),(216,79),(576,79),$
$\displaystyle(144,80),(192,80),(216,80),(320,80),(432,80),(576,80),(720,80),(4320,80)\\}$

We use IrreduicibilityQ command in Mathematica to check that $g_{1}(x)$ is
irreducible for all these values of $(n,s)\in T.$

######  Remark 3.1.

It is not necessary to compute $H_{s,c}$ for all values of $s$. For a fixed
$c$, if $[sc^{-1}]=[(s+1)c^{-1}]$ and $P(s+1)\leq[sc^{-1}]$, then
$H_{s,c}=H_{s+1,c}$. The assertion follows from the definitions of $H_{s,c,1}$
and $H_{s,c,2}$. Therefore $H_{s,c}=H_{s+1,c}$ for $s\in\\{19,27,29,34\\}$
with $c=3.42$, $s\in\\{39,41,47,49,53,55,59\\}$ with $c=5.5$ and
$s\in\\{62,69,71,74,79,83,87\\}$ with $c=7.7$.

######  Remark 3.2.

We can take $c=5.5$ or $c=7.7$ according as $s$ at least $36$ or $s\geq 60$
respectively. But we cannot take $c$ more than $3.42\frac{s}{s-1}$ without
sharpening [6, Corollary 6]. Consequently we get sets $H_{s,c}$ of smaller
size when $s\geq 36$ and this reduces the computations.

### Acknowledgements

The computations for calculating $H_{s,c}$ have been carried out by using
SAGE, and all other computations have been done in MATHEMATICA. We thank
Ankita Jindal for helping us with the computations. The second author is
supported by INSA during the period of this work.

## References

  * [1] M. Filaseta, _The irreducibility of all but finitely many Bessel polynomials_ , Acta Math. 174 (1993), 383-397.
  * [2] F. Hajir, _Some $\tilde{A}_{n}$-extensions obtained from generalized Laguerre polynomials_ Journal of Number Theory 50 (1995), 206-212.
  * [3] F. Hajir, Algebraic properties of a family of generalized Laguerre polynomials,_Canad. J. Math._ 61 (2009), 583-603.
  * [4] H. Hasse, _Number theory_ , Classics in Mathematics, Springer-Verlag, Berlin 2002.
  * [5] A. Jindal, S. Laishram and R. Sarma, Irreducibility and Galois groups of Generalised Laguerre Polynomials $L_{n}^{(-1-n-r)}(x)$, J. Number Theory 183 (2018), 388-406.
  * [6] S. G. Nair and T. N Shorey, _Irreducibility of Laguerre Polynomial $L_{n}^{(-1-n-r)}(x)$_, Indag. Math. 26 (2015), 615-625.
  * [7] S. G. Nair and T.N. Shorey, _Generalised Laguerre Polynomials with applications,_ Math. Student 86, (2017), 87-101.
  * [8] I. Schur,_Gleichungen ohne Affekt_ In: Gesammelte Abhandlungen, Band III, Springer-Verlag, Berlin, 1973, 191-197.
  * [9] I. Schur, _Affektlose Gleichungen in der Theorie der Laguerreschen und Hermiteschen Polynome_ , In: Gesammelte Abhandlungen, Band III, Springer-Verlag, Berlin-New York, 1973, 227-233.
  * [10] E.A Sell, On a certain family of generalized Laguerre polynomials, _J. Number Theory_ 107 (2004), 266-281.
  * [11] S. B. Sinha and T.N. Shorey, Extension of Laguerre Polynomials with negative arguments, Indag. Math, to appear.
  * [12] T. N. Shorey and R. Tijdeman, _Generalizations of some irreducibility results by Schur_ ,_Acta Arith._ 145 (2010), 341-371.