AFTD Auto-Formalizing Theoretical Domains

digraph_nested_parents_overlap_general

theoremverified

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

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).

  1. 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.

    lines 1–5

    uses Finset.sum_range_succ

    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]
    
  2. 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.

    lines 6–25

    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_two

    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]
    
  3. 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.

    lines 26–38

    uses dnpg_sum_six, Nat.descFactorial_eq_factorial_mul_choose, Nat.descFactorial, Nat.eq_of_mul_eq_mul_left

    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)
    
  4. 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.

    lines 39–43

    uses Fin.sum_univ_eq_sum_range, dnpg_arith

    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 k
    
  5. 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.

    lines 44–60

    uses digraph_common_predecessor_overlap_incidence_identity

    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 := 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)
  6. 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.

    lines 61–68

    uses Nat.lt_trans

      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)
  7. 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.

    lines 69–91

    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_disjoint

      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
  8. 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.

    lines 92–108

    uses Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image, Finset.mem_Ioi

      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
  9. 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.

    lines 109–140

    uses Sym2.eq_iff, Fin.val_castLT, congrArg, Fin.ext

      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
  10. 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.

    lines 141–167

    uses SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Ne.symm, Fin.val_castLT, Finset.mem_image

      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
  11. 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).

    lines 168–198

    uses Finset.mem_filter, Finset.mem_univ, true_and, Sym2.mem_iff, Finset.card_le_card, Fin.val_castLT

      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
  12. 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.

    lines 199–207

    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_congr

      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
  13. 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.

    lines 208–218

    uses dnpg_sum_range_fin, Finset.sum_le_sum, Finset.sum_image, Finset.sum_le_sum_of_subset_of_nonneg, Nat.zero_le

      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 _)
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).

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 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 _)
See it in the graphDiscuss this resultChallenge it