Lagrange interpolation at 0
ProvedBitcoinMuSig.lagrange_interpolate_zeroFor identifiers below and a polynomial of degree below over ZMod n: .
import Definitions.Def_BitcoinMuSig open BitcoinMuSig BitcoinSig BitcoinTaproot
theorem BitcoinMuSig.lagrange_interpolate_zero (S : Finset ℕ) (hS : ∀ i ∈ S, i < n)
(f : Polynomial (ZMod n)) (hdeg : f.degree < S.card) :
∑ i ∈ S, lagrangeCoeff S i * f.eval (i : ZMod n) = f.eval 0 := by sorryRead-back
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinMuSig.lagrange_interpolate_zero
Source file: Thm_BitcoinMuSig_lagrange_interpolate_zero.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. Let be a finite set of natural numbers with for every (so the elements of have pairwise distinct residues mod ; is allowed; may be empty), and let be a polynomial with (i.e. , or and ; for only qualifies). Then, in ,
where is evaluated at the residue , is evaluated at , and
with Mathlib's total inverse on (no primality of is assumed as a hypothesis or instance in the statement).
Definitions used, unfolded
Constants
- is a fixed natural number (the field modulus).
- is a fixed natural number (written in hexadecimal).
- and are fixed natural numbers ( is even: its last hexadecimal digit is ).
Residues mod , Lagrange coefficients and polynomials
- is Mathlib's ; for a natural , is its residue . Mathlib's inverse on is a total function: it is the multiplicative inverse when is coprime to , and . (The definition file does not register primality of as an instance.)
- For a finite set and ,
where the subtraction is in . The empty product is (e.g. or ), and need not belong to (then nothing is removed). A factor with , , would be .
- For a polynomial , is its evaluation at . Its degree takes values in with , which is smaller than every natural number. So means: , or and . For it forces .
- For , is its canonical natural representative.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.