AFTD Auto-Formalizing Theoretical Domains

is_config_in_all_products

def

A binary matrix F is a configuration in every p-fold product of matrices from {I_m, I_m^c, T_m} for all sufficiently large m.

Statement

def is_config_in_all_products {m_F n_F : Type*}
    (F : Matrix m_F n_F Bool) (p : ℕ) : Prop
Defined in
arXiv:2610.13987, Definition 2
Verified
23 Oct 2026
Axioms
none listed
Used by 1
  • matrix_product_invariantThe product invariant X(F) is the smallest positive integer p such that F embeds as a configuration in every p-fold product with factors…

Read back from the Lean

The definition is_config_in_all_products takes types m_F and n_F, a boolean matrix F : Matrix m_F n_F Bool, and a natural number p : ℕ. It asserts that: There exists a natural number $m_0$ such that for all natural numbers $m \ge m_0$, and for every function $\tau : \text{Fin } p \to \text{Fin } 3$, there exist: - an injective function $r : m_F \to \text{Fin } p \times \text{Fin } m$, and - an injective function $c : n_F \to (\text{Fin } p \to \text{Fin } m)$, such that for all row indices $i : m_F$ and column indices $j : n_F$, the entry $F_{i, j}$ (coerced to a proposition via $= \text{true}$) is propositionally equal to the result of matching on $\tau((r(i))_1)$: - if $\tau((r(i))_1) = 0$: $(r(i))_2 == (c(j))((r(i))_1)$ (boolean equality on $\text{Fin } m$), - if $\tau((r(i))_1) = 1$: $(r(i))_2 \ne (c(j))((r(i))_1)$ (disequality in $\text{Fin } m$), - otherwise (i.e. if $\tau((r(i))_1) = 2$): $(r(i))_2 \le (c(j))((r(i))_1)$ as natural numbers (via coercion from $\text{Fin } m$ to $\mathbb{N}$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate that a binary matrix F is a configuration in every p-fold product of identity, complement of identity, or triangular matrices of size m for all sufficiently large m. -/
def is_config_in_all_products {m_F n_F : Type*}
    (F : Matrix m_F n_F Bool) (p : ℕ) : Prop :=
  ∃ m₀ : ℕ, ∀ m : ℕ, m₀ ≤ m →
    ∀ τ : Fin p → Fin 3,
      ∃ (r : m_F → Fin p × Fin m) (c : n_F → Fin p → Fin m),
        Function.Injective r ∧ Function.Injective c ∧
        ∀ i j,
          (match τ (r i).1 with
          | 0 => (r i).2 == (c j) (r i).1
          | 1 => (r i).2 ≠ (c j) (r i).1
          | _ => ((r i).2 : ℕ) ≤ (((c j) (r i).1) : ℕ)) = F i j
See it in the graphDiscuss this resultChallenge it