# On the Generalized Covering Radii
of Reed-Muller Codes

Dor Elimelech , Hengjia Wei, and Moshe Schwartz Dor Elimelech is with the
School of Electrical and Computer Engineering, Ben-Gurion University of the
Negev, Beer Sheva 8410501, Israel (e-mail: doreli@post.bgu.ac.il).Hengjia Wei
is with the School of Electrical and Computer Engineering, Ben-Gurion
University of the Negev, Beer Sheva 8410501, Israel (e-mail:
hjwei05@gmail.com).Moshe Schwartz is with the School of Electrical and
Computer Engineering, Ben-Gurion University of the Negev, Beer Sheva 8410501,
Israel (e-mail: schwartz@ee.bgu.ac.il).The work of D. Elimelech was supported
in part by an Israel Science Foundation (ISF) Grant under Grant 1052/18. The
work of H. Wei and M. Schwartz was supported in part by a German Israeli
Project Cooperation (DIP) Grant under Grant PE2398/1-1.

###### Abstract

We study generalized covering radii, a fundamental property of linear codes
that characterizes the trade-off between storage, latency, and access in
linear data-query protocols such as PIR. We prove lower and upper bounds on
the generalized covering radii of Reed-Muller codes, as well as finding their
exact value in certain extreme cases. With the application to linear data-
query protocols in mind, we also construct a covering algorithm that gets as
input a set of points in space, and find a corresponding set of codewords from
the Reed-Muller code that are jointly not farther away from the input than the
upper bound on the generalized covering radius of the code. We prove that the
algorithm runs in time that is polynomial in the code parameters.

###### Index Terms:

Reed-Muller codes, generalized covering radius, covering algorithm

##  I Introduction

The generalized covering radius has recently been proposed [10] as a new
fundamental property of linear codes, generalizing the classical notion of a
covering radius. As a motivating application, these radii characterize a
trade-off between storage, latency, and access complexities in linear data-
query protocols, a prime example of which is the PIR (Private Information
Retrieval) protocol. Several equivalent definitions of the generalized
covering radii were given in [10], showing their combinatorial, geometric, and
algebraic aspects. It has also been observed that there is an intriguing
similarity between the generalized covering radii and the well known
generalized Hamming weights of linear codes [28], hinting at a deeper theory
and perhaps additional applications of these parameters that are yet to be
revealed.

A crucial part in our understanding of any fundamental parameter of codes, is
the values that it takes in specific examples and in parametric families of
codes. In [10], the generalized covering radius hierarchy was found only for
Hamming codes and shortened Hamming codes, whereas the remaining results did
not pertain to specific code families. The Hamming code, in its extended
version, is a specific case of the famous family of Reed-Muller codes, which
is one of the most studied families of linear error-correcting codes. Reed-
Muller codes have been extensively studied in the recent decades due to their
practical applications and fascinating relations with various mathematical
objects. Reed-Muller codes were recently proved to achieve asymptotically the
capacity of erasure channels [17]. They have long been conjectured to achieve
Shannon’s capacity on symmetric channels, and a recent paper [3] took a step
towards a proof of this conjecture, by showing a polarization property in
Reed-Muller codes. Other applications of Reed-Muller codes include locally
decodable code [29], probabilistic proof systems [1], sequence design for
wireless communication [23, 8, 9, 26], and Boolean functions [4, 18, 21]. For
a recent survey, the readers are referred to [2].

While many aspects of Reed-Muller codes have been investigated, of particular
interest to us is the (regular) covering radius. Its relation to the maximum
nonlinearity of Boolean functions, motivated many of the papers on the
subject. The covering radius of Reed-Muller codes has been studied in
different settings [16, 14, 20, 7, 5, 13, 15, 25, 22, 24]. However, despite
decades of research on the subject, the exact covering radius of Reed-Muller
codes is mostly unknown, except for a handful of specific cases, and many
papers resorted to finding lower and upper bounds.

The goal of this paper is to explore the _generalized covering radii_ of Reed-
Muller codes. Our main contributions are the following:

  1. 1.

We prove lower and upper bounds on the generalized covering radii of Reed-
Muller codes, $\operatorname{RM}(r,m)$, in various asymptotic regimes of its
parameters: constant $r$, constant $m-r$, and constant $r/m$. We also find the
exact $t$-th generalized covering radius of $\operatorname{RM}(r,m)$ in simple
cases, $r\in\left\\{0,m-2,m-1,m\right\\}$. These results are summarized in
Table I and Table II.

  2. 2.

Motivated by the application for linear data-querying protocols, we construct
a $t$-covering algorithm for Reed-Muller codes. Loosely speaking, given $t$
vectors in the space, the algorithm finds $t$ codewords that are jointly not
farther away from the given points than the best upper bound that we have on
the $t$-th generalized covering radius of the code. We analyze the run-time
complexity of the algorithm and show it is polynomial in the code parameters.

The paper is organized as follows: Preliminaries and notations are presented
in Section II. Section III is devoted to the derivation of bounds on the
generalized covering radii of Reed-Muller codes. The construction of our
covering algorithm and its analysis are in Section IV. We conclude with a
discussion of the results and some open questions in Section V.

##  II Preliminaries

We use lower-case letters, $v$, to denote scalars, overlined lower-case
letters, $\overline{v}$, to denote vectors, and either bold lower-case
letters, $\mathbf{v}$, or upper-case letter, $V$, to denote matrices. Whether
vectors are row vectors or column vectors is deduced from context.

Let $\mathbb{F}_{q}$ denote the finite field of size $q$. For
$n\in\mathbb{N}$, we define $[n]\triangleq\\{1,\dots,n\\}$, and denote by
$\binom{[n]}{t}$ the set of all subsets of $[n]$ of size $t$. For a vector
$\overline{v}=(v_{1},\dots,v_{n})\in\mathbb{F}_{q}^{n}$, the support of
$\overline{v}$ is defined as
$\operatorname{supp}(\overline{v})\triangleq\left\\{i\in[n]\,\middle|\,\mathopen{}v_{i}\neq
0\right\\}$, and its Hamming weight is defined as
$\operatorname{wt}(\overline{v})\triangleq\left\lvert\operatorname{supp}(\overline{v})\right\rvert$.
The Hamming distance between
$\overline{v},\overline{v}^{\prime}\in\mathbb{F}_{q}^{n}$ is then defined as
$d(\overline{v},\overline{v}^{\prime})\triangleq\operatorname{wt}(\overline{v}^{\prime}-\overline{v})$.

We say $C$ is an $[n,k,d]_{q}$ linear code if $C\subseteq\mathbb{F}_{q}^{n}$
is a $k$-dimensional vector space, and the minimum Hamming distance between
distinct codewords is $d$. The code $C$ may be specified using a $k\times n$
generator matrix $G\in\mathbb{F}_{q}^{k\times n}$, whose row space is $C$, or
by an $(n-k)\times n$ parity-check matrix $H\in\mathbb{F}_{q}^{(n-k)\times
n}$, whose null space is $C$. The dual code of $C$, denoted $C^{\perp}$, is
the code whose generator matrix is $H$, and parity-check matrix is $G$,
namely,

$C^{\perp}\triangleq\left\\{\overline{v}\in\mathbb{F}_{q}^{n}\,\middle|\,\mathopen{}\forall\overline{c}\in
C,\overline{v}\cdot\overline{c}=0\right\\}.$

The dual code, $C^{\perp}$, is an $[n,n-k,d^{\prime}]_{q}$ code. We say
$d^{\prime}$ is the _dual distance_ of $C$.

For any vector $\overline{v}\in\mathbb{F}_{q}^{n}$, the distance between
$\overline{v}$ and the code $C$ is defined as

$d(\overline{v},C)\triangleq\min_{\overline{c}\in
C}d(\overline{c},\overline{v}).$

The covering radius of $C$, denoted $R(C)$, is then defined as

$R(C)\triangleq\max_{\overline{v}\in\mathbb{F}_{q}^{n}}d(\overline{v},C).$

It is therefore the minimum radius at which balls centered at the codewords of
$C$ cover the entire space $\mathbb{F}_{q}^{n}$. A generalization of this
property will be presented shortly when we introduce the generalized covering
radii of $C$. Later, we shall also make use of a connection between the
covering radius of $C$, and the dual distance of $C$. To that end we recall
the definition of Krawtchouk polynomials,

$K_{k}(x;n,q)\triangleq\sum_{j=0}^{k}(-1)^{j}\binom{x}{j}\binom{n-x}{k-j}(q-1)^{k-j},$

where

$\binom{x}{j}\triangleq\frac{x(x-1)\dots(x-j+1)}{j!}.$ (1)

We further denote the minimal root of $K_{k}(x;n,q)$ by

$x(k,n;q)\triangleq\min\left\\{x\in\mathbb{R}\,\middle|\,\mathopen{}K_{k}(x{;}\,n,q)=0\right\\}.$

###### Lemma 1

[27, Theorem 3.3] Let $C$ be an $[n,k]_{q}$ code with dual distance
$d^{\prime}$. Then

$R(C)\leqslant\begin{cases}x(u,n-1;q)&d^{\prime}=2u-1,\\\
x(u,n;q)&d^{\prime}=2u.\end{cases}$

###  II-A The generalized covering radii

The generalized covering radii of a linear code were introduced in [10]. They
have several equivalent definitions, which we bring here and use
interchangeably. We begin with a geometric definition. Consider the set of
matrices $\mathbb{F}_{q}^{t\times n}$, in which we have a generalized notion
for the Hamming weights. For a matrix $\mathbf{v}\in\mathbb{F}_{q}^{t\times
n}$, with row vectors denoted by $\overline{v}_{i}$, the $t$-weight is defined
to be

$\operatorname{wt}^{(t)}(\mathbf{v})\triangleq\left\lvert\bigcup_{i\in[t]}\operatorname{supp}(\overline{v}_{i})\right\rvert.$

The $t$-weight naturally induces a metric on $\mathbb{F}_{q}^{t\times n}$ by

$d^{(t)}(\mathbf{v},\mathbf{u})\triangleq\operatorname{wt}^{(t)}(\mathbf{v}-\mathbf{u}),$

for all $\mathbf{v},\mathbf{u}\in\mathbb{F}_{q}^{t\times n}$. Let
$B_{r}^{(t)}(\mathbf{v})$ denote the ball of radius $r$ centered in
$\mathbf{v}\in\mathbb{F}_{q}^{t\times n}$, with respect to the metric
$d^{(t)}$, namely

$B_{r}^{(t)}(\mathbf{v})\triangleq\left\\{\mathbf{v}^{\prime}\in\mathbb{F}_{q}^{t\times
n}\,\middle|\,\mathopen{}d^{(t)}(\mathbf{v},\mathbf{v}^{\prime})\leqslant
r\right\\}.$

Since this metric is translation invariant, the volume of the ball does not
depend on the choice of its center. We denote this volume by

$V_{q^{t},n,r}\triangleq\left\lvert
B_{r}^{(t)}(\mathbf{v})\right\rvert=\sum_{i=0}^{r}\binom{n}{i}(q^{t}-1)^{i},$
(2)

which is exactly the size of a ball of radius $r$ in $\mathbb{F}_{q^{t}}^{n}$
using the Hamming metric. We now have the following definition for the $t$-th
generalized radius:

###### Definition 2

Let $C$ be an $[n,k]_{q}$ linear code. Then for every $t\in\mathbb{N}$, we
define the $t$-th generalized covering radius, denoted by $R_{t}(C)$, to be
the minimal integer $r$ such that the balls of radius $r$ centered at

$C^{t}\triangleq\left\\{\begin{bmatrix}\overline{c}_{1}\\\ \vdots\\\
\overline{c}_{t}\end{bmatrix}\in\mathbb{F}_{q}^{t\times
n}\,\middle|\,\mathopen{}\forall i\in[t],\overline{c}_{i}\in C\right\\},$ (3)

cover $\mathbb{F}_{q}^{t\times n}$, i.e.,

$\bigcup_{\mathbf{c}\in C^{t}}B^{(t)}_{r}(\mathbf{c})=\mathbb{F}_{q}^{t\times
n}.$

One can easily see that $R_{1}(C)=R(C)$ is indeed the regular covering radius
of the code $C$. Let us now turn to an equivalent definition via the parity-
check matrix of a code. Assume $C$ is a linear $[n,k]_{q}$ code with a (full-
rank) parity-check matrix $H\in\mathbb{F}_{q}^{(n-k)\times n}$. Let the
columns of $H$ be denoted by $\overline{h}_{1},\dots,\overline{h}_{n}$. Then
for $I\in\binom{[n]}{t}$, $1\leqslant t\leqslant n$, we denote the linear span
of $\\{\overline{h}_{i}\\}_{i\in I}$ by $\langle H_{I}\rangle$. We have the
following equivalent definition for the $t$-th generalized covering radius of
$C$:

###### Definition 3

The $t$-th covering radius of $C$, denoted by $R_{t}(C)$, is the smallest
integer $r$ such that for any $t$ vectors
$\overline{v}_{1},\dots,\overline{v}_{t}\in\mathbb{F}_{q}^{n-k}$, there exists
$I\in\binom{[n]}{r}$ such that $\\{v_{1},\dots,v_{t}\\}\subseteq\langle
H_{I}\rangle$.

The final equivalent definition that we recall for the generalized covering
radius is algebraic in nature:

###### Definition 4

Let $C\subseteq\mathbb{F}_{q}^{n}$ be a linear code with a generator matrix
$G\in\mathbb{F}_{q}^{k\times n}$ and a parity-check matrix
$H\in\mathbb{F}_{q}^{(n-k)\times n}$. Let $C_{t}$ be the code over
$\mathbb{F}_{q^{t}}$, with generator matrix $G$ and parity-check matrix $H$,
namely,

$C_{t}\triangleq\left\\{\overline{u}G\,\middle|\,\mathopen{}\overline{u}\in\mathbb{F}_{q^{t}}^{k}\right\\}=\left\\{\overline{v}\in\mathbb{F}_{q^{t}}^{n}\,\middle|\,\mathopen{}H\overline{c}^{\intercal}=\overline{0}^{\intercal}\right\\}.$
(4)

The $t$-th covering radius is defined to be

$R_{t}(C)\triangleq R_{1}(C_{t}),$

where $R_{1}(C_{t})$ is the (regular, first) covering radius of $C_{t}$.

According to Definition 4, the problem of finding the $t$-th covering radius
of a code $C\subseteq\mathbb{F}_{q}^{n}$, is equivalent to finding the regular
covering radius of $C_{t}$ defined over $\mathbb{F}_{q^{t}}$. Since the code
$C_{t}$ will be used many times, we briefly show that, unlike the covering
radius, its minimum distance does not change.

###### Lemma 5

Let $C$ be an $[n,k,d]_{q}$ code. Then for any $t\in\mathbb{N}$, the code
$C_{t}$ of (4) is an $[n,k,d]_{q^{t}}$ code.

###### Proof:

The fact that $C_{t}$ has length $n$ is trivial. Let
$H\in\mathbb{F}_{q}^{(n-k)\times n}$ be parity-check matrix for $C$. Since a
set of vectors from $\mathbb{F}_{q}^{n}$ is linearly independent over
$\mathbb{F}_{q}$ if and only if it is linearly independent over
$\mathbb{F}_{q^{t}}$, the matrix $H$ has the same rank over
$\mathbb{F}_{q^{t}}$, and its null-space, $C_{t}$, has dimension $k$. Finally,
it is well known that the minimum distance $d$ of $C$ is the minimal number of
columns of $H$ that are linearly dependent. By the same argument as before,
this number does not change when considering columns of $H$ and linear
dependence over $\mathbb{F}_{q^{t}}$. Hence, the minimum distance of $C_{t}$
is also $d$. ∎

The generalized covering radius has a subadditivity property that proves to be
useful for establishing many of the results in this work:

###### Lemma 6

[10, Proposition 15] Let $C$ be an $[n,k]_{q}$ code. Then for all
$t_{1},t_{2}\in\mathbb{N}$,

$R_{t_{1}+t_{2}}(C)\leqslant R_{t_{1}}+R_{t_{2}}(C).$

In particular, $R_{t}(C)\leqslant tR_{1}(C)$ for all $t\in\mathbb{N}$.

A simple ball-covering argument is used in the following lemma.

###### Lemma 7

For an $[n,k]_{q}$ code $C$ and $t\in\mathbb{N}$,

$\log_{q^{t}}\left\lparen V_{q^{t},n,R_{t}(C)}\right\rparen\geqslant n-k.$

###### Proof:

Recalling (4), consider the code $C_{t}$ over $\mathbb{F}_{q^{t}}$, generated
by the same generator matrix as $C$. Clearly, $C_{t}$ has the same dimension
and length as $C$. By the standard ball-covering argument (see [6, Theorem
6.2.1]),

$\log_{q^{t}}\left\lparen V_{q^{t},n,R_{1}(C_{t})}\right\rparen\geqslant n-k.$

By Definition 4, $R_{1}(C_{t})=R_{t}(C)$, and we conclude. ∎

Since we shall be interested in asymptotic results, we recall facts about the
asymptotics of binomial coefficients as well as the volume of balls in the
Hamming metric. Let $H_{q}(x)$ denote the $q$-ary entropy function,

$H_{q}(x)\triangleq x\log_{q}(q-1)-x\log_{q}(x)-(1-x)\log_{q}(1-x).$

A useful Taylor expansion near the entropy function’s maximum was presented in
[12, Proposition 3.3.5], showing that, as $\epsilon\to 0$,

$H_{q}\left\lparen
1-\frac{1}{q}-\epsilon\right\rparen=1-\frac{\epsilon^{2}q^{2}}{2(q-1)\ln
q}(1+o(1)).$ (5)

For any real $0<\alpha<1$, such that $\alpha n\in\mathbb{N}$, it is known
(e.g., see [19, Ch. 10, Lemma 7]) that

$\frac{1}{\sqrt{8n\alpha(1-\alpha)}}2^{nH_{2}(\alpha)}\leqslant\binom{n}{\alpha
n}\leqslant\frac{1}{\sqrt{2\pi n\alpha(1-\alpha)}}2^{nH_{2}(\alpha)},$ (6)

and this holds for $n\in\mathbb{R}$, $n>1$ (recall the definition of the
binomial in (1), and see [11, p. 482]). As for the Hamming ball, it is well
known (see [19, Ch. 10, Corollary 9] and [12, Proposition 3.3.1]) that for
$q\geqslant 2$, and $\alpha\leqslant 1-\frac{1}{q}$,

$\frac{1}{\sqrt{8n\alpha(1-\alpha)}}q^{nH_{q}(\alpha)}\leqslant V_{q,n,\alpha
n}\leqslant q^{nH_{q}(\alpha)}.$ (7)

###  II-B Reed-Muller codes

Reed-Muller codes have been extensively studied (e.g., see [19], and the many
references therein). We recall the relevant definitions and properties needed
for this paper. For $m\in\mathbb{N}$ and $0\leqslant r\leqslant m$, the $r$-th
order Reed-Muller code, denoted by $\operatorname{RM}(r,m)$, is a binary
linear $[n,k]$ code with parameters

$\displaystyle n$ $\displaystyle=2^{m},$ $\displaystyle k$
$\displaystyle=\sum_{i=0}^{r}\binom{m}{i}.$ (8)

Reed-Muller codes have multiple equivalent definitions, and one that will be
useful for our needs is a recursive definition, given by the $(u,u+v)$
construction. Assume $C_{1}$ and $C_{2}$ are $[n,k_{1}]_{q}$ and
$[n,k_{2}]_{q}$ codes, respectively. The $(u,u+v)$ construction uses $C_{1}$
and $C_{2}$ to produce a code

$C=\left\\{(\overline{u},\overline{u}+\overline{v})\,\middle|\,\mathopen{}\overline{u}\in
C_{1},\overline{v}\in C_{2}\right\\}.$

As a base for the recursion, we define

$\operatorname{RM}(0,m)\triangleq\left\\{\overline{0},\overline{1}\right\\},$

i.e., the repetition code. Additionally, we define

$\operatorname{RM}(m,m)\triangleq\mathbb{F}_{2}^{2^{m}},$

i.e., the entire set of binary vectors of length $2^{m}$. Finally, for
$1\leqslant r\leqslant m-1$, we define $\operatorname{RM}(r,m)$ to be the code
produced by the $(u,u+v)$ construction using $\operatorname{RM}(r,m-1)$ and
$\operatorname{RM}(r-1,m-1)$.

Reed-Muller codes are nested, namely, for all $1\leqslant r\leqslant m$,

$\operatorname{RM}(r-1,m)\subseteq\operatorname{RM}(r,m).$ (9)

Additionally, the family of Reed-Muller code is closed under code duality, and
in particular

$\operatorname{RM}(r,m)^{\perp}=\operatorname{RM}(m-r-1,m).$

This implies that

$\dim\left\lparen\operatorname{RM}(r,m)\right\rparen=2^{m}-\dim\left\lparen\operatorname{RM}(m-r-1,m)\right\rparen.$
(10)

To avoid cumbersome notation, we denote the $t$-th generalized covering radius
of the $r$-th order Reed-Muller code by

$R_{t}(r,m)\triangleq R_{t}(\operatorname{RM}(r,m)).$

The following fundamental property of $R_{t}(r,m)$ will be used frequently in
this work:

###### Proposition 8

For all $m,t\in\mathbb{N}$, and $1\leqslant r\leqslant m-1$,

$R_{t}(r,m)\leqslant R_{t}(r-1,m-1)+R_{t}(r,m-1).$

###### Proof:

The claim follows from the $(u,u+v)$ construction of Reed-Muller codes. In
[10, Proposition 24] it is proved that if a code $C$ is produced using the
$(u,u+v)$ construction with $C_{1}$ and $C_{2}$, then $R_{t}(C)\leqslant
R_{t}(C_{1})+R_{t}(C_{2})$. ∎

##  III Bounds

Our main results are presented in this section. We prove bounds on the
generalized covering radii of Reed-Muller codes, $\operatorname{RM}(r,m)$, in
three different asymptotic regimes, as $m\to\infty$:

  * •

$r$ is constant.

  * •

$m-r$ is constant.

  * •

$r/m$ is constant.

Upper bounds will be derived using two main strategies: The first is by
considering the upper bounds from [7] and using the subadditivity formula from
Lemma 6. The second strategy involves the use of the recursive formula from
Proposition 8 and analysis of the base cases. Our lower bounds will
essentially be the well known ball-covering lower bound (over the field
$\mathbb{F}_{q^{t}}$), analyzed separately for each of the different cases.

###  III-A The case where $r$ is constant

In this parameter regime, the Reed-Muller codes have vanishing asymptotic
rate, and high covering radius. We first consider the extreme case of
$\operatorname{RM}(0,m)$, which is none other than the repetition code. In
this simple case we can determine the generalized covering radii exactly.

###### Proposition 9

For all $m,t\in\mathbb{N}$,

$R_{t}(0,m)=2^{m}-\left\lceil 2^{m-t}\right\rceil.$

###### Proof:

The Reed-Muller code $C=\operatorname{RM}(0,m)$ is the binary repetition code
of length $2^{m}$, namely, its generator matrix is $G=(1,1,\dots,1)$. Thus,
$C_{t}$ of (4) is just the $2^{t}$-ary repetition code of the same length.
Given a vector $\overline{v}\in\mathbb{F}_{2^{t}}^{2^{m}}$, the closest
codeword of $C_{t}$ to $\overline{v}$ is $\overline{c}=(c,c,\dots,c)\in C_{t}$
where $c\in\mathbb{F}_{2^{t}}$ is the symbol appearing the most times in
$\overline{v}$. By simple averaging, there exists a symbol appearing at least
$\lceil 2^{m-t}\rceil$ times in $\overline{v}$, giving us $R_{t}(0,m)\leqslant
2^{m}-\lceil 2^{m-t}\rceil$. For the lower bound, define
$\ell\triangleq\min\\{t,m\\}$, and let
$\overline{v}\in\mathbb{F}_{2^{t}}^{2^{m}}$ be a vector with $2^{\ell}$
different symbols, such that each symbol appears exactly $2^{m-\ell}$ times.
Clearly, we have

$d(\overline{v},\operatorname{RM}(0,m))=2^{m}-2^{m-\ell}\geqslant 2^{m}-\lceil
2^{m-t}\rceil.$

This proves the lower bound. ∎

For the more general cases of $\operatorname{RM}(r,m)$ with $r\geqslant 1$, we
provide separate upper and lower bound on the generalized covering radii. The
upper bounds are proved by induction on $r$. The base case of
$\operatorname{RM}(1,m)$ is proved first.

###### Lemma 10

For all $m,t\in\mathbb{N}$,

$R_{t}(1,m)\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}2^{m/2}.$

###### Proof:

Denote $C=\operatorname{RM}(1,m)$. It is well known that
$C^{\perp}=\operatorname{RM}(m-2,m)$ is the extended binary Hamming code (see
[19, Ch. 13]), and hence the dual distance of $C$ is $d^{\prime}=4$. By Lemma
5, $d^{\prime}=4$ is the dual distance of $C_{t}$ of (4) as well. By Lemma 1,
the covering radius of $C_{t}$ is upper bounded by

$R_{t}(C)=R_{1}(C_{t})\leqslant x(2,2^{m};2^{t}),$

i.e., the smallest root of the Krawtchouk polynomial $K_{2}(x;2^{m},2^{t})$.
Since

$K_{2}(x;q,n)=\frac{1}{2}\left\lparen
q^{2}x^{2}-q(2qn-q-2n+2)x+(q-1)^{2}n(n-1)\right\rparen,$

it follows that

$\displaystyle x(2,n;q)=\left\lparen 1-\frac{1}{q}\right\rparen
n-\frac{1}{2}+\frac{1}{q}-\frac{\sqrt{(4q-4)n+(q-2)^{2}}}{2q}\leqslant\left\lparen
1-\frac{1}{q}\right\rparen n-\frac{\sqrt{(q-1)n}}{q}.$

Plugging in $n=2^{m}$ and $q=2^{t}$, we obtain the desired result. ∎

We can now prove the general upper bound on $R_{t}(r,m)$ for $r\geqslant 1$.

###### Theorem 11

For all $m,t\in\mathbb{N}$, $1\leqslant r\leqslant m$,

$R_{t}(r,m)\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}(1+\sqrt{2})^{r-1}2^{m/2}+O(m^{r-2}).$

where we consider $r$ and $t$ to be constants.

###### Proof:

We prove the claim by induction on $r$. Lemma 10 shows the claim holds for
$r=1$, and for all $m\in\mathbb{N}$. Assume that the claim holds for all
$\ell\leqslant r-1$, and all $m\in\mathbb{N}$. We now show that it holds for
$r$ as well. By repeatedly using Proposition 8 and the induction hypothesis,
we have,

$\displaystyle R_{t}(r,m)$ $\displaystyle\leqslant
R_{t}(r,m-1)+R_{t}(r-1,m-1)$ $\displaystyle\leqslant R_{t}(r,m-1)+\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m-1}-\frac{\sqrt{2^{t}-1}}{2^{t}}(1+\sqrt{2})^{r-2}2^{(m-1)/2}+O(m^{r-3})$
$\displaystyle\vdots$ $\displaystyle\leqslant
R_{t}(r,r)+\sum_{i=r}^{m-1}\left\lparen\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{i}-\frac{\sqrt{2^{t}-1}}{2^{t}}(1+\sqrt{2})^{r-2}2^{i/2}+O(m^{r-3})\right\rparen$
$\displaystyle\leqslant R_{t}(r,r)+\left\lparen
1-\frac{1}{2^{t}}\right\rparen\sum_{i=0}^{m-1}2^{i}-\frac{\sqrt{2^{t}-1}}{2^{t}}(1+\sqrt{2})^{r-2}\sum_{i=r}^{m-1}2^{i/2}+O(m^{r-2})$
$\displaystyle=\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}(1+\sqrt{2})^{r-1}\left\lparen
2^{m/2}-2^{r/2}\right\rparen+O(m^{r-2})$ $\displaystyle=\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}(1+\sqrt{2})^{r-1}2^{m/2}+O(m^{r-2}).$

Here we also use the fact $R_{t}(r,r)=0$, since
$\operatorname{RM}(r,r)=\mathbb{F}_{2}^{2^{r}}$, and so
$\operatorname{RM}(r,r)_{t}=\mathbb{F}_{2^{t}}^{2^{r}}$, whose covering radius
is $0$. ∎

The corresponding lower bound on $R_{t}(r,m)$ is proved next. It is obtained
by carefully considering both a ball-covering argument, and the upper bound we
just proved.

###### Theorem 12

For all $m,t\in\mathbb{N}$, $1\leqslant r\leqslant m$,

$R_{t}(r,m)\geqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2t(2^{t}-1)\ln 2}}{2^{t}\sqrt{r!}}m^{r/2}2^{m/2}(1+o(1)),$
(11)

where we consider $r$ and $t$ to be constants.

###### Proof:

By Lemma 7, we have that

$\log_{2^{t}}\left\lparen V_{2^{t},2^{m},R_{t}(r,m)}\right\rparen\geqslant
2^{m}-\sum_{i=0}^{r}\binom{m}{i}=2^{m}-\frac{m^{r}}{r!}(1+o(1)).$

According to Theorem 11,

$\frac{R_{t}(r,m)}{2^{m}}=1-\frac{1}{2^{t}}-o(1),$ (12)

and in particular, for all large enough $m$,

$\frac{R_{t}(r,m)}{2^{m}}<1-\frac{1}{2^{t}}.$

Using (7),

$\log_{2^{t}}\left\lparen V_{2^{t},2^{m},R_{t}(r,m)}\right\rparen\leqslant
2^{m}H_{2^{t}}\left\lparen\frac{R_{t}(r,m)}{2^{m}}\right\rparen.$

Combining the two inequalities above, we have

$2^{m}H_{2^{t}}\left\lparen\frac{R_{t}(r,m)}{2^{m}}\right\rparen\geqslant
2^{m}-\frac{m^{r}}{r!}(1+o(1)).$ (13)

Denote $y\triangleq 1-1/2^{t}-R_{t}(r,m)/2^{m}$. Then $y=o(1)$ by (12), and
$y>0$ for all large enough $m$. Thus, by (5) we have

$H_{2^{t}}\left\lparen\frac{R_{t}(r,m)}{2^{m}}\right\rparen=H_{2^{t}}\left\lparen
1-\frac{1}{2^{t}}-y\right\rparen=1-cy^{2}(1+o(1)),$

where $c=\frac{2^{2t}}{2t(2^{t}-1)\ln 2}$. Hence,

$1-cy^{2}(1+o(1))\geqslant 1-\frac{m^{r}}{2^{m}r!}(1+o(1)),$

and so,

$y\leqslant\frac{m^{r/2}}{2^{m/2}\sqrt{r!\cdot c}}(1+o(1)).$

The conclusion follows since $R_{t}(r,m)=(1-1/2^{t}-y)2^{m}$. ∎

###  III-B The case where $m-r$ is constant

The opposite case to the one studied in the previous section, is that of Reed-
Muller codes $\operatorname{RM}(r,m)$ with $m-r$ being constant. These codes
have a high rate and a vanishing normalized covering radius. As we show
shortly, in this asymptotic regime, the $t$-th generalized covering radius is
approximately linear in $t$. We begin, however, with the two extreme cases of
$\operatorname{RM}(m-1,m)$ and $\operatorname{RM}(m-2,m)$.

###### Proposition 13

For all $m,t\in\mathbb{N}$,

$\displaystyle R_{t}(m,m)$ $\displaystyle=0,$ $\displaystyle R_{t}(m-1,m)$
$\displaystyle=1,$ $\displaystyle R_{t}(m-2,m)$
$\displaystyle=\min\left\\{t,m\right\\}+1$

###### Proof:

The case of $R_{t}(m,m)$ is trivial since
$\operatorname{RM}(m,m)=\mathbb{F}_{2}^{2^{m}}$. For the next case,
$\operatorname{RM}(m-1,m)$ is the binary $[2^{m},2^{m}-1,2]$ parity code. Its
parity-check matrix is $H_{1}=(1,1,\dots,1)$. Then, by directly using
Definition 3, we get that for all $t\in\mathbb{N}$, $R_{t}(m-1,m)=1$.

Finally, $\operatorname{RM}(m-2,m)$ is the binary $[2^{m},2^{m}-m-1,4]$
extended Hamming code. A parity-check matrix for this code is the $(m+1)\times
2^{m}$ matrix $H_{2}$ containing all the binary column vectors that start with
a $1$. Let $\overline{e}_{i}$ denote the $i$-th standard unit column vector.
We again use Definition 3 directly: for any $1\leqslant t\leqslant m$, we
contend that the set
$\\{\overline{e}_{2},\overline{e}_{3},\dots,\overline{e}_{t+1}\\}$ cannot be
spanned by $t$ columns of $H_{2}$. That is because
$\langle\overline{e}_{2},\dots,\overline{e}_{t+1}\rangle$ is a $t$-dimensional
vector space, all of whose vectors contain a $0$ in the first coordinate.
However, the span of any $t$ columns from $H_{2}$ is, at best, a
$t$-dimensional vector space, but whose vectors’ first coordinate is not
always $0$. Thus, $R_{t}(m-2,m)\geqslant t+1$. However, given any set of $t$
column vectors of length $m+1$,
$\left\\{\overline{v}_{1},\dots,\overline{v}_{t}\right\\}$, the set is spanned
by the $t+1$ vectors
$\left\\{\overline{v}_{1}^{\prime},\overline{v}_{2}^{\prime},\dots,\overline{v}_{t}^{\prime},\overline{e}_{1}\right\\}$
where $\overline{v}_{i}^{\prime}=\overline{v}_{i}$ if the first coordinate of
$\overline{v}_{i}$ is $1$ and
$\overline{v}_{i}^{\prime}=\overline{v}_{i}+\overline{e}_{1}$ otherwise.
Clearly,
$\left\\{\overline{v}_{1}^{\prime},\overline{v}_{2}^{\prime},\dots,\overline{v}_{t}^{\prime},\overline{e}_{1}\right\\}$
are all columns of $H$, and therefore, $R_{t}(m-2,m)\leqslant t+1$. Combining
the two bounds we get that $R_{t}(m-2,m)=t+1$, for all $t\leqslant m$.
Finally, for $t>m$ the claim is trivial since
$\operatorname{rank}(H_{2})=m+1$, and any set of column vectors of length
$m+1$ can be spanned by $m+1$ linearly independent columns of $H_{2}$. ∎

Turning to the more general case of $\operatorname{RM}(m-s,m)$, we first prove
a technical lemma. The proof of this lemma is primarily based on the
estimation of binomial coefficients by Stirling’s approximation.

###### Lemma 14

Let $t\in\mathbb{N}$ be a constant, and $r=o\left\lparen 2^{m}\right\rparen$.
Then

$\log_{2^{t}}\left\lparen
V_{2^{t},2^{m},r}\right\rparen=\frac{mr}{t}-O(r\log(r)).$

###### Proof:

Since $r=o\left\lparen 2^{m}\right\rparen$, for sufficiently large $m$ we have
that $r<2^{m-1}$, and therefore

$\binom{2^{m}}{i}(2^{t}-1)^{i}\leqslant\binom{2^{m}}{i+1}(2^{t}-1)^{i+1},$

for all $0\leqslant i\leqslant r$. It follows that

$\displaystyle\binom{2^{m}}{r}2^{r(t-1)}\leqslant
V_{2^{t},2^{m},r}=\sum_{i=0}^{r}\binom{2^{m}}{i}(2^{t}-1)^{i}\leqslant(r+1)\binom{2^{m}}{r}2^{rt}.$
(14)

By Stirling’s approximation (e.g., see [11, p. 251]),

$\left\lparen\frac{2^{m}}{r}\right\rparen^{r}\leqslant\binom{2^{m}}{r}\leqslant\left\lparen
e\frac{2^{m}}{r}\right\rparen^{r}.$

Applying $\log_{2^{t}}$ and simplifying we obtain,

$\displaystyle\frac{mr}{t}-r\log_{2^{t}}\left\lparen
r\right\rparen\leqslant\log_{2^{t}}\binom{2^{m}}{r}\leqslant\frac{mr}{t}-r\log_{2^{t}}\left\lparen\frac{r}{e}\right\rparen.$
(15)

Combining (14) and (15) we have

$\displaystyle\log_{2^{t}}\left\lparen V_{2^{t},2^{m},r}\right\rparen$
$\displaystyle\leqslant\log_{2^{t}}\left\lparen(r+1)\binom{2^{m}}{r}2^{rt}\right\rparen\leqslant\log_{2^{t}}(r+1)+\frac{mr}{t}-r\log_{2^{t}}\left\lparen\frac{r}{e}\right\rparen+r$
$\displaystyle=\frac{mr}{t}-O(r\log(r)).$

Similarly,

$\displaystyle\log_{2^{t}}\left\lparen V_{2^{t},2^{m},r}\right\rparen$
$\displaystyle\geqslant\log_{2^{t}}\left\lparen\binom{2^{m}}{r}2^{r(t-1)}\right\rparen\geqslant\frac{mr}{t}-r\log_{2^{t}}\left\lparen
r\right\rparen+\frac{r(t-1)}{t}$ $\displaystyle=\frac{mr}{t}-O(r\log(r)).$

∎

We can now state the main bounds for this asymptotic regime.

###### Theorem 15

For all $m,t\in\mathbb{N}$, $3\leqslant s\leqslant m$,

$\frac{t}{(s-1)!}m^{s-2}+O(m^{s-3}\log(m))\leqslant
R_{t}(m-s,m)\leqslant\frac{t}{(s-2)!}m^{s-2}+O(m^{s-3}),$

where we consider $s$ and $t$ to be constants.

###### Proof:

In [7, Section 3] it is proved for the (first) covering radius that

$R_{1}(m-s,m)\leqslant\frac{m^{s-2}}{(s-2)!}+O(m^{s-3}).$

Combining this with Lemma 6, the upper bound follows immediately.

Having proven the upper bound, we see that $R_{t}(m-s,m)=o(2^{m})$. Thus, by
Lemma 14,

$\log_{2_{t}}\left\lparen
V_{2^{t},2^{m},R_{t}(m-s,m)}\right\rparen=\frac{mR_{t}(m-s,m)}{t}-O(m^{s-2}\log(m)).$

Combining this with the ball-covering argument from Lemma 7 and (10), it
follows that

$\displaystyle\frac{mR_{t}(m-s,m)}{t}-O(m^{s-2}\log(m))$
$\displaystyle=\log_{2_{t}}\left\lparen
V_{2^{t},2^{m},R_{t}(m-s,m)}\right\rparen\geqslant
2^{m}-\dim\left\lparen\operatorname{RM}(m-s,m)\right\rparen$
$\displaystyle=\dim\left\lparen\operatorname{RM}(s-1,m)\right\rparen=\sum_{i=0}^{s-1}\binom{m}{i}\geqslant\binom{m}{s-1}\geqslant\frac{m^{s-1}}{(s-1)!}-O(m^{s-2}).$

After rearranging we get the claim. ∎

###  III-C The case where $r/m$ is constant

The final asymptotic regime we study is when $r/m=\alpha$ is constant. For
technical reasons, we divide the discussion into two different cases:
$\frac{1}{2}<\alpha<1$, and $0<\alpha\leqslant\frac{1}{2}$. We begin with the
range $\frac{1}{2}<\alpha<1$.

###### Theorem 16

For all $m,t\in\mathbb{N}$ and $\frac{1}{2}<\alpha<1$,

$t\cdot\sqrt{\frac{1-\alpha}{8(\alpha m)^{3}}}\cdot
2^{mH_{2}(\alpha)}\cdot(1+o(1))\leqslant R_{t}(\alpha m,m)\leqslant t\cdot
4^{H_{2}(\alpha)}\cdot 2^{mH_{2}(\alpha)}\cdot(1+o(1)),$

where we consider $t$ and $\alpha$ to be constants.

###### Proof:

In [6, Theorem 9.4.25] it is proved that for $\frac{1}{2}<\alpha<1$, the
(first) covering radius satisfies

$R_{1}(\alpha m,m)\leqslant 4^{H_{2}(\alpha)}\cdot
2^{mH_{2}(\alpha)}\cdot(1+o(1)).$

By applying the subadditivity property from Lemma 6 we immediately obtain the
claimed upper bound.

For the lower bound, as in the proof of Theorem 15,

$\displaystyle\log_{2^{t}}\left\lparen V_{2^{t},2^{m},R_{t}(\alpha
m,m)}\right\rparen$
$\displaystyle\geqslant\dim\left\lparen\operatorname{RM}((1-\alpha)m-1,m)\right\rparen=\sum_{i=0}^{(1-\alpha)m-1}\binom{m}{i}$
$\displaystyle\geqslant\binom{m}{(1-\alpha)m-1}=\frac{(1-\alpha)m}{\alpha
m+1}\binom{m}{(1-\alpha)m}=\frac{1-\alpha}{\alpha}\binom{m}{(1-\alpha)m}(1+o(1))$
$\displaystyle\geqslant\sqrt{\frac{1-\alpha}{8m\alpha^{3}}}\cdot
2^{mH_{2}(\alpha)}\cdot(1+o(1)),$

where the last inequality follows from (6). By the Upper bound presented
above, $R_{t}(\alpha m,m)=o(2^{m})$, and Lemma 14 may be applied to obtain

$\frac{mR_{t}(\alpha m,m)}{t}(1+o(1))=\log_{2^{t}}(V_{2^{t},2^{m},R_{t}(\alpha
m,m)})\geqslant\sqrt{\frac{1-\alpha}{8m\alpha^{3}}}\cdot
2^{mH_{2}(\alpha)}\cdot(1+o(1)).$

By rearranging we obtain the desired lower bound. ∎

We now move on to the range $0<\alpha\leqslant\frac{1}{2}$. We begin with two
lemmas, laying the groundwork for the bounds. The first lemma is a weaker,
more general version of an upper bound on $R_{t}(r,m)$.

###### Lemma 17

For all $m,t\in\mathbb{N}$, $1\leqslant r\leqslant m$,

$R_{t}(r,m)\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}\binom{m}{r}.$

###### Proof:

We prove the claim by induction on $m$. We first observe that the the claim
holds in the extreme cases where $r=1$ and $r=m$. Since $2^{m/2}\geqslant
m=\binom{m}{1}$ for any $m\in\mathbb{N}$, by Lemma 10 we have

$R_{t}(1,m)\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}2^{\frac{m}{2}}\leqslant\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}\binom{m}{1}.$

In the case where $r=m$, $\operatorname{RM}(m,m)=\mathbb{F}_{2}^{2^{m}}$, and
thus $R_{t}(m,m)=0$ and the claim holds. In particular, this proves the claim
for $m=1,2$, serving as the induction base.

Assume the claim holds for $m-1$, and we now prove it holds for $m$. We
already know the claim holds for $R_{t}(1,m)$ and $R_{t}(m,m)$. Thus, we only
need to show it holds for $2\leqslant r\leqslant m-1$. By Proposition 8 and
the induction hypothesis,

$\displaystyle R_{t}(r,m)$ $\displaystyle\leqslant
R_{t}(r-1,m-1)+R_{t}(r,m-1)$ $\displaystyle\leqslant\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m-1}-\frac{\sqrt{2^{t}-1}}{2^{t}}\binom{m-1}{r-1}+\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m-1}-\frac{\sqrt{2^{t}-1}}{2^{t}}\binom{m-1}{r}$
$\displaystyle=\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}\binom{m}{r},$

thus completing the induction step. ∎

The next technical lemma proves the limit of $R_{t}(\alpha m,m)/2^{m}$.

###### Lemma 18

Let $0<\alpha\leqslant\frac{1}{2}$ be a constant. Then

$\lim_{m\to\infty}\frac{R_{t}(\alpha m,m)}{2^{m}}=1-\frac{1}{2^{t}}.$

###### Proof:

Using Lemma 7 and (7), we have

$\displaystyle\log_{2^{t}}\left\lparen V_{2^{t},2^{m},R_{t}(\alpha
m,m)}\right\rparen\geqslant 2^{m}-\sum_{i=0}^{\alpha m}\binom{m}{i}\geqslant
2^{m}-2^{mH_{2}(\alpha)}=2^{m}\left\lparen
1-2^{-m(1-H_{2}(\alpha))}\right\rparen.$ (16)

Assume to the contrary that $R_{t}(\alpha m,m)\leqslant\mu 2^{m}$ for some
$\mu<1-\frac{1}{2^{t}}$ and infinitely values of $m$. In that case, by (16)
and (7),

$\displaystyle H_{2^{t}}(\mu)2^{m}$
$\displaystyle\geqslant\log_{2^{t}}\left\lparen
V_{2^{t},2^{m},R_{t}(r,m)}\right\rparen\geqslant 2^{m}\left\lparen
1-2^{-m(1-H_{2}(\alpha))}\right\rparen.$

That is,

$H_{2^{t}}(\mu)\geqslant 1-2^{-m(1-H_{2}(\alpha))}.$

Since $\alpha\leqslant\frac{1}{2}$, we have $H_{2}(\alpha)<1$, and therefore
taking $m\to\infty$ we get $H_{2^{t}}(\mu)\geqslant 1$. That is a
contradiction as $\mu<1-\frac{1}{2^{t}}$. This proves that

$\displaystyle\liminf_{m\to\infty}\frac{R_{t}(\alpha m,m)}{2^{m}}\geqslant
1-\frac{1}{2^{t}}.$

From the upper bound presented in Lemma 17 we have

$\displaystyle\limsup_{m\to\infty}\frac{R_{t}(\alpha m,m)}{2^{m}}\leqslant
1-\frac{1}{2^{t}}.$

Combining these two inequalities we have claim. ∎

Using the previous two lemmas, we can now state the bound on $R_{t}(\alpha
m,m)$.

###### Theorem 19

For all $m,t\in\mathbb{N}$, and $0<\alpha\leqslant\frac{1}{2}$,

$\displaystyle\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2t(2^{t}-1)\ln 2}}{2^{t}}\cdot
2^{\frac{m}{2}(1+H_{2}(\alpha))}\cdot(1+o(1))$ $\displaystyle\qquad\leqslant
R_{t}(\alpha m,m)$ $\displaystyle\qquad\leqslant\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}\cdot\frac{1}{\sqrt{8m\alpha(1-\alpha)}}\cdot
2^{mH_{2}(\alpha)},$

where $t$ and $\alpha$ are constants.

###### Proof:

The upper bound follows immediately from (6) and Lemma 17. We turn to prove
the lower bound. By Lemma 7 and (7) again,

$\displaystyle 2^{m}H_{2^{t}}\left\lparen\frac{R_{t}(\alpha
m,m)}{2^{m}}\right\rparen\geqslant\log_{2^{t}}\left\lparen
V_{2^{t},m,R_{t}(\alpha m,m)}\right\rparen\geqslant 2^{m}-2^{mH_{2}(\alpha)}.$
(17)

Since Lemma 17 implies $R_{t}(\alpha m,m)<\lparen
1-\frac{1}{2^{t}}\rparen{2^{m}}$, we denote $y\triangleq
1-1/2^{t}-R_{t}(\alpha m,m)/2^{m}>0$. By Lemma 18, $y=o(1)$. In a similar
fashion to the proof of Theorem 12, by (5) we have

$H_{2^{t}}\left\lparen\frac{R_{t}(\alpha
m,m)}{2^{m}}\right\rparen=1-cy^{2}(1+o(1)),$

where $c=\frac{2^{2t}}{2t(2^{t}-1)\ln 2}$. Substituting this back into (17) we
get

$1-cy^{2}(1+o(1))\geqslant 1-2^{m(H_{2}(\alpha)-1)},$

and therefore,

$\displaystyle y\leqslant
c^{-\frac{1}{2}}2^{\frac{m}{2}(H_{2}(\alpha)-1)}(1+o(1)).$

Since $R_{t}(\alpha m,m)=(1-1/2^{t}-y)2^{m}$, we reach the claimed lower
bound. ∎

In the region $0<\alpha\leqslant 1-\frac{1}{\sqrt{2}}$, we follow a similar
procedure to that of [7], in order to improve the upper bound of Theorem 19.
The following lemma is a sharpening of Lemma 17, requiring more involved work.

###### Lemma 20

For all $m,t\in\mathbb{N}$, $2\leqslant r\leqslant\frac{m}{2+\sqrt{2}}$, and
$m\geqslant 3$,

$R_{t}(r,m)\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}\left\lparen
1+\sqrt{2}\right\rparen^{r-1}2^{\frac{m-1}{2}}+\frac{\sqrt{2^{t}-1}}{2^{t}\sqrt[4]{2}}r\binom{m}{r}.$

###### Proof:

Like the proof of Lemma 17, we proceed by induction on $m$. Throughout this
proof we denote the constant $\frac{\sqrt{2^{t}-1}}{2^{t}}$ by $c$. As base
cases we shall consider both the case of $m=\lceil(2+\sqrt{2})r\rceil$ and
$r\geqslant 2$, as well as the case of $r=2$ for all $m$.

Assume that $m=\lceil(2+\sqrt{2})r\rceil$ and $r\geqslant 2$. We first observe
that

$H_{2}\left\lparen\frac{1}{2+\sqrt{2}}\right\rparen=\frac{1}{2}+\frac{1}{2+\sqrt{2}}\log_{2}\left\lparen
1+\sqrt{2}\right\rparen.$ (18)

Additionally, by simply monotonicity, as well as (6) and the comment following
it,

$\binom{m}{r}=\binom{\lceil r\lparen
2+\sqrt{2}\rparen\rceil}{r}\geqslant\binom{r\lparen
2+\sqrt{2}\rparen}{r}\geqslant\frac{\sqrt[4]{2}}{\sqrt{8r}}2^{r(2+\sqrt{2})H_{2}\left\lparen\frac{1}{2+\sqrt{2}}\right\rparen}.$
(19)

We now have the following sequence of inequalities proving the first base
case,

$\displaystyle R_{t}(r,m)$ $\displaystyle\overset{(a)}{\leqslant}\left\lparen
1-\frac{1}{2^{t}}\right\rparen 2^{m}$
$\displaystyle\overset{(b)}{\leqslant}\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m}-c\left\lparen\frac{1}{1+\sqrt{2}}-\frac{\sqrt{r}}{\sqrt{8}}\right\rparen
2^{r\log_{2}(1+\sqrt{2})+\frac{r}{2}(2+\sqrt{2})}$
$\displaystyle\overset{(c)}{=}\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{c}{1+\sqrt{2}}(1+\sqrt{2})^{r}2^{\frac{r}{2}(2+\sqrt{2})}+\frac{cr}{\sqrt{8r}}2^{r(2+\sqrt{2})H_{2}\left\lparen\frac{1}{2+\sqrt{2}}\right\rparen}$
$\displaystyle\overset{(d)}{\leqslant}\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m}-c(1+\sqrt{2})^{r-1}2^{\frac{m-1}{2}}+\frac{cr}{\sqrt[4]{2}}\binom{m}{r},$

where $(a)$ follows from Lemma 17, $(b)$ follows since for all $r\geqslant 2$
we have $\frac{1}{1+\sqrt{2}}\leqslant\frac{\sqrt{r}}{\sqrt{8}}$, $(c)$
follows from (18), and $(d)$ follows since $m=\lceil(2+\sqrt{2})r\rceil$ as
well as by (19).

We now check that the claim holds for the second base case, where $r=2$. We
observe that,

$\displaystyle R_{t}(2,m)$
$\displaystyle\overset{(a)}{\leqslant}\sum_{i=2}^{m-1}R_{t}(1,i)$
$\displaystyle\overset{(b)}{\leqslant}\left\lparen
1-\frac{1}{2^{t}}\right\rparen\left\lparen\sum_{i=2}^{m-1}2^{i}\right\rparen-c\sum_{i=2}^{m-1}(\sqrt{2})^{i}$
$\displaystyle\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-c\sum_{i=2}^{m-1}(\sqrt{2})^{i}$ $\displaystyle=\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m}-c\left\lparen(1+\sqrt{2})2^{\frac{m}{2}}-\frac{2}{\sqrt{2}-1}\right\rparen,$

where $(a)$ follows by repeated application of Proposition 8 and the fact that
$R_{t}(2,2)=0$, and $(b)$ follows from Lemma 10. We note that the base case is
proved when

$\displaystyle(1+\sqrt{2})2^{\frac{m}{2}}-\frac{2}{\sqrt{2}-1}\geqslant(1+\sqrt{2})2^{\frac{m-1}{2}}-\frac{1}{\sqrt[4]{2}}\cdot
2\cdot\binom{m}{2},$ (20)

is satisfied. Indeed, one can easily check that (20) holds for all
$m\geqslant\lceil(2+\sqrt{2})2\rceil=7$.

Having completed the induction base cases, assume the claim holds for $m-1$,
i.e., for all $2\leqslant r\leqslant\frac{m-1}{2+\sqrt{2}}$. We shall now
prove the claim also holds for $m$, and all $2\leqslant
r\leqslant\frac{m}{2+\sqrt{2}}$. The two extreme cases, i.e., $r=2$, and
$m=\lceil(2+\sqrt{2})r\rceil$, have already been proved in the base cases. For
the remaining values of $r$,

$\displaystyle R_{t}(r,m)$ $\displaystyle\leqslant
R_{t}(r-1,m-1)+R_{t}(r,m-1)$ $\displaystyle\leqslant\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m-1}-c(1+\sqrt{2})^{r-2}2^{\frac{m-2}{2}}+\frac{c}{\sqrt[4]{2}}(r-1)\binom{m-1}{r-1}$
$\displaystyle\quad+\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m-1}-c(1+\sqrt{2})^{r-1}2^{\frac{m-2}{2}}+\frac{c}{\sqrt[4]{2}}r\binom{m-1}{r}$
$\displaystyle\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-c(1+\sqrt{2})^{r-1}\left\lparen 1+\frac{1}{1+\sqrt{2}}\right\rparen
2^{\frac{m-2}{2}}+\frac{cr}{\sqrt[4]{2}}\left\lparen\binom{m-1}{r}+\binom{m-1}{r-1}\right\rparen$
$\displaystyle=\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-c(1+\sqrt{2})^{r-1}2^{\frac{m-1}{2}}+\frac{cr}{\sqrt[4]{2}}\binom{m}{r},$

where the first inequality follows from Proposition 8, and then we use the
induction hypothesis. ∎

###### Theorem 21

For all $m,t\in\mathbb{N}$, and $0<\alpha<1-\frac{1}{\sqrt{2}}$,

$R_{t}(\alpha m,m)\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}(2+\sqrt{2})}2^{m\left\lparen\frac{1}{2}+\alpha\log_{2}(1+\sqrt{2})\right\rparen}(1+o(1)),$

where $t$ and $\alpha$ are constants.

###### Proof:

By Lemma 20,

$\displaystyle R_{t}(\alpha m,m)$ $\displaystyle\leqslant\left\lparen
1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}\left\lparen(1+\sqrt{2})^{\alpha
m-1}2^{\frac{m-1}{2}}-\frac{\alpha m}{\sqrt[4]{2}}\binom{m}{\alpha
m}\right\rparen$ $\displaystyle=\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}(2+\sqrt{2})}2^{m\left\lparen\frac{1}{2}+\alpha\log_{2}(1+\sqrt{2})\right\rparen}+2^{m(H_{2}(\alpha)+o(1))}$
$\displaystyle=\left\lparen 1-\frac{1}{2^{t}}\right\rparen
2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}(2+\sqrt{2})}2^{m\left\lparen\frac{1}{2}+\alpha\log_{2}(1+\sqrt{2})\right\rparen}(1+o(1)),$

where we made use of (6), and the fact that

$\frac{1}{2}+\alpha\log_{2}(1+\sqrt{2})>H_{2}(\alpha).$

∎

TABLE I: A summary of exact values $R_{t}(0,m)$ | $2^{m}-\left\lceil 2^{m-t}\right\rceil$ |  Proposition 9
---|---|---
$R_{t}(m-2,m)$ | $\min\left\\{t,m\right\\}+1$ |  Proposition 13
$R_{t}(m-1,m)$ | $1$ |  Proposition 13
$R_{t}(m,m)$ | $0$ |  Proposition 13
TABLE II: A summary of the bounds $R_{t}(r,m)$ | $\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen 2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}(1+\sqrt{2})^{r-1}2^{m/2}+O(m^{r-2})$ |  Theorem 11
---|---|---
$\geqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen 2^{m}-\frac{\sqrt{2t(2^{t}-1)\ln 2}}{2^{t}\sqrt{r!}}m^{r/2}2^{m/2}(1+o(1))$ |  Theorem 12
$R_{t}(m-s,m)$ | $\leqslant\frac{t}{(s-2)!}m^{s-2}+O(m^{s-3})$ | Theorem 15
$\geqslant\frac{t}{(s-1)!}m^{s-2}+O(m^{s-3}\log(m))$
$R_{t}(\alpha m,m)$ | $\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen 2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}(2+\sqrt{2})}2^{m\left\lparen\frac{1}{2}+\alpha\log_{2}(1+\sqrt{2})\right\rparen}(1+o(1))$ |  Theorem 21, assuming $0<\alpha<1-\frac{1}{\sqrt{2}}$
$\leqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen 2^{m}-\frac{\sqrt{2^{t}-1}}{2^{t}}\cdot\frac{1}{\sqrt{8m\alpha(1-\alpha)}}\cdot 2^{mH_{2}(\alpha)}$ |  Theorem 19, assuming $1-\frac{1}{\sqrt{2}}\leqslant\alpha\leqslant\frac{1}{2}$
$\leqslant t\cdot 4^{H_{2}(\alpha)}\cdot 2^{mH_{2}(\alpha)}\cdot(1+o(1))$ |  Theorem 16, assuming $\frac{1}{2}<\alpha<1$
$\geqslant\left\lparen 1-\frac{1}{2^{t}}\right\rparen 2^{m}-\frac{\sqrt{2t(2^{t}-1)\ln 2}}{2^{t}}\cdot 2^{\frac{m}{2}(1+H_{2}(\alpha))}\cdot(1+o(1))$ |  Theorem 19, assuming $0<\alpha\leqslant\frac{1}{2}$
$\geqslant t\cdot\sqrt{\frac{1-\alpha}{8(\alpha m)^{3}}}\cdot 2^{mH_{2}(\alpha)}\cdot(1+o(1))$ |  Theorem 16, assuming $\frac{1}{2}<\alpha<1$

##  IV Covering Algorithm

In this section we describe an algorithm which receives as input a matrix
$\mathbf{v}\in\mathbb{F}_{2}^{t\times 2^{m}}$, and returns a codeword matrix
$\mathbf{c}\in\operatorname{RM}^{t}(r,m)$ that is no farther away from
$\mathbf{v}$ than the upper bounds described in the previous section, namely

$d^{(t)}(\mathbf{v},\mathbf{c})\leqslant U_{t}(r,m),$

where $U_{t}(r,m)$ is any upper bound on $R_{t}(r,m)$ from Table II. We call
this a _covering algorithm_ , and it may be thought of as the analogue to a
decoding algorithm for an error-correcting code.

To motivate our study of a covering algorithm, we recall the motivating
example described in [10]. We look at linear data querying schemes, the most
prominent example of which is private information retrieval (PIR), in which
the user queries a database by linear combinations. We think of the database
as a sequence of elements
$\overline{x}=(x_{1},\dots,x_{m})\in\mathbb{F}^{m}_{q^{\ell}}$. The user may
query the contents of the database by providing
$\overline{s}=(s_{1},\dots,s_{m})\in\mathbb{F}^{m}_{q}$, and getting in
response the linear combination
$\overline{s}\cdot\overline{x}=\sum_{i=1}^{m}s_{i}x_{i}$. The access
complexity in such protocols is the number of database items that need to be
read in order to compute the desired linear combination. In a straightforward
implementation, the access complexity is the number of non-zero coefficients
in $s_{1},\dots,s_{m}$. Thus, in a typical PIR scheme, which selects random
coefficients, the expected fraction of non-zero coefficients is
$1-\frac{1}{q}$, resulting in a prohibitively high access complexity.

In order to reduce the access complexity one may pre-compute and store some
linear combinations of data elements. If the original database is
$\overline{x}=(x_{1},\dots,x_{m})\in\mathbb{F}_{q^{\ell}}^{m}$, the linear
combinations
$\overline{h}_{1}\cdot\overline{x},\overline{h}_{2}\cdot\overline{x},\dots,\overline{h}_{n}\cdot\overline{x}$
are pre-computed and stored instead of the original database $\overline{x}$,
where $\overline{h}_{1},\dots,\overline{h}_{n}\in\mathbb{F}_{q}^{m}$. Assume
now that the database receives a query given by
$\overline{s}\in\mathbb{F}_{q}^{m}$. If we can find $r\leqslant m$ vectors
$\overline{h}_{i_{1}},\dots,\overline{h}_{i_{r}}$ such that
$\overline{s}\in\langle\overline{h}_{i_{1}},\dots,\overline{h}_{i_{r}}\rangle$,
then we may answer the query by accessing the $r$ pre-computed linear
combinations
$\overline{h}_{i_{1}}\cdot\overline{x},\dots,\overline{h}_{i_{r}}\cdot\overline{x}$,
instead of accessing all the $m$ elements in the database,
$x_{1},\dots,x_{m}$. Considering the vectors
$\overline{h}_{1},\dots,\overline{h}_{n}$ as the columns of a parity-check
matrix $H$ of an $[n,n-m]_{q}$ linear code $C$, Definition 3 guarantees that
$r\leqslant R_{1}(C)$ such vectors may always be found. Thus, by storing the
$n$ pre-computed linear combinations instead of the original database, we
increased the storage, but we reduced the access complexity since we need to
access at most $R_{1}(C)$ elements of the database. As an additional step,
assume the database does not answer queries individually, but instead groups
together $t$ queries given by
$\overline{s}_{1},\dots,\overline{s}_{t}\in\mathbb{F}_{q}^{m}$. We now need
the $r$ vectors $\overline{h}_{i_{1}},\dots,\overline{h}_{i_{r}}$ to satisfy
$\overline{s}_{1},\dots,\overline{s}_{t}\in\langle\overline{h}_{i_{1}},\dots,\overline{h}_{i_{r}}\rangle$
in order to answer the queries. By Definition 3, $r\leqslant R_{t}(C)$ such
vectors exist, and by Lemma 6, $R_{t}(C)\leqslant tR_{1}(C)$. Thus, by
delaying the answers to queries, namely, increasing the latency, we have
further reduced the access complexity from $tR_{1}(C)$ (the access complexity
of treating $t$ queries individually) to $R_{t}(C)$.

We translate this problem into a more convenient form. Let us write the
vectors $\overline{s}_{1},\dots,\overline{s}_{t}$ as rows of a matrix
$\mathbf{s}\in\mathbb{F}_{q}^{t\times m}$. Since the parity-check matrix of
$C$ is a full-rank matrix, $H\in\mathbb{F}_{q}^{m\times n}$, by solving a set
of linear equations we can efficiently find a matrix
$\mathbf{v}\in\mathbb{F}_{q}^{t\times n}$ such that
$H\mathbf{v}^{\intercal}=\mathbf{s}^{\intercal}$. We would now like to solve
the following task: Given $\mathbf{v}\in\mathbb{F}_{q}^{t\times n}$, find
$\mathbf{c}\in C^{t}$ such that $d^{(t)}(\mathbf{v},\mathbf{c})\leqslant r$.
We observe that by finding such $\mathbf{c}$, since
$H(\mathbf{v}-\mathbf{c})^{\intercal}=\mathbf{s}^{\intercal}$, the rows of
$\mathbf{v}-\mathbf{c}$ describe linear combinations of the columns of $H$
that both result in $\overline{s}_{1},\dots,\overline{s}_{t}$, and use no more
than $r$ columns. Ideally, we would like to choose $r=R_{t}(C)$.

We call such an algorithm a _$t$ -covering algorithm for $C$, with radius
$r$_. It bears a resemblance to a decoding algorithm for an error-correcting
code, however some crucial differences are to be noted. To guarantee unique
decoding, standard decoding algorithms assume the input is a point in the
space that is no more than $\lfloor\frac{d-1}{2}\rfloor$ away from a codeword,
where $d$ is the minimum distance of the code. The covering algorithm may
receive as input _any_ point in the metric space. Additionally, the decoding
algorithm returns the closest (and only) codeword within radius of
$\lfloor\frac{d-1}{2}\rfloor$ from the input point. In contrast, the covering
algorithm may return _any_ codeword whose distance from the input as it most
$r$, and not necessarily the closest codeword. Thus, the covering algorithm
discussed here does not perform maximum-likelihood decoding.

As we saw in Section III, computing the the generalized covering radii of
Reed-Muller codes is a difficult task in general. Even for the case of $t=1$,
and despite having been studied for decades, the covering radius of Reed-
Muller codes is still not fully known. Thus, finding an efficient $t$-covering
algorithm for $\operatorname{RM}(r,m)$, with radius $R_{t}(r,m)$, poses a
great challenge, if only for the fact that $R_{t}(r,m)$ is unknown in general.
An inefficient, brute-force implementation of such an algorithm is trivial,
yet, uninteresting.

Instead, in what follows, we devise an efficient $t$-covering algorithm for
$\operatorname{RM}(r,m)$, with radius $U_{t}(r,m)$, where $U_{t}(r,m)$ is any
of the upper bounds on $R_{t}(r,m)$ found in this paper, and summarized in
Table II. Our approach stems from the fact that all the bounds in Table II are
derived recursively using the $(u,u+v)$ construction (Proposition 8) and
subadditivity (Lemma 6), as well as simple base cases.

Function  _recursive(_$\mathbf{v}$ , $r$_)_

Input : $\mathbf{v}\in\mathbb{F}_{2}^{t\times 2^{m}}$, $r\in\mathbb{N}$,
$1\leqslant r\leqslant m$

// Check edge cases

if  _$r=m$_ then return $\mathbf{v}$

if  _$r=1$_ then return
$\operatorname*{argmin}_{\mathbf{c}\in\operatorname{RM}(1,m)^{t}}d^{(t)}(\mathbf{v},\mathbf{c})$

// Use the $(u,u+v)$ recursion

Let $\mathbf{v}_{1},\mathbf{v}_{2}\in\mathbb{F}_{2}^{t\times 2^{m-1}}$ s.t.
$\mathbf{v}=(\mathbf{v}_{1},\mathbf{v}_{2})$

$\mathbf{c}_{1}\leftarrow\textnormal{{recursive}}(\mathbf{v}_{1},r)$

$\mathbf{c}_{2}\leftarrow\textnormal{{recursive}}(\mathbf{v}_{2}-\mathbf{c}_{1},r-1)$

return $(\mathbf{c}_{1},\mathbf{c}_{1}+\mathbf{c}_{2})$

Function  _subadditive(_$\mathbf{v}$ , $r$_)_

Input : $\mathbf{v}\in\mathbb{F}_{2}^{t\times 2^{m}}$, $r\in\mathbb{N}$,
$1\leqslant r\leqslant m$

// Use subadditivity

Let $\overline{v}_{i}$ be the $i$-th row of $\mathbf{v}$

forall  _$i\in[t]$_ do

$\overline{c}_{i}\leftarrow\textnormal{{recursive}}(\overline{v}_{i},r)$

return
$(\overline{c}_{1}^{\intercal},\dots,\overline{c}_{t}^{\intercal})^{\intercal}$

Function  _cover(_$\mathbf{v}$ , $r$_)_

Input : $\mathbf{v}\in\mathbb{F}_{2}^{t\times 2^{m}}$, $r\in\mathbb{N}$,
$1\leqslant r\leqslant m$

$\mathbf{c}_{\min}\leftarrow\textnormal{{recursive}}(\mathbf{v},r)$

$\mathbf{c}^{\prime}_{\min}\leftarrow\textnormal{{subadditive}}(\mathbf{v},r)$

return
$\operatorname*{argmin}_{\mathbf{c}\in\\{\mathbf{c}_{\min},\mathbf{c}^{\prime}_{\min}\\}}d^{(t)}(\mathbf{v},\mathbf{c})$

Algorithm 1 A $t$-covering algorithm for $\operatorname{RM}(r,m)$ with radius
$U_{t}(r,m)$

###### Theorem 22

For any $t,r,m\in\mathbb{N}$, $r\leqslant m$, and any
$\mathbf{v}\in\mathbb{F}_{2}^{t\times 2^{m}}$, running
$\mathbf{c}=\textnormal{{cover}}(\mathbf{v},r)$, from Algorithm 1, produces
$\mathbf{c}\in\operatorname{RM}(r,m)^{t}$ such that
$d^{(t)}(\mathbf{v},\mathbf{c})\leqslant U_{t}(r,m)$. Additionally, its run-
time complexity is $O(t2^{t}(2^{t+1})^{m+1}(2^{t+1}-1)^{-r}+tm2^{m})$.

###### Proof:

The algorithm clearly stops since, during the recursive calls, either $r$ or
$m$ strictly decrease, and the base cases of $r=1$ and $r=m$ are eventually
reached. The returned $\mathbf{c}$ is clearly a codeword, stemming from the
base cases and the $(u,u+v)$ structure of Reed-Muller codes. Finally,
$d^{(t)}(\mathbf{v},\mathbf{c})\leqslant U_{t}(r,m)$ due to Proposition 8,
Lemma 6, and the fact that all the bounds in Table II are relaxations of both
(including Theorem 15 which is based on a result from [7]).

We move on to the analysis of the run-time complexity. We first analyze
$\textnormal{{recursive}}(\mathbf{v},r)$, whose running time we denote by
$T(t,r,m)$. We contend that for some constant $c\in\mathbb{N}$,

$T(t,r,m)\leqslant f(t,r,m)\triangleq c\left\lparen
t2^{t}(2^{t+1})^{m+1}(2^{t+1}-1)^{-r}+tm2^{m}\right\rparen.$

This proof is by induction. For the first simple base case of $r=m$ we have
$T(t,m,m)=c^{\prime}$, a constant, and indeed

$T(t,m,m)=c^{\prime}\leqslant c\left\lparen
t2^{t}(2^{t+1})^{m+1}(2^{t+1}-1)^{-m}+tm2^{m}\right\rparen=f(t,m,m),$

for a proper choice of $c$. Next, we check the base case $r=1$. In this case,
a brute-force distance measurement is performed between $\mathbf{v}$ and the
codewords of $\operatorname{RM}(1,m)^{t}$. Each codeword is a $t\times 2^{m}$
matrix, and we have a total of
$\lvert\operatorname{RM}(1,m)^{t}\rvert=2^{(m+1)t}$ such codewords. Thus, for
some constant $c^{\prime}$,

$T(t,1,m)=c^{\prime}\cdot t2^{m}\cdot 2^{(m+1)t}\leqslant c\left\lparen
t2^{t}(2^{t+1})^{m+1}(2^{t+1}-1)^{-1}+tm2^{m}\right\rparen=f(t,1,m),$

for any $c\geqslant c^{\prime}$. Moving on to the main recursion, assume the
claim holds for $T(t,r,m-1)$, for all $1\leqslant r\leqslant m-1$, and we
prove it also holds for $T(t,r,m)$ for all $1\leqslant r\leqslant m$. If $r=1$
or $r=m$, we have a base case which we have already proved. Otherwise, the
algorithm manipulates a $t\times 2^{m}$ matrix and runs two recursive
instances. Hence, for some constant $c^{\prime}$, and after choosing any
$c\geqslant c^{\prime}$, we have

$\displaystyle T(t,r,m)$
$\displaystyle=c^{\prime}t2^{m}+T(t,r-1,m-1)+T(t,r,m-1)$
$\displaystyle\leqslant ct2^{m}+c\left\lparen
t2^{t}(2^{t+1})^{m}(2^{t+1}-1)^{-r+1}+t(m-1)2^{m-1}\right\rparen+c\left\lparen
t2^{t}(2^{t+1})^{m}(2^{t+1}-1)^{-r}+t(m-1)2^{m-1}\right\rparen$
$\displaystyle=c\left\lparen
t2^{t}(2^{t+1})^{m+1}(2^{t+1}-1)^{-r}+tm2^{m}\right\rparen$
$\displaystyle=f(t,r,m).$

This completes the induction. To complete the proof as well, we note that the
complexity of $\textnormal{{subadditive}}(\mathbf{v},r)$ is always subsumed by
the complexity of $\textnormal{{recursive}}(\mathbf{v},r)$. ∎

As in the previous section, we analyze three asymptotic regimes for $r$ and
$m$:

###### Corollary 23

Let $t\in\mathbb{N}$ be a constant, let $n=2^{m}$ be the length of the code
$\operatorname{RM}(r,m)$, and denote
$\beta\triangleq\log_{2}\sqrt[t+1]{2^{t+1}-1}$. Then the run-time complexity
of Algorithm 1 is:

  * •

$O(n^{t+1})$ when $r$ is constant.

  * •

$O(n^{(t+1)(1-\alpha\beta)})$ when $r=\alpha m$, and
$0<\alpha<\frac{t}{(t+1)\beta}$ is a constant.

  * •

$O(n\log n)$ when $r=m-s$, $s$ is constant, or when $r=\alpha m$, and
$\frac{t}{(t+1)\beta}\leqslant\alpha<1$ is a constant.

###### Proof:

This is a straightforward application of Theorem 22. The
$\frac{t}{(t+1)\beta}$ cutoff point stems from the fact that the complexity is
in fact $O(n^{(t+1)(1-\alpha\beta)}+n\log n)$. Thus, for
$\alpha<\frac{t}{(t+1)\beta}$, we have that $(t+1)(1-\alpha\beta)>1$, and
$n^{(t+1)(1-\alpha\beta)}$ dominates the complexity. However, when
$\alpha\geqslant\frac{t}{(t+1)\beta}$, we have that
$(t+1)(1-\alpha\beta)\leqslant 1$ and $n\log n$ dominates the complexity. ∎

##  V Conclusion

In this work, we studied the generalized covering radii of Reed-Muller codes,
$R_{t}(r,m)$. In some simple cases we found the exact generalized covering
radii (see Table I). For most other cases we found lower and upper bounds on
the generalized covering radii (see Table II). These bounds were found in
three asymptotic regimes: $r$ constant, $m-r$ constant, and $r/m$ constant. We
also constructed a $t$-covering algorithm with radius no worse than the upper
bounds that we found (see Algorithm 1). We analyzed the algorithm’s run-time
complexity and showed it is polynomial in the code parameters.

We remark that our upper bounds on the covering radii of Reed-Muller codes may
also be used for the study of the asymptotic behaviour of generalized covering
radii of linear codes in general. Given the parameters $t\in\mathbb{N}$,
$\rho\in[0,1]$ and a prime power $q$, the asymptotic minimal rate of a code
over $\mathbb{F}_{q}$ with a normalized $t$-th generalized covering radius of
no more than $\rho$, is denoted by $\kappa_{t}(\rho,q)$. Since the $t$-th
generalized covering radius of a direct sum of codes is the sum of the $t$-th
generalized covering radii of its component codes (see [10, Prop. 25]), an
$[n,k]_{q}$ linear code with $t$-th generalized covering radius of $r$
immediately creates an infinite family of codes with rate $\frac{k}{n}$ and
normalized $t$-th generalized covering radius $\frac{r}{n}$. It then follows
that $\kappa_{t}(r/n,q)\leqslant k/n$. By the monotonicity of
$\kappa_{t}(\rho,q)$ in $\rho$, this upper bound holds for all $\rho\geqslant
r/n$. Thus, our upper bounds on the generalized covering radii of Reed-Muller
codes (denoted by $U_{t}(r,m)$) give the following upper bounds:

$\kappa_{t}(\rho,2)\leqslant\frac{\dim\left\lparen\operatorname{RM}(r,m)\right\rparen}{2^{m}}\text{
for all }\rho\geqslant\frac{U_{t}(r,m)}{2^{m}}$ (21)

In Figure 1, the bound obtained by applying (21) in the range $2\leqslant
m\leqslant 20$, $1\leqslant r\leqslant m$ in the case where $t=3$ is
presented. Each pair $(r,m)$, results in a point depicted in the graph. We
observe that some of the points obtained in this way improve upon the upper
bound from [10, Prop. 14],

$\kappa_{t}(\rho,q)\leqslant 1-H_{q}\left\lparen\frac{\rho}{t}\right\rparen,$
(22)

where $H_{q}(\cdot)$ is the $q$-ary entropy function. A similar comparison,
with $t=2$, is shown in Figure 2. However, specifically for $t=2$, the upper
bound of [10, Theorem 22] is stronger than (22), and so the bound of (21)
offers no improvement.

\begin{overpic}[scale={0.4}]{B1.pdf}
\put(-4.0,35.0){\begin{turn}{90.0}$\kappa_{3}(\rho,2)$\end{turn}}
\put(55.0,-1.0){$\rho$} \put(23.0,30.0){(a)} \put(48.0,26.0){(b)}
\put(76.0,18.8){(c)} \end{overpic} Figure 1:  A comparison of the bounds on
$\kappa_{3}(\rho,2)$: (a) the ball-covering lower bound [10, Prop. 12], (b)
the general upper bound [10, Prop. 14], and (c) our upper bound obtained from
the upper bound on the $t$-th generalized covering radius of Reed-Muller
codes.  \begin{overpic}[scale={0.54}]{B3.pdf}
\put(-4.0,35.0){\begin{turn}{90.0}$\kappa_{2}(\rho,2)$\end{turn}}
\put(55.0,-1.0){$\rho$} \put(17.0,30.0){(a)} \put(28.0,26.0){(b)}
\put(63.0,15.0){(c)} \end{overpic} Figure 2:  A comparison of the bounds on
$\kappa_{2}(\rho,2)$: (a) the ball-covering lower bound [10, Prop. 12], (b)
the improved upper bound [10, Thm. 22], and (c) our upper bound obtained from
the upper bound on the $t$-th generalized covering radius of Reed-Muller
codes.

We would like to mention a couple of interesting open questions pertaining to
the results of this paper. We first observe that, apart from the base cases,
our bounds are obtained using the $(u,u+v)$ recursion, and subadditivity. We
suspect that for improved bounds, a different approach may be needed, perhaps
an approach that exploits the unique geometric and combinatorial properties of
Reed-Muller codes.

Another open problem concerns Algorithm 1. The edge case of
$\operatorname{RM}(1,m)$ is solved in the algorithm using a brute-force
approach: the distance between the input, $\mathbf{v}$, and the codewords of
$\operatorname{RM}(1,m)^{t}$ is measured exhaustively and naively. However,
for $t=1$, the codewords of $\operatorname{RM}(1,m)$ form a Sylvester-type
Hadamard matrix and its complement. Thus, by using the Walsh-Hadamard
transform, an efficient measurement of the distance from $\mathbf{v}$ to the
codewords of $\operatorname{RM}(1,m)$ is possible in $O(n\log n)$ time,
instead of the $\Theta(n^{2})$ of a naive implementation, where $n=2^{m}$ is
the code length. Whether a similar approach can improve Algorithm 1 is still
unknown.

Finally, and more generally, it is known that the generalized covering radii
are monotone non-decreasing in $t$. Thus, any improvement in the bounds on
$R_{t}(r,m)$ may perhaps bring about an improvement in the bounds on the
(regular) covering radius of Reed-Muller codes, $R_{1}(r,m)$. These problems,
and others, are left for future research.

## References

  * [1] E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller codes for random erasures and errors,” _IEEE Trans. Inform. Theory_ , vol. 61, no. 10, pp. 5229–5252, 2015.
  * [2] E. Abbe, A. Shpilka, and M. Ye, “Reed-Muller codes: Theory and algorithms,” _IEEE Trans. Inform. Theory_ , vol. 67, no. 6, pp. 3251–3277, 2021.
  * [3] E. Abbe and M. Ye, “Reed-Muller codes polarize,” _IEEE Trans. Inform. Theory_ , vol. 66, no. 12, pp. 7311–7332, 2020.
  * [4] Y. Borissov, A. Braeken, S. Nikova, and B. Preneel, “On the covering radii of binary Reed-Muller codes in the set of resilient Boolean functions,” _IEEE Trans. Inform. Theory_ , vol. 51, no. 3, pp. 1182–1189, 2005.
  * [5] C. Carlet and S. Mesnager, “Improving the upper bounds on the covering radii of binary Reed-Muller codes,” _IEEE Trans. Inform. Theory_ , vol. 53, no. 1, pp. 162–173, 2006.
  * [6] G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, _Covering codes_. Elsevier, 1997.
  * [7] G. Cohen and S. Litsyn, “On the covering radius of Reed-Muller codes,” _Discrete Math._ , vol. 106, pp. 147–155, 1992.
  * [8] J. A. Davis and J. Jedwab, “Peak-to-mean power control in OFDM, Golay complementary sequences, and Reed-Muller codes,” _IEEE Trans. Inform. Theory_ , vol. 45, no. 7, pp. 2397–2417, 1999.
  * [9] ——, “Peak-to-mean power control and error correction for OFDM transmission using Golay sequences and Reed-Muller codes,” _Electronics Letters_ , vol. 33, no. 4, pp. 267–268, 1997.
  * [10] D. Elimelech, M. Firer, and M. Schwartz, “The generalized covering radii of linear codes,” _arXiv preprint arXiv:2012.06467_ , 2020.
  * [11] R. L. Graham, D. E. Knuth, and O. Patashnik, _Concrete Mathematics: A Foundation for Computer Science_. Addison-Wesley, 1994.
  * [12] V. Guruswami, A. Rudra, and M. Sudan, _Essential Coding Theory_. https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/, 2019.
  * [13] T. Helleseth, T. Kløve, and J. Mykkeltveit, “On the covering radius of binary codes,” _IEEE Trans. Inform. Theory_ , vol. 24, no. 5, pp. 627–628, 1978.
  * [14] X.-D. Hou, “Further results on the covering radii of the Reed-Muller codes,” _Designs, Codes and Cryptography_ , vol. 3, no. 2, pp. 167–177, 1993\.
  * [15] ——, “On the norm and covering radius of the first-order Reed-Muller codes,” _IEEE Trans. Inform. Theory_ , vol. 43, no. 3, pp. 1025–1027, 1997\.
  * [16] ——, “Some results on the covering radii of Reed-Muller codes,” _IEEE Trans. Inform. Theory_ , vol. 39, no. 2, pp. 366–378, 2006.
  * [17] S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoǧlu, and R. L. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” _IEEE Trans. Inform. Theory_ , vol. 63, no. 7, pp. 4298–4316, 2017.
  * [18] K. Kurosawa, T. Iwata, and T. Yoshiwara, “New covering radius of Reed-Muller codes for $t$-resilient functions,” _IEEE Trans. Inform. Theory_ , vol. 50, no. 3, pp. 468–475, 2004.
  * [19] F. J. MacWilliams and N. J. A. Sloane, _The Theory of Error-Correcting Codes_. Elsevier, 1977.
  * [20] A. M. McLoughlin, “The covering radius of the $(m-3)$rd order Reed Muller codes and a lower bound on the $(m-4)$th order Reed Muller codes,” _SIAM J. Appl. Math._ , vol. 37, no. 2, pp. 419–422, 1979.
  * [21] Q. Meng, H. Zhang, M. Yang, and Z. Wang, “Analysis of affinely equivalent Boolean functions,” _Science in China Series F: Information Sciences_ , vol. 50, no. 3, pp. 299–306, 2007.
  * [22] J. Mykkeltveit, “The covering radius of the $(128,8)$ Reed-Muller code is $56$,” _IEEE Trans. Inform. Theory_ , vol. 26, no. 3, pp. 359–362, 1980\.
  * [23] K. G. Paterson, “Generalized Reed-Muller codes and power control in OFDM modulation,” _IEEE Trans. Inform. Theory_ , vol. 46, no. 1, pp. 104–120, 2000.
  * [24] N. J. Patterson and D. H. Wiedemann, “The covering radius of the $(215,16)$ Reed-Muller code is at least $16276$.” _IEEE Trans. Inform. Theory_ , vol. 29, no. 3, pp. 354–355, 1983.
  * [25] J. Schatz, “The second order Reed-Muller code of length $64$ has covering radius $18$,” _IEEE Trans. Inform. Theory_ , vol. 27, no. 4, pp. 529–530, 1981.
  * [26] K.-U. Schmidt, “Complementary sets, generalized Reed-Muller codes, and power control for OFDM,” _IEEE Trans. Inform. Theory_ , vol. 53, no. 2, pp. 808–814, 2007.
  * [27] A. Tietäväinen, “Covering radius and dual distance,” _Designs, Codes and Cryptography_ , vol. 1, pp. 31–46, 1991.
  * [28] V. K. Wei, “Generalized Hamming weights for linear codes,” _IEEE Trans. Inform. Theory_ , vol. 37, no. 5, pp. 1412–1418, Sep. 1991.
  * [29] S. Yekhanin, _Locally Decodable Codes_. Now, 2012.


oethe-Universität Frankfurt - Frankfurt am Main, Germany

# Dielectrons at the LHC – Chances and challenges

Harald Appelshäuser (ALICE Collaboration) GG

###### Abstract

Dielectrons are unique observables in ultra-relativistic heavy-ion collisions.
Thanks to their penetrating nature, they carry information from all stages of
the collision and can provide knowledge about pre-equilibirium dynamics, QGP
temperature and transport coefficients, and chiral symmetry restoration. On
the other hand, experimental challenges are enormous because production cross
sections are small and the signal of interest is eclipsed by a huge
combinatorial and physics background from light- and heavy-flavour hadron
decays. In this talk the status of dielectron measurements with ALICE is shown
and the perspectives with the recently installed and planned ALICE detector
upgrades are discussed.

##  1 Introduction

Owing to their electromagnetic nature and correspondingly large mean free path
in strongly interacting matter, photons and dielectrons are unique tools in
the study of the properties of hot and dense QCD matter created in high-energy
heavy-ion collisions [1], in particular the quark-gluon plasma (QGP). They are
generated at all stages of the system evolution [2] and transport undisturbed
information from the early, hot phase of the reaction into the final state.
Beyond thermal radiation from quark-gluon plasma and the subsequent dense
hadronic system [3, 4], photons and dielectrons are also considered as
important messengers of the very early stage of the collision, characterizing
the dynamics towards equilibration [5, 6].

On the other hand, a conceptual complication arises from the fact that the
observed electromagnetic radiation is integrated over the different collision
stages and needs to be disentangled in the final state. In this respect, there
is a clear advantage for dielectrons since, in contrast to photons, they carry
mass and therefore additional kinematic information that allows the
contributions of different phases to be separated [3]. While radiation from
the QGP dominates the invariant mass ($m_{\rm ee}$) range above 1 GeV/$c^{2}$,
contributions below emerge predominantly from the hadronic phase. This allows
the properties of the QGP to be examined, these properties include its early
temperature, equation of state and effective degrees of freedom, as well as
the properties of hadrons in the medium, which currently represents the most
promising experimental approach to exploring the chiral properties of the QCD
phase transition [7, 8].

On the technical side, dielectrons suffer from lower production rates than
photons due to an extra factor of the electromagnetic coupling constant
$\alpha_{\rm EM}$. On the other hand, photon measurements are limited by
systematic uncertainties arising from the huge background from electromagnetic
decays of short-lived hadrons. Hadronic backgrounds to dielectrons are large
as well, in particular at the highest collider energies, but arise mainly from
correlated weak decays of hadrons with charm or beauty quarks. Experimental
means to suppress these contributions are being developed.

The thermal dielectron yield is determined by the space-time integral over the
thermal emission rate described by the McLerran-Toimela formula [9]:

$\frac{{\rm d}N_{\rm ee}}{{\rm d}^{4}x{\rm
d}^{4}q}=-\frac{\alpha^{2}}{\pi^{3}m_{\rm ee}^{2}}f^{BE}(q_{0},T){\rm
Im}\Pi_{EM}(m_{\rm ee},q,\mu_{B},T).$ (1)

For a structureless spectral function ${\rm Im}\Pi_{EM}$, as is the case at
dielectron masses above the hadron-parton duality threshold at $m_{\rm
ee}\approx 1$ GeV/$c^{2}$, the dielectron yield follows a simple exponential
given by the Bose-Einstein weight $f^{BE}(q_{0},T)$. In this mass region, the
dielectron yield is dominated by radiation from the early phase due to its
higher temperature and allows a straight-forward determination of the
effective QGP temperature by an exponential fit to the data. At lower masses,
radiation from the hadronic phase dominates due to the much larger space-time
volume and the spectral function exhibits a non-trivial shape, depending on
$T$ and $\mu_{B}$. Below $T_{c}$ its properties reflect hadronic degrees of
freedom in finite $T$ and $\mu_{B}$ that are related to chiral symmetry
restoration. Extraction of the medium temperature from low-mass data therefore
requires additional assumptions, i.e. that the spectral function at $m_{\rm
ee}<1$ GeV/$c^{2}$ becomes structureless as well in the relevant range of $T$
and $\mu_{B}$.

Heavy-ion collisions at the LHC produce the hottest, largest, and longest-
lived system to date which makes the LHC the ideal place to investigate the
properties of the QGP. On the other hand, dielectron studies at the LHC are
complicated by huge combinatorial and physical backgrounds. In particular, the
large cross section for charm and beauty production and the large branching
ratios into correlated semi-leptonic weak decays pose a huge challenge for
analysis. In the so-called intermediate-mass region (IMR) between the $\phi$\-
and $J/\psi$-meson peaks, the contributions from heavy-flavor decays outshine
the expected thermal dielectron yield by about one order of magnitude. A very
precise knowledge of the heavy-flavour contributions is therefore essential
for any thermal dielectron analysis at collider energies. In this
presentation, the current experimental situation at the LHC is reviewed and
the prospects for future dielectron measurements with ALICE are discussed.

##  2 Charm and beauty production - constraints from pp and p–Pb collisions

Figure 1: Dielectron $p_{\rm T,ee}$ (left) and $m_{\rm ee}$ (right)
distributions in pp collisions at $\sqrt{s}=5.02$ TeV together with the fitted
contributions from $c\bar{c}$ and $b\bar{b}$ decays (from [12]).

Constraints on charm and beauty production in lead-lead (Pb–Pb) collisions can
be derived from measurements in smaller collision systems. Dielectron
reference data from proton-proton (pp) and proton-lead (p–Pb) collisions at
the same centre-of-mass energy $\sqrt{s_{\rm NN}}$ and with the same
experimental setup are particularly useful because sytematic uncertainties
arising from uncertainties of branching ratios and phase-space extrapolations
cancel. ALICE [10, 11] has conducted a comprehensive dielectron program in pp,
p–Pb, and Pb–Pb collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV from LHC Run 2 [12,
13] .

Dielectron yields in pp collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV are shown
in Fig. 1. The left panel shows the dielectron-pair transverse-momentum
($p_{\rm T,ee}$) distribution in the IMR where, in pp collisions, heavy-
flavour decays are expected to dominate the yield by far. A combined fit of
$c\bar{c}$ and $b\bar{b}$ distributions, modeled by PYTHIA6 [14] and POWHEG
[15, 16, 17, 18], yield slightly different relative contributions from charm
and beauty for the two generators, but both describe the inclusive $p_{\rm
T,ee}$ spectrum equally well. The right panel shows the same data as a
function of $m_{\rm ee}$ compared to POWHEG where also contributions from
light-flavour mesons (green) and $J/\psi$ (blue) are included [12]. A very
good description of the measured dielectron yield is observed. The $c\bar{c}$
and $b\bar{b}$ yields obtained from the fit of POWHEG templates to pp data are
used as input for the construction of the so-called hadronic cocktail in p–Pb
and Pb–Pb collisions, as shown in the following.

Figure 2 (left panel) shows the dielectron invariant mass spectrum in p–Pb
collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV [12]. The data are compared to a
hadronic decay cocktail composed of contributions from light-flavour hadrons
(green), $J/\psi$ (blue) and the POWHEG-based fitted contribution measured in
pp (see above), scaled by the mass number $A=208$. The description is
reasonable within systematic uncertainties, however, a slight tension is
observed at low and intermediate mass.

The nuclear modification factor $R_{\rm pPb}$

$R_{\rm pPb}(m_{\rm ee})=\frac{1}{A}\frac{{\rm d}\sigma_{\rm ee}^{\rm
pPb}/{\rm d}m_{\rm ee}}{{\rm d}\sigma_{\rm ee}^{\rm pp}/{\rm d}m_{\rm ee}}$
(2)

is shown on the right panel of Fig. 2 together with the corresponding ratio of
the cocktails [12]. A suppression below unity is expected at low mass because
the dominant light-flavor contribution in the cocktail does not scale with
$A$. Below $m_{\rm ee}\approx 1$ GeV/$c^{2}$, however, the data tend to be
below the cocktail, possibly indicating cold nuclear matter (CNM) effects in
the Pb-nucleus. A cocktail based on nuclear parton distribution functions from
EPS09 [19] yields a better description of the data at low mass, however, it
slightly underpredicts the measured $R_{\rm pPb}$ in the IMR. This may be
compatible with a small additional contribution from thermal radiation, as
shown by the dashed red line [4]. The present dielectron data in p–Pb are
compatible with a suppression observed in the $R_{\rm pPb}$ of Dmesons below
$p_{\rm T}=2$ GeV/$c$ [20, 21]. The clarification of a possible thermal
dielectron contribution in p–Pb collisions requires higher-precision data that
will be collected by the upgraded ALICE apparatus in LHC Run 3 and 4 (see
below).

Figure 2: Left: dielectron $m_{\rm ee}$ distributions in p–Pb collisions at
$\sqrt{s_{\rm NN}}=5.02$ TeV compared to a cocktail of expected hadronic decay
contributions. Right: dielectron $R_{\rm pPb}$ compared to different cocktails
and a calculation including a thermal dielectron contribution (see text)(from
[12]).

##  3 Search for QGP radiation in Pb–Pb

Figure 3 shows recently published results of dielectron production in Pb–Pb
collisions from LHC Run2 in 2018 [13]. The upper left panel shows the $m_{\rm
ee}$ spectrum in central (0-10%) collisions together with a comparison to the
expected yields from hadronic decay cocktails and model calculations. Cocktail
1 employs the measured heavy-flavour contribution in pp collision at the same
$\sqrt{s_{\rm NN}}$ (see Fig. 1), scaled by the mass number $A=208$. In the
middle panel, the ratio of data to cocktail is shown. In the low-mass region
($0.18<m_{\rm ee}<0.5$ GeV/$c^{2}$) the data exceed the cocktail by a factor
$1.42\pm 0.12(\rm{stat.})\pm 0.17(\rm{syst.})\pm 0.12(\rm{cocktail})$. The
data are compatible with calculations from the PHSD transport model [22] and a
hadronic many-body approach [4] which indicates a strong in-medium
modification of the $\rho$ spectral function at the LHC. In the mass range
$0.5<m_{\rm ee}<1$ GeV/$c^{2}$ the data are compatible with the cocktail
within large experimental uncertainties. In the IMR, however, the data tend to
be below the cocktail. This finding may be compatible with CNM effects and
final-state modifications of charmed hadrons in nuclear collisions, as
observed in D-meson nuclear modification factors $R_{\rm AA}$ [23]. In
Cocktail 2, nuclear effects are taken into account by folding Cocktail 1 with
initial- and final-state effects from EPS09 and measured heavy-flavour
electron $R_{\rm AA}$ results from central Pb–Pb collisons [24], respectively.
Comparison to data yields a better agreement than in the case of Cocktail 1
(see Fig. 3 lower left panel). However, the procedure to include nuclear
effects from EPS09 and Pb–Pb data gives rise to a sizeable increase of the
systematic uncertainties of the cocktail, rendering the observation of
possible excess due to thermal dielectron radiation from the QGP impossible.
This is demonstrated in the right panel of Fig. 3 where Cocktail 2 is
subtracted from the data. Cocktail-agnostic strategies must therefore be
persued to isolate thermal QGP radiation at the LHC.

Figure 3: Upper left: dielectron $m_{\rm ee}$ distributions in the 10% most
central Pb–Pb collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV, compared to two
different hadronic decay cocktails and models (see text). Middle and bottom
left: ratios of data and models to cocktails. Right: excess yield of
dielectrons with respect to the known hadronic sources compared to model
calculations (from [13]).

##  4 Topological separation of dielectron sources

Typical weak decay lengths of a few hundred $\mu$m of hadrons with charm or
beauty quarks can be measured with Si-based vertex detectors such as the Inner
Tracking System (ITS) [10] of ALICE. To this end, the normalized pair
distance-of-closest-approach (${\rm DCA}_{\rm ee}$) is evaluated for each
dielectron candidate:

${\rm DCA}_{\rm ee}=\sqrt{\frac{{\rm DCA}_{1}^{2}+{\rm DCA}_{2}^{2}}{2}}$ (3)

where ${\rm DCA}_{1}$ and ${\rm DCA}_{2}$ are the distances-of-closest-
approach of the electron and positron tracks to the main collision vertex in
the transverse plane. This technique was pioneered by the NA60 collaboration
for dimuons in the forward hemisphere [25]. Recently, a first ${\rm DCA}_{\rm
ee}$ analysis with dielectrons at midrapidity was performed at the LHC, see
Fig. 4 [13]. The left panel shows the distribution ${\rm DCA}_{\rm ee}$,
normalized to the resolution $\sigma$, in the mass region around the $J/\psi$.
Also shown are the expectations from the hadronic cocktail, where the shapes
of the ${\rm DCA}_{\rm ee}$ distributions are generated by a Monte-Carlo (MC)
simulation. The cocktail contains prompt and non-prompt $J/\psi$, and
correlated decays from $c\bar{c}$ and $b\bar{b}$ pairs including initial- and
final-state modifications as implemented in Cocktail 2. Data and cocktail
agree well over the full measured ${\rm DCA}_{\rm ee}$ range. In the right
panel of Fig. 4 the ${\rm DCA}_{\rm ee}$ distribution in the IMR is shown.
While the $J/\psi$ yield is constrained from data, the yields from $c\bar{c}$
and $b\bar{b}$ are now unconstrained from cocktails. In addition, a prompt
dielectron contribution is included in the fit. The best fit implies a
reduction by a factor $0.43\pm 0.4(\rm{stat.})\pm 0.22(\rm{syst.})$ for
$c\bar{c}$ and $0.74\pm 0.24(\rm{stat.})\pm 0.12(\rm{syst.})$ for $b\bar{b}$
with respect to the expectation from Cocktail 1. At the same time, the fit
favours a finite prompt contribution that yields $3.17\pm 3.81(\rm{stat.})\pm
0.35(\rm{syst.})$ and $1.15\pm 1.38(\rm{stat.})\pm 0.13(\rm{syst.})$ times the
contribution from the hadronic many-body and PHSD calculations, respectively.
For the first time at the LHC a hint for a prompt thermal dielectron component
is observed in the IMR with small systematic uncertainties, albeit with a
statistical significance of only $1\sigma$. Nevertheless, this study opens the
door for the next generation of high-precision measurements with the upgraded
ALICE detector in Runs 3 and 4.

Figure 4: Left: dielectron yield in the 10% most central Pb–Pb collisions at
$\sqrt{s_{\rm NN}}=5.02$ TeV as a function of ${\rm DCA}_{\rm ee}$ in
$2.6<m_{\rm ee}<3.1$ GeV/$c^{2}$, compared with a cocktail of expected
sources. Right: fit of the dielectron yield in $1.2<m_{\rm ee}<2.6$
GeV/$c^{2}$. Bottom panels: ratios of data to cocktail.

##  5 First dielectron measurements with ALICE in Run 3

In preparation of the LHC Runs 3 and 4 the ALICE apparatus underwent a
significant upgrade. The TPC, which is main tracking and electron
identification detector, was equipped with a GEM-based, continuous readout
system [26], allowing an increase of the readout rate by a factor 100 (in
Pb–Pb) to 1000 (in pp) with respect to Run 1 and 2. A new all-pixel inner
tracking system (ITS2) was installed which improves the pointing resolution of
charged-particle tracks by a factor 3 (5) in the $xy$\- ($z$-) direction [27].
This enables a 3D definition of the dielectron DCA, ${\rm DCA}_{\rm ee}^{\rm
3D}$, which enhances significantly the capabilities to seperate prompt
dielectrons from heavy-flavour decays.

First dielectron measurements made with 1 pb-1 of pp collision data, recorded
with the upgraded ALICE detector in Run 3, are shown in Fig. 5. The left panel
shows ${\rm DCA}_{\rm ee}^{\rm 3D}$ in two different $m_{\rm ee}$ intervals.
The blue distribution ($0.08<m_{\rm ee}<0.14$ GeV/$c^{2}$) is dominated by
prompt Dalitz decays of $\pi^{0}$-mesons, while the red distribution
($1.1<m_{\rm ee}<2.7$ GeV/$c^{2}$) is populated almost exclusively by heavy-
flavour decays. While the blue distribution represents the detector
resolution, the red distribution exhibits a clear tail owing to the finite
lifetime of the hadrons which can be resolved with the ITS2. The effect of
tight cuts on ${\rm DCA}_{\rm ee}^{\rm 3D}$ on the inclusive $m_{\rm ee}$
spectrum is shown in the right panel of Fig. 5. While a selection on ${\rm
DCA}_{\rm ee}^{\rm 3D}<0.5\sigma$ enhances the prompt contributions from
Dalitz decays and vector mesons, including the $\psi^{\prime}$ (blue points),
a selection ${\rm DCA}_{\rm ee}^{\rm 3D}>2\sigma$ produces the expected
continuum from heavy-flavour decays and a peak from non-prompt $J/\psi$ from
$b$-decays. This demonstrates the unprecedented precision in the pointing
resolution of ITS2 and highlights the large potential for isolating the prompt
thermal dielectron contribution in the IMR from the huge background from
hadron decays.

Figure 5: Left: ${\rm DCA}_{\rm ee}^{\rm 3D}$ distributions in different
$m_{\rm ee}$ intervals in pp collisions at $\sqrt{s}=13.6$ TeV from Run 3.
Right: inclusive raw dielectron yield (black histogram) and after cuts in
${\rm DCA}_{\rm ee}^{\rm 3D}$ (blue and red) as a function of $m_{\rm ee}$.

##  6 Outlook

The upgraded ALICE detector at the LHC will enable high-precision dielectron
measurements in pp, p–Pb, and Pb–Pb collisions thanks to its improved pointing
resolution and increased readout rate via continuous readout. A further
increase of the sensitivity will be achieved by a new vertex tracker (ITS3)
for Run 4 which improves the pointing resolution by another factor of about 3
[28]. These upgrades will allow for a precise discrimination of prompt and
non-prompt dielectrons, enabling a comprehensive study of in-medium
modifications of hadrons and its connection to chiral symmetry restoration,
and an exploration of the early temperature of the system. Furthermore, a
measurement of azimuthal anisotropies of thermal dielectrons can give access
to early collectivity of the system and the partonic equation of state.
Polarization measurements at high invariant masses between $J/\psi$ and
$\Upsilon$ may yield a better understanding of early equilibration processes
and provide an independent assessment of the specific viscosity $\eta/s$ of
the partonic system [5, 6]. Dedicated runs at reduced magnetic field will also
consolidate recent hints for a new dielectron source in pp collisions at very
low $m_{\rm ee}$ and $p_{\rm T,ee}$ [29].

A next-generation heavy-ion experiment ALICE 3 is proposed to continue
precision studies of a large number of observables during LHC Runs 5 and 6. In
the dielectron sector, unprecedented rate capability, pointing resolution and
sensitivity at very low $p_{\rm T}$ will enable precision studies of the time
evolution of the early temperature and collectivity, and spectral
modifications related to chiral symmetry restoration [30]. Furthermore, there
will be access to yet unexplored phenomena at very low $p_{\rm T}$ such as the
emergence of soft dielectrons connected to the Low theorem [31] and a possible
measurement of the electric conductivity of the QGP [32].

## References

  * [1] ALICE Collaboration The ALICE experiment – A journey through QCD, arXiv:2211.04384 [nucl-ex].
  * [2] Gale A. Photon Production in Hot and Dense Strongly Interacting Matter, Landolt-Bornstein232010445, arXiv:0904.2184 [hep-ph].
  * [3] Rapp R. van Hees H. Thermal Dileptons as Fireball Thermometer and Chronometer, Phys. Lett. B7532016586-590, arXiv:1411.4612 [hep-ph].
  * [4] Rapp R. Dilepton Spectroscopy of QCD Matter at Collider Energies, Adv. High Energy Phys.20132013148253, arXiv:1304.2309 [hep-ph].
  * [5] Coquet M., Du X., Ollitraut J.-Y., Schlichting S., Winn M. Intermediate mass dileptons as pre-equilibrium probes in heavy ion collisions, Phys. Lett. B8212021136626, arXiv:2104.07622 [nucl-th].
  * [6] Coquet M., Du X., Ollitraut J.-Y., Schlichting S., Winn M. Transverse mass scaling of dilepton radiation off a quark-gluon plasma, Nucl. Phys. A10302023122579, arXiv:2112.13876 [nucl-th].
  * [7] Pisarski R.D. Where does the $\rho$ go? Chirally symmetric vector mesons in the quark-gluon plasma, Phys. Rev. D521995R3773-R3776, arXiv:hep-ph/9503328.
  * [8] Hohler P.M. Rapp R. Is $\rho$-Meson Melting Compatible with Chiral Restoration? Phys. Lett. B7312014103-109, arXiv:1311.2921 [hep-ph].
  * [9] McLerran L.D. Toimela T. Photon and Dilepton Emission from the Quark - Gluon Plasma: Some General Considerations, Phys. Rev. D311985545
  * [10] ALICE Collaboration The ALICE experiment at the CERN LHC, JINST32008S08002.
  * [11] ALICE Collaboration Performance of the ALICE Experiment at the CERN LHC, Int. J. Mod. Phys. A2920141430044, arXiv:1402.4476 [nucl-ex].
  * [12] ALICE Collaboration Dielectron production in proton-proton and proton-lead collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV, Phys. Rev. C1022020055204
  * [13] ALICE Collaboration Dielectron production in central Pb–Pb collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV, arXiv:2308.16704 [nucl-ex].
  * [14] Sjostrand T, Mrenna S., Skands P.Z. PYTHIA 6.4 Physics and Manual, JHEP052006026, arXiv:hep-ph/0603175.
  * [15] Nason N. A New method for combining NLO QCD with shower Monte Carlo algorithms, JHEP112004040, arXiv:hep-ph/0409146 [hep-ph].
  * [16] Frixione S., Nason P., Ridolphi G. A Positive-weight next-to-leading-order Monte Carlo for heavy flavour hadroproduction, JHEP092007126
  * [17] Frixione S., Nason P., Oleari C. Matching NLO QCD computations with Parton Shower simulations: the POWHEG method, JHEP112007070
  * [18] Frixione S., Nason P., Oleari C., Re E. A general framework for implementing NLO calculations in shower Monte Carlo programs: the POWHEG BOX, JHEP062010043, arXiv:1002.2581 [hep-ph].
  * [19] Eskola K.J., Paukkunen H., Salgado C.A. EPS09: A New Generation of NLO and LO Nuclear Parton Distribution Functions, JHEP042009065, arXiv:0902.4154 [hep-ph].
  * [20] ALICE Collaboration D-meson production in p–Pb collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV and in pp collisions at $\sqrt{s}=7$ TeV, Phys. Rev. D942016054908
  * [21] ALICE Collaboration Measurement of electrons from heavy-flavour hadron decays in p–Pb collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV, Phys. Lett. B754201681-93
  * [22] Song T., Cassing W., Moreau P., Bratkovskaya E. Open charm and dileptons from relativistic heavy-ion collisions, Phys. Rev. C972018064907, arXiv:1803.02698 [nucl-th].
  * [23] ALICE Collaboration Prompt D0, D+, and D∗+ production in Pb–Pb collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV, JHEP012022174, arXiv:2110.09420 [nucl-ex].
  * [24] ALICE Collaboration Measurement of electrons from semileptonic heavy-flavour hadron decays at midrapidity in pp and Pb–Pb collisions at $\sqrt{s_{\rm NN}}=5.02$ TeV, Phys. Lett. B8042020135377, arXiv:1910.09110 [nucl-ex].
  * [25] NA60 Collaboration Evidence for the production of thermal muon pairs with masses above 1 GeV/$c^{2}$ in 158A GeV Indium-Indium Collisions, Eur. Phys. J C592009607-623,
  * [26] ALICE TPC Collaboration The upgrade of the ALICE TPC with GEMs and continuous readout, JINST162021P03022,
  * [27] ALICE Collaboration Technical Design Report for the Upgrade of the ALICE Inner Tracking System, J. Phys. G412014087001.
  * [28] ALICE Collaboration Expression of Interest for an ALICE ITS Upgrade in LS3, http://cds.cern.ch/record/2644611.
  * [29] ALICE Collaboration Soft-Dielectron Excess in Proton–Proton Collisions at $\sqrt{s}=13$ TeV, Phys. Rev. Lett.1272021042302, arXiv:2005.14522 [nucl-ex].
  * [30] ALICE Collaboration Letter of intent for ALICE 3: A next-generation heavy-ion experiment at the LHC, arXiv:2211.02491 [physics.ins-det].
  * [31] Low F.E. Bremsstrahlung of very low-energy quanta in elementary particle collisions, Phys. Rev.1101958974-977.
  * [32] Arnold P.B., Moore G.D., Yaffe L.G. Transport coefficients in high temperature gauge theories. 1. Leading log results, JHEP112000001,