epstein_remoteness_of_is_stein_number
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
- epstein_remoteness_twenty_nineIn Epstein's put-or-take-a-square game, the natural number 29 has remoteness epstein_remoteness 29 = 4.
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.
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.
uses
epstein_remoteness_level.eq_def,epstein_remoteness_level.eq_1rw [epstein_remoteness_level.eq_def 1] dsimp only rw [epstein_remoteness_level.eq_1] simp
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.
uses
epstein_remoteness_level.eq_def,Set.mem_iUnion,exists_prop,Set.mem_ofPred_eq,le_refl,Or.inlrw [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 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.
uses
epstein_remoteness_of_is_stein_number_level_one_eq,Or.inl,Nat.sqrt_eq,pow_tworw [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]
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.
uses
epstein_remoteness_of_is_stein_number_pos_square_mem_level_oneclassical 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
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$.
uses
epstein_remoteness_of_is_stein_number_level_two_eqhave hmem2 : n ∈ epstein_remoteness_level 2 := by rw [epstein_remoteness_of_is_stein_number_level_two_eq] exact ⟨hn0.ne', hdlvl, hulvl⟩
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$.
uses
epstein_remoteness_level.eq_1,epstein_remoteness_of_is_stein_number_level_one_eqhave 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']
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$.
uses
epstein_remoteness.eq_def,dif_poshave 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 _ => ⊤)
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.
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
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$.
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.
- The definition of `epstein_remoteness` uses `WithTop ℕ` and `Nat.find` over the existence of a remoteness level containing `n`, relying on classical logic (`dif_pos`) to extract the witness.
- Simplifying the recursive definition of `epstein_remoteness_level` for levels 1 and 2 relies on bounded index exhaustion ($j < 0$ and $i \le 0$) carried out by simplification and `interval_cases`.
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 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