digraph_seven_two_overlap_order_ge_43
A finite digraph with every outdegree at least seven and twice its common-predecessor overlap below its order has at least 43 vertices.
Statement
theorem digraph_seven_two_overlap_order_ge_43 (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hsmall : 2 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) : 43 ≤ Fintype.card α
- Source
- Order constraint for restricted small-overlap searches in the OP-110 campaign.
- Verified
- 04 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.
- digraph_common_predecessor_edge_le_sum_chooseThe common-predecessor graph has at most the sum over vertices of the number of pairs in each out-neighborhood.
The proof, explained
The proof shows by contradiction that a finite digraph satisfying the outdegree and overlap hypotheses must have order n at least 43. Since every vertex has outdegree at least 7, the sum of pairs of out-neighbors S = ∑_v choose(d⁺(v), 2) is at least 21 * n. The overlap hypothesis 2 * (S - E) < n then implies that the edge count E of the common-predecessor graph satisfies 41 * n < 2 * E. On the other hand, since this graph is simple on n vertices, 2 * E ≤ 2 * choose(n, 2) ≤ n * (n - 1). If n ≤ 42, then n * (n - 1) ≤ 41 * n, contradicting 41 * n < 2 * E ≤ n * (n - 1).
Adjacency in the common-predecessor graph is decidable.
Given vertices u and v, unfolding `digraph_common_predecessor_graph` expresses adjacency as u ≠ v together with the existence of a common predecessor w. Because the vertex type is finite with decidable equality and digraph adjacency is decidable, typeclass inference (`infer_instance`) provides the decision procedure.
intro u v unfold digraph_common_predecessor_graph infer_instance
Letting n = |α|, S = ∑_v choose(d⁺(v), 2), and E be the edge count of the common-predecessor graph, we have E ≤ S.
We introduce names for the order n = |α|, the sum S of pairs of out-neighbors, and the number of edges E in the common-predecessor graph. The inequality E ≤ S holds by `digraph_common_predecessor_edge_le_sum_choose`, reflecting that every edge in the common-predecessor graph arises from at least one pair of outgoing edges sharing a vertex.
uses
digraph_common_predecessor_edge_le_sum_chooseclassical let n := Fintype.card α let S := ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2 let E := (digraph_common_predecessor_graph D).edgeFinset.card have hES : E ≤ S := digraph_common_predecessor_edge_le_sum_choose α D
21 * n ≤ S.
We express 21 * n as the sum of 21 over all n vertices using commutativity of multiplication (`Nat.mul_comm`). By hypothesis `hdeg`, every outdegree is at least 7, so monotonicity of binomial coefficients (`Nat.choose_le_choose`) gives choose(7, 2) ≤ choose(d⁺(v), 2). Since choose(7, 2) = 21, summing these inequalities over all vertices via `Finset.sum_le_sum` establishes 21 * n ≤ S.
uses
Nat.mul_comm,Finset.sum_le_sum,Nat.choose_le_choosehave hS : 21 * n ≤ S := by change 21 * Fintype.card α ≤ ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2 calc 21 * Fintype.card α = ∑ _v : α, 21 := by simp [Nat.mul_comm] _ ≤ _ := by apply Finset.sum_le_sum intro v _ have h := Nat.choose_le_choose 2 (hdeg v) norm_num at h exact h
E ≤ choose(n, 2).
The common-predecessor graph is a simple graph on n vertices, so by `card_edgeFinset_le_card_choose_two`, its number of edges E cannot exceed choose(n, 2).
uses
card_edgeFinset_le_card_choose_twohave hE : E ≤ Nat.choose n 2 := (digraph_common_predecessor_graph D).card_edgeFinset_le_card_choose_two41 * n < 2 * E. automation
The hypothesis `hsmall` states that 2 * (S - E) < n. Combining this with 21 * n ≤ S, linear arithmetic over the natural numbers shows that 42 * n - 2 * E ≤ 2 * (S - E) < n, whence 41 * n < 2 * E, as verified by `omega`.
have hsmall' : 2 * (S - E) < n := hsmall have hlin : 41 * n < 2 * E := by omega
2 * E ≤ n * (n - 1). automation
Rewriting choose(n, 2) as n * (n - 1) / 2 using `Nat.choose_two_right`, the property `Nat.div_mul_le_self` shows that 2 * choose(n, 2) ≤ n * (n - 1). Combining this with E ≤ choose(n, 2), `omega` concludes that 2 * E ≤ n * (n - 1).
uses
Nat.choose_two_right,Nat.div_mul_le_selfhave hchoose : 2 * Nat.choose n 2 ≤ n * (n - 1) := by rw [Nat.choose_two_right] have h := Nat.div_mul_le_self (n * (n - 1)) 2 omega have hbound : 2 * E ≤ n * (n - 1) := by omega
43 ≤ n, completing the proof. automation
Suppose for contradiction that n < 43, so n - 1 ≤ 41 by `omega`. Multiplying both sides by n via `Nat.mul_le_mul_left` and commuting factors with `Nat.mul_comm` gives n * (n - 1) ≤ 41 * n. But we already established 41 * n < 2 * E ≤ n * (n - 1), which contradicts n * (n - 1) ≤ 41 * n. The `omega` tactic detects this contradiction and closes the goal.
uses
Nat.mul_comm,Nat.mul_le_mul_leftby_contra hn have hsub : n - 1 ≤ 41 := by omega have hmul : n * (n - 1) ≤ 41 * n := by simpa [Nat.mul_comm] using Nat.mul_le_mul_left n hsub omega
digraph_common_predecessor_edge_le_sum_choose- In any finite digraph, the number of edges in the common-predecessor graph is at most the sum over all vertices v of the binomial coefficient choose(d⁺(v), 2).
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set s, then the sum of f over s is at most the sum of g over s.
Nat.choose_le_choose- For a fixed lower index c, the binomial coefficient choose(a, c) is a monotone non-decreasing function of the upper index a.
card_edgeFinset_le_card_choose_two- The number of edges in any finite simple graph on vertex set V is at most choose(|V|, 2).
Nat.choose_two_right- For any natural number n, the binomial coefficient choose(n, 2) equals n * (n - 1) / 2.
Nat.div_mul_le_self- Integer division satisfies (m / n) * n ≤ m for all natural numbers m and n.
Nat.mul_le_mul_left- If n ≤ m, then k * n ≤ k * m for any natural number k.
- The auxiliary private instance on lines 1–5 constructs a decidability instance for adjacency in the common-predecessor graph, which is required formally by Lean so that the finite edge set `edgeFinset` can be formed.
- The linear arithmetic tactic `omega` is used multiple times (lines 32, 36, 37, 39, 42) to automate integer inequalities, such as deducing $41 n < 2 E$ from $2(S - E) < n$ and $21 n \le S$, and detecting the final contradiction.
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.
private instance in504_order_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instancetheorem digraph_seven_two_overlap_order_ge_43 (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hsmall : 2 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) : 43 ≤ Fintype.card α := by classical let n := Fintype.card α let S := ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2 let E := (digraph_common_predecessor_graph D).edgeFinset.card have hES : E ≤ S := digraph_common_predecessor_edge_le_sum_choose α D have hS : 21 * n ≤ S := by change 21 * Fintype.card α ≤ ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2 calc 21 * Fintype.card α = ∑ _v : α, 21 := by simp [Nat.mul_comm] _ ≤ _ := by apply Finset.sum_le_sum intro v _ have h := Nat.choose_le_choose 2 (hdeg v) norm_num at h exact h have hE : E ≤ Nat.choose n 2 := (digraph_common_predecessor_graph D).card_edgeFinset_le_card_choose_two have hsmall' : 2 * (S - E) < n := hsmall have hlin : 41 * n < 2 * E := by omega have hchoose : 2 * Nat.choose n 2 ≤ n * (n - 1) := by rw [Nat.choose_two_right] have h := Nat.div_mul_le_self (n * (n - 1)) 2 omega have hbound : 2 * E ≤ n * (n - 1) := by omega by_contra hn have hsub : n - 1 ≤ 41 := by omega have hmul : n * (n - 1) ≤ 41 * n := by simpa [Nat.mul_comm] using Nat.mul_le_mul_left n hsub omega