petersen_strip_witness_card
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
LinearOrderis aTotalPreorder. - 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 thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- petersen_strip_small_boundary_attainmentFor each natural number k ≥ 8, there exists a finite vertex set S in the generalized Petersen strip such that its boundary card is at most…
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.
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.
uses
Finset.disjoint_left,Finset.mem_image.mprw [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
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|.
uses
petersen_strip_witness_card_disjoint_uv,Finset.card_union_of_disjoint,Finset.card_image_of_injectiverw [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]
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.
uses
Finset.card_image_of_injective,Finset.card_range,Nat.add_left_cancel,Nat.cast_injectiverw [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)
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.
uses
Finset.mem_coe,Finset.mem_range,Finset.disjoint_left,Finset.mem_image.mp,Nat.cast_injective,lt_or_gt_of_neset 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
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.
uses
petersen_strip_witness_card_block,Finset.card_biUnion,Finset.sum_congr,Finset.sum_const,Finset.card_range,smul_eq_mulhave 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]
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.
uses
Finset.mem_biUnion,Finset.mem_range,Finset.mem_imageintro 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
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.
uses
beq_iff_eq,Nat.mod_ltintro 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 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.
uses
petersen_strip_witness_card_witness_parts,petersen_strip_witness_card_extra_not_mem_U,Finset.card_insert_of_notMemunfold 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]
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.
uses
Nat.div_le_self,petersen_strip_witness_card_U_eq,petersen_strip_witness_card_arithmetichave 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
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.
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]