AFTD Auto-Formalizing Theoretical Domains

petersen_strip_witness_card

theoremverified

For each natural number k ≥ 8, the witness set petersen_strip_witness k has cardinality k^2/2 + 1.

Statement

theorem petersen_strip_witness_card (k : ℕ) (hk : 8 ≤ k) : (petersen_strip_witness k).card = k ^ 2 / 2 + 1
Source
step towards petersen_strip_small_boundary_attainment
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • petersen_strip_witnessExplicit finite vertex set witness achieving the quadratic bound k^2/2 + 1 with external boundary at most 2k + 1 in the generalized…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • PetersenStripVertexThe vertex set of the infinite generalized Petersen strip, consisting of outer vertices u_i and inner vertices v_i indexed by integers i…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The witness set in the generalized Petersen strip is constructed as the disjoint union of a set of u-vertices indexed by U and a set of v-vertices indexed by V = U ∪ {extra}. The set U is formed by R pairwise disjoint arithmetic blocks of size m = k / 2, so |U| = R * m, and the extra element strictly exceeds every element in U, ensuring |V| = R * m + 1. The total size |U| + |V| = 2 * R * m + 1 then evaluates to k^2 / 2 + 1 via a parity case analysis on k.

  1. The u-vertex image of U and the v-vertex image of V are disjoint for any finite sets of integers U and V.

    To show the two images are disjoint, assume an element x belongs to both. By definition of image under u and v, x must simultaneously equal PetersenStripVertex.u a and PetersenStripVertex.v b for some a in U and b in V. Since u and v are distinct constructors of the inductive type PetersenStripVertex, this equality is contradictory by constructor injectivity and disjointness.

    lines 3–7

    uses Finset.disjoint_left, Finset.mem_image.mp

      rw [Finset.disjoint_left]
      intro x hx hy
      obtain ⟨a, _, rfl⟩ := Finset.mem_image.mp hx
      obtain ⟨b, _, hb⟩ := Finset.mem_image.mp hy
      injection hb
  2. The cardinality of the union (PetersenStripVertex.u '' U) ∪ (PetersenStripVertex.v '' V) equals |U| + |V|.

    Because the two image sets are disjoint, the cardinality of their union is the sum of their individual cardinalities. Furthermore, the constructors u and v are injective, so the cardinality of each image equals the cardinality of the underlying set, yielding |U| + |V|.

    lines 11–14

    uses petersen_strip_witness_card_disjoint_uv, Finset.card_union_of_disjoint, Finset.card_image_of_injective

      rw [Finset.card_union_of_disjoint (petersen_strip_witness_card_disjoint_uv U V)]
      have hu : Function.Injective PetersenStripVertex.u := by intro a b h; injection h
      have hv : Function.Injective PetersenStripVertex.v := by intro a b h; injection h
      rw [Finset.card_image_of_injective _ hu, Finset.card_image_of_injective _ hv]
  3. Each block {r * k + j | 0 ≤ j < m} has cardinality m.

    The map sending j to r * k + j is injective from ℕ to ℤ because integer casting is injective and addition of natural numbers has left cancellation. Since Finset.range m has cardinality m, its image under this injective map also has cardinality m.

    lines 18–22

    uses Finset.card_image_of_injective, Finset.card_range, Nat.add_left_cancel, Nat.cast_injective

      rw [Finset.card_image_of_injective]
      · exact Finset.card_range m
      · intro a b hab
        dsimp at hab
        exact Nat.add_left_cancel (Nat.cast_injective hab)
  4. The blocks t(r) = {r * k + j | 0 ≤ j < m} for r < R are pairwise disjoint when m ≤ k.

    Suppose r₁ ≠ r₂ < R and some x belongs to both t(r₁) and t(r₂). Then r₁ * k + j₁ = r₂ * k + j₂ for some j₁, j₂ < m. Since r₁ ≠ r₂, one must be strictly smaller than the other; assuming without loss of generality r₁ < r₂, we have r₂ ≥ r₁ + 1, which implies r₂ * k + j₂ ≥ (r₁ + 1) * k = r₁ * k + k > r₁ * k + j₁ because j₁ < m ≤ k. This contradicts equality, and the symmetric case r₂ < r₁ similarly yields a contradiction.

    lines 26–41

    uses Finset.mem_coe, Finset.mem_range, Finset.disjoint_left, Finset.mem_image.mp, Nat.cast_injective, lt_or_gt_of_ne

      set t : ℕ → Finset ℤ := fun r => (Finset.range m).image fun j => ((r * k + j : ℕ) : ℤ)
      have ht_disj : (↑(Finset.range R) : Set ℕ).PairwiseDisjoint t := by
        intro r1 hr1 r2 hr2 hne
        rw [Finset.mem_coe, Finset.mem_range] at hr1 hr2
        dsimp [Function.onFun]
        rw [Finset.disjoint_left]
        intro x hx hy
        obtain ⟨j1, hj1, rfl⟩ := Finset.mem_image.mp hx
        obtain ⟨j2, hj2, heq⟩ := Finset.mem_image.mp hy
        rw [Finset.mem_range] at hj1 hj2
        have h_eq : r1 * k + j1 = r2 * k + j2 := Nat.cast_injective heq.symm
        rcases lt_or_gt_of_ne hne with hlt | hgt
        · have : r1 * k + j1 < r2 * k + j2 := by nlinarith
          omega
        · have : r2 * k + j2 < r1 * k + j1 := by nlinarith
          omega
  5. The union of the R blocks, U = ⋃_{r < R} t(r), has cardinality R * m.

    Each block t(r) has size m by the block cardinality lemma. Since the blocks are pairwise disjoint, the cardinality of their union is the sum of their individual cardinalities, which is the sum of R copies of m, giving R * m.

    lines 42–48

    uses petersen_strip_witness_card_block, Finset.card_biUnion, Finset.sum_congr, Finset.sum_const, Finset.card_range, smul_eq_mul

      have ht_card : ∀ r ∈ Finset.range R, (t r).card = m := by
        intro r _
        exact petersen_strip_witness_card_block r k m
      rw [Finset.card_biUnion ht_disj]
      have : (∑ u ∈ Finset.range R, (t u).card) = ∑ u ∈ Finset.range R, m := by
        apply Finset.sum_congr rfl ht_card
      rw [this, Finset.sum_const, Finset.card_range, smul_eq_mul]
  6. The extra element R * k + m - 1 does not belong to U.

    If the extra element were in U, it would equal r * k + j for some r < R and j < m. But r ≤ R - 1 and j ≤ m - 1, together with k ≥ 8, imply r * k + j ≤ (R - 1) * k + m - 1 = R * k - k + m - 1 < R * k + m - 1, a strict inequality that contradicts equality.

    lines 53–66

    uses Finset.mem_biUnion, Finset.mem_range, Finset.mem_image

      intro hmem
      rw [Finset.mem_biUnion] at hmem
      rcases hmem with ⟨r, hr, hj⟩
      rw [Finset.mem_range] at hr
      rw [Finset.mem_image] at hj
      rcases hj with ⟨j, hj, heq⟩
      rw [Finset.mem_range] at hj
      have hr_le : (r : ℤ) ≤ (R : ℤ) - 1 := by omega
      have hj_le : (j : ℤ) ≤ (m : ℤ) - 1 := by omega
      have hk_ge : 8 ≤ (k : ℤ) := by omega
      have h_bound : ((r * k + j : ℕ) : ℤ) < (R : ℤ) * (k : ℤ) + (m : ℤ) - 1 := by
        push_cast
        nlinarith
      omega
  7. The product identity 2 * R * m = k^2 / 2 holds for m = k / 2 and R = if k % 2 == 0 then m else m + 1.

    We split into two cases on whether k is even or odd. If k is even, k = 2m and R = m, so 2 * R * m = 2m^2, which matches (2m)^2 / 2 = 2m^2. If k is odd, k = 2m + 1 and R = m + 1, so 2 * R * m = 2(m + 1)m = 2m^2 + 2m, which matches (2m + 1)^2 / 2 = (4m^2 + 4m + 1) / 2 = 2m^2 + 2m under integer division.

    lines 72–85

    uses beq_iff_eq, Nat.mod_lt

      intro m R
      dsimp [R, m]
      split_ifs with h
      · rw [beq_iff_eq] at h
        have hk : k = 2 * (k / 2) := by omega
        conv_rhs => rw [hk]
        have : (2 * (k / 2)) ^ 2 = 2 * (2 * (k / 2) * (k / 2)) := by ring
        omega
      · rw [beq_iff_eq] at h
        have : k % 2 < 2 := Nat.mod_lt k (by decide)
        have hk : k = 2 * (k / 2) + 1 := by omega
        conv_rhs => rw [hk]
        have : (2 * (k / 2) + 1) ^ 2 = 2 * (2 * (k / 2 + 1) * (k / 2)) + 1 := by ring
        omega
  8. The cardinality of the witness set equals |U| + (|U| + 1).

    Unfolding the definition of the witness set, it is the union of the u-image of U and the v-image of V = insert extra U. By the decomposition lemma, its size is |U| + |V|. Since the extra element is not in U, inserting it increases the cardinality by 1, so |V| = |U| + 1.

    lines 89–95

    uses petersen_strip_witness_card_witness_parts, petersen_strip_witness_card_extra_not_mem_U, Finset.card_insert_of_notMem

      unfold petersen_strip_witness
      rw [petersen_strip_witness_card_witness_parts]
      set m := k / 2
      set R := if (k % 2 == 0) = true then m else m + 1
      set U : Finset ℤ := (Finset.range R).biUnion fun r => (Finset.range m).image fun j => ((r * k + j : ℕ) : ℤ)
      have h_not_mem : ((R : ℤ) * (k : ℤ) + (m : ℤ) - 1) ∉ U := petersen_strip_witness_card_extra_not_mem_U k R m hk
      rw [Finset.card_insert_of_notMem h_not_mem]
  9. The cardinality of petersen_strip_witness k equals k^2 / 2 + 1.

    Since m = k / 2 ≤ k, the block union lemma gives |U| = R * m. The total cardinality is therefore R * m + (R * m + 1) = 2 * R * m + 1. Substituting the arithmetic identity 2 * R * m = k^2 / 2 yields k^2 / 2 + 1.

    lines 96–100

    uses Nat.div_le_self, petersen_strip_witness_card_U_eq, petersen_strip_witness_card_arithmetic

      have hm : m ≤ k := Nat.div_le_self k 2
      have hU : U.card = R * m := petersen_strip_witness_card_U_eq k R m hm
      rw [hU]
      have harith : 2 * R * m = k ^ 2 / 2 := petersen_strip_witness_card_arithmetic k
      rw [show R * m + (R * m + 1) = 2 * R * m + 1 by ring, harith]
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first set belongs to the second set.
Finset.mem_image.mp
If an element belongs to the image of a set under a function, then it is the function's value at some element of that set.
petersen_strip_witness_card_disjoint_uv
The images of any two sets of integers under the vertex constructors u and v are disjoint.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their individual cardinalities.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the set.
Finset.card_range
The range {0, ..., n - 1} has cardinality n.
Nat.add_left_cancel
If n + m = n + k for natural numbers, then m = k.
Nat.cast_injective
The canonical cast from the natural numbers into a ring of characteristic zero is injective.
Finset.mem_coe
An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
Finset.mem_range
A natural number m belongs to the range of n if and only if m < n.
lt_or_gt_of_ne
Two unequal elements in a linear order satisfy either a < b or b < a.
petersen_strip_witness_card_block
The image of {0, ..., m - 1} under the map j ↦ r * k + j has cardinality m.
Finset.card_biUnion
The cardinality of a union of pairwise disjoint finite sets is the sum of their individual cardinalities.
Finset.sum_congr
Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set multiplied by that value.
smul_eq_mul
Scalar multiplication of elements in a ring equals standard multiplication.
Finset.mem_biUnion
An element belongs to a big union of indexed sets if and only if it belongs to one of the indexed sets.
Finset.mem_image
An element belongs to the image of a set under a function if and only if it is the image of some element in that set.
beq_iff_eq
Boolean equality between two terms holds if and only if the terms are propositionally equal.
Nat.mod_lt
The remainder of dividing a natural number x by a positive natural number y is strictly less than y.
petersen_strip_witness_card_witness_parts
The union of the u-image of U and the v-image of V has cardinality |U| + |V|.
petersen_strip_witness_card_extra_not_mem_U
For k ≥ 8, the integer R * k + m - 1 does not belong to the block union U.
Finset.card_insert_of_notMem
Inserting an element into a finite set that does not already contain it increases the cardinality by 1.
Nat.div_le_self
For any natural numbers n and k, the quotient n / k is at most n.
petersen_strip_witness_card_U_eq
If m ≤ k, the union of R blocks of size m of the form {r * k + j | j < m} has cardinality R * m.
petersen_strip_witness_card_arithmetic
For m = k / 2 and R = m (if k is even) or m + 1 (if k is odd), the product 2 * R * m equals k^2 / 2.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma petersen_strip_witness_card_disjoint_uv (U V : Finset ℤ) :    Disjoint (Finset.image PetersenStripVertex.u U) (Finset.image PetersenStripVertex.v V) := by  rw [Finset.disjoint_left]  intro x hx hy  obtain ⟨a, _, rfl⟩ := Finset.mem_image.mp hx  obtain ⟨b, _, hb⟩ := Finset.mem_image.mp hy  injection hblemma petersen_strip_witness_card_witness_parts (U V : Finset ℤ) :    (Finset.image PetersenStripVertex.u U ∪ Finset.image PetersenStripVertex.v V).card = U.card + V.card := by  rw [Finset.card_union_of_disjoint (petersen_strip_witness_card_disjoint_uv U V)]  have hu : Function.Injective PetersenStripVertex.u := by intro a b h; injection h  have hv : Function.Injective PetersenStripVertex.v := by intro a b h; injection h  rw [Finset.card_image_of_injective _ hu, Finset.card_image_of_injective _ hv]lemma petersen_strip_witness_card_block (r k m : ℕ) :    ((Finset.range m).image (fun (j : ℕ) => ((r * k + j : ℕ) : ℤ))).card = m := by  rw [Finset.card_image_of_injective]  · exact Finset.card_range m  · intro a b hab    dsimp at hab    exact Nat.add_left_cancel (Nat.cast_injective hab)lemma petersen_strip_witness_card_U_eq (k R m : ℕ) (hm : m ≤ k) :    ((Finset.range R).biUnion (fun r => (Finset.range m).image (fun j => ((r * k + j : ℕ) : ℤ)))).card = R * m := by  set t : ℕ → Finset ℤ := fun r => (Finset.range m).image fun j => ((r * k + j : ℕ) : ℤ)  have ht_disj : (↑(Finset.range R) : Set ℕ).PairwiseDisjoint t := by    intro r1 hr1 r2 hr2 hne    rw [Finset.mem_coe, Finset.mem_range] at hr1 hr2    dsimp [Function.onFun]    rw [Finset.disjoint_left]    intro x hx hy    obtain ⟨j1, hj1, rfl⟩ := Finset.mem_image.mp hx    obtain ⟨j2, hj2, heq⟩ := Finset.mem_image.mp hy    rw [Finset.mem_range] at hj1 hj2    have h_eq : r1 * k + j1 = r2 * k + j2 := Nat.cast_injective heq.symm    rcases lt_or_gt_of_ne hne with hlt | hgt    · have : r1 * k + j1 < r2 * k + j2 := by nlinarith      omega    · have : r2 * k + j2 < r1 * k + j1 := by nlinarith      omega  have ht_card : ∀ r ∈ Finset.range R, (t r).card = m := by    intro r _    exact petersen_strip_witness_card_block r k m  rw [Finset.card_biUnion ht_disj]  have : (∑ u ∈ Finset.range R, (t u).card) = ∑ u ∈ Finset.range R, m := by    apply Finset.sum_congr rfl ht_card  rw [this, Finset.sum_const, Finset.card_range, smul_eq_mul]lemma petersen_strip_witness_card_extra_not_mem_U (k R m : ℕ) (hk : 8 ≤ k) :    ((R : ℤ) * (k : ℤ) + (m : ℤ) - 1) ∉      ((Finset.range R).biUnion (fun r => (Finset.range m).image (fun j => ((r * k + j : ℕ) : ℤ)))) := by  intro hmem  rw [Finset.mem_biUnion] at hmem  rcases hmem with ⟨r, hr, hj⟩  rw [Finset.mem_range] at hr  rw [Finset.mem_image] at hj  rcases hj with ⟨j, hj, heq⟩  rw [Finset.mem_range] at hj  have hr_le : (r : ℤ) ≤ (R : ℤ) - 1 := by omega  have hj_le : (j : ℤ) ≤ (m : ℤ) - 1 := by omega  have hk_ge : 8 ≤ (k : ℤ) := by omega  have h_bound : ((r * k + j : ℕ) : ℤ) < (R : ℤ) * (k : ℤ) + (m : ℤ) - 1 := by    push_cast    nlinarith  omegalemma petersen_strip_witness_card_arithmetic (k : ℕ) :    let m := k / 2    let R := if (k % 2 == 0) = true then m else m + 1    2 * R * m = k ^ 2 / 2 := by  intro m R  dsimp [R, m]  split_ifs with h  · rw [beq_iff_eq] at h    have hk : k = 2 * (k / 2) := by omega    conv_rhs => rw [hk]    have : (2 * (k / 2)) ^ 2 = 2 * (2 * (k / 2) * (k / 2)) := by ring    omega  · rw [beq_iff_eq] at h    have : k % 2 < 2 := Nat.mod_lt k (by decide)    have hk : k = 2 * (k / 2) + 1 := by omega    conv_rhs => rw [hk]    have : (2 * (k / 2) + 1) ^ 2 = 2 * (2 * (k / 2 + 1) * (k / 2)) + 1 := by ring    omega/-- The finite witness set in the generalized Petersen strip has cardinality k^2 / 2 + 1 for all k ≥ 8. -/theorem petersen_strip_witness_card (k : ℕ) (hk : 8 ≤ k) : (petersen_strip_witness k).card = k ^ 2 / 2 + 1 := by  unfold petersen_strip_witness  rw [petersen_strip_witness_card_witness_parts]  set m := k / 2  set R := if (k % 2 == 0) = true then m else m + 1  set U : Finset ℤ := (Finset.range R).biUnion fun r => (Finset.range m).image fun j => ((r * k + j : ℕ) : ℤ)  have h_not_mem : ((R : ℤ) * (k : ℤ) + (m : ℤ) - 1) ∉ U := petersen_strip_witness_card_extra_not_mem_U k R m hk  rw [Finset.card_insert_of_notMem h_not_mem]  have hm : m ≤ k := Nat.div_le_self k 2  have hU : U.card = R * m := petersen_strip_witness_card_U_eq k R m hm  rw [hU]  have harith : 2 * R * m = k ^ 2 / 2 := petersen_strip_witness_card_arithmetic k  rw [show R * m + (R * m + 1) = 2 * R * m + 1 by ring, harith]
See it in the graphDiscuss this resultChallenge it