# Normal limiting distributions
for systems of linear equations in random sets

Juanjo Rué Email<EMAIL_ADDRESS>Research of J. R. supported by the
Spanish State Research Agency through projects MTM2017-82166-P,
PID2020-113082GB-I00, the Severo Ochoa and María de Maeztu Program for Centers
and Units of Excellence in R&D (CEX2020-001084-M), and the Marie Curie RISE
research network ’RandNet’ MSCA-RISE-2020-101007705. Departament de
Matemàtiques and Institut de Matemàtiques de la UPC (IMTech), Universitat
Politècnica de Catalunya & Centre de Recerca Matemàtica & Barcelona Graduate
School of Mathematics (BGSMath), Barcelona, Spain.  Maximilian Wötzel Email:
<EMAIL_ADDRESS>This research was conducted while M. W. was a member
of the Barcelona Graduate School of Mathematics (BGSMath) as well as the
Universitat Politècnica de Catalunya. Maximilian Wötzel acknowledges financial
support from the Fondo Social Europeo and the Agencia Estatal de Investigación
through the FPI grant number MDM-2014-0445-16-2 and the Spanish Ministry of
Economy and Competitiveness, through the María de Maeztu Programme for Units
of Excellence in R&D (MDM-2014-0445), through the project MTM2017-82166-P, as
well as from the Dutch Science Council (NWO) through the grant number
OCENW.M20.009. Department of Mathematics, Radboud University, Nijmegen, The
Netherlands.

###### Abstract

We consider the binomial random set model $[n]_{p}$ where each element in
$\\{1,\dots,n\\}$ is chosen independently with probability $p:=p(n)$. We show
that for essentially all regimes of $p$ and very general conditions for a
matrix $A$ and a column vector $\bm{b}$, the count of specific integer
solutions to the system of linear equations $A\bm{x}=\bm{b}$ with the entries
of $\bm{x}$ in $[n]_{p}$ follows a (conveniently rescaled) normal limiting
distribution. This applies among others to the number of solutions with every
variable having a different value, as well as to a broader class of so-called
non-trivial solutions in homogeneous strictly balanced systems. Our proof
relies on the delicate linear algebraic study both of the subjacent matrices
and the corresponding ranks of certain submatrices, together with the
application of the method of moments in probability theory.

##  1 Introduction and main results

The study of the existence of solutions to linear equations in subsets of the
integers (and more generally in additive or even non-abelian groups) has been
a prominent topic not only in number theory, but also in extremal
combinatorics, ergodic theory, functional analysis and theoretical computers
science, among other research areas. A prototypical example of such
investigations is Roth’s Theorem [8], which proves (by using Fourier analytic
means) that dense sets of integers always contain arithmetic progressions of
length 3. This result was fully generalized by Szemerédi [17], who obtained a
similar statement for arithmetic progressions of all (fixed) lengths.

Following this line of research, Frankl, Graham and Rödl [5, Theorem 2] proved
similar results for homogeneous systems of linear equations. In particular,
they proved that when $A$ is a _density regular_ matrix with integer entries
(that is, the columns of $A$ sum up to the zero vector), then any dense
integer set $T$ will contain solutions to the linear system $A\bm{x}=0$. This
result generalizes Szemerédi’s Theorem, as arithmetic progressions of length
$k$ (or $k$-APs for short) can be encoded as solutions to the linear system
$x_{2}-x_{1}=x_{3}-x_{2}=\dots=x_{k}-x_{k-1}$. Other classical equations, such
as the Schur equation for sum-free sets (sets without solutions to the
equation $x+y=z$), and Sidon sets (sets without non-trivial solutions to the
equation $x+y=z+t$) also fit into this framework.

A very recent trend of investigation is to transfer these extremal results to
a sparse setting, and hence to prove analogues on subsets which are dense
relative to certain ambient sets. Specific examples for such sparse ambient
sets are for instance the primes or perfect powers, but also the binomial
random set $[n]_{p}$ obtained by choosing to include independently each
element in $[n]=\\{1,2,\dots,n\\}$ with probability $p$. Returning to the
example of $k$-APs, define a set $T$ to be _$(\delta,k)$ –Szemerédi_ if every
subset $U\subseteq T$ with at least $\delta|T|$ elements contains a $k$-AP.
Thus, Szemerédi’s Theorem shows that $[n]$ (in fact, every set $T$ that is
itself dense in $[n]$) is $(\delta,k)$–Szemerédi for every $\delta$ and $k$.
For the specific case of $k=3$, Kohayakawa, Łuczak and Rödl [7] proved that
for all $\delta>0$ there exists constants $c,C>0$ such that if $p\leq
cn^{-1/2}$, then as $n$ tends to infinity,
$\operatorname{\bm{P}}(\text{$[n]_{p}$ is $(\delta,3)$--Szemer\'{e}di})$ tends
to $0$, while if $p\geq Cn^{-1/2}$, it tends to $1$. The existence of this
threshold was extended to all values of $k$ in [14, 4], and later rediscovered
in [13, 1] in the context of independent sets in hypergraphs. These ideas,
named _hypergraph container method_ were then used by Spiegel [15] and
independently by Hancock, Staden and Treglown [6] to extend [5, Theorem 2] to
the broadest class of linear systems possible. Similar techniques were used by
Rué, Serra and Vena [10] to study random sparse analogues of [5, Theorem 2] in
finite fields and more general configurations than linear systems of
equations.

The main contribution of our paper follows this trend of research, with the
aim of studying the _typical_ number of solutions to linear systems of
equations in random sets of integers. Our main theorem, Theorem 18 is
technical and in order to formally state it we need to introduce a wide
variety of algebraic definitions and lemmas, which will be the core of Section
2. However, we will now introduce some main definitions in order to be able to
formulate two important consequences of Theorem 18, namely Theorems 4 and 7.

##### Proper solutions and their distribution

In order to properly state our results we need to introduce some notation. Let
$m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$ an integer matrix,
and $\bm{b}\in\mathbb{Z}^{r}$ an integer vector. We write the _rank_ of a
matrix $A$ by $\operatorname{rk}(A)$. Define
$S(A,\bm{b})=\\{\bm{x}\in\mathbb{Z}^{m}:A\bm{x}=\bm{b}\\}$ as the set of
integer solutions to the system of linear equations $A\bm{x}=\bm{b}$.
Furthermore, if $Q\subset[m]$, let $A^{Q}\in\mathbb{Z}^{r\times|Q|}$ denote
the $r\times|Q|$ matrix obtained by only keeping the columns of $A$ indexed by
$Q$. We notice that the rank of the empty matrix $A^{\emptyset}$ is zero. We
will identify tuples $\bm{x}=(x_{1},\dots,x_{m})\in\mathbb{Z}^{m}$ with the
corresponding column vectors but abuse notation slightly by letting
$\bm{x}^{Q}$ denote the vector obtained by only keeping the _rows_ of
$\bm{x}$. This should not be confused with the notation $\bm{x}^{k}$, where
$k$ is a positive integer, which we will use to denote the vector

$\bm{x}^{k}=(\underbrace{\bm{x},\dots,\bm{x}}_{\text{$k$
times}})=(x_{1},\dots,x_{m},x_{1},\dots,x_{m},\dots,x_{1},\dots,x_{m})\in\mathbb{Z}^{km}.$

Finally, if $\bm{x}=(x_{1},\dots,x_{m})\in\mathbb{Z}^{m}$ is an $m$-tuple, we
will write $\\{\bm{x}\\}$ as a shorthand for the set
$\\{x_{1},\dots,x_{m}\\}$. In particular, if some entry in $\bm{x}$ is
repeated, then the cardinality of $\\{\mathbf{x}\\}$ is strictly less than
$m$.

Roughly speaking, our main goal in this paper is to estimate
$|S(A,\bm{b})\cap[n]_{p}^{m}|$, that is, the number of solutions whose entries
lie in $[n]_{p}$ for different regimes of $p$. In order for this to be a well-
posed problem, we need some definitions from [16] and [11].

######  Definition 1.

An integer matrix $A\in\mathbb{Z}^{r\times m}$ is said to be

  1. i)

_positive_ if there exists an integer solution to $A\bm{x}=\bm{0}$ having all
positive entries:

$S(A,\bm{0})\cap\mathbb{N}^{m}\neq\emptyset,$

and if for any pair of indices $i,j\in[m]$, $i\neq j$, there exists a solution
$(x_{1},\dots,x_{m})\in S(A,\bm{0})$ satisfying $x_{i}\neq x_{j}$.

  2. ii)

_abundant_ if $\operatorname{rk}(A)>0$ and the removal of at most two columns
does not change the rank of $A$:

$\operatorname{rk}(A^{Q})=\operatorname{rk}(A)$

for any $Q\subset[m]$ satisfying $|Q|\geq m-2$.

Sometimes the second requirement for positivity in Definition 1 is called
_irredundancy_. For our applications, we will never consider positivity and
irredundancy separately, and hence we have combined those two properties into
a single one for expediency’s sake.

In general, considering any possible solution in $S(A,\bm{b})$ is a bit too
lenient. For instance, in the $3$-AP situation (whose associated matrix is
$A=\begin{pmatrix}1&-2&1\end{pmatrix}$), $S(A,\bm{0})$ also contains all the
tuples $(a,a,a)$ with $a\in\mathbb{Z}$, and those are clearly not of interest.
To remedy this issue we need to introduce the easy notion of _proper_
solutions to $A\bm{x}=\bm{b}$.

######  Definition 2.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$, and
$\bm{b}\in\mathbb{Z}^{r}$. Then the set $S_{0}(A,\bm{b})$ of _proper_
solutions is the subset of $S(A,\bm{b})$ with all coordinates being pairwise
distinct, that is

$S_{0}(A,\bm{b})=\\{(x_{1},\dots,x_{m})\in S(A,\bm{b}):x_{i}\neq x_{j}\text{
for all }1\leq i<j\leq m\\}.$

Before proceeding to the statement of our first main result, we need to define
one more parameter, which will measure the densest subsystem of $A$. The
motivation behind this can be compared to the graph setting, where one wants
to study the number of occurrences of some fixed graph $G$ as a subgraph of a
binomial random graph with $n$ vertices and edge probability $p$. Here, one
naively would expect the threshold for a random graph to contain $G$ to be
when $p$ is around $n^{-v(G)/e(G)}$, which is when the expected number of
copies of $G$ flips from $0$ to positive. But this is not the case: if $G$
contains a subgraph $H$ with $v(H)/e(H)>v(G)/e(G)$, then $n^{-v(H)/e(H)}$ will
define the threshold instead. A similar behavior occurs for the distribution
of subgraph counts, as shown by Ruciński in [9].

######  Definition 3.

For positive integers $m>r$ and a positive integer matrix
$A\in\mathbb{Z}^{r\times m}$, define the _density_ $c(A)$ of $A$ by

$c(A)=\max_{\emptyset\neq Q\subset[m]}\frac{|Q|}{|Q|-r_{Q}},$

where
$r_{Q}=r_{Q}(A)=\operatorname{rk}(A)-\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})$, and $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}=[m]\setminus Q$.

Note that this is indeed well-defined, since for a positive matrix we see that
$\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})\geq\operatorname{rk}(A)-|Q|+1$ for every $\emptyset\neq Q\subset m$
(see, for instance, the proof of Lemma 12).

We are now ready to state our first main theorem. For a random variable $X$
with finite first moment $\mathbb{E}(X)$ and non-zero finite variance
$\operatorname{\mathbb{V}\mathrm{ar}}(X)$, denote by
$\tilde{X}=(X-\operatorname{\mathbb{E}}(X))/\sqrt{\operatorname{\mathbb{V}\mathrm{ar}}(X)}$
its normalization. We write $X_{n}\xrightarrow{d}Y$ when a sequence of random
variables $\\{X_{n}\\}_{n\geq 1}$ tends in distribution to $Y$.

######  Theorem 4.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$ a positive and
abundant integer matrix, and $\bm{b}\in\mathbb{Z}^{r}$ such that
$S(A,\bm{b})\neq\emptyset$. Furthermore, let $n$ be an integer, $0\leq
p:=p(n)\leq 1$ and $X_{n}$ the random variable equal
$|S_{0}(A,\bm{b})\cap[n]_{p}^{m}|$, which counts the number of proper
solutions $\bm{x}\in[n]_{p}^{m}$ to $A\bm{x}=\bm{b}$. Then

$\tilde{X}_{n}\xrightarrow{d}\mathcal{N}(0,1)$

if $n(1-p)\to\infty$ and $np^{c(A)}\to\infty$.

Note that in the specific case of $k$-APs, this problem was already
investigated by Barhoumi-Andréani, Koch and Liu [2]. In fact, they prove not
only results on the limiting distribution of the number of $k$-term arithmetic
progressions in $[n]_{p}$ even when $k$ is unbounded (but sub-logarithmic),
they also establish a bivariate central limit theorem for the joint
distribution when considering the counts of two distinct progression lengths.
In contrast, Theorem 4 in the setting of progressions requires the length to
be fixed.

##### Non-trivial solutions, and main theorem for their distribution

Proper solutions are always of interest in the number theoretical context, but
in a wide variety of situations we need to take care of non-proper solutions.
For example, for $A=\begin{pmatrix}1&1&-1&-1\end{pmatrix}$, we see that
$S(A,\bm{0})$ is the number of additive quadruples satisfying $a+b=c+d$.
Clearly, if $\\{a,b\\}\cap\\{c,d\\}\neq\emptyset$, then these two sets must in
fact be the same. On the other hand, solutions of the form $2a=c+d$ with
$a\notin\\{c,d\\}$ are not proper but obviously of interest and might be
considered as valid ones.

Keeping this in mind, we will now recall the notion of _non-trivial_ solutions
for systems of linear equations due to Rué, Spiegel and Zumalacárregui [11]
which generalized an earlier notion of this for single line equations
introduced by Ruzsa [12]. For a solution $\bm{x}=(x_{1},\dots,x_{m})\in
S(A,\bm{b})$, we define $\mathfrak{p}(\bm{x})\subset 2^{[m]}$ to be the
partition of $[m]$ such that for any $i,j\in[m]$ it holds that $x_{i}=x_{j}$
if and only if $i$ and $j$ are in the same partition class of
$\mathfrak{p}(\bm{x})$. One can view $\mathfrak{p}(\bm{x})$ as an ordered
$|\mathfrak{p}(\bm{x})|$-tuple $(C_{1},\dots,C_{|\mathfrak{p}(\bm{x})|})$ such
that $\min C_{i}<\min C_{j}$ whenever $i<j$. Doing this, we can now define the
matrix $A_{\mathfrak{p}(\bm{x})}$ in the following way. Suppose the columns of
$A$ are denoted by $\bm{c}_{1},\dots,\bm{c}_{m}\in\mathbb{Z}^{r}$, then

$A_{\mathfrak{p}(\bm{x})}={\begin{pmatrix}\sum_{i\in
C_{1}}\bm{c}_{i}&\big{|}&\sum_{i\in
C_{2}}\bm{c}_{i}&\big{|}&\cdots&\big{|}&\sum_{i\in
C_{|\mathfrak{p}(\bm{x})|}}\bm{c}_{i}\end{pmatrix}},$

so $A_{\mathfrak{p}(\bm{x})}\in\mathbb{Z}^{r\times|\mathfrak{p}(\bm{x})|}$ is
the $r\times|\mathfrak{p}(\bm{x})|$ matrix obtained by contracting all columns
in the same partition class, with columns ordered by the minimum index in each
class. Finally, define the set

$\mathfrak{P}(A)=\\{\mathfrak{p}\subset 2^{[m]}:\mathfrak{p}\text{ is a
partition of }[m]\text{ and
}\operatorname{rk}(A_{\mathfrak{p}})=\operatorname{rk}(A)\\}.$

We are finally ready to introduce the notion of a _non-trivial_ solution.

######  Definition 5.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$, and
$\bm{b}\in\mathbb{Z}^{r}$. Then the set $S_{1}(A,\bm{b})$ of _non-trivial_
solutions is the subset of $S(A,\bm{b})$ with associated partitions coming
from $\mathfrak{P}(A)$, that is

$S_{1}(A,\bm{b})=\\{\bm{x}\in
S(A,\bm{b}):\mathfrak{p}(\bm{x})\in\mathfrak{P}(A)\\}.$

This definition might seem quite arbitrary, but the interested reader is
invited to read the discussions in [11] and [16] which show that, in some
sense, it is quite natural in that it encompasses the natural notions of non-
triviality for specific systems of linear equations studied in the literature.
When we want to investigate the distribution of nontrivial solutions, we
actually need to look at $c(A_{\mathfrak{p}})$ for any partition type
$\mathfrak{p}$ that is to be considered. A special case in which it suffices
to only consider $c(A)$ is that of _strictly balanced_ systems.

######  Definition 6.

Let $m>r$ be positive integers and $A\in\mathbb{Z}^{r\times m}$ be positive.
Then the matrix $A$ is called _strictly balanced_ if

$c(A)=\frac{m}{m-\operatorname{rk}(A)}>\max_{\emptyset\subsetneqq
Q\subsetneqq[m]}\frac{|Q|}{|Q|-r_{Q}(A)},$

and furthermore for every
$\mathfrak{p}\in\mathfrak{P}(A)\setminus\\{\\{1\\},\\{2\\},\dots,\\{m\\}\\}$
such that $A_{\mathfrak{p}}$ is positive, it holds that
$c(A)>c(A_{\mathfrak{p}})$.

We can prove the following theorem about the distribution of nontrivial
solutions of strictly balanced systems of linear equations.

######  Theorem 7.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$ a positive and
abundant strictly balanced integer matrix such that
$S(A,\bm{0})\neq\emptyset$. Furthermore, let $n$ be an integer, $0\leq
p:=p(n)\leq 1$ and $X_{n}$ the random variable
$|S_{1}(A,\bm{0})\cap[n]_{p}^{m}|$ that counts the number of non-trivial
solutions $\bm{x}\in[n]_{p}^{m}$ to $A\bm{x}=\bm{0}$. Then

$\tilde{X}_{n}\xrightarrow{d}\mathcal{N}(0,1)$

if $n(1-p)\to\infty$ and $np^{c(A)}\to\infty$.

Both of our main results can be compared to those proved in [11] and [16]. In
the former the authors investigated the threshold behavior of
$|S_{1}(A,\bm{0})\cap[n]_{p}^{m}|$ when $A\in\mathbb{Z}^{r\times m}$ is a
positive matrix and in the latter, Spiegel extended this to
$|S_{1}(A,\bm{b})\cap[n]_{p}^{m}|$ for an arbitrary $\bm{b}\in\mathbb{Z}^{r}$
when $A$ is positive and also abundant.

In that sense, their results hold in a more general setting, even when
compared to our main technical result, Theorem 18. However, we note that the
study of the distribution is more delicate than the threshold behavior, as can
be seen by another result from [11], in which the authors explore the behavior
at the threshold of nontrivial solutions to $A\bm{x}=\bm{0}$ for strictly
balanced systems, that is, they work exactly in the same setting as in Theorem
7.

To conclude this section, let us mention that the core of the proof is based
on a combination of algebraic ideas dealing with the matrix associated with
the linear system of equations and the method of moments in probability theory
to show convergence towards a normal distribution. The second part is highly
inspired by the techniques developed by Ruciński in [9] where he proved the
following result on the distribution of the number of occurrences of a fixed
graph $G$ as a subgraph in a binomial random graph.

######  Theorem 8 ([9]).

Let $G$ be a graph on $v(G)$ vertices and $e(G)$ edges. Furthermore, let $n$
be an integer, $0\leq p:=p(n)\leq 1$ and $X_{n}$ the random variable that the
number of subgraphs of $G(n,p)$ that are isomorphic to $G$. Then

$\tilde{X}_{n}\xrightarrow{d}\mathcal{N}(0,1)$

if and only if $n^{2}(1-p)\to\infty$ and $np^{d(G)}\to\infty$, where
$d(G)=\max_{H\subset G}e(H)/v(H)$ is the _density_ of $G$.

The proof of our main result, Theorem 18 which in particular implies Theorems
4 and 7 follows a similar structure as that of Theorem 8. Specifically, in
order to show that the stated conditions on $p$ are sufficient, one considers
three different ranges of $p$ and determines the exact structure of the
objects that actually affect the moments.

It turns out that when viewed through the lens of hypergraphs, these important
objects will actually be essentially the same for both graphs and systems of
linear equations. However, we want to stress that actually establishing this
fact requires the delicate study of the more difficult linear algebraic
structure of the patterns we want to take into account, and hence our work
highly differs from [9].

##### Plan of the paper

In Section 2 we will state some needed prior results from [11] and [16], as
well as prove intermediate lemmas that are needed to establish a meta result,
namely Theorem 18 from which one can deduce Theorems 4 and 7. Section 3 will
then be devoted entirely to stating and proving this main meta result, Theorem
18. To do this, we will be using the so-called method of moments to analyze
three distinct regimes of the probability $p$. We conclude with a discussion
on some remaining open problems in Section 4. In particular, we will
investigate the question of whether the sufficient conditions on $p$ in
Theorems 4, 7 and 18 are also necessary.

##  2 Algebraic properties of systems of linear equations

Let us start by investigating the relation between proper and non-trivial
solutions. For any $A\in\mathbb{Z}^{r\times m}$ and $\bm{b}\in\mathbb{Z}^{r}$
it is clear that

$S_{0}(A,\bm{b})\subset S_{1}(A,\bm{b})\subset S(A,\bm{b}).$

Furthermore, suppose $s>1$ and we fix a specific
$(C_{1},\dots,C_{s})=\mathfrak{p}\in\mathfrak{P}(A)$ such that $\min
C_{i}<\min C_{j}$ whenever $i<j$. Then if $\bm{x}=(x_{1},\dots,x_{m})\in
S_{1}(A,\bm{b})$ satisfies $\mathfrak{p}(\bm{x})=\mathfrak{p}$, we see that
$\tilde{\bm{x}}=(x_{\min C_{1}},\dots,x_{\min C_{s}})\in\mathbb{Z}^{s}$ has
$s$ pairwise distinct coordinates and $A_{\mathfrak{p}}\tilde{\bm{x}}=\bm{b}$,
so $\tilde{\bm{x}}\in S_{0}(A_{\mathfrak{p}},\bm{b})$. Conversely, for any
proper solution $\bm{x}=(x_{1},\dots,x_{s})$ in
$S_{0}(A_{\mathfrak{p}},\bm{b})$, we see that the vector
$\tilde{\bm{x}}\in\mathbb{Z}^{m}$ with $i$-th coordinate $\tilde{x}_{i}$
defined as

$\tilde{x}_{i}=\sum_{j=1}^{s}x_{j}\cdot\delta_{i\in C_{j}}$

satisfies $\mathfrak{p}(\tilde{\bm{x}})=\mathfrak{p}$ and
$A\tilde{\bm{x}}=\bm{b}$ (here $\delta_{i\in C_{j}}$ denotes the indicator
function which takes values $0$ or $1$ if $i\not\in C_{j}$ and $i\in C_{j}$,
respectively). So we get the following lemma, which is essentially Lemma 1.10
in [16].

######  Lemma 9 ([16]).

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$, and
$\bm{b}\in\mathbb{Z}^{r}$. Then for any partition
$\mathfrak{p}\in\mathfrak{P}(A)$ and any subset $T\subset\mathbb{Z}$, it holds
that

$|\\{\bm{x}\in S_{1}(A,\bm{b}):\mathfrak{p}(\bm{x})=\mathfrak{p}\\}\cap
T^{m}|=|S_{0}(A_{\mathfrak{p}},\bm{b})\cap T^{|\mathfrak{p}|}|.$

Lemma 9 will be very helpful because if $A$ is positive, then the approximate
size of $S_{0}(A,\bm{b})$ is not difficult to determine for any vector
$\bm{b}$. Specifically, we have the following result which is Lemma 1.4 in
[16].

######  Lemma 10 ([16]).

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$, and
$\bm{b}\in\mathbb{Z}^{r}$ such that $S(A,\bm{b})\neq\emptyset$. Then if
$n\in\mathbb{N}$ it holds that

$|S_{0}(A,\bm{b})\cap[n]^{m}|\leq|S(A,\bm{b})\cap[n]^{m}|\leq
n^{m-\operatorname{rk}(A)}.$

Furthermore, if $A$ is positive we also have

$|S_{0}(A,\bm{b})\cap[n]^{m}|=\Omega(n^{m-\operatorname{rk}(A)}).$

In [11] the authors managed to find a threshold probability function for when
non-trivial solutions to a homogeneous system of linear equations appear in
$[n]_{p}$, but for our current purposes we need to make one more specification
regarding types of solutions. The issue essentially lies in the fact that
while $A$ is positive, the same might not hold for $A_{\mathfrak{p}}$ for some
$\mathfrak{p}\in\mathfrak{P}(A)$. Note that this can only happen in the case
$\bm{b}\neq\bm{0}$, since clearly
$S_{0}(A_{\mathfrak{p}},\bm{0})\neq\emptyset$ implies that $A_{\mathfrak{p}}$
is positive. As a problematic example, consider for instance the matrix
$A=\begin{pmatrix}1&1&1&1&-1\end{pmatrix}$ which is positive since for
instance $\bm{x}=(1,2,3,4,10)\in\mathbb{N}^{5}$ is a proper solution to the
system $A\bm{x}=\bm{0}$. But taking $\bm{b}=6$, we see that
$\bm{y}=(1,2,3,3,3)$ satisfies $A\bm{y}=\bm{b}$. We have
$\mathfrak{p}(\bm{y})=(\\{1\\},\\{2\\},\\{3,4,5\\})$ and hence
$A_{\mathfrak{p}(\bm{y})}=\begin{pmatrix}1&1&1\end{pmatrix}$ which is clearly
not positive.

The problem arises as follows: if $A_{\mathfrak{p}}$ is not positive but we
still have a significant number of solutions of this type – this can for
instance be achieved by using the previous example as a gadget in a larger
system – the number of solutions in the random binomial set will depend
heavily on whether or not a specific bounded number of elements are included,
and so getting any good results on their distribution is unlikely.

Having stated this motivation, we first introduce the concept of _positive
partitions_ as the subset $\mathfrak{P}_{0}(A)\subset\mathfrak{P}(A)$ such
that

$\mathfrak{P}_{0}(A)=\\{\mathfrak{p}\in\mathfrak{P}(A):A_{\mathfrak{p}}\text{
is positive}\\}.$

For any $\mathfrak{P}\subset\mathfrak{P}(A)$ we can now define the concept of
_type- $\mathfrak{P}$_ solutions.

######  Definition 11.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$,
$\bm{b}\in\mathbb{Z}^{r}$, and $\mathfrak{P}\subset\mathfrak{P}(A)$. Then the
set $S_{\mathfrak{P}}(A,\bm{b})$ of _type- $\mathfrak{P}$_ solutions is the
subset of $S(A,\bm{b})$ with associated partitions coming from $\mathfrak{P}$,
that is

$S_{\mathfrak{P}}(A,\bm{b})=\\{\bm{x}\in
S(A,\bm{b}):\mathfrak{p}(\bm{x})\in\mathfrak{P}\\}.$

If $\mathfrak{P}=\\{\mathfrak{p}\\}$, we will write
$S_{\mathfrak{p}}(A,\bm{b})$ instead of $S_{\\{\mathfrak{p}\\}}(A,\bm{b})$.

Non-trivial solutions are therefore the same as type-$\mathfrak{P}(A)$
solutions. The following is a straightforward consequence of Lemma 9 and the
upper bound in Lemma 10.

######  Lemma 12.

Let $m>r$ and $n$ be positive integers, $A\in\mathbb{Z}^{r\times m}$ positive,
$\bm{b}\in\mathbb{Z}^{r}$, $\mathfrak{P}\subset\mathfrak{P}_{0}(A)$, and
$Z\subset[n]$ a fixed set. Then

$\big{|}\\{\bm{y}\in S_{\mathfrak{P}}(A,\bm{b})\cap[n]^{m}:\\{\bm{y}\\}\cap
Z\neq\emptyset\\}\big{|}=O(n^{m-\operatorname{rk}(A)-1}).$

Furthermore, if $A$ is also abundant, then

$\big{|}\\{\bm{y}\in S_{\mathfrak{P}}(A,\bm{b})\cap[n]^{m}:|\\{\bm{y}\\}\cap
Z|\geq 2\\}\big{|}=O(n^{m-\operatorname{rk}(A)-2}).$

###### Proof.

We will consider each partition $\mathfrak{p}\in\mathfrak{P}$ separately. Due
to Lemma 9 we can consider $\bm{y}\in
S_{0}(A_{\mathfrak{p}},\bm{b})\cap[n]^{|\mathfrak{p}|}$. If $\bm{y}$ contains
an element of $Z$, then there exists some non-empty index set
$Q\subset[|\mathfrak{p}|]$ and a vector $\bm{z}\in Z^{|Q|}$ such that
$\bm{y}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}\in S_{0}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},\bm{b}-A_{\mathfrak{p}}^{Q}\bm{z})\cap[n]^{|\mathfrak{p}|-|Q|}$ (note
that here, $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}=[|\mathfrak{p}|]\setminus Q$). By Lemma 10, we have

$\big{|}S_{0}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},\bm{b}-A_{\mathfrak{p}}^{Q}\bm{z})\cap[n]^{|\mathfrak{p}|-|Q|}\big{|}\leq
n^{|\mathfrak{p}|-|Q|-\operatorname{rk}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})}.$

$A_{\mathfrak{p}}$ is positive, which implies that

$\operatorname{rk}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})\geq\operatorname{rk}(A_{\mathfrak{p}})-|Q|+1=\operatorname{rk}(A)-|Q|+1.$

Indeed, the positivity implies that the removal of any single column will not
change the rank of the resulting matrix, and since the rank of a matrix is the
dimension of its column space, any subsequent removal decreases the rank by at
most $1$. Hence

$|\mathfrak{p}|-|Q|-\operatorname{rk}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})\leq|\mathfrak{p}|-\operatorname{rk}(A)-1\leq
m-\operatorname{rk}(A)-1.$ (1)

Since there are only $O(1)$ choices for $\mathfrak{p}$, $Q$ and $\bm{z}$, this
implies the result. For the second part, note first that for any
$|\mathfrak{p}|<m$, Relation (1) actually implies the statement already, so it
only remains to consider the case $|\mathfrak{p}|=m$, that is, $\bm{y}\in
S_{0}(A,\bm{b})\cap[n]^{m}$. If $A$ is abundant, the removal of any two
columns keeps the rank constant, while any subsequent removal will decrease it
by at most $1$ at a time. Hence for any $Q\subset[m]$ with $|Q|\geq 2$ we have

$\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})\geq\operatorname{rk}(A)-|Q|+2,$

and so

$m-|Q|-\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})\leq m-\operatorname{rk}(A)-2,$

which is what we wanted to show. ∎

###  2.1 Compounded matrices

While Lemma 12 showed that the upper bound of Lemma 10 is always helpful in
the situation of counting solutions with some entries fixed beforehand, the
requirement of positivity is sometimes too restrictive to do the same for the
lower bound. Suppose $\bm{x}\in S_{1}(A,\bm{b})$ is some fixed non-trivial
solution. We want then to count the number of solutions $\bm{y}\in
S_{1}(A,\bm{b})$ that intersect $\bm{x}$, that is, the size of the set
$S_{0}(A_{\mathfrak{p}(\bm{y})}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},\bm{b}-A_{\mathfrak{p}(\bm{y})}^{Q}\tilde{\bm{x}})$, where
$Q\subset[|\mathfrak{p}(\bm{y})|]$ is some index set and
$\tilde{\bm{x}}\in\\{\bm{x}\\}^{|Q|}$. Lemma 12 with $Z=\\{\bm{x}\\}$
immediately gives helpful upper bounds, but there are two issues when trying
to apply the lower bound of Lemma 10 directly.

The first is that when summing over several distinct $Q$, the same solution
will be counted multiple times, but this could be alleviated by just counting
a single $Q$ that maximizes the cardinality of the corresponding set. The
bigger issue is that it is not clear at all that the matrix
$A_{\mathfrak{p}(\bm{y})}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{Q}}$
will be positive, and in fact this is not true in general even when
$A_{\mathfrak{p}(\bm{y})}$ is itself positive. Consider for instance the
matrix $A=\begin{pmatrix}1&1&-1\end{pmatrix}$ (associated with the _Schur
equation_ $x+y=z$), which is both positive and abundant. Then for any $Q$ with
$|Q|=1$, the equation $A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}(x,y)=\bm{0}$ implies either $x=y$ or $x=-y$, so in either case
positivity will be violated.

Instead, we will consider the concept of the _compounded_ matrix already used
in [11] to study the distribution at the threshold. For matrices
$A\in\mathbb{Z}^{r_{A}\times m_{A}}$, $B\in\mathbb{Z}^{r_{B}\times m_{B}}$ and
a bijection $M\colon P\to[m_{B}]$ with
$P=\\{p_{1}<\dots<p_{|P|}\\}\subset[m_{A}]$, define the
$(r_{A}+r_{B})\times(m_{A}+m_{B}-|P|)$ matrix $A\overset{M}{\times}B$ as

$A\overset{M}{\times}B=\left(\begin{array}[]{c|c|c|c|c}A^{[m_{A}]\setminus
P}&\bm{a}_{p_{1}}&\dots&\bm{a}_{p_{|P|}}&\bm{0}\\\
\hline\cr\bm{0}&\bm{b}_{M(p_{1})}&\dots&\bm{b}_{M(p_{|P|})}&B^{[m_{B}]\setminus
M(P)}\rule{0.0pt}{12.48604pt}\end{array}\right),$

where $\bm{a}_{1},\dots,\bm{a}_{m_{A}}$ denote the columns of $A$ and
$\bm{b}_{1},\dots,\bm{b}_{m_{B}}$ the columns of $B$. Note that while we can
apply this operator iteratively, the operation is in general not associative
or even well-defined, that is

$(A\overset{M}{\times}B)\overset{M^{\prime}}{\times}C\neq
A\overset{M}{\times}(B\overset{M^{\prime}}{\times}C).$

An exception to this is the case when $\operatorname{dom}(M)=\emptyset$, which
we will abbreviate by writing $A\overset{\bm{.}}{\times}B$. In general,
whenever no parentheses are used the compounded matrix is implied to be
constructed from left to right iteratively, that is
$A\overset{M}{\times}B\overset{M^{\prime}}{\times}C:=(A\overset{M}{\times}B)\overset{M^{\prime}}{\times}C$.
An important example that will appear often concerns the case $A=B$ and
$M=id_{Q}$ the identity function for some index set $Q\subset[m_{A}]$, that
is,

$A\overset{\operatorname{id}_{Q}}{\times}A=\left(\begin{array}[]{c|r|c}A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}&A^{Q}&\bm{0}\\\ \hline\cr\bm{0}&A^{Q}&A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}\rule{0.0pt}{12.48604pt}\end{array}\right).$

The reason to study these matrices is natural: Let
$\rho_{A}=\rho_{A}(M)\colon[m_{A}]\to[m_{A}]$ be the bijective function that
maps the column indices of the first $[m_{A}]$ columns of
$A\overset{M}{\times}A$ to the corresponding ones of $A$, and define
$\rho_{B}\colon[m_{A}+m_{B}-|P|]\setminus[m_{A}-|P|]\to[m_{B}]$ similarly.
Recall that for any integer $t>1$, $\bm{b}^{t}$ denotes the vector
$(\bm{b},\dots,\bm{b})\in\mathbb{Z}^{rt}$. Then
$\bm{z}=(z_{1},\dots,z_{m_{A}+m_{B}-|P|})$ is a proper integer solution to the
system of linear equations $(A\overset{M}{\times}B)\bm{z}=\bm{b}^{2}$ if and
only if

$\bm{x}=(x_{1},\dots,x_{m_{A}}):=(z_{\rho^{-1}_{A}(1)},\dots,z_{\rho^{-1}_{A}(m_{A})})\text{
and
}\bm{y}=(y_{1},\dots,y_{m_{B}}):=(z_{\rho^{-1}_{B}(1)},\dots,z_{\rho^{-1}_{A}(m_{B})})$

are proper solutions to the systems $A\bm{x}=\bm{b}$ and $B\bm{y}=\bm{b}$, and
for any $i\in[m_{A}]$ and $j\in[m_{B}]$ it holds that $x_{i}=y_{j}$ if and
only if $i\in P$ and $j=M(i)$. In other words, elements of
$S_{0}(A\overset{M}{\times}B,\bm{b}^{2})$ correspond to pairs of proper
solutions in $S_{0}(A,\bm{b})$ and $S_{0}(B,\bm{b})$ that intersect exactly in
the coordinates indicated by the function $M$.

We first state an easy but important property that any compounded matrix
satisfies:

######  Lemma 13.

Let $m_{A}>r_{A}$ and $m_{B}>r_{B}$ be positive integers,
$A\in\mathbb{Z}^{r_{A}\times m_{A}}$, $B\in\mathbb{Z}^{r_{B}\times m_{B}}$,
$P\subset[m_{A}]$, $M\colon P\to[m_{B}]$ a bijection and
$Q\subset[m_{A}+m_{B}-|P|]$. If we define $Q_{1}=Q\cap[m_{A}]$ and
$Q_{2}=Q\setminus Q_{1}$, then

$\operatorname{rk}\bigl{(}(A\overset{M}{\times}B)^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}\bigr{)}\geq\operatorname{rk}(A^{[m_{A}]\setminus
Q_{1}})+\operatorname{rk}(B^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{M}\setminus Q_{2}}).$

In particular,
$\operatorname{rk}(A\overset{M}{\times}B)\geq\operatorname{rk}(A)+\operatorname{rk}(B^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{M}})$.

###### Proof.

It is clear that the rank of $(A\overset{M}{\times}B)^{[m_{A}]\setminus
Q_{1}}$ is at least $rk(A^{[m_{A}]\setminus Q_{1}})=:r_{1}$, and similarly the
rank of $(A\overset{M}{\times}B)^{[m_{A}+m_{b}-|P|]\setminus([m_{A}]\cup
Q_{2})}$ is at least $\operatorname{rk}(B^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{M}\setminus Q_{2}})=:r_{2}$, so let $\bm{c}_{1},\dots,\bm{c}_{r_{1}}$ be a
collection of $r_{1}$ linearly independent vectors from the first
$m_{A}-|Q_{1}|$ columns of $(A\overset{M}{\times}B)^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{Q}}$
such that the corresponding column vectors of $A^{[m_{A}]\setminus Q_{1}}$ –
that is, the vectors obtained by only considering the first $r_{A}$ rows – are
also linearly independent, and $\bm{c}_{r_{1}+1},\dots,\bm{c}_{r_{1}+r_{2}}$ a
collection of $r_{2}$ of independent vectors from the $m_{B}-|P|-|Q_{2}|$ last
columns. Then since the entries in the first $r_{A}$ rows of
$\bm{c}_{r_{1}+1},\dots,\bm{c}_{r_{1}+r_{2}}$ are $0$ and the column vectors
obtained by only considering the first $r_{A}$ rows of
$\bm{c}_{1},\dots,\bm{c}_{r_{1}}$ are linearly independent, any linear
representation of $\bm{0}$

$\lambda_{1}\bm{c}_{1}+\dots+\lambda_{r_{1}+r_{2}}\bm{c}_{r_{1}+r_{2}}$

must satisfy $\lambda_{1}=\dots=\lambda_{r_{1}}=0$. But since the remaining
$r_{2}$ columns were also linearly independent, we must have
$\lambda_{r_{1}+1}=\dots=\lambda_{r_{1}+r_{2}}=0$ as well, and hence the
$r_{1}+r_{2}$ columns $\bm{c}_{1},\dots,\bm{c}_{r_{1}+r_{2}}$ are linearly
independent. Since the rank of a matrix is the dimension of its column space
we are done. ∎

Next we will show that for certain compounded matrices this is indeed the
correct rank.

######  Lemma 14.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$, and
$Q\subset[m]$. Then

$\operatorname{rk}(A\overset{\operatorname{id}_{Q}}{\times}A)=\operatorname{rk}(A)+\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}).$

###### Proof.

We prove by obtaining the same upper and lower bounds for
$\operatorname{rk}(A\overset{\operatorname{id}_{Q}}{\times}A)$. The lower
bound follows from Lemma 13. For the upper bound, note that by performing
elementary row and column operations we see that

$\operatorname{rk}(A\overset{\operatorname{id}_{Q}}{\times}A)=\operatorname{rk}\left(\begin{array}[]{c|r|c}A^{Q}&A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}&\bm{0}\\\ \hline\cr\bm{0}&-A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}&A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}\rule{0.0pt}{12.48604pt}\end{array}\right).$

Let $r_{1}=\operatorname{rk}(A)$ and
$r_{2}=\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})$ and suppose we have $r_{1}+r_{2}+1$ row vectors from this matrix. If
at least $r_{1}+1$ rows come from the upper half, then there exists a
nontrivial representation of $\bm{0}\in\mathbb{Z}^{1\times(2m-|Q|)}$, and
hence the remaining coefficients can be set to $0$. If on the other hand more
than $r_{2}+1$ rows come from the bottom half, we can achieve a nontrivial
representation of $\bm{0}$ only using these rows. Since one of those two cases
must happen, we have the required upper bound. ∎

The next result shows how positivity of $A$ can (under some conditions) be
passed on to a compounded matrix.

######  Lemma 15.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$ be positive, and
$Q\subset[m]$. If there exists an integer vector $\bm{y}\in
S(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},\bm{0})$ with all coordinates nonzero, then
$A\overset{\operatorname{id}_{Q}}{\times}A$ is positive.

###### Proof.

Since $A$ was positive, there exists a solution $\bm{x}=(x_{1},\dots,x_{m})\in
S(A,\bm{0})\cap\mathbb{N}^{m}$. But then if we define
$\bm{y}=(\bm{x}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},\bm{x}^{Q},\bm{x}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})$, we clearly have $\bm{y}\in
S(A\overset{\operatorname{id}_{Q}}{\times}A,\bm{0})\cap\mathbb{N}^{m}$. It
remains to be proved that for any two distinct indices $i,j\in[2m-|Q|]$, there
exists a solution $(x_{1},\dots,x_{2m-|Q|})=\bm{x}$ in
$S(A\overset{\operatorname{id}_{Q}}{\times}A,\bm{0})$ such that $x_{i}\neq
x_{j}$. Let $\rho\colon[2m-|Q|]\to[m]$ denote the surjective function that
maps the column indices of $A\overset{\operatorname{id}_{Q}}{\times}A$ to the
corresponding ones of $A$. If $\rho(i)\neq\rho(j)$, that is, $i$ and $j$ refer
to distinct variables of $A$, this again just follows directly from the fact
that $A$ was positive itself. So we need to check the case
$\rho(i)=\rho(j)\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{Q}$.
By our assumption on $A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}$, there exists a vector $\bm{y}\in S(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},\bm{0})$ with all its coordinates nonzero. Clearly, the same will hold
for $2\bm{y}$, and hence

$\bm{x}=(\bm{y},\bm{0},2\bm{y})\in\mathbb{Z}^{2m-|Q|}$

will satisfy $(A\overset{\operatorname{id}_{Q}}{\times}A)\bm{x}=\bm{0}$ and
the $i$-th and $j$-th entry of $\bm{x}$ are different. ∎

Note that if $A\in\mathbb{Z}^{r\times m}$ is abundant, then any $Q\subset[m]$
of size $|Q|=1$ will satisfy the requirements of Lemma 15. The next result
shows that even in the case that $Q$ itself does not satisfy them, we can find
a superset that does, which will help us to get universal lower bounds that
are sufficient for our applications.

######  Lemma 16.

Let $m>r$ be positive integers, $n\in\mathbb{N}$, $A\in\mathbb{Z}^{r\times m}$
positive, and $\bm{b}\in\mathbb{Z}^{r}$ such that $S(A,\bm{b})\neq\emptyset$.
Then for all $Q\subset[m]$ there exists $Q^{\prime}\supset Q$ such that

$\big{|}S_{0}(A\overset{\operatorname{id}_{Q^{\prime}}}{\times}A,\bm{b}^{2})\cap[n]^{2m-|Q^{\prime}|}\big{|}=\Omega\big{(}n^{2m-\operatorname{rk}(A)-\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})-|Q|}\big{)}.$

###### Proof.

If $Q$ satisfies the assumptions of Lemma 15, we see that
$A\overset{\operatorname{id}_{Q}}{\times}A$ is positive and hence we can apply
the lower bound of Lemma 10 directly with $Q^{\prime}=Q$, noting that
$A\overset{\operatorname{id}_{Q}}{\times}A$ has $2m-|Q|$ columns and rank
$\operatorname{rk}(A)+\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})$ by Lemma 14. Otherwise, denote by
$\bm{c}_{1},\dots,\bm{c}_{m}\in\mathbb{Z}^{r}$ the columns of $A$, and let
$Q_{1}\subset\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{Q}$
be the index set of the columns that will always have coefficient zero in a
linear combination of the zero vector. We claim that these columns are
linearly independent and their span does not contain any column $\bm{c}_{i}$
with $i\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}\setminus Q_{1}$. Indeed, linear independence holds because any non-
trivial linear combination $\sum_{i\in Q_{1}}\lambda_{i}\bm{c}_{i}=\bm{0}$
could be extended to a linear combination $\sum_{i\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}\lambda_{i}\bm{c}_{i}=\bm{0}$ such that $\lambda_{i}\neq 0$ for at
least one $i\in Q_{1}$, a contradiction to the definition of $Q_{1}$.
Similarly, if $\sum_{i\in Q_{1}}\lambda_{i}\bm{c}_{i}=\bm{c}_{j}$ for some
$j\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}\setminus Q_{1}$, we obviously see that $\sum_{i\in
Q_{1}}\lambda_{i}\bm{c}_{i}-\bm{c}_{j}=\bm{0}$ is a linear combination with at
least one $\lambda_{i}\neq 0$, again a contradiction.

We thus see that defining $Q^{\prime}=Q\cup Q_{1}$, the matrix
$A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}^{\prime}}$ has rank $\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}^{\prime}})=\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})-|Q_{1}|$ and its number of columns is $m-|Q^{\prime}|=m-|Q|-|Q_{1}|$,
and hence

$m-|Q^{\prime}|-\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}^{\prime}})=m-|Q|-\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}).$

By construction, $A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}^{\prime}}$ satisfies the assumption of Lemma 15, and hence for
$n\in\mathbb{N}$, applying Lemma 10 implies

$\big{|}S_{0}(A\overset{\operatorname{id}_{Q^{\prime}}}{\times}A,\bm{b}^{2})\cap[n]^{2m-|Q^{\prime}|}\big{|}=\Omega\big{(}n^{2m-\operatorname{rk}(A)-\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})-|Q|}\big{)},$

which is what we wanted to show. ∎

Lemmas 14 and 15 actually apply to a more general iterated construction. Using
the assumptions made in Lemma 13, write $Q=\\{q_{1}<\dots<q_{|Q|}\\}$, and
define for any integer $j\geq 1$ the bijection
$M_{j}\colon[j(m-|Q|)+|Q|]\setminus[j(m-|Q|)]\to[|Q|]$ by
$M_{j}(i)=q_{i-j(m-|Q|)}$. Then all the results mentioned in the
aforementioned lemmas also apply in a natural way to the matrix

$A\overset{\operatorname{id}_{Q}}{\times}A\overset{M_{1}}{\times}\cdots\overset{M_{t}}{\times}A=\begin{pmatrix}A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}&&&A^{Q}\\\ &\ddots&&\vdots\\\ &&A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}&A^{Q}\\\ &&&A^{Q}&A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}\end{pmatrix}$ (2)

for any $t\geq 1$. The idea being that instead of just having a pair of proper
solutions to $A\bm{x}=\bm{b}$, we now have a collection of $t+1$ of them that
all mutually intersect exactly in the variables indexed by $Q$. Specifically,
we get the following result.

######  Lemma 17.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$ be positive and
abundant and $Q=\\{i\\}\subset[m]$ of size $1$, and for any positive integer
$j$ let $M_{j}$ denote the function $jm-j+1\mapsto i$. Then for any positive
integer $t$ it holds that the matrix
$A\overset{\operatorname{id}_{Q}}{\times}A\overset{M_{1}}{\times}\cdots\overset{M_{t}}{\times}A$
is positive and of rank

$\operatorname{rk}\bigl{(}A\overset{\operatorname{id}_{Q}}{\times}A\overset{M_{1}}{\times}\cdots\overset{M_{t}}{\times}A\bigr{)}=\operatorname{rk}(A)+(t+1)\operatorname{rk}(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}).$

###### Proof.

The proof is identical to that of Lemmas 14 and 15, noting that since $A$ is
abundant, for any $Q\subset[m]$ of size $1$ it will hold that
$S(A^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},\bm{0})$ contains a solution with all entries non-zero. ∎

##  3 The distribution of type-$\mathfrak{P}$ solutions: the main meta theorem

We now state our main result (which we call _meta theorem_) that will imply
Theorems 4 and 7.

######  Theorem 18.

Let $m>r$ be positive integers, $A\in\mathbb{Z}^{r\times m}$ a positive and
abundant integer matrix, $\bm{b}\in\mathbb{Z}^{r}$ such that
$S(A,\bm{b})\neq\emptyset$, and $\mathfrak{P}\subset\mathfrak{P}(A)$
satisfying $(\\{1\\},\dots,\\{m\\})\in\mathfrak{P}$ and

$\\{\mathfrak{p}\in\mathfrak{P}:S_{0}(A_{\mathfrak{p}},\bm{b})\neq\emptyset\\}\subset\mathfrak{P}_{0}(A).$

Furthermore, let $n$ be an integer, $0\leq p:=p(n)\leq 1$ and $X_{n}$ the
random variable $|S_{\mathfrak{P}}(A,\bm{b})\cap[n]_{p}^{m}|$ that counts the
number of type–$\mathfrak{P}$ solutions $\bm{x}\in[n]_{p}^{m}$ to
$A\bm{x}=\bm{b}$. Then

$\tilde{X}_{n}\xrightarrow{d}\mathcal{N}(0,1)$

if $n(1-p)\to\infty$ and $np^{c(A_{\mathfrak{p}})}\to\infty$ for all
$\mathfrak{p}\in\mathfrak{P}$ with $S_{\mathfrak{p}}(A,\bm{b})\neq\emptyset$.

Let us first see that this indeed implies Theorems 4 and 7.

###### Proof of Theorem 4.

We apply Theorem 18 with $\mathfrak{P}=\\{(\\{1\\},\dots,\\{m\\})\\}$, noting
that $S_{0}(A,\bm{b})\neq\emptyset$ follows from the assumptions and Lemma 10.
∎

###### Proof of Theorem 7.

We see that for any $\mathfrak{p}\in\mathfrak{P}(A)$, whenever
$S_{0}(A_{\mathfrak{p}},\bm{0})\neq\emptyset$, the matrix $A_{\mathfrak{p}}$
is positive by definition, that is $\mathfrak{p}\in\mathfrak{P}_{0}(A)$. Since
$A$ is strictly balanced, it holds that

$c(A)=\frac{m}{m-\operatorname{rk}(A)}>\max_{\emptyset\subsetneqq
Q\subsetneqq[m]}\frac{|Q|}{|Q|-r_{Q}(A)}>c(A_{\mathfrak{p}})$

for any $\mathfrak{p}\in\mathfrak{P}(A)$ with $|\mathfrak{p}|<m$ and hence
$np^{c(A_{\mathfrak{p}})}\to\infty$. ∎

The proof of Theorem 18 involves the analysis of several sub-cases, which we
will split into different subsections. In general, it will follow the ideas
that were used by Ruciński in [9] where he proved a similar result to Theorem
18 in order to determine the distribution of the number of occurrences of a
fixed graph $G$ as a subgraph in a binomial random graph.

###  3.1 The proof of Theorem 18

Before going into further case analysis, let us first discuss the common
jumping off point and strategy. Let
$\mu_{k}=\operatorname{\mathbb{E}}((X_{n}-\operatorname{\mathbb{E}}(X_{n}))^{k})$
denote the $k$-th central moment of $X_{n}$ associated to the system of linear
equations $A\textbf{x}=\bm{b}$. Our final goal will always be to show that,
independently of the system studied,

$\mu_{k}=\begin{cases}(1+o(1))\frac{k!}{(k/2)!}2^{-k/2}\mu_{2}^{k/2}&\text{ if
$k$ is even,}\\\ o(\mu_{2}^{k/2})&\text{ if $k$ is odd.}\end{cases}$ (3)

These estimates would show that the moments
$\operatorname{\mathbb{E}}(\tilde{X}_{n}^{k})$ converge to the moments of a
normal distribution, which is uniquely determined by its moments.

Given a solution $\bm{x}=(x_{1},\dots,x_{m})$ in $S(A,\bm{b})$, denote by
$\operatorname{\mathbb{I}}_{\bm{x}}$ the indicator random variable for the
event $\\{x_{1},\dots,x_{m}\\}\subset[n]_{p}$. Abusing notation somewhat, if
$\chi=(\bm{x}_{1},\dots,\bm{x}_{k})\in S(A,\bm{b})^{k}$ is a $k$-tuple of
solutions, we will write $\\{\chi\\}=\bigcup_{i=1}^{k}\\{\bm{x_{i}}\\}$. As a
visual shorthand, bold latin letters will indicate solutions, while greek
letters will denote tuples of solutions. Note first that by definition we have

$\mu_{k}=\sum_{\chi\in\mathfrak{S}_{k}}\operatorname{\mathbb{E}}\left(\prod_{\bm{x}\in\chi}\left(\operatorname{\mathbb{I}}_{\bm{x}}-p^{|\\{\bm{x}\\}|}\right)\right),$
(4)

where $\mathfrak{S}_{k}$ is the set containing all $k$-tuples
$\chi={(\bm{x}_{1},\dots,\bm{x}_{k})\in(S_{\mathfrak{P}}(A,\bm{b})\cap[n]^{m})^{k}}$
such that for every $i\in[k]$ there exists a $j\in[k]\setminus\\{i\\}$ such
that $\\{\bm{x}_{i}\\}\cap\\{\bm{x}_{j}\\}\neq\emptyset$. Indeed, for any
$k$-tuple $\chi$ that contains some $\bm{x}\in
S_{\mathfrak{P}}(A,\bm{b})\cap[n]^{m}$ that is disjoint from the remaining
$k-1$ solutions, we have

$\operatorname{\mathbb{E}}\left(\prod_{\bm{y}\in\chi}\left(\operatorname{\mathbb{I}}_{\bm{y}}-p^{|\\{\bm{y}\\}|}\right)\right)=\operatorname{\mathbb{E}}\left(\operatorname{\mathbb{I}}_{\bm{x}}-p^{|\\{\bm{x}\\}|}\right)\operatorname{\mathbb{E}}\Bigg{(}\prod_{\begin{subarray}{c}\bm{y}\in\chi\\\
\bm{y}\neq\bm{x}\end{subarray}}\left(\operatorname{\mathbb{I}}_{\bm{y}}-p^{|\\{\bm{y}\\}|}\right)\Bigg{)}=0.$

Equation (4) behaves slightly different depending on the behavior of $p$, so
suppose $p\to a$ for some constant $a\in[0,1]$. We split the analysis in three
cases, depending on wether this limit belongs to $(0,1)$, is equal to 1 and is
equal to 0.

####  3.1.1 Case 1: $\mathbf{0<a<1}$.

In this case we see that (4) implies
$\mu_{k}=\sum_{\mathfrak{S}_{k}}\Theta(1)$, so we need to analyze the
cardinality of $\mathfrak{S}_{k}$. We are going to prove (3) by induction on
$k$. The base cases $k=2$ and $k=1$ are clearly always true. Our induction
hypothesis tells us then that for any $\ell<k$ it holds that
$\mu_{\ell}=O(\mu_{2}^{\ell/2})$ and hence by our previous observation

$|\mathfrak{S}_{\ell}|=O(|\mathfrak{S}_{2}|^{\ell/2}).$

Let us now study the statement for parameter $k$. The analysis will be
different depending on wether $k$ is odd or even. Let
$\mathfrak{S}_{k}^{\prime}$ denote the subset of $\mathfrak{S}_{k}$ containing
all $k$-tuples of solutions $(\bm{x}_{1},\dots,\bm{x}_{k})$ with
$\bm{x}_{i}\in(S_{\mathfrak{P}}(A,\bm{b})\cap[n]^{m})$ such that for every $i$
the choice of $j\neq i$ with
$\\{\bm{x}_{i}\\}\cap\\{\bm{x}_{j}\\}\neq\emptyset$ is unique, that is, the
solutions can be grouped into $k/2$ pairwise disjoint pairs. Note that
clearly, $\mathfrak{S}_{k}^{\prime}=\emptyset$ for every odd $k$. If
$\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k}^{\prime}=\mathfrak{S}_{k}\setminus\mathfrak{S}_{k}^{\prime}$, we
will show that

$|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k}^{\prime}|=o(|\mathfrak{S}_{2}|^{k/2}),$

which would imply

$\sum_{\chi\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k}^{\prime}}\operatorname{\mathbb{E}}\left(\prod_{\bm{x}\in\chi}\left(\operatorname{\mathbb{I}}_{\bm{x}}-p^{|\\{\bm{x}\\}|}\right)\right)=o(\mu_{2}^{k/2}).$

To see that this is true, suppose
$\chi:=(\bm{x}_{1},\dots,\bm{x}_{k})\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k}^{\prime}$. Then there must exist an index $i=i(\chi)\in[k]$ such
that

$\chi^{[k]\setminus\\{i\\}}=(\bm{x}_{1},\dots,\bm{x}_{i-1},\bm{x}_{i+1},\dots,\bm{x}_{k})$

is contained in $\mathfrak{S}_{k-1}$. Taking the minimum choice of $i$ for
each $\chi$, we have thus defined a map $\pi\colon\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k}^{\prime}\to\mathfrak{S}_{k-1}$, and hence

$|\mathfrak{S}_{k}^{\prime}|\leq\max_{\upsilon\in\mathfrak{S}_{k-1}}|\pi^{-1}(\upsilon)|\cdot|\mathfrak{S}_{k-1}|.$

Since by induction $|\mathfrak{S}_{k-1}|=O(|\mathfrak{S}_{2}|^{(k-1)/2})$, it
suffices to show that

$\max_{\upsilon\in\mathfrak{S}_{k-1}}|\pi^{-1}(\upsilon)|=o(|\mathfrak{S}_{2}|^{1/2}).$

We will first determine a lower bound on $|\mathfrak{S}_{2}|$. It is clear
that
$|\mathfrak{S}_{2}|\geq|S_{0}(A\overset{\operatorname{id}_{Q}}{\times}A,\bm{b}^{2})\cap[n]^{2m-|Q|}|$
for any $Q\subset[m]$. Since $A$ is abundant, any $Q$ containing exactly one
index will satisfy the conditions of Lemma 15, so fix an arbitrary one. It
follows by this and Lemma 10 applied to
$A\overset{\operatorname{id}_{Q}}{\times}A$ that

$|\mathfrak{S}_{2}|\geq|S_{0}(A\overset{\operatorname{id}_{Q}}{\times}A,\bm{b}^{2})\cap[n]^{2m-1}|=\Omega(n^{2m-2\operatorname{rk}(A)-1}).$
(5)

We now turn to giving an upper bound on
$\max_{\upsilon\in\mathfrak{S}_{k-1}}|\pi^{-1}(\upsilon)|$, so fix an
$\upsilon\in\mathfrak{S}_{k-1}$. By definition of $\mathfrak{S}_{k}$, any
solution that could extend $\upsilon$ to a $k$-tuple in $\mathfrak{S}_{k}$
must intersect $\\{\upsilon\\}$, and hence by Lemma 12 we see that

$|\pi^{-1}(\upsilon)|=O(n^{m-\operatorname{rk}(A)-1})=o\left(|\mathfrak{S}_{2}|^{1/2}\right)$

by the previously obtained lower bound (5). Since
$\mathfrak{S}_{k}^{\prime}=\emptyset$ for odd $k$, this also proves the odd
case of (3).

We now turn to the case of even $k$, noting that (3.1.1) tells us that
essentially, the tuples that are summed over in $\mu_{k}$ are $k/2$ pairwise
disjoint pairs of those summed over in $\mu_{2}$. We begin by showing that for
all but a negligible amount, pairs $(\bm{x},\bm{y})\in\mathfrak{S}_{2}$ will
satisfy $\bm{x},\bm{y}\in S_{0}(A,\bm{b})$ and
$|\\{\bm{x}\\}\cap\\{\bm{y}\\}|=1$. Let us first see that we can restrict
ourselves to pairs of proper solutions. This follows from a similar argument
as was used in the proof of Lemma 12. Namely, if we fix an arbitrary
$\bm{x}\in S_{\mathfrak{P}}(A,\bm{b})$, then by (1)

$\big{|}\\{y\in
S_{0}(A_{\mathfrak{p}},\bm{b})\cap[n]^{|\mathfrak{p}|}:\mathfrak{p}\in\mathfrak{P},\,|\mathfrak{p}|<m\\}=O(n^{m-\operatorname{rk}(A)-2}).$

Since there are at most $n^{m-\operatorname{rk}(A)}$ choices for $\bm{x}$,
this is negligible when compared to $|\mathfrak{S}_{2}|$. Applying the second
part of Lemma 12 directly, the number of pairs of proper solutions that
intersect in at least two elements is negligible as well. Note that for any
pair $(\bm{x},\bm{y})$ satisfying the structure described above, we have
$\operatorname{\mathbb{E}}((\operatorname{\mathbb{I}}_{\bm{x}}-p^{\\{\bm{x}\\}})(\operatorname{\mathbb{I}}_{\bm{y}}-p^{\\{\bm{y}\\}}))\sim(a^{2m-1}(1-a))$.

Finally, note that for any pair $\chi\in\mathfrak{S}_{2}$, the number of pairs
$\upsilon\in\mathfrak{S}_{2}$ that share elements with $\chi$ is negligible:
Clearly, any such $\upsilon$ will consist of an $\bm{x}\in S_{0}(A,\bm{b})$
satisfying $\\{\bm{x}\\}\cap\\{\chi\\}\neq\emptyset$ and a $\bm{y}\in
S_{0}(A,\bm{b})$ satisfying $\\{\bm{y}\\}\cap\\{\bm{x}\\}\neq\emptyset$.
Applying Lemma 12 again, the number of such pairs is
$O(n^{2m-2\operatorname{rk}(A)-2})=o(|\mathfrak{S}_{2}|)$. We conclude

$|\mathfrak{S}_{k}|\sim\binom{|\mathfrak{S}_{2}|/2}{k/2}k!$

and hence, as $p$ tends to $a\in(0,1)$,

$\mu_{k}\sim\binom{|\mathfrak{S}_{2}|/2}{k/2}k!(a^{2m-1}(1-a))^{k/2}\sim\frac{k!}{(k/2)!}2^{-k/2}\mu_{2}^{k/2},$

which is what we wanted to prove. $\blacksquare$

####  3.1.2 Case 2: $\mathbf{a=1}$.

Recall that $p$ is chosen such that $n(1-p)$ tends to infinity. This property
will be specially relevant in this case. We will instead look at the
complements, so if $\bm{x}$ is a solution to $A\bm{x}=\bm{b}$, define $q=1-p$
and
$\bar{\operatorname{\mathbb{I}}}_{\bm{x}}=1-\operatorname{\mathbb{I}}_{\bm{x}}$.
We see that
$\nu_{\bm{x}}\vcentcolon=\operatorname{\mathbb{E}}(\bar{\operatorname{\mathbb{I}}}_{\bm{x}})=1-p^{|\\{\bm{x}\\}|}\sim|\\{\bm{x}\\}|q$
when $n$ tends to infinity. Let
$\chi=(\bm{x}_{1},\dots,\bm{x}_{k})\in\mathfrak{S}_{k}$ be a $k$-tuple of
solutions in $S_{\mathfrak{P}}(A,\bm{b})\cap[n]^{m}$. Using these definitions
we see that (4) can be written as

$\mu_{k}=\sum_{\chi\in\mathfrak{S}_{k}}\operatorname{\mathbb{E}}\left(\prod_{\bm{x}\in\chi}(\operatorname{\mathbb{I}}_{\bm{x}}-p^{|\\{\bm{x}\\}|})\right)=(-1)^{k}\sum_{\chi\in\mathfrak{S}_{k}}\operatorname{\mathbb{E}}\left(\prod_{\bm{x}\in\chi}(\bar{\operatorname{\mathbb{I}}}_{\bm{x}}-\nu_{\bm{x}})\right).$
(6)

We associate then a set system $\mathcal{H}=\mathcal{H}(\chi)$ to the
$k$-tuple $\chi$ as follows: the vertex set $V(\mathcal{H})$ is just
$\\{\chi\\}$, while the edges are
$E(\mathcal{H})=\\{\\{\bm{x}\\}:\bm{x}\in\chi\\}$. Suppose the vertex cover
number $\tau(\mathcal{H})$ of the hypergraph is $s$, that is, there exist $s$
elements $a_{1},\dots,a_{s}\in\\{\chi\\}$ such that removing them destroys all
solutions in $\chi$, and no collection of less than $s$ elements in $[n]$
achieves this. Then a straightforward computation shows that

$\operatorname{\mathbb{E}}\left(\prod_{\bm{x}\in\chi}\bar{\operatorname{\mathbb{I}}}_{\bm{x}}\right)=\Theta(q^{s}).$

Furthermore, it is clear that for any $t\in[k-1]$, every $(k-t)$-sub-
collection of $\chi$ will require removal of at least $s-t$ elements to
destroy all solutions in it, that is, for any $I\subset[k]$ with $|I|=k-t$ it
holds that

$\operatorname{\mathbb{E}}\left(\prod_{i\in
I}\bar{\operatorname{\mathbb{I}}}_{\bm{x}_{i}}\prod_{j\notin
I}\nu_{\bm{x}_{j}}\right)=\begin{cases}\Theta(q^{s}),&\text{if
$\chi^{I}\in\mathfrak{S}_{k-t}$,}\\\ 0,&\text{otherwise.}\end{cases}$

Note here, we interpret $\chi$ as a $k$-vector in which every coordinate is
itself an $m$-vector, so $\chi^{I}$ denotes the vector obtained by only
keeping the solutions indexed by $I$. Putting this together, we see that (6)
becomes

$\mu_{k}=\sum_{s=1}^{k}\sum_{\chi\in\mathfrak{S}_{k,s}}\Theta(q^{s}),$ (7)

where $\mathfrak{S}_{k,s}$ is the subset of $k$-tuples
$\chi\in\mathfrak{S}_{k}$ such that $\tau(\mathcal{H}(\chi))=s$. We will now
show that for any fixed $s$, only $\chi$ of a certain structure contribute
significantly to (7). For this, define by $\mathfrak{S}_{k,s}^{\prime}$ the
set of _$s$ -milky ways_, which are $\chi\in\mathfrak{S}_{k,s}$ such that
$\mathcal{H}(\chi)$ is the union of $s$ disjoint components, with all edges in
a component intersecting in a unique vertex. Note that this set is only non-
empty for $s\leq\lfloor k/2\rfloor$. Furthermore, note that each component
corresponds to a matrix as described in (2), call it $B_{i}$, hence by
considering the compounded matrix
$B_{1}\overset{\bm{.}}{\times}\cdots\overset{\bm{.}}{\times}B_{s}$ we see that
Lemma 17 together with Lemma 10 implies that for any $k$ and $s\leq\lfloor
k/2\rfloor$

$|\mathfrak{S}_{k,s}^{\prime}|=\Omega(n^{k(m-\operatorname{rk}(A)-1)+s}).$ (8)

The combination of these two lemmas also gives a matching upper bound: For any
fixed way of dividing up the $k$ solutions into $s$ components, there are at
most $O(n^{k(m-\operatorname{rk}(A)-1)+s})$ corresponding $k$-tuples. Since
$k$ and $s$ are fixed, the number of these partitions is $O(1)$, and hence

$|\mathfrak{S}_{k,s}^{\prime}|=O(n^{k(m-\operatorname{rk}(A)-1)+s}).$ (9)

We will now show by induction on $k$ that for any $k$ and $s$,

$|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime}|\coloneqq|\mathfrak{S}_{k,s}\setminus\mathfrak{S}_{k,s}^{\prime}|=O(n^{k(m-\operatorname{rk}(A)-1)+s-1}).$

This holds trivially for $k=1$, and for $k=2$, it follows immediately from
Lemma 12, since $A$ is abundant and $s=1$ being the only vertex cover number
leading to a non-empty set. So suppose $k\geq 3$ and note that the bound (9)
together with the induction hypothesis in particular implies
$|\mathfrak{S}_{\ell,s}|=O(n^{\ell(m-\operatorname{rk}(A)-1)+s})$ for any
$\ell<k$.

We will split up $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime}_{k,s}$ even further, into disjoint sets $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime\prime}$, $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime\prime\prime}$, and $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime\prime\prime\prime}$, which are defined as follows:

  * a)

The set $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime\prime}$ will contain all
$\chi=(\bm{x}_{1},\dots,\bm{x}_{k})\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime}$ such that there are solutions
$\bm{x}_{i},\bm{x}_{j}\in\chi$ satisfying
$\\{\chi^{[k]\setminus\\{i,j\\}}\\}\cap\\{\chi^{\\{i,j\\}}\\}=\emptyset$, and
$|\\{\bm{x}_{i}\\}\cap\\{\bm{x}_{j}\\}|\geq 2$.

  * b)

The set $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s}$ contains all
$\chi=(\bm{x}_{1},\dots,\bm{x}_{k})\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime}\setminus\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime}_{k,s}$, such that there exists a solution
$\bm{x}_{i}\in\chi$ satisfying
$|\\{\bm{x}\\}\cap\\{\chi^{[k]\setminus\\{i\\}}\\}|\geq 2$ and
$\chi^{[k]\setminus\\{i\\}}\in\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}$.

  * c)

Finally, $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime\prime}_{k,s}=\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime}_{k,s}\setminus(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime}_{k,s}\cup\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s})$ are the remaining non-milky ways.

We proceed to analyze the cardinality of each set.

  * a)

We start with case $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{k,s}^{\prime\prime}$. For every $\chi\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime}_{k,s}$, there are indices $i$ and $j$ such that
$\chi^{[k]\setminus\\{i,j\\}}\in\mathfrak{S}_{k-2,s-1}$, and taking the
lexicographic smallest pair we have defined a map $\pi\colon\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime}_{k,s}\to\mathfrak{S}_{k-2,s-1}$, which implies

$|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime}_{k,s}|\leq|\mathfrak{S}_{k-2,s-1}|\max_{\upsilon\in\mathfrak{S}_{k-2,s-1}}|\pi^{-1}(\upsilon)|=O\left(n^{(k-2)(m-\operatorname{rk}(A)-1)+s-1}\max_{\upsilon\in\mathfrak{S}_{k-1,s}}|\pi^{-1}(\upsilon)|\right).$

Lemmas 10 and 12 imply that for any $\upsilon\in\mathfrak{S}_{k-2,s-1}$ we
have $|\pi^{-1}(\upsilon)|=O(n^{2m-2\operatorname{rk}(A)-2})$, and hence

$|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime}_{k,s}|=O(n^{k(m-\operatorname{rk}(A)-1)+s-1}).$ (10)

  * b)

We continue with the analysis of $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s}$. In this case, taking the smallest possible
index $i$, this again defines a map $\pi\colon\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s}\to\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}$
and we see by induction hypothesis that

$\displaystyle|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s}|$
$\displaystyle\leq|\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}|\max_{\upsilon\in\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}}|\pi^{-1}(\upsilon)|$
$\displaystyle=O\left(n^{(k-1)(m-\operatorname{rk}(A)-1)+s}\max_{\upsilon\in\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}}|\pi^{-1}(\upsilon)|\right).$

Again, for any $\upsilon\in\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}$, we
see that $|\pi^{-1}(\upsilon)|$ is at most the number of solutions $\bm{y}\in
S_{\mathfrak{P}}(A,\bm{b})\cap[n]^{m}$ that contain at least $2$ elements from
$\\{\upsilon\\}$, which is $O(n^{m-\operatorname{rk}(A)-2})$ by Lemma 12, and
hence

$|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s}|=O(n^{k(m-\operatorname{rk}(A)-1)+s-1}).$
(11)

  * c)

Finally, it remains to look at $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime\prime}_{k,s}$. If
$\chi=(\bm{x}_{1},\dots,\bm{x}_{k})$ in $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime\prime}_{k,s}$, we claim that there must exist an
index $i$ such that $\chi^{[k]\setminus\\{i\\}}\in\mathfrak{S}_{k-1,s-1}$. In
the sequel, we will only consider the components of $\mathcal{H}(\chi)$ that
do not intersect in a unique vertex, of which there is at least one since
$\chi\notin\mathfrak{S}^{\prime}_{k,s}$. First note that it is clear that
since $\chi\notin\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime}_{k,s}\cup\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime}_{k,s}$, there must exist an index $i$ such that
$\chi^{[k]\setminus\\{i\\}}\in\mathfrak{S}_{k-1,s-1}\cup\mathfrak{S}_{k-1,s}$
or in other words, the remaining solutions are still intersecting. Since
$\chi\notin\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s}$, for all of these indices, it must hold that
$|\\{\bm{x}_{i}\\}\cap\\{\chi^{[k]\setminus\\{i\\}}\\}|=1$. Finally, for at
least one index $i$ of the previously considered, it must actually hold that
there is a unique $j_{i}$ such that

$\\{\bm{x}_{i}\\}\cap\\{\chi^{[k]\setminus\\{i\\}}\\}=\\{\bm{x}_{i}\\}\cap\\{\bm{x}_{j_{i}}\\}.$
(12)

Indeed, since the components we consider are not sunflowers, there must exist
an $\bm{x}_{\ell}$ that intersects the rest of its component in at least two
points, and so the negation of (12) would imply $\chi\in\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime}_{k,s}$, since $\bm{x}_{\ell}$ would be a valid
choice. We see that for any valid $i$ satisfying (12) it holds that
$\chi^{[k]\setminus\\{i\\}}\in\mathfrak{S}_{k-1,s-1}$. Having established
this, we repeat the arguments already used, taking the minimal valid $i$ and
defining the appropriate function $\pi\colon\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime\prime}_{k,s}\to\mathfrak{S}_{k-1,s-1}$ and conclude

$\displaystyle|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}^{\prime\prime\prime\prime}_{k,s}|$
$\displaystyle\leq|\mathfrak{S}_{k-1,s-1}|\max_{\upsilon\in\mathfrak{S}_{k-1,s-1}}|\pi^{-1}(\upsilon)|$
$\displaystyle=O(n^{(k-1)(m-\operatorname{rk}(A)-1)+s-1})\max_{\upsilon\in\mathfrak{S}_{k-1,s-1}}|\pi^{-1}(\upsilon)|$
$\displaystyle=O(n^{k(m-\operatorname{rk}(A)-1)+s-1}).$

Together with (8), we see that (10), (11) and (12) imply that only $s$-milky
ways contribute meaningfully when $s\leq\lfloor k/2\rfloor$. Sadly, this bound
is not quite strong enough when $s>\lfloor k/2\rfloor$, since $s$-milky ways
do not exist here. For this, we will prove by induction on $k$ that for any
$k$ and $s\geq\lfloor k/2\rfloor$ it holds that

$|\mathfrak{S}_{k,s}|=O(n^{k(m-\operatorname{rk}(A)-1)+\lfloor k/2\rfloor}).$
(13)

Again, the cases $k=1$ and $k=2$ follow from previous observations. Moreover,
the statement is trivially true for any $k$ and $s=\lfloor k/2\rfloor$, so
suppose $k\geq 3$ and $s>\lfloor k/2\rfloor$. If
$\chi=(\bm{x}_{1},\dots,\bm{x_{k}})\in\mathfrak{S}_{k,s}$, then there must
exist a least index $i$ such that
$\chi^{[k]\setminus\\{i\\}}\in\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}$,
which allows us again to define a projection map
$\pi\colon\mathfrak{S}_{k,s}\to\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}$.
Since $s\geq\lfloor k/2\rfloor+1$ we have $s-1\geq\lfloor(k-1)/2\rfloor$, and
hence by induction hypothesis we have

$\displaystyle|\mathfrak{S}_{k,s}|$
$\displaystyle\leq|\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}|\max_{\upsilon\in\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}}|\pi^{-1}(\upsilon)|$
$\displaystyle=O(n^{(k-1)(m-\operatorname{rk}(A)-1)+\lfloor(k-1)/2\rfloor})|\max_{\upsilon\in\mathfrak{S}_{k-1,s}\cup\mathfrak{S}_{k-1,s-1}}|\pi^{-1}(\upsilon)|$
$\displaystyle=O(n^{k(m-\operatorname{rk}(A)-1)+\lfloor(k-1)/2\rfloor}),$

which in particular implies (13). Since $q\to 0$, we thus have

$|\mathfrak{S}_{k,s}|q^{s}=o\bigl{(}|\mathfrak{S}_{k,\lfloor
k/2\rfloor}|q^{\lfloor k/2\rfloor}\bigr{)},$

and so the terms with $s>\lfloor k/2\rfloor$ in (7) can be discarded. Now, if
$\chi\in\mathfrak{S}^{\prime}_{k,s}$ is a milky way, we see that

$\operatorname{\mathbb{E}}\left(\prod_{\bm{x}\in\chi}\bar{\operatorname{\mathbb{I}}}_{\bm{x}}\right)\sim
q^{s},$

while for any $I\in[k]$ with $|I|\leq k-1$ we have

$\operatorname{\mathbb{E}}\left(\prod_{i\in
I}\bar{\operatorname{\mathbb{I}}}_{\bm{x}_{i}}\prod_{j\notin
I}\nu_{\bm{x}_{j}}\right)=O(q^{s+1})=o(q^{s}),$

since the removal of any single solution does not impact the cover number,
while any subsequent removal can reduce it by at most one. Furthermore, by our
previous observations we have already seen that for any $k$ and $s\leq\lfloor
k/2\rfloor$

$|\mathfrak{S}^{\prime}_{k,s}|q^{s}=\Theta(n^{k(m-\operatorname{rk}(A)-1)}(nq)^{s}),$

so since $nq\to\infty$ by assumption only the $s=\lfloor k/2\rfloor$ term
contributes significantly. Hence (7) can be rewritten as

$\mu_{k}\sim\sum_{s=1}^{\lfloor
k/2\rfloor}|\mathfrak{S}^{\prime}_{k,s}|q^{s}\sim|\mathfrak{S}^{\prime}_{k,\lfloor
k/2\rfloor}|q^{\lfloor k/2\rfloor}.$ (14)

This proves (3) for odd $k$, since

$\mu_{k}=O(n^{k(m-\operatorname{rk}(A)-1)}(nq)^{(k-1)/2})=o(n^{k(m-\operatorname{rk}(A)-1)}(nq)^{k/2}),$

while

$\mu_{2}^{k/2}=\Omega(n^{k(m-\operatorname{rk}(A)-1)}(nq)^{k/2}).$

For the even case, it is easy to see that one can repeat the argument from
Case 1 to show that only those milky ways with all solutions being proper
contribute meaningfully and that among those, the number of pairs in
$\mathfrak{S}^{\prime}_{2,1}$ that intersect another pair is negligible, so
just like in that case we conclude

$\mu_{k}\sim\binom{|\mathfrak{S}^{\prime}_{2,1}|/2}{k/2}k!q^{k/2}\sim\frac{k!}{(k/2)!}2^{-k/2}\mu_{2}^{k/2}.$

$\blacksquare$

####  3.1.3 Case 3: $\mathbf{a=0}$.

Finally, in this case the crucial property of $p$ that will be used is the
fact that $np^{c(A_{\mathfrak{p}})}$ tends to infinity for every considered
partition type $\mathfrak{p}\in\mathfrak{P}$ with non-empty solution set.

Let $\chi=(\bm{x}_{1},\dots,\bm{x}_{k})\in\mathfrak{S}_{k}$. Then for any
$I\subsetneqq[k]$ we see that

$\operatorname{\mathbb{E}}\Bigl{(}\prod_{i\in
I}\operatorname{\mathbb{I}}_{\bm{x}_{i}}\prod_{j\in[k]\setminus
I}p^{|\\{\bm{x}_{j}\\}|}\Bigr{)}=p^{\left|\bigcup_{i\in
I}\\{\bm{x}_{i}\\}\right|+\sum_{j\in[k]\setminus
I}|\\{\bm{x}_{j}\\}|}=o\left(p^{\left|\bigcup_{i=1}^{k}\\{\bm{x}_{i}\\}\right|}\right),$

since every $\bm{x}_{j}$ with $j\notin I$ intersects at least one other
solution. Since we clearly have
$\operatorname{\mathbb{E}}(\operatorname{\mathbb{I}}_{\bm{x}_{1}}\cdots\operatorname{\mathbb{I}}_{\bm{x}_{k}})=p^{\left|\bigcup_{i=1}^{k}\\{\bm{x}_{i}\\}\right|}$,
it thus follows that

$\operatorname{\mathbb{E}}\left((\mathbb{I}_{\bm{x}_{1}}-p^{|\\{\bm{x}_{1}\\}|})\cdots(\mathbb{I}_{\bm{x}_{k}}-p^{|\\{\bm{x}_{k}\\}|})\right)\sim
p^{\left|\bigcup_{i=1}^{k}\\{\bm{x}_{i}\\}\right|}.$ (15)

Furthermore, since $np^{c(A_{\mathfrak{p}})}\to\infty$ for any
$\mathfrak{p}\in\mathfrak{P}$, wee see that for any nonempty
$Q\subset[|\mathfrak{p}|]$, it holds that

$n^{|Q|-r_{Q}(A_{\mathfrak{p}})}p^{|Q|}=\omega(1).$

Let us prove (3) via induction on $k$, the cases $k=1$ and $k=2$ clearly being
true. Note that in particular, the induction hypothesis implies that for any
$\ell<k$ it holds that $\mu_{\ell}=O(\mu_{2}^{\ell/2})$. Let us decompose
$\mu_{k}$ as

$\mu_{k}\sim\sum_{\chi\in\mathfrak{S}_{k}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{x}\in\chi}\operatorname{\mathbb{I}}_{\bm{x}}\bigg{)}=\sum_{\chi\in\mathfrak{S}^{\prime}_{k}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{x}\in\chi}\operatorname{\mathbb{I}}_{\bm{x}}\bigg{)}+B_{k}.$

Recall that $\mathfrak{S}^{\prime}_{k}$ denoted the subset of
$\mathfrak{S}_{k}$ such that every $\bm{x}\in\chi$ had a unique partner
$\bm{y}\in\chi$ and was disjoint from all other components. Our first step
will be to show that

$B_{k}=o(\mu_{2}^{k/2}),$

which would in particular imply (3) in the case of odd $k$, since here
$\mathfrak{S}^{\prime}_{k}=\emptyset$. To see this, note that
$\chi=(\bm{x}_{1},\dots,\bm{x}_{k})\in\mathfrak{S}_{k}\setminus\mathfrak{S}^{\prime}_{k}$
implies that there must exist an index $i\in[k]$ such that
$\chi^{[k]\setminus\\{i\\}}\in\mathfrak{S}_{k-1}$. Let $i_{\chi}$ denote the
least index $i\in[k]$ for which this is true, then we can define the map
$\pi\colon\mathfrak{S}_{k}\setminus\mathfrak{S}^{\prime}_{k}\to\mathfrak{S}_{k-1}$
by $\pi(\chi)=\chi^{[k]\setminus\\{i_{\chi}\\}}$. Furthermore, let
$Q_{\chi}\subset[|\mathfrak{p}(\bm{x}_{i_{\chi}})|]$ denote the index set of
all the components of $\bm{x}_{\chi}$ that are contained in $\\{\pi(\chi)\\}$.
Then

$\begin{split}B_{k}&=\sum_{\chi\in\mathfrak{S}_{k}\setminus\mathfrak{S}^{\prime}_{k}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{x}\in\chi}\operatorname{\mathbb{I}}_{\bm{x}}\bigg{)}\\\
&=\sum_{\chi\in\mathfrak{S}_{k}\setminus\mathfrak{S}^{\prime}_{k}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{x}\in\pi(\chi)}\operatorname{\mathbb{I}}_{\bm{x}}\bigg{)}p^{|\mathfrak{p}(\bm{x}_{i_{\chi}})|-|Q_{\chi}|}\\\
&\leq\sum_{\upsilon\in\mathfrak{S}_{k-1}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{y}\in\upsilon}\operatorname{\mathbb{I}}_{\bm{y}}\bigg{)}\sum_{\mathfrak{p}\in\mathfrak{P}}\sum_{Q\subset[|\mathfrak{p}|]}\sum_{\bm{z}\in\\{\upsilon\\}^{|Q|}}p^{|\mathfrak{p}|-|Q|}\big{|}S_{0}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}},b-A_{\mathfrak{p}}^{Q}\bm{z})\cap[n]^{|\mathfrak{p}|-|Q|}\big{|}\\\
&\leq\mu_{k-1}\sum_{\mathfrak{p}\in\mathfrak{P}}\sum_{Q\subset[|\mathfrak{p}|]}n^{|\mathfrak{p}|-|Q|-\operatorname{rk}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}})}p^{|\mathfrak{p}|-|Q|}\\\
&=\mu_{k-1}\sum_{\mathfrak{p}\in\mathfrak{P}}\sum_{Q\subset[|\mathfrak{p}|]}n^{|\mathfrak{p}|-\operatorname{rk}(A)-(|Q|-r_{Q}(A_{\mathfrak{p}}))}p^{|\mathfrak{p}|-|Q|}\end{split}$
(16)

Since $\mu_{k-1}=O(\mu_{2}^{(k-1)/2})$ it thus suffices to show that the
remaining expression in (16) is $o({\mu_{2}}^{1/2})$. But by Lemma 16 there
exists a $Q^{\prime}\supset Q$ such that, using $p\to 0$ we see that

$\displaystyle\mu_{2}$ $\displaystyle\geq
p^{2|\mathfrak{p}|-|Q^{\prime}|}\big{|}S_{0}(A_{\mathfrak{p}}\overset{\operatorname{id}_{Q^{\prime}}}{\times}A_{\mathfrak{p}},(\bm{b},\bm{b}))\cap[n]^{2|\mathfrak{p}|-|Q^{\prime}|}\big{|}$
$\displaystyle\geq
p^{2|\mathfrak{p}|-|Q|}\big{|}S_{0}(A_{\mathfrak{p}}\overset{\operatorname{id}_{Q^{\prime}}}{\times}A_{\mathfrak{p}},(\bm{b},\bm{b}))\cap[n]^{2|\mathfrak{p}|-|Q^{\prime}|}\big{|}$
$\displaystyle=\Omega(n^{2|\mathfrak{p}|-2\operatorname{rk}(A)-(|Q|-r_{Q}(A_{\mathfrak{p}}))}p^{2|\mathfrak{p}|-|Q|}),$

and hence

${\mu_{2}}^{1/2}=\Omega(n^{|\mathfrak{p}|-\operatorname{rk}(A)-(|Q|-r_{Q}(A_{\mathfrak{p}}))/2}p^{|\mathfrak{p}|-|Q|/2})=\omega(n^{|\mathfrak{p}|-\operatorname{rk}(A)-(|Q|-r_{Q}(A_{\mathfrak{p}}))}p^{|\mathfrak{p}|-|Q|})$

which follows from (3.1.3). As stated before, this finishes the proof in the
case of odd $k$, so suppose $k$ is even. If
$\mathfrak{p},\mathfrak{q}\in\mathfrak{P}$ and $M\colon P\to Q$ is a bijection
between nonempty $P\subset[|\mathfrak{p}|]$ and $Q\subset[|\mathfrak{q}|]$, we
will call the triple $(\mathfrak{p},\mathfrak{q},M)$ _leading_ if

$p^{|\mathfrak{p}|+|\mathfrak{q}|-|P|}\big{|}S_{0}(A_{\mathfrak{p}}\overset{M}{\times}A_{\mathfrak{q}},(\bm{b},\bm{b}))\cap[n]^{|\mathfrak{p}|+|\mathfrak{q}|-|P|}\big{|}=\Omega(\mu_{2}),$

and hence

$\mu_{2}\sim\sum_{\begin{subarray}{c}(\mathfrak{p},\mathfrak{q},M)\\\
\text{leading}\end{subarray}}p^{|\mathfrak{p}|+|\mathfrak{q}|-|\operatorname{dom}(M)|}\big{|}S_{0}(A_{\mathfrak{p}}\overset{M}{\times}A_{\mathfrak{q}},(\bm{b},\bm{b}))\cap[n]^{|\mathfrak{p}|+|\mathfrak{q}|-|\operatorname{dom}(M)|}\big{|}.$

Let us first make an observation that will be helpful later. Suppose
$|\mathfrak{p}|\geq|\mathfrak{q}|$, and let $M\colon P\to Q$ be a bijection
between some index sets $P\subset[|\mathfrak{p}|]$ and
$Q\subset[|\mathfrak{q}|]$. Then by Lemma 16 there exists a $P^{\prime}\supset
P$ such that using $np\to\infty$ and $p\to 0$ we see

$\begin{split}\mu_{2}&=\Omega\left(p^{2|\mathfrak{p}|-|P^{\prime}|}\big{|}S_{0}\big{(}A_{\mathfrak{p}}\overset{\operatorname{id}_{P^{\prime}}}{\times}A_{\mathfrak{p}},(\bm{b},\bm{b})\big{)}\cap[n]^{2|\mathfrak{p}|-|P^{\prime}|}\big{|}\right)\\\
&=\Omega\left(p^{2|\mathfrak{p}|-|P|}\big{|}S_{0}\big{(}A_{\mathfrak{p}}\overset{\operatorname{id}_{P^{\prime}}}{\times}A_{\mathfrak{p}},(\bm{b},\bm{b})\big{)}\cap[n]^{2|\mathfrak{p}|-|P^{\prime}|}\big{|}\right)\\\
&=\Omega\left(n^{2|\mathfrak{p}|-2\operatorname{rk}(A)-(|P|-r_{P}(A_{\mathfrak{p}}))}p^{2|\mathfrak{p}|-|P|}\right)\\\
&=\Omega\left(n^{|\mathfrak{p}|+|\mathfrak{q}|-2\operatorname{rk}(A)-(|P|-r_{P}(A_{\mathfrak{p}}))}p^{|\mathfrak{p}|+|\mathfrak{q}|-|P|}\right)\\\
&=\Omega\left(p^{|\mathfrak{p}|+|\mathfrak{q}|-|P|}\big{|}S_{0}\big{(}A_{\mathfrak{p}}\overset{M}{\times}A_{\mathfrak{q}},(\bm{b},\bm{b})\big{)}\cap[n]^{2|\mathfrak{p}|-|P|}\big{|}\right).\end{split}$
(17)

Here the last line followed from the fact that
$\operatorname{rk}(A_{\mathfrak{p}}\overset{M}{\times}A_{\mathfrak{q}})\geq\operatorname{rk}(A_{\mathfrak{q}})+\operatorname{rk}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{P}})=2\operatorname{rk}(A)-r_{P}(A_{\mathfrak{p}})$. Hence,
$(\mathfrak{p},\mathfrak{q},M)$ can be a leading overlap only if

  1. i)

$|\mathfrak{p}|=|\mathfrak{q}|$,

  2. ii)

$r_{P}(A_{\mathfrak{p}})=r_{Q}(A_{\mathfrak{q}})$,

  3. iii)

$\operatorname{rk}(A_{\mathfrak{p}}\overset{M}{\times}A_{\mathfrak{q}})=2\operatorname{rk}(A)-r_{P}(A_{\mathfrak{p}})$,

  4. iv)

For any matrix
$C\in\left\\{A_{\mathfrak{p}}\overset{\operatorname{id}_{P}}{\times}A_{\mathfrak{p}},A_{\mathfrak{q}}\overset{\operatorname{id}_{Q}}{\times}A_{\mathfrak{q}},A_{\mathfrak{p}}\overset{M}{\times}A_{\mathfrak{q}}\right\\}$
it holds that

$|S_{0}(C\cap[n]^{2|\mathfrak{p}|-|P|})|=\Theta(n^{2|\mathfrak{p}|-(|P|-r_{P}(A_{\mathfrak{p}}))}),$

and

  5. v)

$(\mathfrak{p},\mathfrak{p},\operatorname{id}_{P})$ and
$(\mathfrak{q},\mathfrak{q},\operatorname{id}_{Q})$ are leading overlaps,

since otherwise some of the $\Omega$ terms in Equation (17) would turn into
’$\omega$’ terms. Note that these things in particular imply that there cannot
exist any $P^{\prime}\supsetneqq P$ satisfying

$|S_{0}(A_{\mathfrak{p}}\overset{\operatorname{id}_{P^{\prime}}}{\times}A_{\mathfrak{p}},\bm{b}^{2})\cap[n]^{2|\mathfrak{p}|-|P^{\prime}|})|=\Omega(n^{2|\mathfrak{p}|-(|P|-r_{P}(A_{\mathfrak{p}}))}),$

since $p\to 0$ would then imply that
$(\mathfrak{p},\mathfrak{p},\operatorname{id}_{P})$ is not a leading triple.
By the proof of Lemma 16 this means that there does not exist any index
$i\in[|\mathfrak{p}|]$ such that $x_{i}=0$ for every solution $\bm{x}\in
S(A_{\mathfrak{p}},\bm{0})$. Before continuing, let us quickly try to
understand the preceding statements. Essentially, one would naively hope that
all leading triples are of the form
$(\mathfrak{p},\mathfrak{p},\operatorname{id}_{P})$ for some
$P\subset[|\mathfrak{p}|]$, but this is too optimistic because it ignores the
inherent symmetry of some systems of linear equations. For instance, it is
clear that for $A=\begin{pmatrix}1&1&1&-1\end{pmatrix}$, the partitions
$\mathfrak{p}=(\\{1,2\\},\\{3\\},\\{4\\})$ and
$\mathfrak{q}=(\\{1,3\\},\\{2\\},\\{4\\})$ are technically different, but
essentially the same in the sense that there exists a bijection between
$S_{0}(A_{\mathfrak{p}},\bm{b})$ and $S_{0}(A_{\mathfrak{q}},\bm{b})$.

We can now continue with the actual proof by defining
$\mathfrak{S}^{\prime\prime}_{k}\subset\mathfrak{S}^{\prime}_{k}$ to be the
set of $k$-tuples $\chi=(\bm{x}_{1},\dots,\bm{x}_{k})$ such that whenever
$1\leq i<j\leq k$ and $|\\{\bm{x}_{i}\\}\cap\\{\bm{x}_{j}\\}|=s>0$, it holds
that $(\mathfrak{p}(\bm{x}_{i}),\mathfrak{p}(\bm{x}_{j}),M_{i,j})$ is a
leading triple. Here $M_{i,j}$ is the bijection defining the incidences
between the distinct components of $\bm{x}_{i}$ and $\bm{x}_{j}$. We will show
that

$\sum_{\chi\in\mathfrak{S}^{\prime}_{k}\setminus\mathfrak{S}^{\prime\prime}_{k}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{x}\in\chi}\operatorname{\mathbb{I}}_{\bm{x}}\bigg{)}=o(\mu_{2}^{k/2}).$

To see this, we will again define a map
$\pi\colon\mathfrak{S}^{\prime}_{k}\setminus\mathfrak{S}^{\prime\prime}_{k}\to\mathfrak{S}^{\prime}_{k-2}$
in the following way. Among all $1\leq i<j\leq k$ such that
$(\mathfrak{p}(\bm{x}_{i}),\mathfrak{p}(\bm{x}_{j}),M_{i,j})$ is not a leading
triple, let $\\{i_{\chi},j_{\chi}\\}$ be the set minimizing $\min\\{i,j\\}$.
Then we can define $\pi(\chi)=\chi^{[k]\setminus\\{i_{\chi},j_{\chi}\\}}$ and
see that

$\displaystyle\sum_{\chi\in\mathfrak{S}^{\prime}_{k}\setminus\mathfrak{S}^{\prime\prime}_{k}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{x}\in\chi}\operatorname{\mathbb{I}}_{\bm{x}}\bigg{)}$
$\displaystyle=\sum_{\chi\in\mathfrak{S}^{\prime}_{k}\setminus\mathfrak{S}^{\prime\prime}_{k}}\operatorname{\mathbb{E}}\bigg{(}\prod_{\bm{x}\in\pi(\chi)}\operatorname{\mathbb{I}}_{\bm{x}}\bigg{)}p^{|\mathfrak{p}(\bm{x}_{i_{\chi}})|+|\mathfrak{p}(\bm{x}_{j_{\chi}})|-|\operatorname{dom}(M_{i_{\chi},j_{\chi}})|}$
$\displaystyle\leq\mu_{k-2}\sum_{\begin{subarray}{c}(\mathfrak{p},\mathfrak{q},M)\\\
\text{not
leading}\end{subarray}}p^{|\mathfrak{p}|+|\mathfrak{q}|-|\operatorname{dom}(M)|}\big{|}S_{0}(A_{\mathfrak{p}}\overset{M}{\times}A_{\mathfrak{q}},(\bm{b},\bm{b}))\cap[n]^{|\mathfrak{p}|+|\mathfrak{q}|-|\operatorname{dom}(M)|}\big{|}$
$\displaystyle=o(\mu_{2}^{k/2}),$

the last line following from the induction hypothesis
$\mu_{k-2}=O(\mu_{2}^{(k-2)/2})$ and the definition of leading triples, noting
that there are only $O(1)$ choices for $\mathfrak{p}$, $\mathfrak{q}$ and $M$.
Let us enumerate the set of leading triples by
$(\mathfrak{p}_{1},\mathfrak{q}_{1},M_{1}),\dots,(\mathfrak{p}_{u},\mathfrak{q}_{u},M_{u})$,
and for any choice of $0\leq i_{1},\dots,i_{u}\leq k/2$ such that $\sum
i_{j}=k/2$, define the matrix $A(i_{1},\dots,i_{u})$ by

$\displaystyle A(i_{1},\dots,i_{u})$
$\displaystyle=\underbrace{(A_{\mathfrak{p}_{1}}\overset{M_{1}}{\times}A_{\mathfrak{q}_{1}})\overset{\bm{.}}{\times}\cdots\overset{\bm{.}}{\times}(A_{\mathfrak{p}_{1}}\overset{M_{1}}{\times}A_{\mathfrak{q}_{1}})}_{\text{$i_{1}$
times}}\overset{\bm{.}}{\times}\cdots\overset{\bm{.}}{\times}\underbrace{(A_{\mathfrak{p}_{u}}\overset{M_{u}}{\times}A_{\mathfrak{q}_{u}})\overset{\bm{.}}{\times}\cdots\overset{\bm{.}}{\times}(A_{\mathfrak{p}_{u}}\overset{M_{u}}{\times}A_{\mathfrak{q}_{u}})}_{\text{$i_{u}$
times}},$

and write $\ell_{j}$ for the expression
$|\mathfrak{p}_{j}|+|\mathfrak{q}_{j}|-|\operatorname{dom}(M_{j})|$. We also
need the following result.

######  Claim.

For any integers $0\leq i_{1},\dots,i_{u}\leq k/2$ satisfying $\sum i_{j}=k/2$
it holds that

$|S_{0}(A(i_{1},\dots,i_{u}),\bm{b}^{k})\cap[n]^{i_{1}\ell_{1}+\dots+i_{u}\ell_{u}}|\sim\prod_{j\in[u]}|S_{0}(A_{\mathfrak{p}_{j}}\overset{M_{j}}{\times}A_{\mathfrak{q}_{j}},\bm{b}^{2})\cap[n]^{\ell_{j}}|^{i_{j}}.$

###### Proof of the claim:.

Let $(\mathfrak{p},\mathfrak{q},M)$ be a leading triple with
$P:=\operatorname{dom}(M)$. We will first show that
$A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{P}}$
does not contain any column $c_{i}$ such that

$\operatorname{rk}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{P}\smallsetminus\\{i\\}})=\operatorname{rk}(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{P}})-1.$

But this follows since for any such hypothetical column, every solution
$\bm{x}\in S(A_{\mathfrak{p}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{P}},\bm{0})$ would satisfy $x_{i}=0$, and we have seen before that this
cannot happen for any leading triple. We are now able to prove the claim.
Consider any $k/2$-tuple $\chi$ of solutions in
$\bigtimes_{j=1}^{u}\bigl{(}S_{0}(A_{\mathfrak{p}_{j}}\overset{M_{j}}{\times}A_{\mathfrak{q}_{j}},\bm{b}^{2})\cap[n]^{\ell_{j}}\bigr{)}^{i_{j}},$
of which there are
$\prod_{j\in[u]}|S_{0}(A_{\mathfrak{p}_{j}}\overset{M_{j}}{\times}A_{\mathfrak{q}_{j}},\bm{b}^{2})\cap[n]^{\ell_{j}}|^{i_{j}}$
many. When these solutions are all pairwise disjoint, they in fact define a
solution in
$S_{0}(A(i_{1},\dots,i_{u}),\bm{b}^{k})\cap[n]^{\ell_{1}i_{1}+\dots+\ell_{u}i_{u}}$.
Otherwise, there exist indices $s,t\in[u]$ and a bijection $M\colon P\to Q$
with $\emptyset\neq P\subset[\ell_{s}]$ and $\emptyset\neq Q\subset[\ell_{t}]$
such that some pair $\bm{x},\bm{y}\in\chi$ defines a solution in
$S_{0}\bigl{(}(A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}})\overset{M}{\times}(A_{\mathfrak{p}_{t}}\overset{M_{t}}{\times}A_{\mathfrak{q}_{t}}),\bm{b}^{4}\bigr{)}\cap[n]^{\ell_{s}+\ell_{t}-|P|}$.
But if we define $Q_{1}=Q\cap[|\mathfrak{p}_{t}|]$ and
$Q_{2}=Q\cap[\ell_{t}]\setminus[|\mathfrak{p}_{t}|]$, we see that

$\displaystyle\operatorname{rk}\bigl{(}(A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}})\overset{M}{\times}(A_{\mathfrak{p}_{t}}\overset{M_{t}}{\times}A_{\mathfrak{q}_{t}})\bigr{)}$
$\displaystyle\geq\operatorname{rk}\bigl{(}A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}}\bigr{)}+\operatorname{rk}\bigl{(}(A_{\mathfrak{p}_{t}}\overset{M_{t}}{\times}A_{\mathfrak{q}_{t}})^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}}\bigr{)}$
$\displaystyle\geq\operatorname{rk}\bigl{(}A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}}\bigr{)}+\operatorname{rk}(A_{\mathfrak{p}_{t}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{Q}_{1}})+\operatorname{rk}(A_{\mathfrak{q}_{t}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}\setminus Q_{2}})$
$\displaystyle\geq\operatorname{rk}\bigl{(}A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}}\bigr{)}+\operatorname{rk}(A_{\mathfrak{p}_{t}})-|Q_{1}|+1+\operatorname{rk}{A_{\mathfrak{q}_{t}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}}-|Q_{2}|+1$
$\displaystyle=\operatorname{rk}\bigl{(}A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}}\bigr{)}+2\operatorname{rk}(A)-|Q|+2-r_{\operatorname{im}(M_{t})}(A_{\mathfrak{q}_{t}}).$

Here, for the third inequality we have used the previously established fact
that removing any one column from $A_{\mathfrak{q}_{t}}^{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}}$
will not reduce the rank. The same clearly holds for $A_{\mathfrak{p}_{t}}$
since this matrix is positive.

We are almost done, since now we can use the upper bound from Lemma 10 and see
that

$\displaystyle\bigl{|}S_{0}\bigl{(}(A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}})\overset{M}{\times}(A_{\mathfrak{p}_{t}}\overset{M_{t}}{\times}A_{\mathfrak{q}_{t}}),\bm{b}^{4}\bigr{)}\cap[n]^{\ell_{s}+\ell_{t}-|P|}\bigr{|}$
$\displaystyle\leq{}$ $\displaystyle
n^{\ell_{s}+\ell_{t}-|Q|-\operatorname{rk}\bigl{(}(A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}})\overset{M}{\times}(A_{\mathfrak{p}_{t}}\overset{M_{t}}{\times}A_{\mathfrak{q}_{t}})\bigr{)}}$
$\displaystyle\leq{}$ $\displaystyle
n^{\ell_{s}+\ell_{t}-\operatorname{rk}(A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}})-2\operatorname{rk}(A)+r_{\operatorname{im}(M_{t})}(A_{\mathfrak{q}_{t}})}$
$\displaystyle={}$ $\displaystyle
o\bigl{(}|S_{0}(A_{\mathfrak{p}_{s}}\overset{M_{s}}{\times}A_{\mathfrak{q}_{s}},\bm{b}^{2})\cap[n]^{\ell_{s}}|\cdot|S_{0}(A_{\mathfrak{p}_{t}}\overset{M_{t}}{\times}A_{\mathfrak{q}_{t}},\bm{b}^{2})\cap[n]^{\ell_{t}}|\bigr{)},$

the last line following from the observations made from (17). Since there are
only $O(1)$ many choices for $s$, $t$, and $M$, this proves the claim. ∎

Using the claim, we can now conclude

$\displaystyle\mu_{k}$
$\displaystyle\sim\frac{k!}{2^{k/2}}\sum_{\begin{subarray}{c}i_{1},\dots,i_{u}\\\
i_{1}+\dots+i_{u}=k/2\end{subarray}}\frac{1}{i_{1}!\cdots
i_{u}!}p^{i_{1}\ell_{1}+\dots+i_{u}\ell_{u}}|S_{0}(A(i_{1},\dots,i_{u}),\bm{b}^{k})\cap[n]^{i_{1}\ell_{1}+\dots+i_{u}\ell_{u}}|$
$\displaystyle\sim\frac{k!}{(k/2)!2^{k/2}}\sum_{\begin{subarray}{c}i_{1},\dots,i_{u}\\\
i_{1}+\dots+i_{u}=k/2\end{subarray}}\binom{k/2}{i_{1},\dots,i_{u}}\prod_{j\in[u]}\bigl{(}p^{\ell_{j}}|S_{0}(A_{\mathfrak{p}_{j}}\overset{M_{j}}{\times}A_{\mathfrak{q}_{j}},\bm{b}^{2})\cap[n]^{\ell_{j}}|\bigr{)}^{i_{j}}$
$\displaystyle\sim\frac{k!}{(k/2)!\,2^{k/2}}\mu_{2}^{k/2},$

which is what we wanted to prove. $\blacksquare$

##  4 Concluding remarks

In this paper we have established sufficient conditions for the choice of $p$
in order to guarantee normal limiting distributions for the number of
solutions to linear systems of equations of the form $A\bm{x}=\bm{b}$.
Specifically, we showed that $n(1-p)\rightarrow\infty$ and
$np^{c(A_{\mathfrak{p}})}\rightarrow\infty$ (for all partitions under
consideration) sufficed, and we used them in their full strength in Cases 2
and 3, respectively of the proof of Theorem 18. Both of these conditions are
analogous to those that appear in Ruciński’s proof of normality for the number
of copies of a given subgraph $H$ in the binomial random model $G(n,p)$. Note
that when comparing to the graph setting, the elements of $[n]$ in systems
take on the function of both vertices and edges, and hence the analogue of our
$n(1-p)\rightarrow\infty$ requirement is to ask that $n^{2}(1-p)$, the
expected number of edges, is unbounded.

In fact, in [9] Ruciński showed that those conditions were necessary as well
as sufficient. In our context we can say something similar regarding the
condition that $n(1-p)$ is unbounded. Observe that the expression $n(1-p)$ can
be interpreted as the expected number of elements that are _not_ chosen in
$[n]_{p}$, hence if $n(1-p)\not\rightarrow\infty$, then $[n]_{p}$ is typically
all the interval $[n]$ with the exception of a bounded number of elements.
Then it is easy to show that under this condition, $X_{n}$ is strongly
concentrated around its mean value, concluding that
$\tilde{X}_{n}\xrightarrow{d}0$, and hence, we de not have a normal limiting
distribution for the number of solutions.

However, the argument used by Ruciński in order to study the second condition
requires a delicate study of moments of order $4$ and $6$, which we are unable
to adapt. Roughly speaking, in our algebraic setting the structure of
solutions is more complicated compared with the graph setting, as solutions
with repeated components can be valid ones (the analogy would be to consider
also subgraphs of the fixed graph $H$ that we want to count the corresponding
number of subcopies). Hence, an open question arising from our work is to
obtain an _only if_ statement of Theorem 18. As an intermediate step, one
could investigate the two main corollaries of our meta theorem, Theorems 4 and
7, and in fact, the following arguments suggest that the sufficient conditions
on $p$ stated in these theorems are also necessary.

Let us start with the setting of Theorem 7, that of non-trivial solutions in
strictly balanced homogeneous systems of linear equations. Here, as discussed
before, Rué, Spiegel and Zumalacárregui in [11] already established a
threshold result showing that when $np^{c(A)}=o(1)$, asymptotically almost
surely $S_{1}(A,\mathbf{0})\cap[n]^{m}_{p}$ is empty. Using a concentration
argument similar to the one above when discussing the necessity of
$n(1-p)\to\infty$, we see that in this case
$|S_{1}(A,\mathbf{0})\cap[n]^{m}_{p}|$ will converge in distribution to the
constant $0$ distribution. In addition to this threshold results, the authors
also studied the distribution at the threshold, that is, the case
$np^{c(A)}\to a>0$ where $a$ is a constant. Their results show that here, the
random variable $|S_{1}(A,\mathbf{0})\cap[n]^{m}_{p}|$ converges in
distribution to a Poisson. Putting all of this together, we see that this
establishes the only if direction for Theorem 7.

Let us now turn to the setting of Theorem 4, that of proper solutions, where
there are no repeated variables by definition. The argument that
$np^{c(A)}=o(1)$ implies that $\tilde{X}_{n}\xrightarrow{d}0$ is the same as
before, so what remains is to understand the case when $np^{c(A)}$ tends to
some positive constant. When $A$ is strictly balanced, one can use the same
arguments that were used by Rué, Spiegel and Zumalacárregui in the proof of
the strictly balanced homogeneous case for the distribution of non-trivial
solutions to see that one will also have a Poisson distribution in the setting
of Theorem 4. When $A$ is not strictly balanced, an analysis as was performed
by Ruciński in the subgraph setting is needed, but since we are now in the
situation that all variables are pairwise distinct, the same result should
follow, which would establish the necessity of $np^{c(A)}\to\infty$.

To conclude, let us mention that once one has proved a normal limiting
distribution, a natural next question is the study local limit theorems as
well as anti-concentration results and tail estimates in a general context.
This has been a very active trend of research in the last years, see for
instance [18, 3].

## Acknowledgments

We thank Oriol Serra for a preliminary reading of this manuscript, as well as
suggestions and improvements in the presentation of the results. We also
thanks the anonymous referees of the paper, whose suggestions had improved the
final presentation of the paper.

This research was conducted while Maximilian Wötzel was a member of the
Barcelona Graduate School of Mathematics (BGSMath) as well as the Universitat
Politècnica de Catalunya. Maximilian Wötzel acknowledges financial support
from the Fondo Social Europeo and the Agencia Estatal de Investigación through
the FPI grant number MDM-2014-0445-16-2 and the Spanish Ministry of Economy
and Competitiveness, through the María de Maeztu Programme for Units of
Excellence in R&D (MDM-2014-0445), through the project MTM2017-82166-P, as
well as from the Dutch Science Council (NWO) through the grant number
OCENW.M20.009.

Juanjo Rué acknowledges financial support from Spanish State Research Agency
through projects MTM2017-82166-P, PID2020-113082GB-I00, the Severo Ochoa and
María de Maeztu Program for Centers and Units of Excellence in R&D
(CEX2020-001084-M), and the Marie Curie RISE research network ’RandNet’ MSCA-
RISE-2020-101007705.

## References

  * [1] József Balogh, Robert Morris, and Wojciech Samotij, _Independent sets in hypergraphs_ , J. Amer. Math. Soc. 28 (2015), no. 3, 669–709.
  * [2] Yacine Barhoumi-Andréani, Christoph Koch, and Hong Liu, _Bivariate fluctuations for the number of arithmetic progressions in random sets_ , Electron. J. Probab. 24 (2019), 32 (English), Id/No 145\.
  * [3] Ross Berkowitz, Ashwin Sah, and Mehtaab Sawhney, _Number of arithmetic progressions in dense random subsets of $\mathbb{Z}/n\mathbb{Z}$_, Isr. J. Math. 244 (2021), no. 2, 589–620 (English).
  * [4] D. Conlon and W. T. Gowers, _Combinatorial theorems in sparse random sets_ , Ann. Math. (2) 184 (2016), no. 2, 367–454 (English).
  * [5] Peter Frankl, Ronald L. Graham, and Vojtěch Rödl, _Quantitative theorems for regular systems of equations_ , J. Comb. Theory, Ser. A 47 (1988), no. 2, 246–261 (English).
  * [6] Robert Hancock, Katherine Staden, and Andrew Treglown, _Independent sets in hypergraphs and Ramsey properties of graphs and the integers_ , SIAM J. Discrete Math. 33 (2019), no. 1, 153–188 (English).
  * [7] Yoshiharu Kohayakawa, Tomasz Łuczak, and Vojtěch Rödl, _Arithmetic progressions of length three in subsets of a random set_ , Acta Arith. 75 (1996), no. 2, 133–163 (English).
  * [8] Klaus F. Roth, _On certain sets of integers_ , J. Lond. Math. Soc. 28 (1953), 104–109 (English).
  * [9] Andrzej Ruciński, _When are small subgraphs of a random graph normally distributed?_ , Probab. Theory Related Fields 78 (1988), no. 1, 1–10.
  * [10] Juanjo Rué, Oriol Serra, and Lluis Vena, _Counting configuration-free sets in groups_ , European J. Combin. 66 (2017), 281–307.
  * [11] Juanjo Rué, Christoph Spiegel, and Ana Zumalacárregui, _Threshold functions and Poisson convergence for systems of equations in random sets_ , Math. Z. 288 (2018), no. 1-2, 333–360.
  * [12] Imre Z. Ruzsa, _Solving a linear equation in a set of integers. I_ , Acta Arith. 65 (1993), no. 3, 259–282.
  * [13] David Saxton and Andrew Thomason, _Hypergraph containers_ , Invent. Math. 201 (2015), no. 3, 925–992.
  * [14] Mathias Schacht, _Extremal results for random discrete structures_ , Ann. of Math. (2) 184 (2016), no. 2, 333–365.
  * [15] Christoph Spiegel, _A note on sparse supersaturation and extremal results for linear homogeneous systems_ , Electron. J. Comb. 24 (2017), no. 3, research paper p3.38, 19 (English).
  * [16] Christoph Spiegel, _Additive structures and randomness in combinatorics_ , Ph.D. thesis, Universitat Politècnica de Catalunya, 2020, Available at http://hdl.handle.net/2117/328203.
  * [17] Endre Szemerédi, _On sets of integers containing no $k$ elements in arithmetic progression_, Acta Arith. 27 (1975), 199–245.
  * [18] Lutz Warnke, _Upper tails for arithmetic progressions in random subsets_ , Israel J. Math. 221 (2017), no. 1, 317–365.