AFTD Auto-Formalizing Theoretical Domains

latin_top_row_availability_eq_one_iff

theoremverified

The availability entry equals one exactly when the prospective positive symbol does not already occur in that column.

Statement

theorem latin_top_row_availability_eq_one_iff (d : YoungDiagram) (T : d.cells → ℕ)
    (w : ℕ) (i j : Fin w) :
    latin_top_row_availability d T w i j = 1 ↔
      i.val + 1 ∉ latin_column_symbols d T j.val
Source
Helper for the open enumeration problem in https://arxiv.org/html/2610.29291v1, Conjecture 6.3, using the availability-permanent identity of Lemma 5.4. Exact computational route: experiments 4100, 4103 and 4106.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • latin_top_row_availabilityThe zero-one matrix whose row index is a prospective symbol minus one and whose column index is a column: an entry is one precisely when…
  • latin_column_symbolsThe finite set of symbols appearing in column j of a fixed filling T of a Young diagram d.
  • mem_latin_column_symbolsA symbol belongs to a column-symbol set exactly when a cell of that column has that value.
Used by 1

The proof, explained

The equivalence is established directly by definition unfolding and quantifier duality. The availability entry at (i, j) is defined to be 1 if and only if no cell in column j carries the symbol i + 1. By mem_latin_column_symbols, this universal condition is precisely the negation of i + 1 belonging to the set of symbols in column j.

  1. The availability entry at (i, j) equals 1 if and only if symbol i + 1 does not belong to column j.

    By definition of latin_top_row_availability, the matrix entry at (i, j) is defined by an if-then-else: it equals 1 if and only if every cell in column j has a label distinct from i + 1 (and 0 otherwise). On the right-hand side, mem_latin_column_symbols states that i + 1 belongs to the column symbols of j if and only if some cell in column j has label i + 1. Its negation, by standard predicate logic, is equivalent to saying that every cell in column j has label different from i + 1. The simplifier unfolds these definitions and closes the equivalence.

    line 5

    uses latin_top_row_availability, mem_latin_column_symbols

      simp [latin_top_row_availability, mem_latin_column_symbols]
latin_top_row_availability
The w × w matrix whose (i, j)-th entry is 1 if every cell in column j has a label different from i + 1, and 0 otherwise.
mem_latin_column_symbols
A symbol x belongs to the column symbols of column j if and only if some cell in column j has label x.

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_top_row_availability_eq_one_iff (d : YoungDiagram) (T : d.cells → ℕ)    (w : ℕ) (i j : Fin w) :    latin_top_row_availability d T w i j = 1 ↔      i.val + 1 ∉ latin_column_symbols d T j.val := by  simp [latin_top_row_availability, mem_latin_column_symbols]
See it in the graphDiscuss this resultChallenge it