cyclic_cubic_distinct_neighbors
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).
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.
uses
Nat.mod_lt,Fin.mk.injtheorem 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
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.
uses
Nat.zero_add,Nat.mod_eq_of_ltrcases 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
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.
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
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).
uses
Nat.mod_eq_of_ltby_cases hlt : x + 1 + 1 < n · have h3 : (x + 1 + 1) % n = x + 2 := Nat.mod_eq_of_lt hlt omega
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.
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.
- In Lean, the cyclic predecessor is written as `(x.val + n - 1) % n` rather than `(x.val - 1) % n` to avoid truncation in natural number subtraction when `x.val = 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
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 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