Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Negated sparse equality exactly compares root sums

Proved
Couret.STROBO2TORS.recoh_normalized_sparse_equal_neg_iff

by alexcour · Nov 8, 2026 · Mathlib c5ea003 (Lean v4.30.0)

couret-programmecouret-unification-20261108

Let ppp be prime, k∈Nk\in\mathbb Nk∈N, ζ\zetaζ primitive of order pk+1p^{k+1}pk+1, and E,FE,FE,F finite exponent lists. Let Np,kN_{p,k}Np,k​ denote reduced cyclotomic sparse terms. Then

SparseEqual⁡(Np,k(E),−Np,k(F))=true⟺∑e∈Eζe=−∑f∈Fζf.\operatorname{SparseEqual}(N_{p,k}(E),-N_{p,k}(F))=\mathrm{true}\Longleftrightarrow\sum_{e\in E}\zeta^e=-\sum_{f\in F}\zeta^f.SparseEqual(Np,k​(E),−Np,k​(F))=true⟺e∈E∑​ζe=−f∈F∑​ζf.

This gives an exact executable comparison up to sign.

Preamble
import Definitions.Def_Couret_RecohCyclotomicNormalization_6797485e207c
import Mathlib.RingTheory.Polynomial.Cyclotomic.Roots
import Mathlib.Tactic
import Theorems.Thm_Couret_STROBO2TORS_recoh_negate_terms_polynomial
import Theorems.Thm_Couret_STROBO2TORS_recoh_root_polynomial_degree
import Mathlib.RingTheory.Polynomial.Cyclotomic.Roots
import Mathlib.Tactic

set_option autoImplicit false

/-!
Exact integer-polynomial normalization for primary character sums.

The parameter `k` is one less than the positive primary exponent: the order
is `p ^ (k + 1)` and the stride is `p ^ k`.  Executable reduction uses lists
of integer monomials.  Mathlib's noncomputable integer-polynomial operations
provide their semantics; complex evaluation occurs in correctness theorems.
The separate Python `cyclotomic_sum` implementation is not extracted from,
or certified by, this module.
-/

namespace Couret.STROBO2TORS

open Polynomial
open scoped BigOperators



























/-! ## Executable sparse terms and their polynomial interpretation -/

























/-! ## Executable equality by summing coefficients at present exponents -/





















Formal statement

theorem recoh_normalized_sparse_equal_neg_iff {p : ℕ} (hp : p.Prime) (k : ℕ)
    {ζ : ℂ} (hζ : IsPrimitiveRoot ζ (p ^ (k + 1))) (es fs : List ℕ) :
    recohSparseEqual (recohReducedTerms p k es)
      (recohNegateTerms (recohReducedTerms p k fs)) = true ↔
      (es.map (ζ ^ ·)).sum = -(fs.map (ζ ^ ·)).sum := by sorry


/-!
## Boundary with the separate Python implementation

`recohRootTerms` uses the same exponent reduction and the same emitted
integer monomials as `cyclotomic_sum` in `../recoh_exact_decoder.py`, with
`order = p ^ (k + 1)` and `stride = p ^ k`.  The Python code subsequently
combines coefficients with `Counter`, omits zeros and sorts by exponent.

The theorems in this module certify the Lean term-list reduction and its
coefficient-summing comparator.  They identify exact equality with equality
of the interpreted integer polynomials and then with complex equality.
They do not certify Python execution, its container operations, parsing,
the extraction of primary orders, or a canonical sorted-list representation.
There is no theorem asserting injectivity of raw monomial lists.

For two normalized triples with prime 2 or 3, the comparator visits at most
twelve exponent positions.  Each test scans both finite term lists.  The
length bounds above do not constitute a bit-complexity theorem: exponent
reduction, integer arithmetic and input reading retain their own costs.
-/


end Couret.STROBO2TORS
Source
Alexandre Couret, Couret — Additive reconstruction: STROBO-4, singleton collisions and RECOH formal proof artifacts, https://zenodo.org/records/23980513; archive COURET_MATHEMATIQUES_20261105.zip, SHA-256 19a3b59aee930df74cab79c27b29e014843bd17179a26fef1261ed6b5a651ab7; file RECOH/lean/RecohCyclotomicNormalization.lean, lines 371–391; source file SHA-256 a32b9cab640a62555c7e6cf6db19b7be429a75e16530887b17a37e8f886e5a45; theorem Couret.STROBO2TORS.recoh_normalized_sparse_equal_neg_iff

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me