AFTD Auto-Formalizing Theoretical Domains

biclique_exact_forward_pairs_sum

theoremverified

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

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.

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

    lines 11–15

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

    lines 16–24

    uses disjoint_left.mpr

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

    lines 25–34

    uses mem_univ

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

    lines 35–37

    uses card_biUnion, fin_forward_pairs_card

      change (∑ 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

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