/-
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 820
References:
[Er74b] Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202.
OEIS A263647: the $n$ with $(2^n-1, 3^n-1) = 1$.
@[expose] public sectionopen Filternamespace Erdos820$H(n)$ is the smallest integer $l$ such that there is some $k < l$ with $(k^n-1, l^n-1) = 1$.
We take $k$ and $l$ to be integers with $k \geq 2$, so that $k^n - 1 \geq 1$ for $n \geq 1$. Smaller $k$ give degenerate values: over the integers $k = 0$ gives $(-1, l^n-1) = 1$, and $k = 1$ gives $(0, l^n-1) = l^n-1$, which is $1$ for $n = 1$, $l = 2$. Both would contradict the value $H(1) = 3$ listed in the source.
For $n \geq 1$ the set is nonempty (see Erdos820.H_spec). For $n = 0$ it is empty, and
H 0 = 0 by the sInf ∅ convention; the only statement whose truth depends on H 0 is
Erdos820.H_eq_three_iff, where both sides are false.
noncomputable def H (n : ℕ) : ℕ :=
sInf {l : ℕ | ∃ k : ℕ, 2 ≤ k ∧ k < l ∧ Nat.Coprime (k ^ n - 1) (l ^ n - 1)}
$K(n)$ is the smallest integer $k \geq 2$ such that $(k^n-1, 2^n-1) = 1$. As for
Erdos820.H, smaller $k$ are excluded because they give degenerate values.
For $n \geq 2$ the value $k = 2$ never works, and $k = 2^n - 1$ always works. For $n = 1$ we
get $K(1) = 2$, and for $n = 0$ the set is empty, so K 0 = 0.
noncomputable def K (n : ℕ) : ℕ :=
sInf {k : ℕ | 2 ≤ k ∧ Nat.Coprime (k ^ n - 1) (2 ^ n - 1)}For $n \geq 1$ the minimum defining $H(n)$ is attained: there is $k$ with $2 \leq k < H(n)$ and $(k^n-1, H(n)^n-1) = 1$. For $n \geq 2$, the pair $k = 2$, $l = 2^n - 1$ shows that the set is nonempty. For $n = 1$, take $k = 2$, $l = 3$.
n:ℕhn:1 ≤ nhne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonempty⊢ ∃ k, 2 ≤ k ∧ k < H n ∧ (k ^ n - 1).Coprime (H n ^ n - 1)
exact Nat.sInf_mem hne All goals completed! 🐙$H(n) = 3$ if and only if $(2^n-1, 3^n-1) = 1$. This holds for every $n$, including $n = 0$, where both sides are false.
@[category API, AMS 11]
theorem H_eq_three_iff (n : ℕ) : H n = 3 ↔ Nat.Coprime (2 ^ n - 1) (3 ^ n - 1) := by n:ℕ⊢ H n = 3 ↔ (2 ^ n - 1).Coprime (3 ^ n - 1)
constructor mp n:ℕ⊢ H n = 3 → (2 ^ n - 1).Coprime (3 ^ n - 1)mpr n:ℕ⊢ (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3
· mp n:ℕ⊢ H n = 3 → (2 ^ n - 1).Coprime (3 ^ n - 1) intro h mp n:ℕh:H n = 3⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)
have hne : {l : ℕ | ∃ k : ℕ, 2 ≤ k ∧ k < l ∧ Nat.Coprime (k ^ n - 1) (l ^ n - 1)}.Nonempty :=
Nat.nonempty_of_pos_sInf (by n:ℕh:H n = 3⊢ 0 < sInf {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)} mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonempty⊢ (2 ^ n - 1).Coprime (3 ^ n - 1) unfold H at h n:ℕh:sInf {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)} = 3⊢ 0 < sInf {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)} mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonempty⊢ (2 ^ n - 1).Coprime (3 ^ n - 1); omega All goals completed! 🐙mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonempty⊢ (2 ^ n - 1).Coprime (3 ^ n - 1))mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonempty⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)
have hmem : H n ∈ {l : ℕ | ∃ k : ℕ, 2 ≤ k ∧ k < l ∧ Nat.Coprime (k ^ n - 1) (l ^ n - 1)} :=
Nat.sInf_mem hne mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyhmem:H n ∈ {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)
rw [h mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyhmem:3 ∈ {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}⊢ (2 ^ n - 1).Coprime (3 ^ n - 1) mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyhmem:3 ∈ {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)] at hmemmp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyhmem:3 ∈ {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)
obtain ⟨k, hk2, hk3, hk⟩ := hmem mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyk:ℕhk2:2 ≤ khk3:k < 3hk:(k ^ n - 1).Coprime (3 ^ n - 1)⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)
obtain rfl : k = 2 := by n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyk:ℕhk2:2 ≤ khk3:k < 3hk:(k ^ n - 1).Coprime (3 ^ n - 1)⊢ k = 2 mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyhk2:2 ≤ 2hk3:2 < 3hk:(2 ^ n - 1).Coprime (3 ^ n - 1)⊢ (2 ^ n - 1).Coprime (3 ^ n - 1) omegamp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyhk2:2 ≤ 2hk3:2 < 3hk:(2 ^ n - 1).Coprime (3 ^ n - 1)⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)mp n:ℕh:H n = 3hne:{l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}.Nonemptyhk2:2 ≤ 2hk3:2 < 3hk:(2 ^ n - 1).Coprime (3 ^ n - 1)⊢ (2 ^ n - 1).Coprime (3 ^ n - 1)
exact hk All goals completed! 🐙
· mpr n:ℕ⊢ (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3 intro h mpr n:ℕh:(2 ^ n - 1).Coprime (3 ^ n - 1)⊢ H n = 3
unfold H mpr n:ℕh:(2 ^ n - 1).Coprime (3 ^ n - 1)⊢ sInf {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)} = 3
refine le_antisymm (Nat.sInf_le ⟨2, le_rfl, by n:ℕh:(2 ^ n - 1).Coprime (3 ^ n - 1)⊢ 2 < 3 norm_num All goals completed! 🐙, h⟩)
(le_csInf ⟨3, 2, le_rfl, by n:ℕh:(2 ^ n - 1).Coprime (3 ^ n - 1)⊢ 2 < 3 norm_num All goals completed! 🐙, h⟩ ?_)
rintro l ⟨k, hk2, hkl, -⟩ mpr n:ℕh:(2 ^ n - 1).Coprime (3 ^ n - 1)l:ℕk:ℕhk2:2 ≤ khkl:k < l⊢ 3 ≤ l
omega All goals completed! 🐙The first values of $H(n)$, for $1 \leq n \leq 10$, are $3, 3, 3, 6, 3, 18, 3, 6, 3, 12$.
@[category test, AMS 11]
theorem H_one_to_ten :
H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧
H 9 = 3 ∧ H 10 = 12 := by ⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
have key : ∀ n m : ℕ, (∃ k, 2 ≤ k ∧ k < m ∧ Nat.Coprime (k ^ n - 1) (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬ Nat.Coprime (k ^ n - 1) (l ^ n - 1)) → H n = m := by
intro n m hm hlt n:ℕm:ℕhm:∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)hlt:∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)⊢ H n = m key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = m⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
unfold H n:ℕm:ℕhm:∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)hlt:∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)⊢ sInf {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)} = m key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = m⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
refine le_antisymm (Nat.sInf_le hm) (le_csInf ⟨m, hm⟩ ?_) n:ℕm:ℕhm:∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)hlt:∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)⊢ ∀ b ∈ {l | ∃ k, 2 ≤ k ∧ k < l ∧ (k ^ n - 1).Coprime (l ^ n - 1)}, m ≤ b key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = m⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
rintro l ⟨k, hk2, hkl, hk⟩ n:ℕm:ℕhm:∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)hlt:∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)l:ℕk:ℕhk2:2 ≤ khkl:k < lhk:(k ^ n - 1).Coprime (l ^ n - 1)⊢ m ≤ l key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = m⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
by_contra! h n:ℕm:ℕhm:∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)hlt:∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)l:ℕk:ℕhk2:2 ≤ khkl:k < lhk:(k ^ n - 1).Coprime (l ^ n - 1)h:l < m⊢ False key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = m⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
exact hlt l h k hkl hk2 hk key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = m⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12 key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = m⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
have three (n : ℕ) (h : Nat.Coprime (2 ^ n - 1) (3 ^ n - 1)) : H n = 3 :=
(H_eq_three_iff n).2 h key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ H 1 = 3 ∧ H 2 = 3 ∧ H 3 = 3 ∧ H 4 = 6 ∧ H 5 = 3 ∧ H 6 = 18 ∧ H 7 = 3 ∧ H 8 = 6 ∧ H 9 = 3 ∧ H 10 = 12
exact ⟨three 1 (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ (2 ^ 1 - 1).Coprime (3 ^ 1 - 1) decide All goals completed! 🐙), three 2 (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ (2 ^ 2 - 1).Coprime (3 ^ 2 - 1) decide All goals completed! 🐙), three 3 (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ (2 ^ 3 - 1).Coprime (3 ^ 3 - 1) decide All goals completed! 🐙),
key 4 6 ⟨5, by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ 2 ≤ 5 ∧ 5 < 6 ∧ (5 ^ 4 - 1).Coprime (6 ^ 4 - 1) decide All goals completed! 🐙⟩ (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ ∀ l < 6, ∀ k < l, 2 ≤ k → ¬(k ^ 4 - 1).Coprime (l ^ 4 - 1) decide +kernel All goals completed! 🐙), three 5 (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ (2 ^ 5 - 1).Coprime (3 ^ 5 - 1) decide All goals completed! 🐙),
key 6 18 ⟨14, by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ 2 ≤ 14 ∧ 14 < 18 ∧ (14 ^ 6 - 1).Coprime (18 ^ 6 - 1) decide All goals completed! 🐙⟩ (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ ∀ l < 18, ∀ k < l, 2 ≤ k → ¬(k ^ 6 - 1).Coprime (l ^ 6 - 1) decide +kernel All goals completed! 🐙), three 7 (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ (2 ^ 7 - 1).Coprime (3 ^ 7 - 1) decide All goals completed! 🐙),
key 8 6 ⟨5, by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ 2 ≤ 5 ∧ 5 < 6 ∧ (5 ^ 8 - 1).Coprime (6 ^ 8 - 1) decide All goals completed! 🐙⟩ (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ ∀ l < 6, ∀ k < l, 2 ≤ k → ¬(k ^ 8 - 1).Coprime (l ^ 8 - 1) decide +kernel All goals completed! 🐙), three 9 (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ (2 ^ 9 - 1).Coprime (3 ^ 9 - 1) decide All goals completed! 🐙),
key 10 12 ⟨11, by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ 2 ≤ 11 ∧ 11 < 12 ∧ (11 ^ 10 - 1).Coprime (12 ^ 10 - 1) decide All goals completed! 🐙⟩ (by key:∀ (n m : ℕ),
(∃ k, 2 ≤ k ∧ k < m ∧ (k ^ n - 1).Coprime (m ^ n - 1)) →
(∀ l < m, ∀ k < l, 2 ≤ k → ¬(k ^ n - 1).Coprime (l ^ n - 1)) → H n = mthree:∀ (n : ℕ), (2 ^ n - 1).Coprime (3 ^ n - 1) → H n = 3⊢ ∀ l < 12, ∀ k < l, 2 ≤ k → ¬(k ^ 10 - 1).Coprime (l ^ 10 - 1) decide +kernel All goals completed! 🐙)⟩
Let $H(n)$ be the smallest integer $l$ such that there exists $k < l$ with $(k^n-1, l^n-1) = 1$.
Is it true that $H(n) = 3$ infinitely often? That is, is $(2^n-1, 3^n-1) = 1$ for infinitely
many $n$ (see Erdos820.H_eq_three_iff)?
The request to estimate $H(n)$ is open-ended and not formalised; the variants below state the specific questions that are asked. See also Erdős Problem 770.
@[category research open, question, AMS 11]
theorem erdos_820 : {n : ℕ | H n = 3}.Infinite := by ⊢ {n | H n = 3}.Infinite
sorry All goals completed! 🐙Is it true that there exists some constant $c > 0$ such that, for all $\epsilon > 0$, $$ H(n) > \exp\left(n^{(c-\epsilon)/\log\log n}\right) $$ for infinitely many $n$ and $$ H(n) < \exp\left(n^{(c+\epsilon)/\log\log n}\right) $$ for all large enough $n$?
@[category research open, question, AMS 11]
theorem erdos_820.variants.log_log_exponent :
∃ c > (0 : ℝ), ∀ ε > (0 : ℝ),
(∃ᶠ n : ℕ in atTop,
Real.exp ((n : ℝ) ^ ((c - ε) / Real.log (Real.log (n : ℝ)))) < (H n : ℝ)) ∧
∀ᶠ n : ℕ in atTop,
(H n : ℝ) < Real.exp ((n : ℝ) ^ ((c + ε) / Real.log (Real.log (n : ℝ)))) := by ⊢ ∃ c > 0,
∀ ε > 0,
(∃ᶠ (n : ℕ) in atTop, Real.exp (↑n ^ ((c - ε) / Real.log (Real.log ↑n))) < ↑(H n)) ∧
∀ᶠ (n : ℕ) in atTop, ↑(H n) < Real.exp (↑n ^ ((c + ε) / Real.log (Real.log ↑n)))
sorry All goals completed! 🐙Let $K(n)$ be the smallest $k$ such that $(k^n-1, 2^n-1) = 1$. Does a similar upper bound hold for $K(n)$? That is, is there a constant $c > 0$ such that, for all $\epsilon > 0$, $$ K(n) < \exp\left(n^{(c+\epsilon)/\log\log n}\right) $$ for all large enough $n$?
We read "similar" as an upper bound of the same shape, with its own constant $c$, which need
not be the same as in Erdos820.erdos_820.variants.log_log_exponent.
@[category research open, question, AMS 11]
theorem erdos_820.variants.two_pow_upper :
∃ c > (0 : ℝ), ∀ ε > (0 : ℝ), ∀ᶠ n : ℕ in atTop,
(K n : ℝ) < Real.exp ((n : ℝ) ^ ((c + ε) / Real.log (Real.log (n : ℝ)))) := by ⊢ ∃ c > 0, ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, ↑(K n) < Real.exp (↑n ^ ((c + ε) / Real.log (Real.log ↑n)))
sorry All goals completed! 🐙Erdős [Er74b] proved that there exists a constant $c > 0$ such that $$ H(n) > \exp\left(n^{c/(\log\log n)^2}\right) $$ for infinitely many $n$.
@[category research solved, AMS 11]
theorem erdos_820.variants.erdos_lower :
∃ c > (0 : ℝ), ∃ᶠ n : ℕ in atTop,
Real.exp ((n : ℝ) ^ (c / Real.log (Real.log (n : ℝ)) ^ 2)) < (H n : ℝ) := by ⊢ ∃ c > 0, ∃ᶠ (n : ℕ) in atTop, Real.exp (↑n ^ (c / Real.log (Real.log ↑n) ^ 2)) < ↑(H n)
sorry All goals completed! 🐙end Erdos820