op_1370_upper_bound_of_matrix
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 alli j : ιwithi ≠ j, for all…
- Used by 1
- op_1370_uncomplemented_strongly_incomparable_upper_boundTheorem 1.7 of arXiv:2611.12199: for all natural numbers
nandt, if𝒜 : Fin t → Finset (Finset (Fin n))is a family such that each…
- op_1370_uncomplemented_strongly_incomparable_upper_boundTheorem 1.7 of arXiv:2611.12199: for all natural numbers
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}$.
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.
obtain ⟨K, _, L, R, hz, hd⟩ := hMThe 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$.
uses
matrix_block_det_card_sum_le_width,Ne.symmhave 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))
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}$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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