digraph_nested_parents_overlap_general
For k transitive low vertices pointing to q, nested common-predecessor counts k+3−t force common-predecessor overlap at least twice choose(k+2,3).
Statement
theorem digraph_nested_parents_overlap_general (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k : ℕ) (low : Fin k → α) (q : α) (hinj : Function.Injective low) (hq : ∀ i, low i ≠ q) (htrans : ∀ i j : Fin k, i.val < j.val → D.Adj (low j) (low i)) (htarget : ∀ i, D.Adj (low i) q) (hparents : ∀ t : ℕ, 1 ≤ t → t ≤ k → k + 3 - t ≤ (Finset.univ.filter fun p : α => p ≠ q ∧ (∀ i, p ≠ low i) ∧ D.Adj p q ∧ ∀ i : Fin k, i.val < t → D.Adj p (low i)).card) : 2 * Nat.choose (k + 2) 3 ≤ (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card
- Source
- General form of common-predecessor incidence counting for the twenty-cut equality route; experiment 26346 checks the arithmetic.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_overlap_incidence_identityFor a finite digraph, the total excess multiplicity of edges of its common-predecessor graph equals the sum of unordered pairs in its…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
The proof, explained
The theorem lower bounds the common-predecessor overlap by rewriting it, via an incidence identity, as the sum of (|P(e)| - 1) over all edges e in the common-predecessor graph, where P(e) denotes the common predecessors of e. To bound this sum, an explicit injective family of edges is constructed, consisting of pairs {q, low(j)} and {low(i), low(j)} with i < j. For each block j, a candidate predecessor set Wf(j) of size at least 2(k - j) + 1 is formed by uniting the assumed external parents with the later low vertices low(j') for j' > j. Since every element of Wf(j) is a common predecessor of each edge in block j, each such edge contributes at least 2(k - j) to the sum. Summing these contributions across all blocks and applying the algebraic identity ∑_{j=0}^{k-1} (j+1)(k-j) = choose(k+2,3) yields the required lower bound of 2 * choose(k+2,3).
For any natural number k, twice the sum ∑_{j=0}^{k-1} (j+1) equals k(k+1).
We proceed by induction on k. The base case k = 0 is 0 = 0. In the inductive step, we peel off the last term (k + 1) using Finset.sum_range_succ and conclude by linear arithmetic using the induction hypothesis ih.
uses
Finset.sum_range_succprivate lemma dnpg_sum_two (k : ℕ) : 2 * (∑ j ∈ Finset.range k, (j+1)) = k*(k+1) := by induction k with | zero => simp | succ k ih => rw [Finset.sum_range_succ]; nlinarith [ih]
For any natural number k, six times the sum ∑_{j=0}^{k-1} (j+1)(k-j) equals k(k+1)(k+2).
We induct on k. The base case k = 0 is trivial. For the step k + 1, we split the sum at k: the last term is (k+1)(k+1-k) = k+1, and for each earlier term we rewrite (j+1)(k+1-j) as (j+1)(k-j) + (j+1). Distributing the sum yields the previous sum plus ∑_{j=0}^{k-1} (j+1). Combining this with dnpg_sum_two and the induction hypothesis, non-linear arithmetic finishes the step.
uses
Finset.sum_range_succ,Nat.add_sub_cancel_left,mul_one,Finset.sum_add_distrib,Finset.sum_congr,Finset.mem_range,mul_add,dnpg_sum_twoprivate lemma dnpg_sum_six (k : ℕ) : 6 * (∑ j ∈ Finset.range k, (j+1)*(k-j)) = k*(k+1)*(k+2) := by induction k with | zero => simp | succ k ih => rw [Finset.sum_range_succ] have hlast : (k+1)*(k+1-k) = k+1 := by rw [Nat.add_sub_cancel_left, mul_one] rw [hlast] have hstep : (∑ j ∈ Finset.range k, (j+1)*(k+1-j)) = (∑ j ∈ Finset.range k, (j+1)*(k-j)) + ∑ j ∈ Finset.range k, (j+1) := by rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro j hj rw [Finset.mem_range] at hj have hkj : k + 1 - j = (k - j) + 1 := by omega rw [hkj, mul_add, mul_one] rw [hstep] have hT := dnpg_sum_two k nlinarith [ih, hT]
For any natural number k, the sum ∑_{j=0}^{k-1} (j+1)(k-j) equals choose(k+2, 3).
By the descending factorial formula, (k+2)^{\underline{3}} = 3! * choose(k+2, 3) = 6 * choose(k+2, 3). Expanding the descending factorial gives (k+2)(k+1)k. Comparing this with dnpg_sum_six, which gives 6 * ∑_{j=0}^{k-1} (j+1)(k-j) = k(k+1)(k+2), and dividing by 6 via Nat.eq_of_mul_eq_mul_left yields the identity.
uses
dnpg_sum_six,Nat.descFactorial_eq_factorial_mul_choose,Nat.descFactorial,Nat.eq_of_mul_eq_mul_leftprivate lemma dnpg_arith (k : ℕ) : (∑ j ∈ Finset.range k, (j+1)*(k-j)) = Nat.choose (k+2) 3 := by have h1 := dnpg_sum_six k have h2 : 6 * Nat.choose (k+2) 3 = (k+2)*(k+1)*k := by have h := Nat.descFactorial_eq_factorial_mul_choose (k+2) 3 have hfac : (3:ℕ).factorial = 6 := by decide rw [hfac] at h rw [← h] simp [Nat.descFactorial] ring rw [show k*(k+1)*(k+2) = (k+2)*(k+1)*k from by ring] at h1 exact Nat.eq_of_mul_eq_mul_left (by decide) (h1.trans h2.symm)
Summing (j+1)(k-j) over the type Fin k yields choose(k+2, 3).
We rewrite the sum over Fin k to a sum over Finset.range k using Fin.sum_univ_eq_sum_range, and then apply dnpg_arith.
uses
Fin.sum_univ_eq_sum_range,dnpg_arithprivate lemma dnpg_sum_range_fin (k : ℕ) : (∑ j : Fin k, (j.val+1)*(k-j.val)) = Nat.choose (k+2) 3 := by rw [Fin.sum_univ_eq_sum_range (fun m => (m+1)*(k-m)) k] exact dnpg_arith k
It suffices to show that 2 * choose(k+2, 3) is at most the sum of (|P(e)| - 1) over all edges e in the common-predecessor graph of D.
By the incidence identity digraph_common_predecessor_overlap_incidence_identity, the common-predecessor overlap ∑_v choose(outdeg(v), 2) - |E(G_cp)| equals ∑_{e ∈ E(G_cp)} (|P(e)| - 1), where P(e) is the set of common in-neighbours of the endpoints of e.
uses
digraph_common_predecessor_overlap_incidence_identitytheorem digraph_nested_parents_overlap_general (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k : ℕ) (low : Fin k → α) (q : α) (hinj : Function.Injective low) (hq : ∀ i, low i ≠ q) (htrans : ∀ i j : Fin k, i.val < j.val → D.Adj (low j) (low i)) (htarget : ∀ i, D.Adj (low i) q) (hparents : ∀ t : ℕ, 1 ≤ t → t ≤ k → k + 3 - t ≤ (Finset.univ.filter fun p : α => p ≠ q ∧ (∀ i, p ≠ low i) ∧ D.Adj p q ∧ ∀ i : Fin k, i.val < t → D.Adj p (low i)).card) : 2 * Nat.choose (k + 2) 3 ≤ (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card := by rw [← digraph_common_predecessor_overlap_incidence_identity] show 2 * Nat.choose (k+2) 3 ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1)
Definitions of candidate predecessor sets Hp and Lt, their union Wf, the index type ι, and the candidate edge map g.
For each block j < k, Hp(j) consists of external vertices pointing to q and low(0), ..., low(j), and Lt(j) consists of low(j') for j' > j. Their union Wf(j) gathers all candidate common predecessors. The index type ι indexes pairs of vertices: Sum.inl j corresponds to {q, low(j)}, and Sum.inr ⟨j, i⟩ corresponds to {low(i), low(j)} for i < j. The map blk assigns each such pair its block index j.
uses
Nat.lt_translet Hp : Fin k → Finset α := fun j => Finset.univ.filter (fun p => p ≠ q ∧ (∀ i, p ≠ low i) ∧ D.Adj p q ∧ ∀ i : Fin k, i.val < j.val + 1 → D.Adj p (low i)) let Lt : Fin k → Finset α := fun j => (Finset.Ioi j).image low let Wf : Fin k → Finset α := fun j => Hp j ∪ Lt j let ι : Type := (Fin k) ⊕ (Σ j : Fin k, Fin j.val) let blk : ι → Fin k := fun i => match i with | Sum.inl j => j | Sum.inr p => p.1 let g : ι → Sym2 α := fun i => match i with | Sum.inl j => Sym2.mk q (low j) | Sum.inr p => Sym2.mk (low (p.2.castLT (Nat.lt_trans p.2.isLt p.1.isLt))) (low p.1)
For each j < k, the set Wf(j) has cardinality at least 2(k - j) + 1.
By the hypothesis hparents with t = j + 1, |Hp(j)| ≥ k + 2 - j. Since low is injective, |Lt(j)| = k - 1 - j. The sets Hp(j) and Lt(j) are disjoint because elements of Hp(j) are distinct from all low vertices. Thus |Wf(j)| = |Hp(j)| + |Lt(j)| ≥ (k + 2 - j) + (k - 1 - j) = 2(k - j) + 1.
uses
Finset.card_image_of_injective,Fin.card_Ioi,Finset.disjoint_left,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_image,Finset.mem_Ioi,Finset.card_union_of_disjointhave hHp_card : ∀ j, k + 3 - (j.val+1) ≤ (Hp j).card := by intro j exact hparents (j.val+1) (by omega) (by omega) have hLt_card : ∀ j, (Lt j).card = k - 1 - j.val := by intro j show ((Finset.Ioi j).image low).card = k - 1 - j.val rw [Finset.card_image_of_injective _ hinj] exact Fin.card_Ioi j have hdisj : ∀ j, Disjoint (Hp j) (Lt j) := by intro j rw [Finset.disjoint_left] intro a ha hb simp only [Hp, Finset.mem_filter, Finset.mem_univ, true_and] at ha simp only [Lt, Finset.mem_image, Finset.mem_Ioi] at hb obtain ⟨j', _, rfl⟩ := hb exact ha.2.1 j' rfl have hWf_card : ∀ j, 2*(k - j.val) + 1 ≤ (Wf j).card := by intro j have hcard : (Wf j).card = (Hp j).card + (Lt j).card := Finset.card_union_of_disjoint (hdisj j) rw [hcard, hLt_card j] have h3 := hHp_card j have := j.isLt omega
Every vertex in Wf(j) points to q and to low(i) for all i ≤ j, and Wf(j) is nonempty.
If w ∈ Hp(j), it points to q and all low(i) with i ≤ j by definition. If w = low(j') ∈ Lt(j) with j' > j, it points to q by htarget and to low(i) by the transitivity hypothesis htrans since i ≤ j < j'. Non-emptiness follows because |Wf(j)| ≥ 2(k - j) + 1 ≥ 1.
uses
Finset.mem_union,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_image,Finset.mem_Ioihave hWf_prop : ∀ j (w : α), w ∈ Wf j → D.Adj w q ∧ (∀ i : Fin k, i.val < j.val+1 → D.Adj w (low i)) := by intro j w hw change w ∈ Hp j ∪ Lt j at hw rw [Finset.mem_union] at hw rcases hw with hw | hw · simp only [Hp, Finset.mem_filter, Finset.mem_univ, true_and] at hw exact ⟨hw.2.2.1, hw.2.2.2⟩ · simp only [Lt, Finset.mem_image, Finset.mem_Ioi] at hw obtain ⟨j', hj', rfl⟩ := hw refine ⟨htarget j', ?_⟩ intro i hi exact htrans i j' (by omega) have hWf_nonempty : ∀ j, (Wf j).Nonempty := by intro j apply Finset.card_pos.mp have := hWf_card j omega
The map g assigning indices in ι to unordered pairs of vertices is injective.
We inspect pairs of indices. A pair containing q cannot equal a pair of low vertices since low(i) ≠ q. Two pairs of low vertices {low(i), low(j)} and {low(i'), low(j')} with i < j and i' < j' can only be equal as unordered pairs if i = i' and j = j', by the injectivity of low and order constraints.
uses
Sym2.eq_iff,Fin.val_castLT,congrArg,Fin.exthave hg_inj : Function.Injective g := by rintro (j | ⟨j, i⟩) (j' | ⟨j', i'⟩) heq · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [hinj h2] · exact absurd h1.symm (hq j') · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1.symm (hq _) · exact absurd h1.symm (hq j') · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (hq _) · exact absurd h2 (hq j) · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · have h1v : i.val = i'.val := by simpa only [Fin.val_castLT] using congrArg Fin.val (hinj h1) have h2v : j = j' := hinj h2 subst h2v rw [Fin.ext h1v] · have h1v : i.val = j'.val := by simpa only [Fin.val_castLT] using congrArg Fin.val (hinj h1) have h2v : j.val = i'.val := by simpa only [Fin.val_castLT] using congrArg Fin.val (hinj h2) have h3 := i.isLt have h4 := i'.isLt omega
The image of g consists of valid edges of the common-predecessor graph of D.
For every index in ι, the two endpoints of g(i) are distinct. Because Wf(blk(i)) is nonempty, any vertex w ∈ Wf(blk(i)) is adjacent to both endpoints, which witnesses that g(i) is an edge in the common-predecessor graph.
uses
SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Ne.symm,Fin.val_castLT,Finset.mem_imagehave hedge1 : ∀ j : Fin k, g (Sum.inl j) ∈ (digraph_common_predecessor_graph D).edgeFinset := by intro j dsimp only [g] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] obtain ⟨w, hw⟩ := hWf_nonempty j exact ⟨Ne.symm (hq j), w, (hWf_prop j w hw).1, (hWf_prop j w hw).2 j (by omega)⟩ have hedge2 : ∀ (j : Fin k) (i : Fin j.val), g (Sum.inr ⟨j, i⟩) ∈ (digraph_common_predecessor_graph D).edgeFinset := by intro j i dsimp only [g] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] refine ⟨?_, ?_⟩ · intro h have hv := congrArg Fin.val (hinj h) rw [Fin.val_castLT] at hv have := i.isLt omega · obtain ⟨w, hw⟩ := hWf_nonempty j exact ⟨w, (hWf_prop j w hw).2 _ (by rw [Fin.val_castLT]; omega), (hWf_prop j w hw).2 j (by omega)⟩ have hEfam_sub : (Finset.univ.image g) ⊆ (digraph_common_predecessor_graph D).edgeFinset := by intro e he rw [Finset.mem_image] at he obtain ⟨i, _, rfl⟩ := he rcases i with j | ⟨j, i⟩ · exact hedge1 j · exact hedge2 j i
For every index i in ι with block j = blk(i), the number of common predecessors of g(i) minus 1 is at least 2(k - j).
Every w ∈ Wf(j) is adjacent to both vertices of g(i), whether g(i) is {q, low(j)} or {low(i'), low(j)}. Thus Wf(j) is a subset of the common predecessors of g(i). Comparing cardinalities gives |P(g(i))| - 1 ≥ |Wf(j)| - 1 ≥ 2(k - j).
uses
Finset.mem_filter,Finset.mem_univ,true_and,Sym2.mem_iff,Finset.card_le_card,Fin.val_castLThave hbound : ∀ i : ι, 2*(k - (blk i).val) ≤ (Finset.univ.filter (fun p => ∀ x, x ∈ g i → D.Adj p x)).card - 1 := by rintro (j | ⟨j, i⟩) · have hsub : Wf j ⊆ Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inl j) → D.Adj p x) := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] dsimp only [g] intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl · exact (hWf_prop j w hw).1 · exact (hWf_prop j w hw).2 j (by omega) have h1 : (Wf j).card ≤ (Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inl j) → D.Adj p x)).card := Finset.card_le_card hsub have h2 := hWf_card j dsimp only [blk] omega · have hsub : Wf j ⊆ Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inr ⟨j, i⟩) → D.Adj p x) := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] dsimp only [g] intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl · exact (hWf_prop j w hw).2 _ (by rw [Fin.val_castLT]; omega) · exact (hWf_prop j w hw).2 j (by omega) have h1 : (Wf j).card ≤ (Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inr ⟨j, i⟩) → D.Adj p x)).card := Finset.card_le_card hsub have h2 := hWf_card j dsimp only [blk] omega
Summing 2(k - blk(i)) over all i in ι equals 2 * ∑_{j ∈ Fin k} (j + 1)(k - j).
We split the sum over the disjoint union ι = Fin k ⊕ Σ_{j ∈ Fin k} Fin j into the sum over the first component and the sum over the sigma type. Each block j appears once from the first component and j times from the second, giving a total weight of 1 + j. Factoring out 2 gives the claimed identity.
uses
Fintype.sum_sum_type,Fintype.sum_sigma,Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,Finset.sum_add_distrib,Finset.mul_sum,Finset.sum_congrhave hval : (∑ i : ι, 2*(k - (blk i).val)) = 2 * ∑ j : Fin k, (j.val+1)*(k-j.val) := by dsimp only [ι, blk] rw [Fintype.sum_sum_type, Fintype.sum_sigma] simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] rw [← Finset.sum_add_distrib, Finset.mul_sum] apply Finset.sum_congr rfl intro x _ simp only [Nat.cast_id] ring
The overlap lower bound of 2 * choose(k + 2, 3) holds.
We chain the established relations: 2 * choose(k + 2, 3) equals the sum over ι by dnpg_sum_range_fin and the block sum identity. Termwise bounding each summand by |P(g(i))| - 1 and reindexing the sum via the injectivity of g gives the sum over image(g). Since image(g) is a subset of the edge set of the common-predecessor graph and all terms are non-negative, this is bounded above by the total sum over all edges.
uses
dnpg_sum_range_fin,Finset.sum_le_sum,Finset.sum_image,Finset.sum_le_sum_of_subset_of_nonneg,Nat.zero_lecalc 2 * Nat.choose (k+2) 3 = 2 * ∑ j : Fin k, (j.val+1)*(k-j.val) := by rw [dnpg_sum_range_fin] _ = ∑ i : ι, 2*(k - (blk i).val) := hval.symm _ ≤ ∑ i : ι, ((Finset.univ.filter (fun p => ∀ x, x ∈ g i → D.Adj p x)).card - 1) := Finset.sum_le_sum (fun i _ => hbound i) _ = ∑ e ∈ Finset.univ.image g, ((Finset.univ.filter (fun p => ∀ x, x ∈ e → D.Adj p x)).card - 1) := by rw [Finset.sum_image (s := Finset.univ) (g := g) (f := fun e => ((Finset.univ.filter (fun p => ∀ x, x ∈ e → D.Adj p x)).card - 1)) hg_inj.injOn] _ ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter (fun p => ∀ x, x ∈ e → D.Adj p x)).card - 1) := Finset.sum_le_sum_of_subset_of_nonneg hEfam_sub (fun i _ _ => Nat.zero_le _)
Finset.sum_range_succ- Summing a function over Finset.range (n + 1) equals the sum over Finset.range n plus the value at n.
Nat.add_sub_cancel_left- For natural numbers, (n + m) - n = m.
mul_one- Multiplying any element by 1 leaves it unchanged (a * 1 = a).
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of the first plus the sum of the second.
Finset.sum_congr- If two index sets are equal and the summands agree pointwise on the set, their finite sums are equal.
Finset.mem_range- An element m belongs to Finset.range n if and only if m < n.
mul_add- Left distributivity of multiplication over addition: a * (b + c) = a * b + a * c.
dnpg_sum_two- Twice the sum of the first k positive integers equals k * (k + 1).
dnpg_sum_six- Six times the sum ∑_{j=0}^{k-1} (j+1)(k-j) equals k * (k + 1) * (k + 2).
Nat.descFactorial_eq_factorial_mul_choose- The descending factorial n^{\underline{k}} equals k! * choose(n, k).
Nat.descFactorial- The descending factorial function n^{\underline{k}} = n(n-1)...(n-k+1).
Nat.eq_of_mul_eq_mul_left- If c > 0 and c * a = c * b for natural numbers, then a = b.
Fin.sum_univ_eq_sum_range- Summing a function over the finite type Fin n equals summing it over Finset.range n.
dnpg_arith- The sum ∑_{j=0}^{k-1} (j+1)(k-j) equals choose(k+2, 3).
digraph_common_predecessor_overlap_incidence_identity- The common-predecessor overlap of D equals the sum over all edges e of the common-predecessor graph of (|P(e)| - 1), where P(e) is the set of common predecessors of e.
Nat.lt_trans- Strict inequality on natural numbers is transitive (if n < m and m < k, then n < k).
Finset.card_image_of_injective- An injective map preserves the cardinality of a finite set under image.
Fin.card_Ioi- The number of elements in Fin n strictly greater than a is n - 1 - a.
Finset.disjoint_left- Two finite sets s and t are disjoint if and only if no element of s belongs to t.
Finset.mem_filter- An element is in Finset.filter p s if and only if it is in s and satisfies predicate p.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- True ∧ p is equivalent to p.
Finset.mem_image- An element b belongs to Finset.image f s if and only if b = f(a) for some a ∈ s.
Finset.mem_Ioi- An element x is in Finset.Ioi a if and only if a < x.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.mem_union- An element belongs to the union of two sets if and only if it belongs to at least one of them.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Fin.val_castLT- Coercing an element of Fin m cast to a larger Fin n yields the same natural number value.
congrArg- Congruence of arguments: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
SimpleGraph.mem_edgeFinset- An unordered pair belongs to the edge finset of a simple graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Sym2.mem_iff- An element a belongs to the unordered pair s(b, c) if and only if a = b or a = c.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t| for finite sets.
Fintype.sum_sum_type- The sum over a disjoint union type α ⊕ β equals the sum over α plus the sum over β.
Fintype.sum_sigma- The sum over a dependent pair type Σ x, α(x) equals the iterated sum over x and y.
Finset.sum_const- Summing a constant b over a finite set s equals |s| * b.
Finset.card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
nsmul_eq_mul- Scalar multiplication of a ring element by a natural number equals ordinary multiplication by that number.
Finset.mul_sum- Distributivity of multiplication over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finite set, then the sum of f over the set is at most the sum of g.
Finset.sum_image- If g is injective on s, then summing f over the image of s under g equals summing f ∘ g over s.
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and f is non-negative on t \ s, then the sum of f over s is at most the sum over t.
Nat.zero_le- For every natural number n, 0 ≤ n.
dnpg_sum_range_fin- The sum over Fin k of (j + 1)(k - j) equals choose(k + 2, 3).
- The source file proves four preparatory arithmetic lemmas (dnpg_sum_two, dnpg_sum_six, dnpg_arith, and dnpg_sum_range_fin) establishing the summation identity ∑_{j=0}^{k-1} (j+1)(k-j) = choose(k+2,3) before using it in the main digraph theorem.
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 lemma dnpg_sum_two (k : ℕ) : 2 * (∑ j ∈ Finset.range k, (j+1)) = k*(k+1) := by induction k with | zero => simp | succ k ih => rw [Finset.sum_range_succ]; nlinarith [ih]private lemma dnpg_sum_six (k : ℕ) : 6 * (∑ j ∈ Finset.range k, (j+1)*(k-j)) = k*(k+1)*(k+2) := by induction k with | zero => simp | succ k ih => rw [Finset.sum_range_succ] have hlast : (k+1)*(k+1-k) = k+1 := by rw [Nat.add_sub_cancel_left, mul_one] rw [hlast] have hstep : (∑ j ∈ Finset.range k, (j+1)*(k+1-j)) = (∑ j ∈ Finset.range k, (j+1)*(k-j)) + ∑ j ∈ Finset.range k, (j+1) := by rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro j hj rw [Finset.mem_range] at hj have hkj : k + 1 - j = (k - j) + 1 := by omega rw [hkj, mul_add, mul_one] rw [hstep] have hT := dnpg_sum_two k nlinarith [ih, hT]private lemma dnpg_arith (k : ℕ) : (∑ j ∈ Finset.range k, (j+1)*(k-j)) = Nat.choose (k+2) 3 := by have h1 := dnpg_sum_six k have h2 : 6 * Nat.choose (k+2) 3 = (k+2)*(k+1)*k := by have h := Nat.descFactorial_eq_factorial_mul_choose (k+2) 3 have hfac : (3:ℕ).factorial = 6 := by decide rw [hfac] at h rw [← h] simp [Nat.descFactorial] ring rw [show k*(k+1)*(k+2) = (k+2)*(k+1)*k from by ring] at h1 exact Nat.eq_of_mul_eq_mul_left (by decide) (h1.trans h2.symm)private lemma dnpg_sum_range_fin (k : ℕ) : (∑ j : Fin k, (j.val+1)*(k-j.val)) = Nat.choose (k+2) 3 := by rw [Fin.sum_univ_eq_sum_range (fun m => (m+1)*(k-m)) k] exact dnpg_arith ktheorem digraph_nested_parents_overlap_general (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k : ℕ) (low : Fin k → α) (q : α) (hinj : Function.Injective low) (hq : ∀ i, low i ≠ q) (htrans : ∀ i j : Fin k, i.val < j.val → D.Adj (low j) (low i)) (htarget : ∀ i, D.Adj (low i) q) (hparents : ∀ t : ℕ, 1 ≤ t → t ≤ k → k + 3 - t ≤ (Finset.univ.filter fun p : α => p ≠ q ∧ (∀ i, p ≠ low i) ∧ D.Adj p q ∧ ∀ i : Fin k, i.val < t → D.Adj p (low i)).card) : 2 * Nat.choose (k + 2) 3 ≤ (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card := by rw [← digraph_common_predecessor_overlap_incidence_identity] show 2 * Nat.choose (k+2) 3 ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) let Hp : Fin k → Finset α := fun j => Finset.univ.filter (fun p => p ≠ q ∧ (∀ i, p ≠ low i) ∧ D.Adj p q ∧ ∀ i : Fin k, i.val < j.val + 1 → D.Adj p (low i)) let Lt : Fin k → Finset α := fun j => (Finset.Ioi j).image low let Wf : Fin k → Finset α := fun j => Hp j ∪ Lt j let ι : Type := (Fin k) ⊕ (Σ j : Fin k, Fin j.val) let blk : ι → Fin k := fun i => match i with | Sum.inl j => j | Sum.inr p => p.1 let g : ι → Sym2 α := fun i => match i with | Sum.inl j => Sym2.mk q (low j) | Sum.inr p => Sym2.mk (low (p.2.castLT (Nat.lt_trans p.2.isLt p.1.isLt))) (low p.1) have hHp_card : ∀ j, k + 3 - (j.val+1) ≤ (Hp j).card := by intro j exact hparents (j.val+1) (by omega) (by omega) have hLt_card : ∀ j, (Lt j).card = k - 1 - j.val := by intro j show ((Finset.Ioi j).image low).card = k - 1 - j.val rw [Finset.card_image_of_injective _ hinj] exact Fin.card_Ioi j have hdisj : ∀ j, Disjoint (Hp j) (Lt j) := by intro j rw [Finset.disjoint_left] intro a ha hb simp only [Hp, Finset.mem_filter, Finset.mem_univ, true_and] at ha simp only [Lt, Finset.mem_image, Finset.mem_Ioi] at hb obtain ⟨j', _, rfl⟩ := hb exact ha.2.1 j' rfl have hWf_card : ∀ j, 2*(k - j.val) + 1 ≤ (Wf j).card := by intro j have hcard : (Wf j).card = (Hp j).card + (Lt j).card := Finset.card_union_of_disjoint (hdisj j) rw [hcard, hLt_card j] have h3 := hHp_card j have := j.isLt omega have hWf_prop : ∀ j (w : α), w ∈ Wf j → D.Adj w q ∧ (∀ i : Fin k, i.val < j.val+1 → D.Adj w (low i)) := by intro j w hw change w ∈ Hp j ∪ Lt j at hw rw [Finset.mem_union] at hw rcases hw with hw | hw · simp only [Hp, Finset.mem_filter, Finset.mem_univ, true_and] at hw exact ⟨hw.2.2.1, hw.2.2.2⟩ · simp only [Lt, Finset.mem_image, Finset.mem_Ioi] at hw obtain ⟨j', hj', rfl⟩ := hw refine ⟨htarget j', ?_⟩ intro i hi exact htrans i j' (by omega) have hWf_nonempty : ∀ j, (Wf j).Nonempty := by intro j apply Finset.card_pos.mp have := hWf_card j omega have hg_inj : Function.Injective g := by rintro (j | ⟨j, i⟩) (j' | ⟨j', i'⟩) heq · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [hinj h2] · exact absurd h1.symm (hq j') · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1.symm (hq _) · exact absurd h1.symm (hq j') · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (hq _) · exact absurd h2 (hq j) · dsimp only [g] at heq rw [Sym2.eq_iff] at heq rcases heq with ⟨h1, h2⟩ | ⟨h1, h2⟩ · have h1v : i.val = i'.val := by simpa only [Fin.val_castLT] using congrArg Fin.val (hinj h1) have h2v : j = j' := hinj h2 subst h2v rw [Fin.ext h1v] · have h1v : i.val = j'.val := by simpa only [Fin.val_castLT] using congrArg Fin.val (hinj h1) have h2v : j.val = i'.val := by simpa only [Fin.val_castLT] using congrArg Fin.val (hinj h2) have h3 := i.isLt have h4 := i'.isLt omega have hedge1 : ∀ j : Fin k, g (Sum.inl j) ∈ (digraph_common_predecessor_graph D).edgeFinset := by intro j dsimp only [g] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] obtain ⟨w, hw⟩ := hWf_nonempty j exact ⟨Ne.symm (hq j), w, (hWf_prop j w hw).1, (hWf_prop j w hw).2 j (by omega)⟩ have hedge2 : ∀ (j : Fin k) (i : Fin j.val), g (Sum.inr ⟨j, i⟩) ∈ (digraph_common_predecessor_graph D).edgeFinset := by intro j i dsimp only [g] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] refine ⟨?_, ?_⟩ · intro h have hv := congrArg Fin.val (hinj h) rw [Fin.val_castLT] at hv have := i.isLt omega · obtain ⟨w, hw⟩ := hWf_nonempty j exact ⟨w, (hWf_prop j w hw).2 _ (by rw [Fin.val_castLT]; omega), (hWf_prop j w hw).2 j (by omega)⟩ have hEfam_sub : (Finset.univ.image g) ⊆ (digraph_common_predecessor_graph D).edgeFinset := by intro e he rw [Finset.mem_image] at he obtain ⟨i, _, rfl⟩ := he rcases i with j | ⟨j, i⟩ · exact hedge1 j · exact hedge2 j i have hbound : ∀ i : ι, 2*(k - (blk i).val) ≤ (Finset.univ.filter (fun p => ∀ x, x ∈ g i → D.Adj p x)).card - 1 := by rintro (j | ⟨j, i⟩) · have hsub : Wf j ⊆ Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inl j) → D.Adj p x) := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] dsimp only [g] intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl · exact (hWf_prop j w hw).1 · exact (hWf_prop j w hw).2 j (by omega) have h1 : (Wf j).card ≤ (Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inl j) → D.Adj p x)).card := Finset.card_le_card hsub have h2 := hWf_card j dsimp only [blk] omega · have hsub : Wf j ⊆ Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inr ⟨j, i⟩) → D.Adj p x) := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] dsimp only [g] intro x hx rw [Sym2.mem_iff] at hx rcases hx with rfl | rfl · exact (hWf_prop j w hw).2 _ (by rw [Fin.val_castLT]; omega) · exact (hWf_prop j w hw).2 j (by omega) have h1 : (Wf j).card ≤ (Finset.univ.filter (fun p => ∀ x, x ∈ g (Sum.inr ⟨j, i⟩) → D.Adj p x)).card := Finset.card_le_card hsub have h2 := hWf_card j dsimp only [blk] omega have hval : (∑ i : ι, 2*(k - (blk i).val)) = 2 * ∑ j : Fin k, (j.val+1)*(k-j.val) := by dsimp only [ι, blk] rw [Fintype.sum_sum_type, Fintype.sum_sigma] simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] rw [← Finset.sum_add_distrib, Finset.mul_sum] apply Finset.sum_congr rfl intro x _ simp only [Nat.cast_id] ring calc 2 * Nat.choose (k+2) 3 = 2 * ∑ j : Fin k, (j.val+1)*(k-j.val) := by rw [dnpg_sum_range_fin] _ = ∑ i : ι, 2*(k - (blk i).val) := hval.symm _ ≤ ∑ i : ι, ((Finset.univ.filter (fun p => ∀ x, x ∈ g i → D.Adj p x)).card - 1) := Finset.sum_le_sum (fun i _ => hbound i) _ = ∑ e ∈ Finset.univ.image g, ((Finset.univ.filter (fun p => ∀ x, x ∈ e → D.Adj p x)).card - 1) := by rw [Finset.sum_image (s := Finset.univ) (g := g) (f := fun e => ((Finset.univ.filter (fun p => ∀ x, x ∈ e → D.Adj p x)).card - 1)) hg_inj.injOn] _ ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter (fun p => ∀ x, x ∈ e → D.Adj p x)).card - 1) := Finset.sum_le_sum_of_subset_of_nonneg hEfam_sub (fun i _ _ => Nat.zero_le _)