Trait PolynomialSpace

pub trait PolynomialSpace: Copy {
    type Val: Field;

    // Required methods
    fn size(&self) -> usize;
    fn first_point(&self) -> Self::Val;
    fn next_point<Ext: ExtensionField<Self::Val>>(&self, x: Ext) -> Option<Ext>;
    fn create_disjoint_domain(&self, min_size: usize) -> Self;
    fn split_domains(&self, num_chunks: usize) -> Vec<Self>;
    fn split_evals(
        &self,
        num_chunks: usize,
        evals: RowMajorMatrix<Self::Val>,
    ) -> Vec<RowMajorMatrix<Self::Val>>;
    fn vanishing_poly_at_point<Ext: ExtensionField<Self::Val>>(
        &self,
        point: Ext,
    ) -> Ext;
    fn selectors_at_point<Ext: ExtensionField<Self::Val>>(
        &self,
        point: Ext,
    ) -> LagrangeSelectors<Ext>;
    fn selectors_on_coset(
        &self,
        coset: Self,
    ) -> LagrangeSelectors<Vec<Self::Val>>;
}

Fixing a field, F, PolynomialSpace<Val = F> denotes an indexed subset of F^n with some additional algebraic structure.

We do not expect PolynomialSpace to store this subset, instead it usually contains some associated data which allows it to generate the subset or pieces of it.

Each PolynomialSpace should be part of a family of similar spaces for some collection of sizes (usually powers of two). Any space other than at the smallest size should be decomposable into a disjoint collection of smaller spaces. Additionally, the set of all PolynomialSpace of a given size should form a disjoint partition of some subset of F^n which supports a group structure.

The canonical example of a PolynomialSpace is a coset gH of a two-adic subgroup H of the multiplicative group F*. This satisfies the properties above as cosets partition the group and decompose as gH = g(H^2) u gh(H^2) for h any generator of H.

The other example in this code base is twin cosets which are sets of the form gH u g^{-1}H. The decomposition above extends easily to this case as h is a generator if and only if h^{-1} is and so gH u g^{-1}H = (g(H^2) u g^{-1}(H^2)) u (gh(H^2) u (gh)^{-1}(H^2)).

Required Associated Types

type Val: Field

The base field F.

Required Methods

fn size(&self) -> usize

The number of elements of the space.

fn first_point(&self) -> Self::Val

The first point in the space.

fn next_point<Ext: ExtensionField<Self::Val>>(&self, x: Ext) -> Option<Ext>

An algebraic function which takes the i’th element of the space and returns the (i+1)’th evaluated on the given point.

When PolynomialSpace corresponds to a coset, gH this function is multiplication by h for a chosen generator h of H.

This function may not exist for other classes of PolynomialSpace in which case this will return None.

fn create_disjoint_domain(&self, min_size: usize) -> Self

Return another PolynomialSpace with size at least min_size disjoint from this space.

When working with spaces of power of two size, this will return a space of size 2^ceil(log_2(min_size)). This will fail if min_size is too large. In particular, log_2(min_size) should be smaller than the 2-adicity of the field.

This fixes a canonical choice for prover/verifier determinism and LDE caching.

fn split_domains(&self, num_chunks: usize) -> Vec<Self>

Split the PolynomialSpace into num_chunks smaller PolynomialSpaces of equal size.

num_chunks must divide self.size() (which usually forces it to be a power of 2.) or this function will panic.

fn split_evals( &self, num_chunks: usize, evals: RowMajorMatrix<Self::Val>, ) -> Vec<RowMajorMatrix<Self::Val>>

Split a set of polynomial evaluations over this PolynomialSpace into a vector of polynomial evaluations over each PolynomialSpace generated from split_domains.

evals.height() must equal self.size() and num_chunks must divide self.size(). evals are assumed to be in standard (not bit-reversed) order.

fn vanishing_poly_at_point<Ext: ExtensionField<Self::Val>>( &self, point: Ext, ) -> Ext

Compute the vanishing polynomial of the space, evaluated at the given point.

This is a polynomial which evaluates to 0 on every point of the space self and has degree equal to self.size(). In other words it is a choice of element of the defining ideal of the given set with this extra degree property.

In the univariate case, it is equal, up to a linear factor, to the product over all elements x, of (X - x). In particular this implies it will not evaluate to 0 at any point not in self.

fn selectors_at_point<Ext: ExtensionField<Self::Val>>( &self, point: Ext, ) -> LagrangeSelectors<Ext>

Compute several Lagrange selectors at a given point.

• The Lagrange selector of the first point.
• The Lagrange selector of the last point.
• The Lagrange selector of everything but the last point.
• The inverse of the vanishing polynomial.

Note that these may not be normalized.

fn selectors_on_coset(&self, coset: Self) -> LagrangeSelectors<Vec<Self::Val>>

Compute several Lagrange selectors at all points of the given disjoint PolynomialSpace.

• The Lagrange selector of the first point.
• The Lagrange selector of the last point.
• The Lagrange selector of everything but the last point.
• The inverse of the vanishing polynomial.

Note that these may not be normalized.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl<Val: TwoAdicField> PolynomialSpace for TwoAdicMultiplicativeCoset<Val>

fn next_point<Ext: ExtensionField<Val>>(&self, x: Ext) -> Option<Ext>

Getting the next point corresponds to multiplication by the generator.

fn create_disjoint_domain(&self, min_size: usize) -> Self

Given the coset gH, return the disjoint coset gfK where f is a fixed generator of F^* and K is the unique two-adic subgroup of with size 2^(ceil(log_2(min_size))).

Panics

This will panic if min_size > 1 << Val::TWO_ADICITY.

fn split_domains(&self, num_chunks: usize) -> Vec<Self>

Given the coset gH and generator h of H, let K = H^{num_chunks} be the unique group of order |H|/num_chunks.

Then we decompose gH into gK, ghK, gh^2K, ..., gh^{num_chunks}K.

fn vanishing_poly_at_point<Ext: ExtensionField<Val>>(&self, point: Ext) -> Ext

Compute the vanishing polynomial at the given point:

Z_{gH}(X) = g^{-|H|}\prod_{h \in H} (X - gh) = (g^{-1}X)^|H| - 1

fn selectors_at_point<Ext: ExtensionField<Val>>( &self, point: Ext, ) -> LagrangeSelectors<Ext>

Compute several Lagrange selectors at the given point:

Defining the vanishing polynomial by Z_{gH}(X) = g^{-|H|}\prod_{h \in H} (X - gh) = (g^{-1}X)^|H| - 1 return:

• Z_{gH}(X)/(g^{-1}X - 1): The Lagrange selector of the point g.
• Z_{gH}(X)/(g^{-1}X - h^{-1}): The Lagrange selector of the point gh^{-1} where h is the generator of H.
• (g^{-1}X - h^{-1}): The Lagrange selector of the subset consisting of everything but the point gh^{-1}.
• 1/Z_{gH}(X): The inverse of the vanishing polynomial.

fn selectors_on_coset(&self, coset: Self) -> LagrangeSelectors<Vec<Val>>

Compute the Lagrange selectors of our space at every point in the coset.

This will error if our space is not the group H and if the given coset is not disjoint from H.

type Val = Val

fn size(&self) -> usize

fn first_point(&self) -> Self::Val

fn split_evals( &self, num_chunks: usize, evals: RowMajorMatrix<Self::Val>, ) -> Vec<RowMajorMatrix<Self::Val>>

Implementors