AFTD Auto-Formalizing Theoretical Domains

is_ap_tile_step_Icc_self

theoremverified

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.

  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.

    lines 4–5

      intro r
      let x := (r - 1).val + 1
  2. 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.

    lines 6–12

    uses Finset.mem_filter, Finset.mem_Icc, Nat.le_add_left, ZMod.val_lt, ZMod.natCast_zmod_val

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

    lines 13–23

    uses Finset.mem_filter, Finset.mem_Icc, Nat.cast_sub, Nat.cast_one, ZMod.val_natCast, Nat.mod_eq_of_lt

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

    lines 24–26

    uses Finset.eq_singleton_iff_unique_mem

      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⟩
  5. 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`.

    line 27

    uses Finset.card_singleton

      rw [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.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it