AFTD Auto-Formalizing Theoretical Domains

ordered_biclique_dyadic_tree_incidence

theoremverified

For 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 which owns each dyadic forward pair exactly once has total vertex incidence plus 2^m equal to g(m+1).

Statement

theorem ordered_biclique_dyadic_tree_incidence
    (g m : ℕ) (hm : 1 ≤ m) (hlo : 2^(m-1) ≤ g)
    (A B : Fin (g-1) → Finset (Fin g))
    (hdis : ∀ r, Disjoint (A r) (B r))
    (htree : ∀ r, (A r).card + (B r).card = 1 +
      (range m).sum (fun j => (((A r).product (B r)).filter
        (fun p : Fin g × Fin g => p.2.val+2^j = p.1.val)).card))
    (hunique : ∀ j < m, ∀ i k : Fin g, k.val+2^j = i.val →
      ∃! r, i ∈ A r ∧ k ∈ B r) :
    (∑ i : Fin g, (univ.filter
      (fun r : Fin (g-1) => i ∈ A r ∪ B r)).card) + 2^m = g*(m+1)
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 2
  • biclique_exact_forward_pairs_sumIf bicliques own every forward pair at distance d exactly once on Fin g, the sum of their numbers of such pairs is g-d.
  • biclique_incidence_sumFor finite disjoint-sided bicliques, total vertex incidence counted by vertices equals total side cardinality counted by bicliques.
Used by 1

The proof, explained

By double counting, the sum of vertex incidences across the bicliques equals the sum of their side sizes |A_r| + |B_r|. Using the tree size condition and the fact that every dyadic forward pair is covered exactly once, this side sum evaluates to (g - 1) + ∑_{j < m} (g - 2^j). Combining these terms with the standard geometric series ∑_{j < m} 2^j = 2^m - 1 balances the dyadic sum to m * g, from which linear arithmetic concludes that the total incidence plus 2^m equals g(m + 1).

  1. Every dyadic step 2^j for j < m is at most g, and g is strictly positive.

    Because j < m, we have j ≤ m - 1, which implies 2^j ≤ 2^(m-1) by monotonicity of exponentiation (Nat.pow_le_pow_right). Combining this with the lower bound 2^(m-1) ≤ g (hlo) yields 2^j ≤ g. Furthermore, 2^(m-1) > 0 by positivity of powers of two (Nat.two_pow_pos), so g > 0 via lt_of_lt_of_le.

    lines 16–19

    uses Nat.pow_le_pow_right, lt_of_lt_of_le, Nat.two_pow_pos

      classical
      have hpow (j : ℕ) (hj : j < m) : 2^j ≤ g :=
        (Nat.pow_le_pow_right (by decide) (by omega : j ≤ m-1)).trans hlo
      have hg : 0 < g := lt_of_lt_of_le (Nat.two_pow_pos _) hlo
  2. At each scale j < m, the total count of dyadic forward pairs of difference 2^j across all bicliques is g - 2^j.

    By the uniqueness assumption (hunique), every pair of vertices (k, i) with k + 2^j = i belongs to B_r × A_r for a unique biclique r. Because 2^j ≤ g, the helper theorem biclique_exact_forward_pairs_sum applies directly to sum these pair counts across all bicliques to g - 2^j.

    lines 20–23

    uses biclique_exact_forward_pairs_sum

      have hsum (j : ℕ) (hj : j < m) :
          (∑ r, (((A r).product (B r)).filter
            (fun p : Fin g × Fin g => p.2.val+2^j = p.1.val)).card) = g-2^j :=
        biclique_exact_forward_pairs_sum g (2^j) (hpow j hj) A B (hunique j hj)
  3. The sum of all biclique side sizes equals (g - 1) + ∑_{j < m} (g - 2^j).

    The tree condition (htree) rewrites |A_r| + |B_r| for each biclique as 1 + ∑_{j < m} |{pairs}|. Distributing the outer sum over the g - 1 bicliques gives a constant term of g - 1 (via sum_const, card_univ, and Fintype.card_fin). Exchanging the order of summation with sum_comm allows us to apply the dyadic pair count from Step 2 to each scale j, producing the sum of g - 2^j.

    lines 24–31

    uses sum_add_distrib, sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul, mul_one, sum_comm, sum_congr

      have htotal : (∑ r, ((A r).card+(B r).card)) =
          (g-1) + (range m).sum (fun j => g-2^j) := by
        simp_rw [htree]
        rw [sum_add_distrib]
        simp only [sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul, mul_one]
        congr 1
        rw [sum_comm]
        exact sum_congr rfl (fun j hj => hsum j (mem_range.mp hj))
  4. For any natural number t, the geometric sum ∑_{j < t} 2^j + 1 equals 2^t.

    This identity is proved by induction on t. For t = 0, the sum over range 0 is empty, so 0 + 1 = 2^0. For the inductive step, sum_range_succ separates the last term 2^t, and pow_succ rewrites 2^(t+1) as 2^t * 2, after which linear arithmetic finishes the step using the induction hypothesis.

    lines 32–36

    uses sum_range_succ, pow_succ

      have hgeom : ∀ t : ℕ, (range t).sum (fun j => 2^j) + 1 = 2^t := by
        intro t
        induction t with
        | zero => norm_num
        | succ t ih => rw [sum_range_succ, pow_succ]; omega
  5. The dyadic counts and powers of two balance: ∑_{j < m} (g - 2^j) + ∑_{j < m} 2^j = m * g.

    Combining the two sums over range m via sum_add_distrib, each summand becomes (g - 2^j) + 2^j. Because 2^j ≤ g, Nat.sub_add_cancel simplifies this to g. Summing the constant g over range m of size m gives m * g.

    lines 37–41

    uses sum_add_distrib, sum_congr, Nat.sub_add_cancel, sum_const, card_range, Nat.nsmul_eq_mul

      have hbalance : (range m).sum (fun j => g-2^j) + (range m).sum (fun j => 2^j) = m*g := by
        rw [← sum_add_distrib]
        have he := sum_congr rfl (fun j (hj : j ∈ range m) =>
          Nat.sub_add_cancel (hpow j (mem_range.mp hj)))
        simpa only [sum_const, card_range, Nat.nsmul_eq_mul] using he
  6. The total vertex incidence plus 2^m equals g * (m + 1). automation

    Because A_r and B_r are disjoint, biclique_incidence_sum converts the total vertex incidence into the total side size, which Step 3 evaluated as (g - 1) + ∑_{j < m} (g - 2^j). Specializing the geometric sum identity to t = m gives ∑_{j < m} 2^j + 1 = 2^m. Along with the balance identity ∑_{j < m} (g - 2^j) + ∑_{j < m} 2^j = m * g and the ring identity g * (m + 1) = m * g + g, Presburger arithmetic (omega) closes the goal.

    lines 42–45

    uses biclique_incidence_sum

      rw [biclique_incidence_sum A B hdis, htotal]
      have hge := hgeom m
      have hmul : g*(m+1) = m*g+g := by ring
      omega
biclique_exact_forward_pairs_sum
If every forward pair of vertices at fixed distance d ≤ g is covered by a unique biclique in a family, then the sum over all bicliques of the number of such forward pairs they contain is g - d.
biclique_incidence_sum
For a family of bicliques with disjoint sides, the sum over all vertices of their biclique incidences equals the sum over all bicliques of their total side sizes.
card_range
The cardinality of the range finset range n = {0, ..., n-1} is n.
card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type itself.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
lt_of_lt_of_le
In a preorder, if a < b and b ≤ c, then a < c.
mul_one
Multiplying an element by 1 on the right leaves it unchanged.
Nat.nsmul_eq_mul
Natural number scalar multiplication m • n equals standard multiplication m * n.
Nat.pow_le_pow_right
For a positive base n > 0, exponentiation n^i is monotonically increasing in the exponent i.
Nat.sub_add_cancel
For natural numbers with m ≤ n, subtracting m and then adding m recovers n.
Nat.two_pow_pos
Powers of two are strictly positive for any natural exponent.
pow_succ
The power a^(n+1) equals a^n * a.
sum_add_distrib
A finite sum of pointwise sums is the sum of the two individual finite sums.
sum_comm
The order of summation in a double finite sum can be interchanged.
sum_congr
Two finite sums over the same set are equal if their terms agree at every element.
sum_const
Summing a constant over a finite set equals the cardinality of the set scalar-multiplied by that constant.
sum_range_succ
Summing over range (n + 1) equals the sum over range n plus the term at 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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem ordered_biclique_dyadic_tree_incidence    (g m : ℕ) (hm : 1 ≤ m) (hlo : 2^(m-1) ≤ g)    (A B : Fin (g-1) → Finset (Fin g))    (hdis : ∀ r, Disjoint (A r) (B r))    (htree : ∀ r, (A r).card + (B r).card = 1 +      (range m).sum (fun j => (((A r).product (B r)).filter        (fun p : Fin g × Fin g => p.2.val+2^j = p.1.val)).card))    (hunique : ∀ j < m, ∀ i k : Fin g, k.val+2^j = i.val →      ∃! r, i ∈ A r ∧ k ∈ B r) :    (∑ i : Fin g, (univ.filter      (fun r : Fin (g-1) => i ∈ A r ∪ B r)).card) + 2^m = g*(m+1) := by  classical  have hpow (j : ℕ) (hj : j < m) : 2^j ≤ g :=    (Nat.pow_le_pow_right (by decide) (by omega : j ≤ m-1)).trans hlo  have hg : 0 < g := lt_of_lt_of_le (Nat.two_pow_pos _) hlo  have hsum (j : ℕ) (hj : j < m) :      (∑ r, (((A r).product (B r)).filter        (fun p : Fin g × Fin g => p.2.val+2^j = p.1.val)).card) = g-2^j :=    biclique_exact_forward_pairs_sum g (2^j) (hpow j hj) A B (hunique j hj)  have htotal : (∑ r, ((A r).card+(B r).card)) =      (g-1) + (range m).sum (fun j => g-2^j) := by    simp_rw [htree]    rw [sum_add_distrib]    simp only [sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul, mul_one]    congr 1    rw [sum_comm]    exact sum_congr rfl (fun j hj => hsum j (mem_range.mp hj))  have hgeom : ∀ t : ℕ, (range t).sum (fun j => 2^j) + 1 = 2^t := by    intro t    induction t with    | zero => norm_num    | succ t ih => rw [sum_range_succ, pow_succ]; omega  have hbalance : (range m).sum (fun j => g-2^j) + (range m).sum (fun j => 2^j) = m*g := by    rw [← sum_add_distrib]    have he := sum_congr rfl (fun j (hj : j ∈ range m) =>      Nat.sub_add_cancel (hpow j (mem_range.mp hj)))    simpa only [sum_const, card_range, Nat.nsmul_eq_mul] using he  rw [biclique_incidence_sum A B hdis, htotal]  have hge := hgeom m  have hmul : g*(m+1) = m*g+g := by ring  omega
See it in the graphDiscuss this resultChallenge it