hilton_strong_incomparability_matrix
For every natural number n there are a field K, a matrix L over K with rows indexed by the subsets of Fin n and 2^(n-1) columns, and a matrix R over K with 2^(n-1) rows and columns indexed by the subsets of Fin n, such that the product M = L*R satisfies: M(A, B) = 0 whenever A and B are incomparable subsets (neither contains the other), and for every uncomplemented family F of subsets of Fin n (no set together with its complement), the principal submatrix of M on F has nonzero determinant.
Statement
theorem hilton_strong_incomparability_matrix (n : ℕ) : ∃ (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
- Formalizes
- arXiv:2611.12199, Theorem 2.1 (rank at most 2^(n-1) stated as a factorization L*R)
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
- weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Cslib.SKI.Polynomial.evalSubstitute terms for the free variables of a polynomial
- 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
Read back from the Lean
For every natural number $n$, there exist: - a type $K$ with a field structure, - a matrix $L$ of size $|\mathcal{P}(\{0, \dots, n-1\})| \times 2^{n-1}$ over $K$, and - a matrix $R$ of size $2^{n-1} \times |\mathcal{P}(\{0, \dots, n-1\})|$ over $K$, such that both of the following conditions hold: 1. For all subsets $A, B \subseteq \{0, \dots, n-1\}$, if $A$ and $B$ are incomparable under inclusion ($A \not\subseteq B$ and $B \not\subseteq A$), then the $(A, B)$-entry of the matrix product $L R$ is $0$. 2. For every family of subsets $F \subseteq \mathcal{P}(\{0, \dots, n-1\})$, if $F$ is uncomplemented (meaning no set in $F$ has its complement also in $F$), then the principal submatrix of $L R$ with rows and columns indexed by $F$ has a non-zero determinant in $K$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
We construct Hilton's strong incomparability matrix of rank at most 2^(n-1) by factoring an intermediate matrix (a diagonal matrix plus a complementation matrix) through 2^(n-1) dimensions, sandwiching it between the Mobius and zeta matrices of the Boolean lattice. The resulting matrix vanishes on incomparable pairs by Mobius inversion and a sign-reversing involution, and has non-zero determinant on any uncomplemented family by specializing polynomial indeterminates and reducing to unitriangular matrices.
The alternating sum vanishes when B is not a subset of A.
Since B is not a subset of A, choose an element i in B but not in A. Pairing each subset C with C symmetric difference {i} gives a sign-reversing involution on the terms of the sum, so all terms cancel in pairs.
uses
Finset.sum_involutionobtain ⟨i, hiB, hiA⟩ := Finset.not_subset.mp h set f : Finset (Fin n) → R := fun C => (if A ⊆ C then (-1 : R) ^ (C \ A).card else 0) * (if Cᶜ ⊆ B then 1 else 0) with hf have key : ∀ C, i ∉ C → f (insert i C) = - f C := by intro C hiC simp only [hf] have h1 : A ⊆ insert i C ↔ A ⊆ C := Finset.subset_insert_iff_of_notMem hiA have h2 : (insert i C)ᶜ ⊆ B ↔ Cᶜ ⊆ B := by rw [Finset.compl_insert] constructor · intro hiltonS x hx by_cases hxi : x = i · exact hxi ▸ hiB · exact hiltonS (Finset.mem_erase.mpr ⟨hxi, hx⟩) · intro hiltonS exact (Finset.erase_subset _ _).trans hiltonS have h3 : (insert i C \ A).card = (C \ A).card + 1 := by rw [Finset.insert_sdiff_of_notMem _ hiA, Finset.card_insert_of_notMem (by simp [hiC])] rw [if_congr h1 rfl rfl, if_congr h2 rfl rfl, h3] split_ifs <;> simp [pow_succ] refine Finset.sum_involution (fun C _ => if i ∈ C then C.erase i else insert i C) ?_ ?_ (fun _ _ => Finset.mem_univ _) ?_ · intro C _ show f C + f (if i ∈ C then C.erase i else insert i C) = 0 by_cases hiC : i ∈ C · simp only [hiC, if_true] have := key (C.erase i) (Finset.notMem_erase i C) rw [Finset.insert_erase hiC] at this rw [this] ring · simp only [hiC, if_false] rw [key C hiC] ring · intro C _ _ by_cases hiC : i ∈ C · simp [hiC, Finset.erase_eq_self] · simp [hiC, Finset.insert_eq_self] · intro C _ by_cases hiC : i ∈ C · simp [hiC, Finset.insert_erase hiC] · simp [hiC, Finset.erase_insert hiC]
The matrix product vanishes on incomparable pairs.
Expanding the matrix product gives two terms: one involving the diagonal part, which vanishes because no subset C can simultaneously contain A and be contained in B when A is not a subset of B; and one involving the complementation matrix, which vanishes by the alternating sum lemma since B is not a subset of A.
rw [Matrix.mul_add, Matrix.add_mul, Matrix.add_apply, Matrix.mul_smul, Matrix.smul_mul, Matrix.smul_apply] have e1 : (hiltonMobius R n * Matrix.diagonal q * hiltonZeta R n) A B = 0 := by rw [Matrix.mul_apply] refine Finset.sum_eq_zero (fun C _ => ?_) rw [Matrix.mul_diagonal] simp only [hiltonMobius, hiltonZeta, Matrix.of_apply] by_cases h1 : A ⊆ C · by_cases h2 : C ⊆ B · exact absurd (h1.trans h2) hAB · simp [h2] · simp [h1] have e2 : (hiltonMobius R n * hiltonCompl R n * hiltonZeta R n) A B = 0 := by rw [Matrix.mul_assoc, Matrix.mul_apply] have hPZ : ∀ C, (hiltonCompl R n * hiltonZeta R n) C B = if Cᶜ ⊆ B then 1 else 0 := by intro C rw [Matrix.mul_apply] simp only [hiltonCompl, hiltonZeta, Matrix.of_apply] rw [Finset.sum_eq_single Cᶜ] · simp · intro D _ hD have : C ≠ Dᶜ := by intro hC exact hD (by rw [hC, compl_compl]) simp [this] · simp simp only [hPZ] simp only [hiltonMobius, Matrix.of_apply] exact hilton_alt_sum_zero A B hBA rw [e1, e2] simp
Unitriangular matrices supported on inclusion have determinant one.
The matrix is block upper triangular when subsets are ordered by cardinality, and each diagonal block is the identity matrix because distinct subsets of the same size cannot contain each other.
classical have hbt : W.BlockTriangular (fun a : F => (a : Finset (Fin n)).card) := by intro i j hij apply hW0 intro hsub exact absurd (Finset.card_le_card hsub) (not_le.mpr hij) rw [hbt.det] refine Finset.prod_eq_one (fun k _ => ?_) have : W.toSquareBlock (fun a : F => (a : Finset (Fin n)).card) k = 1 := by ext ⟨a, ha⟩ ⟨c, hc⟩ rw [Matrix.toSquareBlock_def, Matrix.of_apply, Matrix.one_apply] by_cases hac : a = c · subst hac simp [hW1] · have hne : (⟨a, ha⟩ : {x : F // (x : Finset (Fin n)).card = k}) ≠ ⟨c, hc⟩ := fun h => hac (congrArg Subtype.val h) rw [if_neg hne] apply hW0 intro hsub apply hac apply Subtype.ext exact Finset.eq_of_subset_of_card_le hsub (by omega) rw [this, Matrix.det_one]
Ring homomorphisms commute with the zeta and Mobius matrices.
Applying a ring homomorphism to the zeta and Mobius matrices preserves their entries since their entries are integers (0, 1, or powers of -1).
ext A B simp [hiltonZeta, RingHom.mapMatrix_apply, apply_ite f] theorem hilton_mobius_map {R S : Type} [CommRing R] [CommRing S] (f : R →+* S) (n : ℕ) : f.mapMatrix (hiltonMobius R n) = hiltonMobius S n := by ext A B simp [hiltonMobius, RingHom.mapMatrix_apply, apply_ite f]
The principal submatrix on any uncomplemented family has non-zero determinant.
Specializing the variables to powers of a single variable X and evaluating the determinant at X = 0 reduces the determinant to the product of determinants of the submatrices of Mobius and zeta, each of which is 1 by unitriangularity.
classical by_cases hF0 : F = ∅ · haveI : IsEmpty F := Finset.isEmpty_coe_sort.mpr hF0 rw [Matrix.det_isEmpty] exact one_ne_zero set m := F.card with hmdef have hm : 1 ≤ m := Finset.card_pos.mpr (Finset.nonempty_iff_ne_empty.mpr hF0) set g : Finset (Fin n) → Polynomial ℚ := fun C => if Cᶜ ∈ F then Polynomial.X else 1 with hg set φ : MvPolynomial (Finset (Fin n)) ℚ →+* Polynomial ℚ := MvPolynomial.eval₂Hom Polynomial.C g with hφ set S := Finset.univ.filter (fun D : Finset (Fin n) => Dᶜ ∈ F) with hS have hcnt : S.card = m := by have : S = F.image compl := by ext D simp only [hS, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] constructor · intro h exact ⟨Dᶜ, h, compl_compl D⟩ · rintro ⟨a, ha, rfl⟩ simpa using ha rw [this, Finset.card_image_of_injective _ compl_injective] have hprod : ∀ T : Finset (Finset (Fin n)), φ (∏ C ∈ T, MvPolynomial.X C) = Polynomial.X ^ (T.filter (fun D => Dᶜ ∈ F)).card := by intro T rw [map_prod] simp only [hφ, MvPolynomial.eval₂Hom_X', hg] rw [Finset.prod_ite] simp [Finset.prod_const] have hPi_card : ∀ A, ((Finset.univ.erase A).erase Aᶜ).filter (fun D => Dᶜ ∈ F) = (S.erase A).erase Aᶜ := by intro A rw [Finset.filter_erase, Finset.filter_erase] have hs_im : φ (hiltonS n) = Polynomial.X ^ m := by rw [hiltonS, hprod, ← hS, hcnt] have hqF : ∀ A ∈ F, φ (hiltonQ n A) = Polynomial.X ^ (m - 1) := by intro A hA have hAc : Aᶜ ∉ F := hF A hA have hAS : A ∉ S := by simpa [hS] using hAc have hAcS : Aᶜ ∈ S := by simpa [hS] using hA rw [hiltonQ, map_mul, map_pow, hiltonPi, hprod, hPi_card, Finset.erase_eq_of_notMem hAS, Finset.card_erase_of_mem hAcS, hcnt] simp [hφ, hg, hAc] have hqN : ∀ A ∉ F, Polynomial.X ^ m ∣ φ (hiltonQ n A) := by intro A hA rw [hiltonQ, map_mul, map_pow, hiltonPi, hprod, hPi_card] have hAcS : Aᶜ ∉ S := by simpa [hS] using hA rw [Finset.erase_eq_of_notMem (fun h => hAcS (Finset.mem_of_mem_erase h))] by_cases hAc : Aᶜ ∈ F · have hAS : A ∈ S := by simpa [hS] using hAc rw [Finset.card_erase_of_mem hAS, hcnt] simp only [hφ, MvPolynomial.eval₂Hom_X', hg, if_pos hAc] rw [← pow_add] exact pow_dvd_pow _ (by omega) · have hAS : A ∉ S := by simpa [hS] using hAc rw [Finset.erase_eq_of_notMem hAS, hcnt] simp only [hφ, MvPolynomial.eval₂Hom_X', hg, if_neg hAc] simp set D1 : Matrix (Finset (Fin n)) (Finset (Fin n)) (Polynomial ℚ) := Matrix.diagonal (fun C => if C ∈ F then 1 else 0) with hD1 have hNm : φ.mapMatrix (Matrix.diagonal (hiltonQ n) + hiltonS n • hiltonCompl _ n) = Matrix.diagonal (fun C => φ (hiltonQ n C)) + φ (hiltonS n) • hiltonCompl (Polynomial ℚ) n := by ext A B simp [RingHom.mapMatrix_apply, Matrix.diagonal_apply, hiltonCompl, apply_ite φ] have hdiv : ∀ A B, ∃ e, (Matrix.diagonal (fun C => φ (hiltonQ n C)) + φ (hiltonS n) • hiltonCompl (Polynomial ℚ) n) A B - Polynomial.X ^ (m - 1) * D1 A B = Polynomial.X ^ m * e := by intro A B simp only [Matrix.add_apply, Matrix.smul_apply, Matrix.diagonal_apply, hD1, hiltonCompl, Matrix.of_apply, smul_eq_mul, hs_im] by_cases hAB : A = B · subst hAB by_cases hA : A ∈ F · simp only [if_pos hA, hqF A hA, ↓reduceIte] exact ⟨if A = Aᶜ then 1 else 0, by ring⟩ · simp only [if_neg hA, ↓reduceIte] obtain ⟨c, hc⟩ := hqN A hA exact ⟨c + (if A = Aᶜ then 1 else 0), by rw [hc]; ring⟩ · simp only [if_neg hAB] exact ⟨if A = Bᶜ then 1 else 0, by ring⟩ choose E hE using hdiv have hN'eq : Matrix.diagonal (fun C => φ (hiltonQ n C)) + φ (hiltonS n) • hiltonCompl (Polynomial ℚ) n = (Polynomial.X : Polynomial ℚ) ^ (m - 1) • (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) := by refine Matrix.ext (fun A B => ?_) have h := hE A B have hmm : (Polynomial.X : Polynomial ℚ) ^ m = Polynomial.X ^ (m - 1) * Polynomial.X := by rw [← pow_succ] congr 1 omega rw [hmm] at h simp only [Matrix.smul_apply, Matrix.add_apply, Matrix.of_apply, smul_eq_mul] at h ⊢ linear_combination h have hmap : φ.mapMatrix (hiltonMat n) = (Polynomial.X : Polynomial ℚ) ^ (m - 1) • (hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n) := by rw [hiltonMat, map_mul, map_mul, hilton_mobius_map, hilton_zeta_map, hNm, hN'eq, Matrix.mul_smul, Matrix.smul_mul] intro hdet have h1 := congrArg φ hdet rw [RingHom.map_det, map_zero] at h1 have hsub : φ.mapMatrix ((hiltonMat n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) = (φ.mapMatrix (hiltonMat n)).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := rfl rw [hsub, hmap] at h1 set W := hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n with hWdef have hsm : ((Polynomial.X : Polynomial ℚ) ^ (m - 1) • W).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) = (Polynomial.X : Polynomial ℚ) ^ (m - 1) • W.submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := rfl rw [hsm, Matrix.det_smul] at h1 rcases mul_eq_zero.mp h1 with h | h · exact pow_ne_zero _ (pow_ne_zero _ Polynomial.X_ne_zero) h · have h2 := congrArg (Polynomial.evalRingHom 0) h rw [RingHom.map_det, map_zero] at h2 have hD1m : (Polynomial.evalRingHom 0).mapMatrix (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) = Matrix.diagonal (fun C => if C ∈ F then (1 : ℚ) else 0) := by refine Matrix.ext (fun A B => ?_) by_cases hAB : A = B · subst hAB by_cases hA : A ∈ F <;> simp [hD1, RingHom.mapMatrix_apply, hA] · simp [hD1, RingHom.mapMatrix_apply, Matrix.diagonal_apply, hAB] have hW : (Polynomial.evalRingHom 0).mapMatrix ((hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) = (hiltonMobius ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) * (hiltonZeta ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := by have : (Polynomial.evalRingHom 0).mapMatrix ((hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) = ((Polynomial.evalRingHom 0).mapMatrix (hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n)).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := rfl rw [this, map_mul, map_mul, hilton_mobius_map, hilton_zeta_map, hD1m] refine Matrix.ext (fun a b => ?_) rw [Matrix.submatrix_apply, Matrix.mul_apply, Matrix.mul_apply] simp_rw [Matrix.mul_diagonal, Matrix.submatrix_apply] simp_rw [mul_ite, mul_one, mul_zero, ite_mul, zero_mul] rw [Finset.sum_ite_mem, Finset.univ_inter] exact (Finset.sum_coe_sort F (fun C => hiltonMobius ℚ n a C * hiltonZeta ℚ n C b)).symm rw [hW, Matrix.det_mul] at h2 have hd1 : ((hiltonMobius ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))).det = 1 := by apply hilton_det_unitri · intro a b hab simp [hiltonMobius, hab] · intro a simp [hiltonMobius] have hd2 : ((hiltonZeta ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))).det = 1 := by apply hilton_det_unitri · intro a b hab simp [hiltonZeta, hab] · intro a simp [hiltonZeta] rw [hd1, hd2] at h2 norm_num at h2
Pi is invariant under complementation.
Removing a set and its complement from the universe is symmetric under complementation.
unfold hiltonPi rw [compl_compl, Finset.erase_right_comm]
The diagonal plus complementation matrix factors through 2^(n-1) dimensions.
Grouping subsets into complementary pairs, represented by the subset not containing 0, yields an explicit factorization into a product of matrices of inner dimension 2^(n-1).
classical set T := {r : Finset (Fin (k + 1)) // (0 : Fin (k + 1)) ∉ r} have hcard : Fintype.card T = 2 ^ (k + 1 - 1) := by rw [Fintype.card_subtype] have : Finset.univ.filter (fun r : Finset (Fin (k + 1)) => (0 : Fin (k + 1)) ∉ r) = (Finset.univ.erase (0 : Fin (k + 1))).powerset := by ext r simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_powerset] constructor · intro h x hx exact Finset.mem_erase.mpr ⟨fun e => h (e ▸ hx), Finset.mem_univ _⟩ · intro h h0 exact (Finset.mem_erase.mp (h h0)).1 rfl rw [this, Finset.card_powerset, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin] set e : T ≃ Fin (2 ^ (k + 1 - 1)) := Fintype.equivFinOfCardEq hcard have hne : ∀ A : Finset (Fin (k + 1)), A ≠ Aᶜ := by intro A h by_cases h0 : (0 : Fin (k + 1)) ∈ A · have : (0 : Fin (k + 1)) ∈ Aᶜ := h ▸ h0 exact (Finset.mem_compl.mp this) h0 · have : (0 : Fin (k + 1)) ∉ Aᶜ := h ▸ h0 exact this (Finset.mem_compl.mpr h0) let rep : Finset (Fin (k + 1)) → T := fun A => if h : (0 : Fin (k + 1)) ∈ A then ⟨Aᶜ, by simpa using h⟩ else ⟨A, h⟩ have hrep : ∀ A (r : T), (A = r.1 ∨ A = r.1ᶜ) ↔ r = rep A := by intro A r obtain ⟨r, hr⟩ := r simp only [rep] by_cases h0 : (0 : Fin (k + 1)) ∈ A · rw [dif_pos h0] constructor · rintro (h | h) · exact absurd (h ▸ h0) hr · exact Subtype.ext (by simp [h]) · intro h right have := congrArg Subtype.val h simp only at this rw [this, compl_compl] · rw [dif_neg h0] constructor · rintro (h | h) · exact Subtype.ext h.symm · exfalso apply h0 rw [h] exact Finset.mem_compl.mpr hr · intro h left exact (congrArg Subtype.val h).symm have hrepv : ∀ A, ((rep A).1 = A ∨ (rep A).1 = Aᶜ) := by intro A simp only [rep] split_ifs <;> simp let X0 : Matrix (Finset (Fin (k + 1))) T (MvPolynomial (Finset (Fin (k + 1))) ℚ) := Matrix.of fun A r => if A = r.1 ∨ A = r.1ᶜ then MvPolynomial.X A else 0 let Y0 : Matrix T (Finset (Fin (k + 1))) (MvPolynomial (Finset (Fin (k + 1))) ℚ) := Matrix.of fun r B => if B = r.1 ∨ B = r.1ᶜ then MvPolynomial.X B * hiltonPi (k + 1) r.1 else 0 refine ⟨X0.submatrix id e.symm, Y0.submatrix e.symm id, ?_⟩ rw [Matrix.submatrix_mul_equiv, Matrix.submatrix_id_id] have hs_split : ∀ A : Finset (Fin (k + 1)), hiltonS (k + 1) = MvPolynomial.X A * MvPolynomial.X Aᶜ * hiltonPi (k + 1) A := by intro A unfold hiltonS hiltonPi rw [← Finset.mul_prod_erase Finset.univ _ (Finset.mem_univ A), ← Finset.mul_prod_erase (Finset.univ.erase A) _ (Finset.mem_erase.mpr ⟨(hne A).symm, Finset.mem_univ _⟩)] ring refine Matrix.ext (fun A B => ?_) rw [Matrix.mul_apply] simp only [X0, Y0, Matrix.of_apply, ite_mul, zero_mul] simp only [hrep A] rw [Finset.sum_eq_single (rep A) (fun r _ hr => by rw [if_neg hr]) (by simp), if_pos rfl] have hPi_rep : hiltonPi (k + 1) (rep A).1 = hiltonPi (k + 1) A := by rcases hrepv A with h | h <;> rw [h] exact hilton_pi_compl _ A have hBorb : (B = (rep A).1 ∨ B = (rep A).1ᶜ) ↔ (B = A ∨ B = Aᶜ) := by rcases hrepv A with h | h <;> rw [h] rw [compl_compl, or_comm] rw [hPi_rep, if_congr hBorb rfl rfl] simp only [Matrix.add_apply, Matrix.smul_apply, Matrix.diagonal_apply, hiltonCompl, Matrix.of_apply, smul_eq_mul, hiltonQ] by_cases h1 : B = A · subst h1 have : B ≠ Bᶜ := hne B simp [this] ring · by_cases h2 : B = Aᶜ · subst h2 have : A ≠ Aᶜ := hne A simp [this, Ne.symm this, hs_split A] ring · have h3 : A ≠ Bᶜ := fun h => h2 (by rw [h, compl_compl]) simp [h1, h2, h3, Ne.symm h1]
Matrices over an integral domain lift to its fraction field.
Embedding the entries into the fraction field preserves zero entries and non-zero determinants since the canonical map into the field of fractions is injective.
refine ⟨FractionRing R, inferInstance, L0.map (algebraMap R (FractionRing R)), R0.map (algebraMap R (FractionRing R)), ?_, ?_⟩ · intro A B h1 h2 rw [← Matrix.map_mul, Matrix.map_apply, hz A B h1 h2, map_zero] · intro F hF rw [← Matrix.map_mul] have : ((L0 * R0).map (algebraMap R (FractionRing R))).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) = (algebraMap R (FractionRing R)).mapMatrix ((L0 * R0).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) := rfl rw [this, ← RingHom.map_det] exact (map_ne_zero_iff _ (IsFractionRing.injective R (FractionRing R))).mpr (hd F hF)
Constructing the strong incomparability matrix of Theorem 2.1.
For n = 0 the only uncomplemented family is empty. For n >= 1, we factor the inner matrix into 2^(n-1) dimensions over the polynomial ring, multiply by Mobius and zeta, and lift to the fraction field.
classical rcases n with _ | k · refine ⟨ℚ, inferInstance, 0, 0, fun A B h _ => absurd (Subsingleton.elim A B ▸ subset_refl A) h, fun F hF => ?_⟩ have hF0 : F = ∅ := by rw [Finset.eq_empty_iff_forall_notMem] intro A hA exact hF A hA (by rwa [Subsingleton.elim Aᶜ A]) have : IsEmpty F := Finset.isEmpty_coe_sort.mpr hF0 rw [Matrix.det_isEmpty] exact one_ne_zero · obtain ⟨X, Y, hXY⟩ := hilton_factor k have hLR : (hiltonMobius (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1) * X) * (Y * hiltonZeta (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1)) = hiltonMat (k + 1) := by rw [hiltonMat, Matrix.mul_assoc (hiltonMobius _ _) X, ← Matrix.mul_assoc X, hXY, ← Matrix.mul_assoc] refine hilton_lift (hiltonMobius (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1) * X) (Y * hiltonZeta (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1)) ?_ ?_ · intro A B h1 h2 rw [hLR, hiltonMat] exact hilton_mat_zero_of_incomparable _ _ A B h1 h2 · intro F hF rw [hLR] exact hilton_mat_det_ne F hF
Finset.sum_involution- sum vanishes when elements can be paired with opposite signs
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.
/-- zeta matrix of the Boolean lattice -/noncomputable def hiltonZeta (R : Type) [CommRing R] (n : ℕ) : Matrix (Finset (Fin n)) (Finset (Fin n)) R := Matrix.of fun A B => if A ⊆ B then 1 else 0/-- Möbius matrix of the Boolean lattice -/noncomputable def hiltonMobius (R : Type) [CommRing R] (n : ℕ) : Matrix (Finset (Fin n)) (Finset (Fin n)) R := Matrix.of fun A B => if A ⊆ B then (-1 : R) ^ (B \ A).card else 0/-- complementation matrix -/noncomputable def hiltonCompl (R : Type) [CommRing R] (n : ℕ) : Matrix (Finset (Fin n)) (Finset (Fin n)) R := Matrix.of fun A B => if A = Bᶜ then 1 else 0theorem hilton_alt_sum_zero {R : Type} [CommRing R] {n : ℕ} (A B : Finset (Fin n)) (h : ¬ B ⊆ A) : ∑ C : Finset (Fin n), (if A ⊆ C then (-1 : R) ^ (C \ A).card else 0) * (if Cᶜ ⊆ B then 1 else 0) = 0 := by obtain ⟨i, hiB, hiA⟩ := Finset.not_subset.mp h set f : Finset (Fin n) → R := fun C => (if A ⊆ C then (-1 : R) ^ (C \ A).card else 0) * (if Cᶜ ⊆ B then 1 else 0) with hf have key : ∀ C, i ∉ C → f (insert i C) = - f C := by intro C hiC simp only [hf] have h1 : A ⊆ insert i C ↔ A ⊆ C := Finset.subset_insert_iff_of_notMem hiA have h2 : (insert i C)ᶜ ⊆ B ↔ Cᶜ ⊆ B := by rw [Finset.compl_insert] constructor · intro hiltonS x hx by_cases hxi : x = i · exact hxi ▸ hiB · exact hiltonS (Finset.mem_erase.mpr ⟨hxi, hx⟩) · intro hiltonS exact (Finset.erase_subset _ _).trans hiltonS have h3 : (insert i C \ A).card = (C \ A).card + 1 := by rw [Finset.insert_sdiff_of_notMem _ hiA, Finset.card_insert_of_notMem (by simp [hiC])] rw [if_congr h1 rfl rfl, if_congr h2 rfl rfl, h3] split_ifs <;> simp [pow_succ] refine Finset.sum_involution (fun C _ => if i ∈ C then C.erase i else insert i C) ?_ ?_ (fun _ _ => Finset.mem_univ _) ?_ · intro C _ show f C + f (if i ∈ C then C.erase i else insert i C) = 0 by_cases hiC : i ∈ C · simp only [hiC, if_true] have := key (C.erase i) (Finset.notMem_erase i C) rw [Finset.insert_erase hiC] at this rw [this] ring · simp only [hiC, if_false] rw [key C hiC] ring · intro C _ _ by_cases hiC : i ∈ C · simp [hiC, Finset.erase_eq_self] · simp [hiC, Finset.insert_eq_self] · intro C _ by_cases hiC : i ∈ C · simp [hiC, Finset.insert_erase hiC] · simp [hiC, Finset.erase_insert hiC]/-- the matrix `Zi * (diag q + s P) * Z` vanishes on incomparable pairs -/theorem hilton_mat_zero_of_incomparable {R : Type} [CommRing R] {n : ℕ} (q : Finset (Fin n) → R) (s : R) (A B : Finset (Fin n)) (hAB : ¬ A ⊆ B) (hBA : ¬ B ⊆ A) : (hiltonMobius R n * (Matrix.diagonal q + s • hiltonCompl R n) * hiltonZeta R n) A B = 0 := by rw [Matrix.mul_add, Matrix.add_mul, Matrix.add_apply, Matrix.mul_smul, Matrix.smul_mul, Matrix.smul_apply] have e1 : (hiltonMobius R n * Matrix.diagonal q * hiltonZeta R n) A B = 0 := by rw [Matrix.mul_apply] refine Finset.sum_eq_zero (fun C _ => ?_) rw [Matrix.mul_diagonal] simp only [hiltonMobius, hiltonZeta, Matrix.of_apply] by_cases h1 : A ⊆ C · by_cases h2 : C ⊆ B · exact absurd (h1.trans h2) hAB · simp [h2] · simp [h1] have e2 : (hiltonMobius R n * hiltonCompl R n * hiltonZeta R n) A B = 0 := by rw [Matrix.mul_assoc, Matrix.mul_apply] have hPZ : ∀ C, (hiltonCompl R n * hiltonZeta R n) C B = if Cᶜ ⊆ B then 1 else 0 := by intro C rw [Matrix.mul_apply] simp only [hiltonCompl, hiltonZeta, Matrix.of_apply] rw [Finset.sum_eq_single Cᶜ] · simp · intro D _ hD have : C ≠ Dᶜ := by intro hC exact hD (by rw [hC, compl_compl]) simp [this] · simp simp only [hPZ] simp only [hiltonMobius, Matrix.of_apply] exact hilton_alt_sum_zero A B hBA rw [e1, e2] simp/-- a matrix on an `F`-indexed set, supported on `⊆` with unit diagonal, has determinant one -/theorem hilton_det_unitri {K : Type} [CommRing K] {n : ℕ} (F : Finset (Finset (Fin n))) (W : Matrix F F K) (hW0 : ∀ a b : F, ¬ (a : Finset (Fin n)) ⊆ b → W a b = 0) (hW1 : ∀ a, W a a = 1) : W.det = 1 := by classical have hbt : W.BlockTriangular (fun a : F => (a : Finset (Fin n)).card) := by intro i j hij apply hW0 intro hsub exact absurd (Finset.card_le_card hsub) (not_le.mpr hij) rw [hbt.det] refine Finset.prod_eq_one (fun k _ => ?_) have : W.toSquareBlock (fun a : F => (a : Finset (Fin n)).card) k = 1 := by ext ⟨a, ha⟩ ⟨c, hc⟩ rw [Matrix.toSquareBlock_def, Matrix.of_apply, Matrix.one_apply] by_cases hac : a = c · subst hac simp [hW1] · have hne : (⟨a, ha⟩ : {x : F // (x : Finset (Fin n)).card = k}) ≠ ⟨c, hc⟩ := fun h => hac (congrArg Subtype.val h) rw [if_neg hne] apply hW0 intro hsub apply hac apply Subtype.ext exact Finset.eq_of_subset_of_card_le hsub (by omega) rw [this, Matrix.det_one]/-- the product of the variables outside the orbit of `A` -/noncomputable def hiltonPi (n : ℕ) (A : Finset (Fin n)) : MvPolynomial (Finset (Fin n)) ℚ := ∏ C ∈ (Finset.univ.erase A).erase Aᶜ, MvPolynomial.X C/-- the product of all variables -/noncomputable def hiltonS (n : ℕ) : MvPolynomial (Finset (Fin n)) ℚ := ∏ C, MvPolynomial.X C/-- diagonal weight `q_A = x_A^2 Π'_A` -/noncomputable def hiltonQ (n : ℕ) (A : Finset (Fin n)) : MvPolynomial (Finset (Fin n)) ℚ := MvPolynomial.X A ^ 2 * hiltonPi n A/-- the matrix `M = Z^{-1} (diag q + s P) Z` -/noncomputable def hiltonMat (n : ℕ) : Matrix (Finset (Fin n)) (Finset (Fin n)) (MvPolynomial (Finset (Fin n)) ℚ) := hiltonMobius _ n * (Matrix.diagonal (hiltonQ n) + hiltonS n • hiltonCompl _ n) * hiltonZeta _ ntheorem hilton_zeta_map {R S : Type} [CommRing R] [CommRing S] (f : R →+* S) (n : ℕ) : f.mapMatrix (hiltonZeta R n) = hiltonZeta S n := by ext A B simp [hiltonZeta, RingHom.mapMatrix_apply, apply_ite f]theorem hilton_mobius_map {R S : Type} [CommRing R] [CommRing S] (f : R →+* S) (n : ℕ) : f.mapMatrix (hiltonMobius R n) = hiltonMobius S n := by ext A B simp [hiltonMobius, RingHom.mapMatrix_apply, apply_ite f]theorem hilton_mat_det_ne {n : ℕ} (F : Finset (Finset (Fin n))) (hF : is_uncomplemented F) : ((hiltonMat n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))).det ≠ 0 := by classical by_cases hF0 : F = ∅ · haveI : IsEmpty F := Finset.isEmpty_coe_sort.mpr hF0 rw [Matrix.det_isEmpty] exact one_ne_zero set m := F.card with hmdef have hm : 1 ≤ m := Finset.card_pos.mpr (Finset.nonempty_iff_ne_empty.mpr hF0) set g : Finset (Fin n) → Polynomial ℚ := fun C => if Cᶜ ∈ F then Polynomial.X else 1 with hg set φ : MvPolynomial (Finset (Fin n)) ℚ →+* Polynomial ℚ := MvPolynomial.eval₂Hom Polynomial.C g with hφ set S := Finset.univ.filter (fun D : Finset (Fin n) => Dᶜ ∈ F) with hS have hcnt : S.card = m := by have : S = F.image compl := by ext D simp only [hS, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] constructor · intro h exact ⟨Dᶜ, h, compl_compl D⟩ · rintro ⟨a, ha, rfl⟩ simpa using ha rw [this, Finset.card_image_of_injective _ compl_injective] have hprod : ∀ T : Finset (Finset (Fin n)), φ (∏ C ∈ T, MvPolynomial.X C) = Polynomial.X ^ (T.filter (fun D => Dᶜ ∈ F)).card := by intro T rw [map_prod] simp only [hφ, MvPolynomial.eval₂Hom_X', hg] rw [Finset.prod_ite] simp [Finset.prod_const] have hPi_card : ∀ A, ((Finset.univ.erase A).erase Aᶜ).filter (fun D => Dᶜ ∈ F) = (S.erase A).erase Aᶜ := by intro A rw [Finset.filter_erase, Finset.filter_erase] have hs_im : φ (hiltonS n) = Polynomial.X ^ m := by rw [hiltonS, hprod, ← hS, hcnt] have hqF : ∀ A ∈ F, φ (hiltonQ n A) = Polynomial.X ^ (m - 1) := by intro A hA have hAc : Aᶜ ∉ F := hF A hA have hAS : A ∉ S := by simpa [hS] using hAc have hAcS : Aᶜ ∈ S := by simpa [hS] using hA rw [hiltonQ, map_mul, map_pow, hiltonPi, hprod, hPi_card, Finset.erase_eq_of_notMem hAS, Finset.card_erase_of_mem hAcS, hcnt] simp [hφ, hg, hAc] have hqN : ∀ A ∉ F, Polynomial.X ^ m ∣ φ (hiltonQ n A) := by intro A hA rw [hiltonQ, map_mul, map_pow, hiltonPi, hprod, hPi_card] have hAcS : Aᶜ ∉ S := by simpa [hS] using hA rw [Finset.erase_eq_of_notMem (fun h => hAcS (Finset.mem_of_mem_erase h))] by_cases hAc : Aᶜ ∈ F · have hAS : A ∈ S := by simpa [hS] using hAc rw [Finset.card_erase_of_mem hAS, hcnt] simp only [hφ, MvPolynomial.eval₂Hom_X', hg, if_pos hAc] rw [← pow_add] exact pow_dvd_pow _ (by omega) · have hAS : A ∉ S := by simpa [hS] using hAc rw [Finset.erase_eq_of_notMem hAS, hcnt] simp only [hφ, MvPolynomial.eval₂Hom_X', hg, if_neg hAc] simp set D1 : Matrix (Finset (Fin n)) (Finset (Fin n)) (Polynomial ℚ) := Matrix.diagonal (fun C => if C ∈ F then 1 else 0) with hD1 have hNm : φ.mapMatrix (Matrix.diagonal (hiltonQ n) + hiltonS n • hiltonCompl _ n) = Matrix.diagonal (fun C => φ (hiltonQ n C)) + φ (hiltonS n) • hiltonCompl (Polynomial ℚ) n := by ext A B simp [RingHom.mapMatrix_apply, Matrix.diagonal_apply, hiltonCompl, apply_ite φ] have hdiv : ∀ A B, ∃ e, (Matrix.diagonal (fun C => φ (hiltonQ n C)) + φ (hiltonS n) • hiltonCompl (Polynomial ℚ) n) A B - Polynomial.X ^ (m - 1) * D1 A B = Polynomial.X ^ m * e := by intro A B simp only [Matrix.add_apply, Matrix.smul_apply, Matrix.diagonal_apply, hD1, hiltonCompl, Matrix.of_apply, smul_eq_mul, hs_im] by_cases hAB : A = B · subst hAB by_cases hA : A ∈ F · simp only [if_pos hA, hqF A hA, ↓reduceIte] exact ⟨if A = Aᶜ then 1 else 0, by ring⟩ · simp only [if_neg hA, ↓reduceIte] obtain ⟨c, hc⟩ := hqN A hA exact ⟨c + (if A = Aᶜ then 1 else 0), by rw [hc]; ring⟩ · simp only [if_neg hAB] exact ⟨if A = Bᶜ then 1 else 0, by ring⟩ choose E hE using hdiv have hN'eq : Matrix.diagonal (fun C => φ (hiltonQ n C)) + φ (hiltonS n) • hiltonCompl (Polynomial ℚ) n = (Polynomial.X : Polynomial ℚ) ^ (m - 1) • (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) := by refine Matrix.ext (fun A B => ?_) have h := hE A B have hmm : (Polynomial.X : Polynomial ℚ) ^ m = Polynomial.X ^ (m - 1) * Polynomial.X := by rw [← pow_succ] congr 1 omega rw [hmm] at h simp only [Matrix.smul_apply, Matrix.add_apply, Matrix.of_apply, smul_eq_mul] at h ⊢ linear_combination h have hmap : φ.mapMatrix (hiltonMat n) = (Polynomial.X : Polynomial ℚ) ^ (m - 1) • (hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n) := by rw [hiltonMat, map_mul, map_mul, hilton_mobius_map, hilton_zeta_map, hNm, hN'eq, Matrix.mul_smul, Matrix.smul_mul] intro hdet have h1 := congrArg φ hdet rw [RingHom.map_det, map_zero] at h1 have hsub : φ.mapMatrix ((hiltonMat n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) = (φ.mapMatrix (hiltonMat n)).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := rfl rw [hsub, hmap] at h1 set W := hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n with hWdef have hsm : ((Polynomial.X : Polynomial ℚ) ^ (m - 1) • W).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) = (Polynomial.X : Polynomial ℚ) ^ (m - 1) • W.submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := rfl rw [hsm, Matrix.det_smul] at h1 rcases mul_eq_zero.mp h1 with h | h · exact pow_ne_zero _ (pow_ne_zero _ Polynomial.X_ne_zero) h · have h2 := congrArg (Polynomial.evalRingHom 0) h rw [RingHom.map_det, map_zero] at h2 have hD1m : (Polynomial.evalRingHom 0).mapMatrix (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) = Matrix.diagonal (fun C => if C ∈ F then (1 : ℚ) else 0) := by refine Matrix.ext (fun A B => ?_) by_cases hAB : A = B · subst hAB by_cases hA : A ∈ F <;> simp [hD1, RingHom.mapMatrix_apply, hA] · simp [hD1, RingHom.mapMatrix_apply, Matrix.diagonal_apply, hAB] have hW : (Polynomial.evalRingHom 0).mapMatrix ((hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) = (hiltonMobius ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) * (hiltonZeta ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := by have : (Polynomial.evalRingHom 0).mapMatrix ((hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) = ((Polynomial.evalRingHom 0).mapMatrix (hiltonMobius _ n * (D1 + (Polynomial.X : Polynomial ℚ) • Matrix.of E) * hiltonZeta _ n)).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) := rfl rw [this, map_mul, map_mul, hilton_mobius_map, hilton_zeta_map, hD1m] refine Matrix.ext (fun a b => ?_) rw [Matrix.submatrix_apply, Matrix.mul_apply, Matrix.mul_apply] simp_rw [Matrix.mul_diagonal, Matrix.submatrix_apply] simp_rw [mul_ite, mul_one, mul_zero, ite_mul, zero_mul] rw [Finset.sum_ite_mem, Finset.univ_inter] exact (Finset.sum_coe_sort F (fun C => hiltonMobius ℚ n a C * hiltonZeta ℚ n C b)).symm rw [hW, Matrix.det_mul] at h2 have hd1 : ((hiltonMobius ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))).det = 1 := by apply hilton_det_unitri · intro a b hab simp [hiltonMobius, hab] · intro a simp [hiltonMobius] have hd2 : ((hiltonZeta ℚ n).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))).det = 1 := by apply hilton_det_unitri · intro a b hab simp [hiltonZeta, hab] · intro a simp [hiltonZeta] rw [hd1, hd2] at h2 norm_num at h2theorem hilton_pi_compl (n : ℕ) (A : Finset (Fin n)) : hiltonPi n Aᶜ = hiltonPi n A := by unfold hiltonPi rw [compl_compl, Finset.erase_right_comm]theorem hilton_factor (k : ℕ) : ∃ (X : Matrix (Finset (Fin (k + 1))) (Fin (2 ^ (k + 1 - 1))) (MvPolynomial (Finset (Fin (k + 1))) ℚ)) (Y : Matrix (Fin (2 ^ (k + 1 - 1))) (Finset (Fin (k + 1))) (MvPolynomial (Finset (Fin (k + 1))) ℚ)), X * Y = Matrix.diagonal (hiltonQ (k + 1)) + hiltonS (k + 1) • hiltonCompl _ (k + 1) := by classical set T := {r : Finset (Fin (k + 1)) // (0 : Fin (k + 1)) ∉ r} have hcard : Fintype.card T = 2 ^ (k + 1 - 1) := by rw [Fintype.card_subtype] have : Finset.univ.filter (fun r : Finset (Fin (k + 1)) => (0 : Fin (k + 1)) ∉ r) = (Finset.univ.erase (0 : Fin (k + 1))).powerset := by ext r simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_powerset] constructor · intro h x hx exact Finset.mem_erase.mpr ⟨fun e => h (e ▸ hx), Finset.mem_univ _⟩ · intro h h0 exact (Finset.mem_erase.mp (h h0)).1 rfl rw [this, Finset.card_powerset, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin] set e : T ≃ Fin (2 ^ (k + 1 - 1)) := Fintype.equivFinOfCardEq hcard have hne : ∀ A : Finset (Fin (k + 1)), A ≠ Aᶜ := by intro A h by_cases h0 : (0 : Fin (k + 1)) ∈ A · have : (0 : Fin (k + 1)) ∈ Aᶜ := h ▸ h0 exact (Finset.mem_compl.mp this) h0 · have : (0 : Fin (k + 1)) ∉ Aᶜ := h ▸ h0 exact this (Finset.mem_compl.mpr h0) let rep : Finset (Fin (k + 1)) → T := fun A => if h : (0 : Fin (k + 1)) ∈ A then ⟨Aᶜ, by simpa using h⟩ else ⟨A, h⟩ have hrep : ∀ A (r : T), (A = r.1 ∨ A = r.1ᶜ) ↔ r = rep A := by intro A r obtain ⟨r, hr⟩ := r simp only [rep] by_cases h0 : (0 : Fin (k + 1)) ∈ A · rw [dif_pos h0] constructor · rintro (h | h) · exact absurd (h ▸ h0) hr · exact Subtype.ext (by simp [h]) · intro h right have := congrArg Subtype.val h simp only at this rw [this, compl_compl] · rw [dif_neg h0] constructor · rintro (h | h) · exact Subtype.ext h.symm · exfalso apply h0 rw [h] exact Finset.mem_compl.mpr hr · intro h left exact (congrArg Subtype.val h).symm have hrepv : ∀ A, ((rep A).1 = A ∨ (rep A).1 = Aᶜ) := by intro A simp only [rep] split_ifs <;> simp let X0 : Matrix (Finset (Fin (k + 1))) T (MvPolynomial (Finset (Fin (k + 1))) ℚ) := Matrix.of fun A r => if A = r.1 ∨ A = r.1ᶜ then MvPolynomial.X A else 0 let Y0 : Matrix T (Finset (Fin (k + 1))) (MvPolynomial (Finset (Fin (k + 1))) ℚ) := Matrix.of fun r B => if B = r.1 ∨ B = r.1ᶜ then MvPolynomial.X B * hiltonPi (k + 1) r.1 else 0 refine ⟨X0.submatrix id e.symm, Y0.submatrix e.symm id, ?_⟩ rw [Matrix.submatrix_mul_equiv, Matrix.submatrix_id_id] have hs_split : ∀ A : Finset (Fin (k + 1)), hiltonS (k + 1) = MvPolynomial.X A * MvPolynomial.X Aᶜ * hiltonPi (k + 1) A := by intro A unfold hiltonS hiltonPi rw [← Finset.mul_prod_erase Finset.univ _ (Finset.mem_univ A), ← Finset.mul_prod_erase (Finset.univ.erase A) _ (Finset.mem_erase.mpr ⟨(hne A).symm, Finset.mem_univ _⟩)] ring refine Matrix.ext (fun A B => ?_) rw [Matrix.mul_apply] simp only [X0, Y0, Matrix.of_apply, ite_mul, zero_mul] simp only [hrep A] rw [Finset.sum_eq_single (rep A) (fun r _ hr => by rw [if_neg hr]) (by simp), if_pos rfl] have hPi_rep : hiltonPi (k + 1) (rep A).1 = hiltonPi (k + 1) A := by rcases hrepv A with h | h <;> rw [h] exact hilton_pi_compl _ A have hBorb : (B = (rep A).1 ∨ B = (rep A).1ᶜ) ↔ (B = A ∨ B = Aᶜ) := by rcases hrepv A with h | h <;> rw [h] rw [compl_compl, or_comm] rw [hPi_rep, if_congr hBorb rfl rfl] simp only [Matrix.add_apply, Matrix.smul_apply, Matrix.diagonal_apply, hiltonCompl, Matrix.of_apply, smul_eq_mul, hiltonQ] by_cases h1 : B = A · subst h1 have : B ≠ Bᶜ := hne B simp [this] ring · by_cases h2 : B = Aᶜ · subst h2 have : A ≠ Aᶜ := hne A simp [this, Ne.symm this, hs_split A] ring · have h3 : A ≠ Bᶜ := fun h => h2 (by rw [h, compl_compl]) simp [h1, h2, h3, Ne.symm h1]theorem hilton_lift {R : Type} [CommRing R] [IsDomain R] {n : ℕ} (L0 : Matrix (Finset (Fin n)) (Fin (2 ^ (n - 1))) R) (R0 : Matrix (Fin (2 ^ (n - 1))) (Finset (Fin n)) R) (hz : ∀ A B : Finset (Fin n), ¬ A ⊆ B → ¬ B ⊆ A → (L0 * R0) A B = 0) (hd : ∀ F : Finset (Finset (Fin n)), is_uncomplemented F → ((L0 * R0).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))).det ≠ 0) : ∃ (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 := by refine ⟨FractionRing R, inferInstance, L0.map (algebraMap R (FractionRing R)), R0.map (algebraMap R (FractionRing R)), ?_, ?_⟩ · intro A B h1 h2 rw [← Matrix.map_mul, Matrix.map_apply, hz A B h1 h2, map_zero] · intro F hF rw [← Matrix.map_mul] have : ((L0 * R0).map (algebraMap R (FractionRing R))).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n))) = (algebraMap R (FractionRing R)).mapMatrix ((L0 * R0).submatrix (fun x : F => (x : Finset (Fin n))) (fun x : F => (x : Finset (Fin n)))) := rfl rw [this, ← RingHom.map_det] exact (map_ne_zero_iff _ (IsFractionRing.injective R (FractionRing R))).mpr (hd F hF)/-- The matrix of Theorem 2.1: rank at most 2^(n-1) (as a product through 2^(n-1) dimensions), zero on incomparable pairs, nonsingular on every uncomplemented family. -/theorem hilton_strong_incomparability_matrix (n : ℕ) : ∃ (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 := by classical rcases n with _ | k · refine ⟨ℚ, inferInstance, 0, 0, fun A B h _ => absurd (Subsingleton.elim A B ▸ subset_refl A) h, fun F hF => ?_⟩ have hF0 : F = ∅ := by rw [Finset.eq_empty_iff_forall_notMem] intro A hA exact hF A hA (by rwa [Subsingleton.elim Aᶜ A]) have : IsEmpty F := Finset.isEmpty_coe_sort.mpr hF0 rw [Matrix.det_isEmpty] exact one_ne_zero · obtain ⟨X, Y, hXY⟩ := hilton_factor k have hLR : (hiltonMobius (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1) * X) * (Y * hiltonZeta (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1)) = hiltonMat (k + 1) := by rw [hiltonMat, Matrix.mul_assoc (hiltonMobius _ _) X, ← Matrix.mul_assoc X, hXY, ← Matrix.mul_assoc] refine hilton_lift (hiltonMobius (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1) * X) (Y * hiltonZeta (MvPolynomial (Finset (Fin (k + 1))) ℚ) (k + 1)) ?_ ?_ · intro A B h1 h2 rw [hLR, hiltonMat] exact hilton_mat_zero_of_incomparable _ _ A B h1 h2 · intro F hF rw [hLR] exact hilton_mat_det_ne F hF