AFTD Auto-Formalizing Theoretical Domains

circulant_mixed_graph_no_cycle_lt_g

theoremverified

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).

  1. 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].

    lines 1–13

    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.refl

    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'
  2. 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.

    lines 14–25

    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_lt

      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 hmN
  3. 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.

    lines 27–41

    uses Nat.div_self, Nat.mod_self, Nat.div_eq_of_lt, Nat.mod_eq_of_lt, Nat.add_div_right, Nat.add_mod_right

    lemma 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
  4. 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.

    lines 52–62

    uses if_true, Even.add, even_two, if_false, Nat.not_even_iff_odd.mp

      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)
  5. 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.

    lines 63–80

    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_right

      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
  6. 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.

    lines 81–89

    uses SimpleGraph.fromRel_adj, circulant_mixed_graph_no_cycle_lt_g_val_sub_eq_m_of_rev

      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
  7. 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.

    lines 90–98

    uses circulant_mixed_graph_no_cycle_lt_g_div_mod_cases

      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
  8. 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.

    lines 99–101

    uses circulant_cycle_remainder_bound

      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
  9. 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.

    lines 102–111

    uses mul_comm, Nat.div_add_mod, Finset.sum_congr, Finset.sum_add_distrib, Finset.sum_mul

      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]
  10. 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.

    lines 112–118

    uses circulant_cycle_val_sub_sum_dvd, dvd_mul_left, dvd_trans, Nat.dvd_add_right

      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
  11. 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.

    lines 119–132

    uses Nat.mul_le_mul_left

      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
  12. 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).

    lines 133–139

    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
  13. 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.

    lines 140–147

    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

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

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
See it in the graphDiscuss this resultChallenge it