is_ap_tile_step_Icc_self
For any natural number k with [NeZero k], the initial interval Finset.Icc 1 k is an arithmetic progression tile of step k.
Statement
theorem is_ap_tile_step_Icc_self (k : ℕ) [NeZero k] :
is_ap_tile_step k (Finset.Icc 1 k)- Source
- arXiv:2611.05321 Definition 1.4
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_ap_tile_stepGiven a step parameter k : ℕ with [NeZero k], a finite subset A : Finset ℕ is an arithmetic progression tile with step k if for every…
Read back from the Lean
For every natural number $k$ with $k \ne 0$ (via [NeZero k]), the interval $\{1, \dots, k\}$ (Finset.Icc 1 k) satisfies is_ap_tile_step k.
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 theorem states that the interval {1, ..., k} contains exactly one representative of each residue class modulo k, making it an arithmetic progression tile of step k. For an arbitrary residue r ∈ ZMod k, the proof chooses the explicit candidate x = (r - 1).val + 1, which lies in {1, ..., k} and reduces to r. It then proves that any element y ∈ {1, ..., k} reducing to r must equal x because 0 ≤ y - 1 < k, matching the canonical representative (r - 1).val. Hence the fiber over r is the singleton {x}, which has cardinality 1.
Fix an arbitrary residue r ∈ ZMod k and define the candidate representative x = (r - 1).val + 1.
By definition of `is_ap_tile_step`, we need to show that for every residue class r modulo k, the set of elements in {1, ..., k} congruent to r has cardinality 1. We fix r and construct the candidate representative x by shifting r by -1, taking its canonical representative in {0, ..., k - 1}, and adding 1 back.
intro r let x := (r - 1).val + 1
x belongs to the interval {1, ..., k} and reduces to r modulo k.
Unfolding membership in the filtered interval with `Finset.mem_filter` and `Finset.mem_Icc`, we verify two conditions: first, 1 ≤ x ≤ k, which holds because x = (r - 1).val + 1 ≥ 1 by `Nat.le_add_left` and (r - 1).val < k by `ZMod.val_lt`; second, modulo k, casting x gives (r - 1).val + 1, which equals (r - 1) + 1 = r by `ZMod.natCast_zmod_val` and ring arithmetic.
uses
Finset.mem_filter,Finset.mem_Icc,Nat.le_add_left,ZMod.val_lt,ZMod.natCast_zmod_valhave hx_mem : x ∈ (Finset.Icc 1 k).filter (fun (a : ℕ) => (a : ZMod k) = r) := by rw [Finset.mem_filter, Finset.mem_Icc] refine ⟨⟨Nat.le_add_left 1 _, ZMod.val_lt (r - 1)⟩, ?_⟩ dsimp [x] push_cast rw [ZMod.natCast_zmod_val] ring
Any element y ∈ {1, ..., k} that reduces to r modulo k must equal x.
Suppose y ∈ {1, ..., k} satisfies y ≡ r (mod k). Subtracting 1 gives y - 1 ≡ r - 1 (mod k) by `Nat.cast_sub` and `Nat.cast_one`. Since 1 ≤ y ≤ k, we have y - 1 < k, so (y - 1) % k = y - 1 by `Nat.mod_eq_of_lt`. Taking canonical values in {0, ..., k - 1}, `ZMod.val_natCast` gives (r - 1).val = (y - 1) % k = y - 1. Linear arithmetic (`omega`) then concludes y = (r - 1).val + 1 = x.
uses
Finset.mem_filter,Finset.mem_Icc,Nat.cast_sub,Nat.cast_one,ZMod.val_natCast,Nat.mod_eq_of_lthave hx_uniq : ∀ y ∈ (Finset.Icc 1 k).filter (fun (a : ℕ) => (a : ZMod k) = r), y = x := by intro y hy rw [Finset.mem_filter, Finset.mem_Icc] at hy rcases hy with ⟨⟨hy1, hy2⟩, hyr⟩ have hcast : ((y - 1 : ℕ) : ZMod k) = r - 1 := by rw [Nat.cast_sub hy1, hyr, Nat.cast_one] have hval : ((y - 1 : ℕ) : ZMod k).val = (y - 1) % k := ZMod.val_natCast k (y - 1) have hmod : (y - 1) % k = y - 1 := Nat.mod_eq_of_lt (by omega) rw [hcast] at hval dsimp [x] omega
The subset of elements in {1, ..., k} reducing to r modulo k is precisely the singleton {x}.
By `Finset.eq_singleton_iff_unique_mem`, a finite set equals {x} if and only if x is in the set and every member equals x, both of which were established in the previous two steps.
uses
Finset.eq_singleton_iff_unique_memhave hs : (Finset.Icc 1 k).filter (fun (a : ℕ) => (a : ZMod k) = r) = {x} := by rw [Finset.eq_singleton_iff_unique_mem] exact ⟨hx_mem, hx_uniq⟩
The number of representatives of r in {1, ..., k} is 1.
Rewriting the filtered set with the singleton {x}, its cardinality is 1 by `Finset.card_singleton`.
uses
Finset.card_singletonrw [hs, Finset.card_singleton]
Finset.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.mem_filter- An element belongs to the filtered sub-finset {x ∈ s | p x} if and only if it belongs to s and satisfies predicate p.
Nat.le_add_left- For any natural numbers n and m, n ≤ m + n.
ZMod.val_lt- For a non-zero modulus n, the canonical representative of a ∈ ZMod n satisfies a.val < n.
ZMod.natCast_zmod_val- Casting the canonical integer representative a.val back into ZMod n yields a.
Nat.cast_sub- For natural numbers with m ≤ n, casting n - m into an additive group with 1 equals (n : R) - (m : R).
Nat.cast_one- The natural number 1 casts to 1 in any ring with 1.
ZMod.val_natCast- The canonical representative in ZMod n of a cast natural number a is a % n.
Nat.mod_eq_of_lt- If a < b for natural numbers, then a % b = a.
Finset.eq_singleton_iff_unique_mem- A finite set s is equal to the singleton {a} if and only if a ∈ s and every element of s equals a.
Finset.card_singleton- The cardinality of any singleton set {a} is 1.
- The proof shifts by 1 via `(r - 1).val + 1` to translate between the 1-based interval `{1, ..., k}` and the 0-based range `{0, ..., k - 1}` of `ZMod.val`.
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.
/-- The interval {1, ..., k} contains exactly one representative of each residue class modulo k. -/theorem is_ap_tile_step_Icc_self (k : ℕ) [NeZero k] : is_ap_tile_step k (Finset.Icc 1 k) := by intro r let x := (r - 1).val + 1 have hx_mem : x ∈ (Finset.Icc 1 k).filter (fun (a : ℕ) => (a : ZMod k) = r) := by rw [Finset.mem_filter, Finset.mem_Icc] refine ⟨⟨Nat.le_add_left 1 _, ZMod.val_lt (r - 1)⟩, ?_⟩ dsimp [x] push_cast rw [ZMod.natCast_zmod_val] ring have hx_uniq : ∀ y ∈ (Finset.Icc 1 k).filter (fun (a : ℕ) => (a : ZMod k) = r), y = x := by intro y hy rw [Finset.mem_filter, Finset.mem_Icc] at hy rcases hy with ⟨⟨hy1, hy2⟩, hyr⟩ have hcast : ((y - 1 : ℕ) : ZMod k) = r - 1 := by rw [Nat.cast_sub hy1, hyr, Nat.cast_one] have hval : ((y - 1 : ℕ) : ZMod k).val = (y - 1) % k := ZMod.val_natCast k (y - 1) have hmod : (y - 1) % k = y - 1 := Nat.mod_eq_of_lt (by omega) rw [hcast] at hval dsimp [x] omega have hs : (Finset.Icc 1 k).filter (fun (a : ℕ) => (a : ZMod k) = r) = {x} := by rw [Finset.eq_singleton_iff_unique_mem] exact ⟨hx_mem, hx_uniq⟩ rw [hs, Finset.card_singleton]