AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_class_model_vertex_layers

theoremverified

For an optimal (m+1)-layer dyadic cover, with ell(p) the unique layer covering the endpoint pair (p, p+2^m-1) and the class of p cut to the arc of length 2^m, exactly m+1 of the rooted classes at a fixed vertex v are active.

Statement

theorem simple_graph_cycle_power_dyadic_class_model_vertex_layers
    (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))
    (hellroot : ∀ p : ℤ,
      c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n))
    (helluniq : ∀ (p : ℤ) (s : Fin (m + 1)),
      c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p)
    (v : ℤ) :
    (Finset.range (2 ^ m)).sum (fun a =>
      (decide (a < 2 ^ m ∧
        c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) =
          c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n)))).toNat) = m + 1
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 2

The proof, explained

The proof counts the active rooted classes at vertex v by reinterpreting the indicator sum as the cardinality of the subset S of active offsets a < 2^m. It establishes that the assignment mapping an offset a to its layer ℓ(v - a) is a bijection from S to Fin(m + 1). Injectivity is guaranteed by the fact that distinct active classes at v must have different colors, while surjectivity follows from the spanning property of dyadic covers. Since Fin(m + 1) has size m + 1, exactly m + 1 rooted classes are active at v.

  1. The sum of boolean indicators equals the cardinality of the set S of active offsets a < 2^m at vertex v, reducing the problem to showing |S| = m + 1.

    We define P(a) to be the condition that a < 2^m and the vertex v = (v - a) + a belongs to the same monochromatic class as the root v - a in layer ℓ(v - a). Let S be the subset of offsets in {0, ..., 2^m - 1} satisfying P(a). By `bool_sum_eq_card_filter`, summing the boolean indicator of P(a) over a < 2^m equals |S|. Thus, it suffices to prove |S| = m + 1.

    lines 24–31

    uses bool_sum_eq_card_filter

      classical
      let P : ℕ → Prop := fun a => a < 2^m ∧
        c (ell (v-(a : ℤ))) (((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n)) =
          c (ell (v-(a : ℤ))) ((v-(a : ℤ) : ℤ) : ZMod n)
      let S := (range (2^m)).filter (fun a => decide (P a) = true)
      change (range (2^m)).sum (fun a => (decide (P a)).toNat) = m+1
      rw [bool_sum_eq_card_filter]
      change S.card = m+1
  2. To show |S| = m + 1, it suffices to establish that a ↦ ℓ(v - a) is a bijection from S to Fin(m + 1), and the codomain condition holds trivially.

    We apply `card_bij` with the mapping a ↦ ℓ(v - a) from S to the universe of Fin(m + 1). For every a ∈ S, the image ℓ(v - a) is automatically in the universe `univ` of Fin(m + 1) by `mem_univ`.

    lines 32–35

    uses card_bij, mem_univ

      have hcard : S.card = (univ : Finset (Fin (m+1))).card := by
        apply card_bij (s := S) (t := (univ : Finset (Fin (m+1)))) (fun (a : ℕ) _ => ell (v-(a : ℤ)))
        · intro a ha
          exact mem_univ _
  3. The layer assignment a ↦ ℓ(v - a) is injective on S.

    Assume a, b ∈ S satisfy ℓ(v - a) = ℓ(v - b). Since a, b ∈ S, both P(a) and P(b) hold. If a ≠ b, the lemma `simple_graph_cycle_power_dyadic_class_model_disjoint_colours` states that distinct active classes at v cannot share the same layer color, i.e., ℓ(v - a) ≠ ℓ(v - b). This contradicts our equality, so we must have a = b.

    lines 36–41

    uses decide_eq_true_eq, simple_graph_cycle_power_dyadic_class_model_disjoint_colours

        · intro a ha b hb he
          have hPa : P a := by simpa only [decide_eq_true_eq] using (mem_filter.mp ha).2
          have hPb : P b := by simpa only [decide_eq_true_eq] using (mem_filter.mp hb).2
          by_contra hne
          exact (simple_graph_cycle_power_dyadic_class_model_disjoint_colours
            m n hm hn c hc hcov ell hellroot helluniq v a b hPa.1 hPb.1 hne hPa.2 hPb.2) he
  4. The layer assignment a ↦ ℓ(v - a) is surjective onto Fin(m + 1).

    Given any layer s ∈ Fin(m + 1), the spanning property `simple_graph_cycle_power_dyadic_cover_class_spanning` yields an offset a ≤ 2^m - 1 such that in layer s, v - a shares the color of v, and v - a shares the color of its endpoint (v - a) + (2^m - 1). By the uniqueness hypothesis `helluniq`, s must be the unique layer ℓ(v - a) for root v - a. Since a ≤ 2^m - 1, we have a < 2^m by arithmetic (`Nat.two_pow_pos`), and v = (v - a) + a shares the color of root v - a in layer s = ℓ(v - a), so P(a) holds and a ∈ S maps to s.

    lines 42–56

    uses simple_graph_cycle_power_dyadic_cover_class_spanning, Int.cast_sub, Int.cast_natCast, Nat.two_pow_pos, decide_eq_true_eq

        · intro s hs
          obtain ⟨a, ha, hra, hend⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning
            m n hm hn c hc hcov s (v : ZMod n)
          have he : s = ell (v-(a : ℤ)) := helluniq (v-(a : ℤ)) s
            (by simpa only [Int.cast_sub, Int.cast_natCast] using hend.symm)
          have hv : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring
          have haD : a < 2^m := by
            have hpow := Nat.two_pow_pos m
            omega
          have hPa : P a := by
            refine ⟨haD, ?_⟩
            rw [← he, hv]
            simpa only [Int.cast_sub, Int.cast_natCast] using hra.symm
          refine ⟨a, mem_filter.mpr ⟨mem_range.mpr haD, ?_⟩, he.symm⟩
          simpa only [decide_eq_true_eq] using hPa
  5. The cardinality of S is m + 1, completing the proof.

    The bijection established that |S| equals the cardinality of `univ` on Fin(m + 1). By `card_univ` and `Fintype.card_fin`, the cardinality of Fin(m + 1) is m + 1, so |S| = m + 1.

    line 57

    uses card_univ, Fintype.card_fin

      simpa only [card_univ, Fintype.card_fin] using hcard
bool_sum_eq_card_filter
The sum of a boolean predicate over {0, ..., N - 1} equals the cardinality of the sub-finset of elements satisfying the predicate.
card_bij
Two finsets s and t have the same cardinality if there is a function from s to t that maps into t, is injective on s, and is surjective onto t.
mem_univ
Every element of a finite type belongs to the universal finset `univ`.
decide_eq_true_eq
A decidable proposition p is true if and only if decide p = true.
simple_graph_cycle_power_dyadic_class_model_disjoint_colours
In an optimal dyadic cover of a cycle power graph, two distinct offsets a ≠ b at vertex v that define active monochromatic rooted classes cannot share the same layer color.
simple_graph_cycle_power_dyadic_cover_class_spanning
In an optimal dyadic cover, for every layer s and vertex v, there exists an offset a ≤ 2^m - 1 such that v - a has the same color as v in layer s, and v - a has the same color as the endpoint (v - a) + (2^m - 1).
Int.cast_sub
Integer subtraction commutes with casting into an additive group with one, such as ℤ/nℤ.
Int.cast_natCast
Casting a natural number to integers and then into a ring is equal to casting the natural number directly.
Nat.two_pow_pos
The power 2^w is strictly positive for every natural number w.
card_univ
The cardinality of the universal finset `univ` of a finite type equals the cardinality of the type.
Fintype.card_fin
The finite type Fin n has cardinality n.

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/-- Constant active count: exactly m+1 rooted classes are active at each vertex of an optimal dyadic cover. -/theorem simple_graph_cycle_power_dyadic_class_model_vertex_layers    (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))    (hellroot : ∀ p : ℤ,      c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n))    (helluniq : ∀ (p : ℤ) (s : Fin (m + 1)),      c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p)    (v : ℤ) :    (Finset.range (2 ^ m)).sum (fun a =>      (decide (a < 2 ^ m ∧        c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) =          c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n)))).toNat) = m + 1 := by  classical  let P : ℕ → Prop := fun a => a < 2^m ∧    c (ell (v-(a : ℤ))) (((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n)) =      c (ell (v-(a : ℤ))) ((v-(a : ℤ) : ℤ) : ZMod n)  let S := (range (2^m)).filter (fun a => decide (P a) = true)  change (range (2^m)).sum (fun a => (decide (P a)).toNat) = m+1  rw [bool_sum_eq_card_filter]  change S.card = m+1  have hcard : S.card = (univ : Finset (Fin (m+1))).card := by    apply card_bij (s := S) (t := (univ : Finset (Fin (m+1)))) (fun (a : ℕ) _ => ell (v-(a : ℤ)))    · intro a ha      exact mem_univ _    · intro a ha b hb he      have hPa : P a := by simpa only [decide_eq_true_eq] using (mem_filter.mp ha).2      have hPb : P b := by simpa only [decide_eq_true_eq] using (mem_filter.mp hb).2      by_contra hne      exact (simple_graph_cycle_power_dyadic_class_model_disjoint_colours        m n hm hn c hc hcov ell hellroot helluniq v a b hPa.1 hPb.1 hne hPa.2 hPb.2) he    · intro s hs      obtain ⟨a, ha, hra, hend⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning        m n hm hn c hc hcov s (v : ZMod n)      have he : s = ell (v-(a : ℤ)) := helluniq (v-(a : ℤ)) s        (by simpa only [Int.cast_sub, Int.cast_natCast] using hend.symm)      have hv : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring      have haD : a < 2^m := by        have hpow := Nat.two_pow_pos m        omega      have hPa : P a := by        refine ⟨haD, ?_⟩        rw [← he, hv]        simpa only [Int.cast_sub, Int.cast_natCast] using hra.symm      refine ⟨a, mem_filter.mpr ⟨mem_range.mpr haD, ?_⟩, he.symm⟩      simpa only [decide_eq_true_eq] using hPa  simpa only [card_univ, Fintype.card_fin] using hcard
See it in the graphDiscuss this resultChallenge it