Struct OuterShiftStage 

pub struct OuterShiftStage<F: Field, A: Allocator> { /* private fields */ }

The sumcheck rounds binding the outer shift of a sequence, against the folded oblong table.

The reduction’s h factor spans 24 variables — the bit position and both shift slots — so its value table would hold 2^24 entries. It is never formed. Instead, writing T for the shift operator (shift_operator_table) and d for the oblong weights,

    eta := T[d]                                    2^15 entries
    h(J, s_2, o_2, s_1, o_1) = T[eta(., s_2, o_2)](J, s_1, o_1)

so h is reached by applying T to the oblong weights, taking the outer slice, and applying T again. This stage holds eta and folds it as the rounds bind the outer slot; each round’s h rows are derived from the folded table, one slice at a time. Folding eta first and applying T after gives the same answer as folding h, because T is linear in its weights.

Why the outer slot binds first

Two independent reasons:

• Correctness. The two indicator matrices do not commute — sra is the obstruction, since it is the one shift whose vacated positions all read a single input bit. Nesting T inside T composes them in the order the slots are bound, so only binding the outer slot first computes h rather than its transpose-order counterpart.
• Cost. The push-through is a shift only while the inner pair is still a cube index. Under the opposite order the outer indicator would arrive folded to a dense 2^6 x 2^6 matrix, and each live shift quadruple would cost a matrix-vector product in place of a shift.

Implementations

impl<F: BinaryField, A: Allocator> OuterShiftStage<F, A>

pub fn new(alloc: &A, oblong_weights: &[F]) -> Self

Pushes the oblong weights through every shift, ready for the first round.

Panics

Panics unless the weights hold one entry per bit position of a word.

pub const fn n_vars_remaining(&self) -> usize

The number of outer-index variables the stage has yet to bind.

pub fn psi(&self) -> &[F]

The weights the inner rounds run against: eta at the bound outer point.

The terminal fold of eta is the partial evaluation sum_i d(i) * shift-ind~(i, K, r_s2, r_o2), the multilinear extension commuting with the finite sum over i. So the inner rounds need no division and no second pass.

Preconditions

• self.n_vars_remaining() == 0

pub fn fold(&mut self, challenge: F)

Binds the highest outer variable to a challenge.

Preconditions

• self.n_vars_remaining() >= 1

pub fn round_coeffs<P: PackedField<Scalar = F>>( &self, g: &SparseShiftRows<P>, claim: F, ) -> RoundCoeffs<F>

Computes one round message: the degree-2 round polynomial binding the next outer variable.

The round polynomial is sampled at 1 and at infinity, as RoundEvals documents; the claim supplies its value at 0. Both are linear in g, so each stored row contributes on its own and rows facing each other across the split never have to be paired:

R(1)   = sum_v G_1(v) H_1(v)             row (i, c) adds <c, h[i]>, upper half only
R(inf) = sum_v (G_0 + G_1)(H_0 + H_1)    row (i, c) adds <c, h[i] + h[i ^ half]>, either half

Unlike the rounds that follow, the h rows are not read from a table but derived: a row’s is one slice of the shift operator applied to one stride of the folded eta, which costs O(2^6). A round therefore costs O(2^6 * n_shift) in the number of live shift quadruples, with no charge proportional to the space they are drawn from.

Preconditions

• g’s row index is a shift quadruple, the outer slot above the inner one
• g and this stage have the same number of outer variables left to bind