/-
Copyright 2025 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtil
@[expose] public sectionnamespace Erdos422open Filteropen scoped Topology
IsHofstadterQ f means that $f$ is Hofstadter's $Q$-sequence (OEIS A005185): $f(1) = f(2) = 1$
and for $n > 2$
$$
f(n) = f(n - f(n - 1)) + f(n - f(n - 2)),
$$
where the recurrence requires $f(n - 1) < n$ and $f(n - 2) < n$, so that both arguments on the
right-hand side are positive integers. The sequence begins $1, 1, 2, 3, 3, 4, \ldots$.
At most one function satisfies this predicate. Some function satisfies it if and only if $f(n)$ is well-defined for all $n$, which is not known.
def IsHofstadterQ (f : ℕ+ → ℕ+) : Prop :=
f 1 = 1 ∧ f 2 = 1 ∧
∀ n : ℕ+, 2 < n →
f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))The third term of Hofstadter's $Q$-sequence is $f(3) = f(2) + f(2) = 2$.
f:ℕ+ → ℕ+h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h3:f 3 = f (3 - f (3 - 1)) + f (3 - f (3 - 2))⊢ f 3 = 2
simp only [h3, show (3 : ℕ+) - 1 = 2 from rfl, show (3 : ℕ+) - 2 = 1 from rfl, h1, h2] f:ℕ+ → ℕ+h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h3:f 3 = f (3 - f (3 - 1)) + f (3 - f (3 - 2))⊢ 1 + 1 = 2
rfl All goals completed! 🐙The fourth term of Hofstadter's $Q$-sequence is $f(4) = f(2) + f(3) = 3$.
@[category test, AMS 11]
theorem erdos_422.test.f4 : ∀ f : ℕ+ → ℕ+, IsHofstadterQ f → f 4 = 3 := by ⊢ ∀ (f : ℕ+ → ℕ+), IsHofstadterQ f → f 4 = 3
intro f hf f:ℕ+ → ℕ+hf:IsHofstadterQ f⊢ f 4 = 3
have h3 := erdos_422.test.f3 f hf f:ℕ+ → ℕ+hf:IsHofstadterQ fh3:f 3 = 2⊢ f 4 = 3
obtain ⟨h1, h2, h⟩ := hf f:ℕ+ → ℕ+h3:f 3 = 2h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))⊢ f 4 = 3
obtain ⟨-, -, h4⟩ := h 4 (by f:ℕ+ → ℕ+h3:f 3 = 2h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))⊢ 2 < 4 f:ℕ+ → ℕ+h3:f 3 = 2h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h4:f 4 = f (4 - f (4 - 1)) + f (4 - f (4 - 2))⊢ f 4 = 3 decide All goals completed! 🐙 f:ℕ+ → ℕ+h3:f 3 = 2h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h4:f 4 = f (4 - f (4 - 1)) + f (4 - f (4 - 2))⊢ f 4 = 3) f:ℕ+ → ℕ+h3:f 3 = 2h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h4:f 4 = f (4 - f (4 - 1)) + f (4 - f (4 - 2))⊢ f 4 = 3
simp only [h4, show (4 : ℕ+) - 1 = 3 from rfl, show (4 : ℕ+) - 2 = 2 from rfl, h2, h3] f:ℕ+ → ℕ+h3:f 3 = 2h1:f 1 = 1h2:f 2 = 1h:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h4:f 4 = f (4 - f (4 - 1)) + f (4 - f (4 - 2))⊢ 1 + 2 = 3
rfl All goals completed! 🐙Let $f(1) = f(2) = 1$ and for $n > 2$ $$ f(n) = f(n - f(n - 1)) + f(n - f(n - 2)). $$ Does $f(n)$ miss infinitely many integers?
@[category research open, question, AMS 11]
theorem erdos_422 :
∀ f : ℕ+ → ℕ+, IsHofstadterQ f → Set.Infinite {n | ∀ x, f x ≠ n} := by ⊢ ∀ (f : ℕ+ → ℕ+), IsHofstadterQ f → {n | ∀ (x : ℕ+), f x ≠ n}.Infinite
sorry All goals completed! 🐙Is $f$ surjective?
@[category research open, question, AMS 11]
theorem erdos_422.variants.surjective :
∀ f : ℕ+ → ℕ+, IsHofstadterQ f → f.Surjective := by ⊢ ∀ (f : ℕ+ → ℕ+), IsHofstadterQ f → Function.Surjective f
sorry All goals completed! 🐙def erdos_422.variants.growth_rate.answer : ℕ+ → ℝ := sorryHow does $f$ grow?
@[category research open, question value, AMS 11]
theorem erdos_422.variants.growth_rate :
∀ f : ℕ+ → ℕ+, IsHofstadterQ f →
(fun n ↦ (f n : ℝ)) =O[atTop] erdos_422.variants.growth_rate.answer := by ⊢ ∀ (f : ℕ+ → ℕ+), IsHofstadterQ f → (fun n ↦ ↑↑(f n)) =O[atTop] growth_rate.answer
sorry All goals completed! 🐙Hofstadter's $Q$-sequence is not eventually constant: if $f(n) = c$ for all large $n$, then the recurrence gives $c = f(n - c) + f(n - c) = 2c$.
@[category API, AMS 11]
theorem IsHofstadterQ.not_eventuallyConst {f : ℕ+ → ℕ+} (hf : IsHofstadterQ f) :
¬ EventuallyConst f atTop := by f:ℕ+ → ℕ+hf:IsHofstadterQ f⊢ ¬EventuallyConst f atTop
obtain ⟨-, -, hf⟩ := hf f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))⊢ ¬EventuallyConst f atTop
intro h f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTop⊢ False
obtain ⟨c, hc⟩ := eventuallyConst_iff_exists_eventuallyEq.mp h f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ c⊢ False
obtain ⟨N, hN⟩ := eventually_atTop.mp hc f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) b⊢ False
have hc0 := c.pos f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑c⊢ False
-- Subtracting `k ≤ c + 1` from `n = N + c + 2` leaves an index that is still at least `N`.
have key (k : ℕ+) (hk : (k : ℕ) ≤ c + 1) : f (N + c + 2 - k) = c := hN _ <| by f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1⊢ N ≤ N + c + 2 - k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False
have hlt : k < N + c + 2 := by
rw [← PNat.coe_lt_coe f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1⊢ ↑k < ↑(N + c + 2) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1⊢ ↑k < ↑(N + c + 2) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ N ≤ N + c + 2 - k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False] f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1⊢ ↑k < ↑(N + c + 2) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ N ≤ N + c + 2 - k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False; push_cast f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1⊢ ↑k < ↑N + ↑c + 2 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ N ≤ N + c + 2 - k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False; omega f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ N ≤ N + c + 2 - k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ N ≤ N + c + 2 - k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False
rw [← PNat.coe_le_coe, f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ ↑(N + c + 2 - k) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ ↑(N + c + 2) - ↑k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False PNat.sub_coe, f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ if k < N + c + 2 then ↑(N + c + 2) - ↑k else 1 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ ↑(N + c + 2) - ↑k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False if_pos hlt f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ ↑(N + c + 2) - ↑k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ ↑(N + c + 2) - ↑k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False] f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ ↑(N + c + 2) - ↑k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False
push_cast f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ck:ℕ+hk:↑k ≤ ↑c + 1hlt:k < N + c + 2⊢ ↑N ≤ ↑N + ↑c + 2 - ↑k f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False; omega f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ False
have hn : f (N + c + 2) = c := hN _ <| by f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ N ≤ N + c + 2 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = c⊢ False
rw [← PNat.coe_le_coe f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ ↑N ≤ ↑(N + c + 2) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ ↑N ≤ ↑(N + c + 2) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = c⊢ False] f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ ↑N ≤ ↑(N + c + 2) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = c⊢ False; push_cast f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = c⊢ ↑N ≤ ↑N + ↑c + 2 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = c⊢ False; omega f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = c⊢ False f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = c⊢ False
obtain ⟨-, -, hrec⟩ := hf (N + c + 2) (PNat.lt_add_left 2 (N + c)) f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:f (N + c + 2) = f (N + c + 2 - f (N + c + 2 - 1)) + f (N + c + 2 - f (N + c + 2 - 2))⊢ False
-- The recurrence at `n` now reads `c = c + c`.
rw [hn, f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = f (N + c + 2 - f (N + c + 2 - 1)) + f (N + c + 2 - f (N + c + 2 - 2))⊢ False f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False key 1 (Nat.le_add_left 1 c), f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = f (N + c + 2 - c) + f (N + c + 2 - f (N + c + 2 - 2))⊢ False f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False key 2 (by f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = f (N + c + 2 - c) + f (N + c + 2 - f (N + c + 2 - 2))⊢ ↑2 ≤ ↑c + 1 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False push_cast f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = f (N + c + 2 - c) + f (N + c + 2 - f (N + c + 2 - 2))⊢ 1 ≤ ↑c f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False; omega All goals completed! 🐙 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False), key c (by f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = f (N + c + 2 - c) + f (N + c + 2 - c)⊢ ↑c ≤ ↑c + 1 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False omega All goals completed! 🐙 f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False)] at hrec f:ℕ+ → ℕ+hf:∀ (n : ℕ+), 2 < n → f (n - 1) < n ∧ f (n - 2) < n ∧ f n = f (n - f (n - 1)) + f (n - f (n - 2))h:EventuallyConst f atTopc:ℕ+hc:f =ᶠ[atTop] fun x ↦ cN:ℕ+hN:∀ (b : ℕ+), N ≤ b → f b = (fun x ↦ c) bhc0:0 < ↑ckey:∀ (k : ℕ+), ↑k ≤ ↑c + 1 → f (N + c + 2 - k) = chn:f (N + c + 2) = chrec:c = c + c⊢ False
exact (PNat.lt_add_right c c).ne hrec All goals completed! 🐙Does $f$ become stationary at some point?
No: see IsHofstadterQ.not_eventuallyConst. The statement is existential, so the answer does
not depend on whether $f(n)$ is well-defined for all $n$.
@[category textbook, AMS 11]
theorem erdos_422.variants.eventually_const :
¬ ∃ f : ℕ+ → ℕ+, IsHofstadterQ f ∧ EventuallyConst f atTop :=
fun ⟨_, hf, h⟩ ↦ hf.not_eventuallyConst hIs $f(n)$ well-defined for all $n$?
@[category research open, question, AMS 11]
theorem erdos_422.variants.well_defined : ∃ f : ℕ+ → ℕ+, IsHofstadterQ f := by ⊢ ∃ f, IsHofstadterQ f
sorry All goals completed! 🐙end Erdos422