latin_square_exists_principal_isotope_avoiding_self
The case L' = L: every Latin square of order n > 1 is avoided by one of its own principal isotopes (shift the rows cyclically).
Statement
theorem latin_square_exists_principal_isotope_avoiding_self (n : ℕ) (hn : 1 < n)
(L : Fin n → Fin n → Fin n) (hL : latin_square_is L) :
∃ π ρ : Equiv.Perm (Fin n), ∀ i j, L (π i) (ρ j) ≠ L i j- Formalizes
- arXiv:2610.20008 (Avoiding a partial Latin square with an isotope of a given Latin square), remark after Conjecture 4 (the conjecture is trivially true when L' = L, by a cyclic permutation of the rows).
- Verified
- 17 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- latin_square_isA Latin square of order n: an n × n array with entries in {1, ..., n} whose rows and columns are permutations of {1, ..., n}.
The proof, explained
The proof shows that any Latin square of order n > 1 avoids its principal isotope obtained by shifting rows cyclically by 1 and leaving columns fixed. If this isotope agreed with the original Latin square at some cell (i, j), column injectivity would force the cyclic shift to fix row i, implying i + 1 = i and therefore 1 = 0 in Fin n. Because n > 1, 1 is not congruent to 0 modulo n, producing a contradiction.
It suffices to show that shifting rows cyclically by finRotate n while keeping columns fixed produces no matching entry with L.
We choose the candidate row permutation π to be the cyclic shift finRotate n and the column permutation ρ to be the identity permutation 1. To show they avoid L everywhere, we assume for contradiction that there exist indices i and j such that L (π i) (ρ j) = L i j, which simplifies to L (finRotate n i) j = L i j.
refine ⟨finRotate n, 1, fun i j h => ?_⟩
The cyclic shift must fix the row index i, that is, (finRotate n) i = i.
By definition of a Latin square, every column of L is an injective function (given by hL.2 j). Applying this injectivity to the assumption L (finRotate n i) j = L i j yields (finRotate n) i = i.
have := hL.2 j hThe dimension n can be represented as a successor m + 1.
Since n > 1, linear integer arithmetic establishes n = (n - 1) + 1, so we substitute n with m + 1 where m = n - 1.
obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩
In Fin (m + 1), 1 = 0.
Rewriting the cyclic rotation using finRotate_apply transforms the equality (finRotate (m + 1)) i = i into i + 1 = i. Subtracting i from both sides in Fin (m + 1) simplifies this to 1 = 0.
uses
finRotate_applyrw [finRotate_apply] at this have : (1 : Fin (m + 1)) = 0 := by simpa using this
False (contradiction).
Applying congrArg with Fin.val to the identity 1 = 0 yields that 1 and 0 have the same numerical value in ℕ modulo n. However, since 1 < n, Nat.mod_eq_of_lt shows that (1 : Fin (m + 1)).val = 1 while (0 : Fin (m + 1)).val = 0, so they are not equal; absurd derives False from this contradiction.
uses
absurd,congrArg,Fin.val,Nat.mod_eq_of_ltexact absurd (congrArg Fin.val this) (by simp [Nat.mod_eq_of_lt hn])
finRotate_apply- The cyclic permutation of Fin n shifts each index by 1 modulo n, sending i to i + 1.
congrArg- If two arguments are equal, applying any function to them yields equal results: if a₁ = a₂, then f a₁ = f a₂.
Fin.val- The canonical embedding of an element of Fin n as a natural number strictly less than n.
Nat.mod_eq_of_lt- For natural numbers a and b, if a < b then the remainder a % b is simply a.
absurd- From a proposition and its negation, one can deduce any conclusion (ex falso quodlibet).
- In Lean, arithmetic operations and numerals on finite types Fin n are defined when the modulus is syntactically a successor m + 1. Rewriting n = m + 1 (line 6) is a formal detail needed to perform algebraic simplifications on Fin n.
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.
theorem latin_square_exists_principal_isotope_avoiding_self (n : ℕ) (hn : 1 < n) (L : Fin n → Fin n → Fin n) (hL : latin_square_is L) : ∃ π ρ : Equiv.Perm (Fin n), ∀ i j, L (π i) (ρ j) ≠ L i j := by refine ⟨finRotate n, 1, fun i j h => ?_⟩ have := hL.2 j h obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩ rw [finRotate_apply] at this have : (1 : Fin (m + 1)) = 0 := by simpa using this exact absurd (congrArg Fin.val this) (by simp [Nat.mod_eq_of_lt hn])