Polynomials, Divided Differences, and Codes

In this work, we are specifically interested in the list decoding problem [16, 69], where the aim is to output a list of close codewords for any given received word efficiently. The main parameter of interest is the list decoding radius, which represents the fraction of disagreements that we can decode from, and we would like it to be as large as possible.

To begin with, consider the easier setting where we fix the list decoding radius to be half the minimum distance of the code, which is precisely the setting of the unique decoding problem – in this case, there could only be at most one codeword this close to any given received word, and the aim is to efficiently find it if it exists. This problem has now been solved completely for RS codes [56, 49, 67], for univariate multiplicity codes [53], for RM codes in a special case [40, 5], and quite recently for RM codes in general [41] and for multivariate multiplicity codes [8]. What is noteworthy is that all of these algorithms are insensitive to the field characteristic. We now move on to consider larger list decoding radius.

In the last decade of the 20th century, two classic works [65, 27] showed that all RS codes can be list decoded up to the Johnson bound (which is relative radius $1-\sqrt{R}$, where $R$ is the rate of the code), and also laid an algebraic algorithmic framework that has since been exploited over and over again for several other polynomial codes. Further, we do not know of explicit RS codes that can be list decoded beyond the Johnson bound, but we do know of explicit RS codes that are not list decodable significantly beyond the Johnson bound [7]. Due to recent breakthroughs [11, 26, 2], we now know that random RS codes are list decodable up to (information theoretic) capacity (that is, relative radius $1-R-ϵ$ for arbitrarily small but fixed $ϵ>0$, which represents getting approximately close to the information theoretic limit of list decoding), but we neither know of an explicit construction nor know of an algorithm to achieve this.

It is in this context of list decoding up to the information theoretic capacity that a folding trick has been enlightening. The works of [28, 29] showed that folded Reed-Solomon (FRS) codes (where the bits of an RS codeword are bunched into blocks of large constant size), and univariate multiplicity codes [43] (wherein the codewords are evaluations of polynomials and their derivatives up to a large constant multiplicity) can be algorithmically list decoded up to capacity! Further improvements to the parameters have been achieved in [44, 61, 63, 12] in different settings.

Moving on to multivariate polynomial codes, while the list decoding algorithms of [65, 27] generalize easily to RM codes, the decoding radius now worsens as a function of the number of variables, and attaining Johnson bound is no longer possible with these algorithms. While we know of a Johnson bound attaining algorithm [55] for RM codes when the finite grid is the full vector space ${𝔽}_q^m$ over the base field ${𝔽}_q$, designing a more general algorithm for arbitrary finite grids is still open!

As it turns out, the folding trick helps in the multivariate setting too. The multivariate multiplicity codes [45], which are the obviously defined multivariate analogues of univariate multiplicity codes, were shown to be list decodable up to distance (that is, up to radius $\delta -ϵ$, where $\delta$ is the minimum distance of the code) by [43] when the set of evaluation points is the full vector space ${𝔽}_q^m$. However, just as in the case of RM codes, an analogous result for arbitrary finite grids evaded us for quite some time. Very recently, [9] finally bolstered the algebraic algorithmic framework with some simple additional ingredients and managed to design an algorithm for list decoding multivariate multiplicity codes over arbitrary finite grids up to distance.

Finally, yet another crucial component that could influence the performance of the code (specifically a polynomial code) is the most fundamental underlying algebraic object – the base field over which the polynomials are considered, which is always a finite field in our discussion.

Unlike the unique decoding setting that we mentioned earlier, we do observe sensitivity to the field characteristic in the setting of the list decoding problem. Let us fix the notation that ${𝔽}_q$ denotes the base field, and $p$ denotes the characteristic of ${𝔽}_q$. On one hand, we know that when $q$ is a large power of $p$, there are RS codes that cannot achieve anywhere close to list decoding capacity [7] since we can show instances of received words having superpolynomial sized output lists. On the other hand, upon large constant folding, the univariate multiplicity codes achieve capacity when $p$ is larger than the degree parameter [29, 43], or smaller but linear in the degree [44], and the FRS codes achieve list decoding capacity [28, 29] insensitive to $p$. Thus, the list decodability of the FRS code is insensitive to the field characteristic, whereas the list decodability of the multiplicity code is sensitive to the field characteristic. Indeed, in the case when $q$ is a large power of $p$, the large output lists shown by [7] for RS codes can be used to construct large output lists for multiplicity codes, and so the list decodability is provably poor.

Things get even more interesting in the multivariate setting, since the multivariate multiplicity codes achieve distance when $p$ is larger than the degree parameter [55, 9], but we do not know of a field characteristic insensitive construction of a multivariate polynomial code that algorithmically achieves distance. Furthermore, we also do not know of an appropriate multivariate analogue of the field characteristic insensitive univariate FRS code. In this work, we answer both questions with a single code construction, along with a list decoding algorithm. In particular, our code subsumes the list decoding performance of the field characteristic sensitive multivariate multiplicity code [9], and also provides a natural folded Reed-Muller code construction. The motivation for our construction comes from an extremely simple yet foundational observation within the univariate world itself – the FRS code is also a multiplicity code!

Fix a field ${𝔽}_q$. Consider distinct nonzero points $a_1,\mathrm{\dots },a_n\in {𝔽}_q$. Let $\gamma \in {𝔽}_q^{\times }$ be a multiplicative generator, and suppose $s\ge 1$ such that the points ${\gamma }^j{a}_i,j\in [0,s-1],i\in [n]$ are all distinct. For $k\in [sn]$, the degree-$k$ Folded Reed-Solomon (FRS) code is defined by

Here, the distance function is the Hamming distance on alphabet ${𝔽}_q^s$, that is, the Hamming weight ²²2We are only concerned with codes that are linear over the base field ${𝔽}_q$, and so the Hamming distance between two codewords $c_1,c_2$ is always equal to the Hamming weight of the codeword $c_1-c_2$. of a codeword ${[f]}_{\mathrm{FRS}}$ is the number of $i\in [n]$ such that the block
is a nonzero vector in ${𝔽}_q^s$.

On the other hand, simply assuming $a_1,\mathrm{\dots },a_n\in {𝔽}_q$ are distinct and nothing more about these points, for $k\in [sn]$, the degree-$k$ (univariate) multiplicity code is defined by

Here $f^{(j)}(X):=\frac{{\mathrm{d}}^{j}f(X)}{\mathrm{d}{X}^j}$ for all $j\in [0,s-1]$. ³³3Typically, since we are working over finite fields, there will also be a $j!$ scaling factor multiplied with the derivative, to prevent some pathologies arising in finite fields about higher multiplicity vanishing at a point. With this scaling factor, the derivative is usually called the Hasse derivative. We do not consider this, and implicitly assume that the characteristic is large enough so that these pathologies do not arise. Indeed, this is precisely the setting where the multiplicity codes have good list decodability. Once again, the Hamming weight of a codeword ${[f]}_{\mathrm{Mult}}$ is the number of $i\in [n]$ such that the block is a nonzero vector in ${𝔽}_q^s$.

Let us begin by looking at an algebraic feature that is intrinsic to multiplicity codes. Consider any $f(X)\in {𝔽}_q[X]$ with . For any $a\in {𝔽}_q$, we get the standard Taylor expansion

provided $p:=\text{char}({𝔽}_q)\ge k$. Is there an analogous Taylor expansion in the context of the FRS code? As it turns out, there is such an expansion, and it is even simpler – it is the expansion in terms of the Newton forward differences. Precisely, we have

where

Notably, since $\gamma \in {𝔽}_q^{\times }$ is a multiplicative generator, we always have $\text{ord}(\gamma )=q-1\ge k$, and therefore, this expansion is valid unconditional on $p$.

In the first decade of the 20th century, Jackson [31, 32, 33] (also see [35, 34]) had defined the following specific divided difference operator on the polynomial ring,

In terms of this operator, the above expansion takes the form

where ${[t]}_{\gamma }:=\frac{{\gamma }^t-1}{\gamma -1}=1+\gamma +{\gamma }^2+\mathrm{\cdots }+{\gamma }^{t-1}$, and ${[t]}_{\gamma }!:={[t]}_{\gamma }{[t-1]}_{\gamma }\mathrm{\cdots }{[1]}_{\gamma }$. Returning to the code ${\mathrm{FRS}}_s(a_1,\mathrm{\dots },a_n;k)$, it is then immediate by the definition of $D_{\gamma }$ that there are invertible lower triangular matrices $U(a_i)\in {𝔽}_q^{s\times s},i\in [n]$ such that for any codeword ${[f]}_{\mathrm{FRS}}$, we have

In other words, after a specific change of basis (see, for instance, [42, 4] for a proof), the FRS code can be interpreted as a multiplicity code with respect to the derivative-like operator ${𝖣}_{\gamma }$.

Note that we have list decoding algorithms for FRS codes [28, 29], with the first one being algebraic and the second one being linear algebraic. If we are given the ${𝖣}_{\gamma }$-multiplicity encoding, we may just change the basis to the usual FRS encoding and run one of these two FRS decoders. However, what is really encouraging is that we can straightforwardly adapt the linear algebraic multiplicity decoder [29] to our ${𝖣}_{\gamma }$-multiplicity encoding, and the analysis will have a strong resemblance with that in the case of the classical derivatives. In this work, our main contribution is a construction that pushes this resemblance to the multivariate setting.

Our main algorithm will, in fact, work in the more general paradigm of list recovery, as was the case with the previous algorithms mentioned here.

Our extension of $𝚀$-derivatives from the univariate to multivariate setting is natural, and mimicks the extension of the classical derivatives. Assume indeterminates $𝕏=(X_1,\mathrm{\dots },X_m)$, and for any $f(𝕏)\in 𝕂[𝕏]$ and $\alpha \in {\mathbb{N}}^m$, we define the $\alpha$-th $𝚀$-derivative as the iterated operator

where ${𝖣}_{𝚀,X_i}$ denotes the univariate $𝚀$-derivative in the variable $X_i$. It is easy to see that the operator ${𝖣}_{𝚀}^{\alpha }$ is well-defined and invariant under the order of iterations, just as in the case of the classical partial derivatives.

Now consider indeterminates $𝕐=(Y_1,\mathrm{\dots },Y_m)$. For any $t\ge 0$, denote ${(X_i-Y_i)}_{𝚀}^{(t)}:=(X_i-Y_i)(X_i-𝚀Y_i)\mathrm{\cdots }(X_i-{𝚀}^{t-1}{Y}_i)$, and further, for any $\alpha \in {\mathbb{N}}^m$, denote ${(𝕏-𝕐)}_{𝚀}^{(\alpha )}:={\prod }_{i=1}^m{(X_i-Y_i)}_{𝚀}^{({\alpha }_i)}$. Also denote ${[\alpha ]}_{𝚀}!:={[{\alpha }_1]}_{𝚀}!\mathrm{\cdots }{[{\alpha }_m]}_{𝚀}!$, and ${𝚀}^{\alpha }𝕏=({𝚀}^{{\alpha }_1}{X}_1,\mathrm{\dots },{𝚀}^{{\alpha }_m}{X}_m)$. Then for any $s\ge 1$ and $a\in {({𝔽}_q^{\times })}^m$, there exists (see Proposition 9) an invertible matrix $U(a)\in {𝕂}^{\left(\genfrac{}{}{0pt}{}{m+s-1}{s-1}\right)\times \left(\genfrac{}{}{0pt}{}{m+s-1}{s-1}\right)}$ such that

Fix any $s\ge 1$, and consider any nonempty $A\subseteq {𝔽}_q^{\times }$. For any $k\in [s|A|]$, we define the $m$-variate multiplicity-$s$ degree-$k$ $𝚀$-multiplicity code by

Note that the distance function is now the Hamming distance on the alphabet ${𝕂}^{\left(\genfrac{}{}{0pt}{}{m+s-1}{s-1}\right)}$. Further, by the change of basis that we just saw above, we can define a natural multivariate analogue of the univariate FRS codes. For any $k\in [s|A|]$, we define the $s$-folded degree $k$ folded Reed-Muller (FRM) code by

So by (1), we clearly have the change of basis

The rate and distance of our code constructions can be given as follows, which will be immediate from Corollary 11 and Theorem 13.

Our main result is that over any field ${𝔽}_q$ with sufficiently large $q$, and for sufficiently large constant multiplicity $s$, any constant rate multivariate $𝚀$-multiplicity code $𝚀-{\text{Mult}}_{m,s}(A;k)$, can be efficiently list decoded up to distance.

Our list decoding algorithm is conceptually simpler than that by [9] for the classical multivariate multiplicity codes. Their algorithm in the classical setting entailed recovering the close enough polynomial messages one homogeneous component at a time, while using the classical Euler’s formula for homogeneous polynomials (that relates a homogeneous polynomial to its first order derivatives) ⁵⁵5Euler’s formula states that for a homogeneous degree-$d$ polynomial $f(𝕏)$ over a field of characteristic greater than $d$, we have ${\sum }_{i=1}^m{X}_i\cdot \frac{\partial f(𝕏)}{\partial X_i}=d\cdot f(𝕏)$. to fully recover a homogeneous component (or a partial derivative of it) from its further first order partial derivatives. This formula, as well as the Taylor expansion for classical derivatives employed within the recovery step, both require the field characteristic to be large. In our $𝚀$-setting, firstly there is no Euler’s formula involving $𝚀$-derivatives, and interestingly we don’t need one! Secondly, the Taylor expansion for $𝚀$-derivatives is clearly field characteristic insensitive. These are the only two places in the analysis where conceptually, the field characteristic was relevant in the classical setting, and is now irrelevant in the $𝚀$-setting. Further, the short and clean analysis that we obtain encourages us to believe that this construction is the correct way to obtain a folded version of the RM code.

Let us give a quick outline of our algorithm. We make use of a clean gluing trick from [9] ⁶⁶6As mentioned in [9], this gluing trick seems to have first appeared in the construction of a hitting set generator in [25]. and then proceed to perform a simpler analysis that is extremely close to the univariate analysis of [29]. The informal takeaway of what we show is that

Suppose we are given the code $𝚀-{\text{Mult}}_{m,s}(A;k)$ as in the statement of Theorem 2. Consider any received word

Consider two fresh sets of indeterminates and $𝐙=(Z_1,\mathrm{\dots },Z_m)$. For a suitably chosen parameter $r\le s$, we will find a nonzero interpolating polynomial with coefficients in $𝕂[𝐙]$, having the form

such that the following hold.

1. (Z1)

   The polynomials $\tilde{P}(𝕏),P_0(𝕏),\mathrm{\dots },P_{r-1}(𝕏)$ must have suitably chosen $𝕏$-degree bounds. We will also simultaneously ensure a good $𝐙$-degree bound on the coefficients of these polynomials by performing Gaussian elimination over $𝕂[𝐙]$, as given in [38] or [9, Lemma 3].

2. (Z2)

   For any $f(𝕏)\in 𝕂[𝕏]$, define a projection

   $$P^{[f]}(𝕏):=\tilde{P}(𝕏)+\sum _{j=0}^{r-1}\left(\sum _{|\gamma |=j}{𝖣}_{𝚀}^{\gamma }f(𝕏){𝐙}^{\gamma }\right).$$

   Further, for every , define a $𝕂(𝐙)$-linear operator ${\mathrm{\Delta }}^{(\alpha )}$ (on an appropriate subspace of $𝕂(𝐙)[𝕏,𝕐]$) that satisfies the condition ${({\mathrm{\Delta }}^{(\alpha )}(P))}^{[f]}(𝕏)={𝖣}_{𝚀}^{\alpha }{P}^{[f]}(𝕏)$. The polynomial $P(𝕏,𝕐,𝐙)$ must now satisfy the vanishing conditions

Note that the vanishing conditions in (Z2) define a linear system on the coefficients of $P(𝕏,𝕐,𝐙)$, and we obtain the interpolating polynomial as a nontrivial solution of this linear system, by having large enough degree bounds as in (Z1). So for any close enough polynomial $f(𝕏)$ (that is, having a large number of agreements with $w$), the conditions in (Z2) will imply that $P^{[f]}(𝕏)$ vanishes at the agreement points with multiplicity at least $s-r$ (in the sense of multivariate $𝚀$-derivatives, which we will define later), and this will imply that $P^{[f]}(𝕏)=0$ by a suitable version of Polynomial Identity Lemma for multivariate $𝚀$-derivatives. We can then solve this equation to recover $f(𝕏)$. Importantly, the list decoding radius is dependent on the choice of $r$. We can achieve list decoding up to distance, that is, the claim of Theorem 2 by choosing $s=O(1/{ϵ}^{2m})$ and $r=O(1/{ϵ}^m)$. In fact, as in the analyses of [29, 9], we will show that the collection of all close enough polynomials is contained in a $𝕂$-affine subspace having dimension at most $\left(\genfrac{}{}{0pt}{}{m+r-2}{r-2}\right)$.

This is a fairly simple strategy, very much within the algebraic algorithmic framework started employed in previous list decoding algorithms [65, 27, 28, 29, 43, 9]. Further, employing the gluing trick with the additional $𝐙$-variables as in [9] allows us to formulate what we believe is the correct way to extend the linear algebraic decoding framework from the univariate to the multivariate setting, and our extension turns out to be simpler than the analysis in [9].

There is a subtlety in the recovery step in our multivariate setting vis-à-vis the univariate setting. When we solve the equation $P^{[f]}(𝕏)=0$ to recover a close enough polynomial $f(𝕏)$, we will see that the coefficients of $f(𝕏)$ will be captured within the coefficients of some linear relations between monomials in the $𝐙$-variables. Using a large enough efficient hitting set (an interpolating set of affine points that is large enough to certify all polynomials with a degree bound) in the $𝐙$-variables, we can then recover each of these coefficients. This is similar to what was done in [9] in an analogous situation, but our overall analysis is a bit different and simpler. We will outline this difference now.

Formally, for a vector space $V_d\subseteq 𝕂[𝐙]$ of all polynomials having degree at most $d$, a hitting set is a finite set $H\subseteq {𝕂}^m$ such that for any $g(𝐙)\in V_d$, if $g(𝐙)\ne 0$ then there exists $u\in H$ such that $g(u)\ne 0$. For instance, by the Combinatorial Nullstellensatz [1, Theorem 1.1], every finite grid $S^m$ with $S\subseteq 𝕂,|S|>d$ is a hitting set for $V_d$. (We will precisely use this obvious hitting set in our analysis.) Our departure from the analysis of [9] is that they need to recover the coefficients of $f(𝕏)$ one homogeneous component at a time, by employing the Euler’s formula. In our analysis, we will directly recover one coefficient at a time (with respect to a suitable choice of basis), and this is extremely similar to the corresponding step in the linear algebraic list decoding algorithm [29] for classical univariate multiplicity codes. Recall that we intend to obtain an affine subspace of small dimension that contains all close enough polynomials. Assume the form for all target polynomials in the affine subspace. We will recover the target polynomials inductively from lower coefficients to higher coefficients. In order to kick-start the recovery procedure, as a base case of the induction, we set the coefficients $\left(f_{\gamma }:|\gamma |\le r-2\right)$ arbitrarily. Then for any $\alpha \in {\mathbb{N}}^m,|\alpha |\le k-r$, the equation $P^{[f]}(𝕏)=0$ would imply an equation that has the form

where the polynomials comprising the above $𝕂[𝐙]$-linear combinations all have a good $𝐙$-degree bound due to the $𝐙$-degree bound on $P(𝕏,𝕐,𝐙)$. Note that each of the coefficients $f_{\theta +\eta }$ in the R.H.S. above is strictly below (in the usual componentwise partial order) some coefficient $f_{\alpha +\gamma }$ in the L.H.S. above. Since by induction hypothesis, we have already recovered all the coefficients in the R.H.S, we have the $𝕂[𝐙]$-linear combination comprising the L.H.S. above also determined. We then instantiate a hitting set in the $𝐙$-variables to recover the individual coefficients in the L.H.S. above, in much the same way as [9] instantiate for their linear combinations.

Thus, the coefficients $\left(f_{\gamma }:|\gamma |\le r-2\right)$ are the only possible free coefficients in the above procedure, and therefore, the output list is contained in an affine $𝕂$-subspace having dimension at most $\left(\genfrac{}{}{0pt}{}{m+r-2}{r-2}\right)$. We can further adapt the off-the-shelf pruning algorithm by [44] and its improved analysis by [66] to the multivariate setting, nearly identically as in [9], to finally end up with a randomized algorithm that guarantees constant output list size. Very recently, two concurrent works [63, 12] improved the output list size guarantee for list decoding FRS codes and univariate multiplicity codes from exponential in $1/ϵ$ to $O(1/{ϵ}^2)$ and the optimal $O(1/ϵ)$ respectively. It is possible to extend their argument in the obvious way in the multivariate setting to give an even smaller output list size guarantee in the case of list decoding multivariate $𝚀$-multiplicity codes. We do not mention the details in this presentation.

We will, in fact, prove a more general list recovery result as in Theorem 19, but stick to only showing polynomial output list size guarantee, for simplicity.

Multivariate multiplicity codes evaluated on the vector space ${𝔽}_q^m$ are known to have good locality properties [45], especially when the field characteristic is larger than the degree [43, 44]. It will be interesting to see if similar locality properties hold for the multivariate $𝚀$-multiplicity code in a field characteristic insensitive sense.

For any $f(X)\in 𝕂[X]$, the $𝚀$-derivative [31, 32, 33, 34, 35] is defined by

Further, we are interested in iterated applications of the operator ${𝖣}_{𝚀}$, and so we denote ${𝖣}_{𝚀}^{0}f(X)=f(X)$, and ${𝖣}_{𝚀}^{t+1}f(X)={𝖣}_{𝚀}({𝖣}_{𝚀}^{t}f)(X)$ for all $t\ge 0$.

Let us quickly collect a few basic properties of $𝚀$-derivatives. For an indeterminate $Y$ and $k\ge 0$, denote ${(X-Y)}_{𝚀}^{(k)}={\prod }_{t=0}^{k-1}(X-{𝚀}^{t}Y)$. For any $f(X)\in 𝕂[X]$ and $a\in {𝕂}^{\times }$, denote $(f\circ a)(X)=f(aX)$.

Now assume indeterminates $𝕏=(X_1,\mathrm{\dots },X_m)$, and for any subset $I\subseteq [m]$, denote ${𝕏}_I=(X_i:i\in I)$. For every $i\in [m]$, denote the $𝕂$-linear $𝚀$-derivative map on $𝕂[X_i]$ by ${𝖣}_{𝚀,X_i}$, and note that it extends in an obvious (and unique) way to a $𝕂({𝕏}_{[m]\setminus \{i\}})$-linear map on $𝕂[𝕏]$. It is also immediate that ${𝖣}_{𝚀,X_1},\mathrm{\dots },{𝖣}_{𝚀,X_m}$ commute as $𝕂$-linear maps on $𝕂[𝕏]$. Then for any $f(𝕏)\in 𝕂[𝕏]$ and $\alpha \in {\mathbb{N}}^m$, we define the $\alpha$-th $𝚀$-derivative by

For $\alpha ,\beta \in {\mathbb{N}}^m,\beta \le \alpha$, denote

Also, note the usual binomial coefficient $\left(\genfrac{}{}{0pt}{}{\alpha }{\beta }\right):={\prod }_{i=1}^m\left(\genfrac{}{}{0pt}{}{{\alpha }_i}{{\beta }_i}\right)$. For indeterminates $𝕐=(Y_1,\mathrm{\dots },Y_m)$ and $\alpha \in {\mathbb{N}}^m$, denote ${(𝕏-𝕐)}_{𝚀}^{(\alpha )}={\prod }_{i=1}^m{(X_i-Y_i)}_{𝚀}^{({\alpha }_i)}$. For any $f(𝕏)\in 𝕂[𝕏]$ and $a\in {𝕂}^{\times }$, denote $a𝕏=(a_1{X}_1,\mathrm{\dots },a_m{X}_m)$, and $(f\circ a)(𝕏)=f(a𝕏)$. Also denote $a^{\gamma }=a_1^{{\gamma }_1}\mathrm{\cdots }{a}_m^{{\gamma }_m}$. For any $\gamma \in {\mathbb{N}}^m$, denote ${𝚀}^{\gamma }𝕐=({𝚀}^{{\gamma }_1}{Y}_1,\mathrm{\dots },{𝚀}^{{\gamma }_m}{Y}_m)$.

We easily get the following basic properties of multivariate $𝚀$-derivatives.