AFTD Auto-Formalizing Theoretical Domains

op_1370_upper_bound_of_matrix

theoremverified

Let n be a natural number. Suppose there are a field K, a matrix L with rows indexed by the subsets of Fin n and 2^(n-1) columns, and a matrix R with 2^(n-1) rows and columns indexed by the subsets of Fin n, such that L*R vanishes at every pair (A, B) of incomparable subsets (neither A ⊆ B nor B ⊆ A), and every principal submatrix of L*R on an uncomplemented family of subsets has nonzero determinant. Then for every t and families A_1, ..., A_t of subsets of Fin n, each uncomplemented and together strongly incomparable, the sizes of the A_i sum to at most 2^(n-1).

Statement

theorem op_1370_upper_bound_of_matrix (n : ℕ)
    (hM : ∃ (K : Type) (_ : Field K) (L : Matrix (Finset (Fin n)) (Fin (2 ^ (n - 1))) K)
      (R : Matrix (Fin (2 ^ (n - 1))) (Finset (Fin n)) K),
      (∀ A B : Finset (Fin n), ¬ A ⊆ B → ¬ B ⊆ A → (L * R) A B = 0) ∧
      ∀ F : Finset (Finset (Fin n)), is_uncomplemented F →
        ((L * R).submatrix (fun x : F => (x : Finset (Fin n)))
          (fun x : F => (x : Finset (Fin n)))).det ≠ 0)
    (t : ℕ) (𝒜 : Fin t → Finset (Finset (Fin n))) (hunc : ∀ i, is_uncomplemented (𝒜 i))
    (hinc : strongly_incomparable 𝒜) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1)
Source
arXiv:2611.12199, Section 2.2 (Theorem 2.1 implies Theorem 1.7)
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • matrix_block_det_card_sum_le_widthLet K be a field, L a matrix with rows indexed by a finite type ι and columns by a finite type κ, and R a matrix with rows indexed by κ…
  • is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
  • strongly_incomparableAn indexed family of finset families 𝒜 : ι → Finset (Finset α) is strongly incomparable if for all i j : ι with i ≠ j, for all…
Used by 1

The proof, explained

The theorem is proved by applying a general block-matrix determinant lemma, `matrix_block_det_card_sum_le_width`, which bounds the sum of block sizes by the inner dimension $2^{n-1}$ of the matrix product $L R$. The off-diagonal blocks vanish because strong incomparability of the families $\mathcal{A}_i$ ensures mutual non-inclusion between elements of distinct families, while the diagonal blocks are invertible because each family $\mathcal{A}_i$ is uncomplemented. Simplifying the cardinality of $\operatorname{Fin}(2^{n-1})$ yields the desired bound $2^{n-1}$.

  1. Let $K$ be the field and $L, R$ the factoring matrices of inner dimension $2^{n-1}$, satisfying the incomparability-zero and uncomplemented-minor conditions.

    From the existential hypothesis $hM$, we extract the field $K$, the matrix $L$ of row dimension $2^n$ and column dimension $2^{n-1}$, the matrix $R$ of row dimension $2^{n-1}$ and column dimension $2^n$, the condition ($hz$) that $(L R)_{A, B} = 0$ whenever neither $A \subseteq B$ nor $B \subseteq A$, and the condition ($hd$) that every principal submatrix indexed by an uncomplemented family has non-zero determinant.

    line 11

      obtain ⟨K, _, L, R, hz, hd⟩ := hM
  2. The sum of the sizes of the families $\mathcal{A}_i$ is at most the cardinality of $\operatorname{Fin}(2^{n-1})$.

    We apply the block-matrix lemma `matrix_block_det_card_sum_le_width` to $L$, $R$, and the collection of families $\mathcal{A}$. For distinct indices $i \neq j$ and elements $a \in \mathcal{A}_i$, $b \in \mathcal{A}_j$, strong incomparability ensures that $a \not\subseteq b$, and by symmetry of inequality (`Ne.symm`), $j \neq i$ so also $b \not\subseteq a$; thus $(L R)_{a, b} = 0$ by the vanishing hypothesis $hz$. Furthermore, since each $\mathcal{A}_i$ is uncomplemented ($hunc$), its principal submatrix has non-zero determinant by $hd$.

    lines 12–14

    uses matrix_block_det_card_sum_le_width, Ne.symm

      have h := matrix_block_det_card_sum_le_width L R 𝒜
        (fun i j hij a ha b hb => hz a b (hinc i j hij a ha b hb) (hinc j i (Ne.symm hij) b hb a ha))
        (fun i => hd (𝒜 i) (hunc i))
  3. The sum of the sizes of the families $\mathcal{A}_i$ is at most $2^{n-1}$.

    Evaluating the cardinality of $\operatorname{Fin}(2^{n-1})$ as $2^{n-1}$ simplifies the bound to $\sum_i |\mathcal{A}_i| \le 2^{n-1}$.

    line 15

      simpa using h
matrix_block_det_card_sum_le_width
For matrices $L$ of size $m \times k$ and $R$ of size $k \times m$ over a field, if the product $L R$ vanishes on all pairs between distinct index sets $\mathcal{A}_i$ and $\mathcal{A}_j$ ($i \neq j$) and has non-zero determinant on each principal submatrix $\mathcal{A}_i$, then the sum of the sizes of the $\mathcal{A}_i$ is at most $k$.
Ne.symm
Symmetry of inequality: if $a \neq b$, then $b \neq a$.

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

/-- Hilton's strong-incomparability bound follows from the existence of the rank-2^(n-1) matrix of Theorem 2.1 (the paper's Section 2.2). -/theorem op_1370_upper_bound_of_matrix (n : ℕ)    (hM : ∃ (K : Type) (_ : Field K) (L : Matrix (Finset (Fin n)) (Fin (2 ^ (n - 1))) K)      (R : Matrix (Fin (2 ^ (n - 1))) (Finset (Fin n)) K),      (∀ A B : Finset (Fin n), ¬ A ⊆ B → ¬ B ⊆ A → (L * R) A B = 0) ∧      ∀ F : Finset (Finset (Fin n)), is_uncomplemented F →        ((L * R).submatrix (fun x : F => (x : Finset (Fin n)))          (fun x : F => (x : Finset (Fin n)))).det ≠ 0)    (t : ℕ) (𝒜 : Fin t → Finset (Finset (Fin n))) (hunc : ∀ i, is_uncomplemented (𝒜 i))    (hinc : strongly_incomparable 𝒜) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) := by  obtain ⟨K, _, L, R, hz, hd⟩ := hM  have h := matrix_block_det_card_sum_le_width L R 𝒜    (fun i j hij a ha b hb => hz a b (hinc i j hij a ha b hb) (hinc j i (Ne.symm hij) b hb a ha))    (fun i => hd (𝒜 i) (hunc i))  simpa using h
See it in the graphDiscuss this resultChallenge it