circulant_mixed_graph_no_cycle_lt_g
For z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices contains no mixed cycle of length t < g.
Statement
theorem circulant_mixed_graph_no_cycle_lt_g (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) : let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) let m := N / 2 let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m let A : Fin N → Fin N → Prop := fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2) ∀ t < g, ¬mixed_graph_has_cycle E A t
- Source
- step towards mixed_cage_order_one_le
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- mixed_graph_has_cycleA mixed graph has a cycle of length t ≥ 3: distinct vertices x_0, ..., x_{t-1} such that each x_i is joined to x_{i+1} (indices mod t) by…
- circulant_cycle_val_sub_sum_dvdThe sum of cyclic differences of any function x : Fin t → Fin N is a multiple of N.
- circulant_cycle_not_all_edge_stepsAn injective sequence on Fin N cannot have every cyclic step equal to m when t ≥ 3 and N = 2m, because two steps of jump m return to the…
- circulant_cycle_remainder_boundFor 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…
- Used by 1
- mixed_cage_order_one_leFor z ≥ 1 and g ≥ 3, n(1, z, g) ≤ N(z, g), where N(z, g) = z(g − 1) + 2 for even z and (z + 1)(g − 1) for odd z: the circulant M(z, g) on…
The proof, explained
We argue by contradiction: suppose the circulant mixed graph contains a mixed cycle of length t < g on N = 2m vertices. Each step difference d_i decomposes under division by m into a quotient q_i ≤ 1 and a constrained remainder r_i. Because the cycle closes in ℤ/Nℤ, the total step sum is a multiple of N = 2m, forcing m to divide the remainder sum R = ∑ r_i. Since R ≤ m by `circulant_cycle_remainder_bound`, R can only be 0 (which would force all steps to be antipodal edges of weight m, impossible for a simple cycle of length t ≥ 3) or m (which forces the quotient sum Q to be odd, implying R < m, another contradiction).
If N = 2m, m > 0, and (a - b).val = m, then b ≡ a + m [MOD N]
From (a - b).val = m, the helper lemma `circulant_cycle_not_all_edge_steps_step` gives a ≡ b + m [MOD N]. Adding m to both sides gives b + 2m ≡ a + m [MOD N]. Since 2m = N ≡ 0 [MOD N], the left-hand side reduces to b modulo N, giving b ≡ a + m [MOD N].
uses
circulant_cycle_not_all_edge_steps_step,Nat.ModEq.add_right,Nat.ModEq,Nat.mod_self,Nat.zero_mod,Nat.ModEq.add,Nat.ModEq.refllemma circulant_mixed_graph_no_cycle_lt_g_val_sub_eq_m_of_rev {N m : ℕ} (hN : N = 2 * m) (hm : 0 < m) {a b : Fin N} (h : (a - b).val = m) : (b - a).val = m := by have hmN : m < N := by omega have h1 : a.val ≡ b.val + m [MOD N] := circulant_cycle_not_all_edge_steps_step hN hm h have h2 : b.val ≡ a.val + m [MOD N] := by have h1' : b.val + m + m ≡ a.val + m [MOD N] := (Nat.ModEq.add_right m h1).symm have h2' : b.val + m + m = b.val + N := by omega have h3' : b.val + N ≡ b.val [MOD N] := by have : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod] have := Nat.ModEq.add (Nat.ModEq.refl b.val) this omega rw [h2'] at h1' exact h3'.symm.trans h1'
If N = 2m, m > 0, and (a - b).val = m, then (b - a).val = m
By the formula for subtraction in `Fin N`, (b - a).val = (N - a.val + b.val) % N. Substituting b.val ≡ a.val + m [MOD N] gives N - a.val + b.val ≡ N + m ≡ m [MOD N]. Since m < N = 2m, the remainder modulo N is exactly m.
uses
Fin.val_sub,Nat.ModEq.add_left,Nat.ModEq,Nat.mod_self,Nat.zero_mod,Nat.ModEq.add_right,zero_add,Nat.mod_eq_of_ltrw [Fin.val_sub] have hmod : (N - a.val + b.val) ≡ m [MOD N] := by have : N - a.val + b.val ≡ N - a.val + (a.val + m) [MOD N] := Nat.ModEq.add_left (N - a.val) h2 have heq : N - a.val + (a.val + m) = N + m := by omega rw [heq] at this have hN0 : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod] have hm' : N + m ≡ 0 + m [MOD N] := Nat.ModEq.add_right m hN0 rw [zero_add] at hm' exact this.trans hm' rw [Nat.ModEq] at hmod rw [hmod] exact Nat.mod_eq_of_lt hmN
Any valid step difference d has quotient q = d / m ≤ 1 and remainder r = d % m ≤ (z + 1) / 2, with r ≤ z / 2 when q = 1, and d = m when r = 0
We perform case analysis on the three allowed regions for d: if d = m, then q = 1 and r = 0; if 1 ≤ d ≤ (z + 1) / 2, then d < m (since z < m), so q = 0 and r = d ≤ (z + 1) / 2; and if m + 1 ≤ d ≤ m + z / 2, writing d = (d - m) + m where d - m ≤ z / 2 < m yields q = 1 and r = d - m ≤ z / 2.
uses
Nat.div_self,Nat.mod_self,Nat.div_eq_of_lt,Nat.mod_eq_of_lt,Nat.add_div_right,Nat.add_mod_rightlemma circulant_mixed_graph_no_cycle_lt_g_div_mod_cases (z m d : ℕ) (hz : 1 ≤ z) (hzm : z < m) (hd : d = m ∨ (1 ≤ d ∧ d ≤ (z + 1) / 2) ∨ (m + 1 ≤ d ∧ d ≤ m + z / 2)) : d / m ≤ 1 ∧ d % m ≤ (z + 1) / 2 ∧ (d / m = 1 → d % m ≤ z / 2) ∧ (d % m = 0 → d = m) := by have hm : 0 < m := by omega rcases hd with rfl | ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [Nat.div_self hm, Nat.mod_self] omega · have hdm : d < m := by omega rw [Nat.div_eq_of_lt hdm, Nat.mod_eq_of_lt hdm] omega · have hdm_lt : d - m < m := by omega have heq : d = (d - m) + m := by omega rw [heq, Nat.add_div_right (d - m) hm, Nat.add_mod_right, Nat.div_eq_of_lt hdm_lt, Nat.mod_eq_of_lt hdm_lt] omega
Assume for contradiction that a mixed cycle of length t < g exists, and deduce that N is even
We assume a mixed cycle of length t < g exists, giving an injective cycle vertex sequence x with t ≥ 3. Since g ≥ 3, we have g - 1 ≥ 2. By definition of N, if z is even, N = z * (g - 1) + 2 is a sum of even terms, hence even; if z is odd, z + 1 is even, so N = (z + 1) * (g - 1) is also even.
uses
if_true,Even.add,even_two,if_false,Nat.not_even_iff_odd.mpintro N m E A t htg hcycle have ht3 : 3 ≤ t := hcycle.1 obtain ⟨x, hinj, hstep⟩ := hcycle.2 have hg1 : 2 ≤ g - 1 := by omega have hN_even : Even N := by by_cases hze : Even z · dsimp [N]; simp only [hze, if_true] exact Even.add (hze.mul_right (g - 1)) even_two · dsimp [N]; simp only [hze, if_false] have hodd : Odd z := Nat.not_even_iff_odd.mp hze exact (hodd.add_one).mul_right (g - 1)
2 * (z + 1) ≤ N, N = 2 * m, and z < m (hence m > 0)
Using g - 1 ≥ 2, we have z * (g - 1) + 2 ≥ 2 * z + 2 = 2 * (z + 1) when z is even, and (z + 1) * (g - 1) ≥ 2 * (z + 1) when z is odd, so 2 * (z + 1) ≤ N. Because N is even, N = 2 * (N / 2) = 2 * m. Dividing 2 * (z + 1) ≤ N by 2 yields z + 1 ≤ m, which gives z < m and 0 < m.
uses
if_true,Nat.mul_le_mul_left,if_false,Nat.div_two_mul_two_of_even,Nat.div_le_div_right,Nat.mul_div_righthave hN_ge : 2 * (z + 1) ≤ N := by by_cases hze : Even z · dsimp [N]; simp only [hze, if_true] have h2 : z * 2 ≤ z * (g - 1) := Nat.mul_le_mul_left z hg1 omega · dsimp [N]; simp only [hze, if_false] have h2 : (z + 1) * 2 ≤ (z + 1) * (g - 1) := Nat.mul_le_mul_left (z + 1) hg1 omega have hNm : N = 2 * m := by dsimp [m] have h := Nat.div_two_mul_two_of_even hN_even omega have hzm : z < m := by dsimp [m] have h1 : (2 * (z + 1)) / 2 ≤ N / 2 := Nat.div_le_div_right hN_ge rw [Nat.mul_div_right (z + 1) (by norm_num : 0 < 2)] at h1 omega have hm : 0 < m := by omega
Every step difference d i = (x (finRotate t i) - x i).val satisfies d i = m ∨ (1 ≤ d i ∧ d i ≤ (z + 1) / 2) ∨ (m + 1 ≤ d i ∧ d i ≤ m + z / 2)
At each step i, the transition is either an undirected edge in E or a directed arc in A. If it is an undirected edge in E, then either (x (i + 1) - x i).val = m directly, or (x i - x (i + 1)).val = m, in which case the reversed difference (x (i + 1) - x i).val = m by Lemma 1. If it is a directed arc in A, the condition holds by the definition of A.
uses
SimpleGraph.fromRel_adj,circulant_mixed_graph_no_cycle_lt_g_val_sub_eq_m_of_revlet d : Fin t → ℕ := fun i => (x (finRotate t i) - x i).val have hd_cases : ∀ i, d i = m ∨ (1 ≤ d i ∧ d i ≤ (z + 1) / 2) ∨ (m + 1 ≤ d i ∧ d i ≤ m + z / 2) := by intro i rcases hstep i with hE | hA · rw [SimpleGraph.fromRel_adj] at hE rcases hE.2 with h1 | h2 · left; exact h1 · left; exact circulant_mixed_graph_no_cycle_lt_g_val_sub_eq_m_of_rev hNm hm h2 · right; exact hA
For each step i, the quotient q i = d i / m and remainder r i = d i % m satisfy q i ≤ 1, r i ≤ (z + 1) / 2, (q i = 1 → r i ≤ z / 2), and (r i = 0 → d i = m)
Applying Lemma 2 (`circulant_mixed_graph_no_cycle_lt_g_div_mod_cases`) with 1 ≤ z < m and the step difference cases from the previous step yields all four conditions simultaneously for each i.
uses
circulant_mixed_graph_no_cycle_lt_g_div_mod_caseslet q : Fin t → ℕ := fun i => d i / m let r : Fin t → ℕ := fun i => d i % m have hprops : ∀ i, q i ≤ 1 ∧ r i ≤ (z + 1) / 2 ∧ (q i = 1 → r i ≤ z / 2) ∧ (r i = 0 → d i = m) := by intro i exact circulant_mixed_graph_no_cycle_lt_g_div_mod_cases z m (d i) hz hzm (hd_cases i) have hq : ∀ i, q i ≤ 1 := fun i => (hprops i).1 have hr : ∀ i, r i ≤ (z + 1) / 2 := fun i => (hprops i).2.1 have hr_q : ∀ i, q i = 1 → r i ≤ z / 2 := fun i => (hprops i).2.2.1 have hr_zero : ∀ i, r i = 0 → d i = m := fun i => (hprops i).2.2.2
The total remainder R = ∑ i, r i satisfies R ≤ m, and if Q = ∑ i, q i is odd then R < m
We apply the knowledge-base theorem `circulant_cycle_remainder_bound`, which establishes these bounds for any cycle length t < g given the individual quotient and remainder constraints.
uses
circulant_cycle_remainder_boundhave hbound := circulant_cycle_remainder_bound z g t hz hg htg q r hq hr hr_q have hR_le : (∑ i, r i) ≤ m := hbound.1 have hOdd_Q : Odd (∑ i, q i) → (∑ i, r i) < m := hbound.2
The sum of step differences ∑ i, d i equals (∑ i, q i) * m + ∑ i, r i
For each step i, the Euclidean division identity gives d i = q i * m + r i. Summing this equation over all i ∈ Fin t and distributing the sum over addition and multiplication gives the total sum decomposition.
uses
mul_comm,Nat.div_add_mod,Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_mulhave hd_eq : ∀ i, d i = q i * m + r i := by intro i dsimp [q, r] rw [mul_comm, Nat.div_add_mod] have hsum_d : (∑ i, d i) = (∑ i, q i) * m + (∑ i, r i) := by have : (∑ i, d i) = ∑ i, (q i * m + r i) := by apply Finset.sum_congr rfl intro i _ exact hd_eq i rw [this, Finset.sum_add_distrib, ← Finset.sum_mul]
m divides the sum of remainders ∑ i, r i
The sum of step differences along any cycle is a multiple of N = 2 * m by `circulant_cycle_val_sub_sum_dvd`. Since m divides 2 * m, m divides ∑ i, d i = (∑ i, q i) * m + ∑ i, r i. As m also divides (∑ i, q i) * m, it must divide the remainder sum ∑ i, r i.
uses
circulant_cycle_val_sub_sum_dvd,dvd_mul_left,dvd_trans,Nat.dvd_add_righthave hdvd : N ∣ ∑ i, d i := circulant_cycle_val_sub_sum_dvd x rw [hNm, hsum_d] at hdvd have h_m_dvd_R : m ∣ (∑ i, r i) := by have h1 : m ∣ 2 * m := dvd_mul_left m 2 have h2 : m ∣ (∑ i, q i) * m + (∑ i, r i) := dvd_trans h1 hdvd have h3 : m ∣ (∑ i, q i) * m := dvd_mul_left m (∑ i, q i) exact (Nat.dvd_add_right h3).mp h2
Either ∑ i, r i = 0 or ∑ i, r i = m
Since m divides ∑ i, r i, we can write the sum as k * m for some natural number k. If k = 0, the sum is 0; if k = 1, the sum is m. If k ≥ 2, then ∑ i, r i ≥ 2 * m > m, contradicting the upper bound ∑ i, r i ≤ m.
uses
Nat.mul_le_mul_lefthave hR_cases : (∑ i, r i) = 0 ∨ (∑ i, r i) = m := by obtain ⟨k, hk⟩ := h_m_dvd_R cases k with | zero => left; omega | succ k => cases k with | zero => right; omega | succ k => exfalso have h1 : m * 2 ≤ m * (k + 1 + 1) := Nat.mul_le_mul_left m (by omega) have h2 : m * 2 ≤ ∑ i, r i := by omega have h3 : m * 2 ≤ m := h2.trans hR_le omega rcases hR_cases with hR0 | hRm
The case ∑ i, r i = 0 is impossible
If the sum of non-negative remainders is 0, every individual remainder r i must be 0, which implies every step difference d i = m. But by `circulant_cycle_not_all_edge_steps`, a simple cycle of length t ≥ 3 in a circulant graph on N = 2m vertices cannot have every step equal to m (as alternating antipodal steps would only bounce between two vertices).
uses
Finset.single_le_sum,Nat.zero_le,Finset.mem_univ,circulant_cycle_not_all_edge_steps· have hall_m : ∀ i, d i = m := by intro i have hri : r i = 0 := by have := Finset.single_le_sum (fun j _ => Nat.zero_le (r j)) (Finset.mem_univ i) omega exact hr_zero i hri exact circulant_cycle_not_all_edge_steps ht3 hNm hm x hinj hall_m
The case ∑ i, r i = m is impossible, completing the contradiction
If ∑ i, r i = m, substituting into 2 * m ∣ (∑ i, q i) * m + m gives 2 * m ∣ ((∑ i, q i) + 1) * m. Canceling m > 0 gives 2 ∣ (∑ i, q i) + 1, so ∑ i, q i is odd. But by `circulant_cycle_remainder_bound`, an odd quotient sum forces ∑ i, r i < m, directly contradicting ∑ i, r i = m.
uses
Nat.mul_dvd_mul_iff_right,Nat.odd_iff.mpr· rw [hRm] at hdvd have heq : (∑ i, q i) * m + m = ((∑ i, q i) + 1) * m := by ring rw [heq] at hdvd have hdvd2 : 2 ∣ (∑ i, q i) + 1 := (Nat.mul_dvd_mul_iff_right hm).mp hdvd obtain ⟨k, hk⟩ := hdvd2 have hodd : Odd (∑ i, q i) := Nat.odd_iff.mpr (by omega) have hlt : (∑ i, r i) < m := hOdd_Q hodd omega
circulant_cycle_not_all_edge_steps_step- If (b - a).val = m in ℤ/Nℤ with N = 2m and m > 0, then b ≡ a + m (mod N)
Nat.ModEq.add_right- If a ≡ b (mod n), then a + c ≡ b + c (mod n)
Nat.ModEq- Definition of modular equivalence: a ≡ b [MOD n] means a % n = b % n
Nat.mod_self- n % n = 0 for any natural number n
Nat.zero_mod- 0 % b = 0 for any natural number b
Nat.ModEq.add- If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n)
Nat.ModEq.refl- a ≡ a (mod n)
Fin.val_sub- The representative of (a - b) in Fin n has value (n - b.val + a.val) % n
Nat.ModEq.add_left- If a ≡ b (mod n), then c + a ≡ c + b (mod n)
zero_add- 0 + a = a for any additive element a
Nat.mod_eq_of_lt- If a < b, then a % b = a
Nat.div_self- If n > 0, then n / n = 1
Nat.div_eq_of_lt- If a < b, then a / b = 0
Nat.add_div_right- If z > 0, then (x + z) / z = x / z + 1
Nat.add_mod_right- (x + z) % z = x % z for any natural numbers x, z
if_true- (if True then t else e) = t
Even.add- If a and b are even, then a + b is even
even_two- 2 is an even number
if_false- (if False then t else e) = e
Nat.not_even_iff_odd.mp- If a natural number is not even, it is odd
Nat.mul_le_mul_left- If n ≤ m, then k * n ≤ k * m
Nat.div_two_mul_two_of_even- If n is even, then (n / 2) * 2 = n
Nat.div_le_div_right- If a ≤ b, then a / c ≤ b / c
Nat.mul_div_right- If m > 0, then m * n / m = n
SimpleGraph.fromRel_adj- In a graph built from a relation r, v is adjacent to w iff v ≠ w and (r v w ∨ r w v)
circulant_mixed_graph_no_cycle_lt_g_val_sub_eq_m_of_rev- If N = 2m, m > 0, and (a - b).val = m in Fin N, then (b - a).val = m
circulant_mixed_graph_no_cycle_lt_g_div_mod_cases- For a valid step difference d in M(z, g), d / m ≤ 1, d % m ≤ (z + 1) / 2, with d % m ≤ z / 2 when d / m = 1, and d = m when d % m = 0
circulant_cycle_remainder_bound- For t < g and quotient/remainder sequences satisfying the step constraints, the remainder sum R satisfies R ≤ m, and R < m if the quotient sum Q is odd
mul_comm- Multiplication is commutative: a * b = b * a
Nat.div_add_mod- Division algorithm equality: n * (m / n) + m % n = m
Finset.sum_congr- Two sums over the same finite set are equal if their summands agree at every element
Finset.sum_add_distrib- Sum of a sum of functions distributes: ∑ (f + g) = ∑ f + ∑ g
Finset.sum_mul- Factoring out a scalar from a sum: (∑ f i) * a = ∑ (f i * a)
circulant_cycle_val_sub_sum_dvd- The sum of consecutive cyclic differences around a cycle is a multiple of the ring size N
dvd_mul_left- a divides b * a
dvd_trans- If a divides b and b divides c, then a divides c
Nat.dvd_add_right- If a divides b, then a divides b + c iff a divides c
Finset.single_le_sum- A non-negative summand is bounded above by the total sum over a finite set
Nat.zero_le- 0 ≤ n for every natural number n
Finset.mem_univ- Every element of a Fintype belongs to the universal set Finset.univ
circulant_cycle_not_all_edge_steps- A simple cycle of length t ≥ 3 in a circulant graph on N = 2m vertices cannot have every step difference equal to m
Nat.mul_dvd_mul_iff_right- If c > 0, then a * c divides b * c iff a divides b
Nat.odd_iff.mpr- If n % 2 = 1, then n is odd
- Linear arithmetic over ℕ is repeatedly discharged by the `omega` tactic throughout the lemmas and the main theorem.
- Vertices are elements of `Fin N`, so subtraction `y - x` denotes cyclic difference modulo N whose value lies in {0, ..., N - 1}.
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.
lemma circulant_mixed_graph_no_cycle_lt_g_val_sub_eq_m_of_rev {N m : ℕ} (hN : N = 2 * m) (hm : 0 < m) {a b : Fin N} (h : (a - b).val = m) : (b - a).val = m := by have hmN : m < N := by omega have h1 : a.val ≡ b.val + m [MOD N] := circulant_cycle_not_all_edge_steps_step hN hm h have h2 : b.val ≡ a.val + m [MOD N] := by have h1' : b.val + m + m ≡ a.val + m [MOD N] := (Nat.ModEq.add_right m h1).symm have h2' : b.val + m + m = b.val + N := by omega have h3' : b.val + N ≡ b.val [MOD N] := by have : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod] have := Nat.ModEq.add (Nat.ModEq.refl b.val) this omega rw [h2'] at h1' exact h3'.symm.trans h1' rw [Fin.val_sub] have hmod : (N - a.val + b.val) ≡ m [MOD N] := by have : N - a.val + b.val ≡ N - a.val + (a.val + m) [MOD N] := Nat.ModEq.add_left (N - a.val) h2 have heq : N - a.val + (a.val + m) = N + m := by omega rw [heq] at this have hN0 : N ≡ 0 [MOD N] := by rw [Nat.ModEq, Nat.mod_self, Nat.zero_mod] have hm' : N + m ≡ 0 + m [MOD N] := Nat.ModEq.add_right m hN0 rw [zero_add] at hm' exact this.trans hm' rw [Nat.ModEq] at hmod rw [hmod] exact Nat.mod_eq_of_lt hmNlemma circulant_mixed_graph_no_cycle_lt_g_div_mod_cases (z m d : ℕ) (hz : 1 ≤ z) (hzm : z < m) (hd : d = m ∨ (1 ≤ d ∧ d ≤ (z + 1) / 2) ∨ (m + 1 ≤ d ∧ d ≤ m + z / 2)) : d / m ≤ 1 ∧ d % m ≤ (z + 1) / 2 ∧ (d / m = 1 → d % m ≤ z / 2) ∧ (d % m = 0 → d = m) := by have hm : 0 < m := by omega rcases hd with rfl | ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [Nat.div_self hm, Nat.mod_self] omega · have hdm : d < m := by omega rw [Nat.div_eq_of_lt hdm, Nat.mod_eq_of_lt hdm] omega · have hdm_lt : d - m < m := by omega have heq : d = (d - m) + m := by omega rw [heq, Nat.add_div_right (d - m) hm, Nat.add_mod_right, Nat.div_eq_of_lt hdm_lt, Nat.mod_eq_of_lt hdm_lt] omega/-- The circulant mixed graph M(z, g) has no mixed cycle of length shorter than g. -/theorem circulant_mixed_graph_no_cycle_lt_g (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) : let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) let m := N / 2 let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m let A : Fin N → Fin N → Prop := fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2) ∀ t < g, ¬mixed_graph_has_cycle E A t := by intro N m E A t htg hcycle have ht3 : 3 ≤ t := hcycle.1 obtain ⟨x, hinj, hstep⟩ := hcycle.2 have hg1 : 2 ≤ g - 1 := by omega have hN_even : Even N := by by_cases hze : Even z · dsimp [N]; simp only [hze, if_true] exact Even.add (hze.mul_right (g - 1)) even_two · dsimp [N]; simp only [hze, if_false] have hodd : Odd z := Nat.not_even_iff_odd.mp hze exact (hodd.add_one).mul_right (g - 1) have hN_ge : 2 * (z + 1) ≤ N := by by_cases hze : Even z · dsimp [N]; simp only [hze, if_true] have h2 : z * 2 ≤ z * (g - 1) := Nat.mul_le_mul_left z hg1 omega · dsimp [N]; simp only [hze, if_false] have h2 : (z + 1) * 2 ≤ (z + 1) * (g - 1) := Nat.mul_le_mul_left (z + 1) hg1 omega have hNm : N = 2 * m := by dsimp [m] have h := Nat.div_two_mul_two_of_even hN_even omega have hzm : z < m := by dsimp [m] have h1 : (2 * (z + 1)) / 2 ≤ N / 2 := Nat.div_le_div_right hN_ge rw [Nat.mul_div_right (z + 1) (by norm_num : 0 < 2)] at h1 omega have hm : 0 < m := by omega let d : Fin t → ℕ := fun i => (x (finRotate t i) - x i).val have hd_cases : ∀ i, d i = m ∨ (1 ≤ d i ∧ d i ≤ (z + 1) / 2) ∨ (m + 1 ≤ d i ∧ d i ≤ m + z / 2) := by intro i rcases hstep i with hE | hA · rw [SimpleGraph.fromRel_adj] at hE rcases hE.2 with h1 | h2 · left; exact h1 · left; exact circulant_mixed_graph_no_cycle_lt_g_val_sub_eq_m_of_rev hNm hm h2 · right; exact hA let q : Fin t → ℕ := fun i => d i / m let r : Fin t → ℕ := fun i => d i % m have hprops : ∀ i, q i ≤ 1 ∧ r i ≤ (z + 1) / 2 ∧ (q i = 1 → r i ≤ z / 2) ∧ (r i = 0 → d i = m) := by intro i exact circulant_mixed_graph_no_cycle_lt_g_div_mod_cases z m (d i) hz hzm (hd_cases i) have hq : ∀ i, q i ≤ 1 := fun i => (hprops i).1 have hr : ∀ i, r i ≤ (z + 1) / 2 := fun i => (hprops i).2.1 have hr_q : ∀ i, q i = 1 → r i ≤ z / 2 := fun i => (hprops i).2.2.1 have hr_zero : ∀ i, r i = 0 → d i = m := fun i => (hprops i).2.2.2 have hbound := circulant_cycle_remainder_bound z g t hz hg htg q r hq hr hr_q have hR_le : (∑ i, r i) ≤ m := hbound.1 have hOdd_Q : Odd (∑ i, q i) → (∑ i, r i) < m := hbound.2 have hd_eq : ∀ i, d i = q i * m + r i := by intro i dsimp [q, r] rw [mul_comm, Nat.div_add_mod] have hsum_d : (∑ i, d i) = (∑ i, q i) * m + (∑ i, r i) := by have : (∑ i, d i) = ∑ i, (q i * m + r i) := by apply Finset.sum_congr rfl intro i _ exact hd_eq i rw [this, Finset.sum_add_distrib, ← Finset.sum_mul] have hdvd : N ∣ ∑ i, d i := circulant_cycle_val_sub_sum_dvd x rw [hNm, hsum_d] at hdvd have h_m_dvd_R : m ∣ (∑ i, r i) := by have h1 : m ∣ 2 * m := dvd_mul_left m 2 have h2 : m ∣ (∑ i, q i) * m + (∑ i, r i) := dvd_trans h1 hdvd have h3 : m ∣ (∑ i, q i) * m := dvd_mul_left m (∑ i, q i) exact (Nat.dvd_add_right h3).mp h2 have hR_cases : (∑ i, r i) = 0 ∨ (∑ i, r i) = m := by obtain ⟨k, hk⟩ := h_m_dvd_R cases k with | zero => left; omega | succ k => cases k with | zero => right; omega | succ k => exfalso have h1 : m * 2 ≤ m * (k + 1 + 1) := Nat.mul_le_mul_left m (by omega) have h2 : m * 2 ≤ ∑ i, r i := by omega have h3 : m * 2 ≤ m := h2.trans hR_le omega rcases hR_cases with hR0 | hRm · have hall_m : ∀ i, d i = m := by intro i have hri : r i = 0 := by have := Finset.single_le_sum (fun j _ => Nat.zero_le (r j)) (Finset.mem_univ i) omega exact hr_zero i hri exact circulant_cycle_not_all_edge_steps ht3 hNm hm x hinj hall_m · rw [hRm] at hdvd have heq : (∑ i, q i) * m + m = ((∑ i, q i) + 1) * m := by ring rw [heq] at hdvd have hdvd2 : 2 ∣ (∑ i, q i) + 1 := (Nat.mul_dvd_mul_iff_right hm).mp hdvd obtain ⟨k, hk⟩ := hdvd2 have hodd : Odd (∑ i, q i) := Nat.odd_iff.mpr (by omega) have hlt : (∑ i, r i) < m := hOdd_Q hodd omega