alex

# Minimizing the alphabet size in codes with restricted error sets

Mira Gonen, Michael Langberg, Alex Sprintson  Mira Gonen is with the
Department of Computer Science, Ariel University, Ariel 40700, Israel (e-mail:
mirag@ariel.ac.il).Michael Langberg is with the Department of Electrical
Engineering, University at Buffalo (State University of New-York), Buffalo, NY
14260, USA (e-mail: mikel@buffalo.edu). Work supported in part by NSF grant
1909451.Alex Sprintson is with the Department of Electrical and Computer
Engineering, Texas A&M University, College Station, TX 77843-3128, USA
(e-mail: spalex@tamu.edu).

###### Abstract

This paper focuses on error-correcting codes that can handle a predefined set
of specific error patterns. The need for such codes arises in many settings of
practical interest, including wireless communication and flash memory systems.
In many such settings, a smaller field size is achievable than that offered by
MDS and other standard codes. We establish a connection between the minimum
alphabet size for this generalized setting and the combinatorial properties of
a hypergraph that represents the prespecified collection of error patterns. We
also show a connection between error and erasure correcting codes in this
specialized setting. This allows us to establish bounds on the minimum
alphabet size and show an advantage of non-linear codes over linear codes in a
generalized setting. We also consider a variation of the problem which allows
a small probability of decoding error and relate it to an approximate version
of hypergraph coloring.

##  I Introduction

In many practical settings, there is a need to design error-correcting codes
that can handle specific error patterns. For example, in wireless
communications, magnetic recording, flash memory systems, and Dynamic Random-
Access Memories (DRAMs) the errors can appear in correlated locations such as
bursts, single-row errors, or crisscrosss errors, e.g., [1, 2, 3, 4, 5, 6].
These settings benefit from customized error correcting codes, that may
improve on the best known parameters of standard error correcting codes. For
example, the optimal error-correcting capabilities of the classical $(n,k)$
Maximum Distance Separable (MDS) code, such as the Reed-Solomon code, come at
the price of a significant alphabet size of $q\geq n-k+1$, [7].111The minimum
alphabet size of an $(n,k)$ MDS code is unknown, see Conjectures 1 and 2 in
the paper. As we show in this paper, in many settings with specific error
patters, a much smaller alphabet size is needed.

In this work, we present a general framework for code design that can handle
any possible collection of predefined error patterns. Our framework applies to
both linear and non-linear codes. For an error-correcting code of length $n$,
we use an $n$-vertex hypergraph $G$ to represent the given collection of error
sets. Specifically, nodes of $G$ represent the coordinates (symbols) of the
codewords, while the hyperedges of $G$ represent possible locations for
errors, i.e., each hyperedge $e$ represents the set of coordinates that can be
corrupted in the specific scenario represented by $e$. For each collection of
error sets represented by $G$, we are interested in finding the minimum
alphabet size over which there exists a code that can correct all error sets
specified by edges in $G$. In our setting, $(n,k)$-MDS codes can correct error
patterns corresponding to the complete $(n-k)/2$-uniform $n$-vertex
hypergraph.

In this work, we relate the minimum alphabet size of error-correcting codes
with predefined error patterns to certain variants of hypergraph coloring.
Through reductive arguments to erasure codes, and in particular to our prior
work [8] in the context of erasure codes with generalized decoding sets, we
propose code design for the error setting at hand, and show that non-linear
error-correcting codes outperform linear ones. We then turn to study a
variation of the problem which allows a small probability of decoding error
and relate it to an approximate version of hypergraph coloring.

Our work is structured as follows. In Section II, we give some preliminaries
and, in particular, we introduce our model for generalized erasure and error
patterns. We also review our previous study on erasure codes in the
generalized setting of a predefined collection of decoding sets [8]. In
Section III, we present bounds on the minimum alphabet size of the
corresponding codes through hypergraph coloring. In Section IV, we reduce the
error-correcting setting to the erasure setting. In Section V, we extend our
studies to the problem of error detection. Finally, in Section VI, we relax
the zero-error requirement for decoding a correct message and analyze settings
which allow small $\varepsilon>0$ probability of decoding error.

##  II Model and Preliminaries

Since our paper makes a connection between erasure and error correction in a
generalized setting, we present definitions for both scenarios. We begin by
presenting a definition and our prior results for erasure correction
scenarios.

###  II-A Erasure Correction with predefined decoding sets.

We start by studying the design of erasure-codes in a generalized setting in
which decoding is required from a collection of predefined decoding sets. In
this setting, the decoding sets include the set of coordinates that can be
used to decode the message. The setting is represented by a hypergraph
$G=([n],E)$, with the set $[n]=\\{1,\dots,n\\}$ of nodes representing
coordinates and set of hyperedges $E$ representing decoding sets.

We define the $q_{k}$ parameter of a given hypergraph $G=([n],E)$ as the
minimum alphabet size of a $(n,k)$ erasure code that enables the receiver to
decode the original message from every subset $e\in E$.

######  Definition 1 (The $q_{k}$ parameter [8])

Let $G=([n],E)$ be a hypergraph on the vertex set $[n]=\\{1,\ldots,n\\}$. Let
$k$ be integer. Let $q_{k}(G)$ denote the smallest size $q$ of an alphabet $F$
for which there exist an encoding function

$C:F^{k}\rightarrow F^{n}$

and a decoding function

$D:(F\cup\\{\perp\\})^{n}\rightarrow F^{k}$

such that for every edge $e\in E$ and every message $m\in F^{k}$ it holds that

$D(C_{e}(m))=m.$

Here, $C_{e}(m)$ stands for the word obtained from the codeword $C(m)$ by
replacing the symbols in the locations of $[n]\setminus e$ by the erasure
symbol $\perp$.

Similarly, let $q_{k,lin}(G)$ denote the smallest prime power $q$ for which
there exist linear encoding and decoding functions defined above when $F$ is a
field of size $q$.

In Definition 1, notice that for $G$ that includes edges of size less than $k$
no such $(C,D)$ pair exists (no matter what the size of $F$ is). In this case
we define $q_{k}(G)$ and $q_{k,lin}(G)$ to be $\infty$. Moreover, for every
$G$ with edges of size at least $k$, MDS codes satisfy the requirements on
$(C,D)$ and thus $q_{k}(G)<\infty$. Specifically, observe that for the
complete $n$-vertex $k$-uniform hypergraph, denoted by $\kappa_{n,k}$, the
values of $q_{k}(\kappa_{n,k})$ and $q_{k,lin}(\kappa_{n,k})$ are equal to the
minimum alphabet sizes of general and linear $(n,k)$ MDS codes, respectively.
We state below the MDS conjectures for general and for linear codes (see,
e.g., [7, 9, 10, 11]).

######  Conjecture 1 (MDS Conjecture for general codes)

For given integers $k<q\neq 6$, let $n(q,k)$ be the largest integer $n$ such
that $q_{k}(\kappa_{n,k})\leq q$. Then,

$n(q,k)\leq\left\\{\begin{array}[]{ll}q+2&\mbox{if }4|q\mbox{ and
}k\in\\{3,q-1\\}\\\ q+1&\mbox{otherwise.}\end{array}\right.$ (1)

######  Conjecture 2 (MDS Conjecture for linear codes)

For given integers $k<q$ where $q$ is a prime power, let $n(q,k)$ be the
largest integer $n$ such that $q_{k,lin}(\kappa_{n,k})\leq q$. Then,

$n(q,k)\leq\left\\{\begin{array}[]{ll}q+2&\mbox{if }q\mbox{ is even and
}k\in\\{3,q-1\\}\\\ q+1&\mbox{otherwise.}\end{array}\right.$ (2)

There are strong relations between the $q$ parameter of hypergraphs and
certain colorings.

######  Definition 2 (Hypergraph strong-coloring)

A valid strong-coloring of a hypergraph $G$ is an assignment of colors to its
vertices so that the vertices of each edge are assigned to distinct colors.
The chromatic number $\chi(G)$ of $G$ is the minimum number of colors that
allows a valid strong-coloring of $G$. At times, we refer to $\chi$ simply as
the chromatic number of $G$.

######  Definition 3 (Hypergraph $k$-coloring)

A valid $k$-coloring of a hypergraph $G$ is an assignment of colors to its
vertices so that the vertices of each edge are assigned to at least $k$
distinct colors. The $k$-chromatic number $\chi_{k}(G)$ of $G$ is the minimum
number of colors that allows a valid $k$-coloring of $G$. If $G$ has edges of
size less than $k$, we define $\chi_{k}(G)=\infty$.

Note that a $k$-coloring of a $k$-uniform hypergraph is exactly a strong-
coloring. Also, note that every hypergraph $G$ for which $q_{k}(G)<\infty$
(i.e., all edges are of size at least $k$) satisfies $\chi_{k}(G)\leq\chi(G)$.
In particular, for $k$-uniform hypergraphs $G$, $\chi_{k}(G)=\chi(G)$.

######  Theorem 1 (Connecting $q_{k}(G)$ with $\chi_{k}(G)$, [8])

For every hypergraph $G$ for which $q_{k}(G)<\infty$,

$q_{k}(G)\leq q_{k}(\kappa_{\chi_{k}(G),k})\mbox{ ~{}~{}and~{}~{}
}q_{k,lin}(G)\leq q_{k,lin}(\kappa_{\chi_{k}(G),k}).$

In particular,

$q_{k}(G)\leq q_{k,lin}(G)\leq[\chi_{k}(G)-1]_{pp}.$

Here, for an integer $x$, $[x]_{pp}$ represents the smallest prime power that
is greater or equal to $x$.

Theorem 1 formalizes the natural intuition that for simple collections of
erasure patterns $G$, i.e., the setting in which $\chi_{k}(G)$ is small, a
small alphabet size $q$ suffices for a suitable erasure code. In particular,
the theorem states that $q_{k}(G)$ is upper bounded by
$q_{k}(\kappa_{\chi_{k}(G),k})$, which is the minimum alphabet size of a
$(\chi_{k}(G),k)$ MDS code.

The graph family $G_{q,k}$, defined next, is helpful in analyzing the
tightness of the upper bound provided by Theorem 1.

######  Definition 4 (The graph family $G_{q,k}$)

For integers $q$ and $k$, let $G_{q,k}$ be the $k$-uniform hypergraph whose
vertex set consists of all the balanced vectors of length $q^{k}$ over
$F=\\{0,1,\dots,q-1\\}$, that is, the vectors $u\in F^{q^{k}}$ such that
$|\\{i\in[q^{k}]\mid u_{i}=j\\}|=q^{k-1}$ for every $j\in F$, where $k$
vertices
$u^{1}=(u^{1}_{1},\dots,u^{1}_{q^{k}}),...,u^{k}=(u^{k}_{1},\dots,u^{k}_{q^{k}})$
form an edge if the collection of $k$-tuples
$\\{(u^{1}_{i},u^{2}_{i},\ldots,u^{k}_{i})\\}_{i\in[q^{k}]}$ is equal to
$[q]^{k}$.

The following lemma identified hypergraphs $G$ for which the gap between
$q_{k}(G)$ and $\chi_{k}(G)$ is maximal.

######  Lemma 1 (The extremal nature of $G_{q,k}$, [8])

For integers $q$ and $k$,

  1. 1.

$q_{k}(G_{q,k})\leq q$, and

  2. 2.

$\chi_{k}(G)\leq\chi_{k}(G_{q,k})$ for every graph $G$ with $q_{k}(G)=q$.

Extending results in [8], below we present (rater loose) bounds on
$\chi(G_{q,k})$.

######  Proposition 1 (Bounds of $\chi_{k}(G_{k,q})$)

For every prime power $q$ and $k\geq 2$,

$\frac{q^{k}-1}{q-1}\leq\chi_{k}(G_{q,k})\leq{q^{k-1}+1\choose q^{k-2}+1}.$

Proof:  We first study the collection of vertices in $G_{q,k}$ corresponding
to normalized linear functions $F^{k}\rightarrow F$ for field $F$ of size $q$.
A normalized linear function is one in which the leading nonzero coefficient
equals 1. Such functions, when considered in vector form $(u_{1},\ldots
u_{q^{k}})\in F^{q^{k}}$ are balanced and thus correspond to vertices of
$G_{q,k}$. Moreover, it is not hard to verify that any two vertices of
$G_{q,k}$ corresponding to distinct normalized linear functions are included
in an edge of $G_{q,k}$ (i.e., there exist $k-2$ additional vertices of
$G_{q,k}$ corresponding to normalized linear functions that complete a
linearly independent collection of functions). Thus, any $k$-coloring of
$G_{q,k}$ must color all vertices corresponding to normalized linear functions
with distinct colors. The number of normalized linear functions over $F$
corresponding to vertices of $G_{q,k}$ is
$\sum_{i=1}^{k}{q^{k-i}}=(q^{k}-1)/(q-1)$. Therefore
$\chi(G_{q,k})\geq\frac{q^{k}-1}{q-1}$.

On the other hand, we now show that $\chi(G_{q,k})\leq{q^{k-1}+1\choose
q^{k-2}+1}$. For any vector $u$ in $G_{q,k}$, consider the first $q^{k-1}+1$
entries of $u$. By the pigeonhole principal,
$u_{i_{1}}=u_{i_{2}}=\ldots=u_{i_{q^{k-2}+1}}$ for some collection of entries
indexed by $i_{1}<i_{2}<\ldots<i_{q^{k-2}+1}\in[q^{k-1}+1]$. Now, for any
$q^{k-2}+1$ distinct indices $i_{1}<i_{2}<\ldots<i_{q^{k-2}+1}\in[q^{k-1}+1]$
let $A_{i_{1},i_{2},\ldots,i_{q^{k-2}+1}}$ be the set of all vertices $u\in
F^{q^{k}}$ of $G_{q,k}$ that satisfy
$u_{i_{1}}=u_{i_{2}}=\ldots=u_{i_{q^{k-2}+1}}$. Every set
$A_{i_{1},i_{2},\ldots,i_{q^{k-2}+1}}$ forms an independent set in $G_{q,k}$,
i.e., a set that does not include any two vertices from an edge of $G_{q,k}$.
This follows, since for every two distinct vertices $u,v\in
A_{i_{1},i_{2},\ldots,i_{q^{k-2}+1}}$ we have
$u_{i_{1}}=u_{i_{2}}=\ldots=u_{i_{q^{k-2}+1}}$ and
$v_{i_{1}}=v_{i_{2}}=\ldots=v_{i_{q^{k-2}+1}}$, which is too large of an
overlap to allow the balanced nature of vertices included in edges of
$G_{q,k}$. Specifically, for vertices $u$ and $v$ that appear in an edge of
$G_{q,k}$, it must be for any $j_{1}$ and $j_{2}$ in $F$ that
$|\\{i\in[q^{k}]|u_{i}=j_{1},v_{i}=j_{2}]\\}|=q^{k-2}$. Such independent sets
were referred to as canonical in [8]. As the $q^{k-1}+1\choose q^{k-2}+1$
independent sets $A_{i_{1},i_{2},\ldots,i_{q^{k-2}+1}}$ of $G_{q,k}$ with
$i_{1},i_{2},\ldots,i_{q^{k-2}+1}\in[q^{k-1}+1]$ cover the entire vertex set
of $G_{q,k}$, coloring each one with a distinct color implies the required
upper bound on $\chi_{k}$. ∎

Lemma 1 and Proposition 1 imply a gap between $q_{k}(G_{q,k})$ and
$\chi_{k}(G_{q,k})$ which can be extended to one between $q_{k,lin}$ and the
$k$-chromatic number of the subgraph of $G_{q,k}$ induced by vertices that
correspond to normalized linear functions.

######  Proposition 2 (Gap between $q_{k,lin}(G)$ and $\chi_{k}(G)$, [8])

For every $k\geq 3$ and every prime power $q$, there exists a $k$-uniform
hypergraph $G$ with $q_{k,lin}(G)\leq q$ and yet
$\chi_{k}(G)\geq\frac{q^{k}-1}{q-1}$.

We finally state a modest known gap between $q_{k,lin}$ and $q_{k}$.
Identifying graphs that exhibit a larger gap than that presented below is a
problem left open in this work.

######  Proposition 3 (Gap between $q_{k,lin}$ and $q_{k}$, [12])

For $q=3$ and $k=2$ it holds that

$q_{k,lin}(G_{q,k})=[\chi_{k}(G_{q,k})-1]_{pp}=5>3\geq q_{k}(G_{q,k}).$

###  II-B Error Correction with predefined error sets.

In what follows, we extend our discussion beyond erasures to the context of
errors. As we will see, several of our results on the $q$-parameter
corresponding to erasures extend naturally to the $p$-parameter (defined
below) corresponding to codes with restricted error sets. Similarly, to the
erasure setting, we represent the collection of error sets by using a hyper-
graph $G=([n],E)$, in which the set of vertices $[n]$ represents coordinates
of a codeword. Each edge $e\in E$ of $G$ represents an error set, i.e., the
set of the coordinates that can be altered. Note that this is different from
the notation used in Definition 1 for the erasure case in which edges $e$
represented decoding sets (i.e., sets of uncorrupted symbols).

######  Definition 5 (The $p_{k}$ parameter)

Let $G=([n],E)$ be a hypergraph on the vertex set $[n]=\\{1,\ldots,n\\}$. Let
$k$ be an integer. Let $p_{k}(G)$ denote the smallest size $p$ of an alphabet
$F$ for which there exist an encoding function

$C:F^{k}\rightarrow F^{n}$

and a decoding function

$D:F^{n}\rightarrow F^{k}$

such that for every edge $e\in E$, every message $m\in F^{k}$, and every error
vector $v=(v_{1},\dots,v_{n})\in F^{n}$,

$D(C(m)\diamond_{e}v)=m.$

Here, for $C(m)=c_{1},\dots,c_{n}$, the term $C(m)\diamond_{e}v$ refers to the
vector $y=y_{1},\dots,y_{n}$ for which for $i\in[n]$, $y_{i}=v_{i}$ if $i\in
e$, and otherwise $y_{i}=c_{i}$ (i.e., we overwrite $C(m)$ with values of $v$
in the coordinates $i\in e$).

Similarly, let $p_{k,lin}(G)$ denote the smallest prime power $p$ for which
there exist linear encoding and decoding functions as above when $F$ is a
field of size $p$.

In Definition 5, the pair $(C,D)$ corresponds to a code that is resilient to
errors on locations corresponding to an edge $e\in E$. That is, the edge set
$E$ represents the possible error patterns (i.e., sets of potentially
corrupted symbols).

Similar to Definition 1, in Definition 5, if $G$ has edges of size greater
than $\left\lfloor\frac{n-k}{2}\right\rfloor$, no such codes $(C,D)$ exist,
and we define $p_{k}(G)=p_{k,lin}(G)=\infty$.

As with erasures, for the complete hypergraph
$\kappa_{n,\left\lfloor\frac{n-k}{2}\right\rfloor}$, the values of
$p_{k}(\kappa_{n,\left\lfloor\frac{n-k}{2}\right\rfloor})$ and
$p_{k,lin}(\kappa_{n,\left\lfloor\frac{n-k}{2}\right\rfloor})$ are equal to
the minimum alphabet sizes of general and linear $(n,k)$ MDS codes,
respectively. That is,
$p_{k}(\kappa_{n,\left\lfloor\frac{n-k}{2}\right\rfloor})=q_{k}(\kappa_{n,k})$
and
$p_{k,lin}(\kappa_{n,\left\lfloor\frac{n-k}{2}\right\rfloor})=q_{k,lin}(\kappa_{n,k})$.

Note that Definitions 1 and 5 assume zero-error decoding. We relax this
requirement in Section VI.

##  III Bounds on the Alphabet Size

######  Proposition 4 (Analog of Theorem 1)

Let $k$ be an integer. For every hypergraph $G=([n],E)$ for which
$p_{k}(G)<\infty$ it holds that

$p_{k}(G)\leq p_{k}(\kappa_{\chi,\left\lfloor\frac{\chi-k}{2}\right\rfloor}),$

where $\chi=\chi(\bar{G})$ and $\bar{G}=(V,\bar{E})$ is the hypergraph with
vertex set $V=[n]$ and edges $\bar{E}=\\{V\setminus e|e\in E\\}$.

Proof:  To ease our notation, we assume that $n-k$ and $\chi-k$ are even
(minor modifications in notation are needed otherwise). Let $G$ be as above
and let $\chi=\chi(\bar{G})$. Denoting $p=p_{k}(\kappa_{\chi,(\chi-k)/2})$, it
follows that there exist a $(\chi,k)$ MDS code $C$ over an alphabet $F$ of
size $p$. To prove that $p_{k}(G)\leq p$, we define a coding scheme for $G$
over the alphabet $F$ that includes the following two steps. First, fix a
valid coloring $g:[n]\rightarrow[\chi]$ of $\bar{G}$. Second, consider the
encoding function $\widetilde{C}:F^{k}\rightarrow F^{n}$ that given a message
$m\in F^{k}$ outputs the vector in $F^{n}$ whose $i$’th entry
$\widetilde{C}_{i}(m)$ is $C_{g(i)}(m)$, i.e., $\widetilde{C}_{i}(m)$ is the
coordinate in the codeword $C(m)$ which corresponds to the color of the $i$’th
vertex. Here, and throughout, we use the notation $C_{i}(m)$ to denote the
$i$’th entry in the codeword $C(m)$.

The decoder $\widetilde{D}:F^{n}\rightarrow F^{k}$ for $G$ is now defined
using the following procedure. Consider an error vector $v\in F^{n}$, edge
$e_{0}\in E$, and the corresponding received word
$y=\widetilde{C}(m)\diamond_{e_{0}}v$. For each edge $\bar{e}$ in $\bar{E}$,
the decoder $\widetilde{D}$ considers $y_{\bar{e}}$ consisting of the entries
of $y$ restricted to the indices in ${\bar{e}}$, and detects whether
$y_{\bar{e}}$ has been corrupted, i.e., whether
$\widetilde{C}_{\bar{e}}(m)=y_{\bar{e}}$. As for at least one such edge
$\bar{e}_{0}$ it holds that $\widetilde{C}_{\bar{e}_{0}}(m)=y_{\bar{e}_{0}}$
(e.g. for $\bar{e}_{0}=[n]\setminus{e}_{0}$), the decoder $\widetilde{D}$ can
use $y_{\bar{e}_{0}}$ to decode $m$. We are left to show, given
$\bar{e}\in\bar{E}$, how $\widetilde{D}$ can detect whether
$\widetilde{C}_{\bar{e}}(m)=y_{\bar{e}}$, and if so decode $m$.

To detect whether a given $\bar{e}$ in $\bar{E}$ satisfies
$\widetilde{C}_{\bar{e}}(m)=y_{\bar{e}}$ we note, by the definition of
$\widetilde{C}$ and the fact that all vertices in $\bar{e}$ have distinct
colors under the coloring $g$, that the entries in
$\widetilde{C}_{\bar{e}}(m)$ correspond to at least $(n+k)/2$ distinct entries
$C(m)$. The latter, in turn, implies that $\widetilde{C}_{\bar{e}}(m)$ is
itself a $(|\bar{e}|,k)$ MDS code. As such, $\widetilde{C}_{\bar{e}}(m)$ can
detect up to $|\bar{e}|-k\geq\frac{n-k}{2}$ errors and correct up to
$\left(|\bar{e}|-k\right)/2\geq\frac{n-k}{4}$ errors. We conclude, as all
error sets $e$ are of size at most $(n-k)/2$, that given $\bar{e}$ in
$\bar{E}$, the decoder $\widetilde{D}$ can detect whether or not $y_{\bar{e}}$
has been corrupted, and if not, recover $m$ as required. ∎

Proposition 4 is not tight, meaning that $p_{k}(G)$ might be smaller than
$p_{k}(\kappa_{\chi,(\chi-k)/2})$. For $k=2$ take for example $G=([6],E)$ to
be the $6$-cycle, i.e., the graph on $6$ vertices in which its edges
$E=\\{(i,i+1)|i=0,1,\dots,5\\}$ (with addition $\mod$ 6). Then $p_{2}(G)=2$,
since the binary encoding $C:F^{2}\rightarrow F^{6}$ in which for a message
$m=(x,y)\in F^{2}$ equals $C(x,y)=(x,y,x,y,x,y)$ allows majority decoding for
any 2 errors along an edge in $G$. However, $\chi=\chi(\bar{G})=6$, since
every pair of vertices in $\bar{G}$ is included in some edge in $\bar{E}$, and
by [13] it holds that
$p_{2}(\kappa_{\chi,\left\lfloor\frac{\chi-k}{2}\right\rfloor})=p_{2}(\kappa_{6,2})=5$.
In the next section, we improve on Proposition 4 by connecting the $p_{k}$ and
$q_{k}$ parameters.

##  IV Connecting Error and Erasure Correcting Codes

For parameters $n$ and $k$, we say that encoder $C:F^{k}\rightarrow F^{n}$ is
good for a given hypergraph $G=([n],E)$ with respect to erasures (res.,
errors) if there exists a decoder $D$ satisfying Definition 1 (res.,
Definition 5). The following proposition is proven from basic principles.

######  Proposition 5 (From errors to erasures)

Let $n$ and $k$ be parameters. Consider a hypergraph $G^{\tt err}=([n],E^{\tt
err})$ corresponding to errors. Let $G^{\tt era}=([n],E^{\tt era})$ be the
hypergraph (corresponding to erasures) for which

$E^{\tt era}=\\{[n]\setminus(e_{1}^{\tt err}\cup e_{2}^{\tt err})\mid
e_{1}^{\tt err},e_{2}^{\tt err}\in E^{\tt err}\\}.$

Let $C:F^{k}\rightarrow F^{n}$ be any encoder. Then, $C$ is good for $G^{\tt
err}$ if and only if $C$ is good for $G^{\tt era}$.

Proof:  First assume that $C$ is good for $G^{\tt err}$. We show that for
every edge $e=e^{\tt era}\in E^{\tt era}$, one can decode $m$ from $C_{e}(m)$.
Assume in contradiction that there are two messages $m_{1}\neq m_{2}$ such
that $C_{e}(m_{1})=C_{e}(m_{2})$. Recall that $e=[n]\setminus(e_{1}\cup
e_{2})$ for $e_{1}=e_{1}^{\tt err}\in E^{\tt err}$ and $e_{2}=e_{2}^{\tt
err}\in E^{\tt err}$. Consider the word $y=(y_{1},\dots,y_{n})\in F^{n}$ such
that for $i\in e=[n]\setminus(e_{1}\cup e_{2})$:
$y_{i}=C_{i}(m_{1})=C_{i}(m_{2})$, for $i\in e_{1}\setminus e_{2}$:
$y_{i}=C_{i}(m_{2})$, and for $i\in e_{2}$: $y_{i}=C_{i}(m_{1})$. It is not
hard to verify that there exist vectors $v_{1}$ and $v_{2}$ such that
$y=C(m_{1})\diamond_{e_{1}}v_{1}=C(m_{2})\diamond_{e_{2}}v_{2}$. Namely, $y$
could be obtained from the codeword $C(m_{1})$ with error vector $v_{1}$
corresponding to $e_{1}$ or from the codeword $C(m_{2})$ with error vector
$v_{2}$ corresponding to $e_{2}$, contradicting the existence of a decoder $D$
according to Definition 5.

For the other direction, if code $C$ is not good for $G^{\tt err}$ then there
exist two messages, $m_{1}$ and $m_{2}$, two error vectors $v_{1}$ and
$v_{2}$, and two edges $e_{1}$ and $e_{2}$ in $E^{\tt err}$ such that
$C(m_{1})\diamond_{e_{1}}v_{1}=C(m_{2})\diamond_{e_{2}}v_{2}.$ Otherwise, it
is not hard to verify the existence of a natural decoder $D$ according to
Definition 5. Let $e=[n]\setminus(e_{1}\cup e_{2})\in E^{\tt era}$. The
equality $C(m_{1})\diamond_{e_{1}}v_{1}=C(m_{2})\diamond_{e_{2}}v_{2}$ now
implies that $C_{e}(m_{1})=C_{e}(m_{2})$, which in turn implies that $C$ is
not good for $G^{\tt era}$. ∎

The proposition above has an operational perspective. Namely, one can design
an error-correcting code $C$ and decoder $D$ for a given graph $G^{\tt err}$,
by designing an erasure-code for the graph $G^{\tt era}$. The latter can be
done, e.g., using Theorem 1 to obtain the following corollary.

###### Corollary 2

Let $k$ be an integer. For every hypergraph $G^{\tt err}=([n],E)$ for which
$p_{k}(G^{\tt err})<\infty$ it holds that

$p_{k}(G^{\tt err})\leq q_{k}(G^{\tt era})\leq q_{k}(\kappa_{\chi_{k}(G^{\tt
era}),k})\leq[\chi_{k}(G^{\tt era})-1]_{pp},$

which, in turn, implies that

$p_{k}(G^{\tt err})\leq
p_{k}(\kappa_{\chi,\left\lfloor\frac{\chi-k}{2}\right\rfloor}),$

where $\chi=\chi_{k}(G^{\tt era})$.

We now extend the connections implied by Proposition 5 to capture the $p_{k}$
and $q_{k}$ parameters.

######  Theorem 3 (Connecting $p_{k}$ with $q_{k}$)

Let $n,k$ be parameters such that $n-k\geq k$. Let $G_{0}^{\tt
era}=([n],E_{0}^{\tt era})$ be a hypergraph corresponding to erasures such
that $q_{k}(G_{0}^{\tt era})<\infty$. Then, for $N=2n-k$ there exists a
hypergraph $G^{\tt err}$ on $N$ vertices such that $p_{k}(G^{\tt
err})=q_{k}(G_{0}^{\tt era})$ and $p_{k,lin}(G^{\tt err})=q_{k,lin}(G_{0}^{\tt
era})$.

Proof:  Let $G_{0}^{\tt era}=([n],E_{0}^{\tt era})$ be as above. We define two
graphs according to $G_{0}^{\tt era}$. First consider the graph $G^{\tt
err}=([n]\cup U,E^{\tt err})$ corresponding to errors for which $U$ is a
vertex set of size $n-k$ and

$E^{\tt err}=\\{U\\}\cup\\{[n]\setminus e^{\tt era}|e^{\tt era}\in E_{0}^{\tt
era}\\}.$

Here, we use the fact that edges in $E_{0}^{\tt era}$ are subsets of $[n]$.
Namely, the vertex set $[n]\cup U$ of $G^{\tt err}$ is of size $N=2n-k$ and
each edge in $E^{\tt err}$ is of size at most $\frac{N-k}{2}=n-k$. We refer to
the edges in $\\{[n]\setminus e^{\tt era}|e^{\tt era}\in E_{0}^{\tt
era}\\}\subset E^{\tt err}$ as ordinary edges, and to the edge $U\in E^{\tt
err}$ as the special edge.

Let $G^{\tt era}$ be the graph corresponding to erasures defined by $G^{\tt
err}$ as in Proposition 5. Namely, $G^{\tt era}=([n]\cup U,E^{\tt era})$ where

$E^{\tt era}=\\{([n]\cup U)\setminus(e_{1}^{\tt err}\cup e_{2}^{\tt err})\mid
e_{1}^{\tt err},e_{2}^{\tt err}\in E^{\tt err}\\}.$

Taking a closer look at the edge set $E^{\tt era}$, if an edge $e^{\tt era}$
in $E^{\tt era}$ is defined by two ordinary edges of $E^{\tt err}$, then it is
not hard to verify that $U\subseteq e^{\tt era}$. If an edge $e^{\tt era}$ in
$E^{\tt era}$ is defined by the special edge $U$ and an ordinary edge $e\in
E^{\tt err}$, then $e^{\tt era}=[n]\setminus e$. As the ordinary edge $e\in
E^{\tt err}$, by definition, equals $[n]\setminus e_{0}^{\tt era}$ for an edge
$e_{0}^{\tt era}\in E_{0}^{\tt era}$ we conclude that $e^{\tt era}=e_{0}^{\tt
era}$. Finally, if an edge $e$ in $E^{\tt era}$ is defined solely by $U$
(i.e., we set $e_{1}=e_{2}=U$), then $e=[n]$. All in all, we conclude that the
edge set $E^{\tt era}$ equals the edges $E_{0}^{\tt era}\cup\\{[n]\\}$ and an
additional set of edges $e^{\tt era}$ for which $U\subseteq e^{\tt era}$.

We now show that $p_{k}(G^{\tt err})=q_{k}(G_{0}^{\tt era})$. We start by
studying codes for $G_{0}^{\tt era}$ and $G^{\tt era}$. For any code
$C_{0}:F^{k}\rightarrow F^{n}$ for $G_{0}^{\tt era}$, define the code
$C:F^{k}\rightarrow F^{n+(n-k)}$ for $G^{\tt era}$ in which for every message
$m$ it holds that $C(m)=C_{0}(m)$ on the first $[n]$ entries, that $C(m)=m$ on
entries $n+1,\dots,n+k$ and that $C(m)$ equals the symbol $a\in F$ for the
remaining entries $n+k+1,\ldots,2n{-}k$. Here, we use the fact that $n-k\geq
k$. Similarly, for any code $C:F^{k}\rightarrow F^{n+n-k}$ for $G^{\tt era}$,
let the code $C_{0}:F^{k}\rightarrow F^{n}$ for $G_{0}^{\tt era}$ be the
restriction of $C$ to the first $n$ entries. It is now not hard to verify that
$C_{0}$ is good for $G_{0}^{\tt era}$ if and only if $C$ is good for $G^{\tt
era}$. More specifically, let $C_{0}$ be a code that is good for $G_{0}^{\tt
era}$, and let $D_{0}$ be the corresponding decoder. For any message $m$ and
edge $e=e_{0}^{\tt era}$ it holds that $D_{0}((C_{0})_{e}(m))=m$. To show that
$C$ is good for $G^{\tt era}$ we define the decoder $D$, that for $e^{\tt
era}\in E^{\tt era}$ either runs $D_{0}$ on the first $n$ entries of $C$ if
$e^{\tt era}\subseteq[n]$, or decodes using the identity mapping from $U$ if
$U\subseteq e^{\tt era}$. For the opposite direction, let $C$ be good for
$G^{\tt era}$, and let $D$ be the corresponding decoder. To show that $C_{0}$
is good for $G_{0}^{\tt era}$ we define the decoder $D_{0}$ as the restriction
of $D$ that takes into account only the first $n$ entries of $C$. Correctness
follows as $E_{0}^{\tt era}\subseteq E^{\tt era}$ and as $C_{0}$ is a
restriction of $C$ to the first $n$ entries.

To show that $p_{k}(G^{\tt err})=q_{k}(G_{0}^{\tt era})$, let $N=2n-k$ and let
$C:F^{k}\rightarrow F^{N}$ be any encoder. By Proposition 5, $C$ is good for
$G^{\tt err}$ if and only if $C$ is good for $G^{\tt era}$. By the discussion
above, $C$ is good for $G^{\tt era}$ if and only if the corresponding $C_{0}$
is good for $G_{0}^{\tt era}$. Thus, $C_{0}$ is good for $G_{0}^{\tt era}$ if
and only if $C$ is good for $G^{\tt err}$. Optimizing over $|F|$, we conclude
$p_{k}(G^{\tt err})=q_{k}(G_{0}^{\tt era})$. As the reductions described above
between $C$ and $C_{0}$ preserves linearity, we also conclude that
$p_{k,lin}(G^{\tt err})=q_{k,lin}(G_{0}^{\tt era})$. ∎

By Theorem 3 the gap between the $q_{k}$ parameter and the $q_{k,lin}$
parameter for erasure codes stated in Proposition 3 implies a gap between the
$p_{k}$ parameter and the $p_{k,lin}$ parameter for error correcting codes. We
summarize this results in the following corollary.

######  Corollary 4 (Non-linear codes outperform linear codes)

For $k=2$, there exists a hypergraph $G$ with $p_{k,lin}(G)=5$ and yet
$p_{k}(G)=3$.

##  V Error detection

Similar to the case of errors and erasures, one can define analogs of
Definitions 1 and 5 for the case of error detection. Namely, for a given
hypergraph $G=([n],E)$ the $r_{k}$ parameter defined below equals the minimum
size alphabet of an $(n,k)$ error detection code that can detect error patters
represented by $E$.

######  Definition 6 (The $r_{k}$ parameter)

Let $G=([n],E)$ be a hypergraph on the vertex set $[n]=\\{1,\ldots,n\\}$, and
let $k$ be an integer. Let $r_{k}(G)$ denote the smallest size $r$ of an
alphabet $F$ for which there exist an encoding function

$C:F^{k}\rightarrow F^{n}$

and a decoding function

$D:F^{n}\rightarrow\\{\text{\em error, no-error}\\}$

such that for every edge $e\in E$, every message $m\in F^{k}$, and every error
vector $v=(v_{1},\dots,v_{n})\in F^{n}$,

$D(C(m)\diamond_{e}v)=``\text{\em error}^{\prime\prime}\ \text{\em{if and only
if}}\ C(m)\neq C(m)\diamond_{e}v,$

($\diamond_{e}$ is defined in Definition 5).

Similar to Definition 1, in Definition 6, $r_{k}(G)$ is defined if and only if
all edges of $G$ are of size at most $n-k$, otherwise we define
$r_{k}(G)=\infty$. Also, similar to Proposition 5, the following proposition
is proven from basic principles (its proof is sketched here for completeness).

######  Proposition 6 (Detecting errors vs. correcting erasures)

Let $n$ and $k$ be parameters such that $n-k\geq k$. For a hypergraph
$G=([n],E)$, let $\bar{G}=([n],\bar{E})$ be the hypergraph for which
$\bar{E}=\\{[n]\setminus e|e\in E\\}$. Then, $r_{k}(G)=q_{k}(\bar{G})$.

Proof:  Assume that $\bar{C}$ is a good erasure code for $\bar{G}$. The same
code can be used for detection on $G$. Namely, given a received word $y$, to
check if $y$ is corrupted in locations corresponding to $e\in E$, decode to
$m$ using $y_{\bar{e}}$ (via the erasure decoding) and compare $\bar{C}(m)$ to
$y$. For the other direction, assume that $C$ is a good detection code for
$G$. Use the same code $C$ for erasures. To decode from $C_{\bar{e}}(m)$,
construct the collection $Y$ of size $|F|^{n-|{\bar{e}}|}$ of words $y\in
F^{n}$ that equal $C_{\bar{e}}(m)$ on the locations of ${\bar{e}}$ and
otherwise equal a (distinct) word in $F^{n-|{\bar{e}}|}$. As $C$ is a
detection code for errors with support $e=[n]\setminus\bar{e}$, we can detect
the unique $y\in Y$ that is a codeword, and accordingly decode $m$. ∎

##  VI Average error $\varepsilon$

In what follows, we generalize the $q_{k}$, $p_{k}$, and $r_{k}$ parameters to
include a decoding error. In our prior work [8], for $k=2$ in the context of
erasures, we considered decoding error when averaged over the message set
$F^{k}$. We here consider a looser notion of error that is also averaged over
edges in the edge set $E$ of the hypergraph at hand. As shown below, allowing
a slight error in decoding will in turn allow the construction of codes with
small alphabet sizes (independent of the blocklength $n$).

######  Definition 7 (The $q_{\varepsilon,k}$, $p_{\varepsilon,k}$, and
$r_{\varepsilon,k}$ parameters)

Let $k$ be an integer. Let $G=([n],E)$ be a hypergraph on the vertex set $[n]$
and let $\varepsilon>0$. Let $q_{\varepsilon,k}(G)$ denote the smallest size
$q$ of an alphabet $F$ for which there exist an encoding function
$C:F^{k}\rightarrow F^{n}$ and a decoding function
$D:(F\cup\\{\perp\\})^{n}\rightarrow F^{k}$ such that

$\Pr_{e,m}[D(C_{e}(m))=m]\geq 1-\varepsilon,$

where $m$ is uniformly chosen from $F^{k}$, and $e$ is uniformly chosen from
$E$. One may define $p_{\varepsilon,k}(G)$ and $r_{\varepsilon,k}(G)$ in an
analogous manner.

We will need the following approximate version of coloring.

######  Definition 8 (Hypergraph $(1-\varepsilon)$-$k$-coloring)

A valid $(1-\varepsilon)$-$k$-coloring of a hypergraph $G=(V,E)$ is an
assignment of colors to its vertices $V$ so that for at least
$(1-\varepsilon)|E|$ edges $e\in E$, the vertices of $e$ are assigned to at
least $k$ colors. The $(1-\varepsilon)$-$k$-chromatic number
$\chi_{\varepsilon,k}(G)$ of $G$ is the minimum number of colors that allows a
valid $(1-\varepsilon)$-$k$-coloring of $G$.

###### Theorem 5

Let $G=(V,E)$ be a hypergraph, and $\varepsilon>0$ a parameter. Then
$q_{\varepsilon,k}(G)\leq[\chi_{\varepsilon,k}(G)-1]_{pp}$. In particular, let
$n$ and $k$ be any integers, $q_{\varepsilon,k}(\kappa_{n,k})\leq
O(k^{2}/\varepsilon)$.

Proof:  The proof that
$q_{\varepsilon,k}(G)\leq[\chi_{\varepsilon,k}(G)-1]_{pp}$ is almost identical
to the proof of Theorem 1 (presented in [8]) and is obtained by replacing
$q_{k}$ and $\chi_{k}$ by $q_{\varepsilon,k}$ and $\chi_{\varepsilon,k}$
respectively. The second part of the theorem follows by showing that
$\kappa_{n,k}$ can be $(1-\varepsilon)$-$k$ colored using $k^{2}/\varepsilon$
colors. Consider partitioning $[n]$ into $k^{2}/\varepsilon$ subsets, each of
size $\varepsilon n/k^{2}$. Assign the same color to all the vertices in the
same subset, and distinct colors to vertices in distinct subsets. We now show
that this is a $(1-\varepsilon)$-$k$ coloring. The fraction of edges that are
assigned to at least $k$ colors is

$\frac{{k^{2}/\varepsilon\choose{k}}\cdot(\varepsilon
n/k^{2})^{k}}{{n\choose{k}}}.$

Now, for integers $a$ and $b$, ${a\choose
b}=\frac{\prod_{j=0}^{b-1}(a-j)}{b!}$, and
$a^{b}\geq\prod_{j=0}^{b-1}(a-j)\geq(a-b)^{b}\geq(1-b^{2}/a)a^{b}$, thus

$\frac{(1-b^{2}/a)a^{b}}{b!}\leq{a\choose b}\leq\frac{a^{b}}{b!}.$

Therefore $\frac{{k^{2}/\varepsilon\choose{k}}\cdot(\varepsilon
n/k^{2})^{k}}{{n\choose{k}}}\geq 1-\varepsilon$. ∎

Notice that implications corresponding to those in Theorem 5 on parameters
$p_{\varepsilon,k}$ and $r_{\varepsilon,k}$ can be derived using Theorem 3 and
Proposition 6, respectively.

## References

  * [1] Y. Wu.  Novel burst error correction algorithms for reed-solomon codes.  IEEE Transactions on Information Theory, 58(2):519–529, 2012.
  * [2] Eitan Yaakobi, Jing Ma, Laura Grupp, Paul H Siegel, Steven Swanson, and Jack K Wolf.  Error characterization and coding schemes for flash memories.  In 2010 IEEE Globecom Workshops, pages 1856–1860, 2010.
  * [3] G. Forney.  Burst-correcting codes for the classic bursty channel.  IEEE Transactions on Communication Technology, 19(5):772–781, 1971\.
  * [4] J. Moon and J. Park.  Detection of prescribed error events: application to perpendicular recording.  In IEEE International Conference on Communications, ICC 2005, Seoul, volume 3, pages 2057–2062. IEEE, 200520.
  * [5] L. Yohananov and E. Yaakobi.  Codes for graph erasures.  IEEE Transactions on Information Theory, 65(9):5433–453, 2019\.
  * [6] Vilas Sridharan and Dean Liberty.  A study of dram failures in the field.  In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC ’12, Washington, DC, USA, 2012. IEEE Computer Society Press.
  * [7] K. A. Bush.  Orthogonal arrays of index unity.  Ann. Math. Statistics, 23:426 – 434, 1952.
  * [8] M. Gonen, I. Haviv, M. Langberg, and A. Sprintson.  Minimizing the alphabet size of erasure codes with restricted decoding sets.  In IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, CA, USA, June 21-26, 2020, pages 144–149. IEEE, 2020.
  * [9] B. Segre.  Curve razionali normali e k-archi negli spazi finiti.  Ann. Mat. Pura Appl., 39(4):357–379, 1955.
  * [10] F. J. MacWilliams and N. J. A. Sloane.  The Theory of Error-CorrectingCodes.  Amsterdam: North-Holland, 1977.
  * [11] S. Huntemann.  The upper bound of general maximum distance separable codes, 2012.  Honours Project.
  * [12] A. R. Lehman and E. Lehman.  Network coding: does the model need tuning?  In SODA’05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 499–504, 2005.
  * [13] S. Huntemann.  The Upper Bound of General Maximum Distance Separable Codes, 2012.


S\end{subarray}}\mathbb{P}(a,b\in A^{\prime})$ $\displaystyle\geq$
$\displaystyle\frac{1}{16}|G|^{-2}|A|^{2},$

provided $|A|$ is larger than some sufficiently large absolute constant.777We
need this condition on the size of $A$ so that that the probability of a pair
of elements $a,b\in A$ ending up in $A^{\prime}$ is at least $1/8$. On the
other hand, the theorem holds trivially for $A$ of bounded size as we can take
$C=\\{0\\}$ since there are always at least $\frac{|A|^{3}}{K}$ solutions to
$0=a_{1}+a_{2}-a_{3}-a_{4}$ with elements $a_{1},\dots,a_{4}\in A$.
Thus, there is a choice of $A^{\prime}$ satisfying this bound. Fix such a
subset $A^{\prime}\subseteq A$. Let $\eta=|A^{\prime}|/|S|$. Note also that
$\frac{1}{2K}\leq\eta\leq 1$.
Using Theorem A.2 with sets $A^{\prime}$ and $-S$ and parameter
$\varepsilon=\frac{1}{32}$, we see that

$\mathbbm{1}_{A^{\prime}}\ast\mathbbm{1}_{A^{\prime}}\ast\mathbbm{1}_{-S}(t)\geq\frac{1}{32}|G|^{-2}|A|^{2}$

holds for all $t\in 2T-2T$, where $T\subseteq A^{\prime}$ is a set of size at
least $\exp\Big{(}-O(\log^{O(1)}(2K)))\Big{)}|A|$. Note that
$|T+T|\leq|A^{\prime}+A^{\prime}|\leq K|A|\leq\exp(O(\log^{O(1)}(2K)))|T|$.
Apply Theorem 3.1 to find a symmetric proper coset progression $C\subset
2T-2T$ of rank at most $O(\log^{O(1)}(2K))$ and size at least
$\exp(-O(\log^{O(1)}(2K)))|A|$. For each $c\in C$ we have at least
$\frac{1}{64K}|A|^{3}$ of quadruples $(a_{1},a_{2},a_{3},a_{4})\in A^{4}$ such
that $c=a_{1}+a_{2}-a_{3}-a_{4}$.∎

##  Appendix B Quasirandomness of bipartite graphs

Throughout this appendix, $G$ denotes a bipartite graph on vertex classes $X$
and $Y$. We also view $G$ simultaneously as a $\\{0,1\\}$-valued function on
the product $X\times Y$. Let $\|\cdot\|_{\square}=\|\cdot\|_{\square(X,Y)}$
stand for the box norm, which is defined by

$\|f\|_{\square(X,Y)}=\Big{(}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{0},x_{1}\in
X}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{y_{0},y_{1}\in
Y}f(x_{0},y_{0})\,\overline{f(x_{1},y_{0})}\,\overline{f(x_{0},y_{1})}\,f(x_{1},y_{1})\Big{)}^{1/4}.$

An important property of the box norm is that it provided bounds on the
correlation of a given function $f$ with functions depending on a single
variable only.

######  Lemma B.1.

Let $f\colon X\times Y\to\mathbb{C}$, $u\colon X\to\mathbb{C}$ and $v\colon
Y\to\mathbb{C}$ be functions. Then

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in X,y\in
Y}f(x,y)u(x)v(y)\Big{|}\leq\|f\|_{\square}\|u\|_{L^{2}}\|v\|_{L^{2}}.$

Given a bipartite graph $G$ on vertex classes $X$ and $Y$, its density
$\delta$ is given by $\mathop{\mathbb{E}}_{x\in X,y\in Y}G(x,y)$. We say that
$G$ is $\varepsilon$-_quasirandom_ if $\|G-\delta\|_{\square}\leq\varepsilon$.
Quasirandom graphs behave like randomly chosen graphs of the given density. An
instance of this phenomenon is given by the following lemma, which says that
the intersection of neighbourhoods of $k$ vertices in one vertex class
typically has density about $\delta^{k}$ in the other vertex class.

######  Lemma B.2.

Let $k$ be a positive integer and let $G$ be an $\varepsilon$-quasirandom
bipartite graph of density $\delta$ on vertex classes $X$ and $Y$. Pick
$x_{1},\dots,x_{k}\in X$ uniformly and independently at random. Let $\eta>0$
be a positive real. Then

$\mathbb{P}\Big{(}\Big{|}|N_{x_{1}}\cap\dots\cap
N_{x_{k}}|-\delta^{k}|Y|\Big{|}\geq\eta|Y|\Big{)}\leq 4k\eta^{-2}\varepsilon.$

In our paper we need a more general version of this lemma, which we now state
and prove. Lemma B.2 follows as a corollary.

######  Lemma B.3.

Let $k$ and $m$ be positive integers and let $G$ be an
$\varepsilon$-quasirandom bipartite graph of density $\delta$ on vertex
classes $X$ and $Y$. Let $M\subseteq Y^{m}$ be a set of $m$-tuples in $Y$.
Pick $x_{1},\dots,x_{k}\in X$ uniformly and independently at random. Let
$\eta>0$ be a positive real. Then

$\mathbb{P}\Big{(}\Big{|}|N^{m}_{x_{1}}\cap\dots\cap N^{m}_{x_{k}}\cap
M|-\delta^{mk}|M|\Big{|}\geq\eta|Y|^{m}\Big{)}\leq 4km\eta^{-2}\varepsilon.$

###### Proof.

Let $f(x,y)=G(x,y)-\delta$ and $\mu=|M|/|Y|^{m}$. We have

$\displaystyle\frac{1}{|Y|^{2m}}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1},\dots,x_{k}\in X}$
$\displaystyle\Big{|}|N^{m}_{x_{1}}\cap\dots\cap N^{m}_{x_{k}}\cap
M|-\delta^{mk}|M|\Big{|}^{2}$ $\displaystyle=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1},\dots,x_{k}\in
X}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y_{1},\dots,y_{m}\in
Y}M(y_{1},\dots,y_{k})\Big{(}\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})-\delta^{km}\Big{)}\Big{|}^{2}$
$\displaystyle=$
$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}M(y_{1},\dots,y_{k})M(z_{1},\dots,z_{k})\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})G(x_{i},z_{j})$
$\displaystyle\hskip
56.9055pt-2\delta^{km}\mu\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in
Y\end{subarray}}M(y_{1},\dots,y_{k})\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})+\delta^{2km}\mu^{2}.$
(18)

We approximate the term

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}M(y_{1},\dots,y_{k})M(z_{1},\dots,z_{k})\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})G(x_{i},z_{j})$

by $\delta^{2km}\mu^{2}$ using Lemma B.1. Let us write $M(y)$ and $M(z)$ for
$M(y_{1},\dots,y_{k})$ and $M(z_{1},\dots,z_{k})$ respectively. Using triangle
inequality, we get

$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}M(y)M(z)\Big{(}G(x_{1},y_{1})-\delta\Big{)}G(x_{2},y_{1})\cdots
G(x_{k},y_{1})G(x_{1},y_{2})\cdots
G(x_{k},y_{m})\Big{(}\prod_{i\in[k],j\in[m]}G(x_{i},z_{j})\Big{)}\bigg{|}$
$\displaystyle\hskip
56.9055pt=\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}M(y)M(z)f(x_{1},y_{1})G(x_{2},y_{1})\cdots
G(x_{k},y_{1})G(x_{1},y_{2})\cdots
G(x_{k},y_{m})\Big{(}\prod_{i\in[k],j\in[m]}G(x_{i},z_{j})\Big{)}\bigg{|}$
$\displaystyle\hskip
56.9055pt\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{2},\dots,x_{k}\in X\\\
y_{2},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1}\in X\\\ y_{1}\in
Y\end{subarray}}f(x_{1},y_{1})\Big{(}M(y)G(x_{2},y_{1})\cdots
G(x_{k},y_{1})\Big{)}$ $\displaystyle\hskip
227.62204pt\Big{(}G(x_{1},y_{2})G(x_{1},y_{3})\cdots
G(x_{1},y_{m})G(x_{1},z_{1})\cdots G(x_{1},z_{m})\Big{)}\bigg{|}.$

Applying Lemma B.1 for every choice of
$x_{2},\dots,x_{k},y_{2},\dots,y_{m},z_{1},\dots,z_{m}$ above, we may bound
the last line by $\|f\|_{\square}$. Thus

$\displaystyle\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}M(y)M(z)\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})G(x_{i},z_{j})$
$\displaystyle\hskip
56.9055pt-\delta\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}M(y)M(z)\prod_{\begin{subarray}{c}i\in[k],j\in[m]\\\
(i,j)\not=(1,1)\end{subarray}}G(x_{i},y_{j})\prod_{i\in[k],j\in[m]}G(x_{i},z_{j})\bigg{|}\leq\|f\|_{\square}.$

Repeating the argument above $2km-1$ times in order to eventually replace
every occurrence of $G$ by $\delta$, we obtain

$\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in Y\\\ z_{1},\dots,z_{m}\in
Y\end{subarray}}M(y)M(z)\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})G(x_{i},z_{j})-\delta^{2k}\mu^{2}\bigg{|}\leq
2km\|f\|_{\square}.$

The term $\mathop{\mathbb{E}}_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in
Y\end{subarray}}M(y)\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})$ in expression (18)
can be similarly approximated by $\delta^{km}\mu$

$\bigg{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{\begin{subarray}{c}x_{1},\dots,x_{k}\in X\\\
y_{1},\dots,y_{m}\in
Y\end{subarray}}\prod_{i\in[k],j\in[m]}G(x_{i},y_{j})-\delta^{km}\mu\bigg{|}\leq
km\|f\|_{\square}.$

Going back to (18) and using the assumption $\|f\|_{\square}\leq\varepsilon$
we obtain

$\displaystyle\frac{1}{|Y|^{2m}}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x_{1},\dots,x_{k}\in X}$
$\displaystyle\Big{|}|N^{m}_{x_{1}}\cap\dots\cap N^{m}_{x_{k}}\cap
M|-\delta^{mk}|M|\Big{|}^{2}\leq 4km\varepsilon,$

completing the proof.∎

As it is well-known, properties like the one described in Lemma B.2 are
equivalent to the graph being quasirandom. An example of such a reverse
implication is given by the next lemma.

######  Lemma B.4.

Let $\delta,\varepsilon\in[0,1]$. Suppose that $G$ is a bipartite graph with
vertex classes $X$ and $Y$ such that

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x\in
X}\Big{|}|N_{x}|-\delta|Y|\Big{|}\leq\varepsilon|Y|$ (19)

and

$\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}}\displaylimits_{x,x^{\prime}\in
X}\Big{|}|N_{x}\cap N_{x^{\prime}}|-\delta^{2}|Y|\Big{|}\leq\varepsilon|Y|.$
(20)

Then the density $\delta^{\prime}$ of $G$ satisfies
$|\delta-\delta^{\prime}|\leq\varepsilon$ and the graph $G$ is
$3\sqrt[8]{\varepsilon}$-quasirandom.

###### Proof.

Let $f(x,y)=G(x,y)-\delta$. We begin the proof by showing that $\delta$ and
$\delta^{\prime}$ differ by a small amount. This follows easily from (19),
namely

$|\delta^{\prime}-\delta||X||Y|=\Big{|}\sum_{x\in
X}\Big{(}|N_{x}|-\delta|Y|\Big{)}\Big{|}\leq\sum_{x\in
X}\Big{|}|N_{x}|-\delta|Y|\Big{|}\leq\varepsilon|X||Y|.$

By averaging, we conclude from condition (19) that for at least
$1-\sqrt{\varepsilon}$ proportion of all $x\in X$

$\Big{|}|N_{x}|-\delta|Y|\Big{|}\leq\sqrt{\varepsilon}|Y|$

holds. Similarly, condition (20) implies that for at least
$1-\sqrt{\varepsilon}$ proportion of all pairs $(x,x^{\prime})\in X^{2}$

$\Big{|}|N_{x}\cap
N_{x^{\prime}}|-\delta^{2}|Y|\Big{|}\leq\sqrt{\varepsilon}|Y|$

holds. Thus, for at least $(1-3\sqrt{\varepsilon})|X|^{2}$ of pairs
$(x,x^{\prime})\in X^{2}$ we have

$\Big{|}|N_{x}\cap
N_{x^{\prime}}|-\delta|N_{x}|-\delta|N_{x^{\prime}}|+\delta^{2}|Y|\Big{|}\leq\Big{|}|N_{x}\cap
N_{x^{\prime}}|-\delta^{2}|Y|\Big{|}+\Big{|}\delta|N_{x}|-\delta^{2}|Y|\Big{|}+\Big{|}\delta|N_{x^{\prime}}|-\delta^{2}|Y|\Big{|}\leq
3\sqrt{\varepsilon}|Y|.$

The term on the left hand side equals $|Y|$ times
$\Big{|}\mathop{\mathbb{E}}_{y\in Y}f(x,y)f(x^{\prime},y)\Big{|}$, the latter
being bounded from above by 1. Thus,

$\|f\|_{\square}^{4}=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,x^{\prime}\in X,y,y^{\prime}\in
Y}f(x,y)f(x^{\prime},y)f(x,y^{\prime})f(x^{\prime},y^{\prime})=\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x,x^{\prime}\in
X}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{y\in Y}f(x,y)f(x^{\prime},y)\Big{|}^{2}\leq
9\varepsilon+3\sqrt{\varepsilon}\leq 12\sqrt{\varepsilon}.$

Recalling that $|\delta-\delta^{\prime}|\leq\varepsilon$, we obtain
$\|G-\delta^{\prime}\|_{\square}\leq 3\sqrt[8]{\varepsilon}$.∎

We may view the condition in Lemma B.4 as a type of one-sided quasirandomess.
Thus, combining Lemmas B.2 and B.4 we conclude that if $G$ satisfies the one-
sided quasirandomness condition for the vertex class $X$, then it is in fact
quasirandom, and thus is also satisfies the one-sided quasirandomness
condition for the vertex class $Y$, with a somewhat smaller quasirandomness
parameter.

## References

  * [1] A. Balog and E. Szemerédi, _A statistical theorem of set addition_ , Combinatorica 14 (1994), 263–268.
  * [2] P.-Y. Bienvenu and T.H. Lê, _A bilinear Bogolyubov theorem_ , European Journal of Combinatorics, 77 (2019), 102–113.
  * [3] P.-Y. Bienvenu and T.H. Lê, _Linear and quadratic uniformity of the Möbius function over $\mathbb{F}_{q}[t]$_, Mathematika 65 (2019), 505–529.
  * [4] M.-C. Chang, _A polynomial bound in Freiman’s theorem_ , Duke Mathematical Journal 113 (2002), 399–419.
  * [5] W.T. Gowers, _A new proof of Szemerédi’s theorem for arithmetic progressions of length four_ , Geometric and Functional Analysis 8 (1998), 529–551.
  * [6] W.T. Gowers and L. Milićević, _A quantitative inverse theorem for the $U^{4}$ norm over finite fields_, arXiv preprint (2017), `arXiv:1712.00241`.
  * [7] W.T. Gowers and L. Milićević, _A bilinear version of Bogolyubov’s theorem_ , Proceedings of the American Mathematical Society 148 (2020), 4695–4704.
  * [8] W.T. Gowers and L. Milićević, _An inverse theorem for Freiman multi-homomorphisms_ , arXiv preprint (2020), `arXiv:2002.11667`.
  * [9] B. Green and I.Z. Ruzsa, _Freiman’s theorem in an arbitrary abelian group_ , Journal of the London Mathematical Society 75 (2007), 163–175.
  * [10] B. Green and T. Tao, _An inverse theorem for the Gowers $U^{3}(G)$-norm_, Proc. Edinb. Math. Soc. 51 (2008), 73–153.
  * [11] K. Hosseini and S. Lovett, _A bilinear Bogolyubov-Ruzsa lemma with polylogarithmic bounds_ , Discrete Analysis, paper no. 10 (2019), 1–14.
  * [12] G. Petridis, _New Proofs of Plünnecke-type Estimates for Product Sets in Groups_ , Combinatorica 32 (2012), 721–733.
  * [13] I.Z. Ruzsa, Sumsets and Structure, Combinatorial Number Theory and Additive Group Theory, 87–210 (Springer, 2009).
  * [14] T. Sanders, _On the Bogolyubov-Ruzsa lemma_ , Analysis & PDE 5 (2012), no. 3, 627–655.
  * [15] T. Schoen and O. Sisask, _Roth’s theorem for four variables and additive structures in sums of sparse sets_ , Forum of Mathematics, Sigma 4 (2016), e5, 28pp.
  * [16] T. Tao and V. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, UK, 2006.
  * [17] J. Tidor, _Quantitative bounds for the $U^{4}$-inverse theorem over low characteristic finite fields_, arXiv preprint (2021), `arXiv:2109.13108`.