/-
Copyright 2026 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 FormalConjecturesUtilErdős Problem 1209
References:
[Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.
@[expose] public sectionopen Nat Setnamespace Erdos1209
For every k ≥ 1 and bound m, there is a prime p > m such that k + p is composite:
take a prime q > k and, by Dirichlet, a prime p > max m q with p ≡ -k (mod q).
k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero qhunit:IsUnit (-↑k)p:ℕhp:p > max m qhpp:Nat.Prime phpq:↑p = -↑khdvd:q ∣ k + p⊢ ¬Nat.Prime (k + p)
exact Nat.not_prime_of_dvd_of_lt hdvd hq.two_le (by k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero qhunit:IsUnit (-↑k)p:ℕhp:p > max m qhpp:Nat.Prime phpq:↑p = -↑khdvd:q ∣ k + p⊢ q < k + p omega All goals completed! 🐙)
The counterexample sequence: a 0 is a prime at least f 0, and a (k + 1) is a prime
larger than a k and f (k + 1) with (k + 1) + a (k + 1) composite.
noncomputable def seq (f : ℕ → ℕ) : ℕ → ℕ
| 0 => Classical.choose (Nat.exists_infinite_primes (f 0))
| k + 1 => Classical.choose (exists_prime_gt_not_prime_add (k + 1) (max (seq f k) (f (k + 1)))
(by f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 omega All goals completed! 🐙))
The defining properties of seq f 0.
@[category API, AMS 11]
theorem seq_zero_spec (f : ℕ → ℕ) : f 0 ≤ seq f 0 ∧ (seq f 0).Prime :=
Classical.choose_spec (Nat.exists_infinite_primes (f 0))
The defining properties of seq f (k + 1).
@[category API, AMS 11]
theorem seq_succ_spec (f : ℕ → ℕ) (k : ℕ) :
max (seq f k) (f (k + 1)) < seq f (k + 1) ∧ (seq f (k + 1)).Prime ∧
¬ ((k + 1) + seq f (k + 1)).Prime :=
Classical.choose_spec (exists_prime_gt_not_prime_add (k + 1) (max (seq f k) (f (k + 1)))
(by f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 omega All goals completed! 🐙))Let $A={a_1<a_2<\cdots}$ be a sequence of integers which tends to infinity sufficiently fast. If there is an $n$ such that all $n+a_k$ are primes then must there exist infinitely many such $n$?
Erdős [Er80] wrote 'unless I overlook a trivial way of getting a counterexample these questions are quite hopeless'. There is indeed a trivial counterexample (a variant of the construction in [erdosproblems.com/429]): define $a_1=2$ and for $k\geq 2$ let $a_k>a_{k-1}$ be a prime such that $a_k+k\equiv 0\pmod{q_k}$, where $q_k$ is some prime not dividing $k$. This sequence can be made to grow arbitrarily fast
See also [erdosproblems.com/429] and [erdosproblems.com/1102].
@[category research solved, question, AMS 11]
theorem erdos_1209.parts.i :
¬ ∃ f : ℕ → ℕ, ∀ a : ℕ → ℕ, StrictMono a → (∀ k, f k ≤ a k) →
(∃ n, ∀ k, (n + a k).Prime) →
{n | ∀ k, (n + a k).Prime}.Infinite := by ⊢ ¬∃ f,
∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinite
rintro ⟨f, hf⟩ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinite⊢ False
have hmono : StrictMono (seq f) :=
strictMono_nat_of_lt_succ fun k => lt_of_le_of_lt (le_max_left _ _) (seq_succ_spec f k).1 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)⊢ False
have hbound : ∀ k, f k ≤ seq f k := by ⊢ ¬∃ f,
∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinite f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ False
intro k f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)k:ℕ⊢ f k ≤ seq f k f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ False
cases k with
| zero => zero f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)⊢ f 0 ≤ seq f 0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ False exact (seq_zero_spec f).1 All goals completed! 🐙 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ False
| succ k => succ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)k:ℕ⊢ f (k + 1) ≤ seq f (k + 1) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ False exact (lt_of_le_of_lt (le_max_right _ _) (seq_succ_spec f k).1).le f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ False f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ False
have hprime : ∀ k, (seq f k).Prime := by ⊢ ¬∃ f,
∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinite f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)⊢ False
intro k f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f kk:ℕ⊢ Nat.Prime (seq f k) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)⊢ False
cases k with
| zero => zero f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f k⊢ Nat.Prime (seq f 0) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)⊢ False exact (seq_zero_spec f).2 All goals completed! 🐙 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)⊢ False
| succ k => succ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f kk:ℕ⊢ Nat.Prime (seq f (k + 1)) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)⊢ False exact (seq_succ_spec f k).2.1 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)⊢ False f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)⊢ False
have hinf := hf (seq f) hmono hbound ⟨0, fun k => by f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)k:ℕ⊢ Nat.Prime (0 + seq f k) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infinite⊢ False simpa using hprime k All goals completed! 🐙 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infinite⊢ False⟩ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infinite⊢ False
-- but the set is contained in `{0}`
refine hinf ((Set.finite_singleton 0).subset fun n hn => ?_) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}⊢ n ∈ {0}
rw [Set.mem_singleton_iff f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}⊢ n = 0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}⊢ n = 0] f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}⊢ n = 0
by_contra hn0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0⊢ False
exact (seq_succ_spec f (n - 1)).2.2 (by f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0⊢ Nat.Prime (n - 1 + 1 + seq f (n - 1 + 1))
have := hn n f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0this:Nat.Prime (n + seq f n)⊢ Nat.Prime (n - 1 + 1 + seq f (n - 1 + 1))
rwa [show n - 1 + 1 = n by f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0⊢ Nat.Prime (n - 1 + 1 + seq f (n - 1 + 1)) omega All goals completed! 🐙] f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0this:Nat.Prime (n + seq f n)⊢ Nat.Prime (n + seq f n) )
For every k ≥ 1 and bound m, there is a prime p > m such that k + p is not squarefree:
take a prime q > k and, by Dirichlet, a prime p > m with p ≡ -k (mod q ^ 2).
@[category API, AMS 11]
theorem exists_prime_gt_not_squarefree_add (k m : ℕ) (hk : 1 ≤ k) :
∃ p, m < p ∧ p.Prime ∧ ¬ Squarefree (k + p) := by k:ℕm:ℕhk:1 ≤ k⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)
obtain ⟨q, hqk, hq⟩ := Nat.exists_infinite_primes (k + 1) k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime q⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)
have : NeZero (q ^ 2) := ⟨pow_ne_zero 2 hq.ne_zero⟩ k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)
have hunit : IsUnit (-(k : ZMod (q ^ 2))) := by
refine IsUnit.neg ?_ k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)⊢ IsUnit ↑k k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)
rw [ZMod.isUnit_iff_coprime k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)⊢ k.Coprime (q ^ 2) k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)⊢ k.Coprime (q ^ 2) k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)] k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)⊢ k.Coprime (q ^ 2) k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)
exact Nat.Coprime.pow_right 2 (Nat.coprime_comm.1 ((Nat.Prime.coprime_iff_not_dvd hq).2
(Nat.not_dvd_of_pos_of_lt (by k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)⊢ 0 < k k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p) omega All goals completed! 🐙 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)) (by k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)⊢ k < q k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p) omega All goals completed! 🐙 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p))))) k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)
obtain ⟨p, hp, hpp, hpq⟩ := Nat.forall_exists_prime_gt_and_eq_mod hunit m k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p)
refine ⟨p, hp, hpp, ?_⟩ k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ¬Squarefree (k + p)
have hdvd : q ^ 2 ∣ k + p := by k:ℕm:ℕhk:1 ≤ k⊢ ∃ p, m < p ∧ Nat.Prime p ∧ ¬Squarefree (k + p) k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬Squarefree (k + p)
rw [← ZMod.natCast_eq_zero_iff, k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ↑(k + p) = 0 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ↑k + -↑k = 0 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬Squarefree (k + p) Nat.cast_add, k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ↑k + ↑p = 0 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ↑k + -↑k = 0 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬Squarefree (k + p) hpq k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ↑k + -↑k = 0 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ↑k + -↑k = 0 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬Squarefree (k + p)] k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑k⊢ ↑k + -↑k = 0 k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬Squarefree (k + p)
ring k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬Squarefree (k + p) k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬Squarefree (k + p)
rw [Nat.squarefree_iff_prime_squarefree k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬∀ (x : ℕ), Nat.Prime x → ¬x * x ∣ k + p k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬∀ (x : ℕ), Nat.Prime x → ¬x * x ∣ k + p] k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬∀ (x : ℕ), Nat.Prime x → ¬x * x ∣ k + p
push Not k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ∃ x, Nat.Prime x ∧ x * x ∣ k + p
exact ⟨q, hq, by k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ q * q ∣ k + p rwa [← sq k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ q ^ 2 ∣ k + p] k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ q ^ 2 ∣ k + p⟩The counterexample sequence for the squarefree variant.
noncomputable def seq' (f : ℕ → ℕ) : ℕ → ℕ
| 0 => Classical.choose (Nat.exists_infinite_primes (f 0))
| k + 1 => Classical.choose (exists_prime_gt_not_squarefree_add (k + 1)
(max (seq' f k) (f (k + 1))) (by f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 omega All goals completed! 🐙))
The defining properties of seq' f (k + 1).
@[category API, AMS 11]
theorem seq'_succ_spec (f : ℕ → ℕ) (k : ℕ) :
max (seq' f k) (f (k + 1)) < seq' f (k + 1) ∧ (seq' f (k + 1)).Prime ∧
¬ Squarefree ((k + 1) + seq' f (k + 1)) :=
Classical.choose_spec (exists_prime_gt_not_squarefree_add (k + 1) (max (seq' f k) (f (k + 1)))
(by f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 omega All goals completed! 🐙))What if we ask for $n+a_k$ to be squarefree instead of prime?
A similar construction provides a counterexample to the squarefree question.
@[category research solved, question, AMS 11]
theorem erdos_1209.parts.ii :
¬ ∃ f : ℕ → ℕ, ∀ a : ℕ → ℕ, StrictMono a → (∀ k, f k ≤ a k) →
(∃ n, ∀ k, Squarefree (n + a k)) →
{n | ∀ k, Squarefree (n + a k)}.Infinite := by ⊢ ¬∃ f,
∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infinite
rintro ⟨f, hf⟩ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infinite⊢ False
have h0 := Classical.choose_spec (Nat.exists_infinite_primes (f 0)) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)⊢ False
have hmono : StrictMono (seq' f) :=
strictMono_nat_of_lt_succ fun k => lt_of_le_of_lt (le_max_left _ _) (seq'_succ_spec f k).1 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)⊢ False
have hbound : ∀ k, f k ≤ seq' f k := by ⊢ ¬∃ f,
∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infinite f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ False
intro k f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)k:ℕ⊢ f k ≤ seq' f k f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ False
cases k with
| zero => zero f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)⊢ f 0 ≤ seq' f 0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ False exact h0.1 All goals completed! 🐙 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ False
| succ k => succ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)k:ℕ⊢ f (k + 1) ≤ seq' f (k + 1) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ False exact (lt_of_le_of_lt (le_max_right _ _) (seq'_succ_spec f k).1).le f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ False f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ False
have hprime : ∀ k, (seq' f k).Prime := by ⊢ ¬∃ f,
∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infinite f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)⊢ False
intro k f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f kk:ℕ⊢ Nat.Prime (seq' f k) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)⊢ False
cases k with
| zero => zero f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f k⊢ Nat.Prime (seq' f 0) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)⊢ False exact h0.2 All goals completed! 🐙 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)⊢ False
| succ k => succ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f kk:ℕ⊢ Nat.Prime (seq' f (k + 1)) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)⊢ False exact (seq'_succ_spec f k).2.1 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)⊢ False f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)⊢ False
have hinf := hf (seq' f) hmono hbound
⟨0, fun k => by f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)k:ℕ⊢ Squarefree (0 + seq' f k) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infinite⊢ False simpa using (hprime k).prime.squarefree All goals completed! 🐙 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infinite⊢ False⟩ f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infinite⊢ False
refine hinf ((Set.finite_singleton 0).subset fun n hn => ?_) f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}⊢ n ∈ {0}
rw [Set.mem_singleton_iff f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}⊢ n = 0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}⊢ n = 0] f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}⊢ n = 0
by_contra hn0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0⊢ False
exact (seq'_succ_spec f (n - 1)).2.2 (by f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0⊢ Squarefree (n - 1 + 1 + seq' f (n - 1 + 1))
have := hn n f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0this:Squarefree (n + seq' f n)⊢ Squarefree (n - 1 + 1 + seq' f (n - 1 + 1))
rwa [show n - 1 + 1 = n by f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0⊢ Squarefree (n - 1 + 1 + seq' f (n - 1 + 1)) omega All goals completed! 🐙] f:ℕ → ℕhf:∀ (a : ℕ → ℕ),
StrictMono a →
(∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0this:Squarefree (n + seq' f n)⊢ Squarefree (n + seq' f n))Are there $n$ such that $n+2^{2^k}$ is always a prime?
ebarschkis and GPT have proved that there are no $n$ such that $n+2^{2^k}$ is always prime: let $n\geq 3$ be any odd integer. If $k$ is chosen sufficiently large, and $p=n+2^{2^{k}}$ is prime, then the multiplicative order of $2^{2^k}\pmod{p}$, say $m$ is odd, and hence if $l$ is chosen such that $2^l\equiv 1\pmod{m}$ then $p\mid n+2^{2^{k+rl}}$ for all $r\geq 1$.
This was formalized in Lean by Barschkis using ChatGPT.
@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/ebarschkis/ErdosProblem/blob/main/Problem1209/Formalization.lean"]
theorem erdos_1209.parts.iii.a :
¬ ∃ n : ℕ, ∀ k : ℕ, (n + 2 ^ (2 ^ k)).Prime := by ⊢ ¬∃ n, ∀ (k : ℕ), Nat.Prime (n + 2 ^ 2 ^ k)
sorry All goals completed! 🐙Are there $n$ such that $n+2^{2^k}$ is always squarefree?
@[category research open, question, AMS 11]
theorem erdos_1209.parts.iii.b :
∃ n : ℕ, ∀ k : ℕ, Squarefree (n + 2 ^ (2 ^ k)) := by ⊢ ∃ n, ∀ (k : ℕ), Squarefree (n + 2 ^ 2 ^ k)
sorry All goals completed! 🐙Are there $n$ such that $n+2^{2^k}$ is infinitely often a prime?
@[category research open, question, AMS 11]
theorem erdos_1209.parts.iii.c :
∃ n : ℕ, {k | (n + 2 ^ (2 ^ k)).Prime}.Infinite := by ⊢ ∃ n, {k | Nat.Prime (n + 2 ^ 2 ^ k)}.Infinite
sorry All goals completed! 🐙Are there $n$ such that $n+2^{2^k}$ is infinitely often squarefree?
@[category research open, question, AMS 11]
theorem erdos_1209.parts.iii.d :
∃ n : ℕ, {k | Squarefree (n + 2 ^ (2 ^ k))}.Infinite := by ⊢ ∃ n, {k | Squarefree (n + 2 ^ 2 ^ k)}.Infinite
sorry All goals completed! 🐙end Erdos1209