AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_class_model_layer_choice

theoremverified

There is a periodic integer layer map ell assigning to each integer p the unique layer covering the endpoint pair (p, p+2^m-1), with uniqueness among all layers.

Statement

theorem simple_graph_cycle_power_dyadic_class_model_layer_choice
    (m n : ℕ) [NeZero n] (hm : 1 ≤ m)
    (hn : 3 * (2 ^ m - 1) + 1 ≤ n)
    (c : Fin (m + 1) → ZMod n → ZMod n)
    (hc : ∀ s u v, u ≠ v → c s u = c s v →
      (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)
    (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →
      ∃ s, c s u = c s v) :
    ∃ ell : ℤ → Fin (m + 1),
      (∀ p : ℤ, ell (p + (n : ℤ)) = ell p) ∧
      (∀ p : ℤ,
        c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n)) ∧
      (∀ (p : ℤ) (s : Fin (m + 1)),
        c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p)
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The theorem establishes the existence of an n-periodic layer map ℓ : ℤ → Fin(m+1) assigning to each integer p the unique layer covering (p, p + 2^m - 1). By a previously established lemma on cycle power covers, each residue class i ∈ ℤ/nℤ admits a unique layer identifying i with i + 2^m - 1. The map ℓ is constructed by choosing this unique layer on ℤ/nℤ and pulling it back along the quotient projection ℤ → ℤ/nℤ. Periodicity holds because n ≡ 0 (mod n), and the covering and uniqueness properties on ℤ follow directly from the residue-level uniqueness.

  1. We define the candidate layer map ℓ : ℤ → Fin(m+1) by choosing the unique covering layer for each residue class in ℤ/nℤ, reducing the theorem to periodicity, covering, and uniqueness.

    By simple_graph_cycle_power_dyadic_cover_tight_long_edges, for each vertex i ∈ ℤ/nℤ there exists a unique layer s ∈ Fin(m+1) such that c(s, i) = c(s, i + 2^m - 1). Choosing this unique layer gives a map f : ℤ/nℤ → Fin(m+1) and its specification hf. We define the candidate map ℓ : ℤ → Fin(m+1) by ℓ(p) = f(p mod n). Providing ℓ as the existential witness reduces the theorem to three subgoals: showing that ℓ is n-periodic, that ℓ(p) covers (p, p + 2^m - 1), and that ℓ(p) is unique among all layers.

    lines 20–24

    uses simple_graph_cycle_power_dyadic_cover_tight_long_edges

      classical
      have ht := (simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov).1
      let f : ZMod n → Fin (m+1) := fun p => (ht p).choose
      have hf (p : ZMod n) := (ht p).choose_spec
      refine ⟨fun p => f (p : ZMod n), ?_, ?_, ?_⟩
  2. The layer map ℓ is periodic with period n: ℓ(p + n) = ℓ(p) for all p ∈ ℤ.

    For any integer p, the integer p + n projects in ℤ/nℤ to (p mod n) + (n mod n). Since n mod n = 0, this simplifies to p mod n, so f((p + n) mod n) = f(p mod n). This simplification is performed by rewriting with Int.cast_add, Int.cast_natCast, ZMod.natCast_self, and add_zero.

    lines 25–26

    uses Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero

      · intro p
        simp only [Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero]
  3. For every integer p, the layer ℓ(p) covers the endpoint pair (p, p + 2^m - 1).

    By construction, ℓ(p) = f(p mod n). The covering property of f(p mod n) states that c(f(p mod n), p mod n) = c(f(p mod n), (p mod n) + 2^m - 1). Symmetrizing this equality establishes that c(ℓ(p), p + 2^m - 1) = c(ℓ(p), p).

    lines 27–28

      · intro p
        exact (hf (p : ZMod n)).1.symm
  4. The covering layer ℓ(p) is unique: any layer covering (p, p + 2^m - 1) must equal ℓ(p).

    Let s ∈ Fin(m+1) be any layer such that c(s, p + 2^m - 1) = c(s, p). Symmetrizing this hypothesis yields c(s, p) = c(s, p + 2^m - 1). The uniqueness clause in the specification of f(p mod n) then implies s = f(p mod n) = ℓ(p).

    lines 29–30

      · intro p s hs
        exact (hf (p : ZMod n)).2 s hs.symm
add_zero
Adding zero to any element leaves it unchanged: a + 0 = a.
Int.cast_add
The canonical cast from integers to an additive group with one distributes over addition: ↑(a + b) = ↑a + ↑b.
Int.cast_natCast
Casting a natural number to the integers and then into an additive group with one is the same as casting directly from the natural numbers.
simple_graph_cycle_power_dyadic_cover_tight_long_edges
In any (m + 1)-layer cover of the cycle power C_n^{≤ 2^m - 1}, each vertex i ∈ ℤ/nℤ has a unique layer s such that c(s, i) = c(s, i + 2^m - 1), and similarly for dyadic distances 2^m - 2^j.
ZMod.natCast_self
The modulus n is zero when cast into ℤ/nℤ: ↑n = 0.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000/-- Canonical layer assignment: the unique covering layer of each endpoint-distance pair, extended periodically to the integers. -/theorem simple_graph_cycle_power_dyadic_class_model_layer_choice    (m n : ℕ) [NeZero n] (hm : 1 ≤ m)    (hn : 3 * (2 ^ m - 1) + 1 ≤ n)    (c : Fin (m + 1) → ZMod n → ZMod n)    (hc : ∀ s u v, u ≠ v → c s u = c s v →      (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)    (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →      ∃ s, c s u = c s v) :    ∃ ell : ℤ → Fin (m + 1),      (∀ p : ℤ, ell (p + (n : ℤ)) = ell p) ∧      (∀ p : ℤ,        c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n)) ∧      (∀ (p : ℤ) (s : Fin (m + 1)),        c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p) := by  classical  have ht := (simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov).1  let f : ZMod n → Fin (m+1) := fun p => (ht p).choose  have hf (p : ZMod n) := (ht p).choose_spec  refine ⟨fun p => f (p : ZMod n), ?_, ?_, ?_⟩  · intro p    simp only [Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero]  · intro p    exact (hf (p : ZMod n)).1.symm  · intro p s hs    exact (hf (p : ZMod n)).2 s hs.symm
See it in the graphDiscuss this resultChallenge it