biclique_exact_forward_pairs_sum
If bicliques own every forward pair at distance d exactly once on Fin g, the sum of their numbers of such pairs is g-d.
Statement
theorem biclique_exact_forward_pairs_sum {R : Type*} [Fintype R] (g d : ℕ) (hd : d ≤ g) (A B : R → Finset (Fin g)) (hunique : ∀ i j : Fin g, j.val+d = i.val → ∃! r, i ∈ A r ∧ j ∈ B r) : (∑ r, (((A r).product (B r)).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val)).card) = g-d
- Source
- Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- fin_forward_pairs_cardFor d at most g, the number of ordered pairs of elements of Fin g whose first value is the second value plus d is g-d.
- Used by 1
- ordered_biclique_dyadic_tree_incidenceFor g at least 2^(m-1), m positive, a family of g-1 disjoint-sided bicliques whose side sizes equal one plus their dyadic pair counts and…
The proof, explained
We partition the set S of all pairs (i, j) in Fin g × Fin g at forward distance d (satisfying j + d = i) into the subsets C(r) = (A(r) × B(r)) ∩ S covered by each biclique r. By the hypothesis that every such forward pair is covered by a uniquely determined biclique, the sets C(r) are pairwise disjoint and their union is S. Consequently, the sum of their cardinalities equals the cardinality of S, which evaluates to g - d by fin_forward_pairs_card.
Define the sets C(r) of forward pairs at distance d in biclique r and S of all forward pairs at distance d in Fin g × Fin g.
We enable classical logic and define C(r) for each biclique index r as the set of pairs (i, j) in A(r) × B(r) satisfying the forward distance condition j + d = i. We likewise define S as the set of all pairs in Fin g × Fin g satisfying j + d = i.
classical let C : R → Finset (Fin g × Fin g) := fun r => ((A r).product (B r)).filter (fun p => p.2.val+d = p.1.val) let S := ((univ : Finset (Fin g)).product univ).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val)
The sets C(r) are pairwise disjoint for distinct biclique indices r ≠ s.
To show that C(r) and C(s) are disjoint when r ≠ s, suppose for contradiction that some pair p = (i, j) belongs to both sets. Then p satisfies j + d = i with (i, j) in A(r) × B(r) and in A(s) × B(s). By the uniqueness hypothesis hunique, there is a unique index t such that i ∈ A(t) and j ∈ B(t), which implies r = s, contradicting r ≠ s.
uses
disjoint_left.mprhave hdis : (↑(univ : Finset R) : Set R).PairwiseDisjoint C := by intro r hr s hs hrs apply disjoint_left.mpr intro p hpr hps have hrd := (mem_filter.mp hpr).2 have hri := (mem_product.mp (mem_filter.mp hpr).1) have hsi := (mem_product.mp (mem_filter.mp hps).1) obtain ⟨t, ht, huniq⟩ := hunique p.1 p.2 hrd exact hrs ((huniq r hri).trans (huniq s hsi).symm)
The union of all C(r) over r ∈ R equals S.
We establish the set equality ⋃ r, C(r) = S by double inclusion. If a pair p belongs to C(r) for some r, its coordinates satisfy the distance condition and are in Fin g, so p ∈ S. Conversely, if p = (i, j) ∈ S, it satisfies j + d = i, so by hunique there is some biclique r containing it, meaning p ∈ C(r) and thus p belongs to the union.
uses
mem_univhave hcover : univ.biUnion C = S := by ext p constructor · intro hp obtain ⟨r, hr, hpr⟩ := mem_biUnion.mp hp exact mem_filter.mpr ⟨mem_product.mpr ⟨mem_univ _, mem_univ _⟩, (mem_filter.mp hpr).2⟩ · intro hp have hdist := (mem_filter.mp hp).2 obtain ⟨r, hr, huniq⟩ := hunique p.1 p.2 hdist exact mem_biUnion.mpr ⟨r, mem_univ _, mem_filter.mpr ⟨mem_product.mpr hr, hdist⟩⟩
The sum of the cardinalities of the sets C(r) equals g - d.
By rewriting the sum of the cardinalities of the pairwise disjoint sets C(r) into the cardinality of their union ⋃ r, C(r) = S via card_biUnion, the goal reduces to the cardinality of S. Finally, fin_forward_pairs_card proves that the number of forward pairs at distance d in Fin g is g - d.
uses
card_biUnion,fin_forward_pairs_cardchange (∑ r, (C r).card) = g-d rw [← card_biUnion hdis, hcover] exact fin_forward_pairs_card g d hd
disjoint_left.mpr- Two finite sets are disjoint if no element belongs to both sets.
mem_univ- Every element of a finite type belongs to the universal finite set univ.
card_biUnion- The cardinality of a disjoint union of finite sets is the sum of their individual cardinalities.
fin_forward_pairs_card- For d ≤ g, the number of pairs (i, j) of elements in Fin g satisfying j + d = i is g - d.
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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem biclique_exact_forward_pairs_sum {R : Type*} [Fintype R] (g d : ℕ) (hd : d ≤ g) (A B : R → Finset (Fin g)) (hunique : ∀ i j : Fin g, j.val+d = i.val → ∃! r, i ∈ A r ∧ j ∈ B r) : (∑ r, (((A r).product (B r)).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val)).card) = g-d := by classical let C : R → Finset (Fin g × Fin g) := fun r => ((A r).product (B r)).filter (fun p => p.2.val+d = p.1.val) let S := ((univ : Finset (Fin g)).product univ).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val) have hdis : (↑(univ : Finset R) : Set R).PairwiseDisjoint C := by intro r hr s hs hrs apply disjoint_left.mpr intro p hpr hps have hrd := (mem_filter.mp hpr).2 have hri := (mem_product.mp (mem_filter.mp hpr).1) have hsi := (mem_product.mp (mem_filter.mp hps).1) obtain ⟨t, ht, huniq⟩ := hunique p.1 p.2 hrd exact hrs ((huniq r hri).trans (huniq s hsi).symm) have hcover : univ.biUnion C = S := by ext p constructor · intro hp obtain ⟨r, hr, hpr⟩ := mem_biUnion.mp hp exact mem_filter.mpr ⟨mem_product.mpr ⟨mem_univ _, mem_univ _⟩, (mem_filter.mp hpr).2⟩ · intro hp have hdist := (mem_filter.mp hp).2 obtain ⟨r, hr, huniq⟩ := hunique p.1 p.2 hdist exact mem_biUnion.mpr ⟨r, mem_univ _, mem_filter.mpr ⟨mem_product.mpr hr, hdist⟩⟩ change (∑ r, (C r).card) = g-d rw [← card_biUnion hdis, hcover] exact fin_forward_pairs_card g d hd