circulant_cycle_remainder_bound
For t < g and steps with quotient q_i ∈ {0, 1} and remainder r_i bounded by (z+1)/2 (and at most z/2 when q_i = 1), the sum of remainders R satisfies R ≤ m, and if Q = ∑ q_i is odd then R < m.
Statement
theorem circulant_cycle_remainder_bound (z g t : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) (ht : t < g) (q r : Fin t → ℕ) (hq : ∀ i, q i ≤ 1) (hr : ∀ i, r i ≤ (z + 1) / 2) (hr_q : ∀ i, q i = 1 → r i ≤ z / 2) : let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) let m := N / 2 let Q := ∑ i : Fin t, q i let R := ∑ i : Fin t, r i R ≤ m ∧ (Odd Q → R < m)
- Source
- step towards circulant_mixed_graph_no_cycle_lt_g
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- circulant_mixed_graph_no_cycle_lt_gFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices contains no mixed cycle of length t < g.
The proof, explained
The proof proceeds by case analysis on the parity of z. When z is even, the remainder bound simplifies to r_i ≤ z/2 for all steps, yielding R ≤ t(z/2) ≤ (g - 1)(z/2) < m, so R < m holds strictly and unconditionally. When z is odd, the general bound gives R ≤ t((z + 1)/2) ≤ (g - 1)((z + 1)/2) = m; if Q is odd, at least one step must have quotient q_j = 1, which strictly tightens that remainder to r_j ≤ z/2 < (z + 1)/2 and forces the overall sum to satisfy R < m.
Introduce the local definitions N, m, Q, and R.
Introduce the local values N, m = ⌊N/2⌋, the sum of quotients Q = ∑ q_i, and the sum of remainders R = ∑ r_i into the scope.
open Finset in intro N m Q R
Split into cases on whether z is even or odd.
We analyze the definition of N by performing a case split on the parity of z.
by_cases heven : Even zWhen z is even, N = z(g - 1) + 2 and m = (z/2)(g - 1) + 1.
Under the assumption that z is even, N evaluates to z(g - 1) + 2 by `if_pos`. Writing z = 2k, we have N = 2(k(g - 1) + 1), so integer division by 2 gives m = k(g - 1) + 1 = (z/2)(g - 1) + 1.
uses
if_pos· have hN : N = z * (g - 1) + 2 := if_pos heven have hm : m = (z / 2) * (g - 1) + 1 := by dsimp [m] rw [hN] obtain ⟨k, rfl⟩ := heven have h1 : (k + k) * (g - 1) + 2 = 2 * (k * (g - 1)) + 2 := by ring have h2 : (k + k) / 2 = k := by omega rw [h1, h2] omega
When z is even, the sum of remainders satisfies R ≤ t · (z/2).
Since z is even, ⌊(z + 1)/2⌋ = z/2. The general hypothesis r_i ≤ ⌊(z + 1)/2⌋ therefore means r_i ≤ z/2 for every index i. Summing this uniform bound over all t terms using `sum_le_card_nsmul` gives R ≤ t · (z/2).
uses
sum_le_card_nsmulhave hR : R ≤ t * (z / 2) := by dsimp [R] have hr' : ∀ i, r i ≤ z / 2 := by intro i have := hr i obtain ⟨k, rfl⟩ := heven omega simpa using sum_le_card_nsmul (univ : Finset (Fin t)) r (z / 2) (fun i _ => hr' i)
When z is even, R < m, which implies both R ≤ m and (Odd Q → R < m).
Because t < g, we have t ≤ g - 1 by `Nat.le_pred_of_lt`. Multiplying by z/2 via `Nat.mul_le_mul_right` gives t(z/2) ≤ (g - 1)(z/2) = (z/2)(g - 1). Therefore R ≤ (z/2)(g - 1) < (z/2)(g - 1) + 1 = m. The strict bound R < m immediately yields R ≤ m (via `le_of_lt`) and trivially implies R < m when Q is odd.
uses
Nat.mul_le_mul_right,Nat.le_pred_of_lt,mul_comm,le_of_lthave ht_le : t * (z / 2) ≤ (g - 1) * (z / 2) := Nat.mul_le_mul_right (z / 2) (Nat.le_pred_of_lt ht) have hcomm : (g - 1) * (z / 2) = (z / 2) * (g - 1) := mul_comm _ _ have hlt : R < m := by omega exact ⟨le_of_lt hlt, fun _ => hlt⟩
When z is odd, writing z = 2k + 1, N = (z + 1)(g - 1) and m = ((z + 1)/2)(g - 1) = (k + 1)(g - 1).
When z is not even, N evaluates to (z + 1)(g - 1) by `if_neg`. Since z is odd (`Nat.not_even_iff_odd.mp`), we write z = 2k + 1. Then z + 1 = 2(k + 1), so (z + 1)/2 = k + 1 and m = ⌊N/2⌋ = (k + 1)(g - 1) = ((z + 1)/2)(g - 1).
uses
if_neg,Nat.not_even_iff_odd.mp· have hN : N = (z + 1) * (g - 1) := if_neg heven have hodz : Odd z := Nat.not_even_iff_odd.mp heven obtain ⟨k, rfl⟩ := hodz have hm : m = ((2 * k + 1 + 1) / 2) * (g - 1) := by dsimp [m] rw [hN] have h1 : (2 * k + 1 + 1) * (g - 1) = 2 * ((k + 1) * (g - 1)) := by ring have h2 : (2 * k + 1 + 1) / 2 = k + 1 := by omega rw [h1, h2] omega
When z is odd, R ≤ m holds, and it remains to show R < m when Q is odd.
Each remainder satisfies r_i ≤ (z + 1)/2, so by `sum_le_card_nsmul` the sum satisfies R ≤ t · ((z + 1)/2). Since t ≤ g - 1, we have t · ((z + 1)/2) ≤ (g - 1) · ((z + 1)/2) = m using `Nat.mul_le_mul_right` and `mul_comm`. Hence R ≤ m. We then assume Q is odd and aim to prove R < m.
uses
sum_le_card_nsmul,Nat.mul_le_mul_right,Nat.le_pred_of_lt,mul_commhave hR_le_t : R ≤ t * ((2 * k + 1 + 1) / 2) := by dsimp [R] simpa using sum_le_card_nsmul (univ : Finset (Fin t)) r ((2 * k + 1 + 1) / 2) (fun i _ => hr i) have ht_le : t * ((2 * k + 1 + 1) / 2) ≤ (g - 1) * ((2 * k + 1 + 1) / 2) := Nat.mul_le_mul_right ((2 * k + 1 + 1) / 2) (Nat.le_pred_of_lt ht) have hcomm : (g - 1) * ((2 * k + 1 + 1) / 2) = ((2 * k + 1 + 1) / 2) * (g - 1) := mul_comm _ _ have hR_le_m : R ≤ m := by omega refine ⟨hR_le_m, fun hQ => ?_⟩
If Q is odd, there exists at least one index j with q_j = 1.
Suppose no index has q_j = 1. Since q_i ≤ 1 for all i, this would mean every q_i = 0, so Q = ∑ q_i = 0. But 0 is not odd (`Nat.not_odd_zero`), contradicting the assumption that Q is odd. Thus some index j must have q_j = 1.
uses
Nat.not_odd_zerohave hj : ∃ j : Fin t, q j = 1 := by by_contra! h have h0 : ∀ i : Fin t, q i = 0 := by intro i have := hq i have := h i omega have hsum : Q = 0 := by dsimp [Q] simp [h0] rw [hsum] at hQ exact Nat.not_odd_zero hQ obtain ⟨j, hj1⟩ := hj
At the index j where q_j = 1, the remainder satisfies r_j < (z + 1)/2.
By hypothesis `hr_q`, q_j = 1 implies r_j ≤ ⌊z/2⌋ = ⌊(2k + 1)/2⌋ = k. Since (z + 1)/2 = k + 1, this gives r_j ≤ k < k + 1 = (z + 1)/2.
have hrj : r j < (2 * k + 1 + 1) / 2 := by have := hr_q j hj1 omega
Since r_j is strictly smaller than (z + 1)/2, R < t · ((z + 1)/2) ≤ m, concluding R < m.
Because r_i ≤ (z + 1)/2 for all indices and the inequality is strict at index j, `sum_lt_sum` ensures R = ∑ r_i < ∑ (z + 1)/2 = t · ((z + 1)/2). Combining this with t ≤ g - 1 yields R < (g - 1) · ((z + 1)/2) = m via linear arithmetic (`omega`).
uses
sum_lt_sum,mem_univhave hR_lt_t : R < t * ((2 * k + 1 + 1) / 2) := by dsimp [R] have h1 : ∑ i : Fin t, r i < ∑ i : Fin t, ((2 * k + 1 + 1) / 2) := by apply sum_lt_sum · intro i _ exact hr i · exact ⟨j, mem_univ j, hrj⟩ have h2 : ∑ i : Fin t, ((2 * k + 1 + 1) / 2) = t * ((2 * k + 1 + 1) / 2) := by simp omega omega
if_pos- If a proposition P is true, then `if P then a else b` equals `a`.
if_neg- If a proposition P is false, then `if P then a else b` equals `b`.
sum_le_card_nsmul- If each element f(x) of a finset s is bounded by c, then the sum ∑_{x ∈ s} f(x) is at most |s| · c.
Nat.mul_le_mul_right- If a ≤ b, then a · c ≤ b · c for natural numbers.
Nat.le_pred_of_lt- If a < b, then a ≤ b - 1 for natural numbers.
mul_comm- Multiplication is commutative: a · b = b · a.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
Nat.not_even_iff_odd.mp- If a natural number is not even, it is odd.
Nat.not_odd_zero- Zero is not an odd number.
sum_lt_sum- If f(i) ≤ g(i) for all i in s and f(j) < g(j) for at least one j in s, then ∑_{i ∈ s} f(i) < ∑_{i ∈ s} g(i).
mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
- In the case where z is even, the strict inequality R < m holds unconditionally (regardless of the parity of Q), which immediately implies both R ≤ m and (Odd Q → R < m).
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.
/-- For t < g and steps with quotient q_i ∈ {0, 1} and remainder r_i bounded by (z+1)/2 (and at most z/2 when q_i = 1), the sum of remainders R satisfies R ≤ m, and if Q = ∑ q_i is odd then R < m. -/theorem circulant_cycle_remainder_bound (z g t : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) (ht : t < g) (q r : Fin t → ℕ) (hq : ∀ i, q i ≤ 1) (hr : ∀ i, r i ≤ (z + 1) / 2) (hr_q : ∀ i, q i = 1 → r i ≤ z / 2) : let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) let m := N / 2 let Q := ∑ i : Fin t, q i let R := ∑ i : Fin t, r i R ≤ m ∧ (Odd Q → R < m) := by open Finset in intro N m Q R by_cases heven : Even z · have hN : N = z * (g - 1) + 2 := if_pos heven have hm : m = (z / 2) * (g - 1) + 1 := by dsimp [m] rw [hN] obtain ⟨k, rfl⟩ := heven have h1 : (k + k) * (g - 1) + 2 = 2 * (k * (g - 1)) + 2 := by ring have h2 : (k + k) / 2 = k := by omega rw [h1, h2] omega have hR : R ≤ t * (z / 2) := by dsimp [R] have hr' : ∀ i, r i ≤ z / 2 := by intro i have := hr i obtain ⟨k, rfl⟩ := heven omega simpa using sum_le_card_nsmul (univ : Finset (Fin t)) r (z / 2) (fun i _ => hr' i) have ht_le : t * (z / 2) ≤ (g - 1) * (z / 2) := Nat.mul_le_mul_right (z / 2) (Nat.le_pred_of_lt ht) have hcomm : (g - 1) * (z / 2) = (z / 2) * (g - 1) := mul_comm _ _ have hlt : R < m := by omega exact ⟨le_of_lt hlt, fun _ => hlt⟩ · have hN : N = (z + 1) * (g - 1) := if_neg heven have hodz : Odd z := Nat.not_even_iff_odd.mp heven obtain ⟨k, rfl⟩ := hodz have hm : m = ((2 * k + 1 + 1) / 2) * (g - 1) := by dsimp [m] rw [hN] have h1 : (2 * k + 1 + 1) * (g - 1) = 2 * ((k + 1) * (g - 1)) := by ring have h2 : (2 * k + 1 + 1) / 2 = k + 1 := by omega rw [h1, h2] omega have hR_le_t : R ≤ t * ((2 * k + 1 + 1) / 2) := by dsimp [R] simpa using sum_le_card_nsmul (univ : Finset (Fin t)) r ((2 * k + 1 + 1) / 2) (fun i _ => hr i) have ht_le : t * ((2 * k + 1 + 1) / 2) ≤ (g - 1) * ((2 * k + 1 + 1) / 2) := Nat.mul_le_mul_right ((2 * k + 1 + 1) / 2) (Nat.le_pred_of_lt ht) have hcomm : (g - 1) * ((2 * k + 1 + 1) / 2) = ((2 * k + 1 + 1) / 2) * (g - 1) := mul_comm _ _ have hR_le_m : R ≤ m := by omega refine ⟨hR_le_m, fun hQ => ?_⟩ have hj : ∃ j : Fin t, q j = 1 := by by_contra! h have h0 : ∀ i : Fin t, q i = 0 := by intro i have := hq i have := h i omega have hsum : Q = 0 := by dsimp [Q] simp [h0] rw [hsum] at hQ exact Nat.not_odd_zero hQ obtain ⟨j, hj1⟩ := hj have hrj : r j < (2 * k + 1 + 1) / 2 := by have := hr_q j hj1 omega have hR_lt_t : R < t * ((2 * k + 1 + 1) / 2) := by dsimp [R] have h1 : ∑ i : Fin t, r i < ∑ i : Fin t, ((2 * k + 1 + 1) / 2) := by apply sum_lt_sum · intro i _ exact hr i · exact ⟨j, mem_univ j, hrj⟩ have h2 : ∑ i : Fin t, ((2 * k + 1 + 1) / 2) = t * ((2 * k + 1 + 1) / 2) := by simp omega omega