/-
Copyright 2025 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 999
References:
[Er64b] Erdős, P., Problems and results on diophantine approximations. Compositio Math. (1964), 52-65.
[KoMa20] Koukoulopoulos, Dimitris and Maynard, James, On the Duffin-Schaeffer conjecture. Ann. of Math. (2) (2020), 251--307.
@[expose] public sectionopen MeasureTheorynamespace Erdos999
x is approximable with respect to f if
$$\left\lvert x-\frac{p}{q}\right\rvert < \frac{f(q)}{q}$$
has infinitely many solutions with $(p,q)=1$.
def IsApproximable (f : ℕ → ℝ) (x : ℝ) : Prop :=
{q : ℕ | 0 < q ∧ ∃ p : ℤ, Int.gcd p q = 1 ∧ |x - p / q| < f q / q}.InfiniteFor any function $f:\mathbb{N}\to \mathbb{R}{\geq 0}$ the property that, for almost all $\alpha$ $$\left\lvert \alpha-\frac{p}{q}\right\rvert < \frac{f(q)}{q}$$ has infinitely many solutions with $(p,q)=1$, is equivalent to $$\sum{q\geq 1}\phi(q)\frac{f(q)}{q}=\infty.$$
The Duffin–Schaeffer conjecture. It is easy to prove that the latter follows from the former. Erdős proved this in the special case when $f(q)q$ is bounded. The full conjecture was proved by Koukoulopoulos and Maynard [KoMa20].
@[category research solved, question, AMS 11]
theorem erdos_999 : ∀ f : ℕ → ℝ, (∀ q, 0 ≤ f q) →
((∀ᵐ x : ℝ, IsApproximable f x) ↔
¬ Summable fun q : ℕ ↦ (Nat.totient q : ℝ) * f q / q) := ⊢ ∀ (f : ℕ → ℝ), (∀ (q : ℕ), 0 ≤ f q) → ((∀ᵐ (x : ℝ), IsApproximable f x) ↔ ¬Summable fun q ↦ ↑q.totient * f q / ↑q)
All goals completed! 🐙It is easy to prove that divergence of the series follows from approximability almost everywhere (the Borel–Cantelli lemma).
@[category textbook, AMS 11]
theorem erdos_999.variants.easy_direction (f : ℕ → ℝ) (hf : ∀ q, 0 ≤ f q)
(h : ∀ᵐ x : ℝ, IsApproximable f x) :
¬ Summable fun q : ℕ ↦ (Nat.totient q : ℝ) * f q / q := f:ℕ → ℝhf:∀ (q : ℕ), 0 ≤ f qh:∀ᵐ (x : ℝ), IsApproximable f x⊢ ¬Summable fun q ↦ ↑q.totient * f q / ↑q
All goals completed! 🐙Erdős [Er64b] proved the conjecture in the special case when $f(q)q$ is bounded.
@[category research solved, AMS 11]
theorem erdos_999.variants.erdos (f : ℕ → ℝ) (hf : ∀ q, 0 ≤ f q)
(hb : ∃ C : ℝ, ∀ q, f q * q ≤ C) :
(∀ᵐ x : ℝ, IsApproximable f x) ↔
¬ Summable fun q : ℕ ↦ (Nat.totient q : ℝ) * f q / q := f:ℕ → ℝhf:∀ (q : ℕ), 0 ≤ f qhb:∃ C, ∀ (q : ℕ), f q * ↑q ≤ C⊢ (∀ᵐ (x : ℝ), IsApproximable f x) ↔ ¬Summable fun q ↦ ↑q.totient * f q / ↑q
All goals completed! 🐙end Erdos999