Skip to content

feat(multilinear): evaluation at the Boolean vertices and uniqueness of multilinear interpolants - #404

Merged
dhsorens merged 5 commits into
Verified-zkEVM:mainfrom
tcoratger:feat/multilinear-unique
Oct 27, 2026
Merged

dhsorens merged 5 commits into
Verified-zkEVM:mainfrom
tcoratger:feat/multilinear-unique

Conversation

@tcoratger

Copy link
Copy Markdown
Contributor

What it adds

A new file, CompPoly/Multilinear/Unique.lean.

  • CMlPolynomialEval.vertex i: the Boolean vertex with index i, coordinate j being bit j of i, as the rest of the file reads indices.
  • lagrangeBasis_vertex: at a vertex, the Lagrange basis is the indicator of that vertex.
  • eval_vertex: a hypercube table evaluates to its entry i at the vertex i.
  • ext_of_eval_vertex: two tables with the same values at every vertex are equal.
  • MvPolynomial.eq_of_degreeOf_le_one_of_eval_zeroOne: two polynomials of degree at most one in each variable that agree on {0,1}^σ are equal.

The last one is Lemma 3.6 of Thaler, "Proofs, Arguments, and Zero-Knowledge".

Its proof is three lines on top of mathlib's combinatorial Nullstellensatz, with the set {0, 1} in each variable.

Why

CompPoly evaluates hypercube tables, but has no statement that the evaluation interpolates the table, or that the interpolant is unique.

Plonky3-lean needs both to call its multilinear-extension specification "the" extension.

It currently proves them locally, in big-endian order, which is the order Plonky3 uses.

Validation

lake build CompPoly.Multilinear.Unique, scripts/update-lib.sh, scripts/check-imports.sh and scripts/lint-style.sh pass.

No sorry, no native_decide.

A PR against main would rebase this one commit.

References

  • Thaler, "Proofs, Arguments, and Zero-Knowledge", Section 3.5, Lemma 3.6.
  • Alon, "Combinatorial Nullstellensatz", 1999, Theorem 1.2, as MvPolynomial.eq_zero_of_eval_zero_at_prod_finset.

🤖 Generated with Claude Code

…of multilinear interpolants

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
@github-actions

github-actions Bot commented Oct 23, 2026 •

Copy link
Copy Markdown
Contributor

🤖 PR Summary

ℹ️ This PR modifies 1 file(s) under CompPoly/ToMathlib/ — consider whether a corresponding upstream PR is needed.

Mathematical Formalization

  • CompPoly/Multilinear/Unique.lean:

    • Defines Boolean vertices via CMlPolynomialEval.vertex i (vertex coordinates as bits) and proves CMlPolynomialEval.exists_vertex_get_eq that any Boolean point is uniquely indexed.
    • Establishes evaluation properties: CMlPolynomialEval.lagrangeBasis_vertex (Lagrange basis acts as indicator at vertices) and CMlPolynomialEval.eval_vertex (hypercube table returns entry i at vertex i).
    • Develops the bridge between the coefficient-form representation and multivariate polynomials via CMlPolynomial.monomialBasis_vertex, CMlPolynomial.eval_vertex, CMlPolynomial.eval_lagrangeToMono_vertex, CMlPolynomial.eval_toMvPolynomial, and CMlPolynomial.degreeOf_toMvPolynomial_le_one.
    • Proves the central uniqueness results:
      • CMlPolynomial.toMvPolynomial_eq_of_eval_vertex
      • CMlPolynomialEval.toMvPolynomial_eq_of_eval_vertex
        These show that two polynomials of degree ≤1 per variable that agree on all Boolean vertices are equal (i.e., the multilinear extension is uniquely determined by the hypercube table).
  • CompPoly/ToMathlib/MvPolynomial/Nullstellensatz.lean:

    • Introduces the theorem MvPolynomial.eq_of_degreeOf_le_one_of_eval_zeroOne (Lemma 3.6 of Thaler, Proofs, Arguments, and Zero-Knowledge). For an infinite domain R, two polynomials with each variable of degree at most 1 are equal if they coincide on all assignments where each coordinate is 0 or 1.
    • The proof applies the combinatorial Nullstellensatz (Alon, 1999) as found in Mathlib.Combinatorics.Nullstellensatz.
    • This lemma is the foundational ingredient used in the uniqueness proofs of Unique.lean.

Module Imports

  • CompPoly.lean: The import block now publicly re-exports CompPoly.Multilinear.Unique and CompPoly.ToMathlib.MvPolynomial.Nullstellensatz. This is a mechanical change; no new non‑trivial content is added.

Discrepancy with PR Body

The PR body describes only the file CompPoly/Multilinear/Unique.lean and lists a subset of its theorems (e.g., ext_of_eval_vertex does not appear in the code; the actual extensionality statements are CMlPolynomial.toMvPolynomial_eq_of_eval_vertex and CMlPolynomialEval.toMvPolynomial_eq_of_eval_vertex). It omits the second new file CompPoly/ToMathlib/MvPolynomial/Nullstellensatz.lean which contains the combinatorial Nullstellensatz lemma essential to the uniqueness proof. The present overview reflects the actual code as shown by the per‑file summaries.

Validation

  • lake build CompPoly.Multilinear.Unique succeeds.
  • No sorry or native_decide placeholders are introduced anywhere.

Statistics

Metric Count
📝 Files Changed 3
✅ Lines Added 237
❌ Lines Removed 0

Lean Declarations

✏️ Added: 13 declaration(s)

CompPoly/Multilinear/Unique.lean (12)

  • def vertex [Zero R] [One R] (i : Fin (2 ^ n)) : Vector R n
  • private lemma eq_of_bits {i k : Fin (2 ^ n)}
  • theorem degreeOf_toMvPolynomial_le_one [CommSemiring R] (p : CMlPolynomial R n) (j : Fin n) :
  • theorem eval_lagrangeToMono_vertex [CommRing R] (f : CMlPolynomialEval R n) (i : Fin (2 ^ n)) :
  • theorem eval_toMvPolynomial [CommSemiring R] (p : CMlPolynomial R n) (x : Vector R n) :
  • theorem eval_toMvPolynomial_vertex (f : CMlPolynomialEval R n) (i : Fin (2 ^ n)) :
  • theorem eval_vertex [CommRing R] (p : CMlPolynomial R n) (i : Fin (2 ^ n)) :
  • theorem exists_vertex_get_eq [Zero R] [One R] {x : Fin n → R}
  • theorem ext_of_eval_vertex [CommRing R] {p q : CMlPolynomial R n}
  • theorem lagrangeBasis_vertex (i k : Fin (2 ^ n)) :
  • theorem monomialBasis_vertex [CommSemiring R] (i k : Fin (2 ^ n)) :
  • theorem toMvPolynomial_eq_of_eval_vertex [IsDomain R] {f : CMlPolynomialEval R n}

CompPoly/ToMathlib/MvPolynomial/Nullstellensatz.lean (1)

  • theorem eq_of_degreeOf_le_one_of_eval_zeroOne {p q : MvPolynomial σ R}

sorry Tracking

  • No sorrys were added, removed, or affected.

📋 **Additional Analysis**

The diff introduces two new files and registers them in CompPoly.lean imports. It contains a theorem-only addition with no changes to existing code semantics. The review below follows the project's contribution guidelines as supplied, checking adherence to style, naming, documentation, and scope requirements. Since the change is not a performance contribution, a new codec, or a large blueprint-driven formalization, those specific rules are noted only where relevant (e.g., naming, style, docstrings). No unrelated changes were found; all findings are concrete and tied to the diff. No findings on performance, codec, or benchmark gate (not applicable)."

Findings

Scope and title

  • The diff adds a new formalization plus two new files but contains no PR title/description. Per the guidelines, the title must be <type>(<optional-scope>): <subject>. This is a feat (new formalization) with scope multilinear or mvpolynomial, e.g. feat(multilinear): unique multilinear extension via vertices. The description must state motivation, contrast with previous behavior (none), and ideally reference the Thaler Lemma 3.6 as stated in the docstring.

Module and file layout

  • CompPoly/Multilinear/Unique.lean declares module immediately followed by public imports. The repository convention (and AGENTS.md discussed in project docs) expects imports grouped at the top; module must not appear before imports — put the module line after the imports.
  • Both new files lack a module docstring header /-! ... -/; the guidelines require it for each file, including a title, summary, notation, and references. Nullstellensatz.lean has a /-! block but no /-! after the module imports (it is placed after module and imports, which is also non-standard placement).
  • Unique.lean contains a title/comment block but no /-! module docstring; the block is not in docstring syntax. It should be a /-! ... -/ module header.
  • Style: @[expose] public section appears in both new files, but this is not a standard attribute/marker in this repository’s documented style guide and appears in no other file in the diff. If it is a project-specific mechanism, it should be documented; if not, it should be removed.

Naming and statement phrasing

  • The theorem degreeOf_toMvPolynomial_le_one is fine (degreeOf plus _le_one), but the theorem toMvPolynomial_eq_of_eval_vertex uses _of_ with the hypothesis “eval at every vertex”. Per naming logic, _of_ should separate hypotheses in the order they appear; “eval at vertex” is not a named property. A more conventional name would be toMvPolynomial_eq_of_eval_zeroOne or toMvPolynomial_eq_of_vertex_eval, matching the underlying lemma. Same for CMlPolynomialEval.toMvPolynomial_eq_of_eval_vertex.
  • Acronym rule: CMlPolynomial is already an existing type in the codebase; no issue. But new names monomialBasis_vertex, lagrangeBasis_vertex, eval_toMvPolynomial_vertex, eval_lagrangeToMono_vertex are acceptable (snake_case, descriptive).
  • In Nullstellensatz.lean, the lemma name eq_of_degreeOf_le_one_of_eval_zeroOne mixes _of_ with “eval zeroOne”; that is acceptable but may be clearer as eq_of_degreeOf_le_one_of_eval_boolean or eq_of_degreeOf_le_one_of_eval_pair. Not a hard violation.

Docstrings and references

  • Unique.lean claims “The reference is Thaler, ‘Proofs, Arguments, and Zero-Knowledge’, Lemma 3.6.” The repository’s citation standards require: (1) use citation key in text like [Th23] or [Thaler], (2) add a ## References section in the docstring header, (3) add BibTeX entry in blueprint/src/references.bib. This is not done. The raw text has no citation key and no BibTeX entry.
  • Nullstellensatz.lean also states the lemma is “Lemma 3.6 of Thaler, ...” with no citation key or bibliography entry.
  • No module docstrings in either file (see above), and the reference is informal.

Naming and style details

  • Unique.lean uses Vector.ofFn and .get, which is fine. But Nat.binaryFinMapToNat is not a standard mathlib declaration name; it appears to be a new or local helper in this repository. Its name would not follow mathlib conventions and should be documented or renamed if it is public. (In the diff it is not imported (only MvPolynomial, Finset, no BinaryFinMap import); this is a potential issue: an undeclared/unknown name, unless it exists in the repository outside the visible diff. If it is a private helper elsewhere, this should be noted.)
  • In Nullstellensatz.lean, card_pair is being used; in modern mathlib, card_pair has been deprecated/removed, and one may need card_doubleton or Finset.card_pair. If this compiles with the repository’s mathlib, it is fine; otherwise flag as a potential API-drift issue.
  • one_lt_two is the correct theorem in current mathlib; Nat.one_lt_two is deprecated. No issue.
  • split <;> omega in exists_vertex_get_eq is acceptable, but omega usage on Fin bounds can be slow; no performance concern here.
  • simp only [j.isLt, dite_true, Fin.eta, ...] uses dite_true by name; prefer dif_pos/dif_neg, but not a hard violation.
  • In lagrangeBasis_vertex, the proof uses sum_eq_single i ...; that is fine. In eval_vertex the use of sum_eq_single followed by fun h => absurd (mem_univ i) h is somewhat obfuscated, but not a style violation.
  • In Nullstellensatz.lean, the proof has refine sub_eq_zero.mp (...) ...; this is fine.
  • Vector.ext in ext_of_eval_vertex is used; Vector.ext exists in mathlib as Vector.ext, acceptable.

Used/defined helper names and exposed theorem names

  • The new theorem names appear in CompPoly.lean’s public imports but are not added to a documentation index; the guideline says if PR changes recurring guidance or structure, update docs/wiki/, but adding a theorem is not necessarily such a change. No explicit requirement is violated.
  • Both files use @[expose] public section; if this is a project macro, it should not be there absent a definition; otherwise it is unknown syntax and this diff likely does not compile. Flag it as a suspicious marker.

Documentation completeness

  • Every “definition and major theorem” needs a docstring. In Unique.lean, several declarations lack docstrings: exists_vertex_get_eq has one; eq_of_bits has none (private, but still a lemma; guidelines require major theorems, private lemmas optional); lagrangeBasis_vertex has one; eval_vertex has one; ext_of_eval_vertex has one; monomialBasis_vertex has one; CMlPolynomial.eval_vertex has one; eval_lagrangeToMono_vertex has one; ext_of_eval_vertex has one; eval_toMvPolynomial has one; degreeOf_toMvPolynomial_le_one has one; toMvPolynomial_eq_of_eval_vertex has one. In Nullstellensatz.lean, eq_of_degreeOf_le_one_of_eval_zeroOne has one. So all top-level declarations have docstrings.
  • Missing from docstrings: use of LaTeX for math is required; the docstrings use inline math with $, but some use plain text (degree at most one per variable). Acceptable but could be improved.
  • Sectioning comments (/-! ### ... -/) are not used despite the files being moderately long; this is preferred for large files.

Code formatting

  • In Unique.lean, line 22-27 use two-line expressions with Vector.ofFn and fun j =>; line breaks are generally fine.
  • At line 24: (BitVec.ofFin i).getLsb j is fine.
  • At line 58: lagrangeBasis ... [(k : ℕ)] uses notation introduced by the project; fine.
  • There is a style violation regarding operators: in if (BitVec.ofFin i).getLsb j then 1 else 0, the then etc. is fine.
  • In Nullstellensatz.lean, variables are {R σ : Type*}; the project’s variable conventions prefer R, σ, and i, j for indices. That’s okay.
  • In Nullstellensatz.lean, h : ∀ x : σ → R, ... uses a function binder; style prefers ∀ x, ... with variable declared in variable; but here σ and R are variables, so x is not declared in the section? The section declares {R σ : Type*} but not x; so it is necessary. No issue.
  • simp only [mem_insert, mem_singleton] in the proof is consistent.

New types / codec

  • Not applicable: the diff introduces no new type or carrier; it only proves theorems.

Performance contribution

  • Not applicable: no @[csimp], no benchmark changes, no @[implemented_by].

Blueprint / large contribution

  • The diff adds a small lemma and two files; not a “substantial contribution such as a new proof system”; no blueprint needed.

Repository guardrails (AGENTS.md, TCB)

  • No native_decide, no sorry, no axioms added. lake exe axiomsweep --check should be run and should pass; no evidence in diff but not required in review of a patch currently except as a project rule.

Checklist of hard requirements

  • Files are named UpperCamelCase.lean: Unique.lean, Nullstellensatz.lean — compliant.
  • Imports grouped at top: not compliant in both files (imports appear after module and after a block comment in Unique.lean; in Nullstellensatz.lean, module before import).
  • Module headers: not compliant.
  • Copyright headers: present with 2026 and authors — acceptable.
  • No sorry, no tactic hacks: present none.

Suggested minimum fixes

  1. Add proper module docstrings (/-! ... -/) with title, summary, notation, references to both files, and move module line after imports.
  2. Add the Thaler reference to blueprint/src/references.bib and use a citation key in the docstrings (... [Th16] ...), then add ## References.
  3. Add an explicit /-! ### ... -/ section for each namespace.
  4. Either document/remove @[expose] public section or verify it is a project-specific mechanism.
  5. Rename or document Nat.binaryFinMapToNat; if it is not a standard mathlib name, add import or definition.
  6. Prefer a conventional theorem name toMvPolynomial_eq_of_eval_zeroOne.
  7. Consider replacing card_pair with card_doubleton if it fails to compile.

📄 **Per-File Summaries**
  • CompPoly.lean: The import block in CompPoly.lean now publicly exports two new modules: CompPoly.Multilinear.Unique and CompPoly.ToMathlib.MvPolynomial.Nullstellensatz. The former likely provides a uniqueness theorem or definition within the multilinear framework; the latter adapts the Nullstellensatz (a fundamental algebraic geometry result) to MvPolynomial for use in the project. No new sorry or admit are introduced.
  • CompPoly/Multilinear/Unique.lean: This new file CompPoly/Multilinear/Unique.lean adds several theorems establishing evaluation properties for Boolean vertices in the context of multilinear extensions. Specifically, it introduces CMlPolynomialEval.vertex to define Boolean hypercube vertices (coordinates given by bits), CMlPolynomialEval.exists_vertex_get_eq to uniquely index any point with 0/1 coordinates, CMlPolynomialEval.lagrangeBasis_vertex and CMlPolynomialEval.eval_vertex to evaluate Lagrange basis and hypercube tables at vertices, and CMlPolynomial.monomialBasis_vertex, CMlPolynomial.eval_vertex, CMlPolynomial.eval_lagrangeToMono_vertex, CMlPolynomial.eval_toMvPolynomial, and CMlPolynomial.degreeOf_toMvPolynomial_le_one for coefficient forms. Finally, CMlPolynomial.toMvPolynomial_eq_of_eval_vertex and CMlPolynomialEval.toMvPolynomial_eq_of_eval_vertex prove that the MvPolynomial image of a coefficient form or hypercube table is uniquely determined by its vertex values among polynomials of degree at most one per variable.
  • CompPoly/ToMathlib/MvPolynomial/Nullstellensatz.lean: This file introduces MvPolynomial.eq_of_degreeOf_le_one_of_eval_zeroOne, a new theorem stating that two multivariate polynomials over an infinite domain R with each variable of degree at most 1 are equal if they agree on all points of the Boolean hypercube (i.e., assignments where each coordinate is 0 or 1). The proof uses the combinatorial Nullstellensatz from Mathlib.Combinatorics.Nullstellensatz; the file itself is entirely new.

Last updated: 2026-10-27 12:42 UTC.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

@dhsorens dhsorens left a comment •

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Superseded by my review below, which has the comments inline.

@dhsorens dhsorens left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks, this is a nice, tight addition, and the Nullstellensatz proof of Lemma 3.6 is very clean.

Comments are inline. The main one is connecting the two halves (on ext_of_eval_vertex), so that uniqueness applies to CompPoly's own multilinear type.

Note that CI hasn't run on this yet: workflows on a first PR need a maintainer to approve them.

Comment thread CompPoly/Multilinear/Unique.lean Outdated
simp only [Vector.get_eq_getElem, lagrangeBasis_vertex, ite_true, mul_one, Fin.getElem_fin]

/-- Hypercube tables with the same values at every vertex are equal. -/
theorem ext_of_eval_vertex [Nontrivial R] {p q : CMlPolynomialEval R n}

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is where I'd like the two halves connected. Multilinear/Equiv.lean already has toMvPolynomial / equivMvPolynomialDeg1. A lemma stating that a CMlPolynomial and its MvPolynomial image agree at every vertex i would let eq_of_degreeOf_le_one_of_eval_zeroOne apply to CompPoly's own type, which is the uniqueness the PR title promises.

Comment thread CompPoly/Multilinear/Unique.lean Outdated
Nat.testBit_lt_two_pow (lt_of_lt_of_le k.isLt (Nat.pow_le_pow_right two_pos (by omega)))]

/-- At a Boolean vertex the Lagrange basis is the indicator of that vertex. -/
theorem lagrangeBasis_vertex [Nontrivial R] (i k : Fin (2 ^ n)) :

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is [Nontrivial R] needed here, and on eval_vertex and ext_of_eval_vertex? In the trivial ring all three statements hold anyway. If the proofs go through without it, please drop it (docs/wiki/typeclass-minimization.md).

Comment thread CompPoly/Multilinear/Unique.lean Outdated
if (i : ℕ).testBit j = (k : ℕ).testBit j then (1 : R) else 0 := fun j => by
simp only [vertex, Vector.getElem_ofFn, BitVec.getLsb_eq_getElem, Fin.getElem_fin,
BitVec.getElem_ofFin]
by_cases hi : (i : ℕ).testBit j <;> by_cases hk : (k : ℕ).testBit j <;> simp [hi, hk]

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please use simp only [...] here. Same for (by simp) on line 65 and simpa [eval_vertex] on line 71.

Comment thread CompPoly/Multilinear/Unique.lean Outdated

end CompPoly

namespace MvPolynomial

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This lemma is purely about Mathlib's MvPolynomial, so I'd move it to CompPoly/ToMathlib/MvPolynomial/ and import it here. That's where we keep Mathlib-facing material, and it makes upstreaming easier.

- prove that a coefficient form and its `MvPolynomial` image evaluate alike at every point
- evaluate coefficient forms at the Boolean vertices through the zeta transform
- show that the image of a hypercube table is its unique multilinear extension
- drop the unneeded `[Nontrivial R]` assumptions
- move the Nullstellensatz uniqueness lemma to `ToMathlib/MvPolynomial/Nullstellensatz.lean`
- replace bare `simp` and `simpa` calls with `simp only` forms

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
@tcoratger

Copy link
Copy Markdown
Contributor Author

Thanks for the review! All four points are addressed in e220882.

  • Connecting the two halves.
    • CMlPolynomial.eval_toMvPolynomial: a coefficient form and its MvPolynomial image evaluate alike at every point, not only at the vertices.
    • CMlPolynomial.eval_vertex: the vertex values of a coefficient form are its zeta transform.
    • CMlPolynomial.toMvPolynomial_eq_of_eval_vertex and CMlPolynomialEval.toMvPolynomial_eq_of_eval_vertex (over a domain): a polynomial of degree at most one per variable that matches the form, or the table, on the vertices is its image.
    • CMlPolynomialEval.eval_toMvPolynomial_vertex: the image of a table interpolates it.
    • CMlPolynomial.ext_of_eval_vertex: two coefficient forms with the same vertex values are equal, over any commutative ring, via the zeta/Möbius equivalence.
    • Small helpers: exists_vertex_get_eq (every 0/1 point is a vertex) and degreeOf_toMvPolynomial_le_one.
  • [Nontrivial R]. It wasn't needed, so it is gone from all three lemmas. vertex now only asks for [Zero R] [One R].
  • Location. MvPolynomial.eq_of_degreeOf_le_one_of_eval_zeroOne now lives in CompPoly/ToMathlib/MvPolynomial/Nullstellensatz.lean, named after the Mathlib file it would go into. Unique.lean imports it, and CompPoly.lean is regenerated with update-lib.sh.
  • Style. The bare simp [hi, hk], (by simp) and simpa [eval_vertex] are now simp only / simpa only or plain terms, and so is the simpa in the moved lemma.

@dhsorens
dhsorens merged commit d3b9f2a into Verified-zkEVM:main Oct 27, 2026
5 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants