AFTD Auto-Formalizing Theoretical Domains

circulant_cycle_remainder_bound

theoremverified

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

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.

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

    lines 10–11

      open Finset in
      intro N m Q R
  2. 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.

    line 12

      by_cases heven : Even z
  3. When 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.

    lines 13–21

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

    lines 22–29

    uses sum_le_card_nsmul

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

    lines 30–34

    uses Nat.mul_le_mul_right, Nat.le_pred_of_lt, mul_comm, le_of_lt

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

    lines 35–44

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

    lines 45–52

    uses sum_le_card_nsmul, Nat.mul_le_mul_right, Nat.le_pred_of_lt, mul_comm

        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 => ?_⟩
  8. 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.

    lines 53–65

    uses Nat.not_odd_zero

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

    lines 66–68

        have hrj : r j < (2 * k + 1 + 1) / 2 := by
          have := hr_q j hj1
          omega
  10. 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`).

    lines 69–78

    uses sum_lt_sum, mem_univ

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

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

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