Module subspace_polys 

Evaluating the normalized subspace polynomials $\hat{W}_k$ away from the basis.

The additive NTT reads its input as coefficients in the novel polynomial basis of LCH14. That basis factors bit by bit over the message index $j$:

$$ \hat{X}j(x) = \prod{k ,:, \mathrm{bit}_k(j) = 1} \hat{W}_k(x) $$

Each $\hat{W}_k$ vanishes on the $k$-dimensional subspace $S_k$. It is normalized so that $\hat{W}_k(\beta_k) = 1$.

DomainContext already tabulates $\hat{W}_k$ on the basis elements $\beta_j$. That is everything the NTT and the FRI fold need. This module adds the two evaluations they do not provide.

• At an arbitrary field point, via NormalizedSubspacePolys::evals_at.
• At a domain index, via evals_at_domain_index, a subset sum over that same table.

A generator row is a tensor

The factorization above makes one row of the transform matrix a tensor expansion. Its factors are the $\ell$ numbers $\hat{W}0(x), \ldots, \hat{W}{\ell-1}(x)$. With two variables:

$$ m_0 + m_1 \hat{W}_0(x) + m_2 \hat{W}_1(x) + m_3 \hat{W}_1(x) \hat{W}_0(x) = \langle m, (1, \hat{W}_0(x)) \otimes (1, \hat{W}_1(x)) \rangle $$

Four row entries out of two numbers. Out of $\ell$ numbers you get all $2^\ell$ entries. That is what lets a verifier evaluate a row without materializing it. binius_field::util::expand_subset_products performs the expansion.

Pairing with a Reed-Solomon codeword

Two adjustments turn the identity above into a row of ReedSolomonCode::encode_batch.

First, build the polynomials on the codeword domain, then truncate to the message dimension. Encoding zero-pads the message, so the extra dimensions contribute nothing.

Second, reverse the evaluation order before expanding. encode_batch encodes the bit-reversal permuted message, as reed_solomon.rs states. Reversing the $\ell$ factors applies that same permutation to the tensor.

Writing evals for the evaluations on the codeword domain:

    encode_batch(msg, 0)[x] = <msg, expand_subset_products(rev(evals[..log_dim]))>

Interleaved lanes reduce to that case. Lane lane of a b-lane encoding is the plain encoding of its own columns:

    encode_batch(msg, b)[(x << b) | lane] = encode_batch(lane_msg, 0)[x]
    lane_msg[j] = msg[(reverse_bits(lane, b) << log_dim) | j]

Both identities are pinned by tests in this module.

Structs

NormalizedSubspacePolys

Constants for evaluating the normalized subspace polynomials at an arbitrary field point.

Functions

evals_at_domain_index

Evaluates every $\hat{W}_k$ at the domain element index selects, in increasing $k$.