Module eq_prefix 

The prefix equality indicator over the Boolean hypercube.

For m <= 2^n, eq_{<m}(X, Y) is the 2n-variate multilinear that agrees with eq(X, y) at the hypercube vertices y < m and vanishes at the vertices y >= m, reading a vertex as the integer whose bit k is coordinate k. Its partial evaluation eq_{<m}(r, ·) is the length-m prefix of the eq tensor of r, zero-extended.

The evaluators run the recursion from the lowest coordinate up, with m = Σ m_k 2^k:

P_0 = 0,  E_0 = 1
P_{k+1} = (1 - X_k)(1 - Y_k) · (m_k ? E_k : P_k) + X_k Y_k · (m_k ? P_k : 0)
E_{k+1} = eq(X_k, Y_k) · E_k

Factoring each term as a lerp at X_k leaves only two products with Y_k per step, E_k Y_k and P_k Y_k, which matters in the tensor algebra, where those are the costly horizontal scalings:

P_{k+1} = m_k ? lerp(X_k, E_k - E_k Y_k, P_k Y_k) : lerp(X_k, P_k - P_k Y_k, 0)
E_{k+1} = lerp(X_k, E_k - E_k Y_k, E_k Y_k)

where lerp(t, a, b) = a + t (b - a), computed by extrapolate_line with arguments (a, b, t).

P_k is the indicator of the low k coordinates against m mod 2^k, so the result is P_n, except that m = 2^n selects E_n = eq(X, Y).

Functions

eq_ind_prefix_eval

Evaluates the prefix equality indicator eq_{<m}(x, y) in O(n) field operations.

eq_ind_prefix_eval_tensor_algebra

Evaluates eq_{<m}(φ0(x), φ1(y)) in the tensor algebra.

eq_ind_prefix_partial_eval_in

Computes the partial evaluation eq_{<m}(r, ·) into a buffer drawn from an allocator: the eq tensor of r with every entry at index >= m zeroed.