List Decoding Quotient Reed-Muller Codes

Gotlib, Omri; Kaufman, Tali; Lovett, Shachar

doi:10.4230/LIPIcs.CCC.2025.1

List Decoding Quotient Reed-Muller Codes

Omri Gotlib

Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel Tali Kaufman Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel Shachar Lovett

Department of Computer Science and Engineering, UC San Diego, CA, USA

Abstract

Reed-Muller codes consist of evaluations of $n$ -variate polynomials over a finite field $\mathbbm{F}$ with degree at most $d$ . Much like every linear code, Reed-Muller codes can be characterized by constraints, where a codeword is valid if and only if it satisfies all degree- $d$ constraints.

For a subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , we introduce the notion of ${\tilde{X}}$ -quotient Reed-Muller code. A function $F:{\tilde{X}}\rightarrow\mathbbm{F}$ is a valid codeword in the quotient code if it satisfies all the constraints of degree- $d$ polynomials lying in ${\tilde{X}}$ . This gives rise to a novel phenomenon: a quotient codeword may have many extensions to original codewords. This weakens the connection between original codewords and quotient codewords which introduces a richer range of behaviors along with substantial new challenges.

Our goal is to answer the following question: what properties of ${\tilde{X}}$ will imply that the quotient code inherits its distance and list-decoding radius from the original code?
We address this question using techniques developed by Bhowmick and Lovett [8], identifying key properties of $\mathbbm{F}^{n}$ used in their proof and extending them to general subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ . By introducing a new tool, we overcome the novel challenge in analyzing the quotient code that arises from the weak connection between original and quotient codewords. This enables us to apply known results from additive combinatorics and algebraic geometry [34, 35, 37] to show that when ${\tilde{X}}$ is a high rank variety, ${\tilde{X}}$ -quotient Reed-Muller codes inherit the distance and list-decoding parameters from the original Reed-Muller codes.

Keywords and phrases:

Reed-Muller Codes, Quotient Code, Quotient Reed-Muller Code, List Decoding, High Rank Variety, High-Order Fourier Analysis, Error-Correcting Codes

Funding:

Tali Kaufman: Supported by ISF.

Shachar Lovett: supported by NSF award 2425349 and a Simons investigator award.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Error-correcting codes ; Mathematics of computing

\rightarrow

Coding theory ; Theory of computation

\rightarrow

Pseudorandomness and derandomization

Editors:

Srikanth Srinivasan

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Let $\mathbbm{F}$ be a finite field, $n\in\mathbbm{N}$ , and let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a subset¹¹1As a convention, we use $\tilde{\square}$ to denote properties of the subset, and thus also the subset itself. . We begin by introducing a new definition applicable to any linear code over $\mathbbm{F}$ : the ${\tilde{X}}$ -quotient code. We then illustrate this novel definition using Reed-Muller codes, and present a property of ${\tilde{X}}$ which we use to show that ${\tilde{X}}$ -quotient Reed-Muller code inherits its distance and list decoding radius from the original Reed-Muller code. Finally, leveraging known results from additive combinatorics and algebraic geometry, we establish as a corollary that this inheritance holds when ${\tilde{X}}$ is a high-rank variety.

The Quotient Code

Let $\mathfrak{C}$ be a linear code over $\mathbbm{F}$ . Each codeword of $\mathfrak{C}$ can be described as a function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ that is in the span of the columns of the code’s generator matrix. An equivalent way to describe $\mathfrak{C}$ is using a parity check matrix, where a function $F$ is a codeword if and only if it satisfies the constraints represented by parity-check matrix. Each such constraint can be thought of as a requirement over a few inputs of $F$ from $\mathbbm{F}^{n}$ : the requirement that their weighted sum will equal $0$ .

The first novel definition we introduce is the definition of the ${\tilde{X}}$ -induced code:

Definition 1 (The ${\tilde{X}}$ -Induced Code).

We define the ${\tilde{X}}$ -induced code $\mathfrak{C}_{{\tilde{X}}}$ to be the set of all functions $f:{\tilde{X}}\rightarrow\mathbbm{F}$ ²²2By convention, we use uppercase letters to denote functions with domain $\mathbbm{F}^{n}$ and lowercase letters to denote functions with domain ${\tilde{X}}$ . that satisfy all the constraints of $\mathfrak{C}$ that lie in ${\tilde{X}}$ , i.e. constraints that are supported only on points from ${\tilde{X}}$ ³³3We note that this definition is in fact a property of the constraints of the code, such as other well-studied desired code properties (e.g. local testability). .

Let us briefly describe the connection between codewords in $\mathbbm{F}^{n}$ and ${\tilde{X}}$ -induced codewords. One can easily verify that each original codeword restricted to ${\tilde{X}}$ is a valid codeword in the induced code. This is because each original codeword satisfies all the constraints in $\mathbbm{F}^{n}$ by definition, and the constraints that words need to satisfy to be considered induced-codewords are only a subset of those constraints.
We call an extension of an ${\tilde{X}}$ -induced codeword $f:{\tilde{X}}\rightarrow\mathbbm{F}$ to valid codeword in the original code (extending its domain to $\mathbbm{F}^{n}$ ), a lift of $f$ . When each induced codeword has a unique lift, there is a natural 1-to-1 correspondence between the original and induced codeword. This becomes substantially more interesting for subsets ${\tilde{X}}$ in which induced codewords have multiple lifts. This non-uniqueness weakens the connection between the original codewords and induced codewords, and leads to a richer range of phenomena (and interesting new challenges).

We also note that the other direction is not always true: For a general subset ${\tilde{X}}$ , there might be an induced codeword (a valid codeword in the induced code) that cannot be lifted to a valid codeword in $\mathbbm{F}^{n}$ . We are interested to better understand $\mathfrak{C}_{{\tilde{X}}}$ using $\mathfrak{C}$ and vice-versa, and therefore we introduce a new notion, which is the notion of the ${\tilde{X}}$ -quotient code:

Definition 2 (The ${\tilde{X}}$ -Quotient Code).

Let $\mathfrak{C}$ be a linear code, and let $\mathfrak{C}_{{\tilde{X}}}$ be the ${\tilde{X}}$ -induced code of $\mathfrak{C}$ . We say $\mathfrak{C}_{{\tilde{X}}}$ is a ${\tilde{X}}$ -quotient code if every quotient codeword $f\in\mathfrak{C}_{{\tilde{X}}}$ has a lift to $\mathbbm{F}^{n}$ .

In the case described above, we also say that ${\tilde{X}}$ is a lift-enabler for $\mathfrak{C}$ and that the code $\mathfrak{C}$ is a covering code for the code $\mathfrak{C}_{{\tilde{X}}}$ .
The novelty of this definition is that it captures subsets in which there is a correspondence between codewords in ${\tilde{X}}$ and in $\mathbbm{F}^{n}$ , and the correspondence may be 1-to-many.

Importance of Definition

This timely definition extends a fundamental and useful concept previously introduced for graphs and complexes – namely, the notion of a covering graph or alternatively, the quotient graph. This concept gained an increasing prominence in theoretical computer science, where it was recently employed to construct high dimensional expanders [18, 6] and achieve improved local testing results [26, 19, 3], where the latter also played a crucial role in constructions of PCPs. Consequently, the study of covering spaces for graphs has found usages in theoretical computer science and specifically in development of PCPs with enhanced properties. We believe our question, which explores the analogous question for codes, will similarly lead to meaningful applications in theoretical computer science.

In addition to that, the question of puncturing of codes has caught much attention recently, in a line of work [14, 2, 12, 13], followed by the resolution of the GM-MDS conjecture [39, 45]. Where the question of puncturing is focused exclusively on the case where the lift is unique, the study of quotient codes also tackles subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ where the lift is not unique. Notably, in the unique-lift case there are well-established lower-bounds for the size of ${\tilde{X}}$ such as [20, Theorem 1.1]. In contrast, the size of ${\tilde{X}}$ in quotient codes may be much smaller than its lower-bound in punctured code (for example in Reed-Muller codes), suggesting the potential for new insights and improved results.

Our Question

Our goal is to answer the following question: what properties of ${\tilde{X}}$ will imply that the quotient code inherits its distance and list-decoding radius from the original code?

This question is analogous to the study of quotients of expander graphs – just as not all quotients of an expander necessarily preserve expansion, not all subsets ${\tilde{X}}$ necessarily yield a well-behaved quotient code. Understanding the conditions under which expansion is preserved has been a fundamental problem in the study of expanders, and similarly, identifying the conditions under which a quotient code retains key properties of the original code is a central challenge in our work. Given this parallel, we believe our question may have broader implications for future research in both coding theory and theoretical computer science.

We answer this question in the context of Reed-Muller codes. Notably, our approach does not only address the case of where there are multiple lifts, but also introduces a novel framework for analyzing unique-lift (puncturing) setting when the field size is constant-a scenario that is typically considered more challenging.

Reed-Muller Codes

Let $\mathbbm{F}$ be a finite field, and let $n, d$ be integers. We focus on prime fields ( $\mathbbm{F}=\mathbbm{F}_{p}$ ) and assume this setting unless explicitly stating otherwise. This assumption also applies to all fields considered in the works we reference ⁴⁴4We believe that our techniques may extend to non-prime fields as well, but we do not pursue this direction in the current work. .

Each codeword in Reed-Muller code $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ , is defined by a polynomial over $\mathbbm{F}$ in $n$ variables with total degree $\leq d$ ⁵⁵5We focus on the regime where $d,\left|\mathbbm{F}\right|$ are considered constants and $n$ is considered very large. . The message that one wishes to encode is represented in the code as a polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ , whose coefficients are the different message characters. The encoding of the message is a vector of the different evaluation of $P$ over all possible points in $\mathbbm{F}^{n}$ .

Alternatively, one can describe Reed-Muller codes using a set of local constraints. A function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is a polynomial of degree $\leq d$ if and only if the (alternating) sum of each possible cube, which is a set of points of the form $\left\{x+\sum_{i\in S}y_{i}\right\}_{S\subseteq\left[d+1\right]}$ for $x,y_{1},...,y_{d+1}\in\mathbbm{F}^{n}$ , equals $0$ . Thus each cube represents a constraint, and we refer to the set of all cubes the set of constraints of degree- $d$ polynomials. See Section 2.2 for more information in this regard.

Next, we present our notations for the induced Reed-Muller code:

Notation 3 (The ${\tilde{X}}$ -Induced Reed-Muller Code).

We say a function $F:{\tilde{X}}\rightarrow\mathbbm{F}$ is a polynomial of degree $\leq d$ in ${\tilde{X}}$ if it satisfies all the constraints of degree- $d$ polynomials that lie in ${\tilde{X}}$ ⁶⁶6That is, the set of all cubes that their points are in ${\tilde{X}}$ . .
We denote the ${\tilde{X}}$ -induced Reed-Muller code:

RM_{\mathbbm{F},{\tilde{X}}}(d)=\left\{p:{\tilde{X}}\rightarrow\mathbbm{F}% \middle|p\text{ is a polynomial of degree }\leq d\text{ in }{\tilde{X}}\right\}

Properties of Induced Reed-Muller Codes

A study of Ziegler and Kazhdan [34, 35, 36] shows that if ${\tilde{X}}$ is a high rank variety ⁷⁷7Under some conditions we describe later. , then ${\tilde{X}}$ is a lift-enabler for $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ . In other words, the authors showed that the ${\tilde{X}}$ -induced Reed-Muller code is in fact a ${\tilde{X}}$ -quotient Reed-Muller code. We rely on this property of ${\tilde{X}}$ as a black-box. See Section 3 for more details in this regard.

An additional property of ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ we rely on is the connection between algebraic structure and random behavior (equidistribution) of polynomials in ${\tilde{X}}$ .
For $\mathbbm{F}^{n}$ , this connection is a well-studied result [28, 33, 9]. It lies in the heart of many results in higher-order Fourier analysis, and specifically was used in [8] to analyze the list decoding radius of Reed-Muller code in $\mathbbm{F}^{n}$ .
The equivalent of this relation for subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ was studied in [37, 27]. These works captured the measure of algebraic-structure in ${\tilde{X}}$ by a definition called relative rank, and captured the lack of random behavior in ${\tilde{X}}$ by a definition called relative bias. We note that for subsets, the definition of algebraic structure of a polynomial in ${\tilde{X}}$ considers the algebraic structure of all its possible lifts. It was shown in [37] that when ${\tilde{X}}$ is a high-rank variety, high relative rank implies low relative bias ⁸⁸8 Note that even though Gowers and Karam [27] also acheived a similar relation for a type of subsets, the definition of rank they used is slightly different than the standard definition of rank. While this difference may seem unharmful at first, it is, to our knowledge, does not allow to do a regularization process (note that a generalization of this process is the heart of our proof). .
We use this property as a black box as well. When a subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ has such property for polynomials of degree $\leq d$ , we say that it has the $d$ -relative rank-bias property. See Section 4 for more details.

Our Results

Next, let us present our main theorem more concretely. Our work focuses on the regime where $d<\left|\mathbbm{F}\right|$ . Denote the minimum normalized distance of $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ by $\delta_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ , shorthand by $\delta_{\mathbbm{F}}(d)$ . We have:

\delta_{\mathbbm{F}}(d)=1-d/\left|\mathbbm{F}\right|

Moreover, we define the list decoding count of $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ by:

\ell_{\mathbbm{F},\mathbbm{F}^{n}}(d,\tau)\coloneqq\max_{F:\mathbbm{F}^{n}% \rightarrow\mathbbm{F}}{\left|\left\{P\in Poly_{\leq d}(\mathbbm{F}^{n}% \rightarrow\mathbbm{F})\middle|{dist\left(P,F\right)\leq\tau}\right\}\right|}

Let $LDR_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ be the list decoding radius of $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ , which is the maximum $\tau$ for which $\ell_{\mathbbm{F},\mathbbm{F}^{n}}(d,\tau-\epsilon)$ is bounded by a constant depending only on $\epsilon,\left|\mathbbm{F}\right|,d$ .
In the paper [8] it was shown that for constant field size and degree, the list decoding radius reaches the distance of the code, as conjectured earlier by [24] ⁹⁹9Note that it is known that $LDR_{\mathbbm{F},\mathbbm{F}^{n}}(d)\leq\delta_{\mathbbm{F}}(d)$ , and therefore, in a sense, their result is optimal in $\mathbbm{F}^{n}$ assuming $d,\left|\mathbbm{F}\right|$ are considered as constants. .

For ${\tilde{X}}$ , we define the ${\tilde{X}}$ -list decoding count:

\ell_{\mathbbm{F},{\tilde{X}}}(d,\tau)\coloneqq\max_{F:{\tilde{X}}\rightarrow% \mathbbm{F}}{\left|\left\{P\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F}% )\middle|{dist\left(P,F\right)\leq\tau}\right\}\right|}

We denote the distance parameters of ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ by $\delta_{\mathbbm{F},{\tilde{X}}}(d)$ and $LDR_{\mathbbm{F},{\tilde{X}}}(d)$ respectively,

We next present our main theorem, which establishes that the list decoding radius of the quotient Reed-Muller code is at least as good as the that of the original code:

Theorem (List Decoding Quotient Reed-Muller Code).

¹⁰¹⁰10Informal, for formal see Theorem 76.

Let $\mathbbm{F}$ be a finite field of constant size, let $d\in\mathbbm{N}$ be a constant such that $d<\left|\mathbbm{F}\right|$ , and let $n\in\mathbbm{N}$ be an integer.
Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a subset that is a lift-enabler for $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ and has the $d$ -relative rank-bias property.
Then, $RM_{\mathbbm{F},{\tilde{X}}}(d)$ inherits its list decoding radius from $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ , i.e:

LDR_{\mathbbm{F},{\tilde{X}}}(d)\geq LDR_{\mathbbm{F},\mathbbm{F}^{n}}(d)

In addition, we also achieve a (simpler) result regarding the distance of the quotient Reed-Muller code (Theorem 68): Under the conditions described above, $RM_{\mathbbm{F},{\tilde{X}}}(d)$ also inherits its distance from $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ , i.e $\delta_{\mathbbm{F},{\tilde{X}}}(d)\geq\delta_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ ¹¹¹¹11Our techniques also show that also the other direction is true, which yields an equality in the distance of the two codes. .

As a corollary, using results studied in [34, 35, 37] regarding high-rank varieties, we obtain the following:

Corollary (List Decoding Quotient Reed-Muller Code: High Rank Variety).

Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a high rank variety, that is, ${\tilde{X}}$ is the set of common zeros of a collection of polynomials $\tilde{\mathcal{L}}=(L_{1},...,L_{{\tilde{c}}})$ that is of high rank ¹²¹²12To be more precise, the greater or equals in the decoding parameters wirtten in the theorem are not exact, but they are true up to some $\epsilon$ that depend on the rank of the collection. Thus the higher the rank of the collection is, the more similar the quotient Reed-Muller code and the original Reed-Muller code in terms of distance and list-decoding radius. ¹³¹³13We also note that for this result some assumptions are needed regarding the field size or the degree of the polynomials in the collection. , i.e. ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)=\left\{x\middle|\forall i:L_{i}(% x)=0\right\}$ .
Then, $RM_{\mathbbm{F},{\tilde{X}}}(d)$ inherits its distance parameters from $RM_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ , i.e:

1.

$\delta_{\mathbbm{F},{\tilde{X}}}(d)\geq\delta_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ .
2.

$LDR_{\mathbbm{F},{\tilde{X}}}(d)\geq LDR_{\mathbbm{F},\mathbbm{F}^{n}}(d)$ .

Example 4.

Let $d,n^{\prime}\in\mathbbm{N}$ , and denote $n=d\cdot n^{\prime}$ . Define $L_{n}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ to be:

L_{n}(x_{1},...,x_{n})\coloneqq\sum_{i=1}^{n^{\prime}}{\prod_{j=1}^{d}{x_{(i-1% )\cdot d+j}}}

It was shown [35, Theorem 1.9] that $rank\left(L_{n}\right)\rightarrow\infty$ as $n\rightarrow\infty$ . Thus for sufficiently large $n$ , the variety ${\tilde{X}}\coloneqq Z\left(L_{n}\right)=\left\{x\middle|L_{n}(x)=0\right\}% \subseteq\mathbbm{F}^{n}$ satisfies the necessary conditions so that ${\tilde{X}}$ -quotient Reed-Muller code inherits its distance parameters from the original Reed-Muller code ¹⁴¹⁴14More accuratly, it was shown that its schmidt rank goes to infinity as $n$ goes to infinity. This is a sufficient condition for applying Theorem 76. .

Main Technical Challenge

We achieve these results by combining the two black-box properties of subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ we presented. Analysis of the polynomials in ${\tilde{X}}$ raises a new challenge, as previous techniques that were used to analyze low-degree polynomials, both regarding $\mathbbm{F}^{n}$ [28] and regarding subsets ${\tilde{X}}$ [37], were focused on maintaining the behavior of polynomials within the relevant domain, without maintaining a connection between polynomials over ${\tilde{X}}$ and their extensions to $\mathbbm{F}^{n}$ .
The novelty of our new technique is that it uses a similar approach to analyze polynomials in ${\tilde{X}}$ as commonly used in $\mathbbm{F}^{n}$ , while simultaneously maintaining a connection between polynomials in ${\tilde{X}}$ to polynomials in $\mathbbm{F}^{n}$ . This connection allows us to deduce that polynomials in ${\tilde{X}}$ behave similarly to polynomials in $\mathbbm{F}^{n}$ . Informally, given a question about a polynomial defined over ${\tilde{X}}$ , our technique enables us to identify a suitable lift of the polynomial to a polynomial over $\mathbbm{F}^{n}$ , and answer the question using properties of that lift. Crucially, the appropriate lift depends on the nature of the question, meaning that no single canonical lift suffices for all purposes.

Next we describe this challenge in more detail.
Analyses of polynomials in $\mathbbm{F}^{n}$ were commonly based on the structure-randomness connection of polynomials in $\mathbbm{F}^{n}$ . A central tool that leverages this property of $\mathbbm{F}^{n}$ is the regularization process [28], which transforms any collection of polynomials into a new one that:

1.

Is equidistributed in $\mathbbm{F}^{n}$ .
2.

Captures the same functions as the original collection.

This capturing is formalized via measurability: a function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is said to be measurable with respect to a collection $\mathcal{P}=(P_{1},...,P_{c})$ if it can be expressed as a function of the polynomials in $\mathcal{P}$ . The regularization process guarantees that any function measurable by the original collection remains measurable by the new one.

Equidistribution is obtained by enforcing the collection to be of high rank, which informally means the polynomial has extremly low algebraic structure, that is, it cannot be approximated or predicted by a small number of lower-degree polynomials. In $\mathbbm{F}^{n}$ , this structural condition implies low bias in $\mathbbm{F}^{n}$ , where a low-biased polynomial is equidistributed.

To generalize this process to ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , while being able to deduce properties of polynomials in ${\tilde{X}}$ using polynomials in $\mathbbm{F}^{n}$ , we aim to construct a new collection of polynomials that has additional requirements:

3.

Is equidistributed restricted to ${\tilde{X}}$ .
4.

Captures the same functions as the original collection restricted to ${\tilde{X}}$ .

The requirement of the conditions together is unique to our setting and introduces a key difficulty. Equidistribution over ${\tilde{X}}$ requires the collection to have high relative rank, which requires one to eliminate structure not just from a polynomial, but from all of its ${\tilde{X}}$ -equivalent polynomials – those over $\mathbbm{F}^{n}$ that agree with it on ${\tilde{X}}$ and have the same degree bound ¹⁵¹⁵15This is the same as considering all lifts of the polynomial $P|_{{\tilde{X}}}$ , assuming such lift exist. . Ensuring this while maintaining measurability in $\mathbbm{F}^{n}$ is nontrivial.
To achieve equidistribution in $\mathbbm{F}^{n}$ , the regularization process replaces structured polynomials by a small collection of high-rank ¹⁶¹⁶16More accuratly, the replacement is done recursively unitl the collection is of high rank. polynomials that capture them. Over ${\tilde{X}}$ , avoiding structure in all ${\tilde{X}}$ -equivalents may require replacing a polynomial with polynomials that capture a different – but ${\tilde{X}}$ -equivalent – function. This risks breaking measurability in $\mathbbm{F}^{n}$ and thus losing the connection to the polynomials in $\mathbbm{F}^{n}$ .
In summary, our main technical challenge is to achieve equidistribution over ${\tilde{X}}$ while preserving measurability over both ${\tilde{X}}$ and $\mathbbm{F}^{n}$ , despite the need to eliminate structure across all ${\tilde{X}}$ -equivalent polynomials.

Introducing New Tools

We overcome this challenge by presenting a new definition that relaxes the notion of measurable we required for functions in $\mathbbm{F}^{n}$ , which we call ${\tilde{X}}$ -measurable. This enables us to describe a relaxed version of the regularization process, in which we require that every function in $\mathbbm{F}^{n}$ that was ${\tilde{X}}$ -measurable by the old collection will still be ${\tilde{X}}$ -measurable by the new collection. In contrast to the original regularization process, which mandated that functions that were measurable by the old collection will be measurable by the collection, this relaxed definition only requires such functions to be ${\tilde{X}}$ -measurable by the new collection.

Even though we no longer need to capture all previously captured functions in $\mathbbm{F}^{n}$ , it is important that the new relaxed-definition is strict enough to keep the connection between polynomials in ${\tilde{X}}$ and in $\mathbbm{F}^{n}$ . Therefore, maintaining the ${\tilde{X}}$ -measurable functions throughout the regularization process cannot be done trivially, and this is handled in a procedure we call the ${\tilde{X}}$ -relative regularization process which is a stronger-version of the regularization process that is used in $\mathbbm{F}^{n}$ . This new definition and procedure are thoroughly described in Section 5.

We note that these new definition and procedure are a novel contribution of this work, and we believe they can be useful in future research of the quotient Reed-Muller code.

1.1 Comparison to Related Work

In [8] the authors studied the list decoding radius of Reed Muller codes $\mathbbm{F}^{n}$ . They proved that, for prime fields, the list decoding radius reaches the distance of the code, as conjectured earlier by [24] ¹⁷¹⁷17Note that it is known that $LDR_{\mathbbm{F},\mathbbm{F}^{n}}(d)\leq\delta_{\mathbbm{F}}(d)$ , and therefore, in a sense, their result is optimal in $\mathbbm{F}^{n}$ assuming $d,\left|\mathbbm{F}\right|$ are considered as constants. ¹⁸¹⁸18We also note that their work also apply to the regime $d\geq\left|\mathbbm{F}\right|$ . . Formally, they showed the following theorem:

Theorem 5 ([8, Theorem 1]).

Let $\mathbbm{F}$ be a prime field. Let $\epsilon>0$ and $d,n\in\mathbbm{N}$ . There exists a constant ¹⁹¹⁹19It is important to note that $c$ is independent of $n$ . $c\coloneqq c(\left|\mathbbm{F}\right|,d,\epsilon)$ such that:

\ell_{\mathbbm{F},\mathbbm{F}^{n}}(d,\delta_{\mathbbm{F}}(d)-\epsilon)\leq c

Our work gives new tools for analyzing polynomials in ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , which we later use to follow their line of proof and show an equivalent result in ${\tilde{X}}$ .

We next present related work regarding the study of polynomial codes in subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ . Before presenting them specifically, we note that our work has a fundamental difference than that of the previous study of polynomials in subsets. Most works which studied polynomials over subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ were focused on subsets in which every polynomial has a unique lift. This ensures that there is a 1-to-1 correspondence between polynomials in ${\tilde{X}}$ and in $\mathbbm{F}^{n}$ and therefore allows easier connection between polynomials in ${\tilde{X}}$ and in $\mathbbm{F}^{n}$ .
We note that our work is non-trivial even in this case: it extracts the properties of $\mathbbm{F}^{n}$ that were used in [8], in a way they can be used to analyze quotient Reed-Muller codes. However, as described earlier, our work addresses an additional substantial challenge which arise when the lift is not unique. Thus our work is only comparable to other works in the unique-lift case, which is the less-challenging case we address.

The first line of work we mention is this regard is the study of hitting sets for low degree polynomials [40, 15, 31], and a stronger variant of it which is the study of pseudorandom-generators against low degree polynomials [10, 11, 38, 44, 16, 17, 22] Both definitions capture subsets ²⁰²⁰20Sometimes this subset is allowed to be a multiset. ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ such that every polynomial over $\mathbbm{F}^{n}$ has a non-negligible distance from $0$ when restricted to ${\tilde{X}}$ . This requirement implicitly implies that every low degree polynomial over ${\tilde{X}}$ has at most a single lift.

Another line of work worth mentioning in this regard is [21, 30], which studied puncturing of Reed-Muller codes. This line of work studied the construction of sets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , such that puncturing Reed-Muller codes over ${\tilde{X}}$ , that is, taking every original codeword and restricting it to ${\tilde{X}}$ , will yield a good error-correction code. To perform their analysis, it was important that every polynomial in ${\tilde{X}}$ has at most a single lift, and therefore their work was focused on subsets where there is a unique lift.

The papers [14, 2, 12] also studied similar questions. This line of work is followed by the resolution of the GM-MDS conjecture, which was proved by [39, 45].
We note that these works were focused on the regime where the field is large. More specifically, they require that the field is large in respect of $n$ , i.e. $\Omega(n)$ . We emphasize that our work is focused on constant fields. Moreover, their results were regarding random puncturing, while our result makes an explicit puncturing.

We also note that most studies presented above also achieved results regarding the rate of the punctured code. This property of the code can be analyzed naturally when each polynomial over ${\tilde{X}}$ has a unique lift, as such assumption implies that the number of polynomials remains the same in ${\tilde{X}}$ as of in $\mathbbm{F}^{n}$ . In contrast, our work does not rely on such a uniqueness assumption, and therefore does not address the rate of the resulting code. As our work does not assume such uniqueness, the rate of the code we consider is not analyzed in our work. Nonetheless, we note that the Hilbert function of a subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ corresponds to the rate of the ${\tilde{X}}$ -quotient Reed-Muller code, and that some great progress has been made in analyzing this function [5, 4, 41, 23, 1].

1.2 Proof Overview

Our main technical contribution is a generalization of the regularization process to subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , which we call the relative regularization process. This tool addresses the core difficulty of non-unique lift, and relies on a new notion we introduce: ${\tilde{X}}$ -measurability.

Measurablity and Regularization in $\mathbbm{F}^{n}$

Measurablility is a mathematical-analysis notion, which was first used in a similar context in [29]. It is defined as follows:

Definition 6 (Measurable).

Let ²¹²¹21In this context we think of $c$ as a small (constant for example). $\mathcal{P}=\left(P_{1},...,P_{c}\right)$ be a collection of polynomials of degree $\leq d$ . A function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is measurable in respect of $\mathcal{P}$ if it can be determined by the values of $P_{1},...,P_{c}$ :

F(x)=\Gamma_{F}(P_{1}(x),...,P_{c}(x))

for some function $\Gamma_{F}:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ ²²²²22One can think of this definition as a generalization of linear span: the collection spans the function, where $\Gamma$ is some notion of a span. .

Intuitively, $\mathcal{P}$ captures the information required to compute $F$ . If $\mathcal{P}$ is a high-rank collection, the tuple $(P_{1}(x),\dots,P_{c}(x))$ is equidistributed over $x\in\mathbbm{F}^{n}$ as $\mathbbm{F}^{n}$ has the property that high-rank implies equidistribution. This allows one to analyze $F$ through the simpler function $\Gamma_{F}$ .

The regularization process is a fundamental tool presented in [28] that constructs a high-rank collection $\mathcal{P}^{\prime}$ refining $\mathcal{P}$ , meaning that all $\mathcal{P}$ -measurable functions remain measurable with respect to $\mathcal{P}^{\prime}$ .

${\tilde{X}}$ -Relative Rank

We remind the reader that rank is a notion that measures the algebraic structure of polynomials, where high rank implies extremly low algebraic structure. In addition, ${\tilde{X}}$ -relative rank is a notion that measures the algebraic structure of a polynomial in a subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , by considering the structure of all of its ${\tilde{X}}$ -equivalent polynomials. This notion was presented by [27, 37], and is used to achieve equidistribution in ${\tilde{X}}$ assuming ${\tilde{X}}$ has relative rank-bias property. It is defined as follows:

Definition 7 (Relative Rank, informal. See definition 48).

Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a subset, let $d\in\mathbbm{N}$ , and let $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ be a polynomial of degree $=d$ . The ${\tilde{X}}$ -relative rank of $P$ is defined as follows:

rank_{{\tilde{X}}}\left(P\right)\coloneqq\min\left\{rank\left(P-\overline{P% missing}\right)\middle|\overline{Pmissing}\in Poly_{\leq d}(\mathbbm{F}^{n}% \rightarrow\mathbbm{F}),\overline{Pmissing}|_{{\tilde{X}}}\equiv 0\right\}

1.2.1 ${\tilde{X}}$ -Measurablity and The ${\tilde{X}}$ -Relative Regularization Process

In this subsection we discuss the generalization of the regularization process to subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ using the equivalent of rank-bias relation in ${\tilde{X}}$ . We name this tool the relative regularization process.

Practically, we use this tool to show that given a specific question in mind, every $p:{\tilde{X}}\rightarrow\mathbbm{F}$ has some polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ that behave “similarly” in respect to this question. This allows us to pull properties of $P$ to better understand $p$ . The perfect candidate for such $P$ is a lift of $p$ .
In order to use $P$ to deduce properties of $p$ , we use the well-studied properties of polynomials in $\mathbbm{F}^{n}$ to acheive properties of $P$ , and relate these to properties of $p$ . More specifically, assume that $p$ and $P$ are measurable in respect of a collection of polynomials $\mathcal{P}$ (each in its domain). Our strategy is to use $P$ to deduce properties of $\Gamma_{P}$ , and then use the properties of $\Gamma_{P}$ to deduce properties of $p$ .

Now let us describe the extra challenge. We start by following the ideas of the regularization process we described for $\mathbbm{F}^{n}$ . Assuming the collection is not a collection of ${\tilde{X}}$ -relative high rank, then there must exist a polynomial in the collection that has low relative rank, which we denote by $P^{\star}$ ²³²³23More precisely, some linear combination of polynomials has low relative rank. . Note that in relative rank, this does not necessarily mean that $P^{\star}$ is of low rank, but that there exists another ${\tilde{X}}$ -equivalent polynomial that has a low rank. Thus, even if we remove the low-rank ${\tilde{X}}$ -equivalent polynomial and add to the collection all the polynomials that decomposed it, we cannot require that every function that was measurable by the old collection will still be measurable by the new collection: even the polynomial we removed is not necessarily measurable by the new collection!
To allow such regularization process to still apply, we note that while $P$ might not be measurable in respect of the new collection, a ${\tilde{X}}$ -equivalent polynomial of $P$ is measurable with respect of it. Therefore, we relax the notion of being measurable to being ${\tilde{X}}$ -measurable.
We say a function $F$ is ${\tilde{X}}$ -measurable in respect of $\mathcal{P}$ if it can be determined by the polynomials of $\mathcal{P}$ up to a valid ${\tilde{X}}$ -remainder. We first describe an incomplete definition, then present the challenge that rises with it, and finally present its resolution.

Definition 8 ( ${\tilde{X}}$ -measurable, Incomplete Definition).

²⁴²⁴24This incomplete definition lacks the requirement of the validity of the

{\tilde{X}}

-remainder

We say a function $F$ is ${\tilde{X}}$ -measurable in respect of $\mathcal{P}=(P_{1},...,P_{c})$ if there exists a function $\Gamma:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ and a ${\tilde{X}}$ -remainder, i.e. a function $\overline{Fmissing}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ with $\overline{Fmissing}|_{{\tilde{X}}}\equiv 0$ such that:

\forall a\in\mathbbm{F}^{n}:F(a)=\Gamma(P_{1}(a),...,P_{c}(a))+\overline{F% missing}(a)

Previous works analyzing polynomials in $\mathbbm{F}^{n}$ were able to deduce two things from $F$ being measurable by a high-rank collection $\mathcal{P}$ . The first, is that the structure of $\Gamma$ is similar to the structure of $F$ : for example, if one is a polynomial of bounded degree, so is the other. The second, is that a random input of $\Gamma$ behave similarly to a random input of $F$ : that is, the output distribution of $\Gamma$ (over its inputs $\mathbbm{F}^{c}$ ) is close to the output distribution of $F$ (over its inputs $\mathbbm{F}^{n}$ ).
To study polynomials in ${\tilde{X}}$ , we wish to connect $p$ to $P$ (which is a lift of $p$ ). Thus, we think of $F=P$ , and require two similar things. Firstly, we want the structure of $\Gamma$ to be similar to the structure of $F$ (in this case, $P$ ), which we understand as $F$ is a polynomial in $\mathbbm{F}^{n}$ . Secondly, we want a random input of $\Gamma$ to behave similarly to a random input of $p$ , as $p$ is the polynomial we wish to understand. The latter is easily achieved using the fact high ${\tilde{X}}$ -relative rank implies equidistribution in ${\tilde{X}}$ . The former, however, might be damaged by the remainder as we defined it: we can only learn the structure of $\Gamma$ using the structure of $F-\overline{Fmissing}$ using the equality $F-\overline{Fmissing}=\Gamma(P_{1},...,P_{c})$ . However, the structure of $F-\overline{Fmissing}$ can be very different from the structure of $F$ , as we did not require any structure of the ${\tilde{X}}$ -remainder $\overline{Fmissing}$ . Thus, we can not deduce the structure of $\Gamma$ via the structure of $F$ using the incomplete definition described above.

To handle this issue, we add one more requirement regarding the ${\tilde{X}}$ -remainder, which ensures that the structure of $F$ can be understood via the structure of $\Gamma$ :

\deg(F-\overline{Fmissing})\leq\deg(F)

If the ${\tilde{X}}$ -remainder also has this property, we say it is a valid ${\tilde{X}}$ -remainder for $F$ . This can be summarized by the following (complete) definition:

Definition 9 ( ${\tilde{X}}$ -measurable).

We say a function $F$ is ${\tilde{X}}$ -measurable in respect of $\mathcal{P}=(P_{1},...,P_{c})$ if there exists a function $\Gamma:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ and a valid ${\tilde{X}}$ -remainder, i.e. a function $\overline{Fmissing}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ with $\overline{Fmissing}|_{{\tilde{X}}}\equiv 0$ and $\deg(F-\overline{Fmissing})\leq\deg(F)$ such that:

\forall a\in\mathbbm{F}^{n}:F(a)=\Gamma(P_{1}(a),...,P_{c}(a))+\overline{F% missing}(a)

We use this new definition the following way: Instead of using $F$ to understand $\Gamma$ , we use $F-\overline{Fmissing}$ to do so. We choose $F-\overline{Fmissing}$ as it has the same structure as $F$ , but it is “closer” to the function $\Gamma$ as $F-\overline{Fmissing}=\Gamma(P_{1},...,P_{c})$ ²⁵²⁵25One can think of this step as “taking the right ${\tilde{X}}$ -equivalent” in respect of $\mathcal{P}$ . . Finally, as $\Gamma$ behaves similarly to $p$ for random inputs, we can use $\Gamma$ to deduce properties regarding $p$ .
With this in hand, let us finish describing the relative-regularization process. The requirement on the validity of the ${\tilde{X}}$ -remainder raises a new challenge in the ${\tilde{X}}$ -relative regularization process: we need to somehow control the structure of the ${\tilde{X}}$ -remainder, even though this “error” is substituted in $\Gamma$ each time we wish to replace a polynomial in our collection. We address this challenge using a Lemma proved in [9] called the “faithful composition lemma”, which allows us to deduce strong properties regarding the structure of $\Gamma$ given the collection was of a high (regular) rank in the first place. Therefore, we add to each step of the relative-regularization process a (regular) regularization, which ensures $\Gamma$ is very structured. This strong structure of $\Gamma$ is later used to control the error and deduce it is in the form of a valid ${\tilde{X}}$ -remainder. For the exact details, see Theorem 64. We conclude this by informally stating our main technical theorem, which is the relative regularization process we just described:

Theorem 10 (Relative Regularization Process, Informal, See Theorem 64).

Let ${{r}},d\in\mathbbm{N}$ be integers that represents a requested rank and degree respectively, and let $P_{1},...,P_{c}$ be a collection of polynomials of degree $\leq d$ . Then, there is another collection $P^{\prime}_{1},...,P^{\prime}_{c^{\prime}}$ of polynomials of degree $\leq d$ , such that:

1.

Every function that is ${\tilde{X}}$ -measurable in respect to the first collection is also ${\tilde{X}}$ -measurable in respect to the new collection.
2.

The new collection is of ${\tilde{X}}$ -relative rank $\geq{{r}}$ .
3.

The new collection is of bounded size, i.e. $c^{\prime}\leq C_{{{{r}}},d,c}$ .

1.2.2 List Decoding in ${\tilde{X}}$ via ${\tilde{X}}$ -Relative Regularization

In this subsection, we demonstrate how to use the relative regularization process to achieve our main theorem: analysis of the list decoding radius of $RM_{\mathbbm{F},{\tilde{X}}}(d)$ .

We follow the line of proof of [8], but this time, we are interested in bounding the amount of polynomials in ${\tilde{X}}$ around every function in ${\tilde{X}}$ . More specifically, we wish to show that there is a constant number of words that are $(\delta_{\mathbbm{F}}(d)-\epsilon)$ -close to any fixed function in ${\tilde{X}}$ .

Let $f:{\tilde{X}}\rightarrow\mathbbm{F}$ be a received word. First, we apply a lemma proved in [8, Corollary 3.3]. The lemma shows that there is a constant-sized (depending on $\epsilon$ ) collection of polynomials in ${\tilde{X}}$ , denoted by $\mathfrak{h}$ , such that the distance of $f$ to any polynomial can be approximated by the distance of $f$ to some function that is measurable by $\mathfrak{h}$ in ${\tilde{X}}$ . This means that instead of bounding the number of polynomials in the radius of $f$ , one can bound the number of polynomials in the radius of some function measurable by $\mathfrak{h}$ . Thereby, every polynomial-specific measurable function can be thought of as a low complexity proxy for $f$ in respect to the polynomial.

Next, we lift each polynomial from $\mathfrak{h}$ and apply the relative regularization process. This yields a new collection of polynomials in $\mathbbm{F}^{n}$ that is constant sized and randomly-behaving (in $\mathbbm{F}^{n}$ ). Denote this new collection by $\mathcal{H}^{\prime}$ ²⁶²⁶26We use the same notations as the original proof for clearannce. . Thereby, the question of list decoding is reduced to the following question: We have a specific constant-sized randomly-behaving collection of polynomials $\mathcal{H}^{\prime}=\left\{H_{1}^{\prime},...,H^{\prime}_{c^{\prime}}\right\}$ that was constructed using the function $f$ . We need to bound the amount of polynomials in ${\tilde{X}}$ that are $(\delta_{d}(\mathbbm{F})-\epsilon/2)$ -close to be measurable by this collection in ${\tilde{X}}$ . Note that the randomly-behaving property was achieved using the relative rank-bias property of ${\tilde{X}}$ . Additionally, we note the collection $\mathcal{H}^{\prime}$ is a collection of polynomials in $\mathbbm{F}^{n}$ which we obtained by using the lift-enabler property of ${\tilde{X}}$ .

From there (and similarly to the analysis in $\mathbbm{F}^{n}$ ), the strategy is to show that polynomials that are that close to being measurable by the randomly-behaving collection $\mathcal{H}^{\prime}$ , are in fact measurable by it. This will bound the number of such polynomials by the amount of possible functions that are measurable by $\mathcal{H}^{\prime}$ , which is constant as the collection is of constant size.

Let $p:{\tilde{X}}\rightarrow\mathbbm{F}$ be a polynomial of degree $\leq d$ , and consider a lift of it $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ . Consider the collection $\mathcal{H}^{\prime}\cup\left\{P\right\}$ . Surely, $P$ is measurable by this collection in $\mathbbm{F}^{n}$ . Applying ${\tilde{X}}$ -relative-regularization to this collection yields a new collection $\mathcal{H}^{\prime\prime}$ that is equidistributed in ${\tilde{X}}$ , such that every ${\tilde{X}}$ -measurable function by the old collection is ${\tilde{X}}$ -measurable by the new collection. By a reason we have not explained in this brief explanation, we can ensure this collection is of the form $\mathcal{H}^{\prime\prime}=\mathcal{H}^{\prime}\cup\left\{H_{1}^{\prime\prime}% ,...,H_{c^{\prime\prime}}^{\prime\prime}\right\}$ .

As $P$ was ${\tilde{X}}$ -measurable by $\mathcal{H}^{\prime}\cup\left\{P\right\}$ (it was even measurable), $P$ is ${\tilde{X}}$ -measurable by the new collection $\mathcal{H}^{\prime\prime}$ : That is, $P$ is measurable by $\mathcal{H}^{\prime\prime}$ up to a valid remainder, denoted by $\overline{Pmissing}$ .
This means there exists $\Phi:\mathbbm{F}^{c^{\prime}+c^{\prime\prime}}\rightarrow\mathbbm{F}$ such that:

\forall a\in\mathbbm{F}^{n}:P(a)=\Phi(H^{\prime}_{1}(a),...,H^{\prime}_{c^{% \prime}}(a),H^{\prime\prime}_{1}(a),...,H^{\prime\prime}_{c^{\prime\prime}}(a)% ))+\overline{Pmissing}(a)

In $\mathbbm{F}^{n}$ , the proof would follow by studying the structure of the function $\Phi$ and use it to induce that $\Phi$ does not depend on its last $c^{\prime\prime}$ variables. This implies that $P$ is measurable by the original collection $\mathcal{H}^{\prime}$ which concludes the proof ²⁷²⁷27Note that in $\mathbbm{F}^{n}$ there is no remainder, so the equation above (with the last $c^{\prime\prime}$ variables as constants) implies measurability by $\mathcal{H}^{\prime}$ . .

More accurately, the analysis in $\mathbbm{F}^{n}$ used the fact that substituting randomly behaving polynomials in $\Phi$ yields a structured function ²⁸²⁸28In our notations, this structured function is $P$ , which is a polynomial of degree $\leq d$ and thus structured . This is used to show that $\Phi$ as a function by itself, with inputs from $\mathbbm{F}^{c^{\prime}+c^{\prime\prime}}$ , is a very structured function. The strong structure of $\Phi$ , with the fact that $\Phi$ (with inputs substitued to be the functions of $\mathcal{H}^{\prime\prime}$ ) is close to the function $f$ , are then combined to deduce that $\Phi$ does not depend on its last $c^{\prime\prime}$ variables.

This paradigm can not be extended effortlessly to our case. In ${\tilde{X}}$ , deducing that $\Phi$ is very structured requires a one-more major step. This is because we do not know any correspondence in the behavior of $\Phi$ (which we want to understand) with the behavior of $P$ (which we know is structured). We only know there is a correspondence between $\Phi$ to another function $P-\overline{Pmissing}$ , which apriori we do not know is structured!

Fortunately, the relative regularization process (Theorem 64) mandates that the remainder of the measurement is valid. That is, if $P$ was structured (a polynomial of degree $\leq d$ ), then so does $P-\overline{Pmissing}$ . This is crucial, as it allows us to use the relation between $\Phi$ and $P-\overline{Pmissing}$ to deduce that $\Phi$ is structured, and continue the original outline of the proof of [8]. For more details in this regard, see Theorem 76.

1.3 Organization

In Section 2 we present some basic notations and conventions, and define the preliminaries we have regarding high-order Fourier analysis in $\mathbbm{F}^{n}$ : polynomials, rank and regularization. We later generalize each component we presented in Section 2 to study polynomials in $\mathbbm{F}^{n}$ to also study polynomials in ${\tilde{X}}$ : in Section 3 we present the set of polynomials in ${\tilde{X}}$ and present the lift-enabler property; in Section 4 we present the ${\tilde{X}}$ -relative rank-bias property; and in Section 5 we present the ${\tilde{X}}$ -measurable notion, and our main tool, which is the ${\tilde{X}}$ -relative regularization process. Next, we present two applications regarding the distance parameters of Reed-Muller codes in ${\tilde{X}}$ : In Section 6 we prove the inheritance of the distance of the code; and in Section 7 we prove the inheritance of the list decoding distance of it (which is much more involved).

2 Preliminaries

2.1 Basic Definitions and Notations

We denote by $\mathbbm{N}$ the set set of integers, i.e. natural numbers (excluding 0). For an integer $k$ we denote $\left[k\right]\coloneqq\left\{1,2,...,k\right\}$ . We use $y=x\pm\epsilon$ to denote $y\in\left[x-\epsilon,x+\epsilon\right]$ , and similarly $y=x\mp\lambda$ to denote $y\in\left[x+\lambda,x-\lambda\right]$ (usually when $\lambda<0$ ).
Fix a prime field $\mathbbm{F}=\mathbbm{F}_{p}$ . Denote by $\left|\cdot\right|$ the natural map of $\mathbbm{F}$ to $\left\{1,...,p-1\right\}\in\mathbbm{N}$ . We denote the character from $\mathbbm{F}$ by $e\left[x\right]\coloneqq e^{2\pi i\cdot\left|x\right|}$

Generally speaking and unless stated otherwise, we use the following conventions: We use $n\in\mathbbm{N}$ to denote the number of variables in Reed-Muller code. We use $d$ to denote a degree (typically the degree of the polynomials in our code), and ${\tilde{X}}$ to denote the subset of $\mathbbm{F}^{n}$ we work in i.e. ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ . Properties of the subset ${\tilde{X}}$ will usually be denoted with $\tilde{\square}$ . We use $F, G, H$ to denote general functions with domain $\mathbbm{F}^{n}$ , and $f, g, h$ to denote functions with domain ${\tilde{X}}$ . We use $\mathfrak{F},\mathfrak{G},\mathfrak{H}$ and $\mathfrak{f},\mathfrak{g},\mathfrak{h}$ respectively to denote sets of such functions. Similarly, we use $P, Q, H$ to denote polynomials with domain $\mathbbm{F}^{n}$ , and $p, q, h$ polynomials with domain ${\tilde{X}}$ (polynomials as defined in Section 3). We use $\mathcal{P},\mathcal{Q},\mathcal{H}$ and $\mathfrak{p},\mathfrak{q},\mathfrak{h}$ respectively to denote sets of such polynomials.

2.2 Polynomials in $\mathbbm{F}^{n}$

We start by presenting a standard definition for a polynomial over a finite field.

Definition 11 (Polynomial: Global Definition).

Let $d\in\mathbbm{N}$ be a constant. A function $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is called a polynomial of degree $\leq d$ if it is of the following form:

P(x_{1},...,x_{n})=\sum_{0\leq d_{1},...,d_{n}:\sum_{i=1}^{n}{d_{i}}\leq d}{c_% {d_{1},...,d_{n}}\prod_{i=1}^{n}x_{i}^{d_{i}}}

We denote the set of all polynomials of degree $\leq d$ by $Poly_{\leq d}(\mathbbm{F}^{n}\rightarrow\mathbbm{F})$ . The value $d$ in the definition above is called the global degree of the function $P$ , shorthand by the degree of $P$ , and it is denoted by $\deg(P)=d$ .
Additionally, the set of all polynomials from $\mathbbm{F}^{n}$ to $\mathbbm{F}$ of degree $\leq d$ is denoted by:

Poly_{\leq d}(\mathbbm{F}^{n}\rightarrow\mathbbm{F})

$\blacktriangleright$ Note 12.

Note that it is a folklore that every function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is a polynomial function, that is, can be written in the representation stated above for some degree. This follows from the representation of Dirac delta function over $\mathbbm{F}^{n}$ as a polynomial:

\mathbbm{1}_{\vec{0}}(x_{1},...,x_{n})\coloneqq\begin{cases}1&x_{1}=\dots=x_{n% }=0\\ 0&\text{otherwise}\end{cases}\ =\prod_{i=1}^{n}(1-(x_{i})^{\left|\mathbbm{F}% \right|-1})

Therefore the definition of total degree is meaningful for all functions $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ .

Next, we present a known equivalent definition for a polynomial using derivatives. To do so, we first define a derivative in the case of finite fields.

Definition 13 (Derivative).

Given a function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ and $a\in\mathbbm{F}^{n}$ , we define the derivative of $F$ in direction $a$ as a function $D_{a}F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ defined as follows:

D_{a}F(x)\coloneqq F(x+a)-F(x)

Lemma 14.

Let $d\in\mathbbm{N}$ . A function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is a polynomial of degree $\leq d$ if and only if $D_{a}F$ is a polynomial of degree $\leq d-1$ for all $a\in\mathbbm{F}^{n}$ .

This leads us to a natural definition of a degree of a function using derivatives.

Definition 15 (Local Degree).

For a function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ , we define its local degree, to be the least integer $d\in\mathbbm{N}$ such that for all $a_{1},...,a_{d+1},x\in\mathbbm{F}^{n}$ :

D_{a_{d+1}}...D_{a_{1}}F(x)=0

In $\mathbbm{F}^{n}$ , the two definitions of degree coincide, and we get a single definition of a degree:

Lemma 16 (Equivalance of definitions of a degree).

Let $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ be a function, and let $d\in\mathbbm{N}$ be an integer. Then, the global degree of a $F$ equals its local degree.

$\blacktriangleright$ Remark 17.

We sometimes refer to the requirement that the local degree of a function is $\leq d$ , as the local criteria of degree $\leq d$ polynomials.

2.3 Rank-bias in $\mathbbm{F}^{n}$

We start by defining the notion of bias, which is a measure of how the function is far from being equidistributed (see Appendix A for the exact details).

Definition 18 (Bias).

Let $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ . The bias of the function $F$ is defined in the following way:

bias({F})\coloneqq 1/\left|\mathbbm{F}^{n}\right|\cdot\sum_{x\in\mathbbm{F}^{n% }}{e\left[F(x)\right]}

Moreover, for a subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , we define the bias of $F$ in ${\tilde{X}}$ to be:

bias_{{\tilde{X}}}{({F})}\coloneqq 1/\left|{\tilde{X}}\right|\cdot\sum_{x\in{% \tilde{X}}}{e\left[F(x)\right]}

Next, we present a standard definition of rank of a polynomial, which is a notion that measures how structured is the function. Note that low rank implies the polynomial is highly structured. Formally we have the following definition:

Definition 19 (Rank of a Polynomial).

Given a constant $d\in\mathbbm{N}$ and a polynomial $P$ , the $d$ -rank of $P$ , denoted as $rank_{d}\left(P\right)$ is defined to be the smallest integer ${{r}}$ such that $P$ can be computed given ${{r}}$ polynomials of degree $<d$ . In other wards, we say $rank_{d}\left(P\right)={{r}}$ if ${{r}}$ is the smallest integer such that there exists ${{r}}$ polynomials $Q_{1},...,Q_{{r}}\in Poly_{\leq d-1}(\mathbbm{F}^{n}\rightarrow\mathbbm{F})$ and a function $\Gamma:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ such that:

P(x)=\Gamma\left(Q_{1}(x),...,Q_{{r}}(x)\right)

If $d=1$ , then $1$ -rank is defined to be $\infty$ if $P$ is non constant, and $0$ otherwise.
Moreover, for a polynomial $P$ of degree $\deg(P)=d$ we denote $rank\left(P\right)\coloneqq rank_{d}\left(P\right)$ .
We call such function $\Gamma$ a decomposition or a computation of $P$ using lower-degree polynomials.

Let us now define a factor. Note that we focus our discussion to factors in $\mathbbm{F}^{n}$ , but define the basic definitions over a general set $U$ so they will apply for factors over a general sets. This is necessary as we will later use them also for other sets such as ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .

Definition 20 (Factor).

Let $U\subseteq\mathbbm{F}^{n}$ be a set. Let $F_{1},...,F_{c}:U\rightarrow\mathbbm{F}$ be a collection of functions. A factor defined by $\mathcal{B}_{F_{1},...,F_{c}}$ over $U$ is the map:

\mathcal{B}_{F_{1},...,F_{c}}(u)\rightarrow(F_{1}(u),...,F_{c}(u))

By an abuse of notation, we also use $\mathcal{B}$ to denote the partition of the set $U$ defined by the map. We call each subset in the partition is an atom:

\left\{u\in U\middle|F_{1}(u)=b_{1},...,F_{c}(u)=b_{c}\right\}

for all $b_{1},...,b_{c}\in\mathbbm{F}$ . By an abuse of notation, $\mathcal{B}$ sometimes refers to the set of all atoms (which is a partition of $U$ ).

Notation.

Let $F_{1},...,F_{c}:U\rightarrow\mathbbm{F}$ be a collection of functions. For a factor $\mathcal{B}\coloneqq\mathcal{B}_{F_{1},...,F_{c}}$ , we denote by $\left|\mathcal{B}\right|$ the amount of functions that define it, i.e. $\left|\mathcal{B}\right|=c$ . Moreover, we denote $\left\lVert{\mathcal{B}}\right\rVert\coloneqq\left|\mathbbm{F}\right|^{c}$ , which is the maximal amount of (possibly empty) atoms.

Definition 21 (Polynomial Factor).

We say a factor $\mathcal{B}$ over $\mathbbm{F}^{n}$ is a polynomial factor if it is defined by a collection of polynomials $P_{1},...,P_{c}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ , i.e. $\mathcal{B}=\mathcal{B}_{P_{1},...,P_{c}}$ . The degree of the factor, denote as $\deg(\mathcal{B})$ is the maximal degree of the polynomials $P_{1},...,P_{c}$ .

$\blacktriangleright$ Note.

We emphasize that every function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is a polynomial function for some degree, thus the phrase “polynomial factor“ is used to emphasize that there is a degree bound on the functions defining the factor. Also note that the notion of degree (and polynomial) are defined only for functions over $\mathbbm{F}^{n}$ , therefore this definition is well-defined only for $U=\mathbbm{F}^{n}$ .

Definition 22 (Rank of a Factor).

Let $\mathcal{P}$ be a collection of polynomials $P_{1},...,P_{c}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ . The rank of the polynomial collection is defined as:

rank\left(\mathcal{P}\right)\coloneqq\min\left\{rank_{d}\left(\sum_{i=1}^{c}{% \lambda_{i}P_{i}}\right)\middle|0\neq\vec{\lambda}\in\mathbbm{F}^{c},d=\max_{i% \in\left[c\right]}{\deg(\lambda_{i}P_{i})}\right\}

For a factor $\mathcal{B}$ defined by a collection of polynomials $\mathcal{P}$ , we define its rank to be the rank of the collection of polynomials defining it. For a non-decreasing function ${{{r}}}:\mathbbm{N}\rightarrow\mathbbm{N}$ , a factor $\mathcal{B}$ is called ${{{r}}}$ -regular if its rank is at least ${{{r}}}(\left|\mathcal{B}\right|)$ .

$\blacktriangleright$ Note.

Note that in the definition above, the rank of each linear combination is calculated as the $d$ -rank, where $d$ is the maximal degree of a polynomial that participates in the linear combination non-trivially. This is crucial as it ensures that a high rank factor do not have linear dependence in the largest-degree homogenous component of any of its polynomials.

We now present a fundamental property of high rank polynomials, that was first proved by [28] when $d<\left|\mathbbm{F}\right|$ , later extended to general fields by [33], and further extended also to large fields by [9]. This property of high rank polynomials is that they have low bias:

Theorem 23 (Rank-bias in $\mathbbm{F}^{n}$ ).

Let $\mathbbm{F}$ be a finite field. Let $\epsilon>0$ and $d\in\mathbbm{N}$ . There exists $r_{\ref{high-rank-implies-low-bias}}\coloneqq r_{\ref{high-rank-implies-low-% bias}}(\mathbbm{F},d,\epsilon)$ , such that for every degree- $d$ polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ : if $rank\left(P\right)\geq r_{\ref{high-rank-implies-low-bias}}$ then $bias({P})<\epsilon$ .

$\blacktriangleright$ Remark 24.

This property implies that a collection of polynomials that have high rank is equidistributed. See Appendix A for more details in this regard.

2.4 Regularization in $\mathbbm{F}^{n}$

In this subsection we define the regularization process in $\mathbbm{F}^{n}$ . Before doing so, let us present some definitions in this regard. Note that we define the basic definitions over a general set $U$ so they will apply for factors over a general sets, as this is necessary as we will later use them also for other sets such as ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .

Definition 25 (Measureable).

Let $U$ be a set, and let $A\subseteq U$ . Let $\mathfrak{F}=\left\{F_{1},...,F_{c}\right\}$ be a collection of functions $F_{i}:U\rightarrow\mathbbm{F}$ . We say a function $G:U\rightarrow\mathbbm{F}$ is measurable in respect of $\mathfrak{F}$ in $A$ , shorthand by $\mathfrak{F}$ -measurable in $A$ , if there exists a function $\Gamma:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ such that:

\forall a\in A:g(a)=\Gamma(F_{1}(a),...,F_{c}(a))

When discussing the factor over $A$ defined by $\mathcal{B}=\mathcal{B}_{F_{1},...,F_{c}}$ , we also say $G$ is measurable in resepct of $\mathcal{B}$ . The function $\Gamma$ will be denoted as the measurement function of $G$ in respect of $\mathfrak{F}$ . Additionally, when $A=U$ , we sometimes omit the specification of the domain, and say $G$ is measurable in respect of $\mathfrak{F}$ .
Note that in this paper, we usually think of $U=\mathbbm{F}^{n}$ , and $A$ is either $\mathbbm{F}^{n}$ or ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .

$\blacktriangleright$ Remark 26.

If $G$ is $\mathfrak{F}$ -measurable in $A$ , then every value of $G$ in $A$ can be determined by the values of $F_{1},...,F_{c}$ . In other words, the function $G$ is constant inside every atom of the factor defined by $\mathfrak{F}$ .

Definition 27 (Syntactic Refinement).

Let $\mathcal{B}$ and $\mathcal{B}^{\prime}$ be polynomial factors over $U\subseteq\mathbbm{F}^{n}$ . We say a factor $\mathcal{B}^{\prime}$ is a syntactic refinement of the factor $\mathcal{B}$ , if the collection of functions defining $\mathcal{B}$ is a subset of the set of functions defining $\mathcal{B}^{\prime}$ . We denote this property of $\mathcal{B}^{\prime}$ by $\mathcal{B}^{\prime}\succeq_{\text{syn}}\mathcal{B}$ .

We now present a standard generalized definition of refinement, where we only require the atoms induced by the refined factors are sub-atoms of those that are induced by the original factor. Note that in this refinement, we allow the refined factor to include completely different polynomials than the original factor.

Definition 28 (Semantic Refinement).

Let $\mathcal{B}$ and $\mathcal{B}^{\prime}$ be polynomial factors on $U$ defined by $\mathcal{P}$ and $\mathcal{P}^{\prime}$ respectively. We say the factor $\mathcal{B}^{\prime}$ is a semantic refinement of the factor $\mathcal{B}$ in $A\subseteq U$ , if $x,y\in A$ with $\mathcal{B}^{\prime}(x)=\mathcal{B}^{\prime}(y)$ implies that $\mathcal{B}(x)=\mathcal{B}(y)$ . We denote this property of $\mathcal{B}^{\prime}$ by $\mathcal{B}^{\prime}\succeq_{\text{sem}|A}\mathcal{B}$ . When $A=U$ , we sometimes omit $A$ from the syntax and denote it with $\mathcal{B}^{\prime}\succeq_{\text{sem}}\mathcal{B}$
Note that $\mathcal{B}^{\prime}\succeq_{\text{syn}}\mathcal{B}$ implies $\mathcal{B}^{\prime}\succeq_{\text{sem}|A}\mathcal{B}$ for every $A\subseteq U$ .

$\blacktriangleright$ Remark 29.

A handy property of semantic refinement is that if $F:A\rightarrow\mathbbm{F}$ is $\mathcal{P}$ -measurable, then it is also $\mathcal{P}^{\prime}$ -measurable in $A$ . Moreover, the other direction is also true: If every $\mathcal{P}$ -measurable function $F:A\rightarrow\mathbbm{F}$ in $A$ is also $\mathcal{P}^{\prime}$ -measurable in $A$ , then $\mathcal{B}^{\prime}\succeq_{\text{sem}|A}\mathcal{B}$ .

Next, we recall a lemma that was presented in [7, Theorem 4.1], that allows us, given a polynomial that is measurable by a high rank factor in $\mathbbm{F}^{n}$ , to replace the polynomials in the measurement function to any collection of polynomials with smaller or equal degree, and preserve the degree of the original polynomial. Note that we state the lemma under the constraint that $d<\left|\mathbbm{F}\right|$ , but it is also valid for when $d\geq\left|\mathbbm{F}\right|$ with proper generalization of definitions to this case (See [7, Theorem 4.1] for the exact statement).

Lemma 30 (Preserving Degree in $\mathbbm{F}^{n}$ ).

Let $d>0$ an integer such that $d<\left|\mathbbm{F}\right|$ , and let $P_{1},...,P_{c}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ be polynomials of degree at most $d$ , that form a factor of rank $\geq{{{r}}}^{\ref{preserving-degree-starting-field}}(\mathbbm{F},d,c)$ . Assume that for $\Gamma:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ , the function $\gamma:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ defined as $\gamma(a)\coloneqq\Gamma(P_{1}(a),...,P_{c}(a))$ is of $\deg(\gamma)=d^{\prime}$ .
Then, for every collection of polynomials $Q_{1},...,Q_{c}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ that satisfy $\deg(Q_{i})\leq\deg(P_{i})$ , the function $\gamma^{\prime}$ defined as $\gamma^{\prime}(a)=\Gamma(Q_{1}(a),...,Q_{c}(a))$ is a polynomial of $\deg(\gamma^{\prime})\leq d^{\prime}$ .

Next, we restate a useful lemma from [9, Lemma 4.17] that shows that under the conditions above, $\Gamma$ is as a low-degree polynomial (with even stronger conditions). Formally, they showed:

Lemma 31 (Faithful Composition).

In the case discussed above, the structure of $\Gamma$ is as follows:

\Gamma(z_{1},...,z_{c})=\sum_{\alpha\in\left[p-1\right]^{c}}{{C_{\alpha}}\cdot% {\prod_{i=1}^{c}}{z_{i}^{\alpha_{i}}}}

where $C_{\alpha}=0$ whenever $\sum_{i=1}^{c}(\alpha_{i}\cdot\deg(P_{i}))>d^{\prime}$ .
In other words, this means that $\Gamma$ as a function $\Gamma:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ , is a polynomial of degree $\leq d^{\prime}$ , even when substituting its $i$ -th input by any polynomial of degree $\leq\deg(P_{i})$ .

Next, we restate the regularization process, that was first presented by [28, Lemma 2.3], with the second part of the lemma presented in [28, Lemma 9.3] (a statement the combines the two can be found [32, Lemma 7.29]).
We begin with a definition:

Definition 32.

Let $\mathcal{P}=(P_{1},...,P_{c})$ be a collection of polynomials of degree $\leq d$ that defines a factor $\mathcal{B}$ . Define $M(\mathcal{B})\coloneqq(M_{d},...,M_{1})\in\mathbbm{N}^{d}$ , where $M_{i}$ denotes the number of polynomials in $\mathcal{P}$ that have degree exactly $i$ . Thus, $\sum_{i=1}^{d}M_{i}=c$ .
We define the lexicographical order on $\mathbbm{N}^{d}$ where $M>M^{\prime}$ if and only if $M_{i}>M^{\prime}_{i}$ for some $1\leq i\leq d$ , and $M_{j}=M^{\prime}_{j}$ for all $j>i$ .

The regularization process shows that every factor have a high-rank factor that semantically refines it, without increasing the size of the factor too much (its new size is independent of $n$ ).

Lemma 33 (Regularization in $\mathbbm{F}^{n}$ ).

Let ${{{r}}}:\mathbbm{N}\rightarrow\mathbbm{N}$ be a non-decreasing function and let $d\in\mathbbm{N}$ . There exists $C_{{{{r}}},d}^{\ref{regularization-in-Fn-lemma}}:\mathbbm{N}\rightarrow% \mathbbm{N}$ such that the following holds: Let $\mathcal{B}$ be a factor on $\mathbbm{F}^{n}$ defined by polynomials $\mathcal{P}=(P_{1},...,P_{c})$ where for all $i\in[c]$ : $P_{i}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ and $\deg(P_{i})\leq d$ Then, there is an ${{{r}}}$ -regular factor $\mathcal{B}^{\prime}$ defined by polynomials $\mathcal{Q}=(Q_{1},...,Q_{c^{\prime}})$ where for all $i\in[c^{\prime}]$ : $Q_{i}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ such that $\mathcal{B}^{\prime}\succeq_{\text{sem}}\mathcal{B}$ , $M(\mathcal{B}^{\prime})\leq M(\mathcal{B})$ and $c^{\prime}\leq C_{{{{r}}},d}^{\ref{regularization-in-Fn-lemma}}(c)$ .
Moreover, if $\mathcal{B}\succeq_{\text{syn}}\bar{\mathcal{B}}$ for some polynomial factor $\bar{\mathcal{B}}$ with rank at least ${{{r}}}(c^{\prime})+c^{\prime}+1$ , then we can require that $\mathcal{B}^{\prime}\succeq_{\text{syn}}\bar{\mathcal{B}}$ .

$\blacktriangleright$ Note.

Note that in the definitions above implicitly assume there are no constants in the collections of polynomials we discuss (no polynomials of degree $0$ ). This is a valid assumption as we are interested in the set of functions that are measurable in respect to the collections, and this property is unaffected by constant polynomials in the collection. Therefore, we can always assume there are no such polynomials in any collection we consider in this context.

3 Polynomials in ${\tilde{X}}$

In this section we wish to generalize the definition of degree- $d$ polynomials for functions $f:{\tilde{X}}\rightarrow\mathbbm{F}$ . Note that we wish to define it using a property of $f$ that is intrinsic to ${\tilde{X}}$ : given a function $f:{\tilde{X}}\rightarrow\mathbbm{F}$ , we wish be able to determine its degree only using values of ${\tilde{X}}$ , without considering any value outside of ${\tilde{X}}$ (such as values of $\mathbbm{F}^{n}\setminus{\tilde{X}}$ ).
To define such property, we generalize the local definition of a degree that is defined for polynomials in $\mathbbm{F}^{n}$ . We remind the reader that in $\mathbbm{F}^{n}$ , we said a function over $\mathbbm{F}^{n}$ is a polynomial of degree $\leq d$ if and only if its $(d+1)$ -derivative in every direction is $\equiv 0$ . Thus, in order to determine the $(d+1)$ -derivative of a function in directions $y_{1},...,y_{d+1}$ , one needs to evaluate the function over all the points of the cube generated by $x,y_{1},...,y_{d+1}$ , which is the set of points $\left\{x+\sum_{i\in S}{y_{i}}\right\}_{S\subseteq[d+1]}$ . This raises a challnge in extending this definition for functions defined over ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ : depending on ${\tilde{X}}$ , the function $f:{\tilde{X}}\rightarrow\mathbbm{F}$ is not be defined to all points in all the cubes of $\mathbbm{F}^{n}$ , because some of those points do not lie in ${\tilde{X}}$ .
Therefore, to generalize the definition of a polynomial to ${\tilde{X}}$ , we start by giving the formal definition and notation of the set of cubes in ${\tilde{X}}$ :

Definition 34 (Cubes).

Let $k\in\mathbbm{N}$ be an integer and let $x,y_{1},...,y_{k}\in\mathbbm{F}^{n}$ . We define the cube $(x|y_{1},...y_{k})$ as follows:

(x|y_{1},...,y_{k})\coloneqq\left\{x+\sum_{i\in S}{y_{i}}\right\}_{S\subseteq[% k]}

We refer to $x$ as the offset of the cube, and $y_{1},...,y_{k}$ as the directions of the cube.
Moreover, let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a subset. We define the set of cubes of ${\tilde{X}}$ of size $k$ as follows:

C_{k}({\tilde{X}})\coloneqq\left\{(x|y_{1},...,y_{k})\middle|\forall S% \subseteq[k]:(x+\sum_{i\in S}{y_{i}})\in{\tilde{X}}\right\}

Using this definition, we can define a polynomial of degree $\leq d$ for subsets of $\mathbbm{F}^{n}$ :

Definition 35 (Polynomials in ${\tilde{X}}$ ).

Let $d\in\mathbbm{N}$ be an integer, and let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ . We say the degree of a function $f:{\tilde{X}}\rightarrow\mathbbm{F}$ is $d$ if $d$ is the smallest integer such that $f$ vanishes over all cubes of size $(d+1)$ , i.e:

\forall{(x|y_{1},...,y_{d+1})\in C_{d+1}({\tilde{X}})}:D_{y_{d+1}}...D_{y_{1}}% p(x)=0

A function over ${\tilde{X}}$ of degree $\leq d$ is also called a polynomial of degree $\leq d$ over ${\tilde{X}}$ . We sometimes also refer to such functions as polynomials in ${\tilde{X}}$ , and use the two interchangeably. We denote the set of polynomials of degree $\leq d$ over ${\tilde{X}}$ by $Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ .

$\blacktriangleright$ Note.

For ${\tilde{X}}=\mathbbm{F}^{n}$ , the definition above coincides with the local definition of polynomials.

3.1 Lifting Polynomials

Our goal to achieve good properties for polynomials over ${\tilde{X}}$ . To do so, we wish to connect the desired properties of polynomials defined over ${\tilde{X}}$ , to properties known for polynomials over $\mathbbm{F}^{n}$ . Following such strategy raises a question: given a polynomial $p:{\tilde{X}}\rightarrow\mathbbm{F}$ , which polynomial over $\mathbbm{F}^{n}$ should we consider to deduce properties of $p$ ? To find such a polynomial over $\mathbbm{F}^{n}$ , it would have been useful that all polynomials over ${\tilde{X}}$ actually “came from“ polynomials over $\mathbbm{F}^{n}$ . More formally, it would have been useful that all polynomials $p:{\tilde{X}}\rightarrow\mathbbm{F}$ would be equal to a restriction of some polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ of degree $\leq d$ , to the set ${\tilde{X}}$ . This would give us a “good candidate“ (or candidates) to polynomials over $\mathbbm{F}^{n}$ , that using their known properties, we could achieve the properties we desire for polynomials over ${\tilde{X}}$ .
Generally speaking, the existence of such polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is not trivial by itself, and it mapy depend on the polynomial $p$ and the set ${\tilde{X}}$ . In this subsection, we discuss sets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ that have this property for every polynomial $p:{\tilde{X}}\rightarrow\mathbbm{F}$ . Before formulating the notion above, we start by a simple remark:

$\blacktriangleright$ Remark 36.

By the local criteria for $\mathbbm{F}^{n}$ , we have that a restriction of a polynomial of degree $\leq d$ over $\mathbbm{F}^{n}$ to ${\tilde{X}}$ is a polynomial of degree $\leq d$ over ${\tilde{X}}$ . Therefore, the other direction is true: every restriction of a polynomial over $\mathbbm{F}^{n}$ to ${\tilde{X}}$ is a polynomial over ${\tilde{X}}$ .

Next, let us define subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ that have the desired property, which we call $d$ -lift-enabler variety.

Definition 37 ( $d$ -lift-enabler Subset).

Let $\mathbbm{F}$ be a field, and $n>0$ be an integer. For an integer $d>0$ , we say a subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ is $d$ -lift-enabler if for every $d^{\prime}\leq d$ , for every polynomial $p\in Poly_{d^{\prime}}({\tilde{X}}\rightarrow\mathbbm{F})$ there exist a polynomial $\widehat{p}\in Poly_{d^{\prime}}(\mathbbm{F}^{n}\rightarrow\mathbbm{F})$ such that $p|_{{\tilde{X}}}=\widehat{p}|_{{\tilde{X}}}$ .

$\blacktriangleright$ Remark 38.

Using the local criterion of polynomials and the fact that that $C_{d+1}({\tilde{X}})\subseteq C_{d+1}(\mathbbm{F}^{n})$ , one can see that for a polynomial $p:{\tilde{X}}\rightarrow\mathbbm{F}$ with $\deg(p)=d$ , every extension $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ with $p=P|_{{\tilde{X}}}$ holds the bound $\deg(\widehat{p})\geq d$ . The other direction is not true in the general case, but it is specifically promised when the variety is $d$ -lift-enabler.

This definition naturally raises the following definition:

Definition 39 (The Lift Operator).

Let $d\in\mathbbm{N}$ be an integer. Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a $d$ -lift-enabler subset. We define the $d$ -lift operator to be an operator $\widehat{\square}:Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})\rightarrow Poly% _{\leq d}(\mathbbm{F}^{n}\rightarrow\mathbbm{F})$ the following way:
Let $d^{\prime}\leq d$ . Given a polynomial $p:{\tilde{X}}\rightarrow\mathbbm{F}$ of degree $d^{\prime}$ , the operator $\widehat{\square}$ returns a polynomial $\widehat{p}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ of degree $d^{\prime}$ such that $p=\widehat{p}|_{{\tilde{X}}}$ . Note that we did not require the lift to be unique. Thus, in case there are multiple valid lifts for a polynomial $p\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ , the lift operator picks a single (consistent) one of them. Moreover, the lift always exists because the subset ${\tilde{X}}$ is $d$ -lift-enabler.
In addition, for a collection $\mathfrak{p}=(p_{1},...,p_{c})$ of polynomials $p_{i}\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ , we denote $\widehat{\mathfrak{p}}\coloneqq(\widehat{p_{1}},...,\widehat{p_{c}})$

In the following subsections, we give example to two concrete sets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ that are $d$ -lift-enablers. Before doing so, we define an algebraic variety:

Definition 40 (Algebraic Variety).

For a collection of functions $\mathfrak{F}\coloneqq\left\{F_{1},...F_{c}\right\}$ such that $F_{i}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ , we denote $Z\left(\mathfrak{F}\right)\coloneqq\left\{x\in\mathbbm{F}^{n}\middle|\forall i% :F_{i}(x)=0\right\}$ .
If the collection is a collection of polynomials, we call $Z\left(\mathfrak{F}\right)$ an algebraic variety, shorthand by variety.
The degree of the variety which is a complete intersection is the product of the degrees of the polynomials in the collection that defines it.

3.2 High Rank Varieties of High Minimal Degree

We now present a theorem proved in [34, Corollary 1.10], that shows that high rank varieties are $d$ -lift-enabler when the polynomials defining the variety are of degree $>d$ :

Theorem 41.

Let $\mathbbm{F}$ be a finite field, and let $\tilde{d}$ , ${\tilde{c}}>0$ representing parameters of a variety. Let $d<\tilde{d}$ a positive integer representing a degree of a polynomial which we wish to lift. There exists ${\bar{r}}={\bar{r}}(\mathbbm{F},\tilde{d},{\tilde{c}})>0$ such that for all $n\in\mathbbm{N}$ , any variety ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)\subseteq\mathbbm{F}^{n}$ for $\tilde{\mathcal{L}}=(L_{1},...,L_{{\tilde{c}}})$ which is a complete intersection such that $rank\left(\tilde{\mathcal{L}}\right)>{\bar{r}}$ ²⁹²⁹29The definition of rank used in thier proof is slightly different than our definition of rank. This is addressed in Appendix B. , degree $\deg(\tilde{\mathcal{L}})=\tilde{d}$ , with all defining polynomials of degree $\deg(L_{i})>d$ , it holds that ${\tilde{X}}$ is a $d$ -lift-enabler subset.

$\blacktriangleright$ Remark 42.

Under the conditions stated above, it was proved in [34] that the lift is in fact unique. Formally, if $p:{\tilde{X}}\rightarrow\mathbbm{F}$ is a polynomial of degree $\leq d$ , then there exists a unique polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ such that $P|_{{\tilde{X}}}\equiv p$ .

3.3 High Rank Varieties on a Large Field

In this subsection, we recall a theorem proved by [35, Theorem 1.7] regarding high rank varieties that are defined on “large” fields. We note that the fields are large in respect of the degree $d$ one wish to lift, but still does not depend on $n$ .

Next we define a weakly polynomial, which generalizes our definition of a polynomial in ${\tilde{X}}$ , that was used in [35, Definition 1.1]:

Definition 43.

Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a set. We say a function $F:{\tilde{X}}\rightarrow\mathbbm{F}$ is a weakly polynomial of degree $\leq d$ if for any affine subspace $L\subseteq{\tilde{X}}$ , the restriction $F|_{L}$ is a polynomial of degree $\leq d$ .

$\blacktriangleright$ Remark 44.

By the local criteria of a polynomial, it is easy to see that every $P\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ is a weakly polynomial of degree $\leq d$ .

And now, we can present the lifting theorem for large fields, as proved in [36, Theorem 2.17].

Theorem 45 ([36, Theorem 2.17]).

Let $d,\tilde{d}\in\mathbbm{N}$ , and let $\mathbbm{F}$ be a finite field such that $\left|\mathbbm{F}\right|>d\cdot\tilde{d}$ . There exists ${{{r}}}_{\ref{high-rank-varieties-over-large-fields-are-d-lift-enablers}}={{{r% }}}_{\ref{high-rank-varieties-over-large-fields-are-d-lift-enablers}}(\tilde{d% },d)$ such that for any variety ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ of degree $\leq\tilde{d}$ which is a complete intersection, defined by a collection of polynomials with rank ³⁰³⁰30The definition of rank used in thier proof is slightly different than our definition of rank. This is addressed in Appendix B. $\geq{{{r}}}_{\ref{high-rank-varieties-over-large-fields-are-d-lift-enablers}}$ , have the following property: Every weakly polynomial function $p:{\tilde{X}}\rightarrow\mathbbm{F}$ of degree $\leq d$ can be lifted to a polynomial function $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ of degree $\leq d$ .

$\blacktriangleright$ Note.

Note that we stated the theorem above to finite fields, but it is also valid for infinite algebraically closed fields.

The theorem above implies the following corollary:

Corollary 46.

Let $d,\tilde{d}\in\mathbbm{N}$ , and let $\mathbbm{F}$ be a finite field such that $\left|\mathbbm{F}\right|>d\cdot\tilde{d}$ . There exists ${{{r}}}_{\ref{high-rank-varieties-over-large-fields-are-d-lift-enablers}}={{{r% }}}_{\ref{high-rank-varieties-over-large-fields-are-d-lift-enablers}}(\tilde{d% },d)$ such that for any variety ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ of degree $\tilde{d}$ and rank $\geq{{{r}}}_{\ref{high-rank-varieties-over-large-fields-are-d-lift-enablers}}$ is a $d$ -lift-enabler.

4 Relative Rank-Bias Property

In this section, we generalize the relation between rank and bias that is known for $\mathbbm{F}^{n}$ also for ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ . Specifically, in Theorem 23, it was shown that high rank factors have low bias in $\mathbbm{F}^{n}$ . We wish to define an alternative definition of rank for ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , called ${\tilde{X}}$ -relative rank, such that high ${\tilde{X}}$ -relative rank implies low bias in ${\tilde{X}}$ . This type of relation (and definition) was shown previously to a few sets; in [37, Theorem 1.8] for sets ${\tilde{X}}=Z\left(\mathcal{Q}\right)$ where $\mathcal{Q}$ is a collection of polynomials of high rank; and in [27, Theorem 1.4] for sets ${\tilde{X}}=S^{n}$ for $S\subset\mathbbm{F}$ .

To understand this notion, we first introduce a simple example that demonstrates the need for a different definition of rank to achieve equidistribution properties in subsets of $\mathbbm{F}^{n}$ .

Example 47.

Let ${\tilde{X}}=\left\{x\in\mathbbm{F}^{n}\middle|x_{1}=0\right\}$ . Define $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ by $P(x)\coloneqq x_{1}$ .
In $\mathbbm{F}^{n}$ , $P$ has rank $\infty$ as it can not be decomposed polynomials of degree $<1$ (constants). Additionally, it is perfectly equidistributed. This is the simplest example of the rank-bias relation in $\mathbbm{F}^{n}$ .
However, when restricting $P$ to ${\tilde{X}}$ , we get $P|_{{\tilde{X}}}\equiv 0$ . As $0$ is a constant function, it is the least equidistributed possible in ${\tilde{X}}$ . Therefore, we see that the way we defined rank in $\mathbbm{F}^{n}$ does not imply the desired equidistribution in ${\tilde{X}}$ : we found a polynomial with high rank (infinity) that has a very high bias in ${\tilde{X}}$ (the maximal).

The reason the definition of rank in $\mathbbm{F}^{n}$ fails to capture equidistribution even on subsets that are really similar to $\mathbbm{F}^{n}$ (isomorphic to $\mathbbm{F}^{k}$ ), is because of the following reason: Even though our polynomial $P$ does not have a decomposition to a few lower-degree polynomials by itself, there exists a ${\tilde{X}}$ -equivalent polynomial that has such structured decomposition. Here, by ${\tilde{X}}$ -equivalent we mean a polynomial in $\mathbbm{F}^{n}$ that is bounded by the same degree bound, and is equal to $P$ in ${\tilde{X}}$ . In the example described above, this equivalent polynomial is the constant function $0$ , and its decomposition is the trivial one (any function decomposes a constant function). An alternative perspective which we use throughout this paper to ${\tilde{X}}$ -equivalence is that both polynomials are equal up to a valid ${\tilde{X}}$ -remainder: a bounded degree polynomial that is $\equiv 0$ in ${\tilde{X}}$ .

Generally speaking, high ${\tilde{X}}$ -relative rank may not imply low bias in ${\tilde{X}}$ . Therefore, this structure-randomness relation is not true for a general subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , but is a property of the subset ${\tilde{X}}$ . Thus, we say that a subset has the relative rank-bias property if this relation holds, i.e. if high ${\tilde{X}}$ -relative rank implies equidistribution in ${\tilde{X}}$ .

Let us now formally define our definition for relative rank, inspired by the two different definitions of relative rank presented in [37, Definition 1.6] and in [27, Definition 1.3]:

Definition 48 (Relative Rank of a Polynomial).

Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ and let $d\in\mathbbm{N}$ . For an integer $d\in\mathbbm{N}$ and a polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ , we define its $d$ -relative rank in respect of ${\tilde{X}}$ as:

rank_{{d},{{\tilde{X}}}}\left(P\right)\coloneqq\min\left\{rank_{d}\left(P-% \overline{Pmissing}\right)\middle|\overline{Pmissing}\in Poly_{\leq\deg(P)}(% \mathbbm{F}^{n}\rightarrow\mathbbm{F}),\overline{Pmissing}|_{{\tilde{X}}}% \equiv 0\right\}

For a polynomial $P$ of degree $\deg(P)=d$ we denote $rank_{{\tilde{X}}}\left(P\right)\coloneqq rank_{{d},{{\tilde{X}}}}\left(P\right)$ .

Definition 49 ( ${\tilde{X}}$ -equivalent and ${\tilde{X}}$ -remainder).

Moreover, we say a polynomial is ${\tilde{X}}$ -equivalent to $P$ if its restriction to ${\tilde{X}}$ is $\equiv P|_{{\tilde{X}}}$ . We say it is valid ${\tilde{X}}$ -equivalent to $P$ if it is ${\tilde{X}}$ -equivalent to $P$ and it is of the same degree of $P$ .
Similarly, we say a polynomial is ${\tilde{X}}$ -remainder if its restriction to ${\tilde{X}}$ is $\equiv 0$ . We say it is valid ${\tilde{X}}$ -remainder $P$ if it is ${\tilde{X}}$ -remainder and it is of degree smaller or equal of the degree of $P$ .
We typically denote such polynomial as $\overline{Pmissing}$ .

In other words, the $d$ -relative rank of a polynomial $P$ is the smallest $d$ -rank of all valid ${\tilde{X}}$ -equivalents of $P$ .

$\blacktriangleright$ Note 50.

Note that [27, Definition 1.3] defines rank in a substantially different way than our definition, and consequentially our results will not apply to the sets they presented. One of the main differences in the definition of rank occurs for $d=1$ . In the definition we use for rank, the rank of every (non-constant) degree- $1$ polynomial is $\infty$ , where in the definition used in [27] it is a finite number (which is possibly very small). This difference is crucial, as for example, it makes regularization according to their definition not-trivially possible, where it is known to be possible when rank is defined by the definition we use (Lemma 33).

Definition 51 (Relative Rank of a Factor).

Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ . Let $\mathcal{P}$ be a set of polynomials $\mathcal{P}=\left\{P_{1},...,P_{c}\right\}$ . The rank of the polynomial set $\mathcal{P}$ relative to the subset ${\tilde{X}}$ is defined as:

rank_{{\tilde{X}}}\left(\mathcal{P}\right)\coloneqq\min\left\{rank_{{d},{{% \tilde{X}}}}\left(\sum_{i=1}^{c}{\lambda_{i}P_{i}}\right)\middle|0\neq\vec{% \lambda}\in\mathbbm{F}^{c},d=\max_{i\in\left[c\right]}{\deg(\lambda_{i}P_{i})}\right\}

For a factor $\mathcal{B}$ defined by a collection of polynomials, we define its relative rank relative to ${\tilde{X}}$ to be the relative rank of the collection of polynomials defining it, relative to the set ${\tilde{X}}$ .
For a non-decreasing function ${{{r}}}:\mathbbm{N}\rightarrow\mathbbm{N}$ , a factor $\mathcal{B}$ is called ${{{r}}}$ - ${\tilde{X}}$ -regular if its relative rank in respect to ${\tilde{X}}$ is at least ${{{r}}}(\left|\mathcal{B}\right|)$ .

4.1 Relative Rank-Bias Property

Definition 52 (Relative Rank-Bias property).

Let $\mathbbm{F}$ be a finite field, and let $d\in\mathbbm{N}$ be an integer. Let ${\tilde{r}}:\mathbbm{R}^{+}\rightarrow\mathbbm{N}$ be a function that represents the rank-bias relation for a fixed $d,\mathbbm{F}$ .
We say a set ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ has the $({\tilde{r}},\mathbbm{F},d)$ -relative rank-bias property if for every $\epsilon>0$ , for every polynomial $P$ of degree $\leq d$ with $rank_{{\tilde{X}}}\left(P\right)\geq{\tilde{r}}(\epsilon)$ we have:

bias_{{\tilde{X}}}{({P})}<\epsilon

As an immediate corollary of Theorem 23 that shows that high rank implies low bias, we have that ${\tilde{X}}=\mathbbm{F}^{n}$ has the relative rank-bias property.

Corollary 53 ( $\mathbbm{F}^{n}$ has the relative rank-bias property).

For every finite field $\mathbbm{F}$ and $d\in\mathbbm{N}$ , let ${\tilde{r}}:\mathbbm{R}^{+}\rightarrow\mathbbm{N}$ defined as ${\tilde{r}}(\epsilon)\coloneqq{{r}}_{\ref{high-rank-implies-low-bias}}(% \mathbbm{F},d,\epsilon)$ . Then, we have that the set ${\tilde{X}}=\mathbbm{F}^{n}$ has the $({\tilde{r}},\mathbbm{F},d)$ -relative rank-bias property.

Proof.

This is a simple usage of Theorem 23: Note that when ${\tilde{X}}=\mathbbm{F}^{n}$ , we have that $rank_{{\tilde{X}}}\left(P\right)=rank\left(P\right)$ . Now, if $P$ is a polynomial of degree $\leq d$ and $rank_{{\tilde{X}}}\left(P\right)=rank\left(P\right)\geq{\tilde{r}}(\epsilon)={% \tilde{r}}_{\ref{high-rank-implies-low-bias}}(\mathbbm{F},d,\epsilon)$ , then:

bias_{x\in\mathbbm{F}^{n}}{({P(x)})}<\epsilon\

$\hfill\blacktriangleleft$

4.2 Limited-Relative Rank-Bias Property

Sometimes, however, we can not request ${\tilde{X}}$ to be such that high relative rank implies low bias for every $\epsilon>0$ , but only for $\epsilon^{\prime}\geq\epsilon$ for some constant $\epsilon>0$ . This leads to defining the limited relative rank-bias property, which will be used to discuss such sets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .
As we will later see, this definition raises naturally where ${\tilde{X}}$ is a high rank variety, in which for the relative rank-bias property to hold for some $\epsilon>0$ , the rank of the variety should be greater than a value that is dependent of $\epsilon$ . Thus, to have the relative rank-bias property for a high rank variety but without requiring an infinitely large rank, we must limit the relative rank-bias property for $\epsilon^{\prime}\geq\epsilon$ We formulate the definition of this property as follows:

Definition 54 (Limited Relative Rank-bias property).

Let $\mathbbm{F}$ be a finite field, let $d\in\mathbbm{N}$ be an integer, and let $\epsilon>0$ be a constant. Let ${\tilde{r}}:[\epsilon,\infty]\rightarrow\mathbbm{N}$ be a function that represents the limited-relative-rank-bias relation.
We say a set ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ has the $({\tilde{r}},\mathbbm{F},d,\epsilon)$ -limited-relative-rank-bias property if for every $\epsilon^{\prime}\geq\epsilon$ , for every polynomial $P$ of degree $\leq d$ with $rank_{{\tilde{X}}}\left(P\right)\geq{\tilde{r}}(\epsilon^{\prime})$ we have:

bias_{{\tilde{X}}}{({P})}<\epsilon^{\prime}

As a convention, we denote by ${\tilde{\epsilon}}$ the $\epsilon$ such that the limited-relative-rank-bias property holds for ${\tilde{X}}$ .

4.2.1 High Rank Varieties

In this subsection, we are discussing specifically ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ that are in the form ${\tilde{X}}=Z\left(\mathcal{Q}\right)$ for a set of polynomials $\mathcal{Q}$ that form a high rank factor. Let us present some known results of the relative rank-bias relation for high rank varieites: In the scenario when we are working relative to ${\tilde{X}}$ , the equivalent for Theorem 23 is also known when we assume $d<char(\mathbbm{F})$ , as shown in [37, Theorem 1.8]:

Theorem 55 (High relative rank implies low bias in high rank varieties).

Let $\mathbbm{F}$ be a finite field and let $0\leq d<char(\mathbbm{F})$ . Let $\epsilon>0$ be a constant, and let ${\tilde{c}}\in\mathbbm{N}$ . There exist ${\bar{r}}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}={\bar{r% }}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}(\mathbbm{F},d,% {\tilde{c}},\epsilon)$ and ${{r}}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}={{r}}^{\ref% {high-relative-schmidt-rank-implies-low-relative-bias}}(\mathbbm{F},d,\epsilon)$ such that the following holds:
Let $\tilde{\mathcal{L}}=(L_{1},...,L_{{\tilde{c}}})$ be a collection of polynomials of degrees $\leq d$ with $rank\left(\tilde{\mathcal{L}}\right)\geq{\bar{r}}^{\ref{high-relative-schmidt-% rank-implies-low-relative-bias}}$ and let $P$ be a polynomial of degree $\leq d$ .
Then, if $rank_{{\tilde{X}}}\left(P\right)\geq{{r}}^{\ref{high-relative-schmidt-rank-% implies-low-relative-bias}}$ , we have:

bias_{{\tilde{X}}}{({P})}<\epsilon

$\blacktriangleright$ Note.

Note that the original statements in [37] are stated for a different definition of rank, noted as schmidt rank. In the appendix B we compare the two different definitions, and show that our definition of rank is comprehensive enough in a sense that a polynomial with high rank also has high schmidt rank. Additionally, we show that for a given ${{r}}\in\mathbbm{N}$ , the lower bound of rank required for a polynomial to be of schmidt rank $\geq{{r}}$ , is only $c\cdot{{r}}$ for some constant $c\in\mathbbm{N}$ .

$\blacktriangleright$ Remark 56.

Note that in the original statement of theorem 55 as stated in [37, Theorem 1.8], there are good bounds on the rank needed for $\tilde{\mathcal{L}}$ and $P$ for the theorem to hold.
Specifically, there exist constants $A(d),B(d)$ such that for an error $\epsilon=\left|\mathbbm{F}^{-s}\right|$ , if ${\bar{r}}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}=A({% \tilde{c}}+s)^{B}$ and ${{r}}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}=A(1+s)^{B}$ , then we have:

bias_{Z\left(\tilde{\mathcal{L}}\right)}{({P})}<\left|\mathbbm{F}\right|^{-s}

In our proof, it is enough that the bounds on ${{r}}$ and ${\bar{r}}$ are independent of $n$ , thus we omit the exact bounds stated above and use the statement as stated in Theroem 55.

$\blacktriangleright$ Remark 57.

Note that both ${{r}}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}(\mathbbm{F}% ,d,\epsilon)$ and ${\bar{r}}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}(% \mathbbm{F},d,{\tilde{c}},\epsilon)$ are decreasing when $\epsilon$ is increasing. This means for example, that for all $\epsilon^{\prime}\geq\epsilon$ , a variety that satisfies the theorem’s rank condition for $\epsilon$ also satisfies the theorem’s rank condition for $\epsilon^{\prime}$ . Therefore, a polynomial with rank $\geq{{r}}^{\ref{high-relative-schmidt-rank-implies-low-relative-bias}}(% \mathbbm{F},d,\epsilon)$ will have a bias $<\epsilon^{\prime}$ .

As a corollary of Theorem 55 and Remark 88, we have that high rank varieties has the limited-relative-rank-bias property. Formally, we have:

Corollary 58 (High Rank Varieties Have the Limited-Relative Rank-Bias Property).

Let $\mathbbm{F}$ be a finite field, and let $\tilde{d}\in\mathbbm{N}$ such that $0<\tilde{d}<\left|\mathbbm{F}\right|$ . Let ${\tilde{\epsilon}}>0$ be a constant which represents the desired relative rank-bias limit. There exists ${\tilde{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-property}}:% [{\tilde{\epsilon}},\infty]\rightarrow\mathbbm{N}$ with ${\tilde{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-property}}% \coloneqq{\tilde{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-% property}}(\mathbbm{F},\tilde{d})$ such that the following holds:
Let ${\tilde{c}}\in\mathbbm{N}$ be an integer. There exists ${\bar{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-property}}% \coloneqq{\bar{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-% property}}(\mathbbm{F},\tilde{d},{\tilde{c}},{\tilde{\epsilon}})$ such that for every $\tilde{\mathcal{L}}=(L_{1},...,L_{{\tilde{c}}})$ collection of polynomials with $rank\left(\tilde{\mathcal{L}}\right)\geq{\bar{r}}$ , defining a variety ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)$ of degree $\leq\tilde{d}$ which is a complete intersection, we have:
The variety ${\tilde{X}}$ has the $({\tilde{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-property}}% ,\mathbbm{F},\tilde{d},{\tilde{\epsilon}})$ -limited-relative-rank-bias property.

Proof.

Let $\mathbbm{F}$ be a finite field, and let $\tilde{d}\in\mathbbm{N}$ such that $0<\tilde{d}<\left|\mathbbm{F}\right|$ . Let ${\tilde{\epsilon}}>0$ . We choose:

{\tilde{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-property}}(% \epsilon)\coloneqq{{r}}_{\ref{high-relative-schmidt-rank-implies-low-relative-% bias}}(\mathbbm{F},\tilde{d},\epsilon)

Note that for every $\epsilon$ in its domain, ${\tilde{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-property}}$ does not depend on ${\tilde{\epsilon}}$ . Let ${\tilde{c}}\in\mathbbm{N}$ . Now, we choose:

{\bar{r}}_{\ref{high-rank-variety-has-limited-rank-relative-bias-property}}(% \mathbbm{F},\tilde{d},{\tilde{c}},{\tilde{\epsilon}})\coloneqq{\bar{r}}_{\ref{% high-relative-schmidt-rank-implies-low-relative-bias}}(\mathbbm{F},\tilde{d},{% \tilde{c}},{\tilde{\epsilon}})

Using Theorem 55 that shows high rank implies low bias in ${\tilde{X}}$ , and the assumption that $\epsilon\geq{\tilde{\epsilon}}$ (specifically Remark 57) concludes the proof. $\hfill\blacktriangleleft$

5 Regularization Relative to ${\tilde{X}}$

In this section, we generalize the definitions and statements regarding factors and regularization in $\mathbbm{F}^{n}$ , to their corresponding definitions and statements to relative rank in respect of ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .
Note that in oppose to the previous chapter that we discussed a general $U$ and $A\subseteq U$ , in this chapter we discuss only $U=A=\mathbbm{F}^{n}$ . This is done for clearance and to avoid defining definitions we will not use in our main proof.

Definition 59 (Measurable Relative to ${\tilde{X}}$ ).

Let $\mathfrak{F}=\left\{F_{1},...,F_{c}\right\}$ be a set of functions $F_{i}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ . We say a function $G:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ is measurable in respect of $\mathfrak{F}$ relative to ${\tilde{X}}$ , or ${\tilde{X}}$ -relative $\mathfrak{F}$ -measurable, if there exists a function $\overline{G}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ with $\overline{G}|_{{\tilde{X}}}\equiv 0$ and a function $\Gamma:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ such that:

\forall a\in\mathbbm{F}^{n}:G(a)=\Gamma(F_{1}(a),...,F_{c}(a))+\overline{G}(a)

And:

\deg(G-\overline{G})\leq\deg(G)

We sometimes refer to $\Gamma$ as the ${\tilde{X}}$ -relative measurement function.

$\blacktriangleright$ Note.

Note that if $\deg(G-\overline{G})\leq\deg(G)$ as discussed above, then the same bound also bounds the degree of the remainder, i.e. $\deg(\overline{G})\leq\deg(G)$ . Therefore $\overline{G}$ is a valid ${\tilde{X}}$ -remainder of $G$ . Moreover, this requirement is equivalent to the definition above, as if $\deg(\overline{G})\leq\deg(G)$ , then we also have $\deg(G-\overline{G})\leq\deg(G)$ .

$\blacktriangleright$ Note.

Also note that without the bound on the degree of the remainder, being measurable relative to ${\tilde{X}}$ is in fact equivalent for being a measurable in $A={\tilde{X}}$ . This is true because under these conditions, the remainder $\overline{G}$ has no constraints but $\overline{G}|_{{\tilde{X}}}\equiv 0$ , thus the condition left on the measurement is just being a measurement to $G$ in ${\tilde{X}}$ .

$\blacktriangleright$ Remark 60.

If $G$ is a function that it is $\mathfrak{F}$ -measurable relative to ${\tilde{X}}$ , then every value of $G$ can be determined by the values of $F_{1},...,F_{c}$ up to a remainder $\overline{G}$ of degree $\leq d$ . Thus, perhaps we do not know that the function $G$ is constant inside every atom of $\mathfrak{F}$ as in a regular semantic refinement, but we do know that there exists a function $(G-\overline{G})$ that equals to $G$ on ${\tilde{X}}$ , is constant on every atom of $\mathfrak{F}$ and it is a function with a bounded degree i.e. $\deg(G-\overline{G})\leq\deg(G)$ .

Next, we present a new type of refinement, which is a relaxation of semantic refinement. This relaxation will allow us to discuss the corresponding claim of the polynomial regularity lemma (Lemma 33) for relative rank (instead of rank).

Definition 61 (Semantic Refinement Relative to ${\tilde{X}}$ ).

Let $\mathcal{B}$ and $\mathcal{B}^{\prime}$ be polynomial factors on $\mathbbm{F}^{n}$ , defined by sets of polynomials $\mathcal{P},\mathcal{P}^{\prime}$ respectively, and let $d\in\mathbbm{N}$ . We say a factor $\mathcal{B}^{\prime}$ is a semantic refinement relative to ${\tilde{X}}$ of the factor $\mathcal{B}$ , or ${\tilde{X}}$ -relative semantic refinement, if the following holds: Every function $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ that is $\mathcal{P}$ -measurable relative to ${\tilde{X}}$ , is also $\mathcal{P}^{\prime}$ -measurable relative to ${\tilde{X}}$ . If the definition above holds, we denote $\mathcal{B}^{\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ .

$\blacktriangleright$ Note.

It is easy to see that this relation is transitive, i.e. if $\mathcal{B}^{\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ and $\mathcal{B}^{\prime\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}^{\prime}$ , then $\mathcal{B}^{\prime\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ .

$\blacktriangleright$ Remark 62.

In ${\tilde{X}}$ , semantic refinements relative to ${\tilde{X}}$ behave the same as regular semantic refinements in the perspective of being measurable: every function that is $\mathcal{P}$ -measurable in ${\tilde{X}}$ is also $\mathcal{P}^{\prime}$ -measurable in ${\tilde{X}}$ . However, the two definitions behave differently in the perspective of being measurable in $\mathbbm{F}^{n}$ . Specifically, in relative semantic refinements, if $G$ is a $\mathcal{P}$ -measurable function it is not necessarily $\mathcal{P}^{\prime}$ -measurable. However, it is measurable up to a remainder $\overline{G}$ of degree $\leq\deg(G)$ such that $\overline{G}|_{{\tilde{X}}}\equiv 0$ .

Corollary 63.

If $\mathcal{B}^{\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ , then in ${\tilde{X}}$ it is a regular semantic refinement, i.e. $\mathcal{B}^{\prime}\succeq_{\text{sem}|{\tilde{X}}}\mathcal{B}$ .

Next, we present a new regularization process that allows us to increase the relative rank of a factor without increasing the size of the factor too much (independent of $n$ ). This regularization process generalizes the regularization process in $\mathbbm{F}^{n}$ , that we stated in Lemma 33. We call this type of regularization process a relative-regularization process relative to ${\tilde{X}}$ , shorthand by ${\tilde{X}}$ -regularization For a specific function ${{{r}}}$ , we will sometimes call applying this lemma a ${{{r}}}$ - ${\tilde{X}}$ -regularization. Note that to allow such a relative-regularization process to hold, we must use the relaxed definition of semantic refinement that is presented above.

Theorem 64.

Let ${{{r}}}:\mathbbm{N}\rightarrow\mathbbm{N}$ be a non-decreasing function and let $d\in\mathbbm{N}$ . There exists $C_{{{{r}}},d}^{\ref{theorem:regularization-in-X}}:\mathbbm{N}\rightarrow% \mathbbm{N}$ such that the following holds: Let $\mathcal{B}$ be a factor defined by polynomials $\mathcal{P}=(P_{1},...,P_{c})$ where for all $i\in[c]$ : $P_{i}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ and $\deg(P_{i})\leq d$ . Then, there is an ${{{r}}}$ - ${\tilde{X}}$ -regular factor $\mathcal{B}^{\prime}$ defined by polynomials $\mathcal{P}^{\prime}=(P^{\prime}_{1},...,P^{\prime}_{c^{\prime}})$ where for all $i\in[c]$ : $P^{\prime}_{i}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ and $\deg(P^{\prime}_{i})\leq d$ such that $\mathcal{B}^{\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ and $c^{\prime}\leq C_{{{{r}}},d}^{\ref{theorem:regularization-in-X}}(c)$ .
Moreover, if $\mathcal{B}\succeq_{\text{syn}}\bar{\mathcal{B}}$ for some polynomial factor $\bar{\mathcal{B}}$ with relative rank of at least ${{{r}}}(c^{\prime})+c^{\prime}+1$ and rank of at least ${{{{r}}}_{\ref{preserving-degree-starting-field}}(\mathbbm{F},d,c^{\prime})}+c% ^{\prime}+1$ , then we can require that $\mathcal{B}^{\prime}\succeq_{\text{syn}}\bar{\mathcal{B}}$ .

Proof.

We follow the lines of the proof given by [32][Lemma 7.29], but here, we wish to increase the relative rank of the factor instead of its rank. We present an iterative process, which will eventually lead us to a factor of size $c^{\prime}$ with relative rank higher than ${{{r}}}(c^{\prime})$ , that is a semantic refinement relative to ${\tilde{X}}$ . Let $d\in\mathbbm{N}$ , and let $\mathcal{B}$ be a polynomial factor defined by $\mathcal{P}=(P_{1},...,P_{c})$ such that $P_{i}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ of degree $\leq d$ . We remind the reader definition 32, where we defined $M(\mathcal{B})\coloneqq(M_{d},...,M_{1})\in\mathbbm{N}^{d}$ , where $M_{i}$ denotes the number of polynomials in $\mathcal{P}$ that have degree exactly $i$ , and the lexicographical order on $\mathbbm{N}^{d}$ where $M>M^{\prime}$ if and only if $M_{i}>M^{\prime}_{i}$ for some $1\leq i\leq d$ , and $M_{j}=M^{\prime}_{j}$ for all $j>i$ . This proof will be by transfinite induction on $M$ under the lexicographical order. Next we describe a step of the regularization process.
Let $\mathcal{B}$ be a polynomial factor defined by $\mathcal{P}=(P_{1},...,P_{c})$ . Note that this is an abuse of notations: the factor $\mathcal{B}$ and the set $\mathcal{P}$ refer to the original factor in the first step, and also to the current factor in the middle of the relative-regularization process. If $\mathcal{B}$ is ${{{r}}}$ - ${\tilde{X}}$ -regular, then we are done. Otherwise, we change $\mathcal{B}$ as follows: First, we denote ${{{r}}}_{\ref{preserving-degree-starting-field}}^{\mathbbm{F},d}(c)\coloneqq{{% {r}}}_{\ref{preserving-degree-starting-field}}(\mathbbm{F},d,c)$ , and we ${{{r}}}_{\ref{preserving-degree-starting-field}}$ -regularize $\mathcal{P}$ using lemma 33 to get a set of polynomials $\mathcal{P}_{1}=(P^{1}_{1},...,P^{1}_{c_{1}})$ of degree $\leq d$ , which defines a factor $\mathcal{B}_{1}$ and has a rank $\geq{{{r}}}_{\ref{preserving-degree-starting-field}}^{\mathbbm{F},d}(c_{1})$ . Note that $M(\mathcal{B}_{1})\leq M(\mathcal{B})$ . Then, again, if somehow $\mathcal{B}_{1}$ is now ${{{r}}}$ - ${\tilde{X}}$ -regular, we are done.
Otherwise, by definition, there exists some linear combination of the polynomials in $\mathcal{P}_{1}$ that has $d^{\star}$ -relative rank less than ${{{r}}}(c_{1})$ , where $d^{\star}$ is the maximal degree that participates in the linear combination. Let $\vec{P}(x)=\sum_{i=0}^{c_{1}}{\lambda_{i}P^{1}_{i}(x)}$ where $\vec{0}\neq\vec{\lambda}\in\mathbbm{F}^{c_{1}}$ , be the linear combination with $rank_{{d^{\star}},{{\tilde{X}}}}\left(\vec{P}\right)\leq{{{r}}}(c_{1})$ where $d^{\star}\coloneqq\max_{i\in\left[c_{1}\right]}{\deg(\lambda_{i}P^{1}_{i})}$ . By definition of relative rank, there exists $\overline{Pmissing}\in Poly_{\leq\deg(\vec{P})}(\mathbbm{F}^{n}\rightarrow% \mathbbm{F})$ with $\overline{Pmissing}|_{{\tilde{X}}}\equiv 0$ such that $rank_{d^{\star}}\left(\vec{P}-\overline{Pmissing}\right)\leq{{{r}}}(c_{1})$ . Note that $\deg(\overline{Pmissing})\leq d^{\star}$ . By definition of $d^{\star}$ -rank, we have that we can decompose $\vec{P}-\overline{Pmissing}$ as a function of ${{{r}}}(c_{1})$ polynomials of degree $\leq d^{\star}-1$ . In other words, there exist a measurement function $\vec{\Gamma}:\mathbbm{F}^{{{{r}}}(c_{1})}\rightarrow\mathbbm{F}$ and polynomials $Q_{1},...,Q_{{{{r}}}(c_{1})}$ with $\deg(Q_{i})\leq d^{\star}-1$ such that:

\forall a\in\mathbbm{F}^{n}:\vec{P}(a)-\overline{Pmissing}(a)=\vec{\Gamma}% \left(Q_{1}(a),...,Q_{{{{r}}}(c_{1})}(a)\right)

Now, let $\mathcal{P}^{\star}\subseteq\mathcal{P}_{1}$ be the set of all such maximal-degree polynomials, and let $i^{\star}$ be chosen such that $P^{1}_{i^{\star}}\in\mathcal{P}^{\star}$ . Note that the set $\mathcal{P}^{\star}$ is non empty, as by definition, $d^{\star}$ is the maximal degree of polynomial in the expression $\sum_{i=1}^{c_{1}}{\lambda_{i}P^{1}_{i}}$ such that $\lambda_{i}\neq 0$ .
For the next step, define the polynomial factor $\mathcal{B}_{2}$ be the polynomial factor defined by the set:

\mathcal{P}_{2}\coloneqq\mathcal{P}_{1}\setminus\left\{P^{1}_{i^{\star}}\right% \}\cup\left\{Q_{1},...,Q_{{{{r}}}(c_{1})}\right\}

Finally, the factor $\mathcal{B}_{2}$ will be the factor returned from the relative-regularization step.
It is easy to see that if the process above halts, we get a ${{{r}}}$ - ${\tilde{X}}$ -regular factor. Now, we prove the first part of the lemma by showing the following claims:

Claim 65.

The factor generated from the regularization above is of bounded size: a bound that may depend on ${{{r}}},d,c$ , but does not depend on $n$ . Formally, we claim that there exists $C^{\ref{theorem:regularization-in-X}}_{{{{r}}},d}:\mathbbm{N}\rightarrow% \mathbbm{N}$ such that we have $c^{\prime}\leq C^{\ref{theorem:regularization-in-X}}_{{{{r}}},d}(c)$ .

Proof.

It is enough to prove the following:

1.

In each step, the amount of polynomials there are in $\mathcal{P}_{1},\mathcal{P}_{2}$ are bounded by a bound that depend only on ${{{r}}},d,c$ (independent of $n$ ).
2.

The number of steps of the relative-regularization process is also bounded by a bound that depends only on ${{{r}}},d,c$ (independent of $n$ ).

The combination of these two will obtain the desired bound of the amount of polynomials in the last-step regularized factor, which is $C^{\ref{theorem:regularization-in-X}}_{{{{r}}},d}(c)$ . Note that the bound on the last-step relative-regularized factor in not simply the multiplication of the two bounds, but a recursively-substitution of the bound in 1, a bounded amount of times (bounded by the bound in 2).
For 1, we first notice that the number of polynomials in the regular regularization process is bounded, specifically we have $\left|\mathcal{P}^{1}\right|=c_{1}\leq C^{\ref{regularization-in-Fn-lemma}}_{{% {{r}}}_{\ref{preserving-degree-starting-field}},d}(c)$ . Moreover, the polynomial factor $\mathcal{B}_{2}$ is generated by adding at most ${{{r}}}(c_{1})$ polynomials to the factor, and thus we have $\left|\mathcal{P}_{2}\right|\leq c_{1}+{{{r}}}(c_{1})$ which is also bounded by substituting the bound on $c_{1}$ .
For 2, we use the transfinite induction on $M$ we mentioned earlier to show that the process must halt after a bounded number of steps. Formally, we show that there exist $M^{\prime}$ which depends only on $M(\mathcal{B})$ such that $M(\mathcal{B}_{2})\leq M^{\prime}<M(\mathcal{B})$ . This will bound the number of steps by a value that depend only on $M(\mathcal{B})$ , which depends only on ${{{r}}},d,c$ . To do so, we first notice that the regular regularization does not increase the value of $M$ , i.e. $M(\mathcal{B}_{1})\leq M(\mathcal{B})$ . Thus, we can focus on the second part of the relative-regularization. In this part, we replace a single degree $d^{\star}$ polynomial by at most ${{{r}}}(c_{1})$ polynomials of degree $\leq d^{\star}-1$ . Therefore, by choosing $M^{\prime}\coloneqq(M_{d},...,M_{d^{\star}+1},M_{d^{\star}}-1,M_{d^{\star}-1}+% {{{r}}}(c_{1}),...,M_{1}+{{{r}}}(c_{1}))$ we get that $M(\mathcal{B}_{2})\leq M^{\prime}<M(\mathcal{B}_{1})\leq M(\mathcal{B})$ , which concludes 2. $\hfill\vartriangleleft$

Claim 66.

The factor generated from the regularization above is a ${\tilde{X}}$ -relative semantic refinement of the original factor, i.e. $\mathcal{B}^{\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ .

Proof.

It is enough to show that in each step, the factors generated by the relative-regularization process are semantic refinements relative to ${\tilde{X}}$ of the previous step’s factor. Specifically, we show $\mathcal{B}_{2}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}_{1}\succeq^{{% \tilde{X}}}_{\text{sem}}\mathcal{B}$ and the claim will follow from transitivity of relative semantic refinements.
We start by proving $\mathcal{B}_{1}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ . Let $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ be a function that is $\mathcal{P}$ -measurable relative to ${\tilde{X}}$ . We denote $d_{F}\coloneqq\deg(F)$ . By definition, there exists $\Gamma:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ , $\overline{Fmissing}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ where $\deg(\overline{Fmissing}),\deg(F-\overline{Fmissing})\leq d_{F}$ and $\overline{Fmissing}|_{{\tilde{X}}}\equiv 0$ , such that:

\forall a\in\mathbbm{F}^{n}:F(a)=\Gamma(P_{1}(a),...,P_{c}(a))+\overline{F% missing}(a)

Clearly, the function $\Gamma(P_{1}(a),...,P_{c}(a))$ is $\mathcal{P}$ -measurable in $\mathbbm{F}^{n}$ , and because we have $\mathcal{B}\succeq_{\text{sem}}\mathcal{B}_{1}$ , it is also $\mathcal{P}_{1}$ -measurable in $\mathbbm{F}^{n}$ . Thus there exists $\Gamma_{1}:\mathbbm{F}^{c_{1}}\rightarrow\mathbbm{F}$ such that:

\forall a\in\mathbbm{F}^{n}:F(a)=\Gamma_{1}(P^{1}_{1}(a),...,P^{1}_{c_{1}}(a))% +\overline{Fmissing}(a)

And therefore we have $\mathcal{B}_{1}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ .
Now, we prove $\mathcal{B}_{2}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}_{1}$ . Let $F:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ be a function that is $\mathcal{P}_{1}$ -measurable relative to ${\tilde{X}}$ . Again, we denote $d_{F}\coloneqq\deg(F)$ , and by definition there exists $\Gamma_{1}:\mathbbm{F}^{c_{1}}\rightarrow\mathbbm{F}$ , $\overline{F_{1}}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ where $\deg(F-\overline{F_{1}})\leq d_{F}$ and $\overline{F_{1}}|_{{\tilde{X}}}\equiv 0$ , such that:

\forall a\in\mathbbm{F}^{n}:F(a)=\Gamma_{1}(P^{1}_{1}(a),...,P^{1}_{c_{1}}(a))% +\overline{Fmissing}_{1}(a)

(1)

Note that we also have $\deg(\overline{F_{1}})\leq d_{F}$ . We will refer this equation, and its simplifications we do throughout the proof, as the $\mathcal{P}_{1}$ -decomposition of $F$ .
We wish to show that there exists $\Gamma_{2}:\mathbbm{F}^{c_{2}}\rightarrow\mathbbm{F}$ and $\overline{Fmissing}_{2}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ where $\deg(F-\overline{Fmissing}_{2})\leq d_{F}$ and $\overline{Fmissing}_{2}|_{{\tilde{X}}}\equiv 0$ , such that:

\forall a\in\mathbbm{F}^{n}:F(a)=\Gamma_{2}\left(P^{1}_{1}(a),...P^{1}_{i^{% \star}-1}(a),P^{1}_{i^{\star}+1}(a),...,P^{1}_{c}(a),Q_{1}(a),...,Q_{{{{r}}}(c% _{1})}(a)\right)+\overline{Fmissing}_{2}(a)

We will do so using the $\mathcal{P}_{1}$ -decomposition of $F$ . Note that showing $\deg(F-\overline{F_{2}})\leq d_{F}$ is equivalent of showing $\deg(\overline{Fmissing}_{2})\leq d_{F}$ .
First, by the way we built $\mathcal{P}_{2}$ , using the same notations in the regularization step, we have:

\forall a\in\mathbbm{F}^{n}:P_{i^{\star}}^{1}(a)=\vec{\Gamma}\left(Q_{1}(a),..% .,Q_{{{{r}}}(c_{1})}(a)\right)+\overline{Pmissing}(a)-\sum_{i\neq i^{\star}}{% \lambda_{i}P_{i}^{1}(a)}

Next, we substitute the value of $P_{i^{\star}}^{1}$ in the $\mathcal{P}_{1}$ -decomposition of $F$ (1), and get another decomposition of $F$ that does not depend on $P_{i^{\star}}^{1}$ . Specifically we have:

	$\displaystyle\forall a\in\mathbbm{F}^{n}:F(a)$	$\displaystyle=\Gamma_{1}\left(P^{1}_{1}(a),...,\left(\vec{\Gamma}\left(Q_{1}(a% ),...,Q_{{{{r}}}(c_{1})}(a)\right)+\overline{Pmissing}(a)-\sum_{i\neq i^{\star% }}{\lambda_{i}P_{i}^{1}(a)}\right),...,P^{1}_{c_{1}}(a)\right)$		(2)
		$\displaystyle+\overline{Fmissing}_{2}(a)$		(3)

We wish to use the equation above to show that $F$ is $\mathcal{P}_{2}$ -measurable relative to ${\tilde{X}}$ . However, in order to show that the equation above is in the desired structure that proves that $F$ is $\mathcal{P}_{2}$ -measurable, the expression inside $\Gamma_{1}$ must not depend on $\overline{Pmissing}$ because $\overline{Pmissing}\notin\mathcal{P}_{2}$ . Note that this is enough as the rest of the polynomials in the expression above are in $\mathcal{P}_{2}$ , and therefore without $\overline{Pmissing}$ the expression is $\mathcal{P}_{2}$ -measurable.
To do so, we start by simplifying some of the notations. We denote:

\vec{P}_{2}(a)\coloneqq\vec{\Gamma}\left(Q_{1}(a),...,Q_{{{{r}}}(c_{1})}(a)% \right)-\sum_{i\neq i^{\star}}{\lambda_{i}P_{i}^{1}(a)}

This is the part of the sum that decomposes $P_{i^{\star}}^{1}(a)$ that is $\mathcal{P}_{2}$ -measurable, thus the following equality applies:

P_{i^{\star}}^{1}(a)=\vec{P}_{2}(a)+\overline{Pmissing}(a)

where $\deg(\vec{P_{2}}),\deg(\overline{Pmissing})\leq d^{\star}$ . Using this notation, we write the $\mathcal{P}_{1}$ -decomposition of $F$ (2), and get:

\forall a\in\mathbbm{F}^{n}:F(a)=\Gamma_{1}\left(P^{1}_{1}(a),...,\left(\vec{P% }_{2}(a)-\overline{Pmissing}(a)\right),...,P^{1}_{c_{1}}(a))\right)+\overline{% Fmissing}_{1}(a)

(4)

Now, we use the following key observation: $rank\left(\mathcal{P}_{1}\right)\geq{{{r}}}_{\ref{preserving-degree-starting-% field}}(\mathbbm{F},d,c_{1})$ , and as $\deg(\Gamma_{1}(P_{1}^{1},...,P^{1}_{c_{1}}))\leq d_{F}$ we can use Lemma 30 to achieve that $\Gamma_{1}$ is a polynomial of the form:

\Gamma_{1}(z_{1},...,z_{c_{1}})=\sum_{\alpha\in\left[p-1\right]^{c_{1}}}{C_{% \alpha}\cdot{\prod_{i=1}^{c_{1}}}{z_{i}^{\alpha_{i}}}}

(

\star

)

where $C_{\alpha}=0$ whenever $\sum_{i=1}^{c_{1}}(\alpha_{i}\cdot\deg(P_{i}^{1}))>d_{F}$ .
Next, we substitute the polynomial structure of $\Gamma_{1}$ ( $\star$ ‣ 5) in the $\mathcal{P}_{1}$ -decomposition of $F$ (4), and observe what happens to each summand monomial with non-zero coefficients of $\Gamma_{1}$ in the expression after the substitution.
We will show that each such monomial is either $\mathcal{P}_{2}$ -measurable, or a sum of a $\mathcal{P}_{2}$ -measurable function with a valid ${\tilde{X}}$ -remainder, i.e. a polynomial of degree $\leq d_{F}$ that is $\equiv 0$ in ${\tilde{X}}$ . Note that if this is true for each monomial, every linear combination of such monomials is also a sum of $\mathcal{P}_{2}$ -measurable function with a valid ${\tilde{X}}$ -remainder. Thus, this will also be true for the entire decomposition of $F$ , as it is a linear combination of such monomials summed with a valid remainder $\overline{Fmissing}_{1}$ . This will conclude the proof.
Let $\alpha=(\alpha_{1},...,\alpha_{c_{1}})$ be a vector of degrees that represents such a monomial. If $\alpha_{i^{\star}}=0$ , then the monomial is in the form:

\prod_{i\in[c_{1}]}{{P_{i}}^{\alpha_{i}}}=\prod_{i\in[c_{1}]\setminus\left\{i^% {\star}\right\}}{{P_{i}}^{\alpha_{i}}}

and therefore it is clearly $\mathcal{P}_{2}$ -measurable as all the polynomials in the expression above are in $\mathcal{P}_{2}$ .
Next, if $\alpha_{i^{\star}}\neq 0$ , then the monomial is in the form:

\prod_{i\in[c_{1}]}{{P_{i}}^{\alpha_{i}}}=(\vec{P_{2}}+\overline{Pmissing})^{% \alpha_{i^{\star}}}\cdot\left(\prod_{i\in[c_{1}]\setminus\left\{i^{\star}% \right\}}{{P_{i}}^{\alpha_{i}}}\right)

(5)

where $\sum_{i\in[c_{1}]}(\alpha_{i}\cdot\deg(P_{i}^{1}))\leq d_{F}$ . As $\deg(\vec{P_{2}}+\overline{Pmissing})=\deg(P_{i^{\star}})=d^{\star}$ , we have:

\deg\left(\prod_{i\in[c_{1}]\setminus\left\{i^{\star}\right\}}{{P_{i}}^{\alpha% _{i}}}\right)=\sum_{i\in[c_{1}]\setminus{i^{\star}}}(\alpha_{i}\cdot\deg(P_{i}% ^{1}))\leq d_{F}-\alpha_{i^{\star}}\cdot d^{\star}

Now, we open the left brackets in (5), i.e. $(\vec{P_{2}}+\overline{Pmissing})^{\alpha_{i^{\star}}}$ . This enables us to separate the monomial to the part that only depend on $\vec{P_{2}}$ summed with a polynomial with bounded degree multiplied by $\overline{Pmissing}$ (and therefore a valid remainder). To be more specific, the monomial is in the form:

(\vec{P_{2}}+\overline{Pmissing})^{\alpha_{i^{\star}}}=\vec{P_{2}}^{\alpha_{i^% {\star}}}+\overline{P_{\alpha}}

for some polynomial $\overline{P_{\alpha}}$ such that:

1.

$\overline{P_{\alpha}}$ is of degree $\deg(\overline{P_{\alpha}})\leq\max\left\{\deg(\vec{P_{2}}),\deg(\overline{P)}% \right\}\cdot\alpha_{i^{\star}}\leq\alpha_{i^{\star}}\cdot d^{\star}$
2.

$\overline{P_{\alpha}}$ is a multiple of $\overline{Pmissing}$ , and therefore $\overline{P_{\alpha}}|_{{\tilde{X}}}\equiv 0$

Therefore, by substituting the left brackets back to the equation (5) and as $\vec{P_{2}}$ and $P_{i}$ for $i\neq i^{\star}$ are $\mathcal{P}_{2}$ -measurable, one can see that the monomial is a sum of a $\mathcal{P}_{2}$ -measurable polynomial with a valid remainder. Specifically, the remainder $\equiv 0$ in ${\tilde{X}}$ , and its degree is $\leq\alpha_{i^{\star}}\cdot d^{\star}+d_{F}-\alpha_{i^{\star}}\cdot d^{\star}=% d_{F}$ . This concludes the proof of the claim. $\hfill\vartriangleleft$ Now, it remains to prove the second part of the Theorem 64.

Claim 67.

If $\mathcal{B}\succeq_{\text{syn}}\bar{\mathcal{B}}$ for some polynomial factor $\bar{\mathcal{B}}$ with relative rank of at least ${{{r}}}(c^{\prime})+c^{\prime}+1$ and rank of at least ${{{{r}}}_{\ref{preserving-degree-starting-field}}(\mathbbm{F},d,c^{\prime})}+c% ^{\prime}+1$ , then we can require that $\mathcal{B}^{\prime}\succeq_{\text{syn}}\bar{\mathcal{B}}$ .

Proof.

We will show claim step-by-step. We denote by $\mathcal{P},\bar{\mathcal{P}},\mathcal{P}_{1},\mathcal{P}_{2}$ the polynomial sets that generate the factors $\mathcal{B},\bar{\mathcal{B}},\mathcal{B}_{1},\mathcal{B}_{2}$ . Note that $\mathcal{B}_{1},\mathcal{B}_{2}$ are the factors in the current step of the regularization process, and thus change in each step of the proof. We show that in each step, if $\mathcal{B}\succeq_{\text{syn}}\bar{\mathcal{B}}$ for some polynomial factor $\bar{\mathcal{B}}$ with relative rank of at least ${{{r}}}(c^{\prime})+c^{\prime}+1$ and rank of at least ${{{{r}}}_{\ref{preserving-degree-starting-field}}(\mathbbm{F},d,c^{\prime})}+c% ^{\prime}+1$ , then we can require that $\mathcal{B}_{1}\succeq_{\text{syn}}\bar{\mathcal{B}}$ , and also that $\mathcal{B}_{2}\succeq_{\text{syn}}\bar{\mathcal{B}}$ .
For the first part, we have $\mathcal{B}_{1}\succeq_{\text{syn}}\bar{\mathcal{B}}$ by a simple usage of the second part of lemma 33, as:

rank\left(\bar{\mathcal{P}}\right)>{{{r}}}_{\ref{preserving-degree-starting-% field}}(\mathbbm{F},d,c^{\prime})+c^{\prime}+1\geq{{{r}}}_{\ref{preserving-% degree-starting-field}}(\mathbbm{F},d,c_{1})+c_{1}+1

Now we prove the second part. We show that in the current regularization step, we could replace $P^{1}_{i^{\star}}\in\mathcal{P}_{1}$ such that $P^{1}_{i^{\star}}\notin\bar{\mathcal{P}}$ . Note that this is possible whenever $\mathcal{P}^{\star}\cap\bar{\mathcal{P}}\neq\emptyset$ as the choice of $i^{\star}$ is arbitrary in polynomials which are in $\mathcal{P}^{\star}$ .
Assume that is not possible and the factor $\mathcal{P}_{1}$ is still not ${{{r}}}$ - ${\tilde{X}}$ -regular. Then, we have a linear combination $\vec{P}(x)\coloneqq\sum_{i=0}^{c_{1}}{\lambda_{i}P^{1}_{i}(x)}$ with $rank_{{d^{\star}},{{\tilde{X}}}}\left(\vec{P}\right)\leq{{{r}}}(c_{1})$ where $d^{\star}=\max_{i\in\left[c_{1}\right]}{\deg(\lambda_{i}P^{1}_{i})}$ . We denote by $I^{\star}\subseteq[c_{1}]$ the set of indexes of such maximal-degree polynomials. By this notation, our assumption states that for all $i\in I^{\star}$ we have $P^{1}_{i}\in\bar{\mathcal{P}}$ . Additionally, note that for all $i\notin I^{\star}$ we have $\deg(P^{1}_{i})<d^{\star}$ . Therefore, as the linear combination is of $d^{\star}$ -relative rank $\leq{{{r}}}(c_{1})$ , there exists a polynomial $\overline{Pmissing}$ of degree $\leq\deg(\vec{P})\leq d^{\star}$ with $\overline{Pmissing}|_{{\tilde{X}}}\equiv 0$ such that $rank_{d^{\star}}\left(\vec{P}-\overline{Pmissing}\right)\leq{{{r}}}(c_{1})$ . In other words, there exist a measurement function $\vec{\Gamma}:\mathbbm{F}^{{{{r}}}(c_{1})}\rightarrow\mathbbm{F}$ and polynomials $Q_{1},...,Q_{{{{r}}}(c_{1})}$ with $\deg(Q_{i})\leq d^{\star}$ such that:

\forall a\in\mathbbm{F}^{n}:\vec{P}(a)-\overline{Pmissing}(a)=\vec{\Gamma}% \left(Q_{1}(a),...,Q_{{{{r}}}(c_{1})}(a)\right)

By a simple calculation we have:

\forall a\in\mathbbm{F}^{n}:\sum_{i\in I^{\star}}{P^{1}_{i}(a)}-\overline{P% missing}(a)=\vec{\Gamma}\left(Q_{1}(a),...,Q_{{{{r}}}(c_{1})}(a)\right)+\sum_{% i\notin I^{\star}}{P^{1}_{i}(a)}

and by this we found a linear combination of polynomials in $\bar{\mathcal{P}}$ with maximal degree $d^{\star}$ , that has $d^{\star}$ -relative-rank $\leq{{{r}}}(c_{1})+c_{1}+1$ . This is a contradiction to our assumptions on $\bar{\mathcal{B}}$ , which completes the proof of the claim. $\hfill\vartriangleleft$ This completes the proof of the lemma. $\hfill\blacktriangleleft$

6 Radius of Reed-Muller over ${\tilde{X}}$

We recall that the normalized distances of Reed-Muller codes over $\mathbbm{F}^{n}$ and over ${\tilde{X}}$ are denoted by $\delta_{\mathbbm{F}}(d)$ and $\delta_{\mathbbm{F},{\tilde{X}}}(d)$ respectively. We present a theorem that shows that Reed-Muller codes over a subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ that is $d$ -lift-enabler and has the (limited) relative rank-bias property, has (approximately) an equal normalized distance as Reed-Muller codes over $\mathbbm{F}^{n}$ .

Theorem 68.

There exist a function $\epsilon_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ such that the following holds: Let $\mathbbm{F}$ be a finite field, and let $d\in\mathbbm{N}$ be an integer that represents a degree. Let ${\tilde{\epsilon}}>0$ , and let ${\tilde{r}}:[{\tilde{\epsilon}},\infty]\rightarrow\mathbbm{N}$ be a limited-relative-rank-bias function.
Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a set with the following properties

1.

${\tilde{X}}$ is $d$ -lift-enabler with a lift operator $\widehat{\square}$ .
2.

${\tilde{X}}$ has the $({\tilde{r}},\mathbbm{F},d,{\tilde{\epsilon}})$ -relative-rank-bias property.

Then, for $\epsilon_{1}\coloneqq\epsilon_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ we have that for all $n\in\mathbbm{N}$ :

\delta_{\mathbbm{F},{\tilde{X}}}(d)\geq\ \delta_{\mathbbm{F}}(d)-\epsilon_{1}

Proof.

We wish to do a reduction of our question regarding the radius of Reed-Muller in ${\tilde{X}}$ to the same question about Reed-Muller in $\mathbbm{F}^{n}$ . Let $\mathbbm{F}$ be a finite field, and let $d\in\mathbbm{N}$ be an integer that represents a degree. Let ${\tilde{\epsilon}}>0$ , and let ${\tilde{r}}:[{\tilde{\epsilon}},\infty]\rightarrow\mathbbm{N}$ be a limited-rank-relative-bias function. Let $\epsilon_{1}\coloneqq\epsilon_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ be a function we will specify later. Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a set with the properties defined above.
Moreover, let $\epsilon>\epsilon_{1}$ be some positive value. We will show that:

\delta_{\mathbbm{F},{\tilde{X}}}(d)>\ \delta_{\mathbbm{F}}(d)-\epsilon

This will be enough as if the above holds for every $\epsilon>\epsilon_{1}$ , we get that in fact $\delta_{\mathbbm{F},{\tilde{X}}}(d)\geq\delta_{\mathbbm{F}}(d)-\epsilon_{1}$ .
For start, we note a simple observation: as Reed-Muller over ${\tilde{X}}$ is a linear code, we have

\delta_{\mathbbm{F},{\tilde{X}}}(d)=\min\left\{\Pr_{x\in{\tilde{X}}}\left[p(x)% \neq 0\right]\middle|p\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})\right\}

Now, let $p\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ be a polynomial over ${\tilde{X}}$ , and denote $d_{p}\coloneqq\deg(p)$ . We wish to lower-bound the value of $\Pr_{x\in{\tilde{X}}}\left[p(x)\neq 0\right]$ . To do so, we will equivalently upper-bound the value of $\Pr_{x\in{\tilde{X}}}\left[p(x)=0\right]$ . Precisely, to complete the proof all we need to show is:

\Pr_{x\in{\tilde{X}}}\left[p(x)=0\right]\leq 1-\delta_{\mathbbm{F}}(d)+\epsilon

Now we begin the proof itself. First, we lift the polynomial $p$ and get a polynomial $\widehat{p}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ such that $\widehat{p}|_{{\tilde{X}}}\equiv p$ and $\deg(\widehat{p})=d_{p}$ . Next, denote by $\mathcal{B}_{\widehat{p}}$ the factor defined by the set of single polynomial $\mathcal{P}=\left\{\widehat{p}\right\}$ . Trivially, the polynomial $\widehat{p}$ is measurable in respect of $\mathcal{P}$ .
We define the rank function:

{{{r}}}(m)\coloneqq\max\left\{{\tilde{r}}\left(\dfrac{\epsilon/2}{\left|% \mathbbm{F}\right|^{m}}\right),{{{r}}}_{\ref{high-rank-implies-low-bias}}\left% (\mathbbm{F},d,\dfrac{\epsilon/2}{\left|\mathbbm{F}\right|^{m}}\right)\right\}

Then, we ${{{r}}}$ - ${\tilde{X}}$ -regularize $\mathcal{P}$ using Lemma 64. This gives us a ${{{r}}}$ - ${\tilde{X}}$ -regular factor $\mathcal{B}^{\prime}$ , which is defined by a set of polynomials $\mathcal{P}^{\prime}\coloneqq\left\{P^{\prime}_{1},...,P^{\prime}_{c^{\prime}}\right\}$ of degree $\leq d$ such that $\mathcal{B}^{\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}_{\widehat{p}}$ with $rank_{{\tilde{X}}}\left(\mathcal{P}^{\prime}\right)\geq{{{r}}}$ and with bounded amount of polynomials defining it i.e, $c^{\prime}\leq C_{{{{r}}},d}^{\ref{theorem:regularization-in-X}}(1)$ . Therefore, from definition we have that $\widehat{p}$ is $\mathcal{P}^{\prime}$ -measurable relative to ${\tilde{X}}$ . Thus, there exists a measurement function $\Gamma:\mathbbm{F}^{c^{\prime}}\rightarrow\mathbbm{F}$ and a remainder $\overline{\Gamma}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ with $\overline{\Gamma}|_{{\tilde{X}}}\equiv 0$ and degree bounded by $d_{p}$ , such that:

\forall a\in\mathbbm{F}^{n}:\widehat{p}(a)=\Gamma(P^{\prime}_{1}(a),...,P^{% \prime}_{c^{\prime}}(a))+\overline{\Gamma}(a)

Next, we denote $P^{\prime}\coloneqq\widehat{p}-\overline{\Gamma}$ . By definition of remainder function, we have that $P^{\prime}|_{{\tilde{X}}}\equiv p$ . Additionally, note that $P^{\prime}$ is a polynomial over $\mathbbm{F}^{n}$ of degree $\deg(P^{\prime})=d_{p}\leq d$ , and hence by the definition of $\delta_{\mathbbm{F}}(d)$ :

\Pr_{a\in\mathbbm{F}^{n}}\left[P^{\prime}(a)=0\right]\leq 1-\delta_{\mathbbm{F% }}(d)

(6)

For the next step, we claim that $P^{\prime}$ equals $0$ in $\mathbbm{F}^{n}$ approximately with the same probability it equals $0$ in ${\tilde{X}}$ . Note that this is the heart of the proof: it allows use properties known in $\mathbbm{F}^{n}$ to new properties in ${\tilde{X}}$ . This is formulated as follows:

Claim 69.

We have:

\left|\Pr_{a\in\mathbbm{F}^{n}}\left[P^{\prime}(a)=0\right]-\Pr_{x\in{\tilde{X% }}}\left[P^{\prime}(x)=0\right]\right|\leq\epsilon

Proof.

Denote $S\coloneqq\mathbbm{F}^{c^{\prime}}$ , and for all $s\in S$ , denote:

p_{1}(s)\coloneqq\Pr_{a\in\mathbbm{F}^{n}}\left[(P^{\prime}_{1}(a),...,P^{% \prime}_{c^{\prime}}(a))=s\right]

As of our choice of ${{{r}}}$ , we have $rank\left(\mathcal{P}^{\prime}\right)\geq{{{r}}}_{\ref{high-rank-implies-low-% bias}}\left(\mathbbm{F},d,\dfrac{\epsilon/2}{\left|\mathbbm{F}\right|^{c^{% \prime}}}\right)$ . By combining Theorem 23 with Lemma 81, we have that $p_{1}$ is ( $\epsilon/2\left|S\right|$ )-equidistributed, i.e:

p_{1}(s)=\dfrac{1\pm\epsilon/2}{\left|S\right|}

Similarly, denote:

p_{2}(s)\coloneqq\Pr_{x\in{\tilde{X}}}\left[(P^{\prime}_{1}(x),...,P^{\prime}_% {c^{\prime}}(x))=s\right]

As of our choice of ${{{r}}}$ , we have $rank_{{\tilde{X}}}\left(\mathcal{P}^{\prime}\right)\geq{\tilde{r}}(\epsilon/2% \left|S\right|)$ . Now, we wish to use the relative rank-bias relation with Lemma 81 to conclude similarly that $p_{2}$ is ( $\epsilon/2\left|S\right|$ )-equidistributed, i.e:

p_{2}(s)=\dfrac{1\pm\epsilon/2}{\left|S\right|}

However, in order to so, we must first ensure that $(\epsilon/2\left|S\right|)\geq{\tilde{\epsilon}}$ . This is done by choosing a correct $\epsilon_{1}$ , and formulated in the following claim:

Claim 70.

One can choose $\epsilon_{1}\coloneqq\epsilon_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ such that if $\epsilon\geq\epsilon_{1}$ we have that $\epsilon/2\left|S\right|\geq\epsilon_{1}$ .

Proof.

We need that:

\dfrac{\epsilon}{2\left|\mathbbm{F}\right|^{c^{\prime}}}\geq{\tilde{\epsilon}}

As $c^{\prime}\leq C^{\ref{theorem:regularization-in-X}}_{{{{r}}},d}(1)$ , for the term above to hold it is enough that the following will be true:

\epsilon\geq{\tilde{\epsilon}}\cdot 2\left|\mathbbm{F}\right|^{C^{\ref{theorem% :regularization-in-X}}_{{{{r}}},d}(1)}

and as ${{{r}}}$ and thus also $C^{\ref{theorem:regularization-in-X}}_{{{{r}}},d}(1)$ are independent of $n$ , we can pick $\epsilon_{1}=\epsilon_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ and get what we aimed for. $\hfill\vartriangleleft$ Now, under that assumption of $\epsilon_{1}$ written above, we have that $p_{2}$ is ( $\epsilon/2\left|S\right|$ )-equidistributed. This allows us to use the similar distributions of $\mathcal{P}^{\prime}$ in $\mathbbm{F}^{n}$ and in ${\tilde{X}}$ to conclude that $P^{\prime}$ behaves similar in $\mathbbm{F}^{n}$ and in ${\tilde{X}}$ :

	$\displaystyle\Pr_{a\in\mathbbm{F}^{n}}\left[P^{\prime}(a)=0\right]$	$\displaystyle=\sum_{s\in S}{p_{1}(s)\cdot 1_{\Gamma(s)=0}}$
		$\displaystyle=\sum_{s\in S}{p_{2}(s)\cdot 1_{\Gamma(s)=0}}\pm\epsilon$
		$\displaystyle=\Pr_{x\in{\tilde{X}}}\left[P^{\prime}(x)=0\right]\pm\epsilon$

which concludes the proof of the claim. $\hfill\vartriangleleft$

Finally, as $P^{\prime}|_{{\tilde{X}}}\equiv p$ , we have that $\Pr_{x\in{\tilde{X}}}\left[P^{\prime}(x)=0\right]=\Pr_{x\in{\tilde{X}}}\left[p% (x)=0\right]$ . Thus, the claim above combining with (6) shows that the probability we wished to bound is bounded as we aimed for:

\Pr_{x\in{\tilde{X}}}\left[p(x)=0\right]\leq 1-\delta_{\mathbbm{F}}(d)+\epsilon

This concludes the proof of the theorem. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 71.

Under the same conditions, the distance of Reed-Muller codes in ${\tilde{X}}$ is also bounded from above by the distance of Reed-Muller codes in $\mathbbm{F}^{n}$ , and we have:

\delta_{\mathbbm{F},{\tilde{X}}}(d)\leq\delta_{\mathbbm{F}}(d)+\epsilon_{1}

Proof.

Let $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ be the polynomial in $\mathbbm{F}^{n}$ with the smallest distance from $0$ as possible, that is $\delta_{\mathbbm{F}}(d)$ . Denote $p\coloneqq P|_{{\tilde{X}}}$ . Note that $p$ is a polynomial in ${\tilde{X}}$ . Now repeat the proof using these two polynomials, and by Claim 69, we have that a random input of $P$ yields $0$ (approximately) the same as a random input of $p$ yields $0$ . Thus as we have $\Pr_{x\in\mathbbm{F}^{n}}\left[P(x)=0\right]=1-\delta_{\mathbbm{F}}(d)$ we also get:

\Pr_{x\in{\tilde{X}}}\left[p(x)=0\right]\geq 1-\delta_{\mathbbm{F}}(d)-% \epsilon_{1}

This bounds from above the distance of Reed-Muller code in ${\tilde{X}}$ and we have:

\delta_{\mathbbm{F},{\tilde{X}}}(d)\leq\delta_{\mathbbm{F}}(d)+\epsilon_{1}\

$\hfill\blacktriangleleft$

Corollary 72.

If we assume ${\tilde{X}}$ has the limited-relative rank-bias property to any extent (or just the relative rank-bias property), then the theorem above proves an exact equality $\delta_{\mathbbm{F},{\tilde{X}}}(d)=\delta_{\mathbbm{F}}(d)$ .

7 List Decoding Reed Muller Over ${\tilde{X}}$

In this section, we prove our main theorem: we prove the list decoding radius of Reed-Muller codes in ${\tilde{X}}$ is at least the list decoding radius of Reed-Muller codes in $\mathbbm{F}^{n}$ , assuming ${\tilde{X}}$ is lift-enabler and has the relative rank-bias property. We start by presenting formally the list decoding radius in ${\tilde{X}}$ .

Definition 73 (List Decoding in ${\tilde{X}}$ ).

Let $\mathbbm{F}$ be a finite field. Let $d,n\in\mathbbm{N}$ , and let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .
We define the Reed-Muller list-decoding count in ${\tilde{X}}$ at distance $\tau$ as follows:

\ell_{\mathbbm{F},{\tilde{X}}}(d,\tau)\coloneqq\max_{F:{\tilde{X}}\rightarrow% \mathbbm{F}}{\left|\left\{P\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F}% )\middle|{dist\left(P,F\right)\leq\tau}\right\}\right|}

Additionally, we define $LDR_{\mathbbm{F},{\tilde{X}}}(d)$ to be the list decoding radius, which is the maximum $\tau$ for which $\ell_{\mathbbm{F},{\tilde{X}}}(d,\tau-\epsilon)$ is bounded by a constant depending only on $\epsilon,\left|\mathbbm{F}\right|,d$ .

We recall that it was shown in [8, Theorem 1] that the list decoding radius of Reed Muller is $\delta_{\mathbbm{F}}(d)$ . To be more precise, it was shown that for every $\epsilon>0$ , the list-decoding count is constant (independent of $n$ ) in distance $\tau=\delta_{\mathbbm{F}}(d)-\epsilon$ . Formally, they have shown the following theorem:

Theorem 74 (List Decoding RM in $\mathbbm{F}^{n}$ ).

There exists a function $c(\mathbbm{F},d,\epsilon)$ such that the following holds: Let $\mathbbm{F}$ be a finite field, let $\epsilon>0$ , and let $d,n\in\mathbbm{N}$ . Then, we have:

\ell_{\mathbbm{F},\mathbbm{F}^{n}}(d,\delta_{\mathbbm{F}}(d)-\epsilon)\leq c(% \mathbbm{F},d,\epsilon)

Additionally, we recall a lemma that was presented in [8, Corollary 3.3], and was used in the analysis of the list decoding radius of Reed-Muller codes in $\mathbbm{F}^{n}$ :

Lemma 75 (Low Complexity Approximation).

[8, Corollary 3.3] Let $G:A\rightarrow B$ , and let $\epsilon>0$ . Let $\mathfrak{F}\subseteq B^{A}$ be a collection of functions from $A$ to $B$ . Then there exists $c\leq 1/\epsilon^{2}$ functions $F_{1},...,F_{c}\in\mathfrak{F}$ such that for every $F\in\mathfrak{F}$ , there is a function $\Gamma_{F}:B^{c}\rightarrow B$ such that:

\Pr_{x\in A}\left[\Gamma_{F}(F_{1}(x),...,F_{c}(x))=F(x)\right]\geq\Pr_{x\in A% }\left[G(x)=F(x)\right]-\epsilon

The lemma shows that $G$ can “estimated” by a only a few functions from $\mathfrak{F}$ . Note that the estimation is close to $G$ compared to every $F\in\mathfrak{F}$ and not necessarily close to $G$ itself.

Finally, we present our main theorem, which shows that under assumptions on the subset ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ , the list decoding radius of polynomials in ${\tilde{X}}$ will be similar to the list decoding radius in $\mathbbm{F}^{n}$ .
In more details (and informally), we show that if ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ is lift-enabler, has the limited-relative-rank-bias-property, the list-decoding count is constant (independent of $n$ ) for every valid $\epsilon$ in distance $\tau=\delta_{\mathbbm{F}}(d)-\epsilon$ . Note that not every $\epsilon>0$ will be valid: the valid values of $\epsilon$ will depend on the limitations of the rank-bias property. Formally, we show the following:

Theorem 76 (List Decoding RM in ${\tilde{X}}$ ).

There exist functions $c_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ and $c_{2}(\mathbbm{F},d,{\tilde{r}},\epsilon)$ such that the following holds: Let $\mathbbm{F}$ be a finite field, and let $d\in\mathbbm{N}$ be an integer that represents a degree. Let ${\tilde{\epsilon}}>0$ , and let ${\tilde{r}}:[{\tilde{\epsilon}},\infty]\rightarrow\mathbbm{N}$ be a limited-relative-rank-bias function.
Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a set with the following properties

1.

${\tilde{X}}$ is $d$ -lift-enabler with a lift operator $\widehat{\square}$ .
2.

${\tilde{X}}$ has the $({\tilde{r}},\mathbbm{F},d,{\tilde{\epsilon}})$ -relative-rank-bias property.

Then, for every $\epsilon\geq c_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ it holds:

\ell_{\mathbbm{F},{\tilde{X}}}(d,\delta_{\mathbbm{F},\mathbbm{F}^{n}}(d)-% \epsilon)\leq c_{2}(\mathbbm{F},d,{\tilde{r}},\epsilon)

Proof.

We follow the lines of the proof of [8, Theorem 1]. Let $\mathbbm{F}$ be a finite field, and let $d\in\mathbbm{N}$ be an integer that represents a degree. Let ${\tilde{\epsilon}}>0$ , and let ${\tilde{r}}:[{\tilde{\epsilon}},\infty]\rightarrow\mathbbm{N}$ be a limited-rank-relative-bias function. Let $c_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ be a function we will specify later. Let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be a set with the properties defined above.
Finally, let $\epsilon\geq c_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ for $c_{1}$ that we will specify later, and let $f:{\tilde{X}}\rightarrow\mathbbm{F}$ be a received word. We wish to bound the amount of polynomials in $Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ that are $(\delta_{\mathbbm{F}}(d)-\epsilon)$ -close to $f$ .
Apply Lemma 75 with $A={\tilde{X}}$ , $B=\mathbbm{F}$ , $G=f$ , $\mathfrak{F}={Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})}$ and approximation parameter $\epsilon/2$ to obtain $\mathfrak{h}\subset Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ , defined by $\mathfrak{h}=(h_{1},...,h_{c})$ where $c\leq 4/\epsilon^{2}$ , such that for every $p\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ there is a function $\Gamma_{p}:\mathbbm{F}^{c}\rightarrow\mathbbm{F}$ that approximates $f$ in ${\tilde{X}}$ relative to $Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ i.e.:

\forall p\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F}):\Pr_{x\in{\tilde% {X}}}\left[\Gamma_{p}(h_{1}(x),...,h_{c}(x))=p(x)\right]\geq\Pr_{x\in{\tilde{X% }}}\left[f(x)=p(x)\right]-\epsilon/2

Let ${{{r}}}_{1},{{{r}}}_{2}:\mathbbm{N}\rightarrow\mathbbm{N}$ be two non-decreasing functions that represents rank that we will specify later. For ${{{r}}}_{1}$ , we will require that for all $m\geq 1$ :

{{{r}}}_{1}(m)\geq\max{\left\{\genfrac{}{}{0.0pt}{}{{{{{r}}}_{2}(C_{{{{r}}}_{2% },d}^{\ref{theorem:regularization-in-X}}(m+1))+C_{{{{r}}}_{2},d}^{\ref{theorem% :regularization-in-X}}(m+1)+1,}}{{{{r}}}_{2}(C_{{{{r}}}_{\ref{preserving-% degree-starting-field}},d}^{\ref{theorem:regularization-in-X}}(m+1))+C_{{{{r}}% }_{\ref{preserving-degree-starting-field}},d}^{\ref{theorem:regularization-in-% X}}(m+1)+1}\right\}}

Note that in the expression above, we denote ${{{r}}}_{\ref{preserving-degree-starting-field}}:\mathbbm{N}\rightarrow% \mathbbm{N}$ , as follows: ${{{r}}}_{\ref{preserving-degree-starting-field}}(c)\coloneqq{{{r}}}_{\ref{% preserving-degree-starting-field}}(\mathbbm{F},d,c)$ .
The reason we chose this ${{{r}}}_{1}$ , is that by our choice of ${{{r}}}_{1}$ we can use the second part of Lemma 64. Specifically, if we start with ${{{r}}}_{1}$ - ${\tilde{X}}$ -regular factor and we ${{{r}}}_{2}$ - ${\tilde{X}}$ -regularize it, we get that the ${{{r}}}_{2}$ - ${\tilde{X}}$ -regular factor that we received is a syntactic refinement of the ${{{r}}}_{1}$ - ${\tilde{X}}$ -regular factor we started with.
As a first step, we lift the polynomial factor to get $\mathcal{H}\coloneqq\widehat{\mathfrak{h}}$ . Note that because $\forall x\in{\tilde{X}}:\widehat{h_{i}}(x)=h_{i}(x)$ , for all $p\in F$ we have:

\Pr_{x\in{\tilde{X}}}\left[\Gamma_{p}(\widehat{h_{1}}(x),...,\widehat{h_{c}}(x% ))=p(x)\right]\geq\Pr_{x\in{\tilde{X}}}\left[f(x)=p(x)\right]-\epsilon/2

Next, we ${{{r}}}_{1}$ - ${\tilde{X}}$ -regularize the factor $\mathcal{B}$ generated by the collection $\mathcal{H}$ by Theorem 64. This gives us a ${{{r}}}_{1}$ - ${\tilde{X}}$ -regular factor $\mathcal{B}^{\prime}$ , which is defined by a set of polynomials $\mathcal{H}^{\prime}\coloneqq(H^{\prime}_{1},...,H^{\prime}_{c^{\prime}})$ of degree $\leq d$ such that $\mathcal{B}^{\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}$ , with $rank_{{\tilde{X}}}\left(\mathcal{H}^{\prime}\right)\geq{{{r}}}(c^{\prime})$ and with bounded amount of polynomials defining it i.e. $c^{\prime}\leq C_{{{{r}}}_{1},d}^{\ref{theorem:regularization-in-X}}(c)$ . We apply Corollary 63 and get that $\mathcal{B}^{\prime}\succeq_{\text{sem}|{\tilde{X}}}\mathcal{B}$ . We then use the fact that $\Gamma_{p}(\widehat{h_{1}}(x),...,\widehat{h_{c}}(x))$ is measurable in respect of $\mathcal{H}$ in ${\tilde{X}}$ , and deduce we have a similar approximation of $p$ using $\mathcal{H}^{\prime}$ as the approximation of $p$ using $\mathcal{H}$ . Formally, there exists a function $\Gamma_{p}^{\prime}:\mathbbm{F}^{c^{\prime}}\rightarrow\mathbbm{F}$ such that:

\Pr_{x\in{\tilde{X}}}\left[\Gamma^{\prime}_{p}(H^{\prime}_{1}(x)),...,H^{% \prime}_{c^{\prime}}(x))=p(x)\right]\geq\Pr_{x\in{\tilde{X}}}\left[f(x)=p(x)% \right]-\epsilon/2

Now we recall that we wished to bound the amount of polynomials $p\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ such that $\Pr_{x\in{\tilde{X}}}\left[f(x)\neq p(x)\right]\leq\delta_{\mathbbm{F}}(d)-\epsilon$ . Let $p\in Poly_{\leq d}({\tilde{X}}\rightarrow\mathbbm{F})$ be a polynomial as we just described. We will show that such $p$ is measurable with respect to $\mathcal{H}^{\prime}$ in ${\tilde{X}}$ . This will upper bound the amount of possible polynomials $p$ by the amount of possible different $\Gamma^{\prime}_{p}:\mathbbm{F}^{c^{\prime}}\rightarrow\mathbbm{F}$ , which is $\left|\mathbbm{F}\right|^{\left\lVert{\mathcal{B}^{\prime}}\right\rVert}=p^{(p% ^{c^{\prime}})}$ , and thus $c_{2}(\mathbbm{F},d,{\tilde{r}},\epsilon)\leq p^{(p^{c^{\prime}})}$ .
By our choice of $c^{\prime}$ we have that $c^{\prime}\leq C_{{{{r}}}_{1},d}^{\ref{theorem:regularization-in-X}}(4/% \epsilon^{2})$ , and thus $c_{2}$ is bounded by a function of $(\mathbbm{F},d,{{{r}}}_{1},\epsilon)$ . Note that we have not yet specified the value of ${{{r}}}_{1}$ , because it is determined by the choice of ${{{r}}}_{2}$ that we will later define its exact values. The important thing about our future choice of ${{{r}}}_{2}$ is that the value of ${{{r}}}_{2}$ must be independent of $n$ , but can depend on $(\mathbbm{F},d,{\tilde{r}},\epsilon)$ . This will conclude the proof.
Now, consider a lift of $p$ , i.e. $P\coloneqq\widehat{p}$ . Note that by the definition of lift $\forall x\in{\tilde{X}}:P(x)=p(x)$ . We will show that $P$ is measurable in respect of $\mathcal{H}^{\prime}$ in ${\tilde{X}}$ .
We consider the factor $\mathcal{B}_{P}$ that is generated by $\mathcal{H}_{P}\coloneqq\mathcal{H}^{\prime}\cup\left\{P\right\}$ . By using Theorem 64, we can ${{{r}}}_{2}$ - ${\tilde{X}}$ -regularize it and get the polynomial factor $\mathcal{B}^{\prime\prime}$ that relative-refines $\mathcal{B}_{P}$ . We denote the set of polynomials in the factor as $\mathcal{H}^{\prime\prime}$ .
Next, notice that the factor $\mathcal{B}^{\prime\prime}$ is a ${{{r}}}_{2}$ -regular factor, therefore by our choice of ${{{r}}}_{1}$ and the second part of Theorem 64, we in fact have $\mathcal{B}^{\prime\prime}\succeq_{\text{syn}}\mathcal{B}^{\prime}$ . This is true because by our choice of ${{{r}}}_{1}$ :

rank_{{\tilde{X}}}\left(\mathcal{H}^{\prime}\right)\geq{{{r}}}_{1}(c^{\prime})% \geq{{{r}}}_{2}(C_{{{{r}}}_{2},d}^{\ref{theorem:regularization-in-X}}(c^{% \prime}+1))+C_{{{{r}}}_{2},d}^{\ref{theorem:regularization-in-X}}(c^{\prime}+1% )+1\geq{{{r}}}_{2}(\left|\mathcal{B}^{\prime\prime}\right|)+\left|\mathcal{B}^% {\prime\prime}\right|+1

And as rank is always bigger than relative rank, we also have:

rank\left(\mathcal{H}^{\prime}\right)\geq{{{r}}}_{1}(c^{\prime})\geq{{{r}}}_{2% }(C_{{{{r}}}_{\ref{preserving-degree-starting-field}},d}^{\ref{theorem:% regularization-in-X}}(c^{\prime}+1))+C_{{{{r}}}_{\ref{preserving-degree-% starting-field}},d}^{\ref{theorem:regularization-in-X}}(c^{\prime}+1)+1

Thus, the polynomials defining $\mathcal{B}^{\prime\prime}$ are in the form $\mathcal{H}^{\prime\prime}\coloneqq\mathcal{H}^{\prime}\cup\left\{H^{\prime% \prime}_{1},...,H^{\prime\prime}_{c^{\prime\prime}}\right\}$ . Note that as promised in Theorem 64, we have $\left|\mathcal{H}^{\prime\prime}\right|=c^{\prime}+c^{\prime\prime}\leq C^{% \ref{theorem:regularization-in-X}_{{{{r}}}_{2},d}}(c^{\prime})$ .
Additionally, by the way we built $\mathcal{H}_{P}$ , the function $P$ is measurable in respect of it. Therefore, as $\mathcal{B}^{\prime\prime}\succeq^{{\tilde{X}}}_{\text{sem}}\mathcal{B}_{P}$ , we have that $P$ is $\mathcal{H}^{\prime\prime}$ -measurable relative to ${\tilde{X}}$ . In other words, there exists $\Phi:\mathbbm{F}^{c^{\prime}+c^{\prime\prime}}\rightarrow\mathbbm{F}$ and $\overline{Pmissing}:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ with $\deg(\overline{Pmissing}),\deg(P-\overline{Pmissing})\leq\deg(P)\leq d$ and $\overline{Pmissing}|_{{\tilde{X}}}\equiv 0$ such that:

\forall a\in\mathbbm{F}^{n}:P(a)=\Phi(H^{\prime}_{1}(a),...,H^{\prime}_{c^{% \prime}}(a),H^{\prime\prime}_{1}(a),...,H^{\prime\prime}_{c^{\prime\prime}}(a)% ))+\overline{Pmissing}(a)

And specifically in ${\tilde{X}}$ we have:

\forall x\in{\tilde{X}}:P(x)=\Phi(H^{\prime}_{1}(x),...,H^{\prime}_{c^{\prime}% }(x),H^{\prime\prime}_{1}(x),...,H^{\prime\prime}_{c^{\prime\prime}}(x)))

Denote $P^{\prime}\coloneqq P-\overline{Pmissing}$ . We will show the polynomial $P^{\prime}$ does not depend on its last $c^{\prime\prime}$ variables, and thus $\Phi$ does not depend on its last $c^{\prime\prime}$ variables. This will imply that $P$ is measurable in respect of $\mathcal{H}^{\prime}$ in ${\tilde{X}}$ , which will conclude the proof.
Now, we choose ${{{r}}}_{2}$ to be such that:

{{{r}}}_{2}(m)\geq\max\left\{{\tilde{r}}\left(\dfrac{\epsilon/4}{\left|% \mathbbm{F}\right|^{m}}\right),{{r}}_{\ref{high-rank-implies-low-bias}}\left(% \dfrac{\epsilon/4}{\left|\mathbbm{F}\right|^{m}}\right),{{r}}_{\ref{preserving% -degree-starting-field}}(m)\right\}

Note that in the expression above we are discussing fixed field and degree, i.e. $\mathbbm{F},d$ . Therefore we denote ${{{r}}}_{\ref{preserving-degree-starting-field}}:\mathbbm{N}\rightarrow% \mathbbm{N}$ as ${{{r}}}_{\ref{preserving-degree-starting-field}}(c)\coloneqq{{{r}}}_{\ref{% preserving-degree-starting-field}}(\mathbbm{F},d,c)$ and ${{{r}}}_{\ref{high-rank-implies-low-bias}}:\mathbbm{N}\rightarrow\mathbbm{N}$ as ${{{r}}}_{\ref{high-rank-implies-low-bias}}(\epsilon)\coloneqq{{{r}}}_{\ref{% high-rank-implies-low-bias}}(\mathbbm{F},d,\epsilon)$ .
Next, we show that even if we change the polynomials in the factor to have a disjoint set of inputs in $\mathbbm{F}^{n}$ , we still obtain a polynomial in the same degree, which have an approximation close to the approximation we had in ${\tilde{X}}$ . Note that after this step, the proof becomes very similar to the proof of list decoding Reed Muller in $\mathbbm{F}^{n}$ [8, Theorem 1]: we omit the dependence of ${\tilde{X}}$ and get the same approximation by functions of multiple variables, as we had in $\mathbbm{F}^{n}$ . This is done by the following lemma:

Lemma 77.

Let $\left\{a^{i},b^{j}\right\},i\in[c^{\prime}],j\in[c^{\prime\prime}]$ be pairwise disjoint sets of $n$ variables each. Let $n^{\prime}\coloneqq n(c^{\prime}+c^{\prime\prime})$ . Let $\vec{P}:\mathbbm{F}^{n^{\prime}}\rightarrow\mathbbm{F}$ and $\vec{f}:\mathbbm{F}^{n^{\prime}}\rightarrow\mathbbm{F}$ be functions of $n^{\prime}$ variables defined as follows:

\vec{P^{\prime}}(\vec{a})\coloneqq\Phi\left(H^{\prime}_{1}(a^{1}),...,H^{% \prime}_{c^{\prime}}(a^{c^{\prime}}),H^{\prime\prime}_{1}(b^{1}),...,H^{\prime% \prime}_{c^{\prime\prime}}(b^{c^{\prime\prime}})\right)

and:

\vec{f}(\vec{a})\coloneqq\Gamma^{\prime}_{p}(H^{\prime}_{1}(a^{1})),...,H^{% \prime}_{c^{\prime}}(a^{c^{\prime}}))

Note that $\vec{f}$ is a function that receives $n^{\prime}$ variables, and ignores its last $c^{\prime\prime}$ variables.
Then:

1.

The degree of $\vec{P^{\prime}}$ remains bounded, i.e. $\deg(\vec{P^{\prime}})\leq d$ .
2.

The approximation of $\vec{f}$ to $\vec{P^{\prime}}$ in $\mathbbm{F}^{n^{\prime}}$ is close to the approximation of $\Gamma^{\prime}_{p}$ to $p$ in ${\tilde{X}}$ . Specifically, we show:

$\left|\Pr_{\vec{a}\in\mathbbm{F}^{n^{\prime}}}\left[\vec{f}(\vec{a})=\vec{P^{% \prime}}(\vec{a})\right]-\Pr_{x\in{\tilde{X}}}\left[\Gamma^{\prime}_{p}(H^{% \prime}_{1}(x)),...,H^{\prime}_{c^{\prime}}(x))=p(x)\right]\right|\leq\epsilon/4$

Proof.

We start by proving the first part of the lemma: bounding the degree of $\vec{P^{\prime}}$ by $d$ . First, we recall that $P^{\prime}=P-\overline{Pmissing}$ where $\overline{Pmissing}$ is a valid remainder. Specifically, we have $\deg(P^{\prime})=\deg(P-\overline{Pmissing})\leq\deg(P)\leq d$ . In addition, by the way we built $\Phi$ we have:

\forall a\in\mathbbm{F}^{n}:P^{\prime}(a)=\Phi(H^{\prime}_{1}(a),...,H^{\prime% }_{c^{\prime}}(a),H^{\prime\prime}_{1}(a),...,H^{\prime\prime}_{c^{\prime% \prime}}(a)))

Thus the function above is of degree $\leq d$ . Moreover, we have:

rank\left(\mathcal{H}^{\prime\prime}\right)\geq rank_{{\tilde{X}}}\left(% \mathcal{H}^{\prime\prime}\right)\geq{{{r}}}_{2}(\left|\mathcal{H}^{\prime% \prime}\right|)\geq{{{r}}}_{\ref{preserving-degree-starting-field}}(\left|% \mathcal{H}^{\prime\prime}\right|)

Therefore we can use Lemma 30 to get that $\deg(\vec{P^{\prime}})\leq\deg(P^{\prime})\leq d$ . Note that in order to use the lemma formally, we had to extend the input space of $P^{\prime}$ to be of $n^{\prime}$ variables (and make it depend only on the first $n$ variables as it used to). Because lemma 30 require bounds independent of $n$ , this is done smoothly.
Now we move to the second part of the lemma: bounding the approximation of $\vec{f}$ to $\vec{P^{\prime}}$ . Denote $S\coloneqq\mathbbm{F}^{c^{\prime}+c^{\prime\prime}}$ , and for each $s\in S$ denote:

p_{1}(s)\coloneqq\Pr_{x\in{\tilde{X}}}\left[\left(H^{\prime}_{1}(x),...,H^{% \prime}_{c^{\prime}}(x),H^{\prime\prime}_{1}(x),...,H^{\prime\prime}_{c^{% \prime\prime}}(x)\right)=s\right]

and as of our choice of ${{{r}}}_{2}$ , we have $rank\left(\mathcal{H}^{\prime\prime}\right)\geq{\tilde{r}}(\epsilon/8\left|S% \right|)$ . Therefore, if we require that the relative rank-bias relation holds for $\epsilon/8\left|S\right|$ , we can use Lemma 81 with $A={\tilde{X}}$ to get that $p_{1}$ is $(\epsilon/8\left|S\right|)$ -almost uniform, i.e:

p_{1}(s)=\dfrac{1\pm\epsilon/8}{\left|S\right|}

We show that this can be done in the following claim by choosing a proper $c_{1}$ :

Claim 78.

One can choose $c_{1}\coloneqq c_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ such that if $\epsilon\geq c_{1}$ we have that $\epsilon/8\left|S\right|\geq c_{1}$ .

Proof.

This is done by using the bound we already know. We need that:

{\tilde{\epsilon}}\leq\dfrac{\epsilon}{8\left|\mathbbm{F}\right|^{c^{\prime}+c% ^{\prime\prime}}}

As $c^{\prime}+c^{\prime\prime}\leq C^{\ref{theorem:regularization-in-X}}_{{{{r}}}% _{2},d}(c^{\prime})$ , for the term above to hold it is enough that the following will be true:

\epsilon\geq{\tilde{\epsilon}}\cdot 8\left|\mathbbm{F}\right|^{C^{\ref{theorem% :regularization-in-X}}_{{{{r}}}_{2},d}(c^{\prime})}

and as ${{{r}}}_{2},c^{\prime}$ and thus also $C^{\ref{theorem:regularization-in-X}}_{{{{r}}}_{2},d}(c^{\prime})$ are independent of $n$ , we can pick $c_{1}=c_{1}(\mathbbm{F},d,{\tilde{r}},{\tilde{\epsilon}})$ and get what we aimed for. $\hfill\vartriangleleft$ Thus, we can assume that $p_{1}$ is $(\epsilon/8\left|S\right|)$ -almost uniform. Now, let:

p_{2}(s)\coloneqq\Pr_{\vec{a}\in\mathbbm{F}^{n^{\prime}}}\left[\left(H^{\prime% }_{1}(a^{1}),...,H^{\prime}_{c^{\prime}}(a^{c^{\prime}}),H^{\prime\prime}_{1}(% b^{1}),...,H^{\prime\prime}_{c^{\prime\prime}}(b^{c^{\prime\prime}})\right)=s\right]

Note that the rank of $\vec{\mathcal{H}}^{\prime\prime}={\left\{H^{\prime}_{1}(a^{1}),...,H^{\prime}_% {c^{\prime}}(a^{c^{\prime}}),H^{\prime\prime}_{1}(b^{1}),...,H^{\prime\prime}_% {c^{\prime\prime}}(b^{c^{\prime\prime}})\right\}}$ , as a factor defined over $\mathbbm{F}^{n^{\prime}}$ , can not be lower than the rank of $\mathcal{H}^{\prime\prime}$ and thus we have $rank\left(\vec{\mathcal{H}}^{\prime\prime}\right)\geq{{r}}_{\ref{high-rank-% implies-low-bias}}\left(\dfrac{\epsilon/8}{\left|\mathbbm{F}\right|^{m}}\right)$ . By using Theorem 23, which shows the rank-bias relation for $\mathbbm{F}^{n^{\prime}}$ , we can similarly use Lemma 81 with $A=\mathbbm{F}^{n^{\prime}}$ to get that $p_{2}$ is also $(\epsilon/8\left|S\right|)$ -almost-uniform, i.e:

p_{2}(s)=\dfrac{1\pm\epsilon/8}{\left|S\right|}

Now, we show the approximations are the same. Denote by $s^{\prime}$ the restriction of $s$ to its first $c^{\prime}$ coordinates, and consider the approximation:

	$\displaystyle\Pr_{\vec{a}\in\mathbbm{F}^{n^{\prime}}}\left[\vec{f}(\vec{a})=% \vec{P}^{\prime}(\vec{a})\right]=$
		$\displaystyle=\sum_{s\in S}{p_{2}(s)\cdot 1_{\Phi(s)=\Gamma_{P}^{\prime}(s^{% \prime})}}$
		$\displaystyle=\sum_{s\in S}{p_{1}(s)\cdot 1_{\Phi(s)=\Gamma_{P}^{\prime}(s^{% \prime})}}\pm\epsilon/4$
		$\displaystyle=\Pr_{x\in{\tilde{X}}}\left[\Gamma^{\prime}_{p}(H^{\prime}_{1}(x)% ),...,H^{\prime}_{c^{\prime}}(x))=p(x)\right]\pm\epsilon/4$

This completes the proof the lemma. $\hfill\blacktriangleleft$

The proof is followed by the same methods used in [8]. We repeat if for completeness. We next restate a lemma proved in [8, Claim 4.2], which is a varaiant of the Schwartz-Zippel lemma [43, 46]:

Lemma 79.

Let $d$ , $n_{1}$ , $n_{2}\in\mathbbm{N}$ be integers. Let $P_{1}\in Poly_{\leq d}(\mathbbm{F}^{n_{1}+n_{2}}\rightarrow\mathbbm{F})$ , and let $F_{1}:\mathbbm{F}^{n_{1}}\rightarrow\mathbbm{F}$ be a function. Assume the polynomial is $\delta_{\mathbbm{F}}(d)$ -close to the function, i.e:

\Pr_{x_{1},...,x_{n_{1}+n_{2}}\in\mathbbm{F}}\left[P_{1}(x_{1},...,x_{n_{1}+n_% {2}})=F_{1}(x_{1},...,x_{n})\right]>1-\delta_{\mathbbm{F}}(d)

Then, $P_{1}$ does not depend on $x_{n_{1}+1},...,x_{n_{1}+n_{2}}$ .

Now, apply Lemma 79 to $P_{1}=\vec{P^{\prime}}$ , $F_{1}=\vec{f}$ , $n_{1}=nc^{\prime}$ , $n_{2}=nc^{\prime\prime}$ . We obtain that $\vec{P^{\prime}}$ does not depend on its last $c^{\prime\prime}$ variables, and thus by denoting $C_{i}\coloneqq H^{\prime\prime}_{i}(0)$ for $i\in\left[c^{\prime\prime}\right]$ we have:

\vec{P^{\prime}}(\vec{a})=\Phi\left(H^{\prime}_{1}(a^{1}),...,H^{\prime}_{c^{% \prime}}(a^{c^{\prime}}),C_{1},...,C_{c^{\prime\prime}}\right)

Now, for every $a\in\mathbbm{F}^{n}$ , if we substitute $a$ in the $i$ -th component of $\vec{a}$ for every $i\in\left[c^{\prime}\right]$ in the equation above, we get the following is true:

P^{\prime}(a)=\Phi\left(H^{\prime}_{1}(a),...,H^{\prime}_{c^{\prime}}(a),C_{1}% ,...,C_{c^{\prime\prime}}\right)

Hence $P^{\prime}$ does not depend on its last $c^{\prime\prime}$ variables. As explained earlier, this implies that $P$ is measurable in respect of $\mathcal{H}^{\prime}$ in ${\tilde{X}}$ . This completes the proof of the theorem. $\hfill\blacktriangleleft$

References

[1] Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and João Ribeiro. Low-degree polynomials are good extractors, 2025. doi:10.48550/arXiv.2405.10297.
[2] Omar Alrabiah, Venkatesan Guruswami, and Ray Li. Randomly punctured reed–solomon codes achieve list-decoding capacity over linear-sized fields, 2024. doi:10.48550/arXiv.2304.09445.
[3] Mitali Bafna and Dor Minzer. Characterizing direct product testing via coboundary expansion, 2024. doi:10.48550/arXiv.2308.09668.
[4] Paul Beame, Shayan Oveis Gharan, and Xin Yang. On the bias of reed-muller codes over odd prime fields, 2018. arXiv:1806.06973.
[5] Ido Ben-Eliezer, Rani Hod, and Shachar Lovett. Random low degree polynomials are hard to approximate. In Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX ’09 / RANDOM ’09, pages 366–377, Berlin, Heidelberg, 2009. Springer-Verlag. doi:10.1007/978-3-642-03685-9_28.
[6] Inbar Ben Yaacov, Yotam Dikstein, and Gal Maor. Sparse high dimensional expanders via local lifts, 2024. doi:10.48550/arXiv.2405.19191.
[7] Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. Every locally characterized affine-invariant property is testable, 2013. arXiv:1212.3849.
[8] Abhishek Bhowmick and Shachar Lovett. List decoding reed-muller codes over small fields, 2014. arXiv:1407.3433.
[9] Abhishek Bhowmick and Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. CoRR, abs/1506.02047, 2015. arXiv:1506.02047.
[10] Andrej Bogdanov. Pseudorandom generators for low degree polynomials. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 21–30, New York, NY, USA, 2005. Association for Computing Machinery. doi:10.1145/1060590.1060594.
[11] Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 41–51, 2007. doi:10.1109/FOCS.2007.42.
[12] Joshua Brakensiek, Manik Dhar, and Sivakanth Gopi. Generalized gm-mds: Polynomial codes are higher order mds, 2024. doi:10.48550/arXiv.2310.12888.
[13] Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, and Zihan Zhang. Ag codes achieve list-decoding capacity over constant-sized fields, 2024. doi:10.48550/arXiv.2310.12898.
[14] Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. Generic reed-solomon codes achieve list-decoding capacity, 2024. arXiv:2206.05256.
[15] Nader Bshouty. Testers and their applications. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS ’14, pages 327–352, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2554797.2554828.
[16] Gil Cohen and Amnon Ta-Shma. Pseudorandom generators for low degree polynomials from algebraic geometry codes. Electron. Colloquium Comput. Complex., TR13, 2013. URL: https://api.semanticscholar.org/CorpusID:13155686.
[17] Harm Derksen and Emanuele Viola. Fooling polynomials using invariant theory. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 399–406. IEEE, 2022. doi:10.1109/FOCS54457.2022.00045.
[18] Yotam Dikstein. New high dimensional expanders from covers, 2022. doi:10.48550/arXiv.2211.13568.
[19] Yotam Dikstein and Irit Dinur. Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers, 2024. doi:10.48550/arXiv.2308.09582.
[20] Dean Doron, Amnon Ta-Shma, and Roei Tell. On hitting-set generators for polynomials that vanish rarely. Comput. Complex., 31(2):16, 2022. doi:10.1007/S00037-022-00229-2.
[21] Zeev Dvir and Amir Shpilka. Noisy interpolating sets for low degree polynomials. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 140–148, 2008. doi:10.1109/CCC.2008.14.
[22] Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk. Optimal pseudorandom generators for low-degree polynomials over moderately large fields, 2024. doi:10.48550/arXiv.2402.11915.
[23] Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, and Chao Yan. Hilbert functions and low-degree randomness extractors, 2024. doi:10.48550/arXiv.2405.10277.
[24] Parikshit Gopalan, Adam R. Klivans, and David Zuckerman. List-decoding reed-muller codes over small fields. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 265–274, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1374376.1374417.
[25] Omri Gotlib, Tali Kaufman, and Shachar Lovett. List decoding quotient reed-muller codes, 2025. doi:10.48550/arXiv.2502.15650.
[26] Roy Gotlib and Tali Kaufman. List agreement expansion from coboundary expansion, 2022. doi:10.48550/arXiv.2210.15714.
[27] W. T. Gowers and Thomas Karam. Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbbm{F}_{p}$ , 2022. arXiv:2209.04932.
[28] Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the gowers norms, 2007. arXiv:0711.3191.
[29] Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions, 2007. arXiv:math/0404188.
[30] Venkatesan Guruswami, Lingfei Jin, and Chaoping Xing. Efficiently list-decodable punctured reed-muller codes, 2017. arXiv:1508.00603.
[31] Venkatesan Guruswami and Chaoping Xing. Hitting sets for low-degree polynomials with optimal density. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 161–168, June 2014. doi:10.1109/CCC.2014.24.
[32] Hamed Hatami, Pooya Hatami, and Shachar Lovett. Higher-order Fourier Analysis and Applications. Now Foundation and Trends, January 2019. doi:10.1561/9781680835939.
[33] Tali Kaufman and Shachar Lovett. Worst case to average case reductions for polynomials, 2008. arXiv:0806.4535.
[34] David Kazhdan and Tamar Ziegler. Polynomial functions as splines, 2018. arXiv:1712.09047.
[35] David Kazhdan and Tamar Ziegler. Extending weakly polynomial functions from high rank varieties, 2019. arXiv:1808.09439.
[36] David Kazhdan and Tamar Ziegler. Properties of high rank subvarieties of affine spaces, 2020. arXiv:1902.00767.
[37] Amichai Lampert and Tamar Ziegler. Relative rank and regularization, 2021. arXiv:2106.03933.
[38] Shachar Lovett. Unconditional pseudorandom generators for low degree polynomials. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 557–562, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1374376.1374455.
[39] Shachar Lovett. MDS matrices over small fields: A proof of the GM-MDS conjecture. CoRR, abs/1803.02523, 2018. arXiv:1803.02523.
[40] Chi-Jen Lu. Hitting set generators for sparse polynomials over any finite fields. In 2012 IEEE 27th Conference on Computational Complexity, pages 280–286, 2012. doi:10.1109/CCC.2012.20.
[41] Shay Moran and Cyrus Rashtchian. Shattered sets and the hilbert function, 2020. arXiv:1511.08245.
[42] Wolfgang M. Schmidt. The density of integer points on homogeneous varieties. Acta Mathematica, 154(3-4):243–296, 1985. doi:10.1007/BF02392473.
[43] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, October 1980. doi:10.1145/322217.322225.
[44] Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 124–127, 2008. doi:10.1109/CCC.2008.16.
[45] Hikmet Yildiz and Babak Hassibi. Optimum linear codes with support constraints over small fields. CoRR, abs/1803.03752, 2018. arXiv:1803.03752.
[46] Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, 1979. URL: https://api.semanticscholar.org/CorpusID:15629042.

Appendix A Equidistribution of Functions

Assume we have a collection of functions $(F_{1},...,F_{c}$ ), where $F_{i}:A\rightarrow\mathbbm{F}$ for some finite set $A$ . We are interested in showing that the functions are equidistributed, which means that their values behave close to independent random variables. We begin by formulating this definition:

Definition 80 (Equidistribution of Functions).

Given $\epsilon>0$ and $A\subseteq\mathbbm{F}^{n}$ , we say a collection of functions $\mathfrak{F}=(F_{1},...,F_{c})$ where $F_{i}:A\rightarrow\mathbbm{F}$ is $\epsilon$ -equidistributed in $A$ if for all $\vec{\alpha}=(\alpha_{1},...,\alpha_{c})\in\mathbbm{F}^{c}$ we have:

\Pr_{x\in A}\left[(F_{1}(x),...,F_{c}(x))=\vec{\alpha}\right]=\frac{1}{\left|% \mathbbm{F}\right|^{c}}\pm\epsilon

The following is a standard lemma that shows that if every linear combination of a collection of functions has low bias, the collection is equidistributed. We repeat the steps of the proof of [32, Lemma 7.24], but here, we think of $A$ as any finite set (and not particularly $\mathbbm{F}^{n}$ ):

Lemma 81.

Let $\epsilon>0$ , and let $A$ be a finite set. Let $\mathfrak{F}=(F_{1},...,F_{c})$ be a collection of functions defined over $A$ , i.e. $F_{i}:A\rightarrow\mathbbm{F}$ . Assume each linear combination of the collection has low bias, i.e. for each $\lambda=(\lambda_{1},...,\lambda_{c})\in\mathbbm{F}^{c}$ such that $\lambda\neq\vec{0}$ we have:

bias_{x\in A}{({\sum_{i=1}^{c}{\lambda_{i}F_{i}}})}<\epsilon

Then, the collection $\mathfrak{F}$ is $\epsilon$ -equidistributed over $A$ .
In particular, for $\epsilon<\frac{1}{\left|\mathbbm{F}\right|^{c}}$ , the lemma shows that each atom of $\mathfrak{F}$ is not empty i.e. for all $\vec{\alpha}$ there is some $x\in A$ such that $(F_{1}(x),...,F_{c}(x))=\vec{\alpha}$ .

Proof.

We wish to show that for each $\vec{\alpha}\in\mathbbm{F}^{c}$ we have:

\Pr_{x\in A}\left[(F_{1}(x),...,F_{c}(x))=\vec{\alpha}\right]=\frac{1}{\left|% \mathbbm{F}\right|}\pm\epsilon

We express the fraction of inputs that are in the atom $\vec{\alpha}$ the following way:

\Pr_{x\in A}\left[(F_{1}(x),...,F_{c}(x))\right]=\mathbbm{E}_{x\in A}\left[% \prod_{i=1}^{c}{1_{[F_{i}(x)=\alpha_{i}]}}\right]

We use the fact that for every $0\neq x\in\mathbbm{F}$ , we have $\sum_{\lambda=0}^{p-1}e\left[\lambda x\right]=0$ , and if $x=0$ we have $\sum_{\lambda=0}^{p-1}e\left[\lambda x\right]=p$ . Therefore, the expression above equals:

=\mathbbm{E}_{x\in A}\left[\prod_{i=1}^{c}\left({\frac{1}{p}\cdot\sum_{\lambda% _{i}=0}^{p-1}{e\left[\lambda_{i}(F_{i}(x)-\alpha_{i})\right]}}\right)\right]=% \\ \frac{1}{p^{c}}\cdot{\mathbbm{E}_{x\in A}\left[\prod_{i=1}^{c}\sum_{\lambda_{i% }=0}^{p-1}{e\left[\lambda_{i}(F_{i}(x)-\alpha_{i})\right]}\right]}

By the definition of character functions, we have that $e\left[a+b\right]=e\left[a\right]\cdot e\left[b\right]$ , and therefore the expression above equals:

\frac{1}{p^{c}}\cdot\sum_{(\lambda_{1},...,\lambda_{c})\in\prod_{i=1}^{c}[0,p-% 1]}\left(\mathbbm{E}_{x\in A}\left[e\left[\sum_{i=0}^{c}{\lambda_{i}(F_{i}(x)-% \alpha_{i})}\right]\right]\right)

Now, we use the fact that:

bias_{x\in A}{({\sum_{i=1}^{c}(\lambda_{i}(F_{i}(x)-\alpha_{i})})}=bias_{x\in A% }{({\sum_{i=1}^{c}(\lambda_{i}F_{i}(x))})}<\epsilon

and get that:

\Pr_{x\in A}\left[(F_{1}(x),...,F_{c}(x))=\vec{\alpha}\right]=\frac{1}{p^{c}}% \cdot\left(1\pm\epsilon\prod_{i=1}^{c}{p}\right)=\frac{1}{\left|\mathbbm{F}% \right|^{c}}\pm\epsilon\

$\hfill\blacktriangleleft$

Appendix B Comparing Ranks

In this section, we compare the definition of rank we used in this paper to another definition of rank used implicitly throughout this paper. This comparison is crucial, as there is no universally accepted definition of rank; different theorems presented throughout this paper employ distinct definitions. We demonstrate that our definition is sufficiently comprehensive, in that a polynomial (or a factor) classified as having high rank according to our criteria also exhibits high rank according to the second implicitly-used definition. While in many cases the comparison may appear straightforward, we include it for the sake of completeness.
Specifically, we compare our definition of rank with the definition established in [37]. The paper [37] extended the original definition of rank that was presented in [42], to include also the concept of relative rank. It is important to note that this definition is specifically defined to subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ that can be expressed as sets in the form ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)$ for some set of polynomials $\tilde{\mathcal{L}}$ , and not to a general set ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .
First, we present a useful notation that is used in the definition presented in [37]:

Notation (Largest Degree Homogenous Part).

For a polynomial $P$ of degree $d$ , we denote by $\mathrm{h}({P})$ its degree- $d$ homogenous component. In other words, $\mathrm{h}({P})$ is the sum of all the monomials of $P$ of degree exactly $d$ . For a set of polynomials $\mathcal{P}=\left\{P_{1},...,P_{c}\right\}$ , we define $\mathrm{h}({\mathcal{P}})\coloneqq\left\{\mathrm{h}({P_{i}})\middle|i=1,...,c\right\}$ .

Next, we present the exact definition of rank for a polynomial:

Definition 82 (Schmidt Rank of a Polynomial).

The schmidt rank of a homogenous polynomial $P:\mathbbm{F}^{n}\rightarrow\mathbbm{F}$ , noted as $schmrank\left(P\right)$ , is the minimal $r$ such that there exist $(Q_{i},H_{i})_{i\in[r]}$ with $\deg{Q_{i}},\deg{H_{i}}<\deg{P}$ such that:

P(x)=\sum_{i=1}^{r}(Q(x)\cdot H(x))

For a general polynomial $P$ of degree $d$ , we set its rank to be the rank of its degree- $d$ homogenous component, i.e. $schmrank\left(P\right)\coloneqq schmrank\left(\mathrm{h}({P})\right)$ .

$\blacktriangleright$ Remark 83 (High rank implies high schmidt rank).

If $rank\left(P\right)\geq 2\cdot r+1$ for some constant $r\in\mathbbm{N}$ , then $schmrank\left(P\right)\geq r$ .

Proof.

For homogenous polynomial $P$ , assume $schmrank\left(P\right)<r$ . Then, there exist $r^{\prime}<r$ such that there exist $(Q_{i},H_{i})_{i=1}^{r^{\prime}}$ with $\deg{Q_{i}},\deg{H}_{i}<\deg P$ such that:

P(x)=\sum_{i=1}^{r^{\prime}}(Q(x)\cdot H(x))

Then we can choose $\Gamma:\mathbbm{F}^{2r^{\prime}}\rightarrow\mathbbm{F}$ to be a sum of multiples of each two consecutive variables to get that $P(x)=\Gamma(Q_{1}(x),H_{1}(x),...,Q_{r^{\prime}}(x),H_{r^{\prime}}(x))$ , where the polynomials are from a degree $<\deg(P)$ . This means that $rank\left(P\right)\leq 2r^{\prime}<2r$ as we requested.
If we do not assume $P$ is homogenous, by adding $P-\mathrm{h}({P})$ as an input to $\Gamma$ , one can create a $\Gamma^{\prime}:\mathbbm{F}^{2r^{\prime}+1}\rightarrow\mathbbm{F}$ which equals to $P$ when substituting the inputs with some polynomials with degree $<\deg{P}$ , which concludes the proof in a similar way. $\hfill\blacktriangleleft$

Next, we present the definition of Schmidt rank of a factor as defined in [37].

Definition 84 (Schmidt Rank of a Factor).

For a factor of homogenous polynomials $\mathcal{P}=(P_{1},...,P_{c})$ , the schmidt rank of the factor is defined as:

schmrank\left(\mathcal{P}\right)\coloneqq\min\left(schmrank\left(\sum_{i=1}^{c% }\lambda_{i}P_{i}\right)\middle|0\neq(\lambda_{1},...,\lambda_{c})\in\mathbbm{% F}^{c}\right)

Similarly, for a factor of general polynomials $\mathcal{P}$ , we set its rank to be the rank of its matching homogenous-factor, i.e. $schmrank\left(\mathcal{P}\right)\coloneqq schmrank\left(\mathrm{h}({\mathcal{P% }})\right)$ For a factor $\mathcal{B}$ generated by $\mathcal{P}$ , we define $schmrank\left(\mathcal{B}\right)\coloneqq schmrank\left(\mathcal{P}\right)$ .

To establish the equivalence of this definition with the one employed throughout the paper, we must first acknowledge two key distinctions between the definitions. The first distinction is that this definition focuses on the largest-degree homogeneous components of the polynomials involved in the factor, rather than considering linear combinations of polynomials from the factor. The second distinction pertains to the treatment of $d$ in the computation of $d$ -rank of each linear combination. This definition uses the degree of the linear combination directly to calculate the rank that participates in the minimum, in contrast to our definition which uses $\max_{i}{\deg(\lambda_{i}P_{i})}$ . Despite these differences, we will demonstrate that both definitions ultimately yield a similar rank assessment, thereby affirming their equivalence.

$\blacktriangleright$ Remark 85 (High Rank Implies High Schmidt Rank for Factors).

Let $\mathcal{P}=\left(P_{1},...,P_{c}\right)$ be a set of polynomials and let ${{r}}\in\mathbbm{N}$ be a positive integer, i.e. ${{r}}>0$ . If $rank\left(\mathcal{P}\right)\geq 2\cdot{{r}}+1$ , then $schmrank\left(\mathcal{P}\right)\geq{{r}}$ .

Proof.

Assume that $schmrank\left(\mathcal{P}\right)\leq{{r}}$ for ${{r}}>0$ . We will show that $rank\left(\mathcal{P}\right)\leq 2{{r}}+1$ . By definition, there exists a linear combination of polynomials in $\mathrm{h}({\mathcal{P}})$ with rank $\leq{{r}}$ . In other words, there exists $\vec{0}\neq\lambda\in\mathbbm{F}^{c}$ such that $schmrank\left(\sum_{i=1}^{c}{\lambda_{i}\mathrm{h}({P_{i}})}\right)\leq{{r}}$ . Denote $\vec{P_{h}}\coloneqq\sum_{i=1}^{c}{\lambda_{i}\mathrm{h}({P_{i}})}$ . As was shown in a previous remark, a rank of a polynomial is smaller than its schmidt rank up to a constant factor, thus $rank\left(\vec{P_{h}}\right)\leq 2{{r}}+1$ (see Remark 83).
Next, we denote $\vec{P}\coloneqq\sum_{i=1}^{c}{\lambda_{i}P_{i}}$ , and $d_{M}\coloneqq\max_{i\in\left[c\right]}{\lambda_{i}P_{i}}$ . Note that $\deg(\vec{P})\leq d_{M}$ . We wish to show that $rank_{d_{M}}\left(\vec{P}\right)\leq 2{{r}}+1$ . First, we observe that the $d_{M}$ -degree homogenous component of $\vec{P_{h}}$ equals the $d_{M}$ -degree homogenous component of $\vec{P}$ . This is true because every highest-degree component of polynomials in the linear combination that generated $\vec{P}$ , also exists in the linear combination that generates $\vec{P_{h}}$ . In particular, all homogenous components of degree $d_{M}$ exists in both linear combinations $\vec{P_{h}}$ and $\vec{P}$ . Therefore, if the degree of $\vec{P}$ equals $d_{M}$ , we have that $rank_{d_{M}}\left(\vec{P}\right)=rank\left(\vec{P}\right)\geq 2{{r}}+1$ . Otherwise, if $\deg(\vec{P})<d_{M}$ , then $rank_{d_{M}}\left(\vec{P}\right)=1\leq 2{{r}}+1$ . This completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Note.

In the case discussed above, if $\deg(\vec{P})<d_{M}$ , then $schmrank\left(\mathcal{P}\right)=0$ .

Proof.

Assume that $\deg(\vec{P})<d_{M}$ . Therefore, the degree of the linear combination $\vec{P}=\sum_{i=1}^{c}{\lambda_{i}P_{i}}$ is strictly smaller than the degree of at least one of the polynomials participating in it. Denote by $\vec{\lambda}^{\star}$ the sub-combination of $\vec{\lambda}$ that consists only the polynomials that participated in $\vec{P}$ that are of degree $=d_{M}$ . Trivially, $\vec{\lambda}^{\star}\neq\vec{0}$ . Additionally, we have $\deg(\sum_{i=1}^{c}{\lambda_{i}^{\star}P_{i}})<d_{M}$ . Now, we use the following observation: the linear combination above, when summing only the homogenous components of each polynomial, equals $0$ , i.e. $\sum_{i=1}^{c}{\lambda_{i}^{\star}\mathrm{h}({P_{i}})}\equiv 0$ . By this, we found a linear combination of $\mathrm{h}({\mathcal{P}})$ that is $\equiv 0$ . Thus by definition, we have $schmrank\left(\mathcal{P}\right)=0$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Note.

This shows that if we compare only the differences in the definition of rank of a factor, i.e. the focus on linear combinations of the largest-degree homogenous components in contrast to the use of the maximal degree $d$ -rank, the two definitions for a rank of a factor are equal up to $\pm 1$ (in case we use the same definition of rank for a single polynomial). To avoid confusion, we omit the exact definitions and respective proof.

We now present the definition of relative rank as stated in [37, Definition 1.6]: We remind the reader that this definition is specifically defined to subsets ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ that can be expressed by ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)$ for some set of polynomials $\tilde{\mathcal{L}}$ , and not to a general set ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ .

Definition 86 (Relative Schmidt Rank of a Polynomial).

The relative schmidt rank of a homogeneous polynomial $P$ relative to a collection of homogeneous polynomials $\tilde{\mathcal{L}}=(L_{1},\ldots,L_{{\tilde{c}}})$ is

shcmrank_{\tilde{\mathcal{L}}}\left({P}\right)\coloneqq\\ \min\left\{schmrank\left(P+\sum_{i=1}^{{\tilde{c}}}{R_{i}L_{i}}\right)\middle|% \deg(L_{i})+\deg(R_{i})\leq\deg(P),\forall i\in[{\tilde{c}}]\right\}

Note that whenever $\deg{L_{i}}>\deg{P}$ , this implies $R_{i}=0$ .
For general polynomial $P$ and general collection of polynomials $\tilde{\mathcal{L}}$ , we define the schmidt rank of the former in respect to the latter by the relative rank of their largest-degree homogenous component, i.e. $shcmrank_{\tilde{\mathcal{L}}}\left({P}\right)\coloneqq shcmrank_{\mathrm{h}({% \tilde{\mathcal{L}}})}\left({\mathrm{h}({P})}\right)$ .

$\blacktriangleright$ Remark 87 (High Relative Rank $\Rightarrow$ High Relative Schmidt Rank).

Let $P$ and $\tilde{\mathcal{L}}=\left\{L_{1},...,L_{{\tilde{c}}}\right\}$ be polynomials, and let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be defined as ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)$ .

If $rank_{{\tilde{X}}}\left(P\right)\geq 2\cdot{{r}}+2$ for some constant ${{r}}\in\mathbbm{N}$ , then $shcmrank_{\tilde{\mathcal{L}}}\left({P}\right)\geq r$ .

Proof.

Let $P$ and $L_{1},...,L_{{\tilde{c}}}$ be polynomials. Assume that $shcmrank_{\tilde{\mathcal{L}}}\left({P}\right)\leq{{r}}$ . Then, there exists $R_{1},...,R_{\tilde{c}}$ with $\deg(L_{i})+\deg(R_{i})\leq\deg(P)$ for all $i\in\left[{\tilde{c}}\right]$ such that:

schmrank\left(\mathrm{h}({P})+\sum_{i=1}^{{\tilde{c}}}{R_{i}\mathrm{h}({L_{i}}% )}\right)\leq{{r}}

Denote $\overline{P_{h}}\coloneqq\sum_{i=1}^{{\tilde{c}}}{R_{i}\mathrm{h}({L_{i}})}$ . As we have shown earlier, a rank of a polynomial is smaller than its schmidt rank up to a constant factor (See Remark 83). Thus:

rank\left(\mathrm{h}({P})+\overline{P_{h}}\right)\leq 2\cdot schmrank\left(% \mathrm{h}({P})+\overline{P_{h}}\right)+1\leq 2\cdot shcmrank_{{\tilde{X}}}% \left({P}\right)+1=2{{r}}+1

Next, we denote the respective remainder polynomial for the non-homogenous analogue, i.e. $\overline{Pmissing}\coloneqq\sum_{i=1}^{{\tilde{c}}}{R_{i}L_{i}}$ . By observing the highest degree homogenous component of each summand, one can see that $\mathrm{h}({P+\overline{Pmissing}})=\mathrm{h}({\mathrm{h}({P})+\overline{P_{h% }}})$ . Therefore, by adding to the decomposition the non higest-degree-homogenous-component, one can see that:

rank\left(P+\overline{Pmissing}\right)\leq rank\left(\mathrm{h}({P})+\overline% {P_{h}}\right)+1\leq 2{{r}}+2

This completes the proof as $rank_{{\tilde{X}}}\left(P\right)\leq rank\left(P+\overline{Pmissing}\right)% \leq 2{{r}}+2$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 88 (Relative Schmidt Rank over Varieties of High Degree).

If the polynomials defining the variety $\tilde{\mathcal{L}}=(L_{1},...,L_{{\tilde{c}}})$ are of degree $>\deg(P)$ , then, $shcmrank_{\tilde{\mathcal{L}}}\left({P}\right)=schmrank\left(P\right)$ . This is true because in this case, in the calculation of the minimum in the definition of relative schmidt rank, we must have $R_{i}=1$ for all $i\in[{\tilde{c}}]$ and therefore the minimum above is simply $rank\left(P\right)$ .
Note that a similar statement holds for factors aswell. If $\mathcal{P}=(P_{1},...,P_{c})$ is a factor of degree $d$ , then if all the polynomials in $\tilde{\mathcal{L}}$ have degree $>d$ , then the statement above is also true i.e. $shcmrank_{\tilde{\mathcal{L}}}\left({\mathcal{P}}\right)=schmrank\left(% \mathcal{P}\right)$ . This is true because for every linear combination of $\mathcal{P}$ has degree $\leq d$ and therefore its relative schimdt rank equals its rank.

Finally, we present the extension of the definition of relative rank for polynomials factors:

Definition 89 (Relative Schmidt Rank of a Factor).

The relative rank of a set of homogenous polynomials $\mathcal{P}=\left\{P_{1},...,P_{c}\right\}$ relative to another collection of polynomials $\tilde{\mathcal{L}}=\left\{L_{1},...,L_{\tilde{c}}\right\}$ is defined as:

shcmrank_{\tilde{\mathcal{L}}}\left({\mathcal{P}}\right)\coloneqq\min\left\{% shcmrank_{\tilde{\mathcal{L}}}\left({\sum_{i=1}^{c}{\lambda_{i}P_{i}}}\right)% \middle|\vec{0}\neq(\lambda_{1},...,\lambda_{c})\in\mathbbm{F}^{c}\right\}

If $\mathcal{P}$ is a general collection of polynomials, then $shcmrank_{\tilde{\mathcal{L}}}\left({\mathcal{P}}\right)\coloneqq shcmrank_{% \tilde{\mathcal{L}}}\left({\mathrm{h}({\mathcal{P}})}\right)$ .
For a factor $\mathcal{B}$ generated by a set of polynomials $\mathcal{P}$ , we define its schmidt rank relative to ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)$ to be $shcmrank_{{\tilde{X}}}\left({\mathcal{B}}\right)\coloneqq shcmrank_{\tilde{% \mathcal{L}}}\left({\mathcal{P}}\right)$ .

$\blacktriangleright$ Remark 90.

Let $\mathcal{P}=\left\{P_{1},...,P_{c}\right\}$ and $\tilde{\mathcal{L}}=\left\{L_{1},...,L_{{\tilde{c}}}\right\}$ be sets of polynomials, and let ${\tilde{X}}\subseteq\mathbbm{F}^{n}$ be defined as ${\tilde{X}}=Z\left(\tilde{\mathcal{L}}\right)$ . Additionally, let ${{r}}\in\mathbbm{N}$ such that ${{r}}>0$ . If $rank_{{\tilde{X}}}\left(\mathcal{P}\right)\geq 2\cdot{{r}}+2$ for some constant ${{r}}\in\mathbbm{N}$ , then $shcmrank_{\tilde{\mathcal{L}}}\left({P}\right)\geq r$ .

Proof.

Assume that $shcmrank_{\tilde{\mathcal{L}}}\left({\mathcal{P}}\right)\leq{{r}}$ . We will show that $rank_{{\tilde{X}}}\left(\mathcal{P}\right)\leq 2{{r}}+2$ . Let $\vec{0}\neq\vec{\lambda}\in\mathbbm{F}^{c}$ be some vector of coefficients. Let $\vec{P}\coloneqq\sum_{i=1}^{c}{\lambda_{i}P_{i}}$ and $\vec{P_{h}}\coloneqq\sum_{i=1}^{c}{\lambda_{i}\mathrm{h}({P_{i}})}$ be the linear combinations of polynomials in $\mathcal{P}$ and $\mathrm{h}({\mathcal{P}})$ with coefficients $\vec{\lambda}$ respectively, and let $d_{M}\coloneqq\max_{i\in\left[c\right]}{\deg(\lambda_{i}P_{i})}$ . Additionally, denote $\hat{{{r}}}\coloneqq shcmrank_{\tilde{\mathcal{L}}}\left({\vec{P_{h}}}\right)% \leq{{r}}$ . It is enough to show that $rank_{{d_{M}},{{\tilde{X}}}}\left(\vec{P}\right)\leq 2\hat{{{r}}}+2$ , If $\deg(\vec{P})<d_{M}$ , then $rank_{{d_{M}},{{\tilde{X}}}}\left(\vec{P}\right)=1\leq 2{{r}}+2$ . Otherwise, if $\deg(\vec{P})=d_{M}$ , then the remark follows from Remark 87 as:

rank_{{d_{M}},{{\tilde{X}}}}\left(\vec{P}\right)=rank_{{\tilde{X}}}\left(\vec{% P}\right)\leq 2\cdot shcmrank_{\tilde{\mathcal{L}}}\left({\vec{P}}\right)+2

Where:

shcmrank_{\tilde{\mathcal{L}}}\left({\vec{P}}\right)shcmrank_{\tilde{\mathcal{% L}}}\left({\mathrm{h}({\vec{P}})}\right)=shcmrank_{\tilde{\mathcal{L}}}\left({% \mathrm{h}({\vec{P_{h}}})}\right)=shcmrank_{\tilde{\mathcal{L}}}\left({\vec{P_% {h}}}\right)=\hat{{{r}}}\

$\hfill\blacktriangleleft$

[bib.bib1] [1] Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and João Ribeiro. Low-degree polynomials are good extractors, 2025. doi:10.48550/arXiv.2405.10297.

[bib.bib2] [2] Omar Alrabiah, Venkatesan Guruswami, and Ray Li. Randomly punctured reed–solomon codes achieve list-decoding capacity over linear-sized fields, 2024. doi:10.48550/arXiv.2304.09445.

[bib.bib3] [3] Mitali Bafna and Dor Minzer. Characterizing direct product testing via coboundary expansion, 2024. doi:10.48550/arXiv.2308.09668.

[bib.bib4] [4] Paul Beame, Shayan Oveis Gharan, and Xin Yang. On the bias of reed-muller codes over odd prime fields, 2018. arXiv:1806.06973.

[bib.bib5] [5] Ido Ben-Eliezer, Rani Hod, and Shachar Lovett. Random low degree polynomials are hard to approximate. In Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX ’09 / RANDOM ’09, pages 366–377, Berlin, Heidelberg, 2009. Springer-Verlag. doi:10.1007/978-3-642-03685-9_28.

[bib.bib6] [6] Inbar Ben Yaacov, Yotam Dikstein, and Gal Maor. Sparse high dimensional expanders via local lifts, 2024. doi:10.48550/arXiv.2405.19191.

[bib.bib7] [7] Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. Every locally characterized affine-invariant property is testable, 2013. arXiv:1212.3849.

[bib.bib8] [8] Abhishek Bhowmick and Shachar Lovett. List decoding reed-muller codes over small fields, 2014. arXiv:1407.3433.

[bib.bib9] [9] Abhishek Bhowmick and Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. CoRR, abs/1506.02047, 2015. arXiv:1506.02047.

[bib.bib10] [10] Andrej Bogdanov. Pseudorandom generators for low degree polynomials. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 21–30, New York, NY, USA, 2005. Association for Computing Machinery. doi:10.1145/1060590.1060594.

[bib.bib11] [11] Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 41–51, 2007. doi:10.1109/FOCS.2007.42.

[bib.bib12] [12] Joshua Brakensiek, Manik Dhar, and Sivakanth Gopi. Generalized gm-mds: Polynomial codes are higher order mds, 2024. doi:10.48550/arXiv.2310.12888.

[bib.bib13] [13] Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, and Zihan Zhang. Ag codes achieve list-decoding capacity over constant-sized fields, 2024. doi:10.48550/arXiv.2310.12898.

[bib.bib14] [14] Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. Generic reed-solomon codes achieve list-decoding capacity, 2024. arXiv:2206.05256.

[bib.bib15] [15] Nader Bshouty. Testers and their applications. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS ’14, pages 327–352, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2554797.2554828.

[bib.bib16] [16] Gil Cohen and Amnon Ta-Shma. Pseudorandom generators for low degree polynomials from algebraic geometry codes. Electron. Colloquium Comput. Complex., TR13, 2013. URL: https://api.semanticscholar.org/CorpusID:13155686.

[bib.bib17] [17] Harm Derksen and Emanuele Viola. Fooling polynomials using invariant theory. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 399–406. IEEE, 2022. doi:10.1109/FOCS54457.2022.00045.

[bib.bib18] [18] Yotam Dikstein. New high dimensional expanders from covers, 2022. doi:10.48550/arXiv.2211.13568.

[bib.bib19] [19] Yotam Dikstein and Irit Dinur. Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers, 2024. doi:10.48550/arXiv.2308.09582.

[bib.bib20] [20] Dean Doron, Amnon Ta-Shma, and Roei Tell. On hitting-set generators for polynomials that vanish rarely. Comput. Complex., 31(2):16, 2022. doi:10.1007/S00037-022-00229-2.

[bib.bib21] [21] Zeev Dvir and Amir Shpilka. Noisy interpolating sets for low degree polynomials. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 140–148, 2008. doi:10.1109/CCC.2008.14.

[bib.bib22] [22] Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk. Optimal pseudorandom generators for low-degree polynomials over moderately large fields, 2024. doi:10.48550/arXiv.2402.11915.

[bib.bib23] [23] Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, and Chao Yan. Hilbert functions and low-degree randomness extractors, 2024. doi:10.48550/arXiv.2405.10277.

[bib.bib24] [24] Parikshit Gopalan, Adam R. Klivans, and David Zuckerman. List-decoding reed-muller codes over small fields. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 265–274, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1374376.1374417.

[bib.bib25] [25] Omri Gotlib, Tali Kaufman, and Shachar Lovett. List decoding quotient reed-muller codes, 2025. doi:10.48550/arXiv.2502.15650.

[bib.bib26] [26] Roy Gotlib and Tali Kaufman. List agreement expansion from coboundary expansion, 2022. doi:10.48550/arXiv.2210.15714.

[bib.bib27] [27] W. T. Gowers and Thomas Karam. Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbbm{F}_{p}$ , 2022. arXiv:2209.04932.

[bib.bib28] [28] Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the gowers norms, 2007. arXiv:0711.3191.

[bib.bib29] [29] Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions, 2007. arXiv:math/0404188.

[bib.bib30] [30] Venkatesan Guruswami, Lingfei Jin, and Chaoping Xing. Efficiently list-decodable punctured reed-muller codes, 2017. arXiv:1508.00603.

[bib.bib31] [31] Venkatesan Guruswami and Chaoping Xing. Hitting sets for low-degree polynomials with optimal density. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 161–168, June 2014. doi:10.1109/CCC.2014.24.

[bib.bib32] [32] Hamed Hatami, Pooya Hatami, and Shachar Lovett. Higher-order Fourier Analysis and Applications. Now Foundation and Trends, January 2019. doi:10.1561/9781680835939.

[bib.bib33] [33] Tali Kaufman and Shachar Lovett. Worst case to average case reductions for polynomials, 2008. arXiv:0806.4535.

[bib.bib34] [34] David Kazhdan and Tamar Ziegler. Polynomial functions as splines, 2018. arXiv:1712.09047.

[bib.bib35] [35] David Kazhdan and Tamar Ziegler. Extending weakly polynomial functions from high rank varieties, 2019. arXiv:1808.09439.

[bib.bib36] [36] David Kazhdan and Tamar Ziegler. Properties of high rank subvarieties of affine spaces, 2020. arXiv:1902.00767.

[bib.bib37] [37] Amichai Lampert and Tamar Ziegler. Relative rank and regularization, 2021. arXiv:2106.03933.

[bib.bib38] [38] Shachar Lovett. Unconditional pseudorandom generators for low degree polynomials. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 557–562, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1374376.1374455.

[bib.bib39] [39] Shachar Lovett. MDS matrices over small fields: A proof of the GM-MDS conjecture. CoRR, abs/1803.02523, 2018. arXiv:1803.02523.

[bib.bib40] [40] Chi-Jen Lu. Hitting set generators for sparse polynomials over any finite fields. In 2012 IEEE 27th Conference on Computational Complexity, pages 280–286, 2012. doi:10.1109/CCC.2012.20.

[bib.bib41] [41] Shay Moran and Cyrus Rashtchian. Shattered sets and the hilbert function, 2020. arXiv:1511.08245.

[bib.bib42] [42] Wolfgang M. Schmidt. The density of integer points on homogeneous varieties. Acta Mathematica, 154(3-4):243–296, 1985. doi:10.1007/BF02392473.

[bib.bib43] [43] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, October 1980. doi:10.1145/322217.322225.

[bib.bib44] [44] Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 124–127, 2008. doi:10.1109/CCC.2008.16.

[bib.bib45] [45] Hikmet Yildiz and Babak Hassibi. Optimum linear codes with support constraints over small fields. CoRR, abs/1803.03752, 2018. arXiv:1803.03752.

[bib.bib46] [46] Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, 1979. URL: https://api.semanticscholar.org/CorpusID:15629042.

List Decoding Quotient Reed-Muller Codes

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

The Quotient Code

Definition 1 (The X~-Induced Code).

Definition 2 (The X~-Quotient Code).

Importance of Definition

Our Question

Reed-Muller Codes

Notation 3 (The X~-Induced Reed-Muller Code).

Properties of Induced Reed-Muller Codes

Our Results

Theorem (List Decoding Quotient Reed-Muller Code).

Corollary (List Decoding Quotient Reed-Muller Code: High Rank Variety).

Example 4.

Main Technical Challenge

Introducing New Tools

1.1 Comparison to Related Work

Theorem 5 ([8, Theorem 1]).

1.2 Proof Overview

Measurablity and Regularization in 𝔽𝒏

Definition 6 (Measurable).

𝑿~-Relative Rank

Definition 7 (Relative Rank, informal. See definition 48).

1.2.1 𝑿~-Measurablity and The 𝑿~-Relative Regularization Process

Definition 8 (X~-measurable, Incomplete Definition).

Definition 9 (X~-measurable).

Theorem 10 (Relative Regularization Process, Informal, See Theorem 64).

1.2.2 List Decoding in 𝑿~ via 𝑿~-Relative Regularization

1.3 Organization

2 Preliminaries

2.1 Basic Definitions and Notations

2.2 Polynomials in 𝔽𝒏

Definition 11 (Polynomial: Global Definition).

▶ Note 12.

Definition 13 (Derivative).

Lemma 14.

Definition 15 (Local Degree).

Lemma 16 (Equivalance of definitions of a degree).

▶ Remark 17.

2.3 Rank-bias in 𝔽𝒏

Definition 18 (Bias).

Definition 19 (Rank of a Polynomial).

Definition 20 (Factor).

Notation.

Definition 21 (Polynomial Factor).

▶ Note.

Definition 22 (Rank of a Factor).

▶ Note.

Theorem 23 (Rank-bias in 𝔽n).

▶ Remark 24.

2.4 Regularization in 𝔽𝒏

Definition 25 (Measureable).

▶ Remark 26.

Definition 27 (Syntactic Refinement).

Definition 28 (Semantic Refinement).

▶ Remark 29.

Lemma 30 (Preserving Degree in 𝔽n).

Lemma 31 (Faithful Composition).

Definition 32.

Lemma 33 (Regularization in 𝔽n).

▶ Note.

3 Polynomials in 𝑿~

Definition 34 (Cubes).

Definition 35 (Polynomials in X~).

▶ Note.

3.1 Lifting Polynomials

▶ Remark 36.

Definition 37 (d-lift-enabler Subset).

▶ Remark 38.

Definition 39 (The Lift Operator).

Definition 1 (The ${\tilde{X}}$ -Induced Code).

Definition 2 (The ${\tilde{X}}$ -Quotient Code).

Notation 3 (The ${\tilde{X}}$ -Induced Reed-Muller Code).

Measurablity and Regularization in $\mathbbm{F}^{n}$

${\tilde{X}}$ -Relative Rank

1.2.1 ${\tilde{X}}$ -Measurablity and The ${\tilde{X}}$ -Relative Regularization Process

Definition 8 ( ${\tilde{X}}$ -measurable, Incomplete Definition).

Definition 9 ( ${\tilde{X}}$ -measurable).

1.2.2 List Decoding in ${\tilde{X}}$ via ${\tilde{X}}$ -Relative Regularization

2.2 Polynomials in $\mathbbm{F}^{n}$

$\blacktriangleright$ Note 12.

$\blacktriangleright$ Remark 17.

2.3 Rank-bias in $\mathbbm{F}^{n}$

$\blacktriangleright$ Note.

$\blacktriangleright$ Note.

Theorem 23 (Rank-bias in $\mathbbm{F}^{n}$ ).

$\blacktriangleright$ Remark 24.

2.4 Regularization in $\mathbbm{F}^{n}$

$\blacktriangleright$ Remark 26.

$\blacktriangleright$ Remark 29.

Lemma 30 (Preserving Degree in $\mathbbm{F}^{n}$ ).

Lemma 33 (Regularization in $\mathbbm{F}^{n}$ ).

$\blacktriangleright$ Note.

3 Polynomials in ${\tilde{X}}$

Definition 35 (Polynomials in ${\tilde{X}}$ ).

$\blacktriangleright$ Note.

$\blacktriangleright$ Remark 36.

Definition 37 ( $d$ -lift-enabler Subset).

$\blacktriangleright$ Remark 38.

$\blacktriangleright$ Remark 42.

$\blacktriangleright$ Remark 44.

$\blacktriangleright$ Note.

Definition 49 ( ${\tilde{X}}$ -equivalent and ${\tilde{X}}$ -remainder).

$\blacktriangleright$ Note 50.

Corollary 53 ( $\mathbbm{F}^{n}$ has the relative rank-bias property).

$\blacktriangleright$ Note.

$\blacktriangleright$ Remark 56.

$\blacktriangleright$ Remark 57.

5 Regularization Relative to ${\tilde{X}}$

Definition 59 (Measurable Relative to ${\tilde{X}}$ ).

$\blacktriangleright$ Note.

$\blacktriangleright$ Note.

$\blacktriangleright$ Remark 60.

Definition 61 (Semantic Refinement Relative to ${\tilde{X}}$ ).

$\blacktriangleright$ Note.

$\blacktriangleright$ Remark 62.

6 Radius of Reed-Muller over ${\tilde{X}}$

$\blacktriangleright$ Remark 71.

7 List Decoding Reed Muller Over ${\tilde{X}}$

Definition 73 (List Decoding in ${\tilde{X}}$ ).

Theorem 74 (List Decoding RM in $\mathbbm{F}^{n}$ ).

Theorem 76 (List Decoding RM in ${\tilde{X}}$ ).