Skip to content

Add sum-over-hypercube invariant test for eq polynomial #318

@Bisht13

Description

@Bisht13

Context

PR #317 added unit tests for the sumcheck eq-polynomial utilities (calculate_eq, eval_eq, calculate_evaluations_over_boolean_hypercube_for_eq, transpose/multiply helpers). Coverage is solid, but one fundamental mathematical invariant is untested.

Missing test

For any r ∈ F^n, the sum of eq(r, x) over all x ∈ {0,1}^n must equal 1:

$$\sum_{x \in {0,1}^n} \text{eq}(r, x) = 1$$

This is a core property of the multilinear extension of the equality polynomial.

Why it matters

The existing test_eq_hypercube_len4 cross-validates calculate_evaluations_over_boolean_hypercube_for_eq against calculate_eq entry-by-entry — but if calculate_eq itself has a bug, both sides agree on the wrong answer. The sum property is a self-checking invariant that doesn't depend on a second implementation being correct.

Suggested test

#[test]
fn test_eq_hypercube_sums_to_one() {
    let r = [fe(2), fe(3), fe(4), fe(5)];
    let evals = calculate_evaluations_over_boolean_hypercube_for_eq(&r, 16);
    let sum: FieldElement = evals.iter().copied().sum();
    assert_eq!(sum, fe(1));
}

Location

provekit/common/src/utils/sumcheck.rs, in the #[cfg(test)] mod tests block alongside the existing hypercube tests.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions