AFTD Auto-Formalizing Theoretical Domains

op_1534_constant_word_deletion_envelope_eq

theoremverifiedformalization

For integers t ≥ 1, q ≥ 2, and n ≥ 1, and any threshold r, the t-deletion hinge sum of the all-zero word qary_all_zero_word q n (by omega) equals the closed-form upper envelope qary_constant_word_deletion_envelope t q n r.

Statement

theorem op_1534_constant_word_deletion_envelope_eq
    (t : ℕ) (ht : 1 ≤ t) (q : ℕ) (hq : 2 ≤ q) (n : ℕ) (hn : 1 ≤ n)
    (r : ℕ) :
    qary_multiple_deletion_hinge t q n r (qary_all_zero_word q n (by omega)) =
      qary_constant_word_deletion_envelope t q n r
Formalizes
arXiv:2407.10026 "Conditional entropies of k-deletion/insertion channels"
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • qary_multiple_deletion_hingeFor natural numbers t, q, n, and r, and a q-ary word y of length n (y : Fin n → Fin q), the t-deletion hinge sum is the sum over all words…
  • qary_all_zero_wordFor an alphabet size q with 1 ≤ q and length n, the all-zero word is the word in Fin n → Fin q taking constant value 0 (represented by ⟨0,…
  • qary_constant_word_deletion_envelopeFor deletion radius t, alphabet size q, length n, and threshold r, the explicit upper envelope for the constant-word deletion hinge sum is…
  • q_ary_subsequence_num_embeddingsFor words u of length m and w of length n over an alphabet of size q represented by Fin q, q_ary_subsequence_num_embeddings q m n u w is…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

For all natural numbers $t \ge 1$, $q \ge 2$, $n \ge 1$, and $r \ge 0$, the $q$-ary multiple deletion hinge quantity qary_multiple_deletion_hinge t q n r evaluated at the all-zero word of length $n$ over alphabet size $q$ is equal to the deletion envelope qary_constant_word_deletion_envelope t q n r.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof computes the t-deletion hinge sum of the all-zero word by classifying words x of length n + t according to their number of zeros z. First, it shows that any embedding of the length-n all-zero word into x corresponds bijectively to choosing an n-element subset of the positions where x is zero, giving z.choose n embeddings. Next, it determines that the number of words of length n + t with exactly z zeros is (n + t).choose z * (q - 1)^(n + t - z), by establishing a bijection between words with a fixed zero set and choices of non-zero symbols outside it. Finally, grouping the total sum by z ∈ {0, ..., n + t} and observing that terms with z < n vanish because z.choose n = 0 (and 0 - r = 0 in natural number arithmetic), the sum reduces to z ∈ [n, n + t], matching the deletion envelope definition.

  1. The forward map toFun and inverse map invFun between words with zero-set S and functions from Sᶜ into non-zero symbols are well-defined.

    For a word x whose zero-set is S, any index j ∉ S satisfies x(j) ≠ z0 by definition of the zero-set, so restricting x to Sᶜ gives a well-defined function into the non-zero symbols. Conversely, given a function g from Sᶜ to non-zero symbols, extending it by setting x(j) = z0 for j ∈ S and x(j) = g(j) for j ∉ S produces a word whose zero-set is exactly S, verified by checking the two cases j ∈ S and j ∉ S.

    lines 1–19

    uses op_1534_constant_word_deletion_envelope_eq_zset, dif_pos, iff_of_true, dif_neg, iff_of_false

    open Finset
    
    private def op_1534_constant_word_deletion_envelope_eq_zset {N q : ℕ} (x : Fin N → Fin q) (z0 : Fin q) : Finset (Fin N) :=
      Finset.univ.filter (fun j => x j = z0)
    
    private noncomputable def op_1534_constant_word_deletion_envelope_eq_zset_equiv {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) :
        {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} ≃ ({j : Fin N // j ∉ S} → {v : Fin q // v ≠ z0}) where
      toFun x := fun j => ⟨x.1 j.1, by
          intro h
          have hj : j.1 ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by simp [op_1534_constant_word_deletion_envelope_eq_zset, h]
          rw [x.2] at hj
          exact j.2 hj⟩
      invFun g := ⟨fun j => if h : j ∈ S then z0 else (g ⟨j, h⟩).1, by
          ext j
          simp only [op_1534_constant_word_deletion_envelope_eq_zset, mem_filter, mem_univ, true_and]
          by_cases h : j ∈ S
          · rw [dif_pos h]; exact iff_of_true rfl h
          · rw [dif_neg h]
            exact iff_of_false (g ⟨j, h⟩).2 h⟩
  2. The forward and inverse maps are mutual inverses, establishing an equivalence between words with zero-set S and functions from Sᶜ into non-zero symbols.

    Evaluating the round-trip of a word x at index j reproduces x(j): if j ∈ S then x(j) = z0, which matches the value assigned by the inverse map; if j ∉ S, the inverse map directly returns the restricted value x(j). In the other direction, evaluating the round-trip of a function g at j ∉ S immediately returns g(j) since j ∉ S triggers the else-branch of the definition.

    lines 20–33

    uses op_1534_constant_word_deletion_envelope_eq_zset, dif_neg

      left_inv := by
        intro x
        ext j
        by_cases h : j ∈ S
        · have hx : x.1 j = z0 := by
            have : j ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by rw [x.2]; exact h
            simpa [op_1534_constant_word_deletion_envelope_eq_zset] using this
          simp [h, hx]
        · simp [h]
      right_inv := by
        intro g
        ext j
        simp only [dif_neg j.2]
    
  3. The number of words x : Fin N → Fin q whose zero-set is S equals (q - 1)^(N - |S|).

    Using the equivalence op_1534_constant_word_deletion_envelope_eq_zset_equiv, the number of such words equals the number of functions from Sᶜ to {v : Fin q // v ≠ z0}. The domain has cardinality |Sᶜ| = N - |S| by set complementation in Fin N, and the codomain has cardinality q - 1 by removing the single element z0 from Fin q. The number of functions is therefore (q - 1)^(N - |S|).

    lines 34–47

    uses Fintype.card_congr, op_1534_constant_word_deletion_envelope_eq_zset_equiv, Fintype.card_fun, Fintype.card_subtype, Finset.card_compl, Fintype.card_fin, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ

    private theorem op_1534_constant_word_deletion_envelope_eq_card_zset_fiber {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) :
        Fintype.card {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} = (q - 1) ^ (N - S.card) := by
      rw [Fintype.card_congr (op_1534_constant_word_deletion_envelope_eq_zset_equiv z0 S), Fintype.card_fun]
      have h1 : Fintype.card {j : Fin N // j ∉ S} = N - S.card := by
        rw [Fintype.card_subtype]
        have hh : ({x : Fin N | x ∉ S} : Finset (Fin N)) = Sᶜ := by ext x; simp
        rw [hh, Finset.card_compl, Fintype.card_fin]
      have h2 : Fintype.card {v : Fin q // v ≠ z0} = q - 1 := by
        rw [Fintype.card_subtype]
        have hh : ({v : Fin q | v ≠ z0} : Finset (Fin q)) = (univ : Finset (Fin q)).erase z0 := by
          ext v; simp
        rw [hh, Finset.card_erase_of_mem (Finset.mem_univ z0), Finset.card_univ, Fintype.card_fin]
      rw [h1, h2]
    
  4. The set of words with exactly z zeros maps into the collection of z-element subsets of Fin N, partitioning the count fiberwise.

    The map sending a word x to its zero-set maps every word with z zeros to a subset of Fin N of size z (an element of powersetCard z univ). By fiberwise decomposition of finset cardinality (Finset.card_eq_sum_card_fiberwise), the total count of words with z zeros is the sum over all z-element subsets b of the number of words having zero-set equal to b.

    lines 48–58

    uses Finset.mem_powersetCard, Finset.subset_univ, Finset.card_eq_sum_card_fiberwise

    private theorem op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber {N q : ℕ} (z0 : Fin q) (z : ℕ) :
        (Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z)).card
          = N.choose z * (q - 1) ^ (N - z) := by
      have hmap : Set.MapsTo (fun x : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset x z0)
          ↑(Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z))
          ↑((univ : Finset (Fin N)).powersetCard z) := by
        intro x hx
        simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hx
        rw [Finset.mem_coe, Finset.mem_powersetCard]
        exact ⟨Finset.subset_univ _, hx⟩
      rw [Finset.card_eq_sum_card_fiberwise hmap]
  5. The number of words x : Fin N → Fin q with exactly z zeros is N.choose z * (q - 1)^(N - z).

    For every z-element subset b, the fiber of words whose zero-set is b has cardinality (q - 1)^(N - z) by op_1534_constant_word_deletion_envelope_eq_card_zset_fiber. Since this fiber size is constant across all b in powersetCard z univ, the sum equals the number of such subsets, which is N.choose z, multiplied by (q - 1)^(N - z).

    lines 59–75

    uses Finset.mem_powersetCard, Fintype.card_subtype, op_1534_constant_word_deletion_envelope_eq_card_zset_fiber, Finset.sum_congr, Finset.sum_const, Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul

      have hterm : ∀ b ∈ (univ : Finset (Fin N)).powersetCard z,
          {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b}.card
            = (q - 1) ^ (N - z) := by
        intro b hb
        rw [Finset.mem_powersetCard] at hb
        obtain ⟨-, hbc⟩ := hb
        have heq : {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b}
            = Finset.univ.filter (fun a : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset a z0 = b) := by
          ext a
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          constructor
          · rintro ⟨-, h⟩; exact h
          · intro h; exact ⟨by rw [h]; exact hbc, h⟩
        rw [heq, ← Fintype.card_subtype, op_1534_constant_word_deletion_envelope_eq_card_zset_fiber, hbc]
      rw [Finset.sum_congr rfl hterm, Finset.sum_const, Finset.card_powersetCard,
        Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul]
    
  6. Subsequence embeddings of the constant word of length n map to n-element subsets of the zero-positions via their image.

    A subsequence embedding of the all-z0 word into x is a strictly increasing map f : Fin n → Fin N whose values all equal z0. The image of f is a subset of the zero-positions of x. Because f is strictly monotonic, it is injective, so its image has size |Fin n| = n, yielding a well-defined map into the n-element subsets of the zero-positions.

    lines 76–91

    uses q_ary_subsequence_num_embeddings, Finset.card_powersetCard, Finset.card_bij, Finset.mem_powersetCard, Finset.mem_image, op_1534_constant_word_deletion_envelope_eq_zset, Finset.card_image_of_injective, Finset.card_univ, Fintype.card_fin

    private theorem op_1534_constant_word_deletion_envelope_eq_card_embeddings {n N q : ℕ} (z0 : Fin q) (x : Fin N → Fin q) :
        q_ary_subsequence_num_embeddings q n N (fun _ => z0) x = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n := by
      rw [q_ary_subsequence_num_embeddings]
      rw [← Finset.card_powersetCard]
      apply Finset.card_bij (fun f _ => Finset.image f Finset.univ)
      · intro f hf
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf
        obtain ⟨hmono, hval⟩ := hf
        rw [Finset.mem_powersetCard]
        refine ⟨?_, ?_⟩
        · intro j hj
          rw [Finset.mem_image] at hj
          obtain ⟨i, -, rfl⟩ := hj
          simp only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and]
          exact hval i
        · rw [Finset.card_image_of_injective _ hmono.injective, Finset.card_univ, Fintype.card_fin]
  7. The image map is a bijection, so the number of embeddings of the length-n constant word into x is |zset(x, z0)|.choose n.

    If two strictly monotonic maps f1, f2 from Fin n have the same image S, they are both order embeddings onto S; by uniqueness of order embeddings from Fin n (Finset.orderEmbOfFin_unique), f1 = f2, proving injectivity. Conversely, given any n-element subset S of the zero-positions, the canonical order embedding of S gives a strictly increasing map from Fin n into the zero-positions with image S, proving surjectivity. Thus embeddings are in bijection with n-element subsets of the zero-positions, whose count is |zset(x, z0)|.choose n.

    lines 92–110

    uses Finset.card_image_of_injective, Finset.card_univ, Fintype.card_fin, Finset.orderEmbOfFin_unique, Finset.mem_image_of_mem, Finset.mem_powersetCard, Finset.image_orderEmbOfFin_univ, op_1534_constant_word_deletion_envelope_eq_zset, Finset.orderEmbOfFin_mem

      · intro f1 hf1 f2 hf2 heq
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf1 hf2
        have hc : (Finset.image f1 Finset.univ).card = n := by
          rw [Finset.card_image_of_injective _ hf1.1.injective, Finset.card_univ, Fintype.card_fin]
        have e1 := Finset.orderEmbOfFin_unique hc
          (fun i => Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf1.1
        have e2 := Finset.orderEmbOfFin_unique hc
          (fun i => by rw [heq]; exact Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf2.1
        exact e1.trans e2.symm
      · intro S hS
        rw [Finset.mem_powersetCard] at hS
        obtain ⟨hsub, hcard⟩ := hS
        refine ⟨⇑(S.orderEmbOfFin hcard), ?_, Finset.image_orderEmbOfFin_univ S hcard⟩
        simp only [Finset.mem_filter, Finset.mem_univ, true_and]
        refine ⟨(S.orderEmbOfFin hcard).strictMono, fun i => ?_⟩
        simpa only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and] using
          hsub (Finset.orderEmbOfFin_mem S hcard i)
    
    /-- The multiple-deletion hinge sum of the all-zero word matches the explicit upper envelope. -/
  8. The hinge sum is rewritten with embeddings expressed as binomial coefficients, and every zero-count lies in {0, ..., n + t}.

    The all-zero word is identified with the constant word with value z0 = 0. By op_1534_constant_word_deletion_envelope_eq_card_embeddings, the number of embeddings into any word x of length n + t is |zset(x, z0)|.choose n. Since the zero-set of x is a subset of Fin (n + t), its cardinality is at most n + t, so it belongs to Finset.range (n + t + 1).

    lines 111–132

    uses qary_multiple_deletion_hinge, qary_constant_word_deletion_envelope, op_1534_constant_word_deletion_envelope_eq_card_embeddings, Finset.mem_range, Finset.filter_subset, Finset.card_le_card, Finset.card_univ, Fintype.card_fin

    theorem op_1534_constant_word_deletion_envelope_eq
        (t : ℕ) (ht : 1 ≤ t) (q : ℕ) (hq : 2 ≤ q) (n : ℕ) (hn : 1 ≤ n)
        (r : ℕ) :
        qary_multiple_deletion_hinge t q n r (qary_all_zero_word q n (by omega)) =
          qary_constant_word_deletion_envelope t q n r := by
      rw [qary_multiple_deletion_hinge, qary_constant_word_deletion_envelope]
      set z0 : Fin q := ⟨0, by omega⟩ with hz0
      have hzw : qary_all_zero_word q n (by omega) = (fun _ : Fin n => z0) := rfl
      rw [hzw]
      have hstep : ∀ x : Fin (n + t) → Fin q,
          q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x
            = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n :=
        fun x => op_1534_constant_word_deletion_envelope_eq_card_embeddings z0 x
      have hmap : ∀ x ∈ (Finset.univ : Finset (Fin (n + t) → Fin q)),
          (op_1534_constant_word_deletion_envelope_eq_zset x z0).card ∈ Finset.range (n + t + 1) := by
        intro x _
        rw [Finset.mem_range]
        have h1 : op_1534_constant_word_deletion_envelope_eq_zset x z0 ⊆ (Finset.univ : Finset (Fin (n + t))) :=
          Finset.filter_subset _ _
        have h2 := Finset.card_le_card h1
        rw [Finset.card_univ, Fintype.card_fin] at h2
        omega
  9. Partitioning words by their zero-count z expresses the hinge sum as ∑_{z=0}^{n+t} (n + t).choose z * (q - 1)^(n + t - z) * (z.choose n - r).

    Replacing the embeddings count with |zset(x, z0)|.choose n and regrouping the sum fiberwise by the zero-count z ∈ range (n + t + 1) using Finset.sum_fiberwise_of_maps_to', each fiber has constant summand z.choose n - r. Multiplying by the fiber size (n + t).choose z * (q - 1)^(n + t - z) gives the double sum evaluated as a single sum over z.

    lines 133–146

    uses Finset.sum_congr, Finset.sum_fiberwise_of_maps_to', Finset.sum_const, op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber, Nat.nsmul_eq_mul

      calc ∑ x : Fin (n + t) → Fin q, (q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x - r)
          = ∑ x : Fin (n + t) → Fin q, ((op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n - r) := by
            apply Finset.sum_congr rfl
            intro x _
            rw [hstep x]
        _ = ∑ z ∈ Finset.range (n + t + 1),
              ∑ x ∈ Finset.univ.filter (fun x : Fin (n + t) → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z),
                (z.choose n - r) := by
            exact (Finset.sum_fiberwise_of_maps_to' hmap (fun z => z.choose n - r)).symm
        _ = ∑ z ∈ Finset.range (n + t + 1),
              (((n + t).choose z * (q - 1) ^ (n + t - z)) * (z.choose n - r)) := by
            apply Finset.sum_congr rfl
            intro z _
            rw [Finset.sum_const, op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber, Nat.nsmul_eq_mul]
  10. The summation index restricts from {0, ..., n + t} to [n, n + t], completing the proof.

    For any z < n, the binomial coefficient z.choose n is 0 by Nat.choose_eq_zero_of_lt. In natural number arithmetic, 0 - r = 0, so the entire summand vanishes for all z < n. By Finset.sum_subset, the sum over Finset.range (n + t + 1) reduces to the sum over Finset.Icc n (n + t), which is exactly the definition of qary_constant_word_deletion_envelope.

    lines 147–158

    uses Finset.sum_subset, Finset.mem_Icc, Finset.mem_range, Nat.choose_eq_zero_of_lt

        _ = ∑ z ∈ Finset.Icc n (n + t), ((n + t).choose z * (q - 1) ^ (n + t - z) * (z.choose n - r)) := by
            refine (Finset.sum_subset ?_ ?_).symm
            · intro z hz
              rw [Finset.mem_Icc] at hz
              rw [Finset.mem_range]
              omega
            · intro z hz hznot
              rw [Finset.mem_range] at hz
              rw [Finset.mem_Icc] at hznot
              have hlt : z < n := by omega
              rw [Nat.choose_eq_zero_of_lt hlt]
              simp
op_1534_constant_word_deletion_envelope_eq_zset
the set of coordinate indices j where a word x equals a specified symbol z0
dif_pos
the value of a dependent if-then-else when the condition is true
iff_of_true
an equivalence between two propositions holds if both propositions are true
dif_neg
the value of a dependent if-then-else when the condition is false
iff_of_false
an equivalence between two propositions holds if both propositions are false
op_1534_constant_word_deletion_envelope_eq_zset_equiv
words whose zero-set equals S are in canonical bijection with functions from the complement of S into the non-zero alphabet symbols
Fintype.card_congr
equivalent finite types have the same cardinality
Fintype.card_fun
the number of functions from a finite type α to a finite type β is |β|^|α|
Fintype.card_subtype
the cardinality of a subtype {x // p x} equals the cardinality of the filtered finset {x | p x}
Finset.card_compl
the cardinality of the complement of a subset S in a finite universe is the universe cardinality minus |S|
Fintype.card_fin
the finite set Fin n of integers {0, ..., n - 1} has cardinality n
Finset.card_erase_of_mem
removing an element from a finset decreases its cardinality by 1
Finset.mem_univ
every element of a finite type belongs to the universal finset
Finset.card_univ
the cardinality of the universal finset of a finite type equals the type's cardinality
Finset.mem_powersetCard
a subset belongs to powersetCard n t if and only if it is a subset of t and has cardinality n
Finset.subset_univ
every finset of elements from a finite type is a subset of the universal finset
Finset.card_eq_sum_card_fiberwise
the cardinality of a set s equals the sum of the cardinalities of its fibers over a target finset t under a map f
op_1534_constant_word_deletion_envelope_eq_card_zset_fiber
the number of q-ary words of length N whose zero-set is a given subset S is (q - 1)^(N - |S|)
Finset.sum_congr
two sums over equal index sets are equal if their terms agree at every index
Finset.sum_const
the sum of a constant value b over a finset s equals |s| • b
Finset.card_powersetCard
the number of subsets of size n of a finset s is |s|.choose n
Nat.nsmul_eq_mul
scalar multiplication of natural numbers m • n equals their product m * n
q_ary_subsequence_num_embeddings
the number of strictly increasing embedding maps from word u into word w matching symbols at all positions
Finset.card_bij
two finsets have the same cardinality if there is a function between them that is well-defined, injective, and surjective
Finset.mem_image
an element belongs to the image of a finset under f if and only if it is f(a) for some element a in the finset
Finset.card_image_of_injective
the image of a finset under an injective map has the same cardinality as the finset
Finset.orderEmbOfFin_unique
a strictly monotonic map from Fin k onto a finset of size k is the unique order embedding from Fin k to that set
Finset.mem_image_of_mem
the image of an element of a finset under f belongs to the image finset
Finset.image_orderEmbOfFin_univ
the image of Fin k under the canonical order embedding of a size-k finset s is s itself
Finset.orderEmbOfFin_mem
the canonical order embedding of a finset s maps every element into s
qary_multiple_deletion_hinge
the sum over all words x of length n + t of the hinge quantity (embeddings(y, x) - r)
qary_constant_word_deletion_envelope
the explicit upper envelope sum over z from n to n + t of (n + t).choose z * (q - 1)^(n + t - z) * (z.choose n - r)
op_1534_constant_word_deletion_envelope_eq_card_embeddings
the number of subsequence embeddings of the constant word of length n into x equals |zset(x, z0)|.choose n
Finset.mem_range
a natural number m belongs to Finset.range n if and only if m < n
Finset.filter_subset
filtering a finset by a predicate yields a subset of the original finset
Finset.card_le_card
if s is a subset of t, then the cardinality of s is at most that of t
Finset.sum_fiberwise_of_maps_to'
a sum over s can be rewritten by partitioning into fibers over the values of a map g into t
op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber
the number of q-ary words of length N containing exactly z occurrences of symbol z0 is N.choose z * (q - 1)^(N - z)
Finset.sum_subset
a sum over a smaller finset equals a sum over a larger finset if the summand vanishes outside the smaller finset
Finset.mem_Icc
an element x belongs to the closed interval Icc a b if and only if a ≤ x and x ≤ b
Nat.choose_eq_zero_of_lt
the binomial coefficient n.choose k is zero whenever n < k

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 Finsetprivate def op_1534_constant_word_deletion_envelope_eq_zset {N q : ℕ} (x : Fin N → Fin q) (z0 : Fin q) : Finset (Fin N) :=  Finset.univ.filter (fun j => x j = z0)private noncomputable def op_1534_constant_word_deletion_envelope_eq_zset_equiv {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) :    {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} ≃ ({j : Fin N // j ∉ S} → {v : Fin q // v ≠ z0}) where  toFun x := fun j => ⟨x.1 j.1, by      intro h      have hj : j.1 ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by simp [op_1534_constant_word_deletion_envelope_eq_zset, h]      rw [x.2] at hj      exact j.2 hj⟩  invFun g := ⟨fun j => if h : j ∈ S then z0 else (g ⟨j, h⟩).1, by      ext j      simp only [op_1534_constant_word_deletion_envelope_eq_zset, mem_filter, mem_univ, true_and]      by_cases h : j ∈ S      · rw [dif_pos h]; exact iff_of_true rfl h      · rw [dif_neg h]        exact iff_of_false (g ⟨j, h⟩).2 h⟩  left_inv := by    intro x    ext j    by_cases h : j ∈ S    · have hx : x.1 j = z0 := by        have : j ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by rw [x.2]; exact h        simpa [op_1534_constant_word_deletion_envelope_eq_zset] using this      simp [h, hx]    · simp [h]  right_inv := by    intro g    ext j    simp only [dif_neg j.2]private theorem op_1534_constant_word_deletion_envelope_eq_card_zset_fiber {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) :    Fintype.card {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} = (q - 1) ^ (N - S.card) := by  rw [Fintype.card_congr (op_1534_constant_word_deletion_envelope_eq_zset_equiv z0 S), Fintype.card_fun]  have h1 : Fintype.card {j : Fin N // j ∉ S} = N - S.card := by    rw [Fintype.card_subtype]    have hh : ({x : Fin N | x ∉ S} : Finset (Fin N)) = Sᶜ := by ext x; simp    rw [hh, Finset.card_compl, Fintype.card_fin]  have h2 : Fintype.card {v : Fin q // v ≠ z0} = q - 1 := by    rw [Fintype.card_subtype]    have hh : ({v : Fin q | v ≠ z0} : Finset (Fin q)) = (univ : Finset (Fin q)).erase z0 := by      ext v; simp    rw [hh, Finset.card_erase_of_mem (Finset.mem_univ z0), Finset.card_univ, Fintype.card_fin]  rw [h1, h2]private theorem op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber {N q : ℕ} (z0 : Fin q) (z : ℕ) :    (Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z)).card      = N.choose z * (q - 1) ^ (N - z) := by  have hmap : Set.MapsTo (fun x : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset x z0)      ↑(Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z))      ↑((univ : Finset (Fin N)).powersetCard z) := by    intro x hx    simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hx    rw [Finset.mem_coe, Finset.mem_powersetCard]    exact ⟨Finset.subset_univ _, hx⟩  rw [Finset.card_eq_sum_card_fiberwise hmap]  have hterm : ∀ b ∈ (univ : Finset (Fin N)).powersetCard z,      {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b}.card        = (q - 1) ^ (N - z) := by    intro b hb    rw [Finset.mem_powersetCard] at hb    obtain ⟨-, hbc⟩ := hb    have heq : {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b}        = Finset.univ.filter (fun a : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset a z0 = b) := by      ext a      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      constructor      · rintro ⟨-, h⟩; exact h      · intro h; exact ⟨by rw [h]; exact hbc, h⟩    rw [heq, ← Fintype.card_subtype, op_1534_constant_word_deletion_envelope_eq_card_zset_fiber, hbc]  rw [Finset.sum_congr rfl hterm, Finset.sum_const, Finset.card_powersetCard,    Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul]private theorem op_1534_constant_word_deletion_envelope_eq_card_embeddings {n N q : ℕ} (z0 : Fin q) (x : Fin N → Fin q) :    q_ary_subsequence_num_embeddings q n N (fun _ => z0) x = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n := by  rw [q_ary_subsequence_num_embeddings]  rw [← Finset.card_powersetCard]  apply Finset.card_bij (fun f _ => Finset.image f Finset.univ)  · intro f hf    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf    obtain ⟨hmono, hval⟩ := hf    rw [Finset.mem_powersetCard]    refine ⟨?_, ?_⟩    · intro j hj      rw [Finset.mem_image] at hj      obtain ⟨i, -, rfl⟩ := hj      simp only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and]      exact hval i    · rw [Finset.card_image_of_injective _ hmono.injective, Finset.card_univ, Fintype.card_fin]  · intro f1 hf1 f2 hf2 heq    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf1 hf2    have hc : (Finset.image f1 Finset.univ).card = n := by      rw [Finset.card_image_of_injective _ hf1.1.injective, Finset.card_univ, Fintype.card_fin]    have e1 := Finset.orderEmbOfFin_unique hc      (fun i => Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf1.1    have e2 := Finset.orderEmbOfFin_unique hc      (fun i => by rw [heq]; exact Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf2.1    exact e1.trans e2.symm  · intro S hS    rw [Finset.mem_powersetCard] at hS    obtain ⟨hsub, hcard⟩ := hS    refine ⟨⇑(S.orderEmbOfFin hcard), ?_, Finset.image_orderEmbOfFin_univ S hcard⟩    simp only [Finset.mem_filter, Finset.mem_univ, true_and]    refine ⟨(S.orderEmbOfFin hcard).strictMono, fun i => ?_⟩    simpa only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and] using      hsub (Finset.orderEmbOfFin_mem S hcard i)/-- The multiple-deletion hinge sum of the all-zero word matches the explicit upper envelope. -/theorem op_1534_constant_word_deletion_envelope_eq    (t : ℕ) (ht : 1 ≤ t) (q : ℕ) (hq : 2 ≤ q) (n : ℕ) (hn : 1 ≤ n)    (r : ℕ) :    qary_multiple_deletion_hinge t q n r (qary_all_zero_word q n (by omega)) =      qary_constant_word_deletion_envelope t q n r := by  rw [qary_multiple_deletion_hinge, qary_constant_word_deletion_envelope]  set z0 : Fin q := ⟨0, by omega⟩ with hz0  have hzw : qary_all_zero_word q n (by omega) = (fun _ : Fin n => z0) := rfl  rw [hzw]  have hstep : ∀ x : Fin (n + t) → Fin q,      q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x        = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n :=    fun x => op_1534_constant_word_deletion_envelope_eq_card_embeddings z0 x  have hmap : ∀ x ∈ (Finset.univ : Finset (Fin (n + t) → Fin q)),      (op_1534_constant_word_deletion_envelope_eq_zset x z0).card ∈ Finset.range (n + t + 1) := by    intro x _    rw [Finset.mem_range]    have h1 : op_1534_constant_word_deletion_envelope_eq_zset x z0 ⊆ (Finset.univ : Finset (Fin (n + t))) :=      Finset.filter_subset _ _    have h2 := Finset.card_le_card h1    rw [Finset.card_univ, Fintype.card_fin] at h2    omega  calc ∑ x : Fin (n + t) → Fin q, (q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x - r)      = ∑ x : Fin (n + t) → Fin q, ((op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n - r) := by        apply Finset.sum_congr rfl        intro x _        rw [hstep x]    _ = ∑ z ∈ Finset.range (n + t + 1),          ∑ x ∈ Finset.univ.filter (fun x : Fin (n + t) → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z),            (z.choose n - r) := by        exact (Finset.sum_fiberwise_of_maps_to' hmap (fun z => z.choose n - r)).symm    _ = ∑ z ∈ Finset.range (n + t + 1),          (((n + t).choose z * (q - 1) ^ (n + t - z)) * (z.choose n - r)) := by        apply Finset.sum_congr rfl        intro z _        rw [Finset.sum_const, op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber, Nat.nsmul_eq_mul]    _ = ∑ z ∈ Finset.Icc n (n + t), ((n + t).choose z * (q - 1) ^ (n + t - z) * (z.choose n - r)) := by        refine (Finset.sum_subset ?_ ?_).symm        · intro z hz          rw [Finset.mem_Icc] at hz          rw [Finset.mem_range]          omega        · intro z hz hznot          rw [Finset.mem_range] at hz          rw [Finset.mem_Icc] at hznot          have hlt : z < n := by omega          rw [Nat.choose_eq_zero_of_lt hlt]          simp
See it in the graphDiscuss this resultChallenge it