AFTD Auto-Formalizing Theoretical Domains

digraph_128_regular_independence_small_overlap

theoremverified

A seven-outregular digraph on 128 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z overlap condition.

Statement

theorem digraph_128_regular_independence_small_overlap
    (D : Digraph (Fin 128)) [DecidableRel D.Adj]
    (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)
    (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) :
    3 * ((∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 128)
Source
Extremal overlap counting for OP-110.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…

The proof, explained

To prove the strict overlap condition 3 * (∑ᵥ (|N⁺(v)| choose 2) - |E(J)|) < 128, the proof bounds the edge count of the common-predecessor graph J from below using Turán's theorem on its complement H = Jᶜ. Since J is K₄-independent, H is K₄-free, so Turán's theorem limits H to at most 5461 edges out of the total 8128 edges in K₁₂₈, forcing J to have at least 2667 edges. Summing the pairs of out-neighbors gives 128 * (7 choose 2) = 2688, leaving an excess of at most 2688 - 2667 = 21 edges, so 3 * 21 = 63 < 128.

  1. Adjacency in the common-predecessor graph is decidable.

    Unfolding the definition of the common-predecessor graph shows that two vertices u and v are adjacent if and only if u ≠ v and there exists a vertex w with directed edges to both u and v. Since the vertex set Fin 128 is finite and edge adjacency in D is decidable, typeclass inference synthesizes decidability of this bounded existential condition.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The complement graph H = Jᶜ contains no 4-clique.

    Let J be the common-predecessor graph of D and H = Jᶜ its complement graph. By hypothesis hindep, J has no independent set of size 4. Since an independent set in J corresponds precisely to a clique in the complement H, simplifying with the definitions of J and H establishes that H is 4-clique-free.

    lines 13–16

      classical
      let J := digraph_common_predecessor_graph D
      let H := Jᶜ
      have hfree : H.CliqueFree 4 := by simpa [H, J] using hindep
  3. The complement graph H has at most 5461 edges.

    By Turán's theorem (SimpleGraph.CliqueFree.card_edgeFinset_le with r = 3), any K₄-free graph on 128 vertices has at most (128² - (128 % 3)²) * (3 - 1) / (2 * 3) + (128 % 3).choose 2 edges. Computing this value via norm_num yields the upper bound |E(H)| ≤ 5461.

    lines 17–20

    uses SimpleGraph.CliqueFree.card_edgeFinset_le

      have hupper : H.edgeFinset.card ≤ 5461 := by
        have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := H) (r := 3) hfree
        norm_num at h
        exact h
  4. The edge sets of J and H are disjoint.

    By SimpleGraph.disjoint_edgeFinset, edge sets are disjoint if and only if the underlying graphs are disjoint. Because H is defined as Jᶜ, this reduces to Disjoint J Jᶜ, which holds by disjoint_compl_right.

    lines 21–24

    uses SimpleGraph.disjoint_edgeFinset, disjoint_compl_right

      have hdis : Disjoint J.edgeFinset H.edgeFinset := by
        rw [SimpleGraph.disjoint_edgeFinset]
        change Disjoint J Jᶜ
        exact disjoint_compl_right
  5. The union of the edge sets of J and H is the edge set of the complete graph on 128 vertices.

    By SimpleGraph.edgeFinset_sup, the union of the edge sets of J and H is the edge set of their join J ⊔ H. Since H = Jᶜ, their join is the complete graph ⊤ by sup_compl_eq_top, so SimpleGraph.edgeFinset_inj.mpr implies their edge sets are equal.

    lines 25–28

    uses SimpleGraph.edgeFinset_sup, SimpleGraph.edgeFinset_inj.mpr, sup_compl_eq_top

      have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 128)).edgeFinset := by
        rw [← SimpleGraph.edgeFinset_sup]
        change (J ⊔ Jᶜ).edgeFinset = _
        exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top
  6. The sum of the edge counts of J and H is 8128.

    Because the edge sets of J and H are disjoint, the sum of their sizes equals the size of their union (Finset.card_union_of_disjoint), which is the edge set of the complete graph K₁₂₈ (SimpleGraph.card_edgeFinset_top_eq_card_choose_two). Rewriting the binomial coefficient via Nat.choose_two_right as 128 * 127 / 2 and evaluating it numerically gives 8128.

    lines 29–33

    uses Finset.card_union_of_disjoint, SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Nat.choose_two_right

      have htotal : J.edgeFinset.card + H.edgeFinset.card = 8128 := by
        rw [← Finset.card_union_of_disjoint hdis, hunion,
          SimpleGraph.card_edgeFinset_top_eq_card_choose_two]
        rw [Nat.choose_two_right]
        norm_num
  7. The sum of (out-degree choose 2) over all vertices equals 2688.

    Since every vertex in D has out-degree 7 by hdeg, each term in the sum is 7.choose 2 = 21. Summing 21 over all 128 vertices yields 128 * 21 = 2688.

    lines 34–36

      have hinc : (∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2688 := by
        simp [hdeg]
        norm_num [Nat.choose]
  8. The strict 3z overlap inequality 3 * (2688 - |E(J)|) < 128 holds. automation

    Substituting the sum of 2688 reduces the goal to 3 * (2688 - |E(J)|) < 128. Since |E(J)| + |E(H)| = 8128 and |E(H)| ≤ 5461, we have |E(J)| ≥ 8128 - 5461 = 2667, meaning 2688 - |E(J)| ≤ 21 and 3 * 21 = 63 < 128. The omega tactic concludes the proof by linear integer arithmetic.

    lines 37–40

      change 3 * ((∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
        J.edgeFinset.card) < 128
      rw [hinc]
      omega
SimpleGraph.CliqueFree.card_edgeFinset_le
Turán's theorem: an (r+1)-clique-free graph on n vertices has at most (n² - (n % r)²) * (r - 1) / (2 * r) + (n % r).choose 2 edges.
SimpleGraph.disjoint_edgeFinset
The edge sets of two graphs are disjoint if and only if the graphs themselves are disjoint.
disjoint_compl_right
In any Heyting or Boolean algebra, an element is disjoint from its complement.
SimpleGraph.edgeFinset_sup
The edge set of the join (graph union) of two graphs is the union of their edge sets.
SimpleGraph.edgeFinset_inj.mpr
If two graphs are equal, their edge sets are equal.
sup_compl_eq_top
In a Boolean algebra, the join of any element with its complement is the top element.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two
The complete graph on a finite vertex set has (card V).choose 2 edges.
Nat.choose_two_right
The binomial coefficient n.choose 2 equals n * (n - 1) / 2.

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

private instance in833_order128_decAdj (D : Digraph (Fin 128)) [DecidableRel D.Adj] :    DecidableRel (digraph_common_predecessor_graph D).Adj := by  intro u v  unfold digraph_common_predecessor_graph  infer_instancetheorem digraph_128_regular_independence_small_overlap    (D : Digraph (Fin 128)) [DecidableRel D.Adj]    (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)    (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) :    3 * ((∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 128) := by  classical  let J := digraph_common_predecessor_graph D  let H := Jᶜ  have hfree : H.CliqueFree 4 := by simpa [H, J] using hindep  have hupper : H.edgeFinset.card ≤ 5461 := by    have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := H) (r := 3) hfree    norm_num at h    exact h  have hdis : Disjoint J.edgeFinset H.edgeFinset := by    rw [SimpleGraph.disjoint_edgeFinset]    change Disjoint J Jᶜ    exact disjoint_compl_right  have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 128)).edgeFinset := by    rw [← SimpleGraph.edgeFinset_sup]    change (J ⊔ Jᶜ).edgeFinset = _    exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top  have htotal : J.edgeFinset.card + H.edgeFinset.card = 8128 := by    rw [← Finset.card_union_of_disjoint hdis, hunion,      SimpleGraph.card_edgeFinset_top_eq_card_choose_two]    rw [Nat.choose_two_right]    norm_num  have hinc : (∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2688 := by    simp [hdeg]    norm_num [Nat.choose]  change 3 * ((∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -    J.edgeFinset.card) < 128  rw [hinc]  omega
See it in the graphDiscuss this resultChallenge it