AFTD Auto-Formalizing Theoretical Domains

op869_double_count

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

  1. 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).

    lines 6–7

      classical
      set deg : β → ℕ := fun u => (A.filter (fun x => u ∈ E x)).card with hdeg
  2. 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.

    lines 8–17

    uses Finset.sum_boole, Nat.cast_id, Finset.mem_filter, Finset.sum_congr, Finset.sum_comm

      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]
  3. |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)|.

    lines 18–20

    uses Finset.sum_const, smul_eq_mul, Finset.sum_le_sum

      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
  4. 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|.

    lines 21–26

    uses Finset.card_filter_le, Finset.sum_filter_add_sum_filter_not, Finset.sum_le_sum, Finset.sum_const, smul_eq_mul

      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]
  5. 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).

    lines 27–33

    uses Finset.sum_le_sum, Finset.mem_filter.mp, 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]
  6. |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.

    lines 34–37

    uses Finset.card_filter_add_card_filter_not

      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
  7. 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|.

    lines 38–44

    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
  8. 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|.

    lines 45–53

    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.

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

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]
See it in the graphDiscuss this resultChallenge it