AFTD Auto-Formalizing Theoretical Domains

binary_rank

def

For an n × m binary matrix H with entries in Fin 2, the binary rank is the infimum in ℕ of all natural numbers k for which there exist binary matrices A : Matrix (Fin n) (Fin k) (Fin 2) and B : Matrix (Fin k) (Fin m) (Fin 2) whose values in ℕ satisfy H.map (·.val) = A.map (·.val) * B.map (·.val).

Statement

noncomputable def binary_rank {n m : ℕ} (H : Matrix (Fin n) (Fin m) (Fin 2)) : ℕ
Defined in
arXiv:2611.14163, Definition 2.1
Verified
12 Nov 2026
Axioms
none listed
Used by 1
  • binary_rank_zeroThe all-zero binary matrix of dimensions n × m with entries in Fin 2 has binary rank 0.

Read back from the Lean

For natural numbers n and m and a matrix H : Matrix (Fin n) (Fin m) (Fin 2), binary_rank H is defined as the infimum (in ℕ, via sInf) of the set of all k : ℕ such that there exist matrices A : Matrix (Fin n) (Fin k) (Fin 2) and B : Matrix (Fin k) (Fin m) (Fin 2) satisfying H.map (·.val) = A.map (·.val) * B.map (·.val), where the entries of H, A, and B are mapped to ℕ via Fin.val and matrix multiplication is computed over ℕ.

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

/-- The binary rank of a binary matrix H is the minimum inner dimension k of a binary factorization H = A * B over ℕ. -/
noncomputable def binary_rank {n m : ℕ} (H : Matrix (Fin n) (Fin m) (Fin 2)) : ℕ := sInf {k : ℕ | ∃ (A : Matrix (Fin n) (Fin k) (Fin 2)) (B : Matrix (Fin k) (Fin m) (Fin 2)),
    H.map (·.val) = A.map (·.val) * B.map (·.val)}
See it in the graphDiscuss this resultChallenge it