The simplest proximity-to-low-degree-polynomial test and how to rehabilitate approximate polynomials

Introduction

This post is an apetizer for a blog post in preparation on the FRI protocol. We describe what is arguably the simplest of all proof of proximity (to low degree polynomial functions)^[1] scheme out there. Here and elsewhere, low degree means "of degree

$\le d$" for some fixed positive integer

$d$. But our interest in this scheme is as a means to shed light on a 👻 dual 👻 problem to that of proximity testing.

This scheme was originally described in the 1991 paper Self Testing/Correcting for Polynomials and Approximate Functions by P. Gemmel, R. Lipton, R. Rubinfeld, M. Sudhan and A. Widegerson (we shall sometimes use the acronym GLRSW). It has been referred to as "Sudhan

$d+1$" or some variation on that name in presentations on FRI given by Eli Ben Sasson. In StarkWare's blogpost on Low Degree Testing, it is what is called "the direct test".

Compared to modern proof of proximity schemes such as FRI it is spectacularly inefficient: it runs in linear time

$O(d)$ as opposed to FRI's polylogarithmic time

$O(\ln (d{)}^2)$. However, it has the advantage of sheer simplicity:

• there is only ever one map at play (as opposed to the
  $O(\ln (d))$ inter-dependent maps in FRI);
• coherence is checked for that one map as opposed to having a "trickle down" sequence of coherence conditions relating all the maps in that sequence;
• the redundancy property at the heart of this scheme is second nature to anyone familiar with polynomial interpolation.

Also, proving its "soundness properties", while involved, follows a clear path. It also illustrates well a popular outlook for proving soundness: "deal with the good cases in detail, don't bother analyzing what happens in the bad cases except for bounding the probability of something bad happening in the first place". Usually the good case is when everything happens according to plan, bad cases are everything else. This makes the GLRSW scheme a perfect entry point into proof of proximity schemes.

---

• The simplest proximity-to-low-degree-polynomial test and how to rehabilitate approximate polynomials
  • Introduction
  • Role of proofs of proximity in transparent computational integrity schemes
  • Proofs of proximity vs the GLRSW scheme
  • The barren wasteland of the space of all maps
  • The civilizing influence of low degree maps on their neighbors
    • A neighborhood of maps
    • … Taming / civilizing influence?
  • Polynomials <=> built in redundancy
  • An inefficient proximity test
    • A simple criterion to rule out maps that are far from low degree maps
    • On the wastefulness of this test
  • Outline of the GLRSW scheme
• Details
  • Conventions
  • A quick rundown
    • Step 1: Characterizing low-degreeness
    • The helper function g
    • Step 2: Analyzing the helper function and drawing conclusions
  • Low-degreeness implies redundancy
  • Redundancy implies low degreeness
  • Expected value of interpolation: the helper function g
  • Lemma 1 - the helper function and the oracle agree a lot
  • Lemma 2 - the helper function and the oracle agree a lot
  • Lemma 3 - the helper function is a low degree polynomial
  • Conclusion
  • A question

---

Role of proofs of proximity in transparent computational integrity schemes

We somewhat cryptically indicated that GLRSW is really about a dual problem to that of low-degree proximity testing. Let us try to explain that claim. So before we go any further: what are proof of proximity schemes and what are they useful for? Certainly the main use-case relevant to blockchain related applications is as part of computational integrity schemes.

Computational integrity schemes such as STARKs or SNARKs and many others are protocols whereby a prover can convince a verifier that a complex and/or confidential computation was performed as advertized. The tremedous appeal of such schemes comes from the existence of computational integrity schemes that are

• far quicker to verify than it is to run the computation,
• leak no private information,
• are nigh impossible to twist into producing false positives.

Such schemes rely on a prover to construct a proof of computational integrity. The prover's work can be broadly separated into two phases.

The first phase, common to all such schemes^[2], is the arithmetization of the computation (R1CS or algebraic execution trace for instance). The raw data produced during the computation is converted into algebraic form (typically field elements) which in turn is condensed into polynomial form by means of polynomial interpolation^[3]. Polynomials are useful in this regard: besides addition and scalar multiplication^[4], they support products and divisibility. Importantly, this first phase can be done so that computational integrity (i.e. validity of the underlying computation) is equivalent to the satisfaction of some algebraic constraints by the resulting polynomials. Typically low-degreeness and divisibility conditions.

The second phase, i.e. actually compiling the proof, comes down to finding an efficient commitment of these polynomials. This commitment should allow a verifier to convince themselves of the claim to be proven. In particular, of low-degreeness and divisibility conditions that may apply. There are various ways of doing this, and (at least) two competing philosophies for carrying out the second step.

Philosophy 1: use opaque data and secrets to force the prover down a particular path; valid proofs are those producing ultra-rare collisions. The verifier thus generates some secrets along with associated opaque data (hidden behind a hard discrete log problem, say) called the proving key to be handed to the prover. The proving key is generated in such a way that for one to generate a convincing proof from it, one has to

1. either comply with the verifier and produce a proof according to protocol; such proofs encode polynomials that are low-degree by construction;
2. or successfully break a cryptographically hard problem (e.g. variants of discrete log computations).

For checking divisibility conditions, the relevant fact is that two distinct low degree polynomials

$P$ and

$Q$ virtually never^[5] produce a collision when evaluated at a random (secret) point. Thus, producing an exceedingly rare collision

$P(s)=Q(s)$ at a random (secret) point

$s$ is seen as strong supporting evidence for the claim "

$P=Q$ ". By extension, a collision of the form

$A(s)\cdot H(s)=B(s)$ is interpreted as strong evidence for a divisibility claim "

$A\mid B$ ".

Philosophy 2: no secrets, find another way to enforce low-degreeness / divisibility conditions. Schemes of the first kind had low-degreeness baked into them. For schemes where the prover isn't forced down a narrow path for constructing polynomial commitments, this is no longer the case.

This is immediately problematic: producing collisions between polynomials becomes easy if one is free to use large degree polynomials. Checking for low-degreness thus becomes the central problem. And a difficult problem it certainly is. Checking low-degreeness on the nose is computationnally demanding, at least as demanding as the original computation the verifier may wish to bypass. Proofs of proximity to low-degree maps are an efficient substitute for on the nose low-degree tests. They don't prove that a map is low-degree, they show that a map

$f$ is (likely) in the immediate neighborhood of some low degree map whose properties may be extracted by other means from

$f$.

Once the verifier has sufficient supporting evidence for believing in low-degreeness (or at least proximity to a low degree map), checking divisibilty conditions follows much of the same path as before: open commitments at a random points

$r$ (that usually need not be secret) and check

$A(r)\cdot H(r)\stackrel{?}{=}B(r)$ in the clear.

Proofs of proximity vs the GLRSW scheme

The GLRSW scheme we will describe below can be seen as a crude means to discriminate between maps. To distinguish between those that are very close to being polynomial and those that are far from polynomial. In that sense it can work like a proof of proximity scheme. Indeed, the purpose of such a scheme is to

• ACCEPT with probability 1 low degree polynomial functions
• REJECT with high probability maps that are far from any low degree polynomial function.

The behaviour of such a proof of proximity scheme is illustrated below: low degree maps (here the central red dot) are to be accepted all the time, maps that are outside of some small neighborhood of the set of low degree polynomial maps are to be rejected with high probability.

And then there is a grey area (a small Hamming neighborhood of some low degree polynomial map) where the test's behaviour is unspecified. The GLRSW scheme on the other hand fulfils the complementary (or dual) role of "discovering" the nearest low degree map when fed one of maps in that small neighborhood.

• Proofs of proximity can be seen as means of amplifying the distinction between polynomial maps and their distant neighbors,
• the GLRSW scheme can be understood as contracting small neighborhoods of polynomial functions onto that polynomial function.

So while proof of proximity schemes are in the business of discrimination, GLRSW is in the business of rehabilitation. The next section are our attempt to make explicit the above picture.

The barren wasteland of the space of all maps

Let us think for a moment about the space

$\mathcal{F}$ of all maps

$f:\mathbb{F}\to \mathbb{F}$

$$\mathcal{F}=\left\{\begin{array}{c}\text{the space of all}\\ \text{set maps }\mathbb{F}\to \mathbb{F}\end{array}\right\}$$ (similar mental pictures will apply to the space of all maps

$S\to \mathbb{F}$ for some large subset

$f:S\subset \mathbb{F}$). When

$\mathbb{F}$ is a large finite field,

$\mathcal{F}$ is a very large set:

$$\mathrm{\#}\mathcal{F}=(\mathrm{\#}\mathbb{F}{)}^{\mathrm{\#}\mathbb{F}}$$ For instance, if

$\mathbb{F}$ is a 256 bit prime field, we get

$\mathrm{\#}\mathcal{F}\approx 2^{2^{264}}$. In other words,

$\mathcal{F}$'s size is beyond comprehension. Most of the points in that space^[6] are totally unstructured ''random'' maps.

The overwhelming majority of points of

$\mathcal{F}$ are maps whose interpolation polynomial has degree

$\mathrm{\#}\mathbb{F}$.

Indeed, there are only

$(\mathrm{\#}\mathbb{F}{)}^{\mathrm{\#}\mathbb{F}-1}$ polynomial maps of degree

$<\mathrm{\#}\mathbb{F}$, i.e. the probability of stumbling on a polynomial maps of degree

$<\mathrm{\#}\mathbb{F}$ by chance is

$1/(\mathrm{\#}\mathbb{F})\approx 2^{-256}$.

For all intents and purposes low degree maps don't exist.

For instance, if we consider the collection of all polynomial maps of degree

$\le {10}^9$, a very reasonable bound for any real world application, the likelyhood of stumbling on such a function by chance is 1 in

$(\mathrm{\#}\mathbb{F}{)}^{\mathrm{\#}\mathbb{F}-{10}^9}$ which is, for a 256 bit field,

$⋘$ than 1 in

$2^{2^{263}}$.

The civilizing influence of low degree maps on their neighbors

A neighborhood of maps

While low degree maps are exceedingly rare they do, of course, exist. Furthermore, they exert a taming influence on their immediate neighbor functions. When talking about neighboring functions we are implicitly talking about distances between maps. To measure distances between maps, i.e. points in

$\mathcal{F}$, we use Hamming distance. The Hamming distance

$d(f,g)\in [0,1]$ between two maps

$f,g:S\to \mathbb{F}$ is the proportion of inputs in

$S$ on which they differ. Thus if

$f=g$ they differ on no inputs and

$d(f,g)=0$ while if for all

$s\in S,f(s)\ne g(s)$ then

$d(f,g)=1$. Thus, for any

$ϵ>0$ we can consider the "neighborhood of

$f\in \mathcal{F}$" comprised of all maps

$g$ with

$d(f,g)<ϵ$.

The picture below is a mental picture of a neighborhood of a low degree map

$\text{color}redP$ in

$\mathcal{F}$. It's a pretty large picture, and opening it in a new window will make its features clearer.

In it we depict

• a low degree map
  $\text{color}redP$,
• a somewhat close neighbor
  $\text{color}orangef$ with, say,
  $d(\text{color}orangef,\text{color}redP)\approx .001$)
• a slightly remote neighbor
  $\text{color}greeng$ with, say,
  $d(\text{color}greeng,\text{color}redP)\approx .1$)
• and a map
  $\text{color}blueh$ that bears some ressemblance (yet not all that much) with
  $\text{color}redP$, say
  $h$ with
  $d(\text{color}blueh,\text{color}redP)\approx .5$).

The white halo around

$\text{color}redP$ is meant to represent the small neighborhood on which the civilizing influence of

$\text{color}redP$ can be felt. And then there is a dense and featureless blue ocean of "generic maps".

… Taming / civilizing influence?

What do we mean by "taming influence"? First of all, let us say clearly what we don't mean. We don't mean to suggest that close neighbors of a low degree map

$\text{color}redP$ are themselves low degree … Far from it. Close neighbors are overwhelmingly likely to be of degree

$\mathrm{\#}\mathbb{F}$, the maximum degree possible… Yet, to the casual observer working with incomplete information (e.g. a probabilistic polynomial time Turing machine with oracle access to a close neighbor of

$\text{color}redP$) they are nigh indistinguishable from the polynomial map

$\text{color}redP$ in whose light they bask. Indeed …

Close neighbors of low degree maps exhibit many of the same local redundancies which characterize low degree maps.

Let us qualify that statement: they do with exceedingly high probability. When tested on random inputs:

• maps that are close to a polynomial exhibit many of the local redundancies exhibited by low degree polynomials
• maps that are far from low degree polynomial maps don't.

This loose dichotomy is the basis for proofs of proximity. We can probabilistically test for proximity to a polynomial by checking if the map in question exhibits the expected amount of redundancies.

Polynomials <=> built in redundancy

Let us now be slightly more clear about the way in which polynomials exhibit redundancy. This is pretty basic stuff (interpolation understood using linear algebra) and can nicely be illustrated. In one word this boils down to the fact that the space

${\mathcal{P}}_d$ of polynomial maps of degree

$<d$ is a vector space of dimension

$d$ and the linear functions " evaluation at

$x_i$,

$i=1,\dots ,d$ "

$${\mathrm{ev}}_{x_i}:\{\begin{array}{rcl}{\mathcal{P}}_d& ⟶& \mathbb{F}\\ f& ⟼& f(x_i)\end{array}$$ for distinct points

$x_1,x_2,\dots ,x_d\in \mathbb{F}$ form a basis of the dual space

${\mathcal{P}}_d^{\ast }$.

So, for instance, while there is a whole " line's worth " of polynomial maps

$f$ of degree

$<2$ satisfying the constraint

$f(x_1)=y_1$, there is but one polynomial map of degree

$<2$ satisfying the extra constraint

$f(x_2)=y_2$, as depicted below:

Single Constraint	Two constraints

Similarly there is a whole " line's worth " of polynomial maps

$f$ of degree

$<3$ satisfying the constraints

$f(x_1)=y_1$ and

$f(x_2)=y_2$ (whatever the values

$y_1,y_2$ as long as

$x_1\ne x_2$), but there is only one polynomial map of degree

$<3$ satisfying the extra constraint

$f(x_3)=y_3$, as depicted below:

Two Constraints	Three constraints

This is simply expressing the fact that for distinct

$x_1,\dots ,x_d\in \mathbb{F}$ the " evaluation at

$x_i$ linear forms " form a basis of the dual

${\mathcal{P}}_d^{\ast }$.

Its (ante)dual basis is the basis of Lagrange polynomials. Indeed, to produce the only polynomial function

$f\in {\mathcal{P}}_d$ such that

$f(x_i)=y_i$ for

$i=1,\dots ,d$, one forms

$f=\sum _{i=1}^d{y}_i{L}_i$ where the Lagrange polynomials of the set

$\{x_1,\dots ,x_d\}$:

$$L_i=\prod _{\begin{array}{c}1\le j\le d\\ j\ne i\end{array}}\frac{X-x_j}{x_i-x_j}$$

The fact that the family of linear functionals

$({\mathrm{ev}}_{x_1},\dots ,{\mathrm{ev}}_{x_d})$ forms a basis of the space of linear functionals on

${\mathcal{P}}_d$ also means that evaluations at points

$x\in \mathbb{F}\setminus \{x_1,\dots ,x_d\}$ can be expressed as linear combinations of evaluations at the

$x_i$. This accounts for the " in-built redundancy " of polynomial maps.

Indeed, if

$f$ is a degree

$<d$ polynomial function we can compute

$f(x)$ for any

$x$ by plugging

$x$ into the formula above and using its values at the

$x_i$:

$$f(x)=\sum _{i=1}^d{L}_i(x)\cdot f(x_i)$$ or, if we write

${\lambda }_i^x=L_i(x)$,

$$f(x)=\sum _{i=1}^d{\lambda }_i^x\cdot f(x_i).$$

An inefficient proximity test

We describe a (crude) proximity test to low-degree polynomials. The redundancy within low-degree polynomials is at the heart of it. As we tried to suggest earlier, these redundancies remain by and large true for functions that are very close to low degree polynomial functions. This, in spite of the fact that these functions are hopelessly high degree polynomial functions. These maximal degree polynomial maps do their darndest to emulate low degree maps. These maps will usually pass the following test:

The number of repetitions

$N$ required will depend on a target soundness.

A simple criterion to rule out maps that are far from low degree maps

Let us put

$ϵ=d(f,{\mathcal{P}}_d)⋘1$: in other words, there is some low-degree polynomial

$P_f$ that agrees with

$f$ on a random input with probability

$1-ϵ$. Then the equation

$$f(x)\stackrel{?}{=}\sum _{i=1}^d{\lambda }_i^x\cdot f(x_i),$$ for randomly and independently sampled

$x,x_1,\dots ,x_d\in \mathbb{F}$ is satisfied with probability at least

$(1-ϵ{)}^{d+1}$^[7] and fails with probability at least

$(d+1)ϵ\cdot (1-ϵ{)}^d$^[8]. Using these simple estimates and fixing some desired threshold

${ϵ}_0$ one can find

$N$ so that with overwhelming probability the test will reject maps that are at least

${ϵ}_0$ far from low degree.

On the wastefulness of this test

One could establish "soundness results" for this test. The proof sketched below would likely adapt, albeit with a much larger parameter space:

${\mathbb{F}}^{d+1}$ as opposed to

${\mathbb{F}}^2$. But one should note that this test is particularly impractical. The reason is that every cycle requires recomputing a whole new set of weights

${\lambda }_1^x,\dots ,{\lambda }_d^x$. This requires heavy lifting: at least

$O(d)$ products and inversions. The main point, however, testing

$$f(x)\stackrel{?}{=}\sum _{i=1}^d{\lambda }_i^x\cdot f(x_i),$$ requires minimal computation.

Outline of the GLRSW scheme

The test we describe here is a refinement of the previous one. It works very much the same, but it manages to bypass the constant recomputation of the weights

${\lambda }_1^x,\dots ,{\lambda }_d^x$. The trick is to select

$x,x_1,x_2,\dots ,x_d$ at every round so that the associated weights stay the same through-out.

A simple way to ensure this is to initially choose

$d+1$ distinct points

$b,a_1,\dots ,a_d$, compute once and for all the

$${\alpha }_i=\prod _{\begin{array}{c}1\le j\le d\\ j\ne i\end{array}}\frac{b-a_j}{a_i-a_j},i=1,\dots ,d$$ and at every round draw random

$s,t\leftarrow \mathbb{Z}/p\mathbb{Z}$ and define

$$\{\begin{array}{lcl}x& \leftarrow & s+bt\\ x_1& \leftarrow & s+a_{1}t\\ x_2& \leftarrow & s+a_{2}t\\ ⋮& & ⋮\\ x_d& \leftarrow & s+a_{d}t\end{array}$$
It is quite obvious that for all

$s,t\in \mathbb{Z}/p\mathbb{Z}$,

$${\lambda }_i^x=\prod _{\begin{array}{c}1\le j\le d\\ j\ne i\end{array}}\frac{x-x_j}{x_i-x_j}=\prod _{\begin{array}{c}1\le j\le d\\ j\ne i\end{array}}\frac{(s+ta)-(s+a_{j}t)}{(s+a_{i}t)-(s+a_{j}t)}=\prod _{\begin{array}{c}1\le j\le d\\ j\ne i\end{array}}\frac{b-a_j}{a_i-a_j}={\alpha }_i$$ since the

$s$ disappear both in the numerators and denominators when taking differences, and the

$t$'s factor out in every quotient. We thus have a new improved test:

Note. The reader may have noticed that the definition of the

${\lambda }_i^x$ doesn't make sense when

$t=0$: we are dividing by zero. This isn't really a problem: for

$f$ polynomial function of degree

$<d$, the functional equation

$f(s+bt)\stackrel{?}{=}\sum _{i=1}^d{\alpha }_i\cdot f(s+a_{i}t)$ does still hold in that case, which is all we need.

Details

In this second half of the post we dive into details about the GLRSW scheme, in particular how it rehabilitates approximate polynomials by computing their closest low-degree polynomial. The proofs we present below are fleshed out versions of those from the original paper Self Testing/Correcting for Polynomials and Approximate Functions.

Conventions

In what follows

$\mathbb{F}$ is a finite prime field and

$d$ is a positive integer with

$d<\mathrm{\#}\mathbb{F}$. We will sometimes write

$n=\mathrm{\#}\mathbb{F}$. We define the degree of a map

$f:\mathbb{F}\to \mathbb{F}$ to be the degree of its interpolation polynomial. Thus

$\mathrm{deg}(f)<\mathrm{\#}\mathbb{F}$. We write

${\mathbb{F}}_d[X]$ for the space of all degree

$\le d$ polynomials with coefficients in

$\mathbb{F}$. We furthermore say that a map

$f:\mathbb{F}\to \mathbb{F}$ has low degree if

$\mathrm{deg}(f)\le d$.

In line with the GLRSW paper, we will consider an efficient program

$P$ that supposedly computes a certain function

$f$. We write

$P(x)$ for the output of

$P$ on input

$x$. The program

$P$ should compute

$f$ correctly most of the time, that is, we expect

$P(x)=f(x)$ for most inputs

$x\in \mathbb{F}$. One may think for instance of

$P$ as verifying a Merkle branch from (supposedly)

$f(x)$ to a Merkle root representing

$f$.

A quick rundown

Step 1: Characterizing low-degreeness

We first establish that a certain form of redundancy in the values of a map

$f:\mathbb{F}\to \mathbb{F}$ is equivalent to the interpolating polynomial of that map having low degree (i.e. degree

$\le d$).

• One direction (
  $⟹$) is easily checked. It is a fact about abstract polynomials.
• The converse, i.e. the fact that this form of redundancy in maps precisely characterizes those maps with low degree interpolating polynomial is established in the next section.

The converse seemingly requires one to work in a prime field to avoid having to divide by binomial coefficients which may be zero (because of positive characteristic).

The helper function g

We next introduce a helper function

$g:\mathbb{F}\to \mathbb{F}$. The definition of

$g$ can be explained as follows. If

$P$ were indeed a low-degree polynomial function, then we would be able to predict any of its values

$P(x)$ starting with any

$d+1$ of its values

$P(x_0)$,

$\dots$,

$P(x_d)$. We would simply use the interpolation formula to make a (correct) prediction. What if

$P$ isn't polynomial, though? Then different sets of values

$x_0,\dots ,x_d$ might lead to different predictions of the value of

$P(x)$. We thus define

Informal definition of

$g$. For

$x\in \mathbb{F}$,

$g(x)$ is be the most popular prediction we get by interpolating values of

$P$.

This definition is a little unsatisfying, though. There is potentially room for ambiguity:

Potential source of ambiguity 1. Of the predicted values, there might be two values that are tied for most popular predicted value.

That would be unfortunate, and it is something we have to deal with. A simple (yet not completely satisfactory) work-around is to arbitrarily break ties. Furthermore, one might question the value of this prediction: what if 998 values are respectively predicted

$0.1001\mathrm{\%}$ of the time, and another value is predicted

$0.1002\mathrm{\%}$ of the time? That value would be our definition of

$g(x)$, but its value as a majority value is dubious.

Potential source of ambiguity 2. There might be no value that is predicted

$>50\mathrm{\%}$ of the time.

Note. It is important to note that

• $g$ is never explicitly computed by anybody
• nor is
  $g$ meant to be efficiently computable.

If the verifier had the computational power to compute

$g$ even on a single value it might as well skip computing

$g$ altogether and directly verify that

$P$ is polynomial. The function

$g$ is simply here to be used in abstract arguments.

What matters most is that this

$g$, whatever it may be, is unambiguously defined and contains information about

$P$. The fact that

$g$ may indeed be unambiguously defined and without arbitrary choices (such as arbitrarily resolving ties) is the [first thing we establish] TODO

Step 2: Analyzing the helper function and drawing conclusions

We formulate the expectations one might place on

$g$:

Expectation 1. If

$P$ is close enough to being polynomial, there is no ambiguity in the definition of

$g$.

This is proven in Lemma 1. This result also has psychological value, as it tells us that we don't have to deal with the potential ambiguities listed above, see its Corollary. In this context, close enough means

$\delta <\frac{1}{4(d+1)}$.

Expectation 2. If

$P$ computes a map that is close to polynomial, then

$g$ and

$P$ ought to agree most of the time.

This is indeed true and established in Lemma 2. In this context, most of the time means on a proportion

$>1-2\delta$ of all inputs.

Expectation 3. The if

$P$ is close enough to some low-degree polynomial map, then the helper function

$g$ is that low-degree polynomial map.

This is indeed true and established in Lemma 3. Thus

$g$ rehabilitates

$P$ provided

$P$ is accurate enough.

Low-degreeness implies redundancy

The following lemma is the theoretical foundation of the test. We consider pairwise distinct field elements

$b,a_0,a_1,\dots ,a_d\in \mathbb{F}$. These will remain constant through out.

Lemma. There exist coefficients

${\alpha }_0,\dots ,{\alpha }_d\in \mathbb{F}$ such that for all

$P\in {\mathbb{F}}_d[X]$,

$$P(X+bT)=\sum _{k=0}^d{\alpha }_{k}P(X+a_{k}T)$$

Proof. We start with a special case of

$P$ which turns out to be sufficient. Thus, expand, for

$P=X^d$ and arbitrary

${\alpha }_0,\dots ,{\alpha }_d\in \mathbb{F}$, both sides of the above:

$$\{\begin{array}{rcl}(X+bT{)}^d& =& {\displaystyle \sum _{k=0}^d(\genfrac{}{}{0ex}{}{d}{k})b^k{T}^k{X}^{d-k}}\\ {\displaystyle \sum _{k=0}^d{\alpha }_k(X+a_{k}T{)}^d}& =& {\displaystyle \sum _{k=0}^d(\genfrac{}{}{0ex}{}{d}{k})(\sum _{l=0}^d{\alpha }_l{a}_l^k)T^k{X}^{d-k}}\end{array}$$
To achieve equality, it is enough that the

${\alpha }_i$ be a solution of the linear system

$$\left(\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ a_0& a_1& a_2& \cdots & a_d\\ a_0^2& a_1^2& a_2^2& \cdots & a_d^2\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_0^d& a_1^d& a_2^d& \cdots & a_d^d\end{array}\right)\left(\begin{array}{c}{\alpha }_0\\ {\alpha }_1\\ {\alpha }_2\\ ⋮\\ {\alpha }_d\end{array}\right)=\left(\begin{array}{c}1\\ b\\ b^2\\ ⋮\\ b^d\end{array}\right)$$
This Vandermonde system is known to be invertible and so there is a unique solution

$({\alpha }_0,\dots ,{\alpha }_d)\in {\mathbb{F}}^{d+1}$. We note that had we written a similar system for

$X^k$ with

$k\le d$, the resulting constraints would have been a subset of those for

$P=X^d$. Hence the

${\alpha }_i$ we just identified work for all degree

$\le d$ polynomials.

Redundancy implies low degreeness

In view of the previous lemma, any degree

$\le d$ polynomial map

$f:\mathbb{F}\to \mathbb{F}$ satisfies

$$\mathrm{\forall }s,t\in \mathbb{F},f(s+bt)=\sum _{k=0}^d{\alpha }_{k}f(s+a_{k}t)$$ Since this is the basis of the proximity test above, one should wonder about the converse: are degree

$\le d$ these the only maps

$f:\mathbb{F}\to \mathbb{F}$ satisfying this property? To answer to that question let us define, for every map

$f:\mathbb{F}\to \mathbb{F}$ a new map

$\hat{f}:\mathbb{F}\times \mathbb{F}\to \mathbb{F}$ by the formula

$${\displaystyle \mathrm{\forall }s,t\in \mathbb{F},\hat{f}(s,t):=f(s+bt)-\sum _{i=0}^d{\alpha }_{i}f(s+a_i\cdot t)}$$ We can thus restate the previous question as

Question. Are degree

$\le d$ these the only maps

$f:\mathbb{F}\to \mathbb{F}$ satisfying

$\hat{f}=0$?

The answer is YES:

Lemma. Let

$f:\mathbb{F}\to \mathbb{F}$ be a map. The following are equivalent:

• $\hat{f}=0$
• $\mathrm{deg}(f)\le d$

Proof. The proof isn't complicated. We use polynomial interpolation of bivariate maps to convert the problem from one about maps to one about polynomials. First of all, bivariate polynomial interpolation is possible. The map

${\mathbb{F}}_{n-1,n-1}[X,Y]\to \mathcal{F}(\mathbb{F}\times \mathbb{F},\mathbb{F})$ that sends a bivariate polynomial

$P$ of bidegree

$\le (n-1,n-1)$ to the associated function

$\mathbb{F}\times \mathbb{F}\to \mathbb{F},(x,y)\mapsto P(x,y)$ is an isomorphism. This is easily seen using the polynomials

$L_{a,b}$ defined by

$$L_{a,b}(X,Y)=(\prod _{\begin{array}{c}\alpha \in \mathbb{F}\\ \alpha \ne a\end{array}}\frac{X-\alpha }{a-\alpha })\cdot (\prod _{\begin{array}{c}\beta \in \mathbb{F}\\ \beta \ne a\end{array}}\frac{Y-\beta }{b-\beta })$$ which vanish everywhere except at the one point

$(a,b)\in {\mathbb{F}}^2$.

Similarly to what we did with functions, we can define, for any univariate polynomial

$P\in {\mathbb{F}}_{n-1}[X]$ a bivariate polynomial

$\hat{P}\in {\mathbb{F}}_{n-1,n-1}[S,T]$ like so

$${\displaystyle \hat{P}=P(S+bT)-\sum _{i=0}^d{\alpha }_{i}P(S+a_i\cdot T)}$$ The procedures

$f\mapsto \hat{f}$ and

$P\mapsto \hat{P}$ are compatible with interpolation in the sense that if

$f$ is a map

$\mathbb{F}\to \mathbb{F}$ and

$P_f$ is its degree

$<n$ interpolating polynomial, then

$\widehat{P_f}$ is

$\hat{f}$'s bivariate interpolation polynomial.

Now suppose

$f$ satisfies

$\hat{f}=0$. Then

$\widehat{P_f}=0$ and if

$e$ is

$f$'s degree (i.e.

$e=\mathrm{deg}(P_f)$), then by looking solely at the degree

$e$ term of

$P_f$ we get that

$$(S+bT{)}^e=\sum _{i=0}^d{\alpha }_i(S+a_{i}T{)}^e$$ and by isolating the

$X^{e-j}{T}^j$ terms we see that

$$\mathrm{\forall }j\in \{0,\dots ,e\},b^j=\sum _{i=0}^d{\alpha }_i{a}_i^j$$ and so

$$\left(\begin{array}{c}1\\ b\\ b^2\\ ⋮\\ b^d\\ ⋮\\ b^e\end{array}\right)={\alpha }_0\cdot \left(\begin{array}{c}1\\ a_0\\ a_0^2\\ ⋮\\ a_0^d\\ ⋮\\ a_0^e\end{array}\right)+{\alpha }_1\cdot \left(\begin{array}{c}1\\ a_1\\ a_1^2\\ ⋮\\ a_1^d\\ ⋮\\ a_1^e\end{array}\right)+{\alpha }_2\cdot \left(\begin{array}{c}1\\ a_2\\ a_2^2\\ ⋮\\ a_2^d\\ ⋮\\ a_2^e\end{array}\right)+\cdots +{\alpha }_d\cdot \left(\begin{array}{c}1\\ a_d\\ a_d^2\\ ⋮\\ a_d^d\\ ⋮\\ a_d^e\end{array}\right)$$ This is where we get a contradiction: this is impossible for

$e\ge d+1$ for it would contradict the invertibility of the Vandermonde matrix

$\mathrm{VdM}(b,a_0,a_1,\dots ,a_d)$ (recall that the

$b,a_0,\dots ,a_d$ are supposed pairwise distinct.)

Note. We implicitely used the assumption that

$\mathbb{F}$ is a prime field. Indeed, in the step where we " looked at

$X^{e-j}{T}^j$ terms " we divided by a binomial coefficient

$(\genfrac{}{}{0ex}{}{e}{j})$ with

$e<\mathrm{\#}\mathbb{F}$. To be legitimate in doing so (i.e. to be sure we don't divide by zero) we have to assume

$n=\mathrm{\#}\mathbb{F}$ is prime.

Expected value of interpolation: the helper function g

Suppose you are given oracle access to the values of a map

$P$. In other words, you have some black box that spits out values

$P(x)$ when you feed it some field element

$x\in \mathbb{F}$. Suppose furthermore you are told: "That function

$P:\mathbb{F}\to \mathbb{F}$ is a low degree polynomial map. How low you ask? Its degree is

$\le d$." How would you go about convincing yourself of that claim? If

$P$'s domain

$\mathbb{F}$ is large, it is hopeless to ask for a perfect proof: you would have to interpolate

$P$ from

$d+1$ values and compare the values predicted by your formula to those queried from the oracle.

You might on the other hand try to use the characterization of low degree maps presented above. While we won't be able to find efficient tests of low-degreeness per se, what we can do is reliably reject oracles

$P$ that are far from any degree

$\le d$ polynomial. That is, what we describe below is a probabilistic test of proximity.

To simplify things slightly, we fix

$b=0$ and consider pairwise distinct nonzero

$a_0,\dots ,a_d\in \mathbb{F}$. There is no reason to try to be fancy about choosing the

$a_i$, so taking

$a_i=i$ for instance is a perfectly valid choice. If

$P$ were indeed polynomial of degree

$\le d$, we would have, for all

$x,t\in \mathbb{F}$,

$$P(x)=\sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot t)$$
This can't be reasonably checked on all inputs

$x,t$. But starting from this observation we can make some abstract definitions that turn out to be useful in the analysis. First of all we define a nonnegative

$\delta ={\delta }_P$ by the formula

$$\delta =\frac{{\displaystyle |\{(x,t)\in {\mathbb{F}}^2|P(x)\ne \sum _{i=0}^{d}P(x+{\alpha }_i\cdot t)\}|}}{|\mathbb{F}{|}^2}$$ This is simply the proportion of inputs

$(x,t)$ that fail the expected equation. We can also define subsets of

$\mathbb{F}$ associated with

$P$. For instance,

${\mathsf{Maj}}_P$ is the set of all

$x$ such that the right hand side of this equation takes on a particular value a majority of the time, i.e. more than half of the time with respect to

$t$. We thus define

$${\mathsf{Maj}}_P=\{x\in \mathbb{F}|\mathrm{\exists }\theta \in \mathbb{F},\text{ s.t. }>50\mathrm{\%}\text{ of all }t\text{ satisfy }\theta =\sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot t)\}$$
We can define a map^[9]

$g:{\mathrm{Maj}}_P\to \mathbb{F}$ by setting

$g(x)=\theta$ where

$\theta$ is the value that appears

$>50\mathrm{\%}$ of the time as

$\sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot t)$. No harm is made by arbitrarily extending

$g$ to a map

$\mathbb{F}\to \mathbb{F}$. We can also define the subset where, conveniently, that majority value coindices with the value predicted by the oracle and that predicted by the supposed low degreeness

$${\mathsf{Conv}}_P=\{x\in \mathbb{F}|>50\mathrm{\%}\text{ of all }t\text{ satisfy }P(x)=\sum _{i=1}^{d+1}{\alpha }_{i}P(x+a_i\cdot t)\}$$

Here's a picture to accompany these definitions. We can think of every pair

$(x,t)\in {\mathbb{F}}^2$ as a test case for the expected equality

$P(x)\stackrel{?}{=}\sum _{i=1}^{d+1}{\alpha }_{i}P(x+a_i\cdot t)$. In the diagram below, blue dots signal that this expected equality holds true, yellow crosses that it fails.

For that particular oracle

$P$, most pairs

$(x,t)$ satisfy the expected equality. If we actually count the yellow crosses we get

$\delta ={\delta }_P=39/256\approx 15,23\mathrm{\%}$. Every column that is majority blue is, by definition, indexed by some

$x\in {\mathrm{Conv}}_P$.

Note that three columns have fewer than half of the expected equalities hold. These are columns indexed by

$x\notin {\mathrm{Conv}}_P$, yet some, such as the first from the left, might still define an unambiguous majority value, e.g. the

$x$-coordinate of the first red column might still belong to

${\mathrm{Maj}}_P$.

Lemma 1 - the helper function and the oracle agree a lot

We start with a simple lemma. Let

$\mathbf{X},\mathbf{Y}$ be independent, identically distributed (iid) random values with values in a finite set

$V$. Also let

$v_0$ be (a) the value

$\mathbf{X}$ is likeliest to have, that is

$$\mathbb{P}[\mathbf{X}=v_0]=\underset{v\in V}{max}\mathbb{P}[\mathbf{X}=v]$$ Let

$\mathcal{E}$ be the event that

$\mathbf{X}$ and

$\mathbf{Y}$ agree, i.e.

$\mathcal{E}=[\mathbf{X}=\mathbf{Y}]$, then

Lemma.

$\mathbb{P}[\mathcal{E}]\le \mathbb{P}[\mathbf{X}=v_0]$.

Proof. Decompose the event

$\mathcal{E}$ according to the common value of

$\mathbf{X}$ and

$\mathbf{Y}$:

$$\mathcal{E}=\underset{v\in V}{⨆}[\mathbf{X}=v]\cap [\mathbf{Y}=v].$$ Taking probabilities and since

$\mathbf{X}$ and

$\mathbf{Y}$ are iid,

$$\begin{array}{rcl}\mathbb{P}[\mathcal{E}]& =& \sum _{v\in V}\mathbb{P}[\mathbf{X}=v{]}^2\\ & \le & \sum _{v\in V}\mathbb{P}[\mathbf{X}=v]\mathbb{P}[\mathbf{X}=v_0]\\ & =& \mathbb{P}[\mathbf{X}=v_0].\end{array}$$

---

Fix

$x\in \mathbb{F}$. Consider two independent uniformly distributed random variables

${\mathbf{t}}_{\mathbf{1}}$ and

${\mathbf{t}}_{\mathbf{2}}$ with values in

$\mathbb{F}$. Consider the random variables

$$\{\begin{array}{l}{\displaystyle {\mathbf{Pred}}_{\mathbf{1}}=\sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}})}\\ {\displaystyle {\mathbf{Pred}}_{\mathbf{2}}=\sum _{j=0}^d{\alpha }_{i}P(x+a_j\cdot {\mathbf{t}}_{\mathbf{2}})}\end{array}$$ These represent random predictions of the value of

$P(x)$ obtained by interpolation. These random variables and are independent and identically distributed. Also

$g(x)$ is, by definition, the most likely value of either. In light of the previous lemma we le the

$\mathcal{E}$ be the event where two predictions agree:

$$\mathcal{E}=[{\mathbf{Pred}}_{\mathbf{1}}={\mathbf{Pred}}_{\mathbf{1}}]$$ The previous lemma tells us that

$$\mathbb{P}[\mathcal{E}]\le \left[\begin{array}{c}\text{Proportion of }t\in \mathbb{F}\text{ such that}\\ \sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot t)=g(x)\end{array}\right]$$ If we can find a usable lower bound for the probability

$\mathbb{P}[\mathcal{E}]$, we get a lower bound for the proportion of inputs realizing the majority value

$g(x)$.

In order to produce such a lower bound, we consider the subevent

$$\begin{array}{rcl}\mathcal{E}& \supset & \stackrel{{\displaystyle (1)}}{\overbrace{{\displaystyle \bigcap _{i=0}^d[P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}})=\sum _{j=0}^d{\alpha }_{j}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]}}}\\ & & \cap \underset{{\displaystyle (2)}}{\underbrace{{\displaystyle \bigcap _{j=0}^d[P(x+a_j\cdot {\mathbf{t}}_{\mathbf{2}})=\sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]}}}\end{array}$$ The right hand side is indeed a subset of

$\mathcal{E}$: if all the conditions on the right are met, then

$$\begin{array}{rcl}{\mathbf{Pred}}_{\mathbf{1}}& =& \sum _{i=0}^d{\alpha }_{i}P(x+i\cdot {\mathbf{t}}_{\mathbf{1}})\\ & \stackrel{(1)}{=}& \sum _{i=0}^d{\alpha }_i(\sum _{j=0}^d{\alpha }_{j}P(x+i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}}))\\ & =& \sum _{j=0}^d{\alpha }_j(\sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}}))\\ & \stackrel{(2)}{=}& \sum _{j=0}^d{\alpha }_{i}P(x+a_j\cdot {\mathbf{t}}_{\mathbf{2}})\\ & =& {\mathbf{Pred}}_{\mathbf{2}}\end{array}$$ These subevents allow us to have th random variables

${\mathbf{t}}_{\mathbf{1}},{\mathbf{t}}_{\mathbf{2}}$ interact. Obtaining a lower bound on

$\mathbb{P}[\mathcal{E}]$ is equivalent to getting an upper bound on

$\mathbb{P}[\mathrm{\Omega }\setminus \mathcal{E}]$. The above gives

$$\begin{array}{rcl}\mathrm{\Omega }\setminus \mathcal{E}& \subset & \bigcup _{i=0}^d[P(x+i\cdot {\mathbf{t}}_{\mathbf{1}})\ne \sum _{j=1}^{d+1}{\alpha }_{j}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]\\ & & \cup \bigcup _{j=0}^d[P(x+j\cdot {\mathbf{t}}_{\mathbf{2}})\ne \sum _{i=1}^{d+1}{\alpha }_{i}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]\end{array}$$
So that

$$\begin{array}{rcl}\mathbb{P}[\mathrm{\Omega }\setminus \mathcal{E}]& \le & \sum _{i=0}^d\mathbb{P}[P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}})\ne \sum _{j=0}^d{\alpha }_{j}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]\\ & & +\sum _{j=0}^d\mathbb{P}[P(x+a_j\cdot {\mathbf{t}}_{\mathbf{2}})\ne \sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]\end{array}$$
Now for any

$i=0,\dots ,d$ the random variable

${\mathbf{t}}_{\mathbf{1}}^{\prime }=x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}$ is uniformly distributed and independent from

${\mathbf{t}}_{\mathbf{2}}$, and similarly for any

$j=0,\dots ,d$ the random variable

${\mathbf{t}}_{\mathbf{2}}^{\prime }=x+a_j\cdot {\mathbf{t}}_{\mathbf{2}}$ is uniformly distributed and independent from

${\mathbf{t}}_{\mathbf{1}}$, and so, by definition of

$\delta$,

$$\begin{array}{l}\mathbb{P}[P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}})\ne \sum _{j=0}^d{\alpha }_{j}P(x+a_i\cdot {\mathbf{t}}_{\mathbf{1}}+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]\\ =\mathbb{P}[P({\mathbf{t}}_{\mathbf{1}}^{\prime })\ne \sum _{j=0}^d{\alpha }_{j}P({\mathbf{t}}_{\mathbf{1}}^{\prime }+a_j\cdot {\mathbf{t}}_{\mathbf{2}})]\\ =\delta \end{array}$$
and similarly,

$$\begin{array}{l}\mathbb{P}[P(x+a_j\cdot {\mathbf{t}}_{\mathbf{2}})\ne \sum _{i=0}^d{\alpha }_{i}P(x+a_j\cdot {\mathbf{t}}_{\mathbf{2}}+a_i\cdot {\mathbf{t}}_{\mathbf{1}})]\\ =\mathbb{P}[P({\mathbf{t}}_{\mathbf{2}}^{\prime })\ne \sum _{j=0}^d{\alpha }_{i}P({\mathbf{t}}_{\mathbf{2}}^{\prime }+a_i\cdot {\mathbf{t}}_{\mathbf{1}})]\\ =\delta \end{array}$$ Injecting these into the upper bound for

$\mathbb{P}[\mathrm{\Omega }\setminus \mathcal{E}]=1-\mathbb{P}\left[\mathcal{E}\right]$ obtained previously proves

Lemma 1. For any

$x\in \mathbb{F}$,

$$1-2(d+1)\delta \le \mathbb{P}[\mathcal{E}]\le \mathbb{P}[{\mathbf{Pred}}_{\mathbf{1}}=g(x)].$$

As promised, we can thus lift any and all unpleasant ambiguities in

$g$'s definition. Notice that

$1-2(d+1)\delta >\frac{1}{2}$ as soon as

$\delta <\frac{1}{4(d+1)}$.

Corollary. Suppose that

$\delta <\frac{1}{4(d+1)}$, then for all

$x\in \mathbb{F}$,

$g(x)$ represents

$>50\mathrm{\%}$ of the the values

$\sum _{i=0}^d{\alpha }_{j}P(x+a_i\cdot t)$ where

$t\in \mathbb{F}$. In other words,

${\mathbf{Maj}}_P=\mathbb{F}$.

Lemma 2 - the helper function and the oracle agree a lot

Let us make the headline precise. We just proved that whenever

$\delta <\frac{1}{4(d+1)}$, then

$g(x)$ is unambiguously defined for all

$x\in \mathbb{F}$, that is

${\mathbf{Maj}}_P=\mathbb{F}$. Recall that we defined a subset

${\mathbf{Conj}}_P\subset {\mathbf{Maj}}_P$ of so-called "convenient" inputs. Those were the

$x\in \mathbb{F}$ where, not only

$g$ was unambiguously defined, but

$g(x)$ coïncided with

$P(x)$. We now establish that as long as

$\delta$ is small enough,

${\mathbf{Conj}}_P$ will be large. I.e. if

$\delta$ is small, then the helper function

$g$ and the oracle agree often.

Lemma 2. We have

$\frac{|{\mathsf{Conv}}_P|}{|\mathbb{F}|}\ge 1-2\delta$

Proof. Let us consider the pairs

$(x,t)$ where the expected equality

$$P(x)\stackrel{?}{=}\sum _{i=0}^d{\alpha }_{i}P(x+a_i\cdot t^{\prime })$$ fails. We distinguish two cases:

$x\in {\mathrm{Conj}}_P$ and

$x\notin {\mathrm{Conj}}_P$ :

Thus, by definition of

$\delta$,

The last inequality follows from the fact that when

$x\notin {\mathbf{Conv}}_P$,

$g(x)\ne P(x)$ and thus

$P(x)$ is not a majority value (or it shares that title with

$g(x)$ and was arbitrarily disregarded as the choice for the majority value). In particular, the proportion of

$t\in \mathbb{F}$ such that

$P(x)\ne \sum _{i=0}^{d}P(x+a_i\cdot t)$ is at least

$50\mathrm{\%}$. Rearranging things, we get the inequality from the lemma.

Lemma 3 - the helper function is a low degree polynomial

We first state an informal version of the lemma to prove. A precise statment will be given at the end.

Lemma 3 (informal). If

$\delta$ is small enough, then the helper function

$g$ is polynomial.

The proof strategy is quite interesting: to prove that

$g$ is polynomial of degree

$\le d$ (or to be precise:

$g$'s interpolating polynomial has degree

$\le d$) the authorsinvoke the characterization of low degree functions. The goal is thus to show that for any two

$x,t\in \mathbb{F}$ one has

$$g(x)=\sum _{i=0}^d{\alpha }_{i}g(x+a_i\cdot t)\text{i.e.}\underset{{\displaystyle (\text{Eq. }{\text{color}red\star }_{x,t})}}{\underbrace{\sum _{i=0}^{d+1}{\alpha }_{i}g(x+a_i\cdot t)=0}}$$ where we set

$a_{d+1}=b=0$ and

${\alpha }_{d+1}=-1$. What makes the proof strategy interesting is that the satisfaction of (Eq.

${\text{color}red\star }_{x,t}$) for a particular pair

$(x,t)\in {\mathbb{F}}^2$, which is either true or false, is established using a probabilistic method. To wit, consider the following event

$$\begin{array}{rcl}\mathcal{F}={\mathcal{F}}_{x,t}& =& {\displaystyle \stackrel{{\displaystyle (3)}}{\overbrace{\bigcap _{i=0}^{d+1}[g(x+a_{i}t)=\sum _{j=0}^d{\alpha }_{j}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]}}}\\ & & {\displaystyle \cap \underset{{\displaystyle (4)}}{\underbrace{\bigcap _{j=1}^d[0=\sum _{i=0}^{d+1}{\alpha }_{i}P(x+a_j{\mathbf{t}}_{\mathbf{1}}+a_i(t+a_j{\mathbf{t}}_{\mathbf{2}}))]}}}\end{array}$$ where

${\mathbf{t}}_{\mathbf{1}}$ and

${\mathbf{t}}_{\mathbf{2}}$ are independent uniformly distributed random variables in

$\mathbb{F}$. The relation with (Eq.

${\text{color}red\star }_{x,t}$) is that, whenever the conditions in

$\mathcal{F}$ are met, one has

$$\begin{array}{rcl}{\displaystyle \sum _{i=0}^{d+1}{\alpha }_{i}g(x+a_{i}t)}& \stackrel{(3)}{=}& {\displaystyle \sum _{i=0}^{d+1}{\alpha }_i\sum _{j=0}^d{\alpha }_{j}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+i{\mathbf{t}}_{\mathbf{2}}))}\\ & =& {\displaystyle \sum _{j=0}^d{\alpha }_j\sum _{i=0}^{d+1}{\alpha }_{i}P(x+a_j{\mathbf{t}}_{\mathbf{1}}+a_i(t+j{\mathbf{t}}_{\mathbf{2}}))}\\ & \stackrel{(4)}{=}& 0.\end{array}$$ Thus, to conclude that (Eq.

${\text{color}red\star }_{x,t}$) holds it is enough to show that the event

${\mathcal{F}}_{x,t}$ has nonzero probability. The goal now is to bound the probability of

$\mathcal{F}$ from below, in particular, to show that it is

$>0$ when

$\delta$ is small enough.

Again, the idea will to bound

$\mathbb{P}[{\mathcal{F}}^c]$ from above. First of all,

$$\begin{array}{rcl}{\mathcal{F}}^c& =& {\displaystyle \bigcup _{i=0}^{d+1}[g(x+a_{i}t)\ne \sum _{j=0}^d{\alpha }_{j}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]}\\ & & {\displaystyle \cup \bigcup _{j=0}^d[0\ne \sum _{i=0}^{d+1}{\alpha }_{i}P(x+a_j{\mathbf{t}}_{\mathbf{1}}+a_i(t+a_j{\mathbf{t}}_{\mathbf{2}}))]}\end{array}$$ so that

$$\begin{array}{rcl}1-\mathbb{P}[\mathcal{F}]=\mathbb{P}[{\mathcal{F}}^c]& \le & {\displaystyle \sum _{i=0}^{d+1}\stackrel{{\displaystyle \text{color}red\mathbf{\text{I}}}}{\overbrace{\mathbb{P}[g(x+a_{i}t)\ne \sum _{j=0}^d{\alpha }_{j}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]}}}\\ & & {\displaystyle +\sum _{j=0}^d\underset{{\displaystyle \text{color}blue\mathbf{\text{II}}}}{\underbrace{\mathbb{P}[0\ne \sum _{i=0}^{d+1}{\alpha }_{i}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]}}}\end{array}$$

Bounding

$\text{color}red\mathbf{\text{I}}$. Since for all

$i$, the random variable

${\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}$ is uniformly distributed, we can apply the result from Lemma 1 and obtain

$$\mathrm{\forall }i,\mathbb{P}[g(x+a_{i}t)\ne \sum _{j=0}^d{\alpha }_{j}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]\le 2(d+1)\delta .$$

Bounding

$\text{color}blue\mathbf{\text{II}}$. Take

$j\in \{0,\dots ,d\}$. For any

$i\in \{0,\dots ,d+1\}$, rearranging terms

$$P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))=P(\text{boldsymbol}\xi +a_i\text{boldsymbol}\tau )$$ where

$\text{boldsymbol}\xi =x+a_j{\mathbf{t}}_{\mathbf{1}}$ and

$\text{boldsymbol}\tau =t+a_j{\mathbf{t}}_{\mathbf{2}}$. Note that are

$\text{boldsymbol}\xi$ and

$\text{boldsymbol}\tau$ are both uniformly distributed in

$\mathbb{F}$ (since

$a_j\ne 0$) and independent (since

${\mathbf{t}}_{\mathbf{1}}$ and

${\mathbf{t}}_{\mathbf{2}}$ are). Then by definition of

$\delta$,

$$\begin{array}{rcl}{\displaystyle \mathbb{P}[0\ne \sum _{i=0}^{d+1}{\alpha }_{i}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]}& =& {\displaystyle \mathbb{P}[0\ne \sum _{i=0}^{d+1}{\alpha }_{i}P(x+a_j{\mathbf{t}}_{\mathbf{1}}+a_i(t+a_j{\mathbf{t}}_{\mathbf{2}}))]}\\ & =& {\displaystyle \mathbb{P}[0\ne \sum _{i=0}^{d+1}{\alpha }_{i}P(\text{boldsymbol}\xi +a_i\text{boldsymbol}\tau ))]}\\ & =& \delta .\end{array}$$

Combining these bounds yields:

$$\begin{array}{rcl}1-\mathbb{P}[\mathcal{F}]=\mathbb{P}[{\mathcal{F}}^c]& \le & {\displaystyle \sum _{i=0}^{d+1}\mathbb{P}[g(x+a_{i}t)\ne \sum _{j=0}^d{\alpha }_{j}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]}\\ & & +{\displaystyle \sum _{j=0}^d\mathbb{P}[0\ne \sum _{i=0}^{d+1}{\alpha }_{i}P(x+a_{i}t+a_j({\mathbf{t}}_{\mathbf{1}}+a_i{\mathbf{t}}_{\mathbf{2}}))]}\\ & \le & (d+2)\cdot 2(d+1)\delta +(d+1)\cdot \delta =(d+1)(2d+5)\delta \end{array}$$ i.e.

$$1-(d+1)(2d+5)\delta \le \mathbb{P}[\mathcal{F}].$$ Therefore, as soon as

$\delta <\frac{1}{(d+1)(2d+5)}$,

$g$ is polynomial. We can now state Lemma 3 with precision.

Lemma 3. If

$\delta <\frac{1}{(d+1)(2d+5)}$, the helper function

$g$ is polynomial.

Conclusion

Lemma 3 shows how to "recover" the unique low-degree neighbor function

$g$ of a map

$P$ as soon as

$\delta$ is small enough. Thus

$g$ is the polynomial function the program

$P$ is meant to be computing.

A question

Let

$\mathbb{F}$ be a prime field. Let

$x,x_1,\dots ,x_d\in \mathbb{F}$ are pairwise distinct and, similarly, let

$y,y_1,\dots ,y_d\in \mathbb{F}$ are pairwise distinct. Suppose that for all

$i=1,\dots ,d$,

$$\prod _{\begin{array}{c}1\le j\le d\\ j\ne i\end{array}}\frac{x-x_j}{x_i-x_j}=\prod _{\begin{array}{c}1\le j\le d\\ j\ne i\end{array}}\frac{y-y_j}{y_i-y_j}$$ This is the case for instance if

$y,y_1,\dots ,y_d$ are obtained from

$x,x_1,\dots ,x_d$ by means of an affine transformation

$u\mapsto au+b$ (with

$a\ne 0$). One might ask: is the converse true?

Question. Is it necessarily the case that there exist

$(a,b)\in {\mathbb{F}}^{\times }\times \mathbb{F}$ such that

$y,y_1,\dots ,y_d$ are obtained from the

$x,x_1,\dots ,x_d$ by application of the affine transformation

${\varphi }_{a,b}:u\mapsto au+b$ ?

Note. The restriction to prime fields could potentially be relaxed by allowing automorphisms

$\sigma \in \mathrm{Aut}(\mathbb{F})$ in the affine transformation formula:

${\varphi }_{a,b,\sigma }:u\mapsto a\sigma (u)+b$ and with, say,

$\sigma$ the Frobenius automorphism of the subfield generated by the

$d$ weights above.

---

1. although, more on that later. ↩︎

2. although concrete implementations vary greatly ↩︎

3. the precise way in which this interpolation is done varies. In particular, the domain of interpolation is usually a structured subset of a (finite) field

   $\mathbb{F}$: a subgroup/coset of
   ${\mathbb{F}}^{\times }$ or an additive sugroup/coset of
   ${\mathbb{F}}_{p^d}$. ↩︎

4. which vectors also support ↩︎

5. indeed, if

   $\mathrm{deg}(P),\mathrm{deg}(Q)⋘\mathrm{\#}\mathbb{F}$ and if
   $s$ is drawn at random in a large field
   $\mathbb{F}$, then
   $P(s)=Q(s)$ happens with probability at most
   $\frac{max\{\mathrm{deg}(P),\mathrm{deg}(Q)\}}{\mathrm{\#}\mathbb{F}}⋘1$. ↩︎

6. i.e. we think of maps

   $f:\mathbb{F}\to \mathbb{F}$ as the points of
   $\mathcal{F}$ ↩︎

7. when all conditions

   $f(x)=P_f(x)$,
   $f(x_1)=P_f(x_1)$, …,
   $f(x_d)=P_f(x_d)$ are met simultaneously. There can of course be serendipitous collisions, but those are harder to account for. ↩︎

8. when precisely one of the conditions

   $f(x)=P_f(x)$,
   $f(x_1)=P_f(x_1)$, …,
   $f(x_d)=P_f(x_d)$ isn't met. Of course more than one of these may fail, but it is then unclear whether the equation fails too. ↩︎

9. we defined

   ${\mathrm{Maj}}_P$ precisely in order to define
   $g$ ↩︎