op869_double_count
Double counting in a bipartite incidence: if every element x of A meets at least d elements of B, then for i ≤ |A|, |A|·d ≤ |B|·(i-1) + (|A|-i+1)·(number of elements of B lying in at least i of the sets).
Statement
theorem op869_double_count {α β : Type} [DecidableEq β] (A : Finset α) (B : Finset β) (E : α → Finset β) (d i : ℕ) (hE : ∀ x ∈ A, E x ⊆ B) (hd : ∀ x ∈ A, d ≤ (E x).card) (hi : i ≤ A.card) : A.card * d ≤ B.card * (i - 1) + (A.card - i + 1) * (B.filter (fun u => i ≤ (A.filter (fun x => u ∈ E x)).card)).card
- Source
- arXiv:2610.41516, Lemma 2.2
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- op869_many_shared_colorsIf |B| < |A| and every element of A meets at least d elements of B, then at least d elements of B lie in at least two of the sets.
The proof, explained
The proof double counts the edges of the bipartite incidence between A and B, establishing that ∑_{x ∈ A} |E(x)| = ∑_{u ∈ B} deg(u). Since each vertex in A meets at least d elements of B, the total number of edges is at least |A| · d. Partitioning B into vertices of degree at least i (the set H) and those of lower degree bounds the sum of degrees by |H| · |A| + (|B| - |H|) · (i - 1). Rearranging this bound algebraically completes the proof for both i = 0 and i > 0.
Define the degree function deg(u) on B.
Enable classical logic and define the degree deg(u) of any element u ∈ B as the number of elements x ∈ A such that u ∈ E(x).
classical set deg : β → ℕ := fun u => (A.filter (fun x => u ∈ E x)).card with hdeg
The sum of the sizes of E(x) over x ∈ A equals the sum of the degrees deg(u) over u ∈ B.
Since E(x) ⊆ B for each x ∈ A, the cardinality |E(x)| can be written as the sum of indicator variables ∑_{u ∈ B} (if u ∈ E(x) then 1 else 0). Exchanging the order of summation gives ∑_{u ∈ B} ∑_{x ∈ A} (if u ∈ E(x) then 1 else 0), which equals ∑_{u ∈ B} deg(u) by the definition of deg.
uses
Finset.sum_boole,Nat.cast_id,Finset.mem_filter,Finset.sum_congr,Finset.sum_commhave hsum : ∑ x ∈ A, (E x).card = ∑ u ∈ B, deg u := by have h1 : ∀ x ∈ A, (E x).card = ∑ u ∈ B, if u ∈ E x then 1 else 0 := by intro x hx rw [Finset.sum_boole, Nat.cast_id] congr 1 ext u; simp only [Finset.mem_filter] exact ⟨fun h => ⟨hE x hx h, h⟩, fun h => h.2⟩ rw [Finset.sum_congr rfl h1, Finset.sum_comm] refine Finset.sum_congr rfl fun u _ => ?_ rw [Finset.sum_boole, Nat.cast_id]
|A| · d ≤ ∑_{x ∈ A} |E(x)|.
Each element x ∈ A satisfies d ≤ |E(x)| by assumption. Summing this lower bound over all |A| elements gives |A| · d ≤ ∑_{x ∈ A} |E(x)|.
uses
Finset.sum_const,smul_eq_mul,Finset.sum_le_sumhave hlow : A.card * d ≤ ∑ x ∈ A, (E x).card := by calc A.card * d = ∑ _x ∈ A, d := by rw [Finset.sum_const, smul_eq_mul] _ ≤ _ := Finset.sum_le_sum hd
The sum of degrees over the high-degree vertices H = {u ∈ B | deg(u) ≥ i} is at most |H| · |A|.
For every u ∈ B, deg(u) ≤ |A| because deg(u) counts a subset of A. Decomposing the sum over B into vertices with degree at least i (the set H) and those with degree strictly less than i, each vertex in H contributes at most |A|, yielding ∑_{u ∈ H} deg(u) ≤ |H| · |A|.
uses
Finset.card_filter_le,Finset.sum_filter_add_sum_filter_not,Finset.sum_le_sum,Finset.sum_const,smul_eq_mulhave hdegle : ∀ u, deg u ≤ A.card := fun u => Finset.card_filter_le _ _ set H := B.filter (fun u => i ≤ deg u) with hH have hsplit := Finset.sum_filter_add_sum_filter_not B (fun u => i ≤ deg u) deg have hhigh : ∑ u ∈ B.filter (fun u => i ≤ deg u), deg u ≤ H.card * A.card := by calc _ ≤ ∑ _u ∈ H, A.card := Finset.sum_le_sum fun u _ => hdegle u _ = H.card * A.card := by rw [Finset.sum_const, smul_eq_mul]
The sum of degrees over the low-degree vertices in B \ H is at most |B \ H| · (i - 1).
Any vertex u ∈ B not in H satisfies ¬(i ≤ deg(u)), which means deg(u) ≤ i - 1 in natural arithmetic. Summing this upper bound over all vertices in B \ H yields ∑_{u ∈ B \ H} deg(u) ≤ |B \ H| · (i - 1).
uses
Finset.sum_le_sum,Finset.mem_filter.mp,Finset.sum_const,smul_eq_mulhave hlo : ∑ u ∈ B.filter (fun u => ¬ i ≤ deg u), deg u ≤ (B.filter (fun u => ¬ i ≤ deg u)).card * (i - 1) := by calc _ ≤ ∑ _u ∈ B.filter (fun u => ¬ i ≤ deg u), (i - 1) := Finset.sum_le_sum fun u hu => by have := (Finset.mem_filter.mp hu).2 omega _ = _ := by rw [Finset.sum_const, smul_eq_mul]
|A| · d ≤ |H| · |A| + |B \ H| · (i - 1).
Because H and B \ H partition B, the total sum of degrees equals the sum of the two partial sums. Combining the lower bound |A| · d ≤ ∑_{u ∈ B} deg(u) with the upper bounds on both parts yields the inequality by linear arithmetic.
uses
Finset.card_filter_add_card_filter_nothave hcardsplit : H.card + (B.filter (fun u => ¬ i ≤ deg u)).card = B.card := Finset.card_filter_add_card_filter_not _ have key : A.card * d ≤ H.card * A.card + (B.filter (fun u => ¬ i ≤ deg u)).card * (i - 1) := by omega
The desired inequality holds in the base case i = 0.
Observe that |H| ≤ |B|. When i = 0, truncated subtraction in ℕ yields i - 1 = 0, so |B| · (i - 1) = 0 and |A| - i + 1 = |A| + 1. The key inequality simplifies to |A| · d ≤ |H| · |A|, which is bounded above by (|A| + 1) · |H|.
uses
Finset.card_filter_le,Nat.eq_zero_or_pos,Nat.zero_sub,mul_zero,zero_add,Nat.sub_zero-- H.card * A.card + (B - H) * (i-1) = B*(i-1) + H*(A - (i-1)) have hHle : H.card ≤ B.card := Finset.card_filter_le _ _ rcases Nat.eq_zero_or_pos i with h0 | hpos · subst h0 simp only [Nat.zero_sub, mul_zero, zero_add, Nat.sub_zero] at key ⊢ calc A.card * d ≤ H.card * A.card := by simpa using key _ ≤ (A.card + 1) * H.card := by nlinarith
The desired inequality holds when i > 0.
When i > 0, we have |A| - i + 1 = |A| - (i - 1) and |B \ H| = |B| - |H|. Using the algebraic identities (|B| - |H|)(i - 1) + |H|(i - 1) = |B|(i - 1) and (|A| - (i - 1))|H| + (i - 1)|H| = |A||H|, non-linear arithmetic rewrites the upper bound |H| · |A| + (|B| - |H|)(i - 1) into the required form |B|(i - 1) + (|A| - i + 1)|H|.
uses
add_mul,Nat.sub_add_cancel· have hrw : A.card - i + 1 = A.card - (i - 1) := by omega rw [hrw] have hBH : (B.filter (fun u => ¬ i ≤ deg u)).card = B.card - H.card := by omega rw [hBH] at key have e1 : (B.card - H.card) * (i - 1) + H.card * (i - 1) = B.card * (i - 1) := by rw [← add_mul, Nat.sub_add_cancel hHle] have e2 : (A.card - (i - 1)) * H.card + (i - 1) * H.card = A.card * H.card := by rw [← add_mul, Nat.sub_add_cancel (by omega)] nlinarith [e1, e2]
Finset.sum_boole- The sum over a finite set of the indicator of a predicate equals the cardinality of the filtered subset (cast into the target ring).
Nat.cast_id- The canonical cast from ℕ to ℕ is the identity function.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.sum_congr- If two finite sets are equal and two functions agree on the set, their sums over the set are equal.
Finset.sum_comm- Summation over a product of two finite sets is commutative (the order of two summations can be swapped).
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set scalar-multiplied by the constant.
smul_eq_mul- Scalar multiplication in a multiplicative structure equals standard multiplication.
Finset.sum_le_sum- If f(x) ≤ g(x) for every element x in a finite set, then ∑ f(x) ≤ ∑ g(x).
Finset.card_filter_le- The cardinality of a filtered subset is at most the cardinality of the original finite set.
Finset.sum_filter_add_sum_filter_not- The sum of a function over elements satisfying a predicate plus the sum over elements not satisfying it equals the sum over the entire finite set.
Finset.mem_filter.mp- If an element belongs to a filtered set, it belongs to the base set and satisfies the filtering predicate.
Finset.card_filter_add_card_filter_not- The size of the subset satisfying a predicate plus the size of the subset not satisfying it equals the size of the original set.
Nat.eq_zero_or_pos- Every natural number is either equal to 0 or strictly positive.
Nat.zero_sub- Subtracting any natural number from zero yields zero in truncated natural arithmetic (0 - n = 0).
mul_zero- Multiplying any element by zero on the right gives zero (a * 0 = 0).
zero_add- Adding zero to an element on the left leaves it unchanged (0 + a = a).
Nat.sub_zero- Subtracting zero from a natural number leaves it unchanged (n - 0 = n).
add_mul- Multiplication distributes over addition on the right: (a + b) * c = a * c + b * c.
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
- In natural number arithmetic (ℕ), subtraction is truncated at zero, so 0 - 1 = 0; this simplifies the base case i = 0.
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.
theorem op869_double_count {α β : Type} [DecidableEq β] (A : Finset α) (B : Finset β) (E : α → Finset β) (d i : ℕ) (hE : ∀ x ∈ A, E x ⊆ B) (hd : ∀ x ∈ A, d ≤ (E x).card) (hi : i ≤ A.card) : A.card * d ≤ B.card * (i - 1) + (A.card - i + 1) * (B.filter (fun u => i ≤ (A.filter (fun x => u ∈ E x)).card)).card := by classical set deg : β → ℕ := fun u => (A.filter (fun x => u ∈ E x)).card with hdeg have hsum : ∑ x ∈ A, (E x).card = ∑ u ∈ B, deg u := by have h1 : ∀ x ∈ A, (E x).card = ∑ u ∈ B, if u ∈ E x then 1 else 0 := by intro x hx rw [Finset.sum_boole, Nat.cast_id] congr 1 ext u; simp only [Finset.mem_filter] exact ⟨fun h => ⟨hE x hx h, h⟩, fun h => h.2⟩ rw [Finset.sum_congr rfl h1, Finset.sum_comm] refine Finset.sum_congr rfl fun u _ => ?_ rw [Finset.sum_boole, Nat.cast_id] have hlow : A.card * d ≤ ∑ x ∈ A, (E x).card := by calc A.card * d = ∑ _x ∈ A, d := by rw [Finset.sum_const, smul_eq_mul] _ ≤ _ := Finset.sum_le_sum hd have hdegle : ∀ u, deg u ≤ A.card := fun u => Finset.card_filter_le _ _ set H := B.filter (fun u => i ≤ deg u) with hH have hsplit := Finset.sum_filter_add_sum_filter_not B (fun u => i ≤ deg u) deg have hhigh : ∑ u ∈ B.filter (fun u => i ≤ deg u), deg u ≤ H.card * A.card := by calc _ ≤ ∑ _u ∈ H, A.card := Finset.sum_le_sum fun u _ => hdegle u _ = H.card * A.card := by rw [Finset.sum_const, smul_eq_mul] have hlo : ∑ u ∈ B.filter (fun u => ¬ i ≤ deg u), deg u ≤ (B.filter (fun u => ¬ i ≤ deg u)).card * (i - 1) := by calc _ ≤ ∑ _u ∈ B.filter (fun u => ¬ i ≤ deg u), (i - 1) := Finset.sum_le_sum fun u hu => by have := (Finset.mem_filter.mp hu).2 omega _ = _ := by rw [Finset.sum_const, smul_eq_mul] have hcardsplit : H.card + (B.filter (fun u => ¬ i ≤ deg u)).card = B.card := Finset.card_filter_add_card_filter_not _ have key : A.card * d ≤ H.card * A.card + (B.filter (fun u => ¬ i ≤ deg u)).card * (i - 1) := by omega -- H.card * A.card + (B - H) * (i-1) = B*(i-1) + H*(A - (i-1)) have hHle : H.card ≤ B.card := Finset.card_filter_le _ _ rcases Nat.eq_zero_or_pos i with h0 | hpos · subst h0 simp only [Nat.zero_sub, mul_zero, zero_add, Nat.sub_zero] at key ⊢ calc A.card * d ≤ H.card * A.card := by simpa using key _ ≤ (A.card + 1) * H.card := by nlinarith · have hrw : A.card - i + 1 = A.card - (i - 1) := by omega rw [hrw] have hBH : (B.filter (fun u => ¬ i ≤ deg u)).card = B.card - H.card := by omega rw [hBH] at key have e1 : (B.card - H.card) * (i - 1) + H.card * (i - 1) = B.card * (i - 1) := by rw [← add_mul, Nat.sub_add_cancel hHle] have e2 : (A.card - (i - 1)) * H.card + (i - 1) * H.card = A.card * H.card := by rw [← add_mul, Nat.sub_add_cancel (by omega)] nlinarith [e1, e2]