unrestricted_partition_family_four_intersecting_and_card
For every natural number n ≥ 1, the family partition_A n of partitions of n is 1-intersecting (is_t_intersecting_partition_family 1 (partition_A n)), and its cardinality coerced to ℤ satisfies ((partition_A n).card : ℤ) = partition_number (n - 3 : ℤ) + partition_number (n - 4 : ℤ) + partition_number (n - 5 : ℤ) - partition_number (n - 6 : ℤ) - partition_number (n - 7 : ℤ) - partition_number (n - 8 : ℤ) + partition_number (n - 9 : ℤ).
Statement
theorem unrestricted_partition_family_four_intersecting_and_card (n : ℕ) (hn : 1 ≤ n) :
is_t_intersecting_partition_family 1 (partition_A n) ∧
((partition_A n).card : ℤ) =
partition_number (n - 3 : ℤ) + partition_number (n - 4 : ℤ) + partition_number (n - 5 : ℤ) -
partition_number (n - 6 : ℤ) - partition_number (n - 7 : ℤ) - partition_number (n - 8 : ℤ) +
partition_number (n - 9 : ℤ)- Formalizes
- arXiv:2610.01747 Proposition 6.1
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- partition_AThe family A_n of partitions of n consists of those partitions of n whose multiset of parts contains {1, 2}, {1, 3}, {1, 4}, or {2, 3, 4}.
- is_t_intersecting_partition_familyGiven natural numbers n and t, a finite set F of partitions of n (of type Finset (Nat.Partition n)) is t-intersecting if for every pair of…
- partition_A_is_one_intersectingFor every n, any two partitions in A_n share at least one common part, so A_n is 1-intersecting.
- partition_numberThe function partition_number maps an integer m : ℤ to an integer in ℤ: if 0 ≤ m, it returns the cardinality Nat.card of the type of…
Read back from the Lean
For any natural number $n \ge 1$:
1. The family of partitions $\text{partition\_A}(n)$ is $1$-intersecting: for any two partitions $p, q \in \text{partition\_A}(n)$, the multiset intersection of their parts has cardinality at least $1$ (i.e., they share at least one common part).
2. The number of partitions in $\text{partition\_A}(n)$ is equal to:
$$p(n - 3) + p(n - 4) + p(n - 5) - p(n - 6) - p(n - 7) - p(n - 8) + p(n - 9)$$
where $p(m)$ denotes the partition function (partition_number), which equals the number of partitions of $m$ if $m \ge 0$, and $0$ if $m < 0$.
Here, $\text{partition\_A}(n)$ is the set of all partitions of $n$ whose parts contain both $1$ and $2$, both $1$ and $3$, both $1$ and $4$, or all three of $2$, $3$, and $4$.
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
The theorem states that the partition family partition_A n is 1-intersecting and derives an alternating formula for its size in terms of partition numbers p(n - k). The 1-intersecting property is established by an earlier lemma. To count the family, its membership condition is formulated as a Boolean function on the presence of parts 1, 2, 3, and 4, which expands via inclusion-exclusion into indicators for specified pairs and triples. Removing those parts establishes a bijection with unrestricted partitions of n minus their sum, so each term contributes p(n - k).
The inclusion-exclusion algebraic identity holds for the 4-variable Boolean indicator automation
Reverting all four Boolean variables reduces the identity to a finite check over all 2⁴ = 16 truth assignments, which is discharged by exhaustive evaluation using decide.
revert x1 x2 x3 x4 decideMembership of partition p in partition_A n matches the Boolean formula (x₁ ∧ x₂) ∨ (x₁ ∧ x₃) ∨ (x₁ ∧ x₄) ∨ (x₂ ∧ x₃ ∧ x₄)
Unfolding the definition of partition_A n as a filter on the universe of partitions and translating Boolean conjunctions and disjunctions to propositional logic proves the equivalence.
uses
Bool.eq_iff_iff,decide_eq_true_iff,Finset.mem_filterintro x1 x2 x3 x4 rw [Bool.eq_iff_iff] rw [decide_eq_true_iff] rw [partition_A, Finset.mem_filter] simp only [mem_univ, true_and] dsimp [x1, x2, x3, x4] simp only [Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_iff] tauto
The sum over all partitions of the indicator of membership in a set s equals the cardinality of s
Rewriting the indicator b2z (decide (p ∈ s)) into an if-then-else expression allows applying Finset.sum_filter in reverse, expressing the sum as the count of elements in s.
uses
Finset.sum_filterhave h : ∀ p, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ s)) = if p ∈ s then (1 : ℤ) else 0 := by intro p simp [unrestricted_partition_family_four_intersecting_and_card_b2z] simp_rw [h] rw [← Finset.sum_filter] simp
If multiset s is a submultiset of t, then s.sum ≤ t.sum automation
Since s + (t - s) = t by submultiset difference, taking multiset sums shows t.sum = s.sum + (t - s).sum, and linear arithmetic over ℕ concludes s.sum ≤ t.sum.
uses
tsub_add_cancel_of_le,sum_addlemma unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le {s t : Multiset ℕ} (h : s ≤ t) : s.sum ≤ t.sum := by have : s + (t - s) = t := add_comm s (t - s) ▸ tsub_add_cancel_of_le h rw [← this, sum_add] omega
Partitions of n containing submultiset M are in bijection with partitions of n - M.sum
The bijection sends partition p to parts p.parts - M, and the inverse adds M to the parts. Both directions preserve positivity of parts and the sum invariant, and are two-sided inverses.
uses
Subtype.ext,Nat.Partition.ext,add_tsub_cancel_leftdef unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv {n : ℕ} (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) (hsum : M.sum ≤ n) : {p : Nat.Partition n // M ≤ p.parts} ≃ Nat.Partition (n - M.sum) where toFun p := ⟨p.1.parts - M, fun hx => p.1.parts_pos (mem_of_le tsub_le_self hx), by have hle := p.2 have hsum_eq : (p.1.parts - M).sum + M.sum = p.1.parts.sum := by rw [← sum_add, tsub_add_cancel_of_le hle] have hp := p.1.parts_sum omega⟩ invFun q := ⟨⟨M + q.parts, fun hx => by rcases mem_add.mp hx with h | h · exact hpos _ h · exact q.parts_pos h, by rw [sum_add, q.parts_sum] omega⟩, le_add_right _ _⟩ left_inv p := by apply Subtype.ext apply Nat.Partition.ext dsimp rw [add_comm] exact tsub_add_cancel_of_le p.2 right_inv q := by apply Nat.Partition.ext dsimp exact add_tsub_cancel_left _ _
The number of partitions of n containing submultiset M equals partition_number (n - M.sum) automation
If M.sum ≤ n, the bijection submultisetPartitionEquiv transfers cardinality to partitions of n - M.sum. If n < M.sum, any partition containing M would have parts summing to > n, so the subtype is empty and both sides are 0.
uses
partition_number,unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv,Nat.card_congr,Nat.card_eq_zerotheorem unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) : ((Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ)) = partition_number (n - (M.sum : ℤ)) := by rw [partition_number] split_ifs with h · have hle : M.sum ≤ n := by omega have htoNat : (n - (M.sum : ℤ)).toNat = n - M.sum := by omega rw [htoNat] have e := unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv M hpos hle rw [Nat.card_congr e] · have hlt : n < M.sum := by omega have h_empty : IsEmpty {p : Nat.Partition n // M ≤ p.parts} := by constructor intro ⟨p, hp⟩ have hsum := unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le hp have hp_sum := p.parts_sum omega have : Nat.card {p : Nat.Partition n // M ≤ p.parts} = 0 := Nat.card_eq_zero.mpr (Or.inl h_empty) rw [this, Nat.cast_zero]
The sum of indicators that M ≤ p.parts over all partitions of n equals partition_number (n - M.sum)
Converting the sum of indicators into the cardinality of the subtype {p // M ≤ p.parts} using Finset.sum_filter and card_partition_containing_multiset yields the result.
uses
Finset.sum_filter,Nat.card_eq_fintype_card,unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multisetlemma unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) : (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = partition_number (n - (M.sum : ℤ)) := by have h1 : (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = (Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ) := by rw [← Finset.sum_filter] simp only [sum_const, nsmul_eq_mul, mul_one] congr 1 rw [Nat.card_eq_fintype_card, Fintype.card_subtype] rw [h1, unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset n M hpos]
Two distinct elements both belong to multiset s if and only if the multiset {a, b} is a submultiset of s
Since a ≠ b, a is not in the multiset {b}, so cons_le_of_notMem decomposes {a, b} ≤ s into a ∈ s and b ∈ s.
uses
cons_le_of_notMemlemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two {a b : ℕ} (hab : a ≠ b) (s : Multiset ℕ) : (a ∈ s ∧ b ∈ s) ↔ (a ::ₘ b ::ₘ 0) ≤ s := by have h1 : a ∉ (b ::ₘ 0 : Multiset ℕ) := by simp [hab] have h2 : b ∉ (0 : Multiset ℕ) := by simp rw [cons_le_of_notMem h1, cons_le_of_notMem h2] simp [and_comm]
Three pairwise distinct elements all belong to multiset s if and only if {a, b, c} is a submultiset of s
Applying cons_le_of_notMem inductively three times, using the pairwise distinctness of a, b, c, reduces {a, b, c} ≤ s to the conjunction of memberships in s.
uses
cons_le_of_notMemlemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three {a b c : ℕ} (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (s : Multiset ℕ) : (a ∈ s ∧ b ∈ s ∧ c ∈ s) ↔ (a ::ₘ b ::ₘ c ::ₘ 0) ≤ s := by have h1 : a ∉ (b ::ₘ c ::ₘ 0 : Multiset ℕ) := by simp [hab, hac] have h2 : b ∉ (c ::ₘ 0 : Multiset ℕ) := by simp [hbc] have h3 : c ∉ (0 : Multiset ℕ) := by simp rw [cons_le_of_notMem h1, cons_le_of_notMem h2, cons_le_of_notMem h3] simp
All elements in the multiset {a, b} are strictly positive when a > 0 and b > 0
Any element in {a, b} is either a or b, both of which are positive by hypothesis.
uses
Multiset.mem_conslemma unrestricted_partition_family_four_intersecting_and_card_hpos_two {a b : ℕ} (ha : 0 < a) (hb : 0 < b) : ∀ x ∈ (a ::ₘ b ::ₘ 0 : Multiset ℕ), 0 < x := by intro x hx simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx rcases hx with rfl | rfl <;> assumption
All elements in the multiset {a, b, c} are strictly positive when a, b, c > 0
Any element in {a, b, c} is a, b, or c, all of which are positive by hypothesis.
uses
Multiset.mem_conslemma unrestricted_partition_family_four_intersecting_and_card_hpos_three {a b c : ℕ} (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) : ∀ x ∈ (a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ), 0 < x := by intro x hx simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx rcases hx with rfl | rfl | rfl <;> assumption
The sum over partitions of the indicator that both a and b are parts equals partition_number (n - (a + b))
The conjunction a ∈ p.parts ∧ b ∈ p.parts is equivalent to {a, b} ≤ p.parts, which by sum_if_submultiset_eq sums to partition_number (n - (a + b)).
uses
if_congr,unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two,unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq,unrestricted_partition_family_four_intersecting_and_card_hpos_twolemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two (n : ℕ) (a b : ℕ) (hab : a ≠ b) (ha : 0 < a) (hb : 0 < b) : (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts))) = partition_number (n - ((a ::ₘ b ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts)) = if (a ::ₘ b ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by intro p simp only [unrestricted_partition_family_four_intersecting_and_card_b2z] apply if_congr _ rfl rfl rw [Bool.and_eq_true, decide_eq_true_iff, decide_eq_true_iff] exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two hab p.parts simp_rw [h] exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_two ha hb)
The sum over partitions of the indicator that a, b, c are parts equals partition_number (n - (a + b + c))
The conjunction a ∈ p.parts ∧ b ∈ p.parts ∧ c ∈ p.parts is equivalent to {a, b, c} ≤ p.parts, which sums to partition_number (n - (a + b + c)).
uses
if_congr,unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three,unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq,unrestricted_partition_family_four_intersecting_and_card_hpos_threelemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three (n : ℕ) (a b c : ℕ) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) : (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts))) = partition_number (n - ((a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts)) = if (a ::ₘ b ::ₘ c ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by intro p simp only [unrestricted_partition_family_four_intersecting_and_card_b2z] apply if_congr _ rfl rfl simp only [Bool.and_eq_true, decide_eq_true_iff, and_assoc] exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three hab hac hbc p.parts simp_rw [h] exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ c ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_three ha hb hc)
The partition family partition_A n is 1-intersecting, reducing the theorem to the cardinality formula
The 1-intersecting property is supplied by partition_A_is_one_intersecting n, leaving only the evaluation of the cardinality.
uses
partition_A_is_one_intersectingrefine ⟨partition_A_is_one_intersecting n, ?_⟩The cardinality of partition_A n equals the sum over all partitions of the indicator of membership in partition_A n
Applying unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem in reverse expresses the cardinality as the total sum of the indicators.
uses
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_memhave h_card := (unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem n (partition_A n)).symm rw [h_card]
The indicator of p ∈ partition_A n expands into an alternating sum of pair and triple indicators
For each partition p, the membership indicator is rewritten into the 4-variable Boolean condition via decide_mem_partition_A, which is expanded by bool_pie into the inclusion-exclusion sum of pair and triple indicators.
uses
unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A,unrestricted_partition_family_four_intersecting_and_card_bool_piehave h_eq : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ partition_A n)) = unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts)) + unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts)) + unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (4 ∈ p.parts)) - unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (3 ∈ p.parts)) - unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (4 ∈ p.parts)) - unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) + unrestricted_partition_family_four_intersecting_and_card_b2z (decide (2 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) := by intro p rw [unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A] exact unrestricted_partition_family_four_intersecting_and_card_bool_pie _ _ _ _ simp_rw [h_eq]
The summation distributes over additions and subtractions of indicator terms
Distributing the sum over each term splits the expression into seven separate sums of indicators of pairs and triples of parts.
uses
Finset.sum_add_distrib,Finset.sum_sub_distribsimp only [Finset.sum_add_distrib, Finset.sum_sub_distrib]The multiset sums of the relevant pairs and triples equal 3, 4, 5, 6, 7, 8, and 9
The sums of multisets {1, 2}, {1, 3}, {1, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4} are computed by reflexivity.
have s12 : ((1 ::ₘ 2 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 3 := by rfl have s13 : ((1 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 4 := by rfl have s14 : ((1 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 5 := by rfl have s123 : ((1 ::ₘ 2 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 6 := by rfl have s124 : ((1 ::ₘ 2 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 7 := by rfl have s134 : ((1 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 8 := by rfl have s234 : ((2 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 9 := by rfl
Each indicator sum evaluates to the corresponding partition number, completing the cardinality formula automation
Using sum_b2z_two and sum_b2z_three, each sum of pair or triple indicators becomes partition_number (n - sum), with side conditions on distinctness and positivity resolved by decide. Substituting the precomputed sums yields the final alternating sum.
uses
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two,unrestricted_partition_family_four_intersecting_and_card_sum_b2z_threerw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 2 (by decide) (by decide) (by decide), s12] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 3 (by decide) (by decide) (by decide), s13] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 4 (by decide) (by decide) (by decide), s14] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 3 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s123] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s124] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s134] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 2 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s234]
Bool.eq_iff_iff- Two Booleans are equal if and only if their truth values are logically equivalent
decide_eq_true_iff- For any decidable proposition p, decide p = true is equivalent to p holding
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies p
Finset.sum_filter- Summing a function over a filtered set Finset.filter p s equals summing the if-then-else indicator over s
tsub_add_cancel_of_le- For natural numbers or in an ordered additive semigroup with subtraction, if a ≤ b then b - a + a = b
sum_add- The sum of elements in a sum of multisets s + t is s.sum + t.sum
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal
Nat.Partition.ext- Two partitions of n are equal if their multisets of parts are equal
add_tsub_cancel_left- In an ordered subtractive structure, a + b - a = b
partition_number- The partition function p(m): defined as the number of partitions of m if m ≥ 0, and 0 if m < 0
unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv- Partitions of n whose parts contain multiset M are in bijection with partitions of n - M.sum, provided M has positive elements and M.sum ≤ n
Nat.card_congr- An equivalence between types preserves their cardinalities
Nat.card_eq_zero- The cardinality of a type is 0 if and only if the type is empty (or infinite)
Nat.card_eq_fintype_card- For a finite type α, Nat.card α equals Fintype.card α
unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset- The number of partitions of n containing a given submultiset M of positive parts equals partition_number (n - M.sum)
cons_le_of_notMem- If an element a is not in multiset s, then a ::ₘ s ≤ t if and only if a ∈ t and s ≤ t
Multiset.mem_cons- An element x is in the multiset a ::ₘ s if and only if x = a or x ∈ s
if_congr- If propositions P and Q are equivalent, then the conditional expressions with condition P and Q are equal
unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two- For distinct positive integers a ≠ b, both a and b belong to multiset s if and only if {a, b} ≤ s
unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq- The sum over all partitions p of n of the indicator that M ≤ p.parts equals partition_number (n - M.sum)
unrestricted_partition_family_four_intersecting_and_card_hpos_two- Every element of the multiset {a, b} is strictly positive when a > 0 and b > 0
unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three- For pairwise distinct integers a, b, c, all three belong to multiset s if and only if {a, b, c} ≤ s
unrestricted_partition_family_four_intersecting_and_card_hpos_three- Every element of the multiset {a, b, c} is strictly positive when a, b, c > 0
partition_A_is_one_intersecting- The partition family partition_A n is 1-intersecting
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem- The sum of the indicator values of membership in a finite set s of partitions equals the cardinality of s coerced to ℤ
unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A- Membership of a partition p in partition_A n is logically equivalent to the Boolean formula on parts 1, 2, 3, 4
unrestricted_partition_family_four_intersecting_and_card_bool_pie- The inclusion-exclusion expansion of the indicator of the 4-variable Boolean formula defining partition_A n
Finset.sum_add_distrib- The sum of a sum distributes: ∑ x, (f x + g x) = ∑ x, f x + ∑ x, g x
Finset.sum_sub_distrib- The sum of a difference distributes: ∑ x, (f x - g x) = ∑ x, f x - ∑ x, g x
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two- The sum over partitions of the indicator that distinct positive integers a and b are parts equals partition_number (n - (a + b))
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three- The sum over partitions of the indicator that pairwise distinct positive integers a, b, c are parts equals partition_number (n - (a + b + c))
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.
open Multiset Finsetdef unrestricted_partition_family_four_intersecting_and_card_b2z (b : Bool) : ℤ := if b then 1 else 0lemma unrestricted_partition_family_four_intersecting_and_card_bool_pie (x1 x2 x3 x4 : Bool) : unrestricted_partition_family_four_intersecting_and_card_b2z ((x1 && x2) || (x1 && x3) || (x1 && x4) || (x2 && x3 && x4)) = unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x2) + unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x3) + unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x4) - unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x2 && x3) - unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x2 && x4) - unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x3 && x4) + unrestricted_partition_family_four_intersecting_and_card_b2z (x2 && x3 && x4) := by revert x1 x2 x3 x4 decidelemma unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A (n : ℕ) (p : Nat.Partition n) : let x1 := decide (1 ∈ p.parts) let x2 := decide (2 ∈ p.parts) let x3 := decide (3 ∈ p.parts) let x4 := decide (4 ∈ p.parts) decide (p ∈ partition_A n) = ((x1 && x2) || (x1 && x3) || (x1 && x4) || (x2 && x3 && x4)) := by intro x1 x2 x3 x4 rw [Bool.eq_iff_iff] rw [decide_eq_true_iff] rw [partition_A, Finset.mem_filter] simp only [mem_univ, true_and] dsimp [x1, x2, x3, x4] simp only [Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_iff] tautolemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem (n : ℕ) (s : Finset (Nat.Partition n)) : ∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ s)) = (s.card : ℤ) := by have h : ∀ p, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ s)) = if p ∈ s then (1 : ℤ) else 0 := by intro p simp [unrestricted_partition_family_four_intersecting_and_card_b2z] simp_rw [h] rw [← Finset.sum_filter] simplemma unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le {s t : Multiset ℕ} (h : s ≤ t) : s.sum ≤ t.sum := by have : s + (t - s) = t := add_comm s (t - s) ▸ tsub_add_cancel_of_le h rw [← this, sum_add] omegadef unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv {n : ℕ} (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) (hsum : M.sum ≤ n) : {p : Nat.Partition n // M ≤ p.parts} ≃ Nat.Partition (n - M.sum) where toFun p := ⟨p.1.parts - M, fun hx => p.1.parts_pos (mem_of_le tsub_le_self hx), by have hle := p.2 have hsum_eq : (p.1.parts - M).sum + M.sum = p.1.parts.sum := by rw [← sum_add, tsub_add_cancel_of_le hle] have hp := p.1.parts_sum omega⟩ invFun q := ⟨⟨M + q.parts, fun hx => by rcases mem_add.mp hx with h | h · exact hpos _ h · exact q.parts_pos h, by rw [sum_add, q.parts_sum] omega⟩, le_add_right _ _⟩ left_inv p := by apply Subtype.ext apply Nat.Partition.ext dsimp rw [add_comm] exact tsub_add_cancel_of_le p.2 right_inv q := by apply Nat.Partition.ext dsimp exact add_tsub_cancel_left _ _theorem unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) : ((Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ)) = partition_number (n - (M.sum : ℤ)) := by rw [partition_number] split_ifs with h · have hle : M.sum ≤ n := by omega have htoNat : (n - (M.sum : ℤ)).toNat = n - M.sum := by omega rw [htoNat] have e := unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv M hpos hle rw [Nat.card_congr e] · have hlt : n < M.sum := by omega have h_empty : IsEmpty {p : Nat.Partition n // M ≤ p.parts} := by constructor intro ⟨p, hp⟩ have hsum := unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le hp have hp_sum := p.parts_sum omega have : Nat.card {p : Nat.Partition n // M ≤ p.parts} = 0 := Nat.card_eq_zero.mpr (Or.inl h_empty) rw [this, Nat.cast_zero]lemma unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) : (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = partition_number (n - (M.sum : ℤ)) := by have h1 : (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = (Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ) := by rw [← Finset.sum_filter] simp only [sum_const, nsmul_eq_mul, mul_one] congr 1 rw [Nat.card_eq_fintype_card, Fintype.card_subtype] rw [h1, unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset n M hpos]lemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two {a b : ℕ} (hab : a ≠ b) (s : Multiset ℕ) : (a ∈ s ∧ b ∈ s) ↔ (a ::ₘ b ::ₘ 0) ≤ s := by have h1 : a ∉ (b ::ₘ 0 : Multiset ℕ) := by simp [hab] have h2 : b ∉ (0 : Multiset ℕ) := by simp rw [cons_le_of_notMem h1, cons_le_of_notMem h2] simp [and_comm]lemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three {a b c : ℕ} (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (s : Multiset ℕ) : (a ∈ s ∧ b ∈ s ∧ c ∈ s) ↔ (a ::ₘ b ::ₘ c ::ₘ 0) ≤ s := by have h1 : a ∉ (b ::ₘ c ::ₘ 0 : Multiset ℕ) := by simp [hab, hac] have h2 : b ∉ (c ::ₘ 0 : Multiset ℕ) := by simp [hbc] have h3 : c ∉ (0 : Multiset ℕ) := by simp rw [cons_le_of_notMem h1, cons_le_of_notMem h2, cons_le_of_notMem h3] simplemma unrestricted_partition_family_four_intersecting_and_card_hpos_two {a b : ℕ} (ha : 0 < a) (hb : 0 < b) : ∀ x ∈ (a ::ₘ b ::ₘ 0 : Multiset ℕ), 0 < x := by intro x hx simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx rcases hx with rfl | rfl <;> assumptionlemma unrestricted_partition_family_four_intersecting_and_card_hpos_three {a b c : ℕ} (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) : ∀ x ∈ (a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ), 0 < x := by intro x hx simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx rcases hx with rfl | rfl | rfl <;> assumptionlemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two (n : ℕ) (a b : ℕ) (hab : a ≠ b) (ha : 0 < a) (hb : 0 < b) : (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts))) = partition_number (n - ((a ::ₘ b ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts)) = if (a ::ₘ b ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by intro p simp only [unrestricted_partition_family_four_intersecting_and_card_b2z] apply if_congr _ rfl rfl rw [Bool.and_eq_true, decide_eq_true_iff, decide_eq_true_iff] exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two hab p.parts simp_rw [h] exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_two ha hb)lemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three (n : ℕ) (a b c : ℕ) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) : (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts))) = partition_number (n - ((a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts)) = if (a ::ₘ b ::ₘ c ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by intro p simp only [unrestricted_partition_family_four_intersecting_and_card_b2z] apply if_congr _ rfl rfl simp only [Bool.and_eq_true, decide_eq_true_iff, and_assoc] exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three hab hac hbc p.parts simp_rw [h] exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ c ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_three ha hb hc)/-- Proposition 6.1 (arXiv:2610.01747): A_n is 1-intersecting and its cardinality satisfies the alternating sum formula in terms of p(n-k). -/theorem unrestricted_partition_family_four_intersecting_and_card (n : ℕ) (hn : 1 ≤ n) : is_t_intersecting_partition_family 1 (partition_A n) ∧ ((partition_A n).card : ℤ) = partition_number (n - 3 : ℤ) + partition_number (n - 4 : ℤ) + partition_number (n - 5 : ℤ) - partition_number (n - 6 : ℤ) - partition_number (n - 7 : ℤ) - partition_number (n - 8 : ℤ) + partition_number (n - 9 : ℤ) := by refine ⟨partition_A_is_one_intersecting n, ?_⟩ have h_card := (unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem n (partition_A n)).symm rw [h_card] have h_eq : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ partition_A n)) = unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts)) + unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts)) + unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (4 ∈ p.parts)) - unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (3 ∈ p.parts)) - unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (4 ∈ p.parts)) - unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) + unrestricted_partition_family_four_intersecting_and_card_b2z (decide (2 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) := by intro p rw [unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A] exact unrestricted_partition_family_four_intersecting_and_card_bool_pie _ _ _ _ simp_rw [h_eq] simp only [Finset.sum_add_distrib, Finset.sum_sub_distrib] have s12 : ((1 ::ₘ 2 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 3 := by rfl have s13 : ((1 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 4 := by rfl have s14 : ((1 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 5 := by rfl have s123 : ((1 ::ₘ 2 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 6 := by rfl have s124 : ((1 ::ₘ 2 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 7 := by rfl have s134 : ((1 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 8 := by rfl have s234 : ((2 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 9 := by rfl rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 2 (by decide) (by decide) (by decide), s12] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 3 (by decide) (by decide) (by decide), s13] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 4 (by decide) (by decide) (by decide), s14] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 3 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s123] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s124] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s134] rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 2 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s234]