AFTD Auto-Formalizing Theoretical Domains

ordered_biclique_dyadic_tree_intervals

theoremverified

A nonempty biclique at each cut of Fin g, separated by that cut and covering every ordered pair, has interval sides when each biclique satisfies the dyadic tree cardinality identity and dyadic forward pairs have unique owners, with m positive and g at least 2^(m-1).

Statement

theorem ordered_biclique_dyadic_tree_intervals
    (g m : ℕ) (hm : 1 ≤ m) (hlo : 2^(m-1) ≤ g)
    (A B : Fin (g-1) → Finset (Fin g))
    (hA : ∀ r i, i ∈ A r → r.val < i.val)
    (hB : ∀ r i, i ∈ B r → i.val ≤ r.val)
    (hne : ∀ r, (A r ∪ B r).Nonempty)
    (hcover : ∀ i j : Fin g, i < j → ∃ r, i ∈ B r ∧ j ∈ A 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) :
    (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ A r → k ∈ A r → j ∈ A r) ∧
    (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ B r → k ∈ B r → j ∈ B r)
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
Used by 1

The proof, explained

The theorem establishes that the sides of each biclique A(r) and B(r) are intervals by reducing to the characterization of minimum-incidence ordered biclique covers. First, the lower bound 2^(m-1) ≤ g ensures g > 0, and the cut-separation conditions guarantee that A(r) and B(r) are disjoint for every r. Using this disjointness, the dyadic tree cardinality identity and uniqueness of dyadic forward pairs imply, via ordered_biclique_dyadic_tree_incidence, that the total incidence achieves the minimum bound. Finally, ordered_biclique_minimum_incidence_intervals concludes that any covering achieving this bound has interval sides.

  1. g is strictly positive.

    Since 2^(m - 1) > 0 by Nat.two_pow_pos and 2^(m - 1) ≤ g by assumption hlo, transitivity of strict inequality (lt_of_lt_of_le) gives 0 < g.

    line 19

    uses lt_of_lt_of_le, Nat.two_pow_pos

      have hg : 0 < g := lt_of_lt_of_le (Nat.two_pow_pos _) hlo
  2. For each cut r, the sets A(r) and B(r) are disjoint.

    By disjoint_left.mpr, it suffices to show that no vertex i can belong to both A(r) and B(r). If i ∈ A(r), then r < i by hA. If i ∈ B(r), then i ≤ r by hB. These two inequalities are contradictory, and omega closes the goal by integer linear arithmetic.

    lines 20–25

    uses disjoint_left.mpr

      have hdis (r : Fin (g-1)) : Disjoint (A r) (B r) := by
        apply disjoint_left.mpr
        intro i hi hbi
        have := hA r i hi
        have := hB r i hbi
        omega
  3. For every cut r, the sides A(r) and B(r) are intervals in Fin g.

    With disjointness established, ordered_biclique_dyadic_tree_incidence proves that the total incidence plus 2^m equals g*(m + 1). Supplying this incidence equality along with the separation, nonemptiness, and covering hypotheses to ordered_biclique_minimum_incidence_intervals concludes that every A(r) and B(r) is an interval.

    lines 26–27

    uses ordered_biclique_minimum_incidence_intervals, ordered_biclique_dyadic_tree_incidence

      exact ordered_biclique_minimum_incidence_intervals g m hg A B hA hB hne hcover
        (ordered_biclique_dyadic_tree_incidence g m hm hlo A B hdis htree hunique)
lt_of_lt_of_le
If a < b and b ≤ c, then a < c.
Nat.two_pow_pos
For any natural number w, 2^w is strictly positive.
disjoint_left.mpr
Two sets are disjoint if no element belonging to the first also belongs to the second.
ordered_biclique_dyadic_tree_incidence
Under separation and disjointness, if bicliques satisfy the dyadic tree cardinality identity and cover dyadic forward pairs uniquely, their total incidence satisfies ∑_i |{r : i ∈ A r ∪ B r}| + 2^m = g*(m+1).
ordered_biclique_minimum_incidence_intervals
An ordered biclique covering of all pairs i < j achieving the minimum incidence sum g*(m+1) - 2^m has the property that each A(r) and B(r) is an interval.

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_intervals    (g m : ℕ) (hm : 1 ≤ m) (hlo : 2^(m-1) ≤ g)    (A B : Fin (g-1) → Finset (Fin g))    (hA : ∀ r i, i ∈ A r → r.val < i.val)    (hB : ∀ r i, i ∈ B r → i.val ≤ r.val)    (hne : ∀ r, (A r ∪ B r).Nonempty)    (hcover : ∀ i j : Fin g, i < j → ∃ r, i ∈ B r ∧ j ∈ A 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) :    (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ A r → k ∈ A r → j ∈ A r) ∧    (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ B r → k ∈ B r → j ∈ B r) := by  have hg : 0 < g := lt_of_lt_of_le (Nat.two_pow_pos _) hlo  have hdis (r : Fin (g-1)) : Disjoint (A r) (B r) := by    apply disjoint_left.mpr    intro i hi hbi    have := hA r i hi    have := hB r i hbi    omega  exact ordered_biclique_minimum_incidence_intervals g m hg A B hA hB hne hcover    (ordered_biclique_dyadic_tree_incidence g m hm hlo A B hdis htree hunique)
See it in the graphDiscuss this resultChallenge it