AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_distinct_neighbors

theoremverified

For n ≥ 6 and any x : Fin n, the cyclic neighbors (x - 1) % n and (x + 1) % n are distinct.

Statement

theorem cyclic_cubic_distinct_neighbors (n : ℕ) (hn : 6 ≤ n) (x : Fin n) : (⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) ≠ ⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩
Source
step towards cyclic_cubic_parity_repr_eval_zero
Verified
01 Nov 2026
Axioms
Quot.soundpropext
Used by 1
  • cyclic_cubic_parity_repr_eval_zeroFor n ≥ 6, any affine evaluation (∑_{j ∈ y} c_j = b) on all parities y ∈ S of a parity representation S of cyclic_cubic_syndrome n forces…

The proof, explained

To show that the cyclic neighbors (x - 1) % n and (x + 1) % n are distinct for n ≥ 6, we argue by contradiction and suppose they are equal. Passing to their underlying natural values, we case-split on whether x = 0 or x > 0. When x = 0, the equation reduces to n - 1 = 1, contradicting n ≥ 6. When x = x₀ + 1, the equation simplifies to x₀ = (x₀ + 2) % n, which is impossible whether x₀ + 2 < n (giving x₀ = x₀ + 2) or x₀ + 2 = n (forcing x₀ = 0 and thus n = 2).

  1. Assume for contradiction that the two cyclic neighbors are equal; then their underlying natural values modulo n are equal: (x + n - 1) % n = (x + 1) % n.

    Because n ≥ 6, n > 0, so Nat.mod_lt ensures that the modulo operations produce valid elements of Fin n. We introduce the equality hypothesis h for contradiction. By Fin.mk.inj, equality of the Fin n terms implies equality of their underlying values: (x + n - 1) % n = (x + 1) % n.

    lines 2–6

    uses Nat.mod_lt, Fin.mk.inj

    theorem cyclic_cubic_distinct_neighbors (n : ℕ) (hn : 6 ≤ n) (x : Fin n) : (⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) ≠ ⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ := by
      intro h
      have hval := Fin.mk.inj h
      rcases x with ⟨x, hx⟩
      dsimp at hval
  2. The case x = 0 is impossible.

    When x = 0, the left neighbor simplifies via Nat.zero_add to (n - 1) % n, which equals n - 1 by Nat.mod_eq_of_lt since n - 1 < n. The right neighbor (0 + 1) % n equals 1 by Nat.mod_eq_of_lt since 1 < n. Equating the two yields n - 1 = 1, so n = 2, which contradicts n ≥ 6. Linear arithmetic (omega) closes this case.

    lines 7–12

    uses Nat.zero_add, Nat.mod_eq_of_lt

      rcases x with _ | x
      · have h1 : (0 + n - 1) % n = n - 1 := by
          rw [Nat.zero_add]
          exact Nat.mod_eq_of_lt (by omega)
        have h2 : (0 + 1) % n = 1 := Nat.mod_eq_of_lt (by omega)
        omega
  3. When the element is non-zero (represented as x + 1 with x + 1 < n), the assumed equality reduces to x = (x + 2) % n.

    When the value is x + 1, the left neighbor is (x + 1 + n - 1) % n = (x + n) % n. By Nat.add_mod_right, (x + n) % n = x % n, and since x < x + 1 < n, Nat.mod_eq_of_lt reduces this to x. Substituting this into the assumption simplifies the equation to x = (x + 1 + 1) % n.

    lines 13–17

    uses Nat.add_mod_right, Nat.mod_eq_of_lt

      · have h1 : (x + 1 + n - 1) % n = x % n := by
          have : x + 1 + n - 1 = x + n := by omega
          rw [this, Nat.add_mod_right]
        have h2 : x % n = x := Nat.mod_eq_of_lt (by omega)
        rw [h1, h2] at hval
  4. The subcase x + 2 < n is impossible.

    If x + 2 < n, then Nat.mod_eq_of_lt gives (x + 2) % n = x + 2. The equality then becomes x = x + 2, which is impossible in natural numbers (closed by omega).

    lines 18–20

    uses Nat.mod_eq_of_lt

        by_cases hlt : x + 1 + 1 < n
        · have h3 : (x + 1 + 1) % n = x + 2 := Nat.mod_eq_of_lt hlt
          omega
  5. The subcase x + 2 ≥ n is impossible, concluding the proof.

    Since x + 1 < n, the condition ¬(x + 2 < n) forces x + 2 = n. Then (x + 2) % n = n % n = 0 by Nat.mod_self. The equality x = (x + 2) % n therefore forces x = 0, which gives n = x + 2 = 2, contradicting n ≥ 6. Linear arithmetic (omega) derives False and finishes the proof.

    lines 21–23

    uses Nat.mod_self

        · have h3 : x + 1 + 1 = n := by omega
          have h4 : (x + 1 + 1) % n = 0 := by rw [h3, Nat.mod_self]
          omega
Nat.mod_lt
For any natural numbers x and y with y > 0, the remainder x % y is strictly less than y.
Fin.mk.inj
If two elements of Fin n are equal, their underlying natural number values are equal.
Nat.zero_add
Adding zero on the left preserves any natural number: 0 + n = n.
Nat.mod_eq_of_lt
If a < b for natural numbers a and b, then a % b = a.
Nat.add_mod_right
Adding the modulus z to x does not change the remainder modulo z: (x + z) % z = x % z.
Nat.mod_self
Any natural number modulo itself is zero: n % n = 0.

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 n ≥ 6 and any x : Fin n, the cyclic neighbors (x - 1) % n and (x + 1) % n are distinct. -/theorem cyclic_cubic_distinct_neighbors (n : ℕ) (hn : 6 ≤ n) (x : Fin n) : (⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) ≠ ⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ := by  intro h  have hval := Fin.mk.inj h  rcases x with ⟨x, hx⟩  dsimp at hval  rcases x with _ | x  · have h1 : (0 + n - 1) % n = n - 1 := by      rw [Nat.zero_add]      exact Nat.mod_eq_of_lt (by omega)    have h2 : (0 + 1) % n = 1 := Nat.mod_eq_of_lt (by omega)    omega  · have h1 : (x + 1 + n - 1) % n = x % n := by      have : x + 1 + n - 1 = x + n := by omega      rw [this, Nat.add_mod_right]    have h2 : x % n = x := Nat.mod_eq_of_lt (by omega)    rw [h1, h2] at hval    by_cases hlt : x + 1 + 1 < n    · have h3 : (x + 1 + 1) % n = x + 2 := Nat.mod_eq_of_lt hlt      omega    · have h3 : x + 1 + 1 = n := by omega      have h4 : (x + 1 + 1) % n = 0 := by rw [h3, Nat.mod_self]      omega
See it in the graphDiscuss this resultChallenge it