zorch.poly.multilinear

Multilinear polynomial ops over the boolean hypercube.

eval_mle evaluates an MLE (evals in lexicographic order) at a point via the equality-polynomial inner product (poly.eq.expand_eq_to_hypercube); the LSB-consecutive mle_fold binds one variable; mle_coeffs_to_evals / mle_evals_to_coeffs convert between the monomial-coefficient and hypercube-evaluation bases. Reusable pieces a PCS/IOP stands on — Basefold is the first consumer.

mle_coeffs_to_evals

mle_coeffs_to_evals(coeffs: Array) -> Array

Multilinear coefficient→evaluation (the zeta/subset-sum transform) over the trailing axis of (..., 2ᵏ): the hypercube evaluation at vertex v is the sum of every coefficient whose monomial support is a subset of v. Runs the per-bit passes (a[v] += a[v with one set bit cleared]) as one fixed lax.scan (see _butterfly_scan). Inverse of mle_evals_to_coeffs; leading axes ride through.

Source code in zorch/poly/multilinear.py

def mle_coeffs_to_evals(coeffs: Array) -> Array:
    """Multilinear coefficient→evaluation (the zeta/subset-sum transform) over
    the trailing axis of `(..., 2ᵏ)`: the hypercube evaluation at vertex `v` is
    the sum of every coefficient whose monomial support is a subset of `v`. Runs
    the per-bit passes (`a[v] += a[v with one set bit cleared]`) as one fixed
    `lax.scan` (see `_butterfly_scan`). Inverse of `mle_evals_to_coeffs`; leading
    axes ride through."""
    return _butterfly_scan(coeffs, _zeta_combine)

mle_evals_to_coeffs

mle_evals_to_coeffs(evals: Array) -> Array

Evaluation→coefficient transform, the Möbius inverse of mle_coeffs_to_evals (a[v] -= a[v with one set bit cleared]), as one fixed lax.scan. Leading axes ride through.

Source code in zorch/poly/multilinear.py

def mle_evals_to_coeffs(evals: Array) -> Array:
    """Evaluation→coefficient transform, the Möbius inverse of
    `mle_coeffs_to_evals` (`a[v] -= a[v with one set bit cleared]`), as one fixed
    `lax.scan`. Leading axes ride through."""
    return _butterfly_scan(evals, _mobius_combine)

eval_mle

eval_mle(mle: Array, point: Array, axis: int = 0) -> Array

Evaluate an MLE at point via the eq inner product. Contracts axis (size 2ⁿ); leading/trailing axes ride through. 1-D MLE -> scalar.

Source code in zorch/poly/multilinear.py

def eval_mle(mle: Array, point: Array, axis: int = 0) -> Array:
    """Evaluate an MLE at `point` via the eq inner product. Contracts `axis`
    (size 2ⁿ); leading/trailing axes ride through. 1-D MLE -> scalar."""
    eq = expand_eq_to_hypercube(point, fnp.ones((), mle.dtype))
    shape = [1] * mle.ndim
    shape[axis] = eq.shape[0]
    return (mle * eq.reshape(shape)).sum(axis=axis)

mle_fold

mle_fold(evals: Array, beta: Array) -> Array

Fold a consecutive-LSB variable pair: result[i] = evals[2i] + β·evals[2i+1].

This is the additive Basefold/FRI combine (e0 + β·e1), NOT the multilinear partial-evaluation bind (1−β)·e0 + β·e1 that SumcheckRound uses. Acts on the last axis ((..., 2ⁿ) -> (..., 2ⁿ⁻¹)), so leading batch axes ride through.

Source code in zorch/poly/multilinear.py

def mle_fold(evals: Array, beta: Array) -> Array:
    """Fold a consecutive-LSB variable pair: result[i] = evals[2i] + β·evals[2i+1].

    This is the additive Basefold/FRI combine (e0 + β·e1), NOT the multilinear
    partial-evaluation bind (1−β)·e0 + β·e1 that SumcheckRound uses. Acts on the
    last axis (`(..., 2ⁿ) -> (..., 2ⁿ⁻¹)`), so leading batch axes ride through.
    """
    pairs = evals.reshape(*evals.shape[:-1], -1, 2)
    return pairs[..., 0] + beta * pairs[..., 1]