AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_cover_layer_root_unique

theoremverified

In an optimal (m+1)-layer cover of C_n^{2^m-1}, for each layer s and each vertex v, there is a unique offset a ≤ 2^m-1 such that v-a is the root spanning the class of v in layer s.

Statement

theorem simple_graph_cycle_power_dyadic_cover_layer_root_unique
    (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)
    (s : Fin (m + 1)) (v : ZMod n) :
    ∃! a : ℕ, a ≤ 2 ^ m - 1 ∧
      c s (v - (a : ZMod n)) = c s v ∧
      c s (v - (a : ZMod n)) =
        c s (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n))
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 2

The proof, explained

The proof establishes the unique existence of the root offset a ≤ 2^m - 1 spanning the layer-s color class of v. Existence is provided directly by `simple_graph_cycle_power_dyadic_cover_class_spanning`. For uniqueness, any other candidate offset b satisfies the same boundary conditions, so `simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique` forces the endpoints to coincide in ℤ/nℤ (v - b = v - a), which implies b ≡ a [MOD n]; since both a and b are bounded strictly below n, they must be equal in ℕ.

  1. There exists an offset a ≤ 2^m - 1 spanning the layer-s class of v, reducing the goal to uniqueness.

    By `simple_graph_cycle_power_dyadic_cover_class_spanning`, there exists an offset a ≤ 2^m - 1 such that v - a is monochromatic with v in layer s and spans an interval of length 2^m - 1 (that is, c_s(v - a) = c_s(v - a + 2^m - 1)). Providing this witness reduces the unique existence goal (∃!) to showing that any other offset b satisfying the same properties must equal a.

    lines 19–20

    uses simple_graph_cycle_power_dyadic_cover_class_spanning

      obtain ⟨a, ha⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning m n hm hn c hc hcov s v
      refine ⟨a, ha, ?_⟩
  2. Any candidate offset b satisfies (b : ℤ/nℤ) = (a : ℤ/nℤ).

    Let b be another offset satisfying b ≤ 2^m - 1, c_s(v - b) = c_s(v), and c_s(v - b) = c_s(v - b + 2^m - 1). By transitivity of equality, c_s(v - b) = c_s(v - a). Since both v - b and v - a are endpoints of monochromatic intervals of length 2^m - 1 in the same layer-s fiber, `simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique` applies to show v - b = v - a in ℤ/nℤ. Cancelling v from both sides via `sub_right_inj.mp` yields (b : ℤ/nℤ) = (a : ℤ/nℤ).

    lines 21–24

    uses simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique, sub_right_inj.mp

      intro b hb
      have he := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn (c s) (hc s)
        (v-(b : ZMod n)) (v-(a : ZMod n)) hb.2.2 ha.2.2 (hb.2.1.trans ha.2.1.symm)
      have hecast : (b : ZMod n) = (a : ZMod n) := sub_right_inj.mp he
  3. b = a as natural numbers.

    The equality of the casts in ℤ/nℤ implies the modular congruence b ≡ a [MOD n] by `ZMod.natCast_eq_natCast_iff`. Since a, b ≤ 2^m - 1 and n ≥ 3*(2^m - 1) + 1 > 2^m - 1, both a and b are strictly less than n (verified by `omega`). By `Nat.ModEq.eq_of_lt_of_lt`, two natural numbers strictly less than n that are congruent modulo n are equal.

    line 25

    uses Nat.ModEq.eq_of_lt_of_lt, ZMod.natCast_eq_natCast_iff

      exact Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp hecast) (by omega) (by omega)
simple_graph_cycle_power_dyadic_cover_class_spanning
In an optimal dyadic cover of C_n^{2^m-1}, for each layer s and vertex v, there exists an offset a ≤ 2^m - 1 such that v - a shares the layer-s color of v and spans a monochromatic interval of length 2^m - 1.
simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique
In a layer whose monochromatic pairs are graph edges, if two vertices in the same color class each equal their shift by 2^m - 1, then the two vertices must be identical.
sub_right_inj.mp
In an additive group, if x - y = x - z, then y = z.
Nat.ModEq.eq_of_lt_of_lt
If two natural numbers are congruent modulo m and both are strictly less than m, then they are equal.
ZMod.natCast_eq_natCast_iff
The canonical casts of two natural numbers to ℤ/nℤ are equal if and only if the numbers are congruent modulo 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/-- In an optimal (m+1)-layer cover of C_n^{2^m-1}, for each layer s and each vertex v, there is a unique offset a ≤ 2^m-1 such that v-a is the root spanning the class of v in layer s. -/theorem simple_graph_cycle_power_dyadic_cover_layer_root_unique    (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)    (s : Fin (m + 1)) (v : ZMod n) :    ∃! a : ℕ, a ≤ 2 ^ m - 1 ∧      c s (v - (a : ZMod n)) = c s v ∧      c s (v - (a : ZMod n)) =        c s (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) := by  obtain ⟨a, ha⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning m n hm hn c hc hcov s v  refine ⟨a, ha, ?_⟩  intro b hb  have he := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn (c s) (hc s)    (v-(b : ZMod n)) (v-(a : ZMod n)) hb.2.2 ha.2.2 (hb.2.1.trans ha.2.1.symm)  have hecast : (b : ZMod n) = (a : ZMod n) := sub_right_inj.mp he  exact Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp hecast) (by omega) (by omega)
See it in the graphDiscuss this resultChallenge it