Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Optimal reconstruction of cyclic four-support fibres

Proved
Couret.InterIA.Fibres.cyclic_four_optimal_reconstruction

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

couret-programmecouret-unification-20261108

Let n>0n>0n>0, let S⊆Z/nZS\subseteq\mathbb Z/n\mathbb ZS⊆Z/nZ have four elements, and let F(S)\mathcal F(S)F(S) consist of all four-sets with the same ordered-square counts. There exists d≤2d\le2d≤2, equal to the dimension of the binary affine direction of this fibre, with

∣F(S)∣=2d.|\mathcal F(S)|=2^d.∣F(S)∣=2d.

There are ddd fixed membership probes whose answer vectors biject F(S)\mathcal F(S)F(S) with {0,1}d\{0,1\}^d{0,1}d, and a decoder recovering every fibre member. The resulting fixed-query tree has depth exactly ddd and is correct on the fibre. Every correct membership tree has depth at least ddd. This gives an optimal query scheme, including the case d=0d=0d=0.

Preamble
import Definitions.Def_Couret_MembershipDecisionTree_ec39964080f5
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Field.ZMod
import Mathlib.Algebra.MonoidAlgebra.Defs
import Mathlib.Algebra.MonoidAlgebra.MapDomain
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Data.Finset.Insert
import Mathlib.Data.Finset.Prod
import Mathlib.Data.Finset.SymmDiff
import Mathlib.Data.Fintype.EquivFin
import Mathlib.Data.Set.Card
import Mathlib.Data.ZMod.Basic
import Mathlib.Data.ZMod.Units
import Mathlib.FieldTheory.Finiteness
import Mathlib.GroupTheory.OrderOfElement
import Mathlib.LinearAlgebra.AffineSpace.AffineSubspace.Defs
import Mathlib.Tactic.Abel
import Mathlib.Tactic.FinCases
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Ring
import Mathlib.Tactic.Tauto
import Theorems.Thm_Couret_InterIA_Fibres_MembershipTree_depth_lower_bound
import Theorems.Thm_Couret_InterIA_Fibres_MembershipTree_fixed_depth
import Theorems.Thm_Couret_InterIA_Fibres_MembershipTree_fixed_run
import Theorems.Thm_Couret_InterIA_Fibres_cyclic_four_fibre_card_pow_finrank
import Theorems.Thm_Couret_InterIA_Fibres_cyclic_four_fixed_probes
import Theorems.Thm_Couret_InterIA_Fibres_probeAnswers_bijective
import Theorems.Thm_Couret_InterIA_Fibres_probeDecode_correct
import Definitions.Def_Couret_MembershipDecisionTree_ec39964080f5

set_option autoImplicit false
namespace Couret.InterIA.Fibres
open Finset Couret.InterIA.Parity





Formal statement

theorem cyclic_four_optimal_reconstruction (n : ℕ) (hn : 0 < n)
    (S : Finset (ZMod n)) (hS : S.card=4) :
    ∃ d : ℕ, d ≤ 2 ∧
      d=Module.finrank (ZMod 2) (cyclicFibreAffine n hn S hS).direction ∧
      (cyclicFourFibre n S).ncard=2^d ∧
      (∃ (q : Fin d → ZMod n) (decode : (Fin d → Bool) → Finset (ZMod n)),
        Function.Bijective (fun T : cyclicFourFibre n S => probeAnswers q T.val) ∧
        (∀ T ∈ cyclicFourFibre n S, decode (probeAnswers q T)=T) ∧
        (MembershipTree.fixed d q decode).depth=d ∧
        (MembershipTree.fixed d q decode).CorrectOn (cyclicFourFibre n S)) ∧
      (∀ tree : MembershipTree (ZMod n), tree.CorrectOn (cyclicFourFibre n S) → d ≤ tree.depth) := by sorry


end Couret.InterIA.Fibres
Source
Alexandre Couret, Complete four-point convolution fibres and predictive observations on C12: supplementary proof archive, https://zenodo.org/records/23981750; archive Couret_Supplement_Fibres_Cayley_20261105.zip, SHA-256 a12dde197808771ce3beb81d9e6ff1ab2074db9b06695b6816b0f28adbe8be8b; file fibres/lean/OptimalReconstruction.lean, lines 32–51; source file SHA-256 1457b138661a3d14b47428659d147565f70f2bf4fc62982febb5f8ff25a3b478; theorem Couret.InterIA.Fibres.cyclic_four_optimal_reconstruction

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