Skip to content

feat(Mersenne31): prove circle coset validity and cardinality - #415

Merged
alexanderlhicks merged 2 commits into
Verified-zkEVM:mainfrom
adrienlacombe:codex/circle-index-faithfulness
Nov 18, 2026
Merged

alexanderlhicks merged 2 commits into
Verified-zkEVM:mainfrom
adrienlacombe:codex/circle-index-faithfulness

Conversation

@adrienlacombe

Copy link
Copy Markdown
Contributor

Summary

Follow-up to #310. Prove that circle indices represent distinct points and that valid cosets enumerate exactly their declared number of points.

  • Prove CirclePointIndex.toPoint_injective, preservation of additive order, and the exact order 2^n of subgroupGen n h, including log sizes 0 and 31.
  • Define Coset.Valid by equality of the step's additive order and the declared size. Prove validity for the standard constructors and canonical full and half cosets, and preservation under conjugation.
  • Prove bounded index and point injectivity and range cardinality for valid cosets.
  • Add ordinary-import regression tests and document the guarantees and remaining obligations.

The tests include a zero-step size-two coset that is not valid and a valid singleton half coset that overlaps its conjugate. Coset validity alone does not imply circle-domain validity. Disjointness of domain halves and circle-domain cardinality remain separate follow-up work.

Validation

  • lake build --wfail
  • lake test
  • lake exe axiomsweep --check: 11,145 declarations across 401 modules; zero sorryAx-tainted or non-standard-axiom-tainted declarations.
  • ./scripts/lint-style.sh
  • ./scripts/check-imports.sh
  • uv run --no-project --python 3.12 python scripts/check-docs-integrity.py
  • uv run --no-project --python 3.12 python scripts/check-writing.py --base e28da34
  • git diff --check

All checks passed locally on Lean 4.35.0. No runtime implementations or existing structure fields change.

@chatgpt-codex-connector

chatgpt-codex-connector Bot commented Nov 6, 2026 •

Copy link
Copy Markdown

Codex Review Summary

This comment shows the latest Codex review activity on this pull request.

Review Status Commit Review trigger
📝 Code Review ✅ Completed 2026-11-06T15:56:52.672140Z 4637dd0 PR opened
ℹ️ About Codex in GitHub

Your team has set up Codex to review pull requests in this repo. Reviews are triggered when you

  • Open a pull request for review
  • Mark a draft as ready
  • Comment "@codex review" or "@codex security review".

Codex reacts with 👀 while any review is running, comments if it has suggestions, and reacts with 👍 once all reviews finish with no findings.

@github-actions

github-actions Bot commented Nov 6, 2026 •

Copy link
Copy Markdown
Contributor

🤖 PR Summary

Mathematical Formalization

  • Circle point index injectivity and additive order preservation:

    • CirclePointIndex.toPoint_injective establishes that distinct circle point indices map to distinct points on the circle group.
    • addOrderOf_toPoint and addOrderOf_subgroupGen prove that the additive order of a point equals the order of its index, and that each subgroup generated by subgroupGen n h has exact order 2^n. These results cover the edge cases n = 0 and n = 31.
  • Coset validity:

    • A new predicate Coset.Valid is defined as addOrderOf c.stepSize = c.size (the step’s additive order equals the declared size).
    • Validity is proven for the standard constructors: new_valid, subgroup_valid, odds_valid, halfOdds_valid. For CanonicCoset, both coset_valid and halfCoset_valid are added.
    • Validity is preserved under conjugation (conjugate_valid_iff).
    • For any valid coset, the maps indexAt and pointAt are injective (indexAt_injective, pointAt_injective) and their ranges have the cardinality given by c.size (card_range_indexAt, card_range_pointAt).
  • Consequences and open obligations:

    • The PR explicitly notes that coset validity alone does not imply circle-domain validity (e.g., indices may not be disjoint across the two halves of the domain). The disjointness condition and the cardinality of the full circle domain remain as separate follow-up work.

Documentation

  • docs/wiki/field-extensions.md is updated to reflect the new lemmas and the Coset.Valid predicate, along with the caveat that CircleDomain still needs separate validity, disjointness, and cardinality proofs.

Testing

  • tests/CompPolyTests/Fields/Mersenne31/Circle.lean adds numerous example statements that exercise all the major lemmas: injectivity, additive order transfer, explicit order values for subgroupGen at n = 0,1,30,31, validity of standard cosets, the equivalence valid_iff, injectivity of indexAt and pointAt, cardinality results, and the conjugate_valid_iff.
  • Notable counterexamples include a Coset.mk 0 0 1 that is not valid (zero-step size-two) and a valid singleton half coset whose conjugate overlaps (demonstrating that validity does not guarantee domain disjointness).
  • No sorry or admit appear in the added test code.

Structure: The core mathematical substance is concentrated in CompPoly/Fields/Mersenne31/Circle.lean; the remaining files (docs/wiki/field-extensions.md, the test file) are supporting updates that mirror the same content.


Statistics

Metric Count
📝 Files Changed 3
✅ Lines Added 207
❌ Lines Removed 12

Lean Declarations

✏️ Added: 41 declaration(s)

CompPoly/Fields/Mersenne31/Circle.lean (17)

  • def Valid (c : Coset) : Prop
  • theorem addOrderOf_subgroupGen (n : Nat) (h : n ≤ logOrder) :
  • theorem addOrderOf_toPoint (i : CirclePointIndex) :
  • theorem card_range_indexAt (c : Coset) (hc : c.Valid) :
  • theorem card_range_pointAt (c : Coset) (hc : c.Valid) :
  • theorem conjugate_valid_iff (c : Coset) : c.conjugate.Valid ↔ c.Valid
  • theorem coset_valid (c : CanonicCoset) : c.coset.Valid
  • theorem halfCoset_valid (c : CanonicCoset) : c.halfCoset.Valid
  • theorem halfOdds_valid (n : Nat) (h : n + 2 ≤ logOrder) : (halfOdds n h).Valid
  • theorem indexAt_injective (c : Coset) (hc : c.Valid) :
  • theorem new_valid (i : CirclePointIndex) (n : Nat) (h : n ≤ logOrder) :
  • theorem odds_valid (n : Nat) (h : n + 1 ≤ logOrder) : (odds n h).Valid
  • theorem pointAt_injective (c : Coset) (hc : c.Valid) :
  • theorem subgroup_valid (n : Nat) (h : n ≤ logOrder) : (subgroup n h).Valid
  • theorem toPoint_inj {i j : CirclePointIndex} : toPoint i = toPoint j ↔ i = j
  • theorem toPoint_injective : Function.Injective toPoint
  • theorem valid_iff (c : Coset) : c.Valid ↔ addOrderOf c.stepSize = c.size

tests/CompPolyTests/Fields/Mersenne31/Circle.lean (24)

  • example (c : CanonicCoset) :
  • example (c : CanonicCoset) :
  • example (c : Coset) (hc : c.Valid) (i j : Fin c.size)
  • example (c : Coset) (hc : c.Valid) (i j : Fin c.size)
  • example (c : Coset) (hc : c.Valid) : c.conjugate.Valid
  • example (c : Coset) (hc : c.Valid) :
  • example (c : Coset) (hc : c.Valid) :
  • example (c : Coset) : c.Valid ↔ addOrderOf c.stepSize = c.size
  • example (i : CirclePointIndex) (n : Nat) (h : n ≤ logOrder) :
  • example (i : CirclePointIndex) : CirclePointIndex.toPoint i = 0 ↔ i = 0
  • example (i : CirclePointIndex) :
  • example (i j : CirclePointIndex) :
  • example (n : Nat) (h : n ≤ logOrder) :
  • example : (CircleDomain.new (Coset.subgroup 0 (by decide))).indexAt 0 =
  • example : (Coset.halfOdds 29 (by decide)).Valid
  • example : (Coset.odds 30 (by decide)).Valid
  • example : (Coset.subgroup 0 (by decide)).Valid
  • example : (Coset.subgroup 31 (by decide)).Valid
  • example : Function.Injective CirclePointIndex.toPoint
  • example : addOrderOf (CirclePointIndex.subgroupGen 0 (by decide)) = 1
  • example : addOrderOf (CirclePointIndex.subgroupGen 1 (by decide)) = 2
  • example : addOrderOf (CirclePointIndex.subgroupGen 30 (by decide)) = 2 ^ 30
  • example : addOrderOf (CirclePointIndex.subgroupGen 31 (by decide)) = 2 ^ 31
  • example : ¬ (Coset.mk 0 0 1 (by decide)).Valid

sorry Tracking

  • No sorrys were added, removed, or affected.

📋 **Additional Analysis**

Style and Naming

  • Valid def naming: The predicate def Valid (c : Coset) : Prop := … uses UpperCamelCase, but the style guide states Functions and Terms should use lowerCamelCase. While this is a Prop-valued function and not a typeclass, it still follows the convention for definitions rather than for theorems. Consider renaming to valid to align with lowerCamelCase.
  • All new theorem and lemma names follow snake_case (e.g., addOrderOf_subgroupGen, indexAt_injective, valid_iff). Good.
  • The new Coset.Valid field is a Prop and is used as a field of the structure? Actually it is a standalone def, not a field of Coset. The naming issue stands.

Documentation

  • Missing docstrings:
    • theorem toPoint_inj … (line after toPoint_injective) has no docstring. A simp theorem that is an iff-version of injectivity is a major theorem and should have a docstring.
    • theorem valid_iff … has no docstring. It is the primary interface lemma for Valid. A docstring is expected.
  • All other new definitions and theorems have appropriate docstrings.
  • The module docstring in Circle.lean is updated to reflect the new results; the wiki file field-extensions.md is also updated accordingly. This aligns with the requirement to update matched documentation.

Tests

  • The test file tests/CompPolyTests/Fields/Mersenne31/Circle.lean adds comprehensive examples that check the new theorems, including edge cases (log sizes 0 and 31) and a negative case for a zero-step coset. Good.
  • The test also demonstrates that a valid singleton half coset can still overlap its conjugate, which matches the documentation note that domain validity is follow-up work.

Code Style and Formatting

  • Line length stays under 100 characters in .lean files.
  • Indentation uses 2 spaces consistently.
  • Spaces around :, :=, and infix operators are correct.
  • by is placed at end of line before tactic blocks.
  • No use of ; to separate tactics.
  • No violations of the operator-before-line-break rule.

Validation Commands

  • The diff includes no changes that would require scripts/update-lib.sh or scripts/check-imports.sh. No files are added, renamed, or deleted.
  • No sorrys are added or closed; the axiom baseline is unchanged.
  • The new code compiles as lake build and lake test are expected to pass (the test file is within tests/).

Summary

Overall, the diff is well-structured and follows the project’s guidelines. The two minor issues are the naming of Valid (should be valid per the function naming convention) and the missing docstrings on toPoint_inj and valid_iff.


📄 **Per-File Summaries**
  • CompPoly/Fields/Mersenne31/Circle.lean: Added toPoint_injective, toPoint_inj, addOrderOf_toPoint, and addOrderOf_subgroupGen to establish that CirclePointIndex.toPoint is injective, respects additive order, and that each subgroup step has exact order 2^n. Defined Coset.Valid as addOrderOf c.stepSize = c.size and proved new_valid, subgroup_valid, odds_valid, halfOdds_valid, indexAt_injective, pointAt_injective, card_range_indexAt, card_range_pointAt, and conjugate_valid_iff, showing that valid cosets enumerate distinct indices and points with the declared cardinality. For CanonicCoset, added coset_valid and halfCoset_valid. Updated the module-level documentation to reflect that toPoint is injective and that coset validity now supplies the exact-order condition, while noting that circle domains still need a disjointness condition.
  • docs/wiki/field-extensions.md: Updated docs/wiki/field-extensions.md to document new properties and validity conditions for cosets and circle points. Added CirclePointIndex.toPoint_injective, addOrderOf_toPoint, and addOrderOf_subgroupGen theorems for point distinctness and exact order transfer. Introduced Coset.Valid predicate requiring the step's additive order to equal the declared size, along with proofs that standard constructors satisfy it and that validity is preserved by conjugation. For valid cosets, documented indexAt_injective, pointAt_injective, card_range_indexAt, and card_range_pointAt for distinctness and cardinality results. Clarified that CircleDomain still requires separate domain validity, disjointness, and cardinality proofs, noting that coset validity alone does not guarantee them.
  • tests/CompPolyTests/Fields/Mersenne31/Circle.lean: Added many new example statements demonstrating properties of CirclePointIndex, Coset, and CanonicCoset. These include: injectivity of CirclePointIndex.toPoint via CirclePointIndex.toPoint_injective, equivalence of equality under toPoint via CirclePointIndex.toPoint_inj, preservation of addOrderOf via CirclePointIndex.addOrderOf_toPoint, and explicit addOrderOf values for CirclePointIndex.subgroupGen at n=0,1,30,31. For Coset, the additions assert validity of new, subgroup, odds, and halfOdds constructions (Coset.new_valid, Coset.subgroup_valid, Coset.odds_valid, Coset.halfOdds_valid), the equivalence c.Valid ↔ addOrderOf c.stepSize = c.size (Coset.valid_iff), that c.conjugate.Valid follows from c.Valid (Coset.conjugate_valid_iff), and injectivity of c.indexAt and c.pointAt as well as cardinality results (Coset.indexAt_injective, Coset.pointAt_injective, Coset.card_range_indexAt, Coset.card_range_pointAt). For CanonicCoset, injectivity of pointAt and a cardinality equality are shown. Finally, a counterexample (Coset.mk 0 0 1 is not Valid) and an example demonstrating overlapping indices for a valid singleton half coset were added. No sorry or admit appear.

Last updated: 2026-11-18 00:24 UTC.

@alexanderlhicks
alexanderlhicks enabled auto-merge (squash) November 18, 2026 00:23
@alexanderlhicks
alexanderlhicks merged commit 358c615 into Verified-zkEVM:main Nov 18, 2026
7 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