is_config_in_all_products
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