Erdős Problem 1102

Reference: erdosproblems.com/1102

def Erdos1102.HasPropertyP (A : Set ℕ) : Prop

Property P : A set $A ⊆ ℕ $ has property P, if for all $n ≥ 1$ the set $ \{a ∈ A | n + a\text{ is squarefree}\}$ is finite.

Equations

• Erdos1102.HasPropertyP A = ∀ n ≥ 1, {a : ℕ | a ∈ A ∧ Squarefree (n + a)}.Finite

def Erdos1102.HasPropertyQ (A : Set ℕ) : Prop

Property Q : A set $A ⊆ ℕ $ has property Q, if the set $\{n ∈ ℕ | ∀ a ∈ A, n > a\text{ implies }n + a\text{ is squarefree}\}$ is infinite.

Equations

• Erdos1102.HasPropertyQ A = {n : ℕ | ∀ a ∈ A, a < n → Squarefree (n + a)}.Infinite

theorem Erdos1102.erdos_1102.density_zero_of_P (A : ℕ → ℕ) (h_inc : StrictMono A) (hP : HasPropertyP (Set.range A)) : Filter.Tendsto (fun (j : ℕ) => ↑(A j) / ↑j) Filter.atTop Filter.atTop

If A = {a₁ < a₂ < …} has property P, then A has natural density 0. Equivalently, (a_j / j) → ∞ as j → ∞.

theorem Erdos1102.erdos_1102.exists_sequence_with_P (f : ℕ → ℕ) (h_inf : Filter.Tendsto f Filter.atTop Filter.atTop) (h_pos : ∀ (n : ℕ), f n ≠ 0) : ∃ (A : ℕ → ℕ), StrictMono A ∧ HasPropertyP (Set.range A) ∧ ∀ (j : ℕ), ↑(A j) / ↑j ≤ ↑(f j)

Conversely, for any function f : ℕ → ℕ that goes to infinity, there exists a strictly increasing sequence A = {a₁ < a₂ < …} with property P such that (a_j / j) ≤ f(j) for all j.

theorem Erdos1102.erdos_1102.upper_density_Q (A : ℕ → ℕ) (h_inc : StrictMono A) (hQ : HasPropertyQ (Set.range A)) : ↑(Filter.limsup (fun (j : ℕ) => j / A j) Filter.atTop) ≤ 6 / Real.pi ^ 2

Every sequence with property Q has upper density at most 6 / π^2.

theorem Erdos1102.erdos_1102.lower_density_Q_exists : ∃ (A : ℕ → ℕ), StrictMono A ∧ (∀ (j : ℕ), Squarefree (A j)) ∧ HasPropertyQ (Set.range A) ∧ Filter.Tendsto (fun (j : ℕ) => ↑j / ↑(A j)) Filter.atTop (nhds (6 / Real.pi ^ 2))

There exists an infinite sequence $A = {a₁ < a₂ < …} ⊂ \mathsf{SF}$ where $\mathsf{SF} := \mathbb{N} \setminus \bigcup_{p} p^{2}\mathbb{N}$, i.e. the set of squarefree numbers. The set A has property Q and natural density 6 / π^2. Equivalently, (j / a_j) → 6/π^2 as j → ∞.