AFTD Auto-Formalizing Theoretical Domains

latin_square_exists_principal_isotope_avoiding_self

theoremverifiedformalization

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.

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

    line 4

      refine ⟨finRotate n, 1, fun i j h => ?_⟩
  2. 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.

    line 5

      have := hL.2 j h
  3. The 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.

    line 6

      obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩
  4. 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.

    lines 7–8

    uses finRotate_apply

      rw [finRotate_apply] at this
      have : (1 : Fin (m + 1)) = 0 := by simpa using this
  5. 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.

    line 9

    uses absurd, congrArg, Fin.val, Nat.mod_eq_of_lt

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

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

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