AFTD Auto-Formalizing Theoretical Domains

cycle_power_seven_tight_layer_colouring_dvd

theoremverified

Colouring core of the k = 7 lower bound. Positions of Z/n alternate between N-positions (where N holds) and P-positions, a is 4-periodic on the N-positions, and at every N-position p, with X = σ(p-2) if a(p-2) and σ(p-4) otherwise, the values σ p, σ(p-6), X are distinct and differ from both σ(p+1) and σ(p-7). Then 8 divides n. These are the layers of the four classes through the vertices p+1 and p in a tight 4-cover of C_n^7, once the class types are known.

Statement

theorem cycle_power_seven_tight_layer_colouring_dvd (n : ℕ) [NeZero n] (σ : ZMod n → Fin 4)
    (N a : ZMod n → Bool) (hN : ∀ p, N (p + 1) = !N p)
    (ha : ∀ p, N p = true → a p = a (p - 4))
    (hP : ∀ p, N p = true → ∀ X : Fin 4, X = (if a (p - 2) = true then σ (p - 2) else σ (p - 4)) →
      σ p ≠ σ (p - 6) ∧ σ p ≠ X ∧ σ (p - 6) ≠ X ∧
      σ (p + 1) ≠ σ p ∧ σ (p + 1) ≠ σ (p - 6) ∧ σ (p + 1) ≠ X ∧
      σ (p - 7) ≠ σ p ∧ σ (p - 7) ≠ σ (p - 6) ∧ σ (p - 7) ≠ X) :
    8 ∣ n
Source
step for simple_graph_cycle_power_seven_cover_four_tight_dvd (research thread RT-1, open case k = 7 of OP-205, arXiv:2610.15635)
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof establishes that 8 divides n by showing that the colouring σ is 8-periodic across the entire ring ZMod n, but cannot be 4-periodic. By alternating parity and the avoidance conditions at N-positions, a pigeonhole argument on the four colours shows that σ(q - 8) = σ(q) for every q, so σ is invariant under any integer multiple of 8; meanwhile, the avoidance conditions force σ(q - 4) ≠ σ(q) at some position q. If 8 did not divide n, the greatest common divisor gcd(8, n) would divide 4, and Bézout's identity would express 4 as a multiple of 8 modulo n, forcing 4-periodicity everywhere—a contradiction.

  1. The predicate N is 2-periodic: N(p - 2) = N(p) for all p.

    By hypothesis, moving by 1 toggles N: N(p - 2 + 1) = ¬N(p - 2) and N(p) = ¬N(p - 2 + 1). Applying the negation twice gives N(p) = ¬¬N(p - 2) = N(p - 2).

    lines 9–13

      have hN2 : ∀ p, N (p - 2) = N p := by
        intro p
        have h1 := hN (p - 2); have h2 := hN (p - 2 + 1)
        rw [show p - 2 + 1 + 1 = p by ring, h1] at h2
        rw [h2]; simp
  2. If p is an N-position, then all even offsets p - 2, p - 4, p - 6, p - 8, and p + 2 are also N-positions.

    Applying the 2-periodicity of N repeatedly shifts p by even steps, preserving the condition N = true at each offset.

    lines 14–22

      have hNk : ∀ p, N p = true → N (p - 2) = true ∧ N (p - 4) = true ∧ N (p - 6) = true ∧
          N (p - 8) = true ∧ N (p + 2) = true := by
        intro p hp
        have e2 : N (p - 2) = true := by rw [hN2]; exact hp
        have e4 : N (p - 4) = true := by rw [show p - 4 = p - 2 - 2 by ring, hN2]; exact e2
        have e6 : N (p - 6) = true := by rw [show p - 6 = p - 4 - 2 by ring, hN2]; exact e4
        have e8 : N (p - 8) = true := by rw [show p - 8 = p - 6 - 2 by ring, hN2]; exact e6
        have e2' : N (p + 2) = true := by rw [← hN2, show p + 2 - 2 = p by ring]; exact hp
        exact ⟨e2, e4, e6, e8, e2'⟩
  3. Pigeonhole principle on four elements: if b, c, d ∈ Fin 4 are pairwise distinct and both x and e differ from all three, then e = x. automation

    Since Fin 4 has only four elements, the three distinct elements b, c, d leave exactly one available value. Any element distinct from all three must equal that unique remainder, so e must equal x.

    lines 23–27

    uses ne_eq, Fin.ext_iff

      have pig : ∀ x b c d e : Fin 4, x ≠ b → x ≠ c → x ≠ d → b ≠ c → b ≠ d → c ≠ d →
          e ≠ b → e ≠ c → e ≠ d → e = x := by
        intro x b c d e h1 h2 h3 h4 h5 h6 h7 h8 h9
        simp only [ne_eq, Fin.ext_iff] at *
        omega
  4. The layer colouring σ is 8-periodic: σ(q - 8) = σ(q) for every position q.

    We split into cases depending on whether q is an N-position or a P-position. If N(q) holds, all even predecessors q - 2, q - 4, q - 6, q - 8 are N-positions. By 4-periodicity of a on N-positions, a(q - 2) = a(q - 6) and a(q - 4) = a(q - 8). Evaluating the avoidance hypothesis at these points and case-splitting on the Boolean values of a(q - 2) and a(q - 4), three predecessor values always provide three distinct colours that differ from both σ(q) and σ(q - 8). By the pigeonhole lemma `pig`, σ(q - 8) = σ(q). If N(q) is false, then q - 1 is an N-position; the avoidance condition at q - 1 directly ensures that σ(q) and σ(q - 8) avoid the same three distinct colours, so again `pig` gives σ(q - 8) = σ(q).

    lines 29–65

    uses if_true, if_false, Bool.false_eq_true, id, Ne.symm, sub_add_cancel

      have h8 : ∀ q, σ (q - 8) = σ q := by
        intro q
        by_cases hq : N q = true
        · obtain ⟨hq2, hq4, hq6, hq8, -⟩ := hNk q hq
          have a26 := ha (q - 2) hq2
          have a48 := ha (q - 4) hq4
          rw [show q - 2 - 4 = q - 6 by ring] at a26
          rw [show q - 4 - 4 = q - 8 by ring] at a48
          have F0 := hP q hq _ rfl
          have F2 := hP (q - 2) hq2 _ rfl
          have F4 := hP (q - 4) hq4 _ rfl
          have F6 := hP (q - 6) hq6 _ rfl
          have F8 := (hP (q - 8) hq8 _ rfl).2.2.2.1
          rw [show q - 8 + 1 = q - 7 by ring] at F8
          rw [show q - 2 - 2 = q - 4 by ring, show q - 2 - 6 = q - 8 by ring,
            show q - 2 - 4 = q - 6 by ring] at F2
          rw [show q - 4 - 2 = q - 6 by ring, show q - 4 - 4 = q - 8 by ring, ← a26] at F4
          rw [show q - 6 - 2 = q - 8 by ring, ← a48] at F6
          revert F0 F2 F4 F6
          cases h2 : a (q - 2) <;> cases h4 : a (q - 4) <;>
            simp only [if_true, if_false, Bool.false_eq_true] <;>
            intro F0 F2 F4 F6 <;>
            obtain ⟨-, -, -, -, -, -, g1, g2, g3⟩ := id F0
          · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)
              F2.2.2.1 (Ne.symm F4.2.1) (Ne.symm F8)
          · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)
              (Ne.symm F6.2.1) (Ne.symm F4.2.1) (Ne.symm F8)
          · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)
              F2.2.2.1 (Ne.symm F2.1) (Ne.symm F8)
          · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)
              (Ne.symm F6.2.1) (Ne.symm F2.1) (Ne.symm F8)
        · have hp : N (q - 1) = true := by
            have := hN (q - 1); rw [sub_add_cancel] at this; rw [this] at hq; simpa using hq
          obtain ⟨f1, f2, f3, f4, f5, f6, f7, f8, f9⟩ := hP (q - 1) hp _ rfl
          rw [sub_add_cancel] at f4 f5 f6
          rw [show q - 1 - 7 = q - 8 by ring] at f7 f8 f9
          exact pig _ _ _ _ _ f4 f5 f6 f1 f2 f3 f7 f8 f9
  5. The colouring is not 4-periodic everywhere: there exists a position q such that σ(q - 4) ≠ σ(q).

    Because N alternates at adjacent positions, at least one of 0 or 1 is an N-position; call it p. Then p + 2 is also an N-position. Evaluating the avoidance hypothesis at p and p + 2 and considering the Boolean values of a(p - 2) and a(p), one of the distinctness conditions directly yields σ(p - 4) ≠ σ(p) in three cases and σ((p + 2) - 4) ≠ σ(p + 2) in the fourth.

    lines 67–82

    uses zero_add, if_true, if_false, Bool.false_eq_true

      have hex : ∃ q, σ (q - 4) ≠ σ q := by
        obtain ⟨p, hp⟩ : ∃ p, N p = true := by
          by_cases h0 : N 0 = true
          · exact ⟨0, h0⟩
          · refine ⟨1, ?_⟩; have := hN 0; rw [zero_add] at this; rw [this]; simpa using h0
        obtain ⟨-, -, -, -, hp2⟩ := hNk p hp
        have F0 := hP p hp _ rfl
        have F2 := hP (p + 2) hp2 _ rfl
        rw [show p + 2 - 2 = p by ring, show p + 2 - 6 = p - 4 by ring] at F2
        revert F0 F2
        cases h2 : a (p - 2) <;> cases h0 : a p <;>
          simp only [if_true, if_false, Bool.false_eq_true] <;> intro F0 F2
        · exact ⟨p, fun h => F0.2.1 h.symm⟩
        · exact ⟨p, fun h => F0.2.1 h.symm⟩
        · exact ⟨p + 2, fun h => F2.2.1 h.symm⟩
        · exact ⟨p, F2.2.2.1⟩
  6. The colouring is invariant under any integer multiple of 8: σ(q + 8z) = σ(q) for all z ∈ ℤ and all q.

    This is proved by integer induction on z. The base case z = 0 is immediate. The step from k to k + 1 applies 8-periodicity `h8` to the shifted point and simplifies using the induction hypothesis. The step from -k to -k - 1 similarly applies 8-periodicity and ring arithmetic.

    lines 83–94

    uses Int.induction_on

      have hZ : ∀ z : ℤ, ∀ q, σ (q + 8 * (z : ZMod n)) = σ q := by
        intro z
        induction z using Int.induction_on with
        | zero => intro q; simp
        | succ k ih =>
          intro q
          have := h8 (q + 8 * (((k : ℤ) + 1 : ℤ) : ZMod n))
          rw [← this, ← ih q]; congr 1; push_cast; ring
        | pred k ih =>
          intro q
          have := h8 (q + 8 * ((-(k : ℤ) : ℤ) : ZMod n))
          rw [ih q] at this; rw [← this]; congr 1; push_cast; ring
  7. Assuming 8 does not divide n, the greatest common divisor g = gcd(8, n) divides 4. automation

    By definition, g divides 8, so g ≤ 8. If g were 8, then 8 would divide n, contradicting the assumption. Exhausting the remaining divisors of 8 (namely 1, 2, and 4) shows that g must divide 4.

    lines 95–103

    uses Nat.gcd_dvd_left, Nat.gcd_dvd_right, Nat.le_of_dvd

      by_contra hnd
      obtain ⟨g, hg⟩ : ∃ g, g = Nat.gcd 8 n := ⟨_, rfl⟩
      have hg8 : g ∣ 8 := hg ▸ Nat.gcd_dvd_left 8 n
      have hgn : g ∣ n := hg ▸ Nat.gcd_dvd_right 8 n
      have hg4 : g ∣ 4 := by
        have hgle : g ≤ 8 := Nat.le_of_dvd (by norm_num) hg8
        have hne : g ≠ 8 := fun h => hnd (h ▸ hgn)
        interval_cases g <;> first | decide | (exfalso; revert hg8; decide) | exact absurd rfl hne
      obtain ⟨w, hw⟩ := hg4
  8. In ZMod n, shifting by 4 is equivalent to shifting by a multiple of 8, which forces σ(q - 4) = σ(q) everywhere and contradicts non-4-periodicity.

    Since g divides 4, we write 4 = g * w for some integer w. By Bézout's identity, g = 8 * gcdA(8, n) + n * gcdB(8, n). Multiplying by w gives 4 = 8(gcdA(8, n) * w) + n(gcdB(8, n) * w). Reducing modulo n annihilates the n-term, so 4 = 8(gcdA(8, n) * w) in ZMod n. Thus shifting by -4 equals shifting by an integer multiple of 8, so by the invariance lemma `hZ`, σ(q - 4) = σ(q) for all q. This contradicts the existence of a position where σ(q - 4) ≠ σ(q), completing the proof that 8 divides n.

    lines 104–114

    uses Nat.gcd_eq_gcd_ab, ZMod.natCast_self, zero_mul, add_zero

      have hb : ((Nat.gcd 8 n : ℕ) : ℤ) = 8 * Nat.gcdA 8 n + n * Nat.gcdB 8 n := Nat.gcd_eq_gcd_ab 8 n
      have h4z : ((4 : ℤ) : ZMod n) = ((8 * (Nat.gcdA 8 n * w) + n * (Nat.gcdB 8 n * w) : ℤ) : ZMod n) := by
        congr 1
        have : (4 : ℤ) = ((g * w : ℕ) : ℤ) := by rw [← hw]; rfl
        rw [this, hg]; push_cast; rw [hb]; ring
      push_cast at h4z
      rw [ZMod.natCast_self, zero_mul, add_zero] at h4z
      obtain ⟨q, hq⟩ := hex
      apply hq
      rw [← hZ (-(Nat.gcdA 8 n * w)) q]
      congr 1; push_cast; linear_combination (-1 : ZMod n) * h4z
ne_eq
inequality a ≠ b is defined as the negation ¬(a = b)
Fin.ext_iff
two elements of Fin n are equal if and only if their underlying natural number values are equal
if_true
an if-then-else expression with a true condition evaluates to its then-branch
if_false
an if-then-else expression with a false condition evaluates to its else-branch
Bool.false_eq_true
the proposition (false = true) is equivalent to False
id
the identity function, returning its argument unchanged
Ne.symm
inequality is symmetric: if a ≠ b then b ≠ a
sub_add_cancel
in an additive group, subtracting and then adding the same element restores the original value: (a - b) + b = a
zero_add
zero is the left additive identity: 0 + a = a
Int.induction_on
induction principle for integers: a property holding at 0 and preserved by successor and predecessor holds for all integers
Nat.gcd_dvd_left
the greatest common divisor gcd(m, n) divides m
Nat.gcd_dvd_right
the greatest common divisor gcd(m, n) divides n
Nat.le_of_dvd
a positive divisor of a positive integer is at most that integer: if m ∣ n and 0 < n, then m ≤ n
Nat.gcd_eq_gcd_ab
Bézout's identity: gcd(x, y) = x * gcdA(x, y) + y * gcdB(x, y) in the integers
ZMod.natCast_self
in the ring ZMod n, the canonical image of n is 0
zero_mul
multiplication by zero on the left yields zero: 0 * a = 0
add_zero
zero is the right additive identity: a + 0 = a

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

theorem cycle_power_seven_tight_layer_colouring_dvd (n : ℕ) [NeZero n] (σ : ZMod n → Fin 4)    (N a : ZMod n → Bool) (hN : ∀ p, N (p + 1) = !N p)    (ha : ∀ p, N p = true → a p = a (p - 4))    (hP : ∀ p, N p = true → ∀ X : Fin 4, X = (if a (p - 2) = true then σ (p - 2) else σ (p - 4)) →      σ p ≠ σ (p - 6) ∧ σ p ≠ X ∧ σ (p - 6) ≠ X ∧      σ (p + 1) ≠ σ p ∧ σ (p + 1) ≠ σ (p - 6) ∧ σ (p + 1) ≠ X ∧      σ (p - 7) ≠ σ p ∧ σ (p - 7) ≠ σ (p - 6) ∧ σ (p - 7) ≠ X) :    8 ∣ n := by  have hN2 : ∀ p, N (p - 2) = N p := by    intro p    have h1 := hN (p - 2); have h2 := hN (p - 2 + 1)    rw [show p - 2 + 1 + 1 = p by ring, h1] at h2    rw [h2]; simp  have hNk : ∀ p, N p = true → N (p - 2) = true ∧ N (p - 4) = true ∧ N (p - 6) = true ∧      N (p - 8) = true ∧ N (p + 2) = true := by    intro p hp    have e2 : N (p - 2) = true := by rw [hN2]; exact hp    have e4 : N (p - 4) = true := by rw [show p - 4 = p - 2 - 2 by ring, hN2]; exact e2    have e6 : N (p - 6) = true := by rw [show p - 6 = p - 4 - 2 by ring, hN2]; exact e4    have e8 : N (p - 8) = true := by rw [show p - 8 = p - 6 - 2 by ring, hN2]; exact e6    have e2' : N (p + 2) = true := by rw [← hN2, show p + 2 - 2 = p by ring]; exact hp    exact ⟨e2, e4, e6, e8, e2'⟩  have pig : ∀ x b c d e : Fin 4, x ≠ b → x ≠ c → x ≠ d → b ≠ c → b ≠ d → c ≠ d →      e ≠ b → e ≠ c → e ≠ d → e = x := by    intro x b c d e h1 h2 h3 h4 h5 h6 h7 h8 h9    simp only [ne_eq, Fin.ext_iff] at *    omega  -- the layers repeat at distance 8  have h8 : ∀ q, σ (q - 8) = σ q := by    intro q    by_cases hq : N q = true    · obtain ⟨hq2, hq4, hq6, hq8, -⟩ := hNk q hq      have a26 := ha (q - 2) hq2      have a48 := ha (q - 4) hq4      rw [show q - 2 - 4 = q - 6 by ring] at a26      rw [show q - 4 - 4 = q - 8 by ring] at a48      have F0 := hP q hq _ rfl      have F2 := hP (q - 2) hq2 _ rfl      have F4 := hP (q - 4) hq4 _ rfl      have F6 := hP (q - 6) hq6 _ rfl      have F8 := (hP (q - 8) hq8 _ rfl).2.2.2.1      rw [show q - 8 + 1 = q - 7 by ring] at F8      rw [show q - 2 - 2 = q - 4 by ring, show q - 2 - 6 = q - 8 by ring,        show q - 2 - 4 = q - 6 by ring] at F2      rw [show q - 4 - 2 = q - 6 by ring, show q - 4 - 4 = q - 8 by ring, ← a26] at F4      rw [show q - 6 - 2 = q - 8 by ring, ← a48] at F6      revert F0 F2 F4 F6      cases h2 : a (q - 2) <;> cases h4 : a (q - 4) <;>        simp only [if_true, if_false, Bool.false_eq_true] <;>        intro F0 F2 F4 F6 <;>        obtain ⟨-, -, -, -, -, -, g1, g2, g3⟩ := id F0      · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)          F2.2.2.1 (Ne.symm F4.2.1) (Ne.symm F8)      · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)          (Ne.symm F6.2.1) (Ne.symm F4.2.1) (Ne.symm F8)      · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)          F2.2.2.1 (Ne.symm F2.1) (Ne.symm F8)      · exact pig _ _ _ _ _ F0.1 F0.2.1 (Ne.symm g1) F0.2.2.1 (Ne.symm g2) (Ne.symm g3)          (Ne.symm F6.2.1) (Ne.symm F2.1) (Ne.symm F8)    · have hp : N (q - 1) = true := by        have := hN (q - 1); rw [sub_add_cancel] at this; rw [this] at hq; simpa using hq      obtain ⟨f1, f2, f3, f4, f5, f6, f7, f8, f9⟩ := hP (q - 1) hp _ rfl      rw [sub_add_cancel] at f4 f5 f6      rw [show q - 1 - 7 = q - 8 by ring] at f7 f8 f9      exact pig _ _ _ _ _ f4 f5 f6 f1 f2 f3 f7 f8 f9  -- somewhere the layers do not repeat at distance 4  have hex : ∃ q, σ (q - 4) ≠ σ q := by    obtain ⟨p, hp⟩ : ∃ p, N p = true := by      by_cases h0 : N 0 = true      · exact ⟨0, h0⟩      · refine ⟨1, ?_⟩; have := hN 0; rw [zero_add] at this; rw [this]; simpa using h0    obtain ⟨-, -, -, -, hp2⟩ := hNk p hp    have F0 := hP p hp _ rfl    have F2 := hP (p + 2) hp2 _ rfl    rw [show p + 2 - 2 = p by ring, show p + 2 - 6 = p - 4 by ring] at F2    revert F0 F2    cases h2 : a (p - 2) <;> cases h0 : a p <;>      simp only [if_true, if_false, Bool.false_eq_true] <;> intro F0 F2    · exact ⟨p, fun h => F0.2.1 h.symm⟩    · exact ⟨p, fun h => F0.2.1 h.symm⟩    · exact ⟨p + 2, fun h => F2.2.1 h.symm⟩    · exact ⟨p, F2.2.2.1⟩  have hZ : ∀ z : ℤ, ∀ q, σ (q + 8 * (z : ZMod n)) = σ q := by    intro z    induction z using Int.induction_on with    | zero => intro q; simp    | succ k ih =>      intro q      have := h8 (q + 8 * (((k : ℤ) + 1 : ℤ) : ZMod n))      rw [← this, ← ih q]; congr 1; push_cast; ring    | pred k ih =>      intro q      have := h8 (q + 8 * ((-(k : ℤ) : ℤ) : ZMod n))      rw [ih q] at this; rw [← this]; congr 1; push_cast; ring  by_contra hnd  obtain ⟨g, hg⟩ : ∃ g, g = Nat.gcd 8 n := ⟨_, rfl⟩  have hg8 : g ∣ 8 := hg ▸ Nat.gcd_dvd_left 8 n  have hgn : g ∣ n := hg ▸ Nat.gcd_dvd_right 8 n  have hg4 : g ∣ 4 := by    have hgle : g ≤ 8 := Nat.le_of_dvd (by norm_num) hg8    have hne : g ≠ 8 := fun h => hnd (h ▸ hgn)    interval_cases g <;> first | decide | (exfalso; revert hg8; decide) | exact absurd rfl hne  obtain ⟨w, hw⟩ := hg4  have hb : ((Nat.gcd 8 n : ℕ) : ℤ) = 8 * Nat.gcdA 8 n + n * Nat.gcdB 8 n := Nat.gcd_eq_gcd_ab 8 n  have h4z : ((4 : ℤ) : ZMod n) = ((8 * (Nat.gcdA 8 n * w) + n * (Nat.gcdB 8 n * w) : ℤ) : ZMod n) := by    congr 1    have : (4 : ℤ) = ((g * w : ℕ) : ℤ) := by rw [← hw]; rfl    rw [this, hg]; push_cast; rw [hb]; ring  push_cast at h4z  rw [ZMod.natCast_self, zero_mul, add_zero] at h4z  obtain ⟨q, hq⟩ := hex  apply hq  rw [← hZ (-(Nat.gcdA 8 n * w)) q]  congr 1; push_cast; linear_combination (-1 : ZMod n) * h4z
See it in the graphDiscuss this resultChallenge it