AFTD Auto-Formalizing Theoretical Domains

epstein_remoteness_of_is_stein_number

theoremverifiedformalization

For every natural number n, if n is an E. P. Stein number (is_stein_number n), then its remoteness epstein_remoteness n is equal to 2.

Statement

theorem epstein_remoteness_of_is_stein_number (n : ℕ) (h : is_stein_number n) : epstein_remoteness n = 2
Formalizes
arXiv:2611.05898 Def 1.3
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • epstein_remotenessThe remoteness epstein_remoteness n of position n in Epstein's game, defined as the least natural number k such that n ∈…
  • is_stein_numberA positive integer n is an E. P. Stein number if, with m = Nat.sqrt n, both n - m^2 and n + m^2 are positive squares.
  • epstein_remoteness_levelThe set epstein_remoteness_level k of positions with remoteness k in Epstein's put-or-take game: level 0 contains only 0; for odd k =…
  • epstein_upThe up-move in Epstein's put-or-take-a-square game, defined as epstein_up n = n + (Nat.sqrt n)^2.
  • epstein_downThe down-move in Epstein's put-or-take-a-square game, defined as epstein_down n = n - (Nat.sqrt n)^2.
Used by 1

Read back from the Lean

For every natural number $n$, if $n$ is a Stein number (that is, $n > 0$, $n - \lfloor\sqrt{n}\rfloor^2 > 0$, $n - \lfloor\sqrt{n}\rfloor^2$ is a square, $n + \lfloor\sqrt{n}\rfloor^2 > 0$, and $n + \lfloor\sqrt{n}\rfloor^2$ is a square), then the Epstein remoteness of $n$ is equal to 2 (as an element of WithTop ℕ).

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

In Epstein's game, remoteness level 1 consists of nonzero positions that can reach 0 in one move (including all positive squares), and level 2 consists of nonzero positions from which both moves land in level 1. By definition, if $n$ is an E. P. Stein number, then both $\text{epstein\_down}(n)$ and $\text{epstein\_up}(n)$ are positive perfect squares, placing both moves in level 1 and thus placing $n$ in level 2. Because $n > 0$, it is not in level 0, and because neither move lands on 0, it is not in level 1. Therefore, 2 is the minimal level containing $n$, so the remoteness of $n$ is 2.

  1. Remoteness level 1 consists of all nonzero positions whose down-move or up-move lands on 0.

    Unfolding `epstein_remoteness_level 1` gives the odd-level case with parameter $m = 0 / 2 = 0$. The requirement that both moves avoid all even levels strictly below 0 is vacuously true ($j < 0$), and since level 0 is $\{0\}$, the condition simplifies to $n \ne 0$ and at least one move landing on 0.

    lines 4–7

    uses epstein_remoteness_level.eq_def, epstein_remoteness_level.eq_1

      rw [epstein_remoteness_level.eq_def 1]
      dsimp only
      rw [epstein_remoteness_level.eq_1]
      simp
  2. Remoteness level 2 consists of all nonzero positions both of whose moves land in remoteness level 1.

    Unfolding `epstein_remoteness_level 2` gives the even-level case with $m = (1 - 1)/2 = 0$. Both moves must land in $\bigcup_{j \le 0} \text{level}(2j + 1) = \text{level } 1$, and at least one move must land in level 1, which holds automatically once both do.

    lines 12–27

    uses epstein_remoteness_level.eq_def, Set.mem_iUnion, exists_prop, Set.mem_ofPred_eq, le_refl, Or.inl

      rw [epstein_remoteness_level.eq_def 2]
      dsimp only
      simp only [Set.mem_iUnion, exists_prop]
      ext n
      simp only [Set.mem_ofPred_eq]
      constructor
      · rintro ⟨h0, h1, h2, _⟩
        refine ⟨h0, ?_, ?_⟩
        · obtain ⟨i, hi, hmem⟩ := h1
          interval_cases i
          simpa using hmem
        · obtain ⟨i, hi, hmem⟩ := h2
          interval_cases i
          simpa using hmem
      · rintro ⟨h0, h1, h2⟩
        exact ⟨h0, ⟨0, le_refl 0, h1⟩, ⟨0, le_refl 0, h2⟩, Or.inl h1⟩
  3. Every positive perfect square belongs to remoteness level 1.

    For a positive square $x = r^2$, its integer square root is $r$, so its down-move is $r^2 - (\lfloor \sqrt{r^2} \rfloor)^2 = r^2 - r^2 = 0$. Since $x \ne 0$ and its down-move lands on 0, the characterization of level 1 places $x$ in level 1.

    lines 32–35

    uses epstein_remoteness_of_is_stein_number_level_one_eq, Or.inl, Nat.sqrt_eq, pow_two

      rw [epstein_remoteness_of_is_stein_number_level_one_eq]
      refine ⟨hx.ne', Or.inl ?_⟩
      obtain ⟨r, rfl⟩ := hsq
      simp [epstein_down, Nat.sqrt_eq, pow_two]
  4. For any E. P. Stein number $n$, both $\text{epstein\_down}(n)$ and $\text{epstein\_up}(n)$ belong to remoteness level 1.

    By definition of an E. P. Stein number, $n > 0$, $\text{epstein\_down}(n) > 0$ is a square, and $\text{epstein\_up}(n) > 0$ is a square. Applying the lemma that positive squares lie in level 1 shows that both moves land in level 1.

    lines 39–48

    uses epstein_remoteness_of_is_stein_number_pos_square_mem_level_one

      classical
      have hn0 : 0 < n := h.1
      have hd0 : 0 < epstein_down n := h.2.1
      have hdsq : IsSquare (epstein_down n) := h.2.2.1
      have hu0 : 0 < epstein_up n := h.2.2.2.1
      have husq : IsSquare (epstein_up n) := h.2.2.2.2
      have hdlvl : epstein_down n ∈ epstein_remoteness_level 1 :=
        epstein_remoteness_of_is_stein_number_pos_square_mem_level_one hd0 hdsq
      have hulvl : epstein_up n ∈ epstein_remoteness_level 1 :=
        epstein_remoteness_of_is_stein_number_pos_square_mem_level_one hu0 husq
  5. The number $n$ belongs to remoteness level 2.

    Since $n > 0$ (so $n \ne 0$) and both its down-move and up-move belong to level 1, the characterization of level 2 proves that $n \in \text{epstein\_remoteness\_level } 2$.

    lines 49–51

    uses epstein_remoteness_of_is_stein_number_level_two_eq

      have hmem2 : n ∈ epstein_remoteness_level 2 := by
        rw [epstein_remoteness_of_is_stein_number_level_two_eq]
        exact ⟨hn0.ne', hdlvl, hulvl⟩
  6. The number $n$ does not belong to remoteness level 0 or remoteness level 1.

    Remoteness level 0 contains only 0, but $n > 0$, so $n \notin \text{level } 0$. Remoteness level 1 requires at least one move to equal 0, but both $\text{epstein\_down}(n) > 0$ and $\text{epstein\_up}(n) > 0$, so $n \notin \text{level } 1$.

    lines 52–57

    uses epstein_remoteness_level.eq_1, epstein_remoteness_of_is_stein_number_level_one_eq

      have hn0lvl : n ∉ epstein_remoteness_level 0 := by
        rw [epstein_remoteness_level.eq_1]
        simp [hn0.ne']
      have hn1lvl : n ∉ epstein_remoteness_level 1 := by
        rw [epstein_remoteness_of_is_stein_number_level_one_eq]
        simp [hd0.ne', hu0.ne']
  7. The remoteness $\text{epstein\_remoteness}(n)$ evaluates to the minimal index $k$ such that $n$ is in level $k$.

    Because $n \in \text{level } 2$, there exists a level containing $n$. By definition of `epstein_remoteness`, the conditional reduces via `dif_pos` to `some (Nat.find hex)`, where `Nat.find hex` is the smallest level index containing $n$.

    lines 58–63

    uses epstein_remoteness.eq_def, dif_pos

      have hex : ∃ k, n ∈ epstein_remoteness_level k := ⟨2, hmem2⟩
      have hstep : epstein_remoteness n = (some (Nat.find hex) : WithTop ℕ) := by
        rw [epstein_remoteness.eq_def]
        exact @dif_pos (c := ∃ k, n ∈ epstein_remoteness_level k) (h := Classical.propDecidable _) hex
          (α := WithTop ℕ) (t := fun hh => @Option.some ℕ (Nat.find (p := fun k => n ∈ epstein_remoteness_level k) hh))
          (e := fun _ => ⊤)
  8. The minimal level index containing $n$ is equal to 2.

    The index `Nat.find hex` is at most 2 because $n \in \text{level } 2$. Since $n \notin \text{level } 0$ and $n \notin \text{level } 1$, the index cannot be 0 or 1. Linear arithmetic over $\mathbb{N}$ (`omega`) concludes that the minimal index must be exactly 2.

    lines 64–73

    uses Nat.find_spec, Nat.find_min'

      have hfind : Nat.find hex = 2 := by
        have hspec : n ∈ epstein_remoteness_level (Nat.find hex) := Nat.find_spec hex
        have hle : Nat.find hex ≤ 2 := Nat.find_min' hex hmem2
        have hne0 : Nat.find hex ≠ 0 := by
          intro hh
          exact hn0lvl (hh ▸ hspec)
        have hne1 : Nat.find hex ≠ 1 := by
          intro hh
          exact hn1lvl (hh ▸ hspec)
        omega
  9. The remoteness $\text{epstein\_remoteness}(n)$ equals 2.

    Substituting the value $\text{Nat.find hex} = 2$ into the expression for remoteness simplifies it to $2$.

    lines 74–75

      rw [hstep, hfind]
      rfl
epstein_remoteness.eq_def
The definition of `epstein_remoteness n`, which evaluates to `some (Nat.find h)` if `n` belongs to some remoteness level, and $\top$ otherwise.
epstein_remoteness_level.eq_1
The base case of the remoteness levels: `epstein_remoteness_level 0 = {0}`.
epstein_remoteness_level.eq_def
The recursive definition of the remoteness levels in Epstein's game.
epstein_remoteness_of_is_stein_number_level_one_eq
The characterization of remoteness level 1 as the set of nonzero numbers whose down-move or up-move lands on 0.
epstein_remoteness_of_is_stein_number_level_two_eq
The characterization of remoteness level 2 as the set of nonzero numbers both of whose moves land in remoteness level 1.
epstein_remoteness_of_is_stein_number_pos_square_mem_level_one
Every positive perfect square belongs to remoteness level 1 in Epstein's game.
exists_prop
An existential quantifier over a proposition, $\exists (\_ : a), b$, is equivalent to the conjunction $a \wedge b$.
dif_pos
A dependent if-then-else `if h : c then t else e` reduces to $t$ when $c$ is true.
le_refl
The reflexivity of inequality: $a \le a$.
Nat.sqrt_eq
For any natural number $n$, the integer square root of $n \cdot n$ equals $n$.
Nat.find_min'
The value returned by `Nat.find` is less than or equal to any natural number satisfying the predicate.
Nat.find_spec
The value returned by `Nat.find` satisfies the given predicate.
Or.inl
Introduces a disjunction $a \vee b$ from a proof of its left disjunct $a$.
pow_two
For any element $a$ in a monoid, $a^2 = a \cdot a$.
Set.mem_iUnion
An element belongs to a union $\bigcup_i s_i$ if and only if it belongs to $s_i$ for some index $i$.
Set.mem_ofPred_eq
An element $x$ belongs to a set defined by comprehension $\{y \mid p(y)\}$ if and only if $p(x)$ holds.

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 remoteness level 1 of Epstein's game is exactly the set of nonzero positions whose down- or up-move lands on 0. -/lemma epstein_remoteness_of_is_stein_number_level_one_eq :    epstein_remoteness_level 1 = {n : ℕ | n ≠ 0 ∧ (epstein_down n = 0 ∨ epstein_up n = 0)} := by  rw [epstein_remoteness_level.eq_def 1]  dsimp only  rw [epstein_remoteness_level.eq_1]  simp/-- The remoteness level 2 of Epstein's game is exactly the set of nonzero positions both of whose moves land in level 1. -/lemma epstein_remoteness_of_is_stein_number_level_two_eq :    epstein_remoteness_level 2 = {n : ℕ | n ≠ 0 ∧ epstein_down n ∈ epstein_remoteness_level 1 ∧ epstein_up n ∈ epstein_remoteness_level 1} := by  rw [epstein_remoteness_level.eq_def 2]  dsimp only  simp only [Set.mem_iUnion, exists_prop]  ext n  simp only [Set.mem_ofPred_eq]  constructor  · rintro ⟨h0, h1, h2, _⟩    refine ⟨h0, ?_, ?_⟩    · obtain ⟨i, hi, hmem⟩ := h1      interval_cases i      simpa using hmem    · obtain ⟨i, hi, hmem⟩ := h2      interval_cases i      simpa using hmem  · rintro ⟨h0, h1, h2⟩    exact ⟨h0, ⟨0, le_refl 0, h1⟩, ⟨0, le_refl 0, h2⟩, Or.inl h1⟩/-- Every positive perfect square lies in remoteness level 1 of Epstein's game. -/lemma epstein_remoteness_of_is_stein_number_pos_square_mem_level_one {x : ℕ} (hx : 0 < x) (hsq : IsSquare x) :    x ∈ epstein_remoteness_level 1 := by  rw [epstein_remoteness_of_is_stein_number_level_one_eq]  refine ⟨hx.ne', Or.inl ?_⟩  obtain ⟨r, rfl⟩ := hsq  simp [epstein_down, Nat.sqrt_eq, pow_two]/-- Every E. P. Stein number has remoteness 2 in Epstein's game. -/theorem epstein_remoteness_of_is_stein_number (n : ℕ) (h : is_stein_number n) : epstein_remoteness n = 2 := by  classical  have hn0 : 0 < n := h.1  have hd0 : 0 < epstein_down n := h.2.1  have hdsq : IsSquare (epstein_down n) := h.2.2.1  have hu0 : 0 < epstein_up n := h.2.2.2.1  have husq : IsSquare (epstein_up n) := h.2.2.2.2  have hdlvl : epstein_down n ∈ epstein_remoteness_level 1 :=    epstein_remoteness_of_is_stein_number_pos_square_mem_level_one hd0 hdsq  have hulvl : epstein_up n ∈ epstein_remoteness_level 1 :=    epstein_remoteness_of_is_stein_number_pos_square_mem_level_one hu0 husq  have hmem2 : n ∈ epstein_remoteness_level 2 := by    rw [epstein_remoteness_of_is_stein_number_level_two_eq]    exact ⟨hn0.ne', hdlvl, hulvl⟩  have hn0lvl : n ∉ epstein_remoteness_level 0 := by    rw [epstein_remoteness_level.eq_1]    simp [hn0.ne']  have hn1lvl : n ∉ epstein_remoteness_level 1 := by    rw [epstein_remoteness_of_is_stein_number_level_one_eq]    simp [hd0.ne', hu0.ne']  have hex : ∃ k, n ∈ epstein_remoteness_level k := ⟨2, hmem2⟩  have hstep : epstein_remoteness n = (some (Nat.find hex) : WithTop ℕ) := by    rw [epstein_remoteness.eq_def]    exact @dif_pos (c := ∃ k, n ∈ epstein_remoteness_level k) (h := Classical.propDecidable _) hex      (α := WithTop ℕ) (t := fun hh => @Option.some ℕ (Nat.find (p := fun k => n ∈ epstein_remoteness_level k) hh))      (e := fun _ => ⊤)  have hfind : Nat.find hex = 2 := by    have hspec : n ∈ epstein_remoteness_level (Nat.find hex) := Nat.find_spec hex    have hle : Nat.find hex ≤ 2 := Nat.find_min' hex hmem2    have hne0 : Nat.find hex ≠ 0 := by      intro hh      exact hn0lvl (hh ▸ hspec)    have hne1 : Nat.find hex ≠ 1 := by      intro hh      exact hn1lvl (hh ▸ hspec)    omega  rw [hstep, hfind]  rfl
See it in the graphDiscuss this resultChallenge it