cycle_power_seven_tight_layer_colouring_dvd
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
- simple_graph_cycle_power_seven_cover_four_tight_dvdA tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
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.
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).
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
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.
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'⟩
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.
uses
ne_eq,Fin.ext_iffhave 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 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).
uses
if_true,if_false,Bool.false_eq_true,id,Ne.symm,sub_add_cancelhave 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
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.
uses
zero_add,if_true,if_false,Bool.false_eq_truehave 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⟩
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.
uses
Int.induction_onhave 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
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.
uses
Nat.gcd_dvd_left,Nat.gcd_dvd_right,Nat.le_of_dvdby_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
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.
uses
Nat.gcd_eq_gcd_ab,ZMod.natCast_self,zero_mul,add_zerohave 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
- The pigeonhole lemma `pig` on `Fin 4` is verified by the `omega` decision procedure by viewing elements as integers in {0, 1, 2, 3}.
- The case analysis in the 8-periodicity proof splits on the four Boolean values of (a (q - 2), a (q - 4)), invoking `pig` in each branch.
- The fact that gcd(8, n) divides 4 when 8 does not divide n is closed automatically by `interval_cases` and `decide` on the finite range 1 ≤ g ≤ 8.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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