/-
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 675
References:
[Er79] Erdős, Paul, Some unconventional problems in number theory. Math. Mag. (1979), 67-70.
[Ho26] Ho, B. S., A squarefree lower bound for Erdős Problem 675. PDF (2026).
@[expose] public sectionopen Asymptotics Filternamespace Erdos675
IsTranslation A n t says that $t \geq 1$ and, for all $1 \leq a \leq n$, $a \in A$ if and
only if $a + t \in A$.
def IsTranslation (A : Set ℕ) (n t : ℕ) : Prop :=
1 ≤ t ∧ ∀ a : ℕ, 1 ≤ a → a ≤ n → (a ∈ A ↔ a + t ∈ A)A set $A \subseteq \mathbb{N}$ has the translation property if, for every $n$, there is an integer $t_n \geq 1$ such that, for all $1 \leq a \leq n$, $a \in A$ if and only if $a + t_n \in A$.
def HasTranslationProperty (A : Set ℕ) : Prop :=
∀ n : ℕ, ∃ t : ℕ, IsTranslation A n t
minTranslation A n is the least $t_n \geq 1$ such that, for all $1 \leq a \leq n$,
$a \in A$ if and only if $a + t_n \in A$. It is 0 if there is no such $t_n$.
noncomputable def minTranslation (A : Set ℕ) (n : ℕ) : ℕ :=
sInf {t : ℕ | IsTranslation A n t}
composedOf P is the set of positive integers all of whose prime factors lie in P
(a version of Nat.factoredNumbers for an arbitrary set P). It contains $1$.
def composedOf (P : Set ℕ) : Set ℕ :=
{m : ℕ | 0 < m ∧ ∀ p : ℕ, p.Prime → p ∣ m → p ∈ P}The set ${1}$ does not have the translation property: for $n = 1$ it would need $1 + t \in {1}$ for some $t \geq 1$.
h:HasTranslationProperty {1}t:ℕht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 1 → (a ∈ {1} ↔ a + t ∈ {1})h1:1 + t = 1⊢ False
omega All goals completed! 🐙The numbers $1, 2, 3$ are squarefree, and $t = 4$ is the least $t \geq 1$ such that $1 + t$, $2 + t$ and $3 + t$ are all squarefree.
@[category test, AMS 11]
theorem minTranslation_squarefree_three : minTranslation {m : ℕ | Squarefree m} 3 = 4 := by ⊢ minTranslation {m | Squarefree m} 3 = 4
refine IsLeast.csInf_eq ⟨⟨by ⊢ 1 ≤ 4 norm_num All goals completed! 🐙, fun a ha1 ha3 ↦ ?_⟩, fun t ⟨ht1, ht⟩ ↦ ?_⟩
· refine_1 a:ℕha1:1 ≤ aha3:a ≤ 3⊢ a ∈ {m | Squarefree m} ↔ a + 4 ∈ {m | Squarefree m} interval_cases a refine_1.«1» a:ℕha1:1 ≤ 1ha3:1 ≤ 3⊢ 1 ∈ {m | Squarefree m} ↔ 1 + 4 ∈ {m | Squarefree m}refine_1.«2» a:ℕha1:1 ≤ 2ha3:2 ≤ 3⊢ 2 ∈ {m | Squarefree m} ↔ 2 + 4 ∈ {m | Squarefree m}refine_1.«3» a:ℕha1:1 ≤ 3ha3:3 ≤ 3⊢ 3 ∈ {m | Squarefree m} ↔ 3 + 4 ∈ {m | Squarefree m} <;> refine_1.«1» a:ℕha1:1 ≤ 1ha3:1 ≤ 3⊢ 1 ∈ {m | Squarefree m} ↔ 1 + 4 ∈ {m | Squarefree m}refine_1.«2» a:ℕha1:1 ≤ 2ha3:2 ≤ 3⊢ 2 ∈ {m | Squarefree m} ↔ 2 + 4 ∈ {m | Squarefree m}refine_1.«3» a:ℕha1:1 ≤ 3ha3:3 ≤ 3⊢ 3 ∈ {m | Squarefree m} ↔ 3 + 4 ∈ {m | Squarefree m} simp [Nat.squarefree_iff_nodup_primeFactorsList] All goals completed! 🐙
· refine_2 t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})⊢ 4 ≤ t by_contra! h refine_2 t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4⊢ False
have := ht (4 - t) (by t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4⊢ 1 ≤ 4 - t refine_2 t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4this:4 - t ∈ {m | Squarefree m} ↔ 4 - t + t ∈ {m | Squarefree m}⊢ False omega All goals completed! 🐙 refine_2 t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4this:4 - t ∈ {m | Squarefree m} ↔ 4 - t + t ∈ {m | Squarefree m}⊢ False) (by t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4⊢ 4 - t ≤ 3refine_2 t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4this:4 - t ∈ {m | Squarefree m} ↔ 4 - t + t ∈ {m | Squarefree m}⊢ False omega All goals completed! 🐙refine_2 t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4this:4 - t ∈ {m | Squarefree m} ↔ 4 - t + t ∈ {m | Squarefree m}⊢ False)refine_2 t:ℕx✝:t ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ tht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + t ∈ {m | Squarefree m})h:t < 4this:4 - t ∈ {m | Squarefree m} ↔ 4 - t + t ∈ {m | Squarefree m}⊢ False
interval_cases t refine_2.«1» t:ℕx✝:1 ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ 1ht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + 1 ∈ {m | Squarefree m})h:1 < 4this:4 - 1 ∈ {m | Squarefree m} ↔ 4 - 1 + 1 ∈ {m | Squarefree m}⊢ Falserefine_2.«2» t:ℕx✝:2 ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ 2ht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + 2 ∈ {m | Squarefree m})h:2 < 4this:4 - 2 ∈ {m | Squarefree m} ↔ 4 - 2 + 2 ∈ {m | Squarefree m}⊢ Falserefine_2.«3» t:ℕx✝:3 ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ 3ht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + 3 ∈ {m | Squarefree m})h:3 < 4this:4 - 3 ∈ {m | Squarefree m} ↔ 4 - 3 + 3 ∈ {m | Squarefree m}⊢ False <;> refine_2.«1» t:ℕx✝:1 ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ 1ht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + 1 ∈ {m | Squarefree m})h:1 < 4this:4 - 1 ∈ {m | Squarefree m} ↔ 4 - 1 + 1 ∈ {m | Squarefree m}⊢ Falserefine_2.«2» t:ℕx✝:2 ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ 2ht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + 2 ∈ {m | Squarefree m})h:2 < 4this:4 - 2 ∈ {m | Squarefree m} ↔ 4 - 2 + 2 ∈ {m | Squarefree m}⊢ Falserefine_2.«3» t:ℕx✝:3 ∈ {t | IsTranslation {m | Squarefree m} 3 t}ht1:1 ≤ 3ht:∀ (a : ℕ), 1 ≤ a → a ≤ 3 → (a ∈ {m | Squarefree m} ↔ a + 3 ∈ {m | Squarefree m})h:3 < 4this:4 - 3 ∈ {m | Squarefree m} ↔ 4 - 3 + 3 ∈ {m | Squarefree m}⊢ False simp [Nat.squarefree_iff_nodup_primeFactorsList] at this All goals completed! 🐙
If P contains every prime, then composedOf P is the set of all positive integers.
@[category test, AMS 11]
theorem composedOf_primes : composedOf {p : ℕ | p.Prime} = {m : ℕ | 0 < m} := by ⊢ composedOf {p | Nat.Prime p} = {m | 0 < m}
ext m m:ℕ⊢ m ∈ composedOf {p | Nat.Prime p} ↔ m ∈ {m | 0 < m}
show (0 < m ∧ ∀ p : ℕ, p.Prime → p ∣ m → p ∈ {p : ℕ | p.Prime}) ↔ 0 < m m:ℕ⊢ (0 < m ∧ ∀ (p : ℕ), Nat.Prime p → p ∣ m → p ∈ {p | Nat.Prime p}) ↔ 0 < m
exact ⟨fun h ↦ h.1, fun h ↦ ⟨h, fun _ hp _ ↦ hp⟩⟩ All goals completed! 🐙A set $A \subseteq \mathbb{N}$ has the translation property if, for every $n$, there is an integer $t_n \geq 1$ such that, for all $1 \leq a \leq n$, $a \in A$ if and only if $a + t_n \in A$. Does the set of sums of two squares ${x^2 + y^2 : x, y \in \mathbb{N}}$ have the translation property?
@[category research open, question, AMS 11]
theorem erdos_675.parts.i :
HasTranslationProperty {m : ℕ | ∃ x y : ℕ, m = x ^ 2 + y ^ 2} := by ⊢ HasTranslationProperty {m | ∃ x y, m = x ^ 2 + y ^ 2}
sorry All goals completed! 🐙If we partition all primes into $P\sqcup Q$, such that each set contains $\gg x/\log x$ many primes $\leq x$ for all large $x$, then can the set of integers only divisible by primes from $P$ have the translation property?
We read "can" as: is there such a partition for which this set (which contains $1$) has the translation property?
@[category research open, question, AMS 11]
theorem erdos_675.parts.ii :
∃ P : Set ℕ, P ⊆ {p : ℕ | p.Prime} ∧
(fun x : ℕ ↦ (x : ℝ) / Real.log x) =O[atTop] (fun x ↦ ((P ∩ Set.Iic x).ncard : ℝ)) ∧
(fun x : ℕ ↦ (x : ℝ) / Real.log x) =O[atTop]
(fun x ↦ ((({p : ℕ | p.Prime} \ P) ∩ Set.Iic x).ncard : ℝ)) ∧
HasTranslationProperty (composedOf P) := by ⊢ ∃ P ⊆ {p | Nat.Prime p},
((fun x ↦ ↑x / Real.log ↑x) =O[atTop] fun x ↦ ↑(P ∩ Set.Iic x).ncard) ∧
((fun x ↦ ↑x / Real.log ↑x) =O[atTop] fun x ↦ ↑({p | Nat.Prime p} \ P ∩ Set.Iic x).ncard) ∧
HasTranslationProperty (composedOf P)
sorry All goals completed! 🐙If $A$ is the set of squarefree numbers then how fast does the minimal such $t_n$ grow? Is it true that $t_n>\exp(n^c)$ for some constant $c>0$?
We ask for the inequality for all sufficiently large $n$, since $t_1 = 1$.
Ho [Ho26] proved that the answer is yes: for every fixed $0 < c < 25/72$, $t_n > \exp(n^c)$ for all sufficiently large $n$ (Theorem 1.2 and Corollary 3.2); see also the forum discussion.
@[category research solved, question, AMS 11]
theorem erdos_675.parts.iii :
∃ c > (0 : ℝ), ∀ᶠ n : ℕ in atTop,
Real.exp ((n : ℝ) ^ c) < (minTranslation {m : ℕ | Squarefree m} n : ℝ) := by ⊢ ∃ c > 0, ∀ᶠ (n : ℕ) in atTop, Real.exp (↑n ^ c) < ↑(minTranslation {m | Squarefree m} n)
sorry All goals completed! 🐙Elementary sieve theory implies that the set of squarefree numbers has the translation property (as remarked on erdosproblems.com).
@[category research solved, AMS 11]
theorem erdos_675.variants.squarefree : HasTranslationProperty {m : ℕ | Squarefree m} := by ⊢ HasTranslationProperty {m | Squarefree m}
sorry All goals completed! 🐙open scoped Classical inLet $B \subseteq \mathbb{N}$ be a set of pairwise coprime integers with $$\sum_{b \in B,\ b < x} \frac{1}{b} = o(\log \log x).$$ Then $A = {n : b \nmid n \text{ for all } b \in B}$ has the translation property. As remarked on erdosproblems.com, this follows from Brun's sieve, and Erdős did not know what happens if the condition on the sum is weakened or dropped.
@[category research solved, AMS 11]
theorem erdos_675.variants.brun (B : Set ℕ) (hB : B.Pairwise Nat.Coprime)
(hsum : (fun x : ℕ ↦ ∑ b ∈ Finset.range x with b ∈ B, (1 : ℝ) / (b : ℝ)) =o[atTop]
fun x : ℕ ↦ Real.log (Real.log (x : ℝ))) :
HasTranslationProperty {n : ℕ | ∀ b ∈ B, ¬ b ∣ n} := by B:Set ℕhB:B.Pairwise Nat.Coprimehsum:(fun x ↦ ∑ b ∈ Finset.range x with b ∈ B, 1 / ↑b) =o[atTop] fun x ↦ Real.log (Real.log ↑x)⊢ HasTranslationProperty {n | ∀ b ∈ B, ¬b ∣ n}
sorry All goals completed! 🐙end Erdos675