/-
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 969
References:
Moser, L. and MacLeod, R. A., The error term for the squarefree integers. Canadian Mathematical Bulletin 9 (1966), 303–306. https://doi.org/10.4153/CMB-1966-039-4
@[expose] public sectionnamespace Erdos969open Filter Asymptotics
The squarefree counting function Q(x).
def squarefreeCounting (x : ℕ) : ℕ :=
((Finset.Icc 1 x).filter Squarefree).cardExactly seven integers in $[1,10]$ are squarefree, including $1$.
@[category test, AMS 11]
theorem squarefreeCounting_ten : squarefreeCounting 10 = 7 := ⊢ squarefreeCounting 10 = 7
All goals completed! 🐙
The error term in Q(x) = (6 / π^2) x + E(x).
noncomputable def squarefreeCountingError (x : ℕ) : ℝ :=
(squarefreeCounting x : ℝ) - 6 / Real.pi ^ 2 * xdef erdos_969.answer : ℕ → ℝ := sorryLet $Q(x)$ count the squarefree integers in $[1,x]$, and define $E(x)$ by $$Q(x)=\frac{6}{\pi^2}x+E(x).$$ Determine the order of magnitude of $E(x)$: an upper bound $E(x)=O(g(x))$ with a matching oscillation bound $E(x)\ne o(g(x))$.
@[category research open, question value, AMS 11]
theorem erdos_969 :
let g := erdos_969.answer
(fun x => |squarefreeCountingError x|) =O[atTop] g ∧
¬(fun x => |squarefreeCountingError x|) =o[atTop] g := ⊢ let g := erdos_969.answer;
(fun x ↦ |squarefreeCountingError x|) =O[atTop] g ∧ ¬(fun x ↦ |squarefreeCountingError x|) =o[atTop] g
All goals completed! 🐙The prime number theorem implies $E(x)=o(\sqrt{x})$.
@[category research solved, AMS 11]
theorem erdos_969.variants.prime_number_theorem :
(fun x => |squarefreeCountingError x|) =o[atTop] (fun x : ℕ => (x : ℝ).sqrt) := ⊢ (fun x ↦ |squarefreeCountingError x|) =o[atTop] fun x ↦ √↑x
All goals completed! 🐙Evelyn and Linfoot proved $E(x)=\Omega(x^{1/4})$.
@[category research solved, AMS 11]
theorem erdos_969.variants.evelyn_linfoot :
¬(fun x => |squarefreeCountingError x|) =o[atTop]
(fun x : ℕ => (x : ℝ) ^ (1 / 4 : ℝ)) := ⊢ ¬(fun x ↦ |squarefreeCountingError x|) =o[atTop] fun x ↦ ↑x ^ (1 / 4)
All goals completed! 🐙end Erdos969