Skip to content

feat(ToMathlib): Lagrange interpolation on a coset of the roots of unity - #403

Merged
dhsorens merged 3 commits into
Verified-zkEVM:mainfrom
tcoratger:feat/coset-lagrange-periodic
Oct 27, 2026
Merged

dhsorens merged 3 commits into
Verified-zkEVM:mainfrom
tcoratger:feat/coset-lagrange-periodic

Conversation

@tcoratger

Copy link
Copy Markdown
Contributor

lake build CompPoly.ToMathlib.Polynomial.CosetLagrange passes.

update-lib.sh and check-imports.sh pass.

What it adds

For a primitive n-th root of unity omega and s != 0, the points x_i = s omega^i form the coset s mu_n.

  • Its nodal polynomial is X^n - s^n.
  • The barycentric weight of x_i is x_i / (n s^n).
  • Off the coset, L_i(x) = (x^n - s^n) x_i / (n s^n (x - x_i)).
  • A function of period p on the coset, with n = p m, interpolates to Q(X^m), for Q its interpolant over s^m mu_p.
    n = 8, p = 2, m = 4:   f = (a, b, a, b, a, b, a, b) on s mu_8
                           Q interpolates (a, b) on s^4 mu_2
                           interpolate(f) = Q(X^4)

Why

Plonky3's STARK verifier evaluates periodic columns this way, at O(p) cost instead of O(n).

The Lagrange constants are what its selectors use, unnormalized.

Plonky3-lean proves both against its transcription of p3-commit, for powers of two.

This is the general statement, for any n, staged where every downstream user can reach it.

References

  • Berrut and Trefethen, Barycentric Lagrange Interpolation, SIAM Review 46(3), 2004, for the weights.
  • The periodic evaluator of p3-commit, plonky3/commit/src/domain.rs, for the folding.

🤖 Generated with Claude Code

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.

To be concise, the overview should present the formalization in terms of the new file and its theorems. No headers beyond what are relevant, but the mathematical content is central.


Statistics

Metric Count
📝 Files Changed 2
✅ Lines Added 131
❌ Lines Removed 0

Lean Declarations

✏️ Added: 6 declaration(s)

CompPoly/ToMathlib/Polynomial/CosetLagrange.lean (6)

  • def rootsOfUnityCoset (s ω : F) (n : ℕ) : Fin n → F
  • theorem eval_basis_rootsOfUnityCoset {s ω x : F} {n : ℕ} (hω : IsPrimitiveRoot ω n)
  • theorem interpolate_rootsOfUnityCoset_periodic {s ω : F} {p m : ℕ} [NeZero p]
  • theorem nodalWeight_rootsOfUnityCoset {s ω : F} {n : ℕ} (hω : IsPrimitiveRoot ω n)
  • theorem nodal_rootsOfUnityCoset {s ω : F} {n : ℕ} (hω : IsPrimitiveRoot ω n) (hn : 0 < n) :
  • theorem rootsOfUnityCoset_injective {s ω : F} {n : ℕ} (hω : IsPrimitiveRoot ω n) (hs : s ≠ 0) :

sorry Tracking

  • No sorrys were added, removed, or affected.

📄 **Per-File Summaries**
  • CompPoly/ToMathlib/Polynomial/CosetLagrange.lean: This new file introduces a suite of definitions and theorems for Lagrange interpolation on a coset of the n-th roots of unity, formalizing the formulas needed for a STARK verifier's periodic-column evaluation. It defines rootsOfUnityCoset s ω n as the points s·ωⁱ and proves rootsOfUnityCoset_injective, nodal_rootsOfUnityCoset (nodal polynomial Xⁿ-sⁿ), nodalWeight_rootsOfUnityCoset (barycentric weight xᵢ/(n sⁿ)), eval_basis_rootsOfUnityCoset (Lagrange basis off the coset), and interpolate_rootsOfUnityCoset_periodic (periodic functions interpolate to Q(Xᵐ)). No sorries or admits appear.
  • 1 file(s) filtered as noise (lockfiles, generated, or trivial): CompPoly.lean

Last updated: 2026-10-26 13:31 UTC.

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

Copy link
Copy Markdown
Collaborator

welcome to CompPoly @tcoratger ! :)

@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 useful result to have in one place, and the periodic folding is a nice general statement. The maths reads correctly to me.

A few changes are inline. The main one is the hypothesis on p in interpolate_coset_periodic.

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

theorem interpolate_coset_periodic {s ω : F} {p m : ℕ} (hω : IsPrimitiveRoot ω (p * m))
(hs : s ≠ 0) (hm : 0 < m) (g : Fin p → F) :
interpolate univ (cosetPoints s ω (p * m)) (fun i => g ⟨i % p, Nat.mod_lt _ (by
rcases Nat.eq_zero_or_pos p with rfl | hp

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.

Building the proof of 0 < p inside the statement makes this hard to read and awkward to apply. Could you take (hp : 0 < p) (or [NeZero p]) as a hypothesis and write ⟨i % p, Nat.mod_lt _ hp⟩? The p = 0 case is vacuous anyway, so this also removes the rcases on line 105.

variable {F : Type*} [Field F]

/-- The points `s omega^i` of the coset `s mu_n`. -/
def cosetPoints (s ω : F) (n : ℕ) : Fin n → F := fun i => s * ω ^ (i : ℕ)

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.

These all land in namespace Polynomial (Polynomial.cosetPoints, Polynomial.nodal_coset, ...). Names that generic could collide with Mathlib later. Could they go under a more specific namespace, or get names that say "roots of unity"?

rcases eq_or_ne Q 0 with h | h
· rw [h]; simpa using hp
· exact (natDegree_lt_iff_degree_lt h).mpr hQ
nlinarith

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 Q.natDegree * m < p * m from Q.natDegree < p and 0 < m, so Nat.mul_lt_mul_of_pos_right (or similar) closes it directly without nlinarith.

nodal univ (cosetPoints s ω n) = X ^ n - C (s ^ n) := by
rw [X_pow_sub_C_eq_prod hω hn rfl, nodal_eq,
← Fin.prod_univ_eq_prod_range (fun i => X - C (ω ^ i * s))]
simp [cosetPoints, mul_comm]

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 the bare simp on lines 91 and 106.

- Take `[NeZero p]` in the periodic folding and index with `Fin.ofNat p i`.
- Rename the declarations after the roots-of-unity coset:
  `cosetPoints` -> `rootsOfUnityCoset`, `nodal_coset` -> `nodal_rootsOfUnityCoset`,
  `nodalWeight_coset`, `eval_basis_coset`, `interpolate_coset_periodic` likewise.
- Close the degree bound with `Nat.mul_lt_mul_of_pos_right` instead of `nlinarith`.
- Replace the bare `simp` calls with `simp only [...]`.

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 305f9e9.

  • Hypothesis on p: interpolate_rootsOfUnityCoset_periodic now takes [NeZero p], and the values are indexed by g (Fin.ofNat p i), which is ⟨i % p, _⟩. The inline rcases and the p = 0 branch are gone.
  • Naming: everything is named after the roots-of-unity coset now: rootsOfUnityCoset (was cosetPoints), rootsOfUnityCoset_injective, nodal_rootsOfUnityCoset, nodalWeight_rootsOfUnityCoset, eval_basis_rootsOfUnityCoset and interpolate_rootsOfUnityCoset_periodic. Nothing else in the repo used the old names.
  • nlinarith: the degree bound now closes with Nat.mul_lt_mul_of_pos_right this hm.
  • Style: the bare simp calls are now simp only [...], including the two (n : F) ≠ 0 → 0 < n side goals.

@dhsorens
dhsorens merged commit 1a9f8dc into Verified-zkEVM:main Oct 27, 2026
5 checks passed
@dhsorens

Copy link
Copy Markdown
Collaborator

merging - thanks @tcoratger !

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