ordered_biclique_dyadic_tree_incidence
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
- ordered_biclique_dyadic_tree_intervalsA nonempty biclique at each cut of Fin g, separated by that cut and covering every ordered pair, has interval sides when each biclique…
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).
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.
uses
Nat.pow_le_pow_right,lt_of_lt_of_le,Nat.two_pow_posclassical 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
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.
uses
biclique_exact_forward_pairs_sumhave 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)
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.
uses
sum_add_distrib,sum_const,card_univ,Fintype.card_fin,Nat.nsmul_eq_mul,mul_one,sum_comm,sum_congrhave 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))
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.
uses
sum_range_succ,pow_succhave 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
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.
uses
sum_add_distrib,sum_congr,Nat.sub_add_cancel,sum_const,card_range,Nat.nsmul_eq_mulhave 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
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.
uses
biclique_incidence_sumrw [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.
- The final step relies on the automated tactic omega to perform Presburger arithmetic on natural numbers, combining the dyadic balance identity, the geometric sum evaluation, and the algebraic expansion g*(m+1) = m*g + g.
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 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