restatethm[2]

######  Theorem 0.1 (#2).

# Efficient List-decoding of Polynomial Ideal Codes
with Optimal List Size

Noga Ron-Zewi Department of Computer Science, University of Haifa.
<EMAIL_ADDRESS>Research supported in part by BSF grant 2021683, ISF
grant 735/20, and by the European Union (ERC, ECCC, 101076663). Views and
opinions expressed are however those of the author(s) only and do not
necessarily reflect those of the European Union or the European Research
Council. Neither the European Union nor the granting authority can be held
responsible for them.  S. Venkitesh Department of Computer Science, University
of Haifa<EMAIL_ADDRESS>Research supported in part by BSF grant
2021683, ISF grant 735/20, and by the European Union (ERC, ECCC, 101076663).
Views and opinions expressed are however those of the author(s) only and do
not necessarily reflect those of the European Union or the European Research
Council. Neither the European Union nor the granting authority can be held
responsible for them. Mary Wootters Departments of Computer Science and
Department of Electrical Engineering, Stanford University.
<EMAIL_ADDRESS>Research supported in part by NSF grants CAREER grant
CCF-1844628, NSF-BSF grant CCF-2231157, and NSF-BSF grant CCF-2133154.

###### Abstract

In a recent breakthrough [BGM23, GZ23, AGL23], it was shown that Reed-Solomon
codes, defined over random evaluation points, are list decodable with
_optimal_ list size with high probability, i.e., they attain the _Singleton
bound for list decoding_ [ST20, Rot22, GST22]. We extend this result to a
large subclass of _polynomial ideal codes_ , which includes several well-
studied families of error-correcting codes such as Reed-Solomon codes, folded
Reed-Solomon codes, and multiplicity codes. Our results imply that a large
subclass of polynomial ideal codes with random evaluation points over
exponentially large fields achieve the Singleton bound for list-decoding
exactly; while such codes over quadratically-sized fields approximately
achieve it.

Combining this with the efficient list-decoding algorithms for polynomial
ideal codes of [BHKS21], our result implies as a corollary that a large
subclass of polynomial ideal codes (over random evaluation points) is
_efficiently_ list decodable with optimal list size. To the best of our
knowledge, this gives the first family of codes that can be efficiently list
decoded with optimal list size (for all list sizes), as well as the first
family of linear codes of rate $R$ that can be efficiently list decoded up to
a radius of $1-R-\epsilon$ with list size that is polynomial (and even linear)
in $1/\epsilon$. Moreover, the result applies to natural families of codes
with algebraic structure such as folded Reed-Solomon or multiplicity codes
(over random evaluation points).

Our proof follows the general framework of [BGM23, GZ23], where the main new
ingredients are a _duality theorem_ for polynomial ideal codes, as well as a
new _algebraic folded GM-MDS theorem_ (extending the algebraic GM-MDS theorem
of [YH19, Lov21]), which may be of independent interest.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Error-correcting codes and list-decoding
    2. 2.2 Polynomial ideal codes
    3. 2.3 Generalized polynomial ideal codes
    4. 2.4 Affine monomial codes
  3. 3 Duals of polynomial ideal codes
  4. 4 Algebraic folded GM-MDS theorem
    1. 4.1 Folded zero patterns, and folded MDS matrices
    2. 4.2 Polynomial ideal codes are MDS
    3. 4.3 Folded Hall’s theorem, and an algebraic folded GM-MDS theorem
    4. 4.4 A technical lemma, and proof of the algebraic folded GM-MDS theorem
    5. 4.5 Proof of the technical lemma
  5. 5 List decoding randomly punctured polynomial ideal codes
    1. 5.1 Preparations for Theorem 5.1
    2. 5.2 Proof of Theorem 5.1
  6. 6 Reducing alphabet size
    1. 6.1 Reduced intersection matrix (RIM)
    2. 6.2 Full-rankness of RIM
    3. 6.3 Full-rankness of RIM under random assignment
    4. 6.4 List decoding up to capacity
    5. 6.5 Algorithmic list decoding up to capacity
  7. A Duals of polynomial ideal codes with irreducible moduli

##  1 Introduction

An error-correcting code $C\subseteq\Sigma^{n}$ is a collection of codewords
$c$ of length $n$ over an _alphabet_ $\Sigma$. We say that $C$ is
$\mathbb{F}$-_linear_ if $\Sigma=\mathbb{F}^{s}$ for some finite field
$\mathbb{F}$, and $C$ is a vector space over $\mathbb{F}$. The _rate_ of $C$
is $R:=\frac{\log_{|\Sigma|}|C|}{n}$, and it measures the amount of
information that can be sent using the code. The _relative distance_ $\delta$
of $C$ is the smallest relative Hamming distance111The _relative Hamming
distance_ $\delta(a,b)$ between a pair of strings $a,b\in\Sigma^{n}$ is the
fraction of coordinates on which $a$ and $b$ differ. $\delta(c,c^{\prime})$
between any pair of distinct codewords $c,c^{\prime}\in C$. The distance
$\delta$ of a code is important because it allows us to correct errors: more
precisely, given $w\in\Sigma^{n}$ so that $\delta(w,c)<\frac{\delta}{2}$ for
some $c\in C$, then this codeword $c$ is uniquely determined. Thus, a code
with distance $\delta$ can be _uniquely decoded_ from an $\alpha$ fraction of
worst-case errors, for any $\alpha\in\big{[}0,\frac{\delta}{2}\big{)}$.

The Singleton Bound states that any code with rate $R$ and relative distance
$\delta$ must satisfy that $\delta\leq 1-R$, and this bound is attained for
example by the classical family of Reed-Solomon (RS) codes [RS60]. Given a
finite field $\mathbb{F}$, $n$ distinct _evaluation points_
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}$, and a degree parameter $k\leq n$,
the Reed-Solomon code
$\mathrm{RS}(\alpha_{1},\ldots,\alpha_{n};k)\subseteq\mathbb{F}^{n}$ is the
code whose codewords are of the form $(f(\alpha_{1}),\ldots,f(\alpha_{n}))$,
where $f\in\mathbb{F}[X]$ is a polynomial of degree smaller than $k$. It
follows by definition that $\mathrm{RS}(\alpha_{1},\ldots,\alpha_{n};k)$ has
rate $R=\frac{k}{n}$, and its relative distance is at least
$\delta=\frac{n-k+1}{n}\to 1-R$, since a pair of distinct polynomials of
degree smaller than $k$ can agree on at most $k-1$ distinct points in
$\mathbb{F}$. Moreover, classical decoding algorithms for RS codes [Pet60,
BW87] can efficiently decode (in $\text{poly}(n)$ time) these codes from up to
$\frac{\delta}{2}=\frac{1-R}{2}$ fraction of errors.

##### List-decoding.

In list-decoding, the fraction of errors $\alpha$ is large enough so that
unique recovery of the message $c$ is impossible (that is,
$\alpha>\frac{\delta}{2}$). Instead, the goal is, given a received word $w$,
to return a short list $\mathcal{L}$ with the guarantee that $c\in\mathcal{L}$
for any codeword $c$ with $\delta(w,c)\leq\alpha$. More formally, we say that
a code $C\subseteq\Sigma^{n}$ is $(\alpha,L)$-list decodable if for any string
$w\in\Sigma^{n}$, there are at most $L$ distinct codewords $c\in C$ satisfying
that $\delta(w,c)\leq\alpha$. The task of _list-decoding from
$\alpha$-fraction of errors_ is to find these $L$ codewords given $w$.

Besides being a fundamental concept in coding theory, list-decoding has found
diverse applications in theoretical computer science, for example in
cryptography [GL89], learning theory [KM93], average-to-worst-case reductions
[CPS99, GRS00], hardness amplification [BFNW93, STV01, Tre03], and pseudo-
randomness [TZ04, GUV09, DKSS13, TU12, GRX18].

##### The Singleton bound for list-decoding.

Given the central role of list-decoding in the theory of error-correcting
codes and in theoretical computer science, it may come as a surprise that only
very recently there has been an attempt to extend the aforementioned Singleton
bound to the setting of list-decoding [ST20, Rot22, GST22]. Specifically, it
was shown that any $(\alpha,L)$-list decodable code $C\subseteq\Sigma^{n}$
must satisfy that $\alpha\leq\frac{L}{L+1}(1-R)$. Note that the classical
Singleton bound for unique decoding corresponds to the special case of $L=1$,
in which case $\alpha\leq\frac{\delta}{2}\leq\frac{1-R}{2}$. For larger values
of $L$, this bound in particular implies that $(\alpha,L)$-list decodable
codes must have $\alpha\leq 1-R-\epsilon$ for some $\epsilon=\epsilon(L)$
which approaches zero as $L$ grows, and a code $C\subseteq\Sigma^{n}$ is said
to attain _list-decoding capacity_ if it matches this coarser bound, i.e., it
is $(1-R-\epsilon,O_{\epsilon}(1))$-list decodable for any $\epsilon>0$.

A beautiful recent work of Brakensiek, Gopi, and Makam [BGM23] has shown that
RS codes, defined over random evaluation points, chosen from an exponentially
large field (in the codeword length $n$), attain the Singleton bound for list-
decoding with high probability (in particular, this resolved a long-standing
open problem about the existence of RS codes attaining list-decoding
capacity). This was shown by revealing deep connections between the above
Singleton bound for list-decoding, the theory of MDS codes, and the recently
proven GM-MDS Theorem [YH19, Lov21]. Follow-up work has shown that the size of
the field from which the evaluation points are chosen can be further reduced
to polynomial in $n$ [GZ23] (and even linear in $n$ [AGL23]), for
_approximately_ attaining the Singleton bound.222More precisely, it was shown
that for any $\epsilon>0$, RS codes, defined over random evaluation points,
chosen from a field of size $O_{\epsilon}(n)$, are
$(\frac{L}{L+1}(1-R-\epsilon),L)$-list decodable with high probability.

However, in contrast to the unique decoding setting, it is currently not known
how to _efficiently_ list decode RS codes over random evaluation points up to
the (approximate) Singleton bound for list-decoding, and obtaining such an
efficient list-decoding algorithm is a very interesting question.

##### Efficient list-decoding.

As for efficient list-decoding, the celebrated work of Guruswami and Sudan
[Sud97, GS99] showed that RS codes can be efficiently list decoded beyond half
their minimum distance (up to the so-called _Johnson bound_), which gave the
first family of error-correcting codes that are _efficiently_ list decodable
beyond the unique decoding radius. A decade later, the seminal work of
Guruswami and Rudra [GR08] showed that folded Reed-Solomon (FRS) codes can be
efficiently list decoded up to a radius of $1-R-\epsilon$, which gave the
first family of error-correcting codes that are _efficiently_ list decodable
up to list-decoding capacity.

Folded Reed-Solomon codes are a simple variant of Reed-Solomon codes, defined
as follows. Let $\gamma$ be a generator of the multiplicative group of a
finite field $\mathbb{F}$. Given a _folding parameter_ $s\geq 1$, $n$
evaluation points $\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}$ so that the sets
$\\{\gamma^{j}\alpha_{i}:j\in[0,s-1]\\},\,i\in[n]$ are pairwise disjoint, and
a degree parameter $k\leq sn$, the Folded Reed-Solomon code
$\mathrm{RS}^{(s)}(\alpha_{1},\ldots,\alpha_{n};k)\subseteq(\mathbb{F}^{s})^{n}$
is defined similarly to the corresponding RS code, except that each codeword
entry $f(\alpha_{i})$ is replaced with the $s$-tuple
$(f(\alpha_{i}),f(\gamma\alpha_{i}),\ldots,f(\gamma^{s-1}\alpha_{i}))\in\mathbb{F}^{s}$.

Another related variant is _multiplicity codes_ , which extend RS codes by
also including evaluations of derivatives. That is, given a _multiplicity
parameter_ $s\geq 1$, $n$ distinct evaluation points
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}$, and a degree parameter $k\leq
sn$, the multiplicity code
$\mathrm{Mult}^{(s)}(\alpha_{1},\ldots,\alpha_{n};k)\subseteq(\mathbb{F}^{s})^{n}$
is defined similarly to the corresponding RS code, except that now each
codeword entry $f(\alpha_{i})$ is replaced with the $s$-tuple
$(f(\alpha_{i}),f^{(1)}(\alpha_{i}),\ldots,f^{(s-1)}(\alpha_{i}))\in\mathbb{F}^{s}$.
It was shown in [Kop15, GW13] that multiplicity codes can also be efficiently
list-decoded up to list-decoding capacity, with an algorithm similar to that
of FRS.

In a recent beautiful work [BHKS21], Bhandari, Harsha, Kumar, and Sudan
abstracted out the properties required out of the codes in order to apply the
list-decoding algorithm of [GW13], and used this to devise an efficient list-
decoding algorithm that applies to a larger subclass of _polynomial ideal_
(PI) _codes_ (which in particular includes FRS and multiplicity codes as
special cases). Polynomial ideal codes are defined as follows. Let
$E(X,Y)\in\mathbb{F}[X,Y]$ be a bivariate polynomial over $\mathbb{F}$, of the
form $E(X,Y)=X^{s}+\sum_{j=0}^{s-1}E_{j}(Y)X^{j}$ (that is, it is a monic
polynomial of degree $s$ in $\mathbb{F}(Y)[X]$) such that $E_{0}(Y)\neq 0$.
Given $n$ evaluation points $\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}$ so
that $E(X,\alpha_{1}),\ldots,E(X,\alpha_{n})\in\mathbb{F}[X]$ are pairwise
coprime, and a degree parameter $k\leq sn$, the polynomial ideal code
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)\subseteq(\mathbb{F}^{s})^{n}$
is defined similarly to the corresponding RS code, except that each codeword
entry $f(\alpha_{i})$ is replaced with the $s$-tuple representing the
coefficients of the polynomial $f(X)\mod E(X,\alpha_{i})$.

It is not hard to see that PI codes include both FRS and multiplicity codes as
special cases (up to applying a fixed invertible linear transformation on each
of the codeword entries) by letting $E(X,Y)=\prod_{i=0}^{s-1}(X-\gamma^{i}Y)$
and $E(X,Y)=(X-Y)^{s}$, respectively (where RS codes correspond to the special
case that $s=1$ and $E(X,Y)=(X-Y)$). But PI codes also include other families
of codes of interest such as _affine Folded Reed-Solomon codes_
$\mathrm{AFRS}^{(s)}_{\ell}(y_{1},\ldots,y_{n};k)$, which correspond to the
special case that $E(X,Y)=\prod_{i=0}^{s-1}(X-\ell^{(i)}(Y))$ for some linear
function $\ell:\mathbb{F}\to\mathbb{F}$ (where $\ell^{(i)}$ denotes the $i$-th
repeated application of $\ell$; note once more that FRS and multiplicity codes
correspond to the special case that $\ell(X)=\gamma X$ and $\ell(X)=X$,
respectively).

While all of these list-decoding algorithms achieve list-decoding capacity,
the list sizes guaranteed are far from optimal. In more detail, the list size
obtained by the list-decoding algorithms of [GR08, Kop15, GW13] for FRS or
multiplicity codes was initially a very large polynomial on the order of
$n^{\Theta(1/\epsilon)}$. More recently, [KRZSW23] gave an improved bound on
the list size for these codes that depended only on $\epsilon$, on the order
of $\exp(\text{poly}(1/\epsilon))$ (also see [Tam23] for a recent improvement
on the constants hiding in the exponent of this bound). The methods of
[KRZSW23] were also used in [BHKS21] to give a similar bound for (a large
subclass of) polynomial ideal codes. Note however that for all these codes,
the best known list size is exponential in $\epsilon$, and in particular they
are very far from achieving the Singleton bound for list-decoding.

##### Our results.

Our main result extends the results of [BGM23, GZ23] about RS codes over
random evaluation points achieving the Singleton bound for list-decoding, to a
large subclass of random PI codes. Similarly to the RS setting, we show that
if the random evaluation points are chosen from an exponentially large field,
then the codes _exactly_ attain the Singleton bound for list-decoding, while
if the points are chosen from a quadratic-sized field, then the codes
_approximately_ attain the this bound.

######  Theorem 1.1 (Random PI codes attain Singleton bound for list-
decoding).

Let $s,s^{\prime},k,n$ be non-negative integers so that $s\,|\,(k-1)$ and
$k\leq sn$. Let $\mathbb{F}$ be a finite field of size at least $n$, let
$E(X,Y)=\prod_{j=0}^{s}(X-\phi_{j}(Y))$, where $\phi_{j}\in\mathbb{F}[Y]$ is a
non-zero polynomial of degree at most $s^{\prime}$ for any $0\leq j\leq s$,
and let $\alpha_{1},\ldots,\alpha_{n}$ be chosen independently and uniformly
at random from $\mathbb{F}$. Let $L$ be a non-negative integer, and let
$\epsilon>0$.

If $|\mathbb{F}|\geq\exp_{s,s^{\prime},L}(n)$, then
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ is a code of rate
$R:=\frac{k}{sn}$, that is
$\big{(}\frac{L}{L+1}\big{(}1-R\big{)},L\big{)}$-list decodable with high
probability. Furthermore, if
$|\mathbb{F}|\geq\Theta_{\epsilon,s,s^{\prime},L}(n^{2})$, then
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ is
$\big{(}\frac{L}{L+1}(1-R-\epsilon),L\big{)}$-list decodable with high
probability.

We prove Theorem 1.1 in two parts, one for large alphabets and one for small
alphabets. The formal statement for large alphabets is Theorem 5.5, while the
formal statement for small alphabets is Theorem 6.1.

Theorem 1.1 in particular applies to random FRS and multiplicity codes since,
as mentioned above, both can be viewed as PI codes with respect to a
polynomial $E(X,Y)$ that decomposes into linear factors over
$\mathbb{F}(Y)[X]$ (up to applying a fixed invertible linear transformation on
each of the codeword entries). While it was already shown in [GR08, GW13,
KRZSW23] that these codes (over any subset of evaluation points) achieve list-
decoding capacity (and even with efficient list-decoding algorithms), as
mentioned above, the bound on the list size obtained in these works was very
far from the Singleton bound. Moreover, it required a sufficiently large
folding or multiplicity parameter $s$, and in the case of multiplicity codes,
also a field of sufficiently large characteristic. In contrast, the above
theorem holds for _any_ folding or multiplicity parameter, and over _any_
characteristic.

We further note that in a very recent work, Tamo [Tam23] has shown that for
the special case of list size $L=2$, FRS codes (over _any_ subset of
evaluation points) approximately attain the Singleton bound for list-decoding,
which gave the first _explicit_ construction of a code attaining this bound
for some list size $L>1$. In contrast, our construction is randomized, but
applies for _any_ list size, and for a larger class of codes.

Combining the above Theorem 1.1 with the efficient list-decoding algorithm of
[BHKS21], we show that a large subclass of random PI codes can be
_efficiently_ list-decoded up to the Singleton bound. In particular, we can
show that this is the case for the class of affine folded RS codes (the result
actually applies to a larger subclass of PI codes, see Section 6.5 for more
details).

######  Corollary 1.2 (Efficient list-decoding of random PI codes with optimal
list size).

Let $\epsilon>0$, and let $s,k,n,L$ be non-negative integers so that
$s\,|\,(k+1)$ and $k\leq sn$. Let $\mathbb{F}$ be a finite field of size at
least $\Theta_{\epsilon,s,L}(n^{2})$, let $\ell:\mathbb{F}\to\mathbb{F}$ be a
linear function of order at least $k$, and let $\alpha_{1},\ldots,\alpha_{n}$
be chosen independently and uniformly at random from $\mathbb{F}$. Then there
exists a polynomial-time algorithm that list decodes
$\mathrm{AFRS}^{(s)}_{\ell}(\alpha_{1},\ldots,\alpha_{n};k)$ up to a radius of
$\frac{L}{L+1}(1-R-\epsilon)$ with list size $L$, where $R:=\frac{k}{sn}$ is
the rate of the code.

The above corollary gives the first family of codes that can be _efficiently_
list-decoded up to the Singleton bound for list-decoding (for any list size).
Moreover, this corollary gives the first family of _linear_ codes that can be
_efficiently_ list-decoded up to a radius of $1-R-\epsilon$ with list size
that is polynomial (and even linear) in $1/\epsilon$. Indeed, prior to this
work, the only known family of codes satisfying this property was obtained by
restricting algebraic codes to a large random non-linear subset [GX22].
Furthermore, the above corollary applies to more natural families of codes
such as FRS or multiplicity codes (over random evaluation points), that
satisfy some other useful properties that are needed in various applications
(e.g., multiplication property).

##### Techniques.

Theorem 1.1 is proven using the general framework of prior work [BGM23, GZ23],
but replacing the recently proven GM-MDS theorem [YH19, Lov21] with a more
general folded GM-MDS theorem, which may be of independent interest (see
Section 4). This also partially answers a question raised by [BDG23] about a
potential GM-MDS theorem for generator matrices which _share_ variables across
rows. Additionally, in [BGM23, GZ23], the list-decodability of RS codes was
deduced by applying the GM-MDS theorem to _duals_ of RS codes (which happen to
be (generalized) RS codes). To carry out this approach in our setting, we
prove a duality theorem for a large subclass of polynomial ideal codes, which
once more may be of independent interest (see Section 3).333 For an
$\mathbb{F}$-linear code $C\subseteq(\mathbb{F}^{s})^{n}$, we let its _dual
code_ be the code $C^{\perp}\subseteq(\mathbb{F}^{s})^{n}$, whose codewords
are all strings $c^{\prime}\in(\mathbb{F}^{s})^{n}$ so that
$\sum_{i=1}^{n}\sum_{j=1}^{s}c^{\prime}_{i,j}\cdot c_{i,j}=0$ for any $c\in
C$, where for a string $y\in(\mathbb{F}^{s})^{n}$, $y_{i,j}$ denotes the
$j$-th entry in the $i$-th entry of $y$. Finally, Corollary 1.2 follows by
combining Theorem 1.1 with the efficient list-decoding algorithm of [BHKS21]
for a subclass of PI codes (see Section 6.5).

##### Open problems.

The results of [BGM23, GZ23, AGL23] were recently extended in [BDGZ23] to show
that AG codes over random evaluation points achieve the Singleton bound for
list-decoding with high probability over a _constant-size_ alphabet. There has
also been a long line of work on _efficient_ list-decoding algorithms up to
capacity for folded versions of AG codes over constant-size alphabet [Gur09,
GX12, GX14, GX15, GX22, GR22]. We leave the question of extending our results
to the setting of AG codes, to obtain efficiently list-decodable codes up to
the Singleton bound over _constant-size_ alphabets, as an interesting question
for future research.

##### Paper organization.

We begin with some notations and definitions in Section 2. In Section 3, we
prove our duality theorem for polynomial ideal codes, while in Section 4, we
prove our folded GM-MDS theorem. In Section 5, we use these to show that
polynomial ideal codes over random evaluation points, chosen from an
exponential-size field, achieve list-decoding capacity, while in Section 6 we
show how to reduce the field size to quadratic. An alternate characterization
of duals of polynomial ideal codes, in a different case that we do not
consider for list-decoding, is given in Appendix A.

##  2 Preliminaries

Let us begin with some basic notations and terminology. We will denote by
$\mathbb{F}_{q}$ the finite field with $q$ elements, where $q$ is a prime
power. For a field $\mathbb{F}$, and indeterminates $Y_{1},\ldots,Y_{n}$ over
$\mathbb{F}$, we let $\mathbb{F}(Y_{1},\ldots,Y_{n})$ denote the _field of
rational functions_ in $Y_{1},\ldots,Y_{n}$ over $\mathbb{F}$. Throughout, we
will emphasize indeterminates over $\mathbb{F}$ by denoting them using upper-
case letters $Y_{1},\ldots,Y_{n}$, and elements in $\mathbb{F}$ by denoting
them using lower-case letters $y_{1},\ldots,y_{n}$. Throughout, $\mathbb{F}$
will be either a finite field $\mathbb{F}_{q}$, or a field of rational
functions $\mathbb{F}_{q}(Y_{1},\ldots,Y_{n})$.

For a field $\mathbb{F}$, and a univariate polynomial $f(X)\in\mathbb{F}[X]$,
and $t\geq 0$, the coefficient of a monomial $X^{t}$ in $f(X)$ will be denoted
by $\text{coeff}(X^{t},f)$. The degree of $f$ will be denoted by $\deg(f)$.
For a multivariate polynomial
$f(Y_{1},\ldots,Y_{n})\in\mathbb{F}[Y_{1},\ldots,Y_{n}]$, by $\deg(f)$ we will
mean the _total_ degree of $f$. Further, the degree of $f$ in $Y_{i}$ will be
denoted by $\deg_{Y_{i}}(f)$. For a nonconstant monic polynomial
$E(X)\in\mathbb{F}[X]$, and a pair of polynomials $f(X),g(X)\in\mathbb{F}[X]$,
we will write $g(X)=f(X)\,\left(\text{mod }E(X)\right)$ to mean that $g(X)$ is
the unique remainder of $f(X)$ modulo $E(X)$, and $g(X)\equiv
f(X)\,\left(\text{mod }E(X)\right)$ to mean that $g(X)$ and $f(X)$ are
equivalent modulo $E(X)$ (so $g(X)$ and $f(X)$ have the same unique remainder
modulo $E(X)$, but $g(X)$ need not be the remainder of $f(X)$ modulo $E(X)$).

For a vector space $\mathbb{F}^{N}$, we will denote its standard basis by
$\\{e_{N,0},\ldots,e_{N,N-1}\\}$, where
$e_{N,j}=(0^{j},1,0^{N-j-1})\in\mathbb{F}^{N}$ is a column vector.

##### Asymptotics.

We would like to emphasize that all our results are asymptotic. Henceforth,
whenever we encounter parameters $n,s\geq 1$ and $|\mathbb{F}|$, we will
assume the following condition.

######  Condition 2.1.

The parameters $n,s\geq 1$ and the field $\mathbb{F}$ satisfy the following.

  1. (a)

$n\to\infty$ is the fundamental parameter for asymptotics.

  2. (b)

$s=O(1)$.

  3. (c)

$\mathbb{F}$ is either infinite or $|\mathbb{F}|\geq\Omega_{s}(n^{2})$.
($\mathbb{F}$ may, however, have low or fixed positive characteristic.)

The hidden constants may depend on other parameters that are independent of
$n$.

###  2.1 Error-correcting codes and list-decoding

In this work we consider $\mathbb{F}$-linear codes $C\subseteq\mathbb{F}^{sn}$
of dimension $k$. That is, $C$ is simply a $k$-dimensional $\mathbb{F}$-linear
subspace of $\mathbb{F}^{sn}$. We will think of $C$ as living in
$(\mathbb{F}^{s})^{n}$; so that alphabet $\Sigma$ is $\mathbb{F}^{s}$. We will
refer to such a $C$ as an $s$-folded $\mathbb{F}$-linear code to emphasize
this.444We will also consider a generalization where the “alphabet” may vary
from symbol to symbol, so the $i$-th symbol of a codeword $c\in C$ will
satisfy $c_{i}\in\mathbb{F}^{s_{i}}$ for integers $s_{1},\ldots,s_{n}$ that
need not be equal. As $C$ is a $\mathbb{F}$-linear subspace, we may write $C$
as the image of a matrix $G\in\mathbb{F}^{sn\times k}$; such a $G$ is called a
generator matrix of $C$. Similarly, we may also write $C$ as the kernel of a
matrix
$H^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\in\mathbb{F}^{(sn-k)\times
sn}$; such an $H$ is called a parity-check matrix for $C$. We may also define
the dual code $C^{\perp}$ by

$C^{\perp}=\\{b\in\mathbb{F}^{sn}\,:\,a^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}b=0,\text{
for all }b\in C\\},$

where
$a^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}b\coloneqq\sum_{i=1}^{sn}a_{i}b_{i}$
is the standard dot product. The rate of such a code $C$ is defined as
$R:=\frac{k}{sn}$. The distance is defined as the Hamming distance of $C$ when
viewed over the _alphabet_ $\mathbb{F}^{s}$; that is, for
$a=(a_{1},\ldots,a_{n})\in(\mathbb{F}^{s})^{n}$ and
$b=(b_{1},\ldots,b_{n})\in(\mathbb{F}^{s})^{n}$, we define the Hamming
distance between $a$ and $b$ by

$\Delta^{(s)}_{n}(a,b)=|\\{i\in[n]:a_{i}\neq b_{i}\\}|$

and we define the (minimum) distance of the code $C$ as

$\Delta^{(s)}_{n}(C)=\min_{c\neq c^{\prime}\in C}\Delta_{n}(c,c^{\prime}).$

We note that, as $C$ is linear, $\Delta^{(s)}_{n}(C)$ is also the minimum
Hamming weight of any nonzero codeword in $C$; that is,
$\Delta^{(s)}_{n}(C)=\min_{c\in C\setminus\\{0\\}}\Delta^{(s)}_{n}(c,0).$ We
define the (relative) distance of $C$ as

$\delta^{(s)}_{n}(C)=\frac{\Delta^{(s)}_{n}(C)}{n}.$

As an _unfolded_ code (that is, over the alphabet $\mathbb{F}$), the best
possible trade-off between the rate $R$ and distance $\delta$ of a code (for
large alphabets) is given by the _Singleton bound_ : $R+\delta\leq 1$. Codes
that meet the Singleton bound are known as _Maximum Distance Separable_ (MDS)
codes.

It is not hard to see that for $w\in(\mathbb{F}^{s})^{n}$, there is at most
one codeword $c\in C$ satisfying $\Delta_{n}(c,w)<\Delta^{(s)}_{n}(C)/2$; the
unique decoding problem is to recover this $w$, given $c$. In this paper we
are concerned with a generalization of the unique decoding problem known as
list-decoding. Formally, we have the following definition.

######  Definition 2.2.

Let $C\subseteq(\mathbb{F}^{s})^{n}$ be an $s$-folded $\mathbb{F}$-linear
code. We say that $C$ is $(\alpha,L)$-list-decodable if for all
$w\in(\mathbb{F}^{s})^{n}$,

$|\\{c\in C\,:\,\Delta_{n}(w,c)\leq n\alpha\\}|\leq L.$

###  2.2 Polynomial ideal codes

Polynomial ideal codes are linear folded codes where the codewords correspond
to bounded-degree polynomials modulo a fixed set of polynomials.555Polynomial
ideal codes are also called _redundant residue codes_ (see MacWilliams and
Sloane [MS77, Chapter 10]), and are a special case of _ideal-based codes_ , as
defined in Guruswami [Gur04, Chapter 7], where the base ring is the polynomial
ring. Let us begin by gathering the definition and some basic facts.
Polynomial ideal codes were recently studied by Bhandari, Harsha, Kumar, and
Sudan [BHKS21] in the context of algorithmic list decoding. We use some of
their notation, although our presentation is a change-of-basis away from
theirs. After we present the formalism, we show how to instantiate it for the
familiar cases of folded RS codes and univariate multiplicity codes in
Examples 2.6 and 2.7, respectively.

For a parameter $s\geq 1$, we define a formal modulus to be a bivariate
polynomial
$E(X,Y)=X^{s}+\sum_{j=0}^{s-1}E_{j}(Y)X^{j}\in\big{(}\mathbb{F}[Y]\big{)}[X]$
that is monic in $X$ with $\deg_{X}(E)=s$, and $E_{0}(Y)\neq 0$. Further, for
any $y\in\mathbb{F}$, we will call the univariate restriction $E(X,y)$ a
functional modulus.666In the case the base field $\mathbb{F}$ is
$\mathbb{F}_{q}(Y_{1},\ldots,Y_{n})$, for indeterminates $Y_{1},\ldots,Y_{n}$,
the univariate restrictions $E(X,Y_{1}),\ldots,E(X,Y_{n})$ will still be
called functional moduli. Further, for a parameter $n\geq 1$, let
$y_{1},\ldots,y_{n}\in\mathbb{F}$ be distinct such that the functional moduli
$E(X,y_{1}),\ldots,E(X,y_{n})$ are pairwise coprime (note that this requires
$E_{0}(Y)\neq 0$).777We consider a single bivariate polynomial $E(X,Y)$, and
its univariate restrictions $E(X,y_{1}),\ldots,E(X,y_{n})$, simply for
notational convenience. Note that the univariate polynomials
$E_{j}(Y),\,j\in[0,s-1]$, that are the ‘coefficients’ of $E(X,Y)$, are
unrestricted. So, instead, we could start with a set of pairwise coprime monic
polynomials $\widetilde{E}_{1}(X),\ldots,\widetilde{E}_{n}(X)$, each having
degree equal to $s$, and then interpolate w.r.t. $Y$ to obtain $E(X,Y)$ such
that $E(X,y_{i})=\widetilde{E}_{i}(X),\,i\in[n]$.

Since $E(X,Y)$ is monic in $X$, by Division Algorithm on the univariate
polynomial ring $\big{(}\mathbb{F}[Y]\big{)}[X]$, for any
$f(X)\in\mathbb{F}[X]\subseteq\big{(}\mathbb{F}[Y]\big{)}[X]$, there exist
unique $Q_{f}(X,Y),R_{f}(X,Y)\in\big{(}\mathbb{F}[Y]\big{)}[X]$ such that

$f(X)=Q_{f}(X,Y)E(X,Y)+R_{f}(X,Y),\quad\text{with }\deg_{X}(R_{f})<s.$

Now denote

$R_{f}(X,Y)=\sum_{j=0}^{s-1}L_{j}(f)(Y)X^{j},\quad\mathcal{L}(f)(Y)=\begin{bmatrix}L_{0}(f)(Y)\\\
\vdots\\\ L_{s-1}(f)(Y)\end{bmatrix}_{s\times 1},\quad\text{and
}[f]=\begin{bmatrix}[f]_{1}\\\ \vdots\\\
[f]_{n}\end{bmatrix}=\begin{bmatrix}\mathcal{L}(f)(y_{1})\\\ \vdots\\\
\mathcal{L}(f)(y_{n})\end{bmatrix}_{sn\times 1}.$

As a consequence of Division Algorithm, for every $j\in[0,s-1]$, the map
$L_{j}:\mathbb{F}[X]\to\mathbb{F}[Y]$ is $\mathbb{F}$-linear. Therefore, the
map

$\mathbb{F}[X]\to\mathbb{F}^{sn},\quad f(X)\mapsto[f]$

is $\mathbb{F}$-linear with kernel
$\big{\langle}\prod_{i=1}^{n}E(X,y_{i})\big{\rangle}$. Since
$E(X,y_{1}),\ldots,E(X,y_{n})$ are pairwise coprime, by appealing to the
Chinese Remainder Theorem, we can conclude that this map is also surjective,
and so we have the $\mathbb{F}$-linear isomorphism

$\frac{\mathbb{F}[X]}{\big{\langle}\prod_{i=1}^{n}E(X,y_{i})\big{\rangle}}\simeq\mathbb{F}^{sn},\quad
f(X)\mapsto[f].$

The collection of monomials $\\{X^{j}:j\in[0,sn-1]\\}$ is an
$\mathbb{F}$-linear basis of
$\mathbb{F}[X]\big{/}\big{\langle}\prod_{i=1}^{n}E(X,y_{i})\big{\rangle}$.888Strictly
speaking, the basis is the image of the set of monomials
$\\{X^{j}:j\in[0,sn-1]\\}$ in the quotient ring
$\mathbb{F}[X]\big{/}\big{\langle}\prod_{i=1}^{n}E(X,y_{i})\big{\rangle}$.
However, since $\prod_{i=1}^{n}E(X,y_{i})$ has degree $sn$, each monomial
$X^{j},\,j\in[0,sn-1]$ is _reduced_ modulo $\prod_{i=1}^{n}E(X,y_{i})$. So, we
identify each of these monomials with its image.

For any $k\in[sn]$, the polynomial ideal code (with the formal modulus
$E(X,Y)$) is defined by

$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)=\\{[f]:f(X)\in\mathbb{F}[X],\,\deg(f)<k\\}.$

Also, denote

$\displaystyle G_{E,k}(y_{i})$
$\displaystyle=\begin{bmatrix}L_{0}(1)(y_{i})&L_{0}(X)(y_{i})&\cdots&L_{0}(X^{k-1})(y_{i})\\\
\vdots&\vdots&\ddots&\vdots\\\
L_{s-1}(1)(y_{i})&L_{s-1}(X)(y_{i})&\cdots&L_{s-1}(X^{k-1})(y_{i})\end{bmatrix}\in\mathbb{F}^{s\times
k}$ $\displaystyle\text{for }i\in[n],$ $\displaystyle\text{and}\quad
G_{E,k}(y_{I})$
$\displaystyle=\begin{bmatrix}G_{E,k}(y_{i})\end{bmatrix}_{i\in
I}\in\mathbb{F}^{s|I|\times k}$ $\displaystyle\text{for }I\subseteq[n].$

Next, we make an observation. For any
$f(X)=\sum_{t=0}^{k-1}f_{t}X^{t}\in\mathbb{F}[X]$, by abuse of notation, let
$f=\begin{bmatrix}f_{0}&\cdots&f_{k-1}\end{bmatrix}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\in\mathbb{F}^{k\times
1}$ denote the vector of coefficients of $f(X)$.

######  Observation 2.3.

The matrix $G_{E,k}(y_{[n]})$ is a generator matrix of
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$, and defines an encoding for
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$.

###### Proof.

For any $f(X)=\sum_{t=0}^{k-1}f_{t}X^{t}\in\mathbb{F}[X]$, we have

$G_{E,k}(y_{i})\cdot\begin{bmatrix}f_{0}\\\ \vdots\\\
f_{k-1}\end{bmatrix}=\sum_{t=0}^{k-1}f_{t}\,\mathcal{L}(X^{t})(y_{i})=\mathcal{L}\bigg{(}\sum_{t=0}^{k-1}f_{t}X^{t}\bigg{)}(y_{i})=\mathcal{L}(f)(y_{i}),\quad\text{for
all }i\in[n].$

Therefore, $G_{E,k}(y_{[n]})\cdot f=[f]$. ∎

We can also reinterpret $\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ in terms of
matrix polynomials. Let $C_{E}\in\big{(}\mathbb{F}[Y]\big{)}^{s\times s}$ be
the companion matrix of $E(X,Y)$ defined by

$C_{E}(Y)=\begin{bmatrix}0&&&-E_{0}(Y)\\\ 1&&&-E_{1}(Y)\\\ &\ddots&&\vdots\\\
&&1&-E_{s-1}(Y)\end{bmatrix}.$

The following observation was made in [BHKS21]; however, since their notation
is slightly different, we include a proof for completeness.

######  Observation 2.4 ([BHKS21]).

For any $f(X)\in\mathbb{F}[X],\,i\in[n]$, we have
$\mathcal{L}(f)(y_{i})=f(C_{E}(y_{i}))\cdot\mathcal{L}(1)$.

###### Proof.

Firstly, if $s=1$, then clearly, $E(X,Y)=X+E_{0}(Y)$, and $\mathcal{L}(1)=1$.
Also, $C_{E}(y_{i})=-E_{0}(y_{i})$ and
$\mathcal{L}(f)(y_{i})=L_{0}(f)(y_{i})$, for all $i\in[n]$. Then by
definition, we have $L_{0}(f)(y_{i})=R_{f}(X,y_{i})=f(-E_{0}(y_{i}))$ for all
$i\in[n]$.

Now suppose $s\geq 2$. Clearly,
$\mathcal{L}(1)=(1,0^{s-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$.
Further, for any $f(X)\in\mathbb{F}[X]$, Division Algorithm gives

$\displaystyle R_{X\cdot f}(X,Y)$
$\displaystyle=\sum_{j=1}^{s-1}L_{j-1}(f)(Y)X^{j}-L_{s-1}(f)(Y)\cdot\sum_{t=0}^{s-1}E_{t}(Y)X^{t}$
$\displaystyle=-E_{0}(Y)L_{s-1}(f)(Y)+\sum_{j=1}^{s-1}\big{(}E_{j}(Y)L_{s-1}(f)(Y)-L_{j-1}(f)(Y)\big{)}X^{j}.$

This implies $\mathcal{L}(X\cdot
f)(y_{i})=C_{E}(y_{i})\cdot\mathcal{L}(f)(y_{i})$ for all $i\in[n]$. In
particular, by induction on $r\geq 0$, we get
$\mathcal{L}(X^{r})(y_{i})(C_{E}(y_{i}))^{r}\cdot\mathcal{L}(1)$ for all
$i\in[n]$. Then the proof of the claim is complete, by linearity. ∎

Now let $e_{s,j}\coloneqq(0^{j-1},1,0^{s-j})$ be the $j$-th standard unit
vector in $\mathbb{F}^{s}$, as a column vector, for $j\in[0,s-1]$. It is
immediate that $R_{1}(X,Y)=1$, that is, $\mathcal{L}(1)(y_{i})=e_{s,0}$ for
all $i\in[n]$. Therefore, Observation 2.3 and Observation 2.4 imply the
following.

######  Observation 2.5.

For any $[f]\in\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$, we have

$G_{E,k}(y_{[n]})\cdot f=[f]=\begin{bmatrix}f(C_{E}(y_{1}))&&\\\ &\ddots&\\\
&&f(C_{E}(y_{n}))\end{bmatrix}_{sn\times sn}\begin{bmatrix}e_{s,0}\\\
\vdots\\\ e_{s,0}\end{bmatrix}_{sn\times 1}.$

###  2.3 Generalized polynomial ideal codes

As noted in [BHKS21], the well-known examples of _folded Reed-Solomon codes_
and _univariate multiplicity codes_ are polynomial ideal codes, up to a linear
transformation of each coordinate. To incorporate such a linear
transformation, we define _generalized_ polynomial ideal codes.

We say an invertible matrix $U\in\mathbb{F}^{sn\times sn}$ is block invertible
if $U=\text{diag}(U_{1},\ldots,U_{n})$, for some invertible matrices
$U_{i}\in\mathbb{F}^{s\times s},\,i\in[n]$. We define the generalized
polynomial ideal code (with the formal modulus $E(X,Y)$, and the block
invertible matrix $U$) by

$\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)=\\{U\cdot[f]:f(X)\in\mathbb{F}[X],\,\deg(f)<k\\},$

that is, for each $f(X)\in\mathbb{F}[X],\,\deg(f)<k$, the corresponding
codeword in $\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)$ is

$U\cdot[f]=\begin{bmatrix}U_{1}&&\\\ &\ddots&\\\
&&U_{n}\end{bmatrix}_{sn\times sn}\begin{bmatrix}f(C_{E}(y_{1}))&&\\\
&\ddots&\\\ &&f(C_{E}(y_{n}))\end{bmatrix}_{sn\times
sn}\begin{bmatrix}e_{s,0}\\\ \vdots\\\ e_{s,0}\end{bmatrix}_{sn\times 1}.$

Let us quickly see how folded Reed-Solomon codes and univariate multiplicity
codes are generalized polynomial ideal codes. These are simple consequences of
the classical Lagrange and Hermite interpolations.

######  Example 2.6 (Folded Reed-Solomon codes as generalized polynomial ideal
codes).

Fix a field $\mathbb{F}$. Let $s,n\geq 1$, and consider
$\gamma\in\mathbb{F}^{\times}$, as well as distinct
$y_{1},\ldots,y_{n}\in\mathbb{F}$ such that the sets
$\\{\gamma^{j}y_{i}:j\in[0,s-1]\\},\,i\in[n]$ are pairwise disjoint (and so
the multiplicative order of $\gamma$ is at least $s$). For $k\in[sn]$, the
folded Reed-Solomon code [Kra03, GR08] is defined by

$\mathrm{RS}^{(s)}(y_{1},\ldots,y_{n};k)=\left\\{\widehat{f}\coloneqq\begin{bmatrix}\widehat{f}_{1}\\\
\vdots\\\
\widehat{f}_{n}\end{bmatrix}:f(X)\in\mathbb{F}[X],\,\deg(f)<k\right\\},$

where
$\widehat{f}_{i}\coloneqq\begin{bmatrix}f(\gamma^{j}y_{i})\end{bmatrix}_{j=0}^{s-1}\in\mathbb{F}^{s}$
are column vectors. Let $E(X,Y)=\prod_{j=0}^{s-1}(X-\gamma^{j}Y)$. Fix
$i\in[n]$. Consider any $f(X)\in\mathbb{F}[X],\,\deg(f)<k$. We have

$R_{f}(X,y_{i})=\sum_{j=0}^{s-1}L_{j}(f)(y_{i})X^{j}=f(X)\,\left(\text{mod
}\prod_{j=0}^{s-1}(X-\gamma^{j}y_{i})\right).$

On the other hand, we have, for every $j\in[0,s-1]$,

$f(\gamma^{j}y_{i})=Q_{f}(\gamma^{j}y_{i},y_{i})E(\gamma^{j}y_{i},y_{i})+R_{f}(\gamma^{j}y_{i},y_{i})=R_{f}(\gamma^{j}y_{i},y_{i}),$

using the fact that $E(X,y_{i})$ vanishes when $X=\gamma^{j}y_{i}$. Thus, we
may apply Lagrange interpolation to $R_{f}(X,y_{i})$ to see that

$R_{f}(X,y_{i})=\sum_{j=0}^{s-1}\mathsf{A}_{i,j}(X)\cdot f(\gamma^{j}y_{i}),$

where, for every $j\in[0,s-1]$, the polynomial $\mathsf{A}_{i,j}(X)$ satisfies

$\deg(\mathsf{A}_{i,j})=s-1,\quad\text{and}\quad\mathsf{A}_{i,j}(\gamma^{j^{\prime}}y_{i})=\begin{cases}1&\text{if
}j^{\prime}=j\\\ 0&\text{if }j^{\prime}\neq j\end{cases}.$

Thus, there exists an invertible matrix $U_{i}\in\mathbb{F}^{s\times s}$ such
that for every $f(X)\in\mathbb{F}[X],\,\deg(f)<k$, we have

$\begin{bmatrix}f(y_{i})\\\ \vdots\\\
f(\gamma^{s-1}y_{i})\end{bmatrix}=U_{i}\cdot\begin{bmatrix}L_{0}(f)(y_{i})\\\
\vdots\\\ L_{s-1}(f)(y_{i})\end{bmatrix}=U_{i}\cdot f(C_{E}(y_{i}))\cdot
e_{s,0}.$

Indeed, in the first equality, we take $U_{i}$ to be the matrix that changes
basis from the monomial basis $1,X,\ldots,X^{s-1}$ to the basis of Lagrange
polynomials $A_{i,0}(X),\ldots,A_{i,s-1}(X)$; in the second equality, we use
the fact that $\mathcal{L}(1)(y_{i})=e_{s,0}$ for all $i\in[n]$, and use
Obsevation 2.4.

Therefore,
$\mathrm{RS}^{(s)}(y_{1},\ldots,y_{n};k)=\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)$,
where $U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{F}^{sn\times sn}$.

######  Example 2.7 (Univariate multiplicity codes as generalized polynomial
ideal codes).

Fix a field $\mathbb{F}$. For any $f(X)\in\mathbb{F}[X]$, let
$\mathfrak{h}_{f}^{(t)}(X)$ denote the $t$-th Hasse derivative of $f(X)$, for
$t\geq 0$; equivalently, we can define $\mathfrak{h}_{f}^{(t)}(X)$ by the
Taylor expansion

$f(X+Z)=\sum_{t\geq 0}\mathfrak{h}_{f}^{(t)}(X)\cdot Z^{t}\in\mathbb{F}[X,Z].$

Let $s,n\geq 1$, and consider distinct $y_{1},\ldots,y_{n}\in\mathbb{F}$. For
$k\in[sn]$, the univariate multiplicity code [RT97, KSY14, GW13] is defined by

$\mathrm{Mult}^{(s)}(y_{1},\ldots,y_{n};k)=\left\\{\widehat{f}\coloneqq\begin{bmatrix}\widehat{f}_{1}\\\
\vdots\\\
\widehat{f}_{n}\end{bmatrix}:f(X)\in\mathbb{F}[X],\,\deg(f)<k\right\\},$

where
$\widehat{f}_{i}\coloneqq\begin{bmatrix}\mathfrak{h}_{f}^{(j)}(y_{i})\end{bmatrix}_{j=0}^{s-1}\in\mathbb{F}^{s}$
are column vectors. Let $E(X,Y)=(X-Y)^{s}$. Fix $i\in[n]$. Consider any
$f(X)\in\mathbb{F}[X],\,\deg(f)<k$. We have

$R_{f}(X,y_{i})=\sum_{j=0}^{s-1}L_{j}(f)(y_{i})X^{j}=f(X)\,\left(\text{mod
}(X-y_{i})^{s}\right).$

On the other hand, similarly to the previous example, by Hermite interpolation
we also have

$R_{f}(X,y_{i})=\sum_{j=0}^{s-1}\mathsf{A}_{i,j}(X)\cdot\mathfrak{h}_{f}^{(j)}(y_{i}),$

where, for every $j\in[0,s-1]$, the polynomial $\mathsf{A}_{i,j}(X)$ satisfies

$\mathfrak{h}_{\mathsf{A}_{i,j}}^{(j^{\prime})}(y_{i})=\begin{cases}1&\text{if
}j^{\prime}=j\\\ 0&\text{if }j^{\prime}\neq j\end{cases}.$

Thus, there exists an invertible matrix $U_{i}\in\mathbb{F}^{s\times s}$ such
that for every $f(X)\in\mathbb{F}[X],\,\deg(f)<k$, we have

$\begin{bmatrix}\mathfrak{h}_{f}^{(0)}(y_{i})\\\ \vdots\\\
\mathfrak{h}_{f}^{(s-1)}(y_{i})\end{bmatrix}=U_{i}\cdot\begin{bmatrix}L_{0}(f)(y_{i})\\\
\vdots\\\ L_{s-1}(f)(y_{i})\end{bmatrix}=U_{i}\cdot f(C_{E}(y_{i}))\cdot
e_{s,0}.$

Therefore,
$\mathrm{Mult}^{(s)}(y_{1},\ldots,y_{n};k)=\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)$,
where $U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{F}^{sn\times sn}$.

###  2.4 Affine monomial codes

The folded Reed-Solomon codes and univariate multiplicity codes are special
cases of a larger class of well-structured generalized polynomial ideal codes,
called _affine folded Reed-Solomon codes_. These were considered in Spitzbart
[Spi60] in the context of generalized Hermite interpolation, and in [BHKS21]
in the context of algorithmic list decoding. In fact, [Spi60] considered a
slightly more general class of codes, which we call _affine monomial codes_.
This generality is important to us, since we shall use affine monomial codes
as an intermediate family of codes to characterize the duals of a large
subclass of polynomial ideal codes (in Section 3), and to show that all
polynomial ideal codes are MDS (in Section 4.2).

Fix a field $\mathbb{F}$. Let $z_{1},\ldots,z_{n}\in\mathbb{F}$ be distinct.
Also let $s_{1},\ldots,s_{n}\geq 1$, and $N\coloneqq\sum_{i=1}^{n}s_{i}$. Let
the coordinates of $\mathbb{F}^{N}$ be indexed by
$\bigsqcup_{i=1}^{n}\big{(}\\{i\\}\times[0,s_{i}-1]\big{)}$, and the order on
the coordinates be given by

$(1,0)<\cdots<(1,s_{1}-1)<(2,0)<\cdots<(2,s_{2}-1)<\cdots<(n,0)<\cdots<(n,s_{n}-1).$

For $k\in[N]$, we define the affine monomial code999We use the terminology
‘affine monomial code’ since for the degree parameter $k$, the code admits a
basis that can be naturally identified with the set of all monomials with
degree less than $k$. by

$\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)=\left\\{\widehat{f}\coloneqq\begin{bmatrix}\widehat{f}_{1}\\\
\vdots\\\
\widehat{f}_{n}\end{bmatrix}:f(X)\in\mathbb{F}[X],\,\deg(f)<k\right\\},$

where
$\widehat{f}_{i}\coloneqq\begin{bmatrix}\mathfrak{h}_{f}^{(j)}(z_{i})\end{bmatrix}_{j=0}^{s_{i}-1}\in\mathbb{F}^{s_{i}}$
are column vectors. Further, for a block invertible matrix
$U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{F}^{N\times N}$, where
$U_{i}\in\mathbb{F}^{s_{i}\times s_{i}},\,i\in[n]$, and $k\in[N]$, the
generalized affine monomial code is defined by

$\text{GAM}(U;z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)=\\{U\cdot\widehat{f}:f(X)\in\mathbb{F}[X],\,\deg(f)<k\\},$

that is, for each $f(X)\in\mathbb{F}[X],\,\deg(f)<k$, the corresponding
codeword in $\text{GAM}(U;z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$ is

$U\cdot\widehat{f}=\begin{bmatrix}U_{1}&&\\\ &\ddots&\\\
&&U_{n}\end{bmatrix}_{sn\times
sn}\begin{bmatrix}\begin{bmatrix}\mathfrak{h}_{f}^{(j)}(z_{1})\end{bmatrix}_{j=0}^{s_{1}-1}\\\
\vdots\\\
\begin{bmatrix}\mathfrak{h}_{f}^{(j)}(z_{n})\end{bmatrix}_{j=0}^{s_{n}-1}\end{bmatrix}_{sn\times
1}.$

We briefly mention a few important examples of affine monomial codes.

######  Example 2.8 (Folded Reed-Solomon and univariate multiplicity codes as
affine monomial codes).

The folded Reed-Solomon code $\mathrm{RS}^{(s)}(y_{1},\ldots,y_{n};k)$, as an
unfolded code, is simply the Reed-Solomon code

$\mathrm{RS}\Big{(}\underbrace{\gamma^{j}y_{1},\ldots,\gamma^{j}y_{n}}_{j\in[0,s-1]}\enspace;\,k\Big{)},$

which is the affine monomial code

$\text{AM}\Big{(}\underbrace{\gamma^{j}y_{1},\ldots,\gamma^{j}y_{n}}_{j\in[0,s-1]}\enspace;\,\underbrace{1,\ldots,1}_{sn\,\text{times}}\enspace;\,k\Big{)}.$

The univariate multiplicity code $\mathrm{Mult}^{(s)}(y_{1},\ldots,y_{n};k)$,
as an unfolded code, is the affine monomial code

$\text{AM}\Big{(}y_{1},\ldots,y_{n}\enspace;\,\underbrace{s,\ldots,s}_{n\,\text{times}}\enspace;\,k\Big{)}.$

######  Example 2.9 (Affine folded Reed-solomon codes as affine monomial
codes).

Let $\ell:\mathbb{F}\to\mathbb{F},\,\ell(y)=\alpha y+\beta$, where
$\alpha,\beta\in\mathbb{F},\,\alpha\neq 0$, be a nonzero affine linear map.
Define $\text{ord}(\ell)$ to be the smallest positive integer $d$ such that
$\ell^{(d)}\coloneqq\underbrace{\ell\circ\cdots\circ\ell}_{d\,\text{times}}$
is the identity map. If such a $d$ does not exist, then we define
$\text{ord}(\ell)=\infty$.

Let $s\geq 1$. If $\text{ord}(\ell)\in\mathbb{Z}^{+}$, then let
$u=\text{ord}(\ell)$, and $s=mu+s^{\prime}$, where $m\geq 0,\,s^{\prime}<u$.
If $\text{ord}(\ell)=\infty$, then let $m=0,\,u=s^{\prime}=s$. For
$j\in[0,u-1]$, let us denote $\ell^{(j)}(Y)=\alpha_{j}Y+\beta_{j}$, where
$\alpha_{j}=\alpha^{j},\,\beta_{j}=\beta\sum_{r=0}^{j-1}\alpha^{r}$. Let
$n\geq 1$, and consider distinct $y_{1},\ldots,y_{n}\in\mathbb{F}$ such that
the sets
$\\{\alpha_{0}y_{i}+\beta_{0},\ldots,\alpha_{u-1}y_{i}+\beta_{u-1}\\},\,i\in[n]$,
are pairwise disjoint.

For $k\in[sn]$, the affine folded Reed-Solomon code (as defined in [BHKS21];
also see [Spi60]) is the affine monomial code

$\displaystyle\mathrm{AFRS}^{(s)}_{\ell}(y_{1},\ldots,y_{n};k)$
$\displaystyle\coloneqq\text{AM}\Big{(}\underbrace{\alpha_{j}y_{1}+\beta_{j},\ldots,\alpha_{j}y_{n}+\beta_{j}}_{j\in[0,s^{\prime}-1]},\enspace\underbrace{\alpha_{j}y_{1}+\beta_{j},\ldots,\alpha_{j}y_{n}+\beta_{j}}_{j\in[s^{\prime},u-1]}\enspace;\,\underbrace{m+1,\ldots,m+1}_{s^{\prime}n\,\text{times}},\underbrace{m,\ldots,m}_{(u-s^{\prime})n\,\text{times}}\enspace;\,k\Big{)},$

Let us conclude the preliminaries with a basic, but fundamental result –
polynomial ideal codes and _equifolded_ affine monomial codes are equivalent.

### Equifolded affine monomial codes as generalized polynomial ideal codes

The arguments in Example 2.6 and Example 2.7 can be readily extended, via
generalized Hermite interpolation, to conclude that a large subclass of affine
monomial codes (including all affine folded Reed-Solomon codes) are
generalized polynomial ideal codes. We call these _equifolded affine monomial
codes_.101010Note that we regard affine monomial codes primarily as unfolded
codes. A subclass of these codes that admit equal folding can be regarded as
(folded) polynomial ideal codes. Hence the terminology ‘equifolded’.

Let $\\{z_{i,1},\ldots,z_{i,m_{i}}\\}\subseteq\mathbb{F},\,i\in[n]$ be
pairwise disjoint sets of nonzero points. Further, let $s\geq 1$, and let
$\\{s_{i,1},\ldots,s_{i,m_{i}}\\}\subseteq\mathbb{Z}^{+},\,i\in[n]$ such that
$\sum_{t=1}^{m_{i}}s_{i,t}=s$ for all $i\in[n]$. Then for any $k\in[sn]$, we
say the affine monomial code
$\text{AM}\Big{(}\underbrace{z_{i,1},\ldots,z_{i,m_{i}}}_{i\in[n]}\enspace;\,\underbrace{s_{i,1},\ldots,s_{i,m_{i}}}_{i\in[n]}\enspace;\,k\Big{)}$
is $(n,s)$-equifolded.

######  Proposition 2.10.

Every equifolded affine monomial code is a generalized polynomial ideal code.

###### Proof.

Let $\\{z_{i,1},\ldots,z_{i,m_{i}}\\}\subseteq\mathbb{F},\,i\in[n]$ be
pairwise disjoint sets of points. Further, let $s\geq 1$, and let
$\\{s_{i,1},\ldots,s_{i,m_{i}}\\}\subseteq\mathbb{Z}^{+},\,i\in[n]$ such that
$\sum_{t=1}^{m_{i}}s_{i,t}=s$ for all $i\in[n]$. We can then choose distinct
points $y_{1},\ldots,y_{n}\in\mathbb{F}$, interpolate polynomials
$E_{0}(Y),\ldots,E_{s-1}(Y)$, and define
$E(X,Y)=X^{s}+\sum_{j=0}^{s-1}E_{j}(Y)X^{j}$ such that

$E(X,y_{i})=(X-z_{i,1})^{s_{i,1}}\cdots(X-z_{i,m_{i}})^{s_{i,m_{i}}},\quad\text{for
all }i\in[n].$

Then, clearly, $E(X,y_{1}),\ldots,E(X,y_{n})$ are pairwise coprime and
$E_{0}(Y)\neq 0$.

Fix $i\in[n]$. Consider any $f(X)\in\mathbb{F}[X],\,\deg(f)<sn$. We have

$R_{f}(X,y_{i})=\sum_{j=0}^{s-1}L_{j}(f)(y_{i})X^{j}=f(X)\,\left(\text{mod
}E(X,y_{i})\right).$

On the other hand, by Hermite interpolation, we also have

$R_{f}(X,y_{i})=\sum_{t=1}^{m_{i}}\sum_{j=0}^{s_{i,t}-1}\mathsf{A}_{i,t,j}(X)\cdot\mathfrak{h}_{f}^{(j)}(z_{i,t}),$

where, for every $t\in[m_{i}],\,j\in[0,s_{i,t}-1]$, the polynomial
$\mathsf{A}_{i,j}(X)$ satisfies

$\mathfrak{h}_{\mathsf{A}_{i,t,j}}^{(j^{\prime})}(z_{i,t})=\begin{cases}1&\text{if
}j^{\prime}=j\\\ 0&\text{if }j^{\prime}\neq j\end{cases}.$

Thus, there exists an invertible matrix $U_{i}\in\mathbb{F}^{s\times s}$ such
that for every $f(X)\in\mathbb{F}[X],\,\deg(f)<sn$, we have

$\begin{bmatrix}\begin{bmatrix}\mathfrak{h}_{f}^{(j)}(z_{i,1})\end{bmatrix}_{j=0}^{s_{i,1}-1}\\\
\vdots\\\
\begin{bmatrix}\mathfrak{h}_{f}^{(j)}(z_{i,m_{i}})\end{bmatrix}_{j=0}^{s_{i,m_{i}}-1}\end{bmatrix}=U_{i}\cdot\begin{bmatrix}L_{0}(f)(y_{i})\\\
\vdots\\\ L_{s-1}(f)(y_{i})\end{bmatrix}=U_{i}\cdot f(C_{E}(y_{i}))\cdot
e_{s,0}.$

Therefore, defining $U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{F}^{sn\times
sn}$, we get

$\text{AM}\Big{(}\underbrace{z_{i,1},\ldots,z_{i,m_{i}}}_{i\in[n]}\enspace;\,\underbrace{s_{i,1},\ldots,s_{i,m_{i}}}_{i\in[n]}\enspace;\,k\Big{)}=\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k).\qed$

### Polynomial ideal codes as generalized equifolded affine monomial codes

Let us now show that a converse of Proposition 2.10 also holds. We will first
show a general statement, that involves working over field extensions, and
considering subcodes. Later, we will specialize to a case where we do not need
these additional operations.

We will need to consider linear codes over different fields at the same time.
So we denote $C\Big{\|}_{\mathbb{F}}$ to mean an $\mathbb{F}$-linear code $C$.

######  Proposition 2.11.

Every $\mathbb{F}$-linear polynomial ideal code is a subcode of a
$\mathbb{K}$-linear generalized equifolded affine monomial code, for some
finite-degree field extension $\mathbb{K}$ of $\mathbb{F}$.

###### Proof.

Consider a polynomial ideal code
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)\Big{\|}_{\mathbb{F}}$. Let
$\overline{\mathbb{F}}$ denote the algebraic closure of $\mathbb{F}$. So, for
every $i\in[n]$, the functional modulus $E(X,y_{i})\in\mathbb{F}[X]$
factorizes in $\overline{\mathbb{F}}[X]$ as

$E(X,y_{i})=(X-z_{i,1})^{s_{i,1}}\cdots(X-z_{i,m_{i}})^{s_{i,m_{i}}},\quad\text{for
some distinct }z_{i,1},\ldots,z_{i,m_{i}}\in\overline{\mathbb{F}}.$

Let $\mathbb{K}=\mathbb{F}\big{(}\\{z_{i,t}:t\in[m_{i}],\,i\in[n]\\}\big{)}$,
which is the smallest field extension of $\mathbb{F}$ containing all roots of
the functional moduli $E(X,y_{i}),\,i\in[n]$. Then clearly, $\mathbb{K}$ is a
finite-degree field extension of $\mathbb{F}$. Since
$E(X,y_{1}),\ldots,E(X,y_{n})$ are pairwise coprime in $\mathbb{F}[X]$, these
are also pairwise coprime in $\mathbb{K}[X]$, and further, the $z_{i,t}$-s are
all distinct elements.

By Proposition 2.10, there is a block diagonal matrix
$U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{K}^{sn\times sn}$ (independent of
$k\in[sn]$) such that

$\displaystyle\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)\Big{\|}_{\mathbb{K}}$
$\displaystyle=\text{AM}\Big{(}\underbrace{z_{i,1},\ldots,z_{i,m_{i}}}_{i\in[n]},\enspace\underbrace{s_{i,1},\ldots,s_{i,m_{i}}}_{i\in[n]}\enspace;\,k\Big{)}\Big{\|}_{\mathbb{K}},$
that is,
$\displaystyle\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)\Big{\|}_{\mathbb{K}}$
$\displaystyle=\text{GAM}\Big{(}U^{-1};\underbrace{z_{i,1},\ldots,z_{i,m_{i}}}_{i\in[n]},\enspace\underbrace{s_{i,1},\ldots,s_{i,m_{i}}}_{i\in[n]}\enspace;\,k\Big{)}\Big{\|}_{\mathbb{K}}.$

Now, for any $f(X)\in\mathbb{F}[X],\,i\in[n]$, the remainder of $f(X)$ upon
division by $E(X,y_{i})\in\mathbb{F}[X]$ is the same in $\mathbb{F}[X]$ and in
$\mathbb{K}[X]$. This implies

$\displaystyle\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)\Big{\|}_{\mathbb{F}}$
$\displaystyle=\Big{\\{}[f]\in\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)\Big{\|}_{\mathbb{K}}:f(X)\in\mathbb{F}[X]\Big{\\}}$
$\displaystyle=\Big{\\{}U^{-1}\cdot\widehat{f}\in\text{GAM}\Big{(}U^{-1};\underbrace{z_{i,1},\ldots,z_{i,m_{i}}}_{i\in[n]},\enspace\underbrace{s_{i,1},\ldots,s_{i,m_{i}}}_{i\in[n]}\enspace;\,k\Big{)}\Big{\|}_{\mathbb{K}},\,f(X)\in\mathbb{F}[X]\Big{\\}}.$

This completes the proof. ∎

Let us now see that Proposition 2.11 simplifies in a special case. We say a
formal modulus $E(X,Y)\in\big{(}\mathbb{F}[Y]\big{)}[X]$ is
polylinear111111The terminology ‘polylinear’ was suggested by Srikanth
Srinivasan. if $E(X,Y)=(X-P_{1}(Y))\cdots(X-P_{s}(Y))$, for some
$P_{1}(Y),\ldots,P_{s}(Y)\in\mathbb{F}[Y]$, where $s=\deg_{X}(E)$. The
following is then immediate, by retracing the proof of Proposition 2.11.

######  Corollary 2.12.

Every $\mathbb{F}$-linear polynomial ideal code with a polylinear formal
modulus is an $\mathbb{F}$-linear generalized equifolded affine monomial code.

##  3 Duals of polynomial ideal codes

As we indicated in the introduction, our list decoding argument involves
working with the duals of polynomial ideal codes. In order to move on to
polynomial ideal codes, in this section, we prove the missing link – the class
of polynomial ideal codes with polylinear formal modulus is closed under
duality (up to a generalized transformation). (Also see Appendix A for a
different characterization of the dual of a polynomial ideal code in a
different case – where the functional moduli are all irreducible, and the
formal modulus is therefore not polylinear. We will not consider this case in
the rest of the discussion.)

We will now show that the class of generalized affine monomial codes is closed
under duality. In particular, the dual of an affine monomial code is a
generalized affine monomial code. Our proof is inspired from a simple proof of
the dual of the Reed-Solomon code, that uses Lagrange interpolation. (See
[MS77, Chapter 9].) The classic Lagrange interpolation for Reed-Solomon codes,
as well as Hermite interpolation for univariate multiplicity codes, has an
easy extension to all affine monomial codes, over all fields, due to Spitzbart
[Spi60].

######  Proposition 3.1 (Generalized Hermite interpolation [Spi60]).

121212Spitzbart [Spi60] gave the exact expression (1) for
$\mathsf{A}_{i,j}(X)$ over the reals, and in terms of the classical
derivatives. This expression extends easily to any field, in terms of the
Hasse derivatives.

Let $\mathbb{F}$ be a field, and $z_{1},\ldots,z_{n}\in\mathbb{F}$ be
distinct. Also let $s_{1},\ldots,s_{n}\geq 1$, and $N=\sum_{i=1}^{n}s_{i}$.
For every $i\in[n]$, define

$\displaystyle\mu_{i}(X)$ $\displaystyle=\prod_{i^{\prime}\neq
i}(X-z_{i^{\prime}})^{s_{i^{\prime}}},$ $\displaystyle\eta_{i}(X)$
$\displaystyle=\big{(}\mu_{i}(X)\big{)}^{-1}\,\left(\text{mod
}(X-z_{i})^{s_{i}}\right).$

Then for any $f(X)\in\mathbb{F}[X]$ with $\deg(f)<N$, we have

$f(X)=\sum_{i=1}^{n}\sum_{j=0}^{s_{i}-1}\mathsf{A}_{i,j}(X)\,\mathfrak{h}^{(j)}_{f}(z_{i}),$

where

$\displaystyle\mathsf{A}_{i,j}(X)=\mu_{i}(X)(X-z_{i})^{j}\sum_{t=0}^{s_{i}-1-j}\mathfrak{h}^{(t)}_{\eta_{i}}(z_{i})(X-z_{i})^{t},\quad\text{for
all }i\in[n],\,j\in[0,s_{i}-1].$ (1)

Assuming the notations in Proposition 3.1, let
$c_{i,j}=\text{coeff}(X^{N-1},\mathsf{A}_{i,j})$ for all
$i\in[n],\,j\in[0,s_{i}-1]$. Further, denote

$c(\mathsf{A})_{i}=\begin{bmatrix}c_{i,0}&c_{i,1}&\cdots&c_{i,s_{i}-1}\\\
c_{i,1}&&\text{\reflectbox{$\ddots$}}&\\\
\vdots&\text{\reflectbox{$\ddots$}}&&\\\
c_{i,s_{i}-1}&&&\end{bmatrix}_{s_{i}\times s_{i}}\text{ for
}i\in[n],\quad\text{and}\quad
c(\mathsf{A})=\begin{bmatrix}c(\mathsf{A})_{1}&&\\\ &\ddots&\\\
&&c(\mathsf{A})_{n}\end{bmatrix}_{N\times N}.$

Let us make a quick observation.

######  Observation 3.2.

The matrix $c(\mathsf{A})$ is block invertible.

###### Proof.

Fix any $i\in[n]$. We have $\eta_{i}(X)\mu_{i}(X)\equiv 1\,\left(\text{mod
}(X-z_{i})^{s_{i}}\right)$, and so $\eta_{i}(z_{i})\mu_{i}(z_{i})\neq 0$,
which implies $\eta_{i}(z_{i})\neq 0$. So from (1), we get
$c_{i,s_{i}-1}=\text{coeff}(X^{N-1},\mathsf{A}_{i,s_{i}-1})=\mathfrak{h}^{(0)}_{\eta_{i}}(z_{i})=\eta_{i}(z_{i})\neq
0$. This means
$\det(c(\mathsf{A})_{i})=(-1)^{\binom{s_{i}}{2}}c_{i,s_{i}-1}\neq 0$, that is,
$c(\mathsf{A})_{i}$ is invertible. This completes the proof. ∎

We are now ready to prove the characterization of duals of generalized affine
monomial codes.

######  Theorem 3.3.

Let $\mathbb{F}$ be a field, and $z_{1},\ldots,z_{n}\in\mathbb{F}$ be
distinct. Also let $s_{1},\ldots,s_{n}\geq 1$, and $N=\sum_{i=1}^{n}s_{i}$.
For any $k\in[N]$, and block invertible matrix
$U=\text{diag}(U_{1},\ldots,U_{n})\in\mathbb{F}^{N\times N}$ with
$U_{i}\in\mathbb{F}^{s_{i}\times s_{i}},\,i\in[n]$, we have

$\text{GAM}(U;z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)^{\perp}=\text{GAM}((c(\mathsf{A})\cdot
U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}};z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};N-k).$

In particular,

$\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)^{\perp}=\text{GAM}(c(\mathsf{A})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}};z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};N-k).$

###### Proof of Theorem 3.3.

Consider any $f(X),g(X)\in\mathbb{F}[X]$ with $\deg(f)<k,\,\deg(g)<N-k$. So
Proposition 3.1 gives

$f(X)g(X)=\sum_{i=1}^{n}\sum_{j=0}^{s_{i}-1}\mathsf{A}_{i,j}(X)\,\mathfrak{h}^{(j)}_{fg}(z_{i}).$

Further, by the product rule for Hasse derivatives, we get

$\displaystyle\text{coeff}(X^{N-1},fg)$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=0}^{s_{i}-1}c_{i,j}\,\mathfrak{h}^{(j)}_{fg}(z_{i})$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=0}^{s_{i}-1}c_{i,j}\sum_{j^{\prime}=0}^{j}\mathfrak{h}^{(j^{\prime})}_{f}(z_{i})\,\mathfrak{h}^{(j-j^{\prime})}_{g}(z_{i})$
$\displaystyle=\sum_{i=1}^{n}\big{(}\widehat{g}_{i}\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
c(\mathsf{A})_{i}\cdot\widehat{f}_{i}$
$\displaystyle=\sum_{i=1}^{n}\big{(}c(\mathsf{A})_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\widehat{g}_{i}\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\widehat{f}_{i}$
$\displaystyle=\sum_{i=1}^{n}\big{(}(c(\mathsf{A})_{i}\cdot
U_{i}^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\widehat{g}_{i}\big{)}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\big{(}U_{i}\cdot\widehat{f}_{i}\big{)}.$
(2)

Since $\deg(fg)<N-1$, we have $\text{coeff}(X^{N-1},fg)=0$, and so from (2),
we get the identity

$\big{(}(c(\mathsf{A})\cdot
U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\widehat{g}\big{)}\cdot\big{(}U\cdot\widehat{f}\big{)}=0.$

Thus

$\text{GAM}(U;z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)^{\perp}\subseteq\text{GAM}((c(\mathsf{A})\cdot
U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}};z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};N-k).$

Further, both the above vector spaces have dimension $N-k$, and this completes
the proof. ∎

We can now quickly describe the duals of polynomial ideal codes, with
polylinear moduli.

######  Theorem 3.4.

Let $\mathbb{F}$ be a field, and $E(X,Y)\in\big{(}\mathbb{F}[Y]\big{)}[X]$ be
a polylinear modulus with $\deg(E)=s$. Also let
$y_{1},\ldots,y_{n}\in\mathbb{F}$ be distinct. Then there exists a block
invertible matrix $\Gamma\in\mathbb{F}^{sn\times sn}$ such that for any
$k\in[sn]$, and block invertible $U\in\mathbb{F}^{sn\times sn}$, we have

$\mathbf{GPI}_{E}(U;y_{1},\ldots,y_{n};k)^{\perp}=\mathbf{GPI}_{E}((\Gamma\cdot
U^{-1})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}};y_{1},\ldots,y_{n};sn-k).$

In particular,

$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)^{\perp}=\mathbf{GPI}_{E}(\Gamma^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}};y_{1},\ldots,y_{n};sn-k).$

###### Proof.

Immediate consequence of Theorem 3.3 and Corollary 2.12. ∎

##  4 Algebraic folded GM-MDS theorem

For any column vector
$a=\begin{bmatrix}a_{1}&\cdots&a_{n}\end{bmatrix}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\in\mathbb{F}^{n}$,
we say $i\in[n]$ is a zero of $a$ if $a_{i}=0$. Let $\mathcal{Z}(a)$ denote
the set of all zeros of $a$. Let $C\subseteq\mathbb{F}^{n}$ be a
$k$-dimensional unfolded linear code with a generator matrix
$G=\begin{bmatrix}G_{1}&\cdots&G_{k}\end{bmatrix}\in\mathbb{F}^{n\times k}$.
It is folklore (see [DSDY13, DSY14]) that if $C$ is MDS, then
$\big{|}\bigcap_{t\in I}\mathcal{Z}(G_{t})\big{|}\leq k-|I|$, for all
$I\subseteq[k],\,I\neq\emptyset$. The _GM-MDS conjecture_ asserts a converse
of sorts.

Define a set system $\\{Z_{1},\ldots,Z_{k}\\}\subseteq 2^{[n]}$ to be an MDS
zero pattern131313These are called _generic zero patterns_ in [BGM23]. if

$\bigg{|}\bigcap_{t\in I}Z_{t}\bigg{|}\leq k-|I|,\quad\text{for all
}I\subseteq[k],\,I\neq\emptyset.$

Further, we say a matrix
$M=\begin{bmatrix}M_{1}&\cdots&M_{k}\end{bmatrix}\in\mathbb{F}^{n\times k}$
contains $\\{Z_{1},\ldots,Z_{k}\\}$ if $Z_{t}\subseteq\mathcal{Z}(M_{t})$ for
all $t\in[k]$, and say $M$ attains $\\{Z_{1},\ldots,Z_{k}\\}$ if $MU$ contains
$\\{Z_{1},\ldots,Z_{k}\\}$, for some invertible matrix
$U\in\mathbb{F}^{k\times k}$. The GM-MDS conjecture states the following, and
was proved by Yildiz and Hassibi [YH19] and Lovett [Lov21]. It is easily seen
that the statement is true, by the probabilistic method, if $|\mathbb{F}|$ is
sufficiently large (see [DSDY13]). The proofs by [YH19, Lov21] optimized the
field size.

######  Theorem 4.1 (GM-MDS theorem [YH19, Lov21]).

Assume $|\mathbb{F}|\geq n-k+1$. If $\\{Z_{1},\ldots,Z_{k}\\}\subseteq
2^{[n]}$ is an MDS zero pattern, then a generator matrix of some
$k$-dimensional MDS linear code in $\mathbb{F}^{n}$ contains
$\\{Z_{1},\ldots,Z_{k}\\}$.

In this section, we will obtain an algebraic version of Theorem 4.1 for folded
codes. Let us begin with some basics.

###  4.1 Folded zero patterns, and folded MDS matrices

Consider the vector space $\mathbb{F}^{sn}$. The coordinates of
$\mathbb{F}^{sn}$ are indexed by $[n]\times[0,s-1]$, that is, we write any
$a\in\mathbb{F}^{n}$ as $a=(a_{1},\ldots,a_{n})$, where
$a_{i}=(a_{i,0},\ldots,a_{i,s-1})$ for all $i\in[n]$. Recall that the
$s$-folded Hamming distance function $\Delta_{n}^{(s)}$ on $\mathbb{F}^{sn}$
is defined by

$\Delta_{n}^{(s)}(a,b)=|\\{i\in[n]:a_{i}\neq b_{i}\\}|,\quad\text{for all
}a,b\in\mathbb{F}^{sn}.$

For convenience, we will introduce two set operators – _folding_ and
_unfolding_. For any $A\subseteq[n]\times[0,s-1]$, the $s$-folding of $A$ is
defined by $A\big{\downarrow}^{s}=\\{i\in[n]:\\{i\\}\times[0,s-1]\subseteq
A\\}$. For any $A\subseteq[n]$, the $s$-unfolding of $A$ is defined by
$A\big{\uparrow}_{s}=A\times[0,s-1]$.

For any $a=(a_{1},\ldots,a_{n})\in\mathbb{F}^{sn},\,a\neq 0^{sn}$, we say
$i\in[n]$ is an $s$-folded zero of $a$ if $a_{i}=0^{s}$. Let
$\mathcal{Z}^{(s)}(a)$ denote the set of all $s$-folded zeros of $a$. We now
define a set system $\\{Z_{1},\ldots,Z_{k}\\}\subseteq 2^{[n]}$ to be an
$s$-folded MDS zero pattern if the unfolded set system
$\big{\\{}Z_{1}\big{\uparrow}_{s},\ldots,Z_{k}\big{\uparrow}_{s}\big{\\}}\subseteq
2^{[n]\times[0,s-1]}$ is an MDS zero pattern. This implies that

$\bigg{|}\bigcap_{t\in
I}Z_{t}\bigg{|}\leq\left\lfloor\frac{k-|I|}{s}\right\rfloor,\quad\text{for all
}I\subseteq[k],\,I\neq\emptyset.$

It follows immediately that if $C\subseteq\mathbb{F}^{sn}$ is a
$k$-dimensional $s$-folded linear MDS code with a generator matrix
$G=\begin{bmatrix}G_{1}&\cdots&G_{k}\end{bmatrix}\in\mathbb{F}^{sn\times k}$,
then $\\{\mathcal{Z}^{(s)}(G_{1}),\ldots,\mathcal{Z}^{(s)}(G_{k})\\}$ is an
$(s,n,k)$-MDS zero pattern.

Now, let
$M=\begin{bmatrix}M_{1}&\cdots&M_{k}\end{bmatrix}\in\mathbb{F}^{sn\times k}$
be a full rank matrix. We define the $s$-folded zero pattern of $M$ by
$\mathcal{Z}^{(s)}(M)=\\{\mathcal{Z}^{(s)}(M_{1}),\ldots,\mathcal{Z}^{(s)}(M_{k})\\}$.
Further, we say $M$ is an $s$-folded MDS matrix if $\mathcal{Z}^{(s)}(M)$ is
an $s$-folded MDS zero pattern. We say a matrix $M\in\mathbb{F}^{sn\times k}$
contains $\\{Z_{1},\ldots,Z_{k}\\}$ if $\mathcal{Z}^{(s)}(M_{t})\supseteq
Z_{t}$ for all $t\in[k]$, and say $M$ attains $\\{Z_{1},\ldots,Z_{k}\\}$ if
there exists an invertible matrix $U\in\mathbb{F}^{k\times k}$ such that $MU$
contains $\\{Z_{1},\ldots,Z_{k}\\}$.

Towards proving or algebraic version of Theorem 4.1 for folded codes, we will
need to first show that polynomial ideal codes are MDS.

###  4.2 Polynomial ideal codes are MDS

It was noted in earlier works [Kra03, GR08, RT97, KSY14, GW13] that folded
Reed-Solomon codes and univariate multiplicity codes, and more generally in
[BHKS21] that affine folded Reed-Solomon codes are MDS. In this section, we
show that in fact this extends to all polynomial ideal codes. To this end, we
first show that affine monomial codes are MDS, and then use this to conclude
that all polynomial ideal codes are MDS.

######  Proposition 4.2.

Let $z_{1},\ldots,z_{n}\in\mathbb{F}$ be distinct. Also let
$s_{1},\ldots,s_{n}\geq 1$, and $N\coloneqq\sum_{i=1}^{n}s_{i}$. For every
$k\in[N]$, the affine monomial code
$\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$ is MDS.

###### Proof.

Clearly, the dimension of $\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$
is $k$, and so by the Singleton bound, the minimum distance of
$\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$ is at most $N-k+1$.
Further, consider any $f(X)\in\mathbb{F}[X]$ with $\deg(f)<k$. Define

$\xi(f)=\big{\\{}(i,j)\in\mathbb{N}^{2}:i\in[n],\,j=\min\big{(}\\{s_{i}\\}\cup\\{t\geq
0:\mathfrak{h}_{f}^{(t)}(z_{i})\neq 0\\}\big{)}\big{\\}}.$

The following are then immediate.

  1. (a)

$(i,j)\in\xi(f)$ if and only if $(X-z_{i})^{j}$ divides $f(X)$.

  2. (b)

$\Delta_{N}(\widehat{f},0^{N})=N-\sum_{(i,j)\in\xi(f)}j$.

Since $\deg(f)<k$, from (a) above, we have $\sum_{(i,j)\in\xi(f)}j\leq k-1$.
Then, from (b) above, we get $\Delta_{N}(\widehat{f},0^{N})\geq N-K+1$. So the
minimum distance of $\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$ is at
least $N-k+1$. Thus, $\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$ is
MDS. ∎

######  Remark 4.3.

Let us quickly illustrate a codeword in
$\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$ that attains the minimum
distance $N-k+1$. Denote $s_{0}=0$. So there is a unique $r\in[0,n-1]$ such
that $k-1=\sum_{i=0}^{r}s_{i}+k^{\prime},\,k^{\prime}\in[0,s_{r+1}-1]$. It
then follows immediately that for the polynomial

$f(X)\coloneqq(X-z_{1})^{s_{1}}\cdots(X-z_{r})^{s_{r}}(X-z_{r+1})^{k^{\prime}},$

we have $\widehat{f}\in\text{AM}(z_{1},\ldots,z_{n};s_{1},\ldots,s_{n};k)$,
and further,
$\Delta_{N}(\widehat{f},0^{N})=N-(\sum_{i=0}^{r}s_{i}+k^{\prime})=N-k+1$.

An immediate corollary of Proposition 2.11 is that polynomial ideal codes are
MDS.

######  Corollary 4.4.

The polynomial ideal code $\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ is MDS.

###### Proof.

By Proposition 2.11, there exist

  * •

a sufficiently large field extension $\mathbb{K}$ of $\mathbb{F}$,

  * •

suitable points $z_{i,1},\ldots,z_{i,m_{i}}\in\mathbb{K}$ for each $i\in[n]$,

  * •

suitable integers $s_{i,1},\ldots,s_{i,m_{i}}\in\mathbb{Z}^{+}$ with
$\sum_{t=1}^{m_{i}}s_{i,t}=s$ for each $i\in[n]$, and

  * •

a suitable block invertible matrix $V\in\mathbb{K}^{sn\times sn}$,

such that

$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)\Big{\|}_{\mathbb{F}}=\Big{\\{}V\cdot\widehat{f}:\widehat{f}\in\text{AM}\Big{(}\underbrace{z_{i,1},\ldots,z_{i,m_{i}}}_{i\in[n]},\enspace\underbrace{s_{i,1},\ldots,s_{i,m_{i}}}_{i\in[n]}\enspace;\,k\Big{)}\Big{\|}_{\mathbb{K}},\,f(X)\in\mathbb{F}[X]\Big{\\}}.$

Let $G\in\mathbb{K}^{sn\times k}$ be a generator matrix of
$\text{AM}\Big{(}\underbrace{z_{i,1},\ldots,z_{i,m_{i}}}_{i\in[n]},\enspace\underbrace{s_{i,1},\ldots,s_{i,m_{i}}}_{i\in[n]}\enspace;\,k\Big{)}\Big{\|}_{\mathbb{K}}$
such that for every $f(X)\in\mathbb{K}[X],\,\deg(f)<k$, we have
$\widehat{f}=G\cdot f$. Now note that $G_{E,k}(y_{[n]})\in\mathbb{F}^{sn\times
k}$ is a generator matrix of
$\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)\Big{\|}_{\mathbb{F}}$, and
$[f]=G_{E,k}(y_{[n]})\cdot f$ for every $f(X)\in\mathbb{F}[X],\,\deg(f)<k$.
Thus, we get $G_{E,k}(y_{[n]})=V\cdot G$. By Proposition 4.2, $G$ is an MDS
matrix, and since $V$ is block invertible, we conclude that $G_{E,k}(y_{[n]})$
is an MDS matrix. Hence, $\mathbf{PI}_{E}(y_{1},\ldots,y_{n};k)$ is MDS. ∎

###  4.3 Folded Hall’s theorem, and an algebraic folded GM-MDS theorem

The GM-MDS conjecture was originally posed by Dau, Song, and Yuen [DSY14], who
also proposed a stronger _algebraic GM-MDS conjecture_ , which states that
every unfolded MDS zero pattern is attained by some unfolded MDS generic
matrix. This was the statement proved by Yildiz and Hassibi [YH19], and Lovett
[Lov21]. We will follow a similar approach, and prove an _algebraic folded GM-
MDS theorem_. We will have an additional mild restriction on the _degree_ of
polynomials141414We are really interested in asserting that the folded version
of the GM-MDS theorem holds asymptotically. So the restriction on the degree
is mild, since we would still get infinitely many instances where the
assertion would hold. that we consider, as well as the formal modulus
$E(X,Y)$.

######  Definition 4.5.

We say a polylinear formal modulus $E(X,Y)\in\big{(}\mathbb{F}[Y]\big{)}[X]$
is completely $s$-bounded if there exists $c=c(s)>0$ (independent of all other
parameters) such that for the factorization
$E(X,Y)=(X-\phi_{1}(Y))\cdots(X-\phi_{s}(Y))$, we have $\deg(\phi_{j})\leq
c(s)$, for all $j\in[s]$.

Note that we will usually also assume Condition 2.1. So this means
$\deg(\phi_{j})=O(1)$ in the above definition.

For $k\in[sn]$, and for any
$Z\subseteq[n],\,|Z|\leq\left\lfloor\frac{k-1}{s}\right\rfloor$, define

$P_{Z}(X,Y_{1},\ldots,Y_{n})=\bigg{(}\prod_{i\in
Z}E(X,Y_{i})\bigg{)}X^{k-1-s|Z|}.$

######  Theorem 4.6 (Algebraic folded GM-MDS theorem).

Assume Condition 2.1, and suppose
$E(X,Y)\in\big{(}\mathbb{F}_{q}[Y]\big{)}[X]$ is a polylinear completely
$s$-bounded formal modulus. Consider the generic field
$\mathbb{F}_{q}(Y_{1},\ldots,Y_{n})$. Let $k\in[sn]$ such that $s$ divides
$k-1$. Let $\\{Z_{1},\ldots,Z_{k}\\}\subseteq 2^{[n]}$ be any $s$-folded MDS
zero pattern. Then there exists a generator matrix of the generic polynomial
ideal code $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$ that contains
$\\{Z_{1},\ldots,Z_{k}\\}$.

We say a matrix $M\in\mathbb{F}^{sn\times k}$ is $s$-folded ZP-
MDS151515[BGM23] define the unfolded version of ZP-MDS, and call it ‘GZP’,
which stands for _generic zero patterns_. Also, they consider a finer notion
of ‘$\text{GZP}(\ell)$’, where $\ell\geq 1$ is a parameter. We do not require
this finer notion explicitly, although it will appear implicitly in our
proofs. if $M$ attains every $s$-folded MDS zero pattern
$\\{Z_{1},\ldots,Z_{k}\\}$. We emphasize that this means for every $s$-folded
MDS zero pattern $\\{Z_{1},\ldots,Z_{k}\\}$, there exists an invertible matrix
$U\in\mathbb{F}^{k\times k}$, _possibly depending on_
$\\{Z_{1},\ldots,Z_{k}\\}$, such that $MU$ contains
$\\{Z_{1},\ldots,Z_{k}\\}$.

We note an important corollary of Theorem 4.6, which we will need later.
Theorem 3.4 implies that a parity check matrix of the polynomial ideal code
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$ is
$H_{E,k}(Y_{[n]})\coloneqq\Gamma^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
G_{E,sn-k}(Y_{[n]})$.

######  Corollary 4.7.

Assume Condition 2.1, and suppose
$E(X,Y)\in\big{(}\mathbb{F}_{q}[Y]\big{)}[X]$ is a polylinear completely
$s$-bounded formal modulus. Consider the generic field
$\mathbb{F}_{q}(Y_{1},\ldots,Y_{n})$. Let $k\in[sn]$, and consider the generic
polynomial ideal code $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$.

  1. (a)

If $s$ divides $k-1$, then the generator matrix $G_{E,k}(Y_{[n]})$ is
$s$-folded ZP-MDS.

  2. (b)

If $s$ divides $k+1$, then the parity check matrix $H_{E,k}(Y_{[n]})$ is
$s$-folded ZP-MDS.

###### Proof.

If $s$ divides $k-1$, then the assertion of Theorem 4.6 is that
$G_{E,k}(Y_{[n]})$ is $s$-folded ZP-MDS. If $s$ divides $k+1$, then $s$
divides $sn-k-1$. So $G_{E,sn-k}(Y_{[n]})$ is $s$-folded ZP-MDS, and hence,
$H_{E,k}(Y_{[n]})=\Gamma^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot
G_{E,sn-k}(Y_{[n]})$ is $s$-folded ZP-MDS. ∎

The statement of the algebraic GM-MDS conjecture in [DSY14] made sense after
obtaining an _extended_ zero pattern for any given MDS zero pattern. This was
guaranteed by a generalization of Hall’s theorem in [DSY14, Theorem
2.2].161616This is, in fact, an instance of a much more general result in
_transversal theory_ in combinatorics by Welsh [Wel71]. We will need a variant
of the same for the folded setting, which we call the _folded Hall’s theorem_.
In the folded setting, we extend the zero patterns in two steps – the first is
an _almost extension_ which is a folded analogue of the extension given by
Hall’s theorem, and the second is the final _tight extension_ which is a more
elementary extension by increasing the length of the zero patterns.

######  Theorem 4.8 (Folded Hall’s theorem).

Let $s\geq 1,\,K\leq sN$. Consider subsets $Z_{1},\ldots,Z_{K}\subseteq[N]$
such that

$\displaystyle\bigg{|}\bigcap_{t\in I}Z_{t}\bigg{|}$
$\displaystyle\leq\left\lfloor\frac{K-|I|}{s}\right\rfloor,$
$\displaystyle\text{for all }I\subseteq[K],\,I\neq\emptyset.$ (3)

  1. (a)

_(Almost extension)_ There exist subsets $Z_{t}\subseteq
Z^{\prime}_{t}\subseteq[N],\,t\in[K]$ such that

$\displaystyle\bigg{|}\bigcap_{t\in I}Z^{\prime}_{t}\bigg{|}$
$\displaystyle\leq\left\lfloor\frac{K-|I|}{s}\right\rfloor,$
$\displaystyle\text{for all }I\subseteq[K],\,I\neq\emptyset,$ and
$\displaystyle|Z^{\prime}_{t}|$
$\displaystyle\in\left\\{\left\lfloor\frac{K}{s}\right\rfloor-1,\left\lfloor\frac{K-1}{s}\right\rfloor\right\\},$
$\displaystyle\text{for all }t\in[K].$

  2. (b)

_(Tight extension)_ There exist subsets $Z_{t}\subseteq
Z^{\prime\prime}_{t}\subseteq[N+K],\,t\in[K]$ such that

$\displaystyle\bigg{|}\bigcap_{t\in I}Z^{\prime\prime}_{t}\bigg{|}$
$\displaystyle\leq\left\lfloor\frac{K-|I|}{s}\right\rfloor,$
$\displaystyle\text{for all }I\subseteq[K],\,I\neq\emptyset,$ and
$\displaystyle|Z^{\prime\prime}_{t}|$
$\displaystyle=\left\lfloor\frac{K-1}{s}\right\rfloor,$
$\displaystyle\text{for all }t\in[K].$

###### Proof.

  1. (a)

We assume that $Z_{1},\ldots,Z_{K}$ are maximal with respect to satisfying
(3), that is, adding an element to any one of $Z_{1},\ldots,Z_{K}$ would
violate (3). Otherwise, we add elements until maximality is attained, and then
proceed with our argument. Now suppose the assertion is not true. Without loss
of generality, let $|Z_{1}|<\left\lfloor K/s\right\rfloor-1$. So, choose
$a,b\in[N]\setminus Z_{1},\,a\neq b$, and
$A,B\subseteq[K],\,A,B\neq\emptyset,\,1\not\in A\cup B$ such that

$\bigg{|}(Z_{1}\sqcup\\{a\\})\cap\bigcap_{t\in
A}Z_{t}\bigg{|}>\left\lfloor\frac{K-|A|-1}{s}\right\rfloor,\quad\text{and}\quad\bigg{|}(Z_{1}\sqcup\\{b\\})\cap\bigcap_{t\in
B}Z_{t}\bigg{|}>\left\lfloor\frac{K-|B|-1}{s}\right\rfloor.$

So we have the inequalities

$\displaystyle\left\lfloor\frac{K-|A|-1}{s}\right\rfloor$
$\displaystyle<\bigg{|}(Z_{1}\sqcup\\{a\\})\cap\bigcap_{t\in
A}Z_{t}\bigg{|}\leq\bigg{|}\bigcap_{t\in
A}Z_{t}\bigg{|}=\left\lfloor\frac{K-|A|}{s}\right\rfloor,$
$\displaystyle\text{and}\quad\left\lfloor\frac{K-|B|-1}{s}\right\rfloor$
$\displaystyle<\bigg{|}(Z_{1}\sqcup\\{b\\})\cap\bigcap_{t\in
B}Z_{t}\bigg{|}\leq\bigg{|}\bigcap_{t\in
B}Z_{t}\bigg{|}=\left\lfloor\frac{K-|B|}{s}\right\rfloor.$

If $s$ does not either divide $K-|A|$ or $K-|B|$, then this would violate one
of the above inequalities. So $s$ divides both $K-|A|$ and $K-|B|$. This
implies

$\displaystyle\bigg{|}\bigcap_{t\in A}Z_{t}\bigg{|}$
$\displaystyle=\bigg{|}(Z_{1}\sqcup\\{a\\})\cap\bigcap_{t\in
A}Z_{t}\bigg{|}=\left\lfloor\frac{K-|A|}{s}\right\rfloor=\frac{K-|A|}{s},$
$\displaystyle\text{and}\quad\bigg{|}\bigcap_{t\in B}Z_{t}\bigg{|}$
$\displaystyle=\bigg{|}(Z_{1}\sqcup\\{b\\})\cap\bigcap_{t\in
B}Z_{t}\bigg{|}=\left\lfloor\frac{K-|B|}{s}\right\rfloor=\frac{K-|B|}{s}.$

Therefore,

$\bigg{|}\bigcap_{t\in A}Z_{t}\cap\bigcap_{t\in
B}Z_{t}\bigg{|}=\bigg{|}\bigcap_{t\in A\cup
B\cup\\{1\\}}Z_{t}\bigg{|}\leq\left\lfloor\frac{K-|A\cup
B|-1}{s}\right\rfloor.$

Further,

$\bigg{|}\bigcap_{t\in A}Z_{t}\cup\bigcap_{t\in
B}Z_{t}\bigg{|}\begin{cases}\leq\big{|}\bigcap_{t\in A\cap
B}Z_{t}\big{|}\leq\Big{\lfloor}\frac{K-|A\cap B|}{s}\Big{\rfloor},&\text{if
}A\cap B\neq\emptyset,\\\\[15.0pt]
\leq|Z_{1}\sqcup\\{a,b\\}|\leq\Big{\lfloor}\frac{K}{s}\Big{\rfloor}=\Big{\lfloor}\frac{K-|A\cap
B|}{s}\Big{\rfloor}&\text{if }A\cap B=\emptyset.\end{cases}$

Thus, we get the inequalities

$\displaystyle\frac{2K-|A|-|B|}{s}$
$\displaystyle=\frac{K-|A|}{s}+\frac{K-|B|}{s}$
$\displaystyle=\bigg{|}\bigcap_{t\in A}Z_{t}\bigg{|}+\bigg{|}\bigcap_{t\in
B}Z_{t}\bigg{|}$ $\displaystyle=\bigg{|}\bigcap_{t\in A}Z_{t}\cap\bigcap_{t\in
B}Z_{t}\bigg{|}+\bigg{|}\bigcap_{t\in A}Z_{t}\cup\bigcap_{t\in
B}Z_{t}\bigg{|}$ $\displaystyle\leq\left\lfloor\frac{K-|A\cup
B|-1}{s}\right\rfloor+\left\lfloor\frac{K-|A\cap B|}{s}\right\rfloor$
$\displaystyle\leq\frac{2K-|A|-|B|}{s}-\frac{1}{s},$

which is a contradiction. This proves the claim.

  2. (b)

We begin with the set system
$\\{Z^{\prime}_{1},\ldots,Z^{\prime}_{K}\\}\subseteq[N]$ as in the assertion
of (a). Now define

$Z^{\prime\prime}_{t}=\begin{cases}Z^{\prime}_{t}&\text{if
}|Z^{\prime}_{t}|=\left\lfloor\frac{K-1}{s}\right\rfloor,\\\\[5.0pt]
Z^{\prime}_{t}\sqcup\\{N+t\\}&\text{if
}|Z^{\prime}_{t}|<\left\lfloor\frac{K-1}{s}\right\rfloor.\end{cases}$

Then it is immediate that
$\\{Z^{\prime\prime}_{1},\ldots,Z^{\prime\prime}_{K}\\}$ satisfies the claim.∎

###  4.4 A technical lemma, and proof of the algebraic folded GM-MDS theorem

In order to prove Theorem 4.6, we will extend a technical lemma by Lovett
[Lov21]171717A slightly different version was proved by [YH19], towards their
proof of the algebraic GM-MDS theorem. to our folded setting. Let
$\mathcal{V}=\\{v_{1},\ldots,v_{m}\\}\subseteq\mathbb{N}^{n}$, and let $k\geq
1$. Define

$\displaystyle P(k,s,v)$
$\displaystyle=\bigg{\\{}\bigg{(}\prod_{i=1}^{n}E(X,Y_{i})^{v(i)}\bigg{)}X^{e}:e\in[0,k-1-s|v|]\bigg{\\}},\quad\text{for
all }v\in\mathcal{V},$ $\displaystyle\text{and}\quad P(k,s,\mathcal{V})$
$\displaystyle=\bigcup_{v\in\mathcal{V}}P(k,v).$

We say $\mathcal{V}=\\{v_{1},\ldots,v_{m}\\}\subseteq\mathbb{N}^{n}$ satisfies
$V^{*}(k,s)$ property if it satisfies three conditions $V^{*}_{1}(k,s)$,
$V^{*}_{2}(k,s)$, and $V^{*}_{3}(k,s)$, as follows.

  1. $V^{*}_{1}(k,s)$:

$v_{t}\in\\{0,1\\}^{n-1}\times\mathbb{N}$, for all $t\in[m]$.

  2. $V^{*}_{2}(k,s)$:

$s|v_{t}|\leq k-1$, for all $t\in[m]$.

  3. $V^{*}_{3}(k,s)$:

$\sum_{t\in I}(k-s|v_{t}|)+s\big{|}\bigwedge_{t\in I}v_{t}\big{|}\leq k$, for
all $I\subseteq[m],\,I\neq\emptyset$.

We will now state the lemma, and prove it in Section 4.5.

######  Lemma 4.9.

If $\mathcal{V}=\\{v_{1},\ldots,v_{m}\\}\subseteq\mathbb{N}^{n}$ satisfies
$V^{*}(k,s)$, then the set of polynomials $P(k,s,\mathcal{V})$ is linearly
independent over $\mathbb{F}(Y_{1},\ldots,Y_{n})$.

Lemma 4.9 will imply our algebraic folded GM-MDS theorem 4.6. Let us see this
implication quickly. Our argument is similar to that of [Lov21], but we need
an additional component involving random projections.

#### Implication: Lemma 4.9 $\implies$ Theorem 4.6

Assume Condition 2.1, and suppose
$E(X,Y)\in\big{(}\mathbb{F}_{q}[Y]\big{)}[X]$ is polylinear, completely
$s$-bounded. Let $k\in[sn]$ such that $s$ divides $k-1$. Let
$\\{Z_{1},\ldots,Z_{k}\\}\subseteq 2^{[n]}$ be any $s$-folded MDS zero
pattern. By the folded Hall’s theorem 4.8, there exist subsets $Z_{t}\subseteq
Z^{\prime\prime}_{t}\subseteq[n+k]$ with $|Z^{\prime\prime}_{t}|=(k-1)/s$ for
all $t\in[k]$, such that
$\\{Z^{\prime\prime}_{1},\ldots,Z^{\prime\prime}_{k}\\}\subseteq 2^{[n+k]}$ is
an $s$-folded MDS zero pattern.

Consider indeterminates $Y_{1},\ldots,Y_{n+k}$. Then the functional moduli
$E(X,Y_{1}),\ldots,E(X,Y_{n+k})$ are trivially pairwise coprime over
$\mathbb{F}_{q}(Y_{[n+k]})$.

Let $\mathcal{V}=\\{v_{1},\ldots,v_{k}\\}\subseteq\\{0,1\\}^{n+k}$ be defined
by $Z^{\prime\prime}_{t}=\text{supp}(v_{t}),\,t\in[k]$. So clearly,
$\mathcal{V}$ satisfies $V^{*}_{1}(k,s)$ and $V^{*}_{2}(k,s)$. Now consider
any $I\subseteq[k],\,I\neq\emptyset$. Then we have

$\sum_{t\in I}(k-s|v_{t}|)+s|v_{I}|=\sum_{t\in
I}(k-s|Z^{\prime\prime}_{t}|)+s\,\bigg{|}\bigcap_{t\in
I}Z^{\prime\prime}_{t}\bigg{|}\leq|I|+s\left\lfloor\frac{k-|I|}{s}\right\rfloor\leq
k.$

So $\mathcal{V}$ satisfies $V^{*}_{3}(k,s)$. By Lemma 4.9, the set of
polynomials $P(k,s,\mathcal{V})$ is linearly independent over
$\mathbb{F}(Y_{[n+k]})$. However,

$P(k,s,\mathcal{V})=\bigg{\\{}\prod_{i=1}^{n}E(X,Y_{i})^{v_{t}(i)}:t\in[k]\bigg{\\}},$

that is,
$P(k,s,\mathcal{V})=\\{P_{Z^{\prime\prime}_{1}}(X,Y_{[n+k]}),\ldots,P_{Z^{\prime\prime}_{k}}(X,Y_{[n+k]})\\}$,
where
$P_{Z^{\prime\prime}_{t}}(X,Y_{[n+k]})=\prod_{i=1}^{n}E(X,Y_{i})^{v_{t}(i)}$
for all $t\in[k]$. Denote $P_{t}=P_{Z^{\prime\prime}_{t}}$ for $t\in[k]$. So
we have

  1. (L.a)

$\deg(P_{t})=k-1$ for all $t\in[k]$.

  2. (L.b)

the set of polynomials $\\{P_{1}(X,Y_{[n+k]}),\ldots,P_{k}(X,Y_{[n+k]})\\}$ is
$\mathbb{F}_{q}(Y_{[n+k]})$-linearly independent, having size $k$.

Now denote

$[P_{t}](Y_{i})=\begin{bmatrix}L_{0}(P_{t})(Y_{i})\\\ \vdots\\\
L_{s-1}(P_{t})(Y_{i})\end{bmatrix},\quad\text{for all }i\in[n+k],\,t\in[k].$

By (L.a), we have

$\begin{bmatrix}[P_{t}](Y_{1})\\\ \vdots\\\ [P_{t}](Y_{n})\\\ \vdots\\\
[P_{t}](Y_{n+k})\end{bmatrix}\in\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n},\ldots,Y_{n+k};k),\quad\text{for
all }t\in[k].$

By (L.b), the $\mathbb{F}_{q}(Y_{[n+k]})$-linear span of
$\\{P_{1}(X,Y_{[n+k]}),\ldots,P_{k}(X,Y_{[n+k]})\\}$ is the set of all
polynomials in $\mathbb{F}_{q}(Y_{[n+k]})[X]$ with degree at most $k-1$. So,
we can conclude that the matrix

$G(Y_{[n]},Y_{[n+1,n+k]})\coloneqq\begin{bmatrix}[P_{1}](Y_{1})&\cdots&[P_{k}](Y_{1})\\\
\vdots&\ddots&\vdots\\\ [P_{1}](Y_{n})&\cdots&[P_{k}](Y_{n})\\\
\vdots&\ddots&\vdots\\\ [P_{1}](Y_{n+k})&\cdots&[P_{k}](Y_{n+k})\end{bmatrix}$

is a generator matrix of
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n},\ldots,Y_{n+k};k)$.

By Corollary 4.4, $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n},\ldots,Y_{n+k};k)$ is
MDS, and so every $k\times k$ minor of $G(Y_{[n]},Y_{[n+1,n+k]})$ is nonzero.
We will now be concerned with the submatrix of $G(Y_{[n]},Y_{[n+1,n+k]})$
given by

$\widehat{G}(Y_{[n]},Y_{[n+1,n+k]})\coloneqq\begin{bmatrix}[P_{1}](Y_{1})&\cdots&[P_{k}](Y_{1})\\\
\vdots&\ddots&\vdots\\\ [P_{1}](Y_{n})&\cdots&[P_{k}](Y_{n})\end{bmatrix}.$

So, immediately, every $k\times k$ minor of
$\widehat{G}(Y_{[n]},Y_{[n+1,n+k]})$ is nonzero. Note that
$\widehat{G}(Y_{[n]},Y_{[n+1,n+k]})$ also depends on $Y_{n+1},\ldots,Y_{n+k}$,
since the polynomials $P_{1},\ldots,P_{k}$ depend on $Y_{n+1},\ldots,Y_{n+k}$.

Now fix a nonzero $k\times k$ minor $M(X,Y_{[n]},Y_{[n+1,n+k]})$ of
$\widehat{G}(Y_{[n]},Y_{[n+1,n+k]})$. Since, by definition,
$P_{t}(X,Y_{[n]},Y_{[n+1,n+k]})$ is a polynomial in $X,Y_{[n]},Y_{[n+1,n+k]}$
over $\mathbb{F}_{q}$ for all $t\in[k]$, the Division Algorithm implies that
$M(X,Y_{[n]},Y_{[n+1,n+k]})$ is a nonzero polynomial in
$X,Y_{[n]},Y_{[n+1,n+k]}$ over $\mathbb{F}_{q}$.

Now consider independent and uniformly random points
$\boldsymbol{\beta}_{1},\ldots,\boldsymbol{\beta}_{k}\in\mathbb{F}_{q}$.
Denote
$\boldsymbol{\beta}=(\boldsymbol{\beta}_{1},\ldots,\boldsymbol{\beta}_{k})$,
and consider the random restrictions
$\mathbf{P}_{t}(X,Y_{[n]},\boldsymbol{\beta}),\,t\in[k]$. Since $E(X,Y)$ is
monic in $X$, and $\deg_{X}(E)=s$, we have $\deg(\mathbf{P}_{t})=k-1$ for all
$t\in[k]$.

We are concerned with the random matrix
$\widehat{G}(Y_{[n]},\boldsymbol{\beta})$, and its $k\times k$ minor
$M(X,Y_{[n]},\boldsymbol{\beta})$. By definition of
$\widehat{G}(Y_{[n]},Y_{[n+1,n+k]})$, it is clear that $\deg_{Y_{i}}(M)\leq
s\cdot c(s)\cdot(k-1),\,i\in[n+1,n+k]$. So

$\big{(}\deg_{Y_{n+1}}+\cdots+\deg_{Y_{n+k}}\big{)}(M)\leq s\cdot c(s)\cdot
k(k-1).$

We then get, by the Öre-DeMillo-Lipton-Schwartz-Zippel Lemma [Ö22, DL78,
Sch80, Zip79], the minor polynomial $M(X,Y_{[n]},\boldsymbol{\beta})\neq 0$
with probability at least $1-\big{(}\big{(}s\cdot c(s)\cdot
k(k-1)\big{)}/q\big{)}$. Therefore, with positive probability, we get the
following simultaneously.

  1. (R.a)

$\deg(P_{t})=k-1$ for all $t\in[k]$.

  2. (R.b)

$M(X,Y_{[n]},\boldsymbol{\beta})\neq 0$, and therefore, the matrix

$\widehat{G}(Y_{[n]},\boldsymbol{\beta})=\begin{bmatrix}[\mathbf{P}_{1}](Y_{1})&\cdots&[\mathbf{P}_{k}](Y_{1})\\\
\vdots&\ddots&\vdots\\\
[\mathbf{P}_{1}](Y_{n})&\cdots&[\mathbf{P}_{k}](Y_{n})\end{bmatrix}$

has full rank $k$ over $\mathbb{F}_{q}(Y_{[n]})$. In other words, the set of
random polynomials
$\\{\mathbf{P}_{1}(X,Y_{[n]},\boldsymbol{\beta}),\ldots,\mathbf{P}_{k}(X,Y_{[n]},\boldsymbol{\beta})\\}$
is $\mathbb{F}_{q}(Y_{[n]})$-linearly independent, having size $k$.

In other words, with positive probability,
$\widehat{G}(Y_{[n]},\boldsymbol{\beta})$ is a generator matrix of
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$.

So we choose such distinct elements $\beta_{1},\ldots,\beta_{k}\in\mathbb{F}$,
and consider the corresponding matrix
$\widetilde{G}(Y_{[n]})\coloneqq\widehat{G}(Y_{[n]},\beta_{1},\ldots,\beta_{k})$,
which is a generator matrix of $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$. Now
note that by Lemma 4.9, we already get that $G(Y_{[n]},Y_{[n+1,n+k]})$
contains $\\{Z^{\prime\prime}_{1},\ldots,Z^{\prime\prime}_{k}\\}$. So, by
definition of the polynomials $P_{t},\,t\in[k]$, this immediately implies that
$\widehat{G}(Y_{[n]},Y_{[n+1,n+k]})$ contains $\\{Z_{1},\ldots,Z_{k}\\}$, and
hence, $\widetilde{G}(Y_{[n]})$ also contains $\\{Z_{1},\ldots,Z_{k}\\}$. This
completes the proof of Theorem 4.6.

###  4.5 Proof of the technical lemma

Let us now prove Lemma 4.9. Suppose
$\mathcal{V}=\\{v_{1},\ldots,v_{m}\\}\subseteq\mathbb{N}^{n}$ satisfies
$V^{*}(k,s)$. For $I\subseteq[k]$, denote $v_{I}=\bigwedge_{t\in I}v_{t}$.
Also denote $d=|P(k,s,\mathcal{V})|=\sum_{t=1}^{m}(k-|v_{t}|)$. As in [Lov21],
we will induct on the parameters $n,k,s,m,d\geq 1$.

####  4.5.1 Base case

Our base case is arbitrarily fixed $n,s\geq 1$, and $k\leq s$. Then
$V^{*}_{2}(k,s)$ implies $m=1$ and $\mathcal{V}=\\{0^{n}\\}$. Thus,
$P(k,s,\mathcal{V})=\\{1,X,\ldots,X^{k-1}\\}$ and $d=k$. So, clearly
$P(k,s,\mathcal{V})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$.

####  4.5.2 Inductive hypothesis

We consider arbitrarily fixed $n,s\geq 1,\,k>s$, a set
$\mathcal{V}=\\{v_{1},\ldots,v_{m}\\}\subseteq\mathbb{N}^{n}$ that satisfies
$V^{*}(k,s)$, and $d=|P(k,s,\mathcal{V})|$. We assume that $\mathcal{V}$ is a
minimal set such that $P(k,s,\mathcal{V})$ is linearly dependent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$. So for any valid setting of parameters
$n^{\prime}\leq n,\,s^{\prime}\leq s,\,m^{\prime}\leq m,\,k^{\prime}\leq
k,\,d^{\prime}\leq d$ with at least one of the inequalities being strict,
corresponding to a set $\mathcal{V}^{\prime}\subseteq\mathbb{N}^{n}$
satisfying $V^{*}(k^{\prime},s^{\prime})$, the set of polynomials
$P(k^{\prime},s^{\prime},\mathcal{V}^{\prime})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$.

####  4.5.3 Induction: Main lemmas

Suppose $P(k,s,\mathcal{V})$ is not linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$, and further, $\mathcal{V}$ is a minimal set
such that this holds. Our argument now breaks into a sequence of lemmas.

######  Lemma 4.10.

For $v_{i},v_{j}\in\mathcal{V}$, if $v_{i}\leq v_{j}$, then $v_{i}=v_{j}$.

###### Proof.

Suppose there exist $i,j\in[m],\,i\neq j$ such that $v_{i}\leq v_{j}$. Then
$v_{i}\wedge v_{j}=v_{i}$. So for $I=\\{i,j\\}$, by $V^{*}_{3}(k,s)$ we get
$2k-s(|v_{i}|+|v_{j}|)+s|v_{i}|\leq k$, that is, $s|v_{j}|\geq k$, which
contradicts $V^{*}_{1}(k,s)$. Thus, the claim holds. ∎

######  Lemma 4.11.

$v_{[m]}=0^{n}$.

###### Proof.

Suppose, there exists $i_{0}\in[n]$ such that $v_{t}(i_{0})\geq 1$ for all
$t\in[m]$. Define

$\widetilde{V}=\\{\widetilde{v}_{1}\coloneqq
v_{1}-e_{i_{0}},\ldots,\widetilde{v}_{m}\coloneqq v_{m}-e_{i_{0}}\\}.$

Clearly $\widetilde{\mathcal{V}}$ satisfies $V^{*}_{1}(k-s,s)$. Further, for
every $t\in[m]$, we have $s|\widetilde{v}_{t}|=s(|v_{t}|-1)\leq k-s-1$. So
$\widetilde{\mathcal{V}}$ satisfies $V^{*}_{2}(k-s,s)$. Now consider any
$I\subseteq[m],\,I\neq\emptyset$. Since $\mathcal{V}$ satisfies
$V^{*}_{3}(k,s)$, we have

$\displaystyle\sum_{t\in I}(k-s-s|\widetilde{v}_{t}|)+s|\widetilde{v}_{I}|$
$\displaystyle=\sum_{t\in I}(k-s-s(|v_{t}|-1))+s(|v_{I}|-1)$
$\displaystyle=\sum_{t\in I}(k-s|v_{t}|)+s|v_{I}|-s$ $\displaystyle\leq k-s.$

So $\widetilde{\mathcal{V}}$ satisfies $V^{*}_{3}(k-s,s)$. Thus,
$\widetilde{\mathcal{V}}$ satisfies $V^{*}(k-s,s)$, and therefore, by the
inductive hypothesis, $P(k-s,s,\widetilde{\mathcal{V}})$ is linearly
independent over $\mathbb{F}(Y_{1},\ldots,Y_{n})$. Further, we have

$P(k,s,\mathcal{V})=\\{f(X)E(X,Y_{i_{0}}):f(X)\in
P(k-s,s,\widetilde{\mathcal{V}})\\}.$

It then follows that $P(k,s,\mathcal{V})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$. This is a contradiction, and hence
$v_{[m]}=0^{n}$. ∎

Now define a subset $I\subseteq[m],\,I\neq\emptyset$ to be tight for
$\mathcal{V}$ if equality holds in $V^{*}_{3}(k,s)$, that is, $\sum_{t\in
I}(k-s|v_{t}|)+s|v_{I}|=k$.

######  Lemma 4.12.

If $I\subseteq[m],\,I\neq\emptyset$ is tight for $\mathcal{V}$, then $|I|=1$
or $I=[m]$.

###### Proof.

Suppose $I$ is tight for $\mathcal{V}$, and $1<|I|<m$. Without loss of
generality, let $I=[c,m]$ for some $c\in[2,m-1]$. Define

$\widetilde{\mathcal{V}}=\\{\widetilde{v}_{1}\coloneqq
v_{1},\ldots,\widetilde{v}_{c-1}\coloneqq v_{c-1},\widetilde{v}_{c}\coloneqq
v_{I}\\}.$

Clearly $\widetilde{V}$ satisfies $V^{*}_{1}(k,s)$ and $V^{*}_{2}(k,s)$. Now
consider any $I^{\prime}\subseteq[c],\,I^{\prime}\neq\emptyset$. If $c\not\in
I^{\prime}$, then

$\sum_{t\in
I^{\prime}}(k-s|\widetilde{v}_{t}|)+s|\widetilde{v}_{I^{\prime}}|=\sum_{t\in
I^{\prime}}(k-s|v_{t}|)+s|v_{I^{\prime}}|\leq k.$

If $c\in I^{\prime}$, then

$\displaystyle\sum_{t\in
I^{\prime}}(k-s|\widetilde{v}_{t}|)+s|\widetilde{v}_{I^{\prime}}|$
$\displaystyle=\sum_{\begin{subarray}{c}t\in I^{\prime}\\\ t\neq
c\end{subarray}}(k-s|v_{t}|)+(k-s|v_{I}|)+s|v_{I^{\prime}\cup I}|$
$\displaystyle=\sum_{\begin{subarray}{c}t\in I^{\prime}\\\ t\neq
c\end{subarray}}(k-s|v_{t}|)+\sum_{t\in I}(k-|v_{t}|)+s|v_{I^{\prime}\cup I}|$
$I$ is tight $\displaystyle=\sum_{t\in I^{\prime}\cup
I}(k-s|v_{t}|)+s|v_{I^{\prime}\cup I}|$ $(I^{\prime}\setminus\\{c\\})\cup
I=I^{\prime}\cup I$ $\displaystyle\leq k$ $\mathcal{V}$ satisfies
$V^{*}_{3}(k,s)$.

Thus, $\widetilde{\mathcal{V}}$ satisfies $V^{*}(k,s)$, and therefore, by the
inductive hypothesis, $P(k,s,\widetilde{\mathcal{V}})$ is linearly independent
over $\mathbb{F}(Y_{1},\ldots,Y_{n})$. But

$\displaystyle|P(k,s,\widetilde{\mathcal{V}})|$
$\displaystyle=\sum_{t=1}^{c-1}|P(k,s,\widetilde{v}_{t})|+|P(k,s,\widetilde{v}_{c})|$
$\displaystyle=\sum_{t=1}^{c-1}|P(k,s,v_{t})|+|P(k,s,v_{I})|$
$\displaystyle=\sum_{t=1}^{c-1}(k-s|v_{t}|)+(k-s|v_{I}|)$
$\displaystyle=\sum_{t=1}^{c-1}(k-s|v_{t}|)+\sum_{t=c}^{m}(k-s|v_{t}|)$ $I$ is
tight $\displaystyle=|P(k,s,\mathcal{V})|.$

Further,

$\displaystyle P(k,s,\widetilde{\mathcal{V}})$
$\displaystyle=\bigsqcup_{t=1}^{c-1}P(k,s,v_{t})\sqcup P(k,s,v_{I})$
$\displaystyle=P(k,s,\mathcal{V}_{[1,c-1]})\sqcup P(k,s,v_{I}),$
$\displaystyle\text{and}\quad P(k,s,\mathcal{V})$
$\displaystyle=\bigsqcup_{t=1}^{c-1}P(k,s,v_{t})\sqcup\bigsqcup_{t=c}^{m}P(k,s,v_{t})$
$\displaystyle=P(k,s,\mathcal{V}_{[1,c-1]})\sqcup P(k,s,\mathcal{V}_{I}),$

where $\mathcal{V}_{[1,c-1]}=\\{v_{t}\in\mathcal{V}:t\in[1,c-1]\\}$ and
$\mathcal{V}_{I}=\\{v_{t}\in\mathcal{V}:t\in I\\}$. Thus,
$|P(k,s,v_{I})|=|P(k,s,\mathcal{V}_{I})|$. Clearly, $P(k,s,\mathcal{V}_{I})$
satisfies $V^{*}(k,s)$, and so by the inductive hypothesis,
$P(k,s,\mathcal{V}_{I})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$. Also, by definition, we have $\deg(f)\leq
k-1$ for all $f(X)\in P(k,s,\mathcal{V}_{I})$. Let
$Q(X,Y_{1},\ldots,Y_{n})=\prod_{i=1}^{n}E(X,Y_{i})^{v_{I}(i)}$. Since
$v_{I}\leq v_{t}$ for all $t\in I$, we conclude that $Q$ divides $f(X)$ for
all $f(X)\in P(k,s,\mathcal{V}_{I})$. Now

$\displaystyle P(k,s,v_{I})$ $\displaystyle=\\{Q\cdot
X^{e}:e\in[0,k-1-s|v_{I}|]\\},$ $\displaystyle\text{and
so}\quad\text{span}\,P(k,s,\mathcal{V}_{I})$
$\displaystyle=\\{f(X)\in\mathbb{F}[X]:\deg(f)\leq k-1,\text{ and }Q\text{
divides }f(X)\\}.$

Thus, $\text{span}\,P(k,s,\mathcal{V}_{I})\subseteq\text{span}\,P(k,s,v_{I})$,
and both vector spaces have the same dimension, which implies
$\text{span}\,P(k,s,\mathcal{V}_{I})=\text{span}\,P(k,s,v_{I})$. This means
$\text{span}\,P(k,s,\mathcal{V})\subseteq\text{span}\,P(k,s,\widetilde{\mathcal{V}})$,
and both vector spaces have the same dimension, which implies
$\text{span}\,P(k,s,\mathcal{V})=\text{span}\,P(k,s,\widetilde{\mathcal{V}})$.
Therefore, $P(k,s,\mathcal{V})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$. This is a contradiction, and hence the claim
is true. ∎

We will now prove that there must be a specific vector in $\mathcal{V}$, by
minimality of $\mathcal{V}$.

######  Lemma 4.13.

$(1^{n-1},0)\in\mathcal{V}$.

###### Proof.

Since $v_{[m]}=0^{n}$ by Lemma 4.11, there exists $t_{0}\in[m]$ such that
$v_{t_{0}}(n)=0$. Without loss of generality, assume $t_{0}=m$. We will now
show that $v_{m}=(1^{n-1},0)$. Suppose this is not true. Then there exists
$i_{0}\in[m-1]$ such that $v_{m}(i_{0})=0$. Without loss of generality, assume
$i_{0}=n-1$. Thus, we have $v_{m}(n-1)=v_{m}(n)=0$. Now define
$\widetilde{\mathcal{V}}=\\{\widetilde{v}_{1},\ldots,\widetilde{v}_{m}\\}\subseteq\mathbb{N}^{n-1}$,
where

$\widetilde{v}_{t}\coloneqq(v_{t}(1),\ldots,v_{t}(n-2),v_{t}(n-1)+v_{t}(n)),\quad\text{for
all }t\in[m].$

Clearly $\widetilde{V}$ satisfies $V^{*}_{1}(k,s)$ and $V^{*}_{2}(k,s)$. Now
consider any $I\subseteq[m],\,I\neq\emptyset$. We have the following cases.

  1. Case 1.

$|I|=1$. Then the $V^{*}_{3}(k,s)$ condition is obvious.

  2. Case 2.

$|I|=m$. Then $v_{I}(n-1)=v_{I}(n)=0$, since $v_{I}\leq v_{m}$. This means
$\widetilde{v}_{m}(n-1)=\widetilde{v}_{I}(n-1)=0$.

$\sum_{t\in I}(k-|\widetilde{v}_{t}|)+|\widetilde{v}_{I}|=\sum_{t\in
I}(k-|v_{t}|)+|v_{I}|\leq k.$

  3. Case 3.

$1<|I|<m$. So $I$ is not tight, by Lemma 4.12. This means

$\displaystyle\sum_{t\in I}(k-|v_{t}|)+|v_{I}|\leq k-1.$ (4)

Since $\mathcal{V}$ satisfies $V^{*}_{3}(k,s)$, we have
$v_{t}(n-1)\in\\{0,1\\}$ for all $t\in[m]$. Therefore
$v_{I}(n-1)\in\\{0,1\\}$, and so
$\widetilde{v}_{I}(n-1)\in\\{v_{I}(n),v_{I}(n)+1\\}$. This implies

$\displaystyle\sum_{t\in
I}(k-|\widetilde{v}_{t}|)+|\widetilde{v}_{I}|\leq\sum_{t\in
I}(k-|v_{t}|)+(|v_{I}|+1)\leq k$ by (4).

So $\widetilde{\mathcal{V}}$ satisfies $V^{*}_{3}(k,s)$. Thus,
$\widetilde{\mathcal{V}}$ satisfies $V^{*}(k,s)$, and therefore, by the
inductive hypothesis, $P(k,s,\widetilde{\mathcal{V}})$ is linearly independent
over $\mathbb{F}(Y_{1},\ldots,Y_{n-1})$. Again note that
$|\widetilde{v}_{t}|=|v_{t}|$ for all $i\in[m]$. By definition, we see that

$\displaystyle P(k,s,\mathcal{V})$
$\displaystyle=\\{P_{t,e}(X,Y_{1},\ldots,Y_{n-1},Y_{n}):t\in[m],\,e\in[0,k-1-s|v_{t}|]\\},$
$\displaystyle\text{and}\quad P(k,s,\widetilde{\mathcal{V}})$
$\displaystyle=\\{\widetilde{P}_{t,e}(X,Y_{1},\ldots,Y_{n-1}):t\in[m],\,e\in[0,k-1-s|v_{t}|]\\},$

where

$\displaystyle P_{t,e}(X,Y_{1},\ldots,Y_{n-1},Y_{n})$
$\displaystyle=\prod_{i=1}^{n-2}E(X,Y_{i})^{v_{t}(i)}\cdot
E(X,Y_{n-1})^{v_{t}(n-1)}\cdot E(X,Y_{n})^{v_{t}(n)},$
$\displaystyle\text{and}\quad\widetilde{P}_{t,e}(X,Y_{1},\ldots,Y_{n-1})$
$\displaystyle=\prod_{i=1}^{n-2}E(X,Y_{i})^{v_{t}(i)}\cdot
E(X,Y_{n-1})^{v_{t}(n-1)+v_{t}(n)}.$

So we have
$\widetilde{P}_{t,e}(X,Y_{1},\ldots,Y_{n-1})=P_{t,e}(X,Y_{1},\ldots,Y_{n-1},Y_{n-1})$,
for all pairs $(t,e)$. Now suppose $P(k,s,\mathcal{V})$ is linearly dependent
over $\mathbb{F}(Y_{1},\ldots,Y_{n})$. Then (by clearing denominators, and
dividing by common factors, if required) we conclude that there exist
polyomials $\\{w_{t,e}(Y_{1},\ldots,Y_{n})\\}_{\text{all pairs }(t,e)}$, not
all zero, satisfying $\gcd(w_{t,e}:\text{all pairs }(t,e))=1$, such that

$\displaystyle\sum_{(t,e)}w_{t,e}(Y_{1},\ldots,Y_{n-1},Y_{n})\,P_{t,e}(X,Y_{1},\ldots,Y_{n-1},Y_{n})$
$\displaystyle=0$ $\displaystyle\implies$
$\displaystyle\sum_{(t,e)}w_{t,e}(Y_{1},\ldots,Y_{n-1},Y_{n-1})\,\widetilde{P}_{t,e}(X,Y_{1},\ldots,Y_{n-1})$
$\displaystyle=0$ $\displaystyle\implies$ $\displaystyle
w_{t,e}(Y_{1},\ldots,Y_{n-1},Y_{n-1})=0,\quad\text{for all pairs }(t,e).$

This means $(Y_{n}-Y_{n-1})$ divides
$w_{t,e}(Y_{1},\ldots,Y_{n-1},Y_{n})\in\mathbb{F}[Y_{1},\ldots,Y_{n}]$, for
all pairs $(t,e)$, which contradicts that $\gcd(w_{t,e}:\text{all pairs
}(t,e))=1$. Thus, $P(k,s,\mathcal{V})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$, which is a contradiction. Hence, we get
$(1^{n-1},0)\in\mathcal{V}$. ∎

Now that we have concluded $(1^{n-1},0)\in\mathcal{V}$, without loss of
generality, assume $v_{m}=(1^{n-1},0)$. Since $\mathcal{V}$ satisfies
$V^{*}_{3}(k,s)$, we get $s|v_{m}|=s(n-1)\leq k-1$, that is,
$n-1\leq\left\lfloor\frac{k-1}{s}\right\rfloor$. Our final lemma says that
this inequality must be tight.

######  Lemma 4.14.

$n-1=\left\lfloor\frac{k-1}{s}\right\rfloor$.

###### Proof.

Suppose $n-1<\left\lfloor\frac{k-1}{s}\right\rfloor$. Define

$\widetilde{\mathcal{V}}=\\{\widetilde{v}_{1}\coloneqq
v_{1},\ldots,\widetilde{v}_{m-1}\coloneqq v_{m-1},\widetilde{v}_{m}\coloneqq
1^{n}\\}.$

For any $t\in[m-1]$, if $v_{t}(n)=0$ then $v_{t}\leq v_{m}$, which is not
possible due to Lemma 4.10. Thus, $v_{t}(n)\geq 1$ for all $t\in[m-1]$.
Clearly $\widetilde{\mathcal{V}}$ satisfies $V^{*}_{1}(k,s)$. Also
$|\widetilde{v}_{m}|=n\leq\left\lfloor\frac{k-1}{s}\right\rfloor$, that is,
$s|\widetilde{v}_{m}|\leq k-1$. So $\widetilde{\mathcal{V}}$ satisfies
$V^{*}_{2}(k,s)$. Now consider any $I\subseteq[m],\,I\neq\emptyset$. If
$m\not\in I$, then the $V^{*}_{3}(k,s)$ condition is obvious. If $m\in I$,
then we have

$\sum_{t\in
I}(k-s|\widetilde{v}_{t}|)+s|\widetilde{v}_{I}|=\sum_{\begin{subarray}{c}t\in
I\\\ t\neq m\end{subarray}}(k-s|v_{t}|)+(k-s|v_{m}|-s)+(s|v_{I}|+s)=\sum_{t\in
I}(k-s|v_{t}|)+s|v_{I}|\leq k.$

So $\widetilde{\mathcal{V}}$ satisfies $V^{*}_{3}(k,s)$. Thus,
$\widetilde{\mathcal{V}}$ satisfies $V^{*}(k,s)$, and therefore, by the
inductive hypothesis, $P(k,s,\widetilde{\mathcal{V}})$ is linearly independent
over $\mathbb{F}(Y_{1},\ldots,Y_{n})$. Note that

$|P(k,s,\widetilde{\mathcal{V}})|=\sum_{t\in[m]}(k-s|\widetilde{v}_{t}|)=\sum_{t\in[m-1]}(k-s|v_{t}|)+(k-s|v_{m}|-s)=|P(k,s,\mathcal{V})|-s=d-s.$

Also,

$P(k,s,\mathcal{V})=\bigg{(}\bigsqcup_{t\in[m-1]}P(k,s,v_{t})\bigg{)}\sqcup
P(k,s,v_{m}),\quad\text{and}\quad
P(k,s,\widetilde{\mathcal{V}})=\bigg{(}\bigsqcup_{t\in[m-1]}P(k,s,v_{t})\bigg{)}\sqcup
P(k,s,\widetilde{v}_{m}).$

Let $Q(X,Y_{1},\ldots,Y_{n-1})=\prod_{i=1}^{n-1}E(X,Y_{i})$. Then by
definition, we have

$\displaystyle P(k,s,v_{m})$ $\displaystyle=\\{Q\cdot
X^{e}:e\in[0,k-1-s(n-1)]\\},$ $\displaystyle
P(k,s,\widetilde{v}_{m})\sqcup\\{Q,Q\cdot X,\ldots,Q\cdot X^{s-1}\\}$
$\displaystyle=\\{Q\cdot E(X,Y_{n})X^{e}:e\in[0,k-1-sn]\\}$
$\displaystyle\qquad\sqcup\\{Q,Q\cdot X,\ldots,Q\cdot X^{s-1}\\}.$

It is easy to check that

$\displaystyle\text{span}(P(k,s,v_{m}))$
$\displaystyle=\text{span}(P(k,s,\widetilde{v}_{m})\sqcup\\{Q,Q\cdot
X,\ldots,Q\cdot X^{s-1}\\})$
$\displaystyle=\\{f(X)\in\mathbb{F}[X]:\deg(f)\leq k-1,\text{ and }Q\text{
divides }f(X)\\}.$

Now enumerate $P(k,s,\widetilde{\mathcal{V}})=\\{P_{1},\ldots,P_{d-s}\\}$. For
$w_{r}(Y_{1},\ldots,Y_{n})\in\mathbb{F}[Y_{1},\ldots,Y_{n}],\,r\in[d-s]$, and
$\hat{w}_{j}(Y_{1},\ldots,Y_{n})\in\mathbb{F}[Y_{1},\ldots,Y_{n}],\,j\in[0,s-1]$,
consider the linear combination

$\sum_{j=0}^{s-1}\hat{w}_{j}\cdot Q\cdot X^{j}+\sum_{r=1}^{d-s}w_{u}\cdot
P_{u}=0.$

Since $\widetilde{v}_{t}(n)\geq 1$ for all $t\in[m]$, we note that
$E(X,Y_{n})$ divides $P_{u}$ for all $u\in[d-s]$. This implies

$\sum_{j=0}^{s-1}\hat{w}_{j}\cdot Q\cdot X^{j}\equiv 0\,\left(\text{mod
}E(X,Y_{n})\right).$

Since $Q$ is coprime to $E(X,Y_{n})$, and $X^{j}\not\equiv 0\,\left(\text{mod
}E(X,Y_{n})\right)$, the set $\\{Q,Q\cdot X,\ldots,Q\cdot X^{s-1}\\}$ is
linearly independent in
$\frac{\mathbb{F}(Y_{1},\ldots,Y_{n})[X]}{E(X,Y_{n})}$. So
$\hat{w}_{r}(Y_{1},\ldots,Y_{n})=0$ for all $r\in[0,s-1]$. This gives

$\sum_{u=1}^{d-s}w_{u}\cdot P_{u}=0\quad\implies\quad w_{u}=0\text{ for all
}u\in[d-s],$

since $P(k,s,\widetilde{\mathcal{V}})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$. So $P(k,s,\mathcal{V})$ is linearly
independent over $\mathbb{F}(Y_{1},\ldots,Y_{n})$, which is a contradiction.
Thus, $n-1=\left\lfloor\frac{k-1}{s}\right\rfloor$. ∎

####  4.5.4 Finishing the proof

By Lemma 4.13 and convention, we have $v_{m}=(1^{n-1},0)$. Further,
$|v_{m}|=n-1=\left\lfloor\frac{k-1}{s}\right\rfloor$ by Lemma 4.14. Now let
$\widetilde{\mathcal{V}}=\\{v_{1},\ldots,v_{m-1}\\}$. Then clearly,
$\widetilde{\mathcal{V}}$ satisfies $V^{*}(k,s)$. So by the inductive
hypothesis, $P(k,s,\widetilde{\mathcal{V}})$ is linearly independent over
$\mathbb{F}(Y_{1},\ldots,Y_{n})$. Further, we see that $P(k,s,v_{m})=\\{Q\cdot
X^{e}:e\in[0,k-1-s(n-1)]\\}$. Proceeding as in the proof of Lemma 4.14, we can
conclude that $P(k,s,\mathcal{V})$ is linearly independent, which is a
contradiction.

##  5 List decoding randomly punctured polynomial ideal codes

Inspired by the breakthroughs in [BGM23, GZ23, AGL23], we will prove that
duals of some randomly punctured polynomial ideal codes over $\mathbb{F}_{q}$,
with folding parameter $s$, achieve list decoding capacity with field size
$q=(sn)^{O(sn/\epsilon)}$ (Theorem 5.4). Our argument could be considered an
extension of that in [BGM23] to the folded setting. Combined with our duality
characterization in Theorem 3.4, this will prove that some randomly punctured
polynomial ideal codes over $\mathbb{F}_{q}$, with folding parameter $s$,
achieve list decoding capacity with field size $q=(sn)^{O(sn/\epsilon)}$
(Theorem 5.5). In Section 6, we will also discuss a reduction in the field
size, which is an extension of the arguments in [GZ23].

Consider a field $\mathbb{F}$. Since we are interested in folded codes, also
consider a folding parameter $s\geq 1$. An $s$-folded code
$C\subseteq(\mathbb{F}^{s})^{n}$ is said to be $(\rho,L)$-average radius list
decodable if there do not exist $w\in(\mathbb{F}^{s})^{n}$, and distinct
codewords $c^{(1)},\ldots,c^{(L+1)}\in C$ such that

$\frac{1}{L+1}\sum_{j=1}^{L+1}\Delta_{n}^{(s)}(w,c^{(j)})\leq\rho n.$

It is not hard to see that average radius list decodability implies list
decodability; indeed, this follows from the fact that the average is always at
most the maximum. Now, assuming $C$ is $\mathbb{F}$-linear, and has constant
rate $R=k/sn$, we say $C$ achieves list decoding capacity if for any
$\epsilon>0$, we can (combinatorially) list decode $C$ up to radius
$1-R-\epsilon$, with list size $O_{\epsilon}(1)$.

Our aim is to show that some randomly punctured primal and dual polynomial
ideal codes achieve the Singleton bound over large fields. We will first
consider the analogous statement for duals of generic polynomial ideal codes
over the generic field $\mathbb{F}(Y_{1},\ldots,Y_{n})$. Assume Condition 2.1
throughout.

######  Theorem 5.1.

Let $s,k,n$ be non-negative integers so that $s\,|\,(k-1)$ and $k\leq sn$. Let
$\mathbb{F}$ be a finite field of size at least $n$, and consider the generic
field $\mathbb{F}(Y_{1},\ldots,Y_{n})$. Let $E(X,Y)\in\mathbb{F}[X,Y]$ be a
bivariate polylinear completely $s$-bounded polynomial over $\mathbb{F}$. Let
$L$ be a non-negative integer.

Then $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)^{\perp}$ is a generic code of rate
$R:=1-\frac{k}{sn}$, that is
$\big{(}\frac{L}{L+1}\big{(}1-R\big{)},L\big{)}$-list decodable.

The statement for the generic polynomial ideal codes follows immediately.

######  Theorem 5.2.

Let $s,k,n$ be non-negative integers so that $s\,|\,(k+1)$ and $k\leq sn$. Let
$\mathbb{F}$ be a finite field of size at least $n$, and consider the generic
field $\mathbb{F}(Y_{1},\ldots,Y_{n})$. Let $E(X,Y)\in\mathbb{F}[X,Y]$ be a
bivariate polylinear completely $s$-bounded polynomial over $\mathbb{F}$. Let
$L$ be a non-negative integer.

Then $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$ is a generic code of rate
$R:=\frac{k}{sn}$, that is
$\big{(}\frac{L}{L+1}\big{(}1-R\big{)},L\big{)}$-list decodable.

###### Proof.

By Theorem 3.4, we know that
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};sn-k)^{\perp}=\mathbf{GPI}_{E}(U;Y_{1},\ldots,Y_{n};k)$
for some block invertible matrix $U$. Since $s\,|\,(k+1)$, we have
$s\,|\,(sn-k-1)$. Theorem 5.1 then implies that
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};sn-k)^{\perp}$ is
$\big{(}\frac{L}{L+1}(1-R),L\big{)}$-list decodable, that is,
$\mathbf{GPI}_{E}(U;Y_{1},\ldots,Y_{n};k)$ is
$\big{(}\frac{L}{L+1}(1-R),L\big{)}$-list decodable. Therefore,
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$ is
$\big{(}\frac{L}{L+1}(1-R),L\big{)}$-list decodable. ∎

The required statements, under random puncturing, are a consequence of the
following lemma on the behaviour of polylinear, completely $s$-bounded,
randomly projected functional moduli.

######  Lemma 5.3 (Coprimality under random projections).

Assume Condition 2.1, and let $E(X,Y)\in\big{(}\mathbb{F}[Y]\big{)}[X]$ be
polylinear, completely $s$-bounded. Then, for randomly chosen
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}$, the functional moduli
$E(X,\alpha_{1}),\ldots,E(X,\alpha_{n})$ are pairwise coprime with probability
$1-o(1)$.

###### Proof.

Consider the factorization $E(X,Y)=(X-\phi_{1}(Y))\cdots(X-\phi_{s}(Y))$,
where for each $j\in[s]$, we have $\deg(\phi_{j})\leq c(s)$. So, for every
$j\in[0,s-1]$, and each $z\in\mathbb{F}$, equation $\phi_{j}(y)=z$ has at most
$c(s)$ many distinct solutions $y\in\mathbb{F}$. So by Condition 2.1, the
subsets $\\{\phi_{1}(\alpha_{i}),\ldots,\phi_{s}(\alpha_{i})\\},\,i\in[n]$ are
well-defined and pairwise disjoint, with probability $1-o(1)$. The claim is
then immediate. ∎

The required statement, under random puncturing, for dual polynomial ideal
codes is the following.

######  Theorem 5.4.

Let $s,k,n$ be non-negative integers so that $s\,|\,(k-1)$ and $k\leq sn$. Let
$\mathbb{F}$ be a finite field of size at least $n$, let
$E(X,Y)\in\mathbb{F}[X,Y]$ be a polylinear completely $s$-bounded polynomial
over $\mathbb{F}$, and let $\alpha_{1},\ldots,\alpha_{n}$ be chosen
independently and uniformly at random from $\mathbb{F}$. Let $L$ be a non-
negative integer.

Then if $|\mathbb{F}|\geq\exp_{s,L}(n)$, then
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)^{\perp}$ is a code of rate
$R:=1-\frac{k}{sn}$, that is
$\big{(}\frac{L}{L+1}\big{(}1-R\big{)},L\big{)}$-list decodable with high
probability.

###### Proof.

We can choose an absolute constant $D>0$ large enough so that if
$q\geq(sn)^{Dsn(L+1)}$, by appealing to Lemma 5.3, we can conclude that the
randomly chosen points $\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}$ are
distinct, and the generator matrix $G_{E,k}(\alpha_{1},\ldots,\alpha_{n})$ of
the polynomial ideal code $\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ is
$s$-folded ZP-MDS with probability $1-o(1)$. Then the proof of Theorem 5.1
shows that the dual code
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)^{\perp}$ is
$\big{(}\frac{L}{L+1}\big{(}1-\frac{k}{sn}\big{)},L\big{)}$-average radius
list decodable with probability $1-o(1)$. ∎

The required statement, under random puncturing, for primal polynomial ideal
codes is the following.

######  Theorem 5.5 (Theorem 1.1 for exponential field size).

Let $s,k,n$ be non-negative integers so that $s\,|\,(k+1)$ and $k\leq sn$. Let
$\mathbb{F}$ be a finite field of size at least $n$, let
$E(X,Y)\in\mathbb{F}[X,Y]$ be a polylinear completely $s$-bounded polynomial
over $\mathbb{F}$, and let $\alpha_{1},\ldots,\alpha_{n}$ be chosen
independently and uniformly at random from $\mathbb{F}$. Let $L$ be a non-
negative integer.

Then if $|\mathbb{F}|\geq\exp_{s,L}(n)$, then
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ is a code of rate
$R:=\frac{k}{sn}$, that is
$\big{(}\frac{L}{L+1}\big{(}1-R\big{)},L\big{)}$-list decodable with high
probability.

###### Proof.

Follows from Theorem 5.2, via Lemma 5.3, in the same way as Theorem 5.4
follows from Theorem 5.1. ∎

###  5.1 Preparations for Theorem 5.1

The proof of Theorem 5.1 is similar to that in [BGM23], but extended to the
folded setting. Towards this, we will need a couple of results from [BGM23].
Recall the set operator _unfolding_ , which we defined as follows. For any
$A\subseteq[n]$, the $s$-unfolding of $A$ is defined by
$A\big{\uparrow}_{s}=A\times[0,s-1]$. We make the following observations.

######  Observation 5.6.

  1. (a)

$\big{|}A\big{\uparrow}_{s}\big{|}=s|A|$, for all $A\subseteq[n]$.

  2. (b)

$(A\cap B)\big{\uparrow}_{s}=A\big{\uparrow}_{s}\cap B\big{\uparrow}_{s}$, for
all $A,B\subseteq[n]$.

  3. (c)

$([n]\setminus A)\big{\uparrow}_{s}=([n]\times[0,s-1])\setminus
A\big{\uparrow}_{s}$, for all $A\subseteq[n]$.

###### Proof.

For (a), note that $|A\times[0,s-1]|=|A|\cdot|[0,s-1]|$.

For (b), note that $(A\cap
B)\times[0,s-1]=(A\times[0,s-1])\cap(B\times[0,s-1])$.

For (c), note that $([n]\setminus
A)\times[0,s-1]=([n]\times[0,s-1])\setminus(A\times[0,s-1])$. ∎

For a matrix $M=\begin{bmatrix}M_{i,j}\end{bmatrix}\in\mathbb{F}^{sn\times
k}$, and any $A\subseteq[n]$, we denote
$M_{A\big{\uparrow}_{s}}=\text{span}_{\mathbb{F}}\big{\\{}(M_{u,1},\ldots,M_{u,k}):u\in
A\big{\uparrow}_{s}\big{\\}}$. Also, for any
$A_{1},\ldots,A_{\ell}\subseteq[n]$, and $P\subseteq[\ell]$, denote
$\bigcap(A,P)=\bigcap_{t\in P}A_{t}$. We define an $sn\times k$ generic matrix
to be $W=\begin{bmatrix}W_{u,j}\end{bmatrix}_{sn\times
k}\in\mathbb{F}(W_{u,j}:u\in[n]\times[0,s-1],\,j\in[k])$, where the
$W_{u,j}$-s are indeterminates.

Firstly, we will consider _unfolded_ MDS zero patterns, that is, 1-folded MDS
zero patterns.

######  Lemma 5.7 ([BGM23, Lemma 2.8]).

Let $s\geq 1,\,k\in[sn],\,d\geq 0$. Let
$B_{1},\ldots,B_{\ell}\subseteq[n]\times[0,s-1]$ with $|B_{j}|\leq
k,\,j\in[\ell]$. The following are equivalent.

  1. (a)

There exist $\delta_{1},\ldots,\delta_{\ell}\geq 0$ such that
$\sum_{i=1}^{\ell}\delta_{i}=k-d$, and there exists an unfolded MDS zero
pattern for $sn\times k$ matrices, which contains $\delta_{t}$ copies of
$B_{t}$, for all $t\in[\ell]$, and $d$ copies of the empty set.

  2. (b)

There exist $\delta_{1},\ldots,\delta_{\ell}\geq 0$ such that
$\sum_{i=1}^{\ell}\delta_{i}=k-d$, and

$\bigg{|}\bigcap_{t\in I}B_{t}\bigg{|}\leq k-\sum_{t\in
I}\delta_{t},\quad\text{for all }I\subseteq[\ell],\,I\neq\emptyset.$

  3. (c)

For any partition $P_{1}\sqcup\cdots\sqcup P_{\nu}=[\ell]$, we have

$\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in P_{i}}B_{j}\bigg{|}\leq(\nu-1)k+d.$

Secondly, we will consider intersection subspaces of a generic matrix.

######  Theorem 5.8.

Consider an $sn\times k$ generic matrix $W$, and let
$B_{1},\ldots,B_{\ell}\subseteq[n]\times[0,s-1]$ with $|B_{j}|\leq
k,\,j\in[\ell]$. Then

$\dim(W_{B_{1}}\cap\cdots\cap
W_{B_{\ell}})=\max_{\begin{subarray}{c}P_{1}\sqcup\cdots\sqcup
P_{\nu}=[\ell]\\\
\text{partition}\end{subarray}}\bigg{(}\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in
P_{i}}B_{j}\bigg{|}-(\nu-1)k\bigg{)}.$

We will now obtain an analogue of a result by [BGM23], for dimensions of
intersection subspaces, in the folded setting. The proof is very similar to
that in [BGM23].

######  Lemma 5.9.

Let $M\in\mathbb{F}^{sn\times k}$ be an unfolded MDS matrix which is
$s$-folded ZP-MDS. Then for any $A_{1},\ldots,A_{\ell}\subseteq[n]$ with
$|A_{j}|\leq k/s,\,j\in[\ell]$, we have

$\dim\big{(}M_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
M_{A_{\ell}\big{\uparrow}_{s}}\big{)}=\max_{\begin{subarray}{c}P_{1}\sqcup\cdots\sqcup
P_{\nu}=[\ell]\\\
\text{partition}\end{subarray}}\bigg{(}s\cdot\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in
P_{i}}A_{j}\bigg{|}-(\nu-1)k\bigg{)}.$

###### Proof.

Since $M\in\mathbb{F}^{sn\times k}$ is unfolded MDS, we have

$\dim\big{(}\big{(}M_{A\big{\uparrow}_{s}}\big{)}^{\perp}\big{)}=k-\dim\big{(}M_{A\big{\uparrow}_{s}}\big{)}\geq
k-s|A|,\quad\text{for all }A\subseteq[n].$

For any $j\in[\ell]$, since $|A_{j}|\leq k/s$, we have
$|\prescript{\\#}{}{A}_{j}|\leq k$. So, for any partition
$P_{1}\sqcup\cdots\sqcup P_{\nu}=[\ell]$, we get

$\displaystyle\dim\big{(}M_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
M_{A_{\ell}\big{\uparrow}_{s}}\big{)}$
$\displaystyle\geq\dim\big{(}M_{\bigcap(A,P_{1})\big{\uparrow}_{s}}\cap\cdots\cap
M_{\bigcap(A,P_{\nu})\big{\uparrow}_{s}}\big{)}$ $\displaystyle\geq
k-\sum_{i=1}^{\nu}\dim\big{(}\big{(}M_{\bigcap(A,P_{i})\big{\uparrow}_{s}}\big{)}^{\perp}\big{)}$
$\displaystyle\geq
k-\sum_{i=1}^{\nu}\bigg{(}k-s\cdot\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in
P_{i}}A_{j}\bigg{|}\bigg{)}$
$\displaystyle=s\cdot\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in
P_{i}}A_{j}\bigg{|}-(\nu-1)k.$

This shows that the L.H.S. is at least the R.H.S.

Now let

$d=\max_{\begin{subarray}{c}P_{1}\sqcup\cdots\sqcup P_{\nu}=[\ell]\\\
\text{partition}\end{subarray}}\bigg{(}s\cdot\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in
P_{i}}A_{j}\bigg{|}-(\nu-1)k\bigg{)}.$

By Lemma 5.7, there exist $\delta_{1},\ldots,\delta_{\ell}\geq 0$ such that
$\sum_{i=1}^{\ell}\delta_{i}=k-d$, and

  * •

$\big{|}\bigcap_{t\in I}A_{t}\big{\uparrow}_{s}\big{|}\leq k-\sum_{t\in
I}\delta_{t}$, for all $I\subseteq[\ell],\,I\neq\emptyset$.

  * •

There exists an unfolded MDS zero pattern $\\{S_{1},\ldots,S_{k}\\}\subseteq
2^{[n]\times[0,s-1]}$ which contains exactly $\delta_{t}$ copies of
$\prescript{\\#}{}{A}_{t}$ for all $t\in[\ell]$, and $d$ copies of the empty
set.

Now consider the set system $\\{Z_{1},\ldots,Z_{k}\\}\subseteq 2^{[n]}$
defined by $S_{t}=Z_{t}\big{\uparrow}_{s},\,t\in[\ell]$. (This is well-defined
by the description of $S_{t}$ obtained.) Then it follows immediately that
$\\{Z_{1},\ldots,Z_{k}\\}$ is an $s$-folded MDS zero pattern, which contains
exactly $\delta_{t}$ copies of $A_{t}$ for all $t\in[\ell]$, and $d$ copies of
the empty set. Therefore, since $M$ is $s$-folded ZP-MDS, we conclude that $M$
attains $\\{Z_{1},\ldots,Z_{k}\\}$.

Let $U\in\mathbb{F}^{k\times k}$ be invertible such that $U\cdot M$ contains
$\\{Z_{1},\ldots,Z_{k}\\}$. Without loss of generality, suppose
$Z_{k-d+1}=\cdots=Z_{k}=\emptyset$. Now consider any
$v\in(UM)_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap(UM)_{A_{\ell}\big{\uparrow}_{s}}$.
Since every $Z_{j},\,j\leq k-d$ is equal to some $A_{t},\,t\in[\ell]$, this
means $v_{j}=0$ for all $j\leq k-d$. Thus,
$v\in\\{0\\}^{k-d}\times\mathbb{F}^{d}$. Thus, we get

$\dim\big{(}M_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
M_{A_{\ell}\big{\uparrow}_{s}}\big{)}=\dim\big{(}(UM)_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap(UM)_{A_{\ell}\big{\uparrow}_{s}}\big{)}\leq
d.$

This shows that the L.H.S. is at most the R.H.S., and completes the proof. ∎

###  5.2 Proof of Theorem 5.1

We are now ready to prove Theorem 5.1.

###### Proof of Theorem 5.1.

Consider any $L\geq 1$, and suppose
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)^{\perp}$ is not
$\big{(}\frac{L}{L+1}\big{(}1-R\big{)},L\big{)}$-average radius list
decodable, where $R=1-\frac{k}{sn}$. So there exist
$w\in(\mathbb{F}^{s})^{n}$, and distinct codewords
$c^{(1)},\ldots,c^{(L+1)}\in\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)^{\perp}$
such that

$\displaystyle\sum_{j=1}^{L+1}\Delta_{n}^{(s)}(w,c^{(j)})\leq
L\bigg{(}n-\frac{sn-k}{s}\bigg{)}.$ (5)

For $j\in[L+1]$, let $A_{j}=\text{supp}(w-c^{(j)})=\big{\\{}i\in[n]:w_{i}\neq
c^{(j)}_{i}\big{\\}}$; this means $|A_{j}|=\Delta_{n}^{(s)}(w,c^{(j)})$. Note
that the distance of $\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)^{\perp}$ is
$1-\frac{1}{n}\left\lfloor\frac{sn-k-1}{s}\right\rfloor$. We immediately
observe the following.

  * •

If $A_{j_{0}}=\emptyset$ for some $j_{0}\in[L+1]$, then it means
$w=c^{(j_{0})}$, and therefore, $\Delta_{n}^{(s)}(w,c^{(j)})\geq
n-\left\lfloor\frac{sn-k-1}{s}\right\rfloor>n-\frac{sn-k}{s}$ for all
$j\in[L+1],\,j\neq j_{0}$, which violates (5).

  * •

If $|A_{j}|>n-\frac{sn-k}{s}$ for all $j\in[L+1]$, then this violates (5).

  * •

If $|A_{j_{0}}|>n-\frac{sn-k}{s}$ for some $j_{0}\in[L+1]$, then

$\sum_{j\neq
j_{0}}\Delta_{n}^{(s)}(w,c^{(j)})=\sum_{j=1}^{L+1}\Delta_{n}^{(s)}(w,c^{(j)})-\Delta_{n}^{(s)}(w,c^{(j_{0})})\leq(L-1)\bigg{(}n-\frac{sn-k}{s}\bigg{)},$

and therefore, we may work with the smaller set of codewords
$\\{c^{(j)}:j\in[L+1],\,j\neq j_{0}\\}$.

So, without loss of generality, we assume $1\leq|A_{j}|\leq n-\frac{sn-k}{s}$
for all $j\in[L+1]$.

By Theorem 3.4, and Corollary 4.4, the generator matrix $G\coloneqq
G_{E,k}(Y_{[n]})\in\mathbb{F}^{sn\times k}$ is unfolded MDS and $s$-folded ZP-
MDS. Let

$d=\max_{\begin{subarray}{c}P_{1}\sqcup\cdots\sqcup P_{\nu}=[L+1]\\\
\text{partition}\end{subarray}}\bigg{(}s\cdot\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in
P_{i}}A_{j}\bigg{|}-(\nu-1)k\bigg{)}.$

So by Theorem 5.8 and Lemma 5.9, we get

$\displaystyle\dim\big{(}H_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
H_{A_{L+1}\big{\uparrow}_{s}}\big{)}=\dim\big{(}W_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
W_{A_{L+1}\big{\uparrow}_{s}}\big{)}=d,$ (6)

where $W$ is a $sn\times k$ generic matrix.

Firstly, we have $w\not\in\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)^{\perp}$, and
so
$G^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(w-c^{(1)})\neq
0$. Also,
$G^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(w-c^{(1)})\in
G_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap G_{A_{L+1}\big{\uparrow}_{s}}$. So
$\dim\big{(}W_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
W_{A_{L+1}\big{\uparrow}_{s}}\big{)}\geq 1$. By Theorem 5.8, fix a partition
$P_{1}\sqcup\cdots\sqcup P_{\nu}=[L+1]$ such that

$\dim\big{(}W_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
W_{A_{L+1}\big{\uparrow}_{s}}\big{)}=s\cdot\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in
P_{i}}A_{j}\bigg{|}-(\nu-1)k=d.$

If $\nu=L+1$, which implies
$\\{P_{1},\ldots,P_{\nu}\\}=\\{\\{1\\},\ldots,\\{L+1\\}\\}$, then we get

$\dim\big{(}W_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
W_{A_{L+1}\big{\uparrow}_{s}}\big{)}=s\cdot\sum_{j=1}^{L+1}|A_{j}|-Lk\leq 0,$

which is a contradiction. So $\nu\leq L$.

Define vector spaces

$\displaystyle V$
$\displaystyle=\\{(u_{1},\ldots,u_{L+1}):G^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}u_{1}=\cdots=G^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}u_{L+1},\,\text{supp}(u_{j})\subseteq
A_{j}\text{ for all }j\in[L+1]\\},$ $\displaystyle V^{\prime}$
$\displaystyle=\\{(u_{1},\ldots,u_{L+1})\in V:u_{j}=u_{j^{\prime}}\text{ if
}j,j^{\prime}\in P_{i}\\}.$

Then $\dim(V)=\dim\big{(}G_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
G_{A_{L+1}\big{\uparrow}_{s}}\big{)}$, and
$\dim(V^{\prime})=\dim\big{(}G_{\bigcap(A,P_{1})\big{\uparrow}_{s}}\cap\cdots\cap
G_{\bigcap(A,P_{\nu})\big{\uparrow}_{s}}\big{)}$. Further, since
$c^{(1)},\ldots,c^{(L+1)}\in\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)^{\perp}$ are
distinct, and $\nu\leq L$, we get $(w-c^{(1)},\ldots,w-c^{(L+1)})\in
V\setminus V^{\prime}$. So $\dim(V)>\dim(V^{\prime})$. Since generic matrices
minimize the dimensions of intersection subspaces, we thus get

$\displaystyle\dim\big{(}G_{A_{1}\big{\uparrow}_{s}}\cap\cdots\cap
G_{A_{L+1}\big{\uparrow}_{s}}\big{)}$
$\displaystyle>\dim\big{(}G_{\bigcap(A,P_{1})\big{\uparrow}_{s}}\cap\cdots\cap
G_{\bigcap(A,P_{\nu})\big{\uparrow}_{s}}\big{)}$ (7)
$\displaystyle\geq\dim\big{(}W_{\bigcap(A,P_{1})\big{\uparrow}_{s}}\cap\cdots\cap
W_{\bigcap(A,P_{\nu})\big{\uparrow}_{s}}\big{)}$ (8) $\displaystyle\geq
s\cdot\sum_{i=1}^{\nu}\bigg{|}\bigcap_{j\in P_{i}}A_{j}\bigg{|}-(\nu-1)k$ by
Theorem 5.8

which contradicts (6). This completes the proof. ∎

##  6 Reducing alphabet size

In this section, we will improve the bound on the alphabet size from
exponential to polynomial, in fact, quadratic in the block length. Assume
Condition 2.1 throughout. Let us first state our result.

######  Theorem 6.1 (Theorem 1.1 for polynomial field size).

Let $s,k,n$ be non-negative integers so that $s\,|\,(k+1)$ and $k\leq sn$. Let
$\mathbb{F}_{q}$ be a finite field of size at least $n$, let
$E(X,Y)\in\mathbb{F}_{q}[X,Y]$ be a polylinear completely $s$-bounded
polynomial over $\mathbb{F}_{q}$, and let $\alpha_{1},\ldots,\alpha_{n}$ be
chosen independently and uniformly at random from $\mathbb{F}_{q}$. Let $L$ be
a non-negative integer, and let $\epsilon>0$.

If $|\mathbb{F}_{q}|\geq\Theta_{\epsilon,s,L}(n^{2})$, then
$\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ is
$\big{(}\frac{L}{L+1}(1-R-\epsilon),L\big{)}$-list decodable with high
probability.

###  6.1 Reduced intersection matrix (RIM)

To prove the above theorems we shall consider the notion of _reduced
intersection matrix_ , introduced in [GZ23]. The reduced intersection matrix
was introduced in [GZ23], as an improved version of _intersection matrix_
introduced by Shangguan and Tamo [ST20]. We will work with an extension of
these, specifically for generic polynomial ideal codes.

Fix the function field $\mathbb{F}_{q}(Y_{1},\ldots,Y_{n})$, and let $s\geq
1,\,k\in[sn]$. Also, fix any distinct
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}$, and consider the polynomial
ideal code $\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$. Let

$w=\begin{bmatrix}w_{1}\\\ \vdots\\\
w_{n}\end{bmatrix}=\begin{bmatrix}[w_{1,t}]_{t=0}^{s-1}\\\ \vdots\\\
[w_{n,t}]_{t=0}^{s-1}\end{bmatrix}\in\mathbb{F}_{q}^{sn\times
1},\quad\text{and}\quad[f_{1}],\ldots,[f_{T}]\in\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k).$

Note that $[f_{j}]=H_{E,k}(\alpha_{[n]})\cdot f_{j}$ for all $j\in[T]$. The
key idea behind a reduced intersection matrix is to record the _incidences_
between the codewords in $\mathbf{PI}_{E}(\alpha_{1},\ldots,\alpha_{n};k)$ as
_generic incidences_ between corresponding generic codewords in
$\mathbf{PI}_{E}(Y_{1},\ldots,Y_{n};k)$. More precisely, for some $i\in[n]$
and $j,j^{\prime}\in[T],\,j\neq j^{\prime}$, if there is an _incidence_
$[f_{j}]_{i}=w_{i}=[f_{j^{\prime}}]_{i}$, that is,
$G_{E,k}(\alpha_{i})\cdot(f_{j}-f_{j^{\prime}})=0$, then we record it as a
_generic incidence_ $G_{E,k}(Y_{i})\cdot(f_{j}-f_{j^{\prime}})=0$.

Fix any $B\subseteq[n],\,J\subseteq[T]$. For $i\in[n],\,j\in[T]$, define
$I_{j}=\\{i\in[n]\setminus B:[f_{j}]_{i}=w_{i}\\}$ and $J_{i}=\\{j\in
J:[f_{j}]_{i}=w_{i}\\}$. Now let $T_{J}=\max(J)\leq T$, and denote

$\displaystyle j_{i}$ $\displaystyle=\min(J_{i}),$ $\displaystyle
J^{\prime}_{i}$ $\displaystyle=J_{i}\setminus\\{j_{i}\\},$
$\displaystyle\widehat{J}_{i}$
$\displaystyle=J_{i}\setminus\\{j_{i},T_{J}\\}.$

We assume that each $|J_{i}|\geq 2$ (otherwise, we include $i\in B$). Now
consider any $i\in[n]$. For every $j\in\widehat{J}_{i}$, define a
$s\times(|J|-1)k$ matrix

$R_{i,j}(Y_{i})=\setcounter{MaxMatrixCols}{11}\begin{bmatrix}0^{s\times
k}&\cdots&0^{s\times k}&\underset{j_{i}\text{-th
block}}{G_{E,k}(Y_{i})}&0^{s\times k}&\cdots&0^{s\times
k}&\underset{j\text{-th block}}{-G_{E,k}(Y_{i})}&0^{s\times
k}&\cdots&0^{s\times k}\end{bmatrix}.$

Further, if $T_{J}\in J^{\prime}_{i}$, then define an $s\times(|J|-1)k$ matrix

$R_{i,T_{J}}(Y_{i})=\setcounter{MaxMatrixCols}{11}\begin{bmatrix}0^{s\times
k}&\cdots&0^{s\times k}&\underset{j_{i}\text{-th
block}}{G_{E,k}(Y_{i})}&0^{s\times k}&\cdots&0^{s\times
k}&\phantom{iiii}0^{s\times k}\phantom{iiii}&0^{s\times k}&\cdots&0^{s\times
k}\end{bmatrix}.$

Now let

$R_{i}(Y_{i})=\begin{bmatrix}R_{i,j}(Y_{i})\end{bmatrix}_{j\in
J^{\prime}_{i}}\in\mathbb{F}(Y_{i})^{|J^{\prime}_{i}|s\times(|J|-1)k},$

and denote $I_{J}=(I_{j}:j\in J)$. The reduced intersection matrix (RIM) is
then defined by

$\mathsf{RIM}_{I_{J}}^{B}(Y_{[n]\setminus
B})=\begin{bmatrix}R_{i}(Y_{i})\end{bmatrix}_{i\in[n]\setminus
B}\in\mathbb{F}(Y_{[n]\setminus B})^{\big{(}\sum_{i\in[n]\setminus
B}|J^{\prime}_{i}|s\big{)}\times(|J|-1)k}.$

We also denote
$\mathsf{RIM}_{I_{J}}(Y_{[n]})=\mathsf{RIM}_{I_{J}}^{\emptyset}(Y_{[n]})$.

###  6.2 Full-rankness of RIM

Let us begin by mentioning two results about dimensions of intersections of