/- 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 FormalConjecturesUtil public import FormalConjectures.GreensOpenProblems.«46»

Erdős Problem 687

References:

    erdosproblems.com/687

    Ben Green's Open Problem 46: the same question; see Green46 in FormalConjectures.GreensOpenProblems.«46».

    OEIS A058989: the values $Y(p_n)$, where $p_n$ is the $n$-th prime.

    OEIS A048670: Jacobsthal's function of $\prod_{p \leq p_n} p$, which is $Y(p_n) + 1$.

    [Er79d] Erdős, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. 33 (1979), 71-80.

    [Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89-115.

    [Er96b] Erdős, Paul, Some problems I presented or planned to present in my short talk. Analytic number theory, Vol. 1 (Allerton Park, IL, 1995), Progr. Math. 138 (1996), 333-335.

    [Iw78] Iwaniec, Henryk, On the problem of Jacobsthal. Demonstratio Math. 11 (1978), 225-232. doi:10.1515/dema-1978-0121

    [MaPo90] Maier, Helmut and Pomerance, Carl, Unusually large gaps between consecutive primes. Trans. Amer. Math. Soc. 322 (1990), 201-237.

    [FGKMT18] Ford, Kevin and Green, Ben and Konyagin, Sergei and Maynard, James and Tao, Terence, Long gaps between primes. J. Amer. Math. Soc. 31 (2018), 65-105. arXiv:1412.5029

    [OAI26a] OpenAI, A quadratic bound for Jacobsthal's function. OpenAI Math Release preprint (2026). https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-quadratic-bound-for-Jacobsthals-function-September-25-2026/paper.pdf

@[expose] public sectionopen Filternamespace Erdos687

Y x is $Y(x)$, the maximal $y$ such that there is a choice of congruence classes $a_p$, one for each prime $p \leq x$, such that every integer in $[1, y]$ is congruent to at least one of the $a_p \pmod{p}$. The covering condition is Green46.IsCoveredByResidues x y.

We take $x$ to be a natural number, since $Y(x)$ only depends on $\lfloor x \rfloor$. The set of such $y$ contains $0$ and is bounded by $\prod_{p \leq x} p$ (Erdos687.lt_primorial_of_isCoveredByResidues), so sSup is its maximum. $Y(x) = 0$ for $x < 2$.

noncomputable def Y (x : ℕ) : ℕ := sSup {y : ℕ | Green46.IsCoveredByResidues x y}

Green46.maxY is Y cast to ℝ.

@[category test, AMS 11] theorem maxY_eq_Y (x : ℕ) : Green46.maxY x = Y x := rfl

If $[1, y]$ is covered by classes $a_p \pmod{p}$, $p \leq x$, then $y < \prod_{p \leq x} p$: by the Chinese remainder theorem some integer in $[1, \prod_{p \leq x} p]$ lies in none of the classes.

x:ℕy:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ x, Nat.Prime p ∧ m ≡ a p [MOD p]hy:primorial x ≤ yt:Finset ℕ := Finset.filter Nat.Prime (Finset.range (x + 1))hs:∀ p ∈ t, (fun p ↦ p) p ≠ 0pp:(↑t).Pairwise (Function.onFun Nat.Coprime fun p ↦ p)k:{ k // ∀ i ∈ t, k ≡ a i + 1 [MOD i] } := Nat.chineseRemainderOfFinset (fun p ↦ a p + 1) (fun p ↦ p) t hs pphk:↑k < primorial xm:ℕhm1:1 ≤ mhmP:m ≤ primorial xhmk:∀ p ∈ t, m ≡ ↑k [MOD p]p:ℕhpx:p ≤ xhp:Nat.Prime phpm:m ≡ a p [MOD p]hpt:p ∈ th1:a p ≡ a p + 1 [MOD p]hd:p ∣ 1⊢ False All goals completed! 🐙

With the single prime $2$, one class covers $1$ but no class covers both $1$ and $2$, so $Y(2) = 1$.

h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ sSup {y | Green46.IsCoveredByResidues 2 y} = 1 All goals completed! 🐙

The classes $1 \pmod 2$ and $2 \pmod 3$ cover $1, 2, 3$, but no choice of classes modulo $2$ and $3$ covers $1, 2, 3, 4$, so $Y(3) = 3$.

h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ sSup {y | Green46.IsCoveredByResidues 3 y} = 3 All goals completed! 🐙def erdos_687.parts.i.answer : ℕ → ℝ := sorry

Let $Y(x)$ be the maximal $y$ such that there exists a choice of congruence classes $a_p$ for all primes $p\leq x$ such that every integer in $[1,y]$ is congruent to at least one of the $a_p\pmod{p}$. Give good estimates for $Y(x)$.

We formalise this as determining $Y(x)$ up to constant factors.

@[category research open, question value, AMS 11] theorem erdos_687.parts.i : (fun x : ℕ ↦ (Y x : ℝ)) =Θ[atTop] erdos_687.parts.i.answer := ⊢ (fun x ↦ ↑(Y x)) =Θ[atTop] i.answer All goals completed! 🐙

In particular, can one prove that $Y(x)=o(x^2)$?

Yes: an internal OpenAI model proved $h(k) \ll k^2$ for Jacobsthal's function $h$ [OAI26a] (see Erdos970.erdos_970). Since $Y(x) + 1$ is Jacobsthal's function of $\prod_{p \leq x} p$, which has $\pi(x) \ll x/\log x$ prime factors, this gives $Y(x) \ll x^2/(\log x)^2$. The linked Lean proof is by 30k30, from the bound of [OAI26a].

@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/30k30/scholia/blob/b072c89c3edac06521868e32cc15b2bc91bd8533/erdos-687/glue/JacobsthalTo687.lean#L325"] theorem erdos_687.parts.ii : (fun x : ℕ ↦ (Y x : ℝ)) =o[atTop] (fun x : ℕ ↦ (x : ℝ) ^ 2) := ⊢ (fun x ↦ ↑(Y x)) =o[atTop] fun x ↦ ↑x ^ 2 All goals completed! 🐙

Or, even stronger, can one prove that $Y(x)\ll x^{1+o(1)}$?

We read $Y(x)\ll x^{1+o(1)}$ as $Y(x) = O(x^{1+\varepsilon})$ for every fixed $\varepsilon > 0$.

@[category research open, question, AMS 11] theorem erdos_687.parts.iii : ∀ ε > (0 : ℝ), (fun x : ℕ ↦ (Y x : ℝ)) =O[atTop] (fun x : ℕ ↦ (x : ℝ) ^ (1 + ε)) := ⊢ ∀ ε > 0, (fun x ↦ ↑(Y x)) =O[atTop] fun x ↦ ↑x ^ (1 + ε) All goals completed! 🐙

Iwaniec's upper bound for Jacobsthal's function [Iw78] gives $Y(x) \ll x^2$.

@[category research solved, AMS 11] theorem erdos_687.variants.iwaniec : (fun x : ℕ ↦ (Y x : ℝ)) =O[atTop] (fun x : ℕ ↦ (x : ℝ) ^ 2) := ⊢ (fun x ↦ ↑(Y x)) =O[atTop] fun x ↦ ↑x ^ 2 All goals completed! 🐙

Ford, Green, Konyagin, Maynard and Tao [FGKMT18] proved $$Y(x) \gg \frac{x \log x \log\log\log x}{\log\log x}.$$

@[category research solved, AMS 11] theorem erdos_687.variants.fgkmt : (fun x : ℕ ↦ (x : ℝ) * Real.log x * Real.log (Real.log (Real.log x)) / Real.log (Real.log x)) =O[atTop] (fun x : ℕ ↦ (Y x : ℝ)) := ⊢ (fun x ↦ ↑x * Real.log ↑x * Real.log (Real.log (Real.log ↑x)) / Real.log (Real.log ↑x)) =O[atTop] fun x ↦ ↑(Y x) All goals completed! 🐙

Maier and Pomerance [MaPo90] conjectured that $Y(x) \ll x(\log x)^{2+o(1)}$ (in this form it is stated in [FGKMT18]).

We read this as $Y(x) = O(x(\log x)^{2+\varepsilon})$ for every fixed $\varepsilon > 0$.

@[category research open, AMS 11] theorem erdos_687.variants.maier_pomerance : ∀ ε > (0 : ℝ), (fun x : ℕ ↦ (Y x : ℝ)) =O[atTop] (fun x : ℕ ↦ (x : ℝ) * Real.log x ^ (2 + ε)) := ⊢ ∀ ε > 0, (fun x ↦ ↑(Y x)) =O[atTop] fun x ↦ ↑x * Real.log ↑x ^ (2 + ε) All goals completed! 🐙end Erdos687