/- 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

Erdős Problem 852

References:

@[expose] public sectionopen Filternamespace Erdos852

The $H$ prime gaps $d_n, d_{n+1}, \ldots, d_{n+H-1}$ are pairwise distinct.

Here $d_n = p_{n+1} - p_n$ is primeGap n, so the primes are indexed from $p_0 = 2$. The empty run $H = 0$ and every run with $H = 1$ are distinct.

def DistinctGapRun (n H : ℕ) : Prop := Set.InjOn primeGap (Set.Ico n (n + H))

The gaps $d_0, d_1 = 1, 2$ are distinct.

h0:primeGap 0 = 1h1:primeGap 1 = 2a:ℕb:ℕhab:primeGap a = primeGap bha:0 ≤ a ∧ a < 0 + 2hb:0 ≤ b ∧ b < 0 + 2ha':a = 0 ∨ a = 1hb':b = 0 ∨ b = 1⊢ a = b h0:primeGap 0 = 1h1:primeGap 1 = 2b:ℕhb:0 ≤ b ∧ b < 0 + 2hb':b = 0 ∨ b = 1hab:primeGap 0 = primeGap bha:0 ≤ 0 ∧ 0 < 0 + 2⊢ 0 = bh0:primeGap 0 = 1h1:primeGap 1 = 2b:ℕhb:0 ≤ b ∧ b < 0 + 2hb':b = 0 ∨ b = 1hab:primeGap 1 = primeGap bha:0 ≤ 1 ∧ 1 < 0 + 2⊢ 1 = b h0:primeGap 0 = 1h1:primeGap 1 = 2b:ℕhb:0 ≤ b ∧ b < 0 + 2hb':b = 0 ∨ b = 1hab:primeGap 0 = primeGap bha:0 ≤ 0 ∧ 0 < 0 + 2⊢ 0 = bh0:primeGap 0 = 1h1:primeGap 1 = 2b:ℕhb:0 ≤ b ∧ b < 0 + 2hb':b = 0 ∨ b = 1hab:primeGap 1 = primeGap bha:0 ≤ 1 ∧ 1 < 0 + 2⊢ 1 = b h0:primeGap 0 = 1h1:primeGap 1 = 2ha:0 ≤ 1 ∧ 1 < 0 + 2hb:0 ≤ 0 ∧ 0 < 0 + 2hab:primeGap 1 = primeGap 0⊢ 1 = 0h0:primeGap 0 = 1h1:primeGap 1 = 2ha:0 ≤ 1 ∧ 1 < 0 + 2hb:0 ≤ 1 ∧ 1 < 0 + 2hab:primeGap 1 = primeGap 1⊢ 1 = 1 h0:primeGap 0 = 1h1:primeGap 1 = 2ha:0 ≤ 0 ∧ 0 < 0 + 2hb:0 ≤ 0 ∧ 0 < 0 + 2hab:primeGap 0 = primeGap 0⊢ 0 = 0h0:primeGap 0 = 1h1:primeGap 1 = 2ha:0 ≤ 0 ∧ 0 < 0 + 2hb:0 ≤ 1 ∧ 1 < 0 + 2hab:primeGap 0 = primeGap 1⊢ 0 = 1h0:primeGap 0 = 1h1:primeGap 1 = 2ha:0 ≤ 1 ∧ 1 < 0 + 2hb:0 ≤ 0 ∧ 0 < 0 + 2hab:primeGap 1 = primeGap 0⊢ 1 = 0h0:primeGap 0 = 1h1:primeGap 1 = 2ha:0 ≤ 1 ∧ 1 < 0 + 2hb:0 ≤ 1 ∧ 1 < 0 + 2hab:primeGap 1 = primeGap 1⊢ 1 = 1 All goals completed! 🐙

The gaps $d_0, d_1, d_2 = 1, 2, 2$ are not distinct.

h1:primeGap 1 = 2h2:primeGap 2 = 2h:DistinctGapRun 0 3this:1 = 2⊢ False All goals completed! 🐙

Let $d_n = p_{n+1} - p_n$, where $p_n$ is the $n$th prime. Let $h(x)$ be maximal such that for some $n < x$ the numbers $d_n, d_{n+1}, \ldots, d_{n+h(x)-1}$ are all distinct [Er85c]. Estimate $h(x)$. In particular, is it true that $$h(x) > (\log x)^c$$ for some constant $c > 0$?

The statement avoids defining $h$. Since $h(x)$ is the longest such run, $h(x) > y$ holds exactly when some $n < x$ starts a run of $H > y$ distinct gaps. We state the question this way, with $x$ real. We read it as asking for one $c > 0$ such that the inequality holds for all large $x$.

The primes are indexed from $p_0 = 2$, as in primeGap. Shifting the index by one does not change the question.

@[category research open, question, AMS 11] theorem erdos_852.parts.i : ∃ c : ℝ, 0 < c ∧ ∀ᶠ x : ℝ in atTop, ∃ n : ℕ, (n : ℝ) < x ∧ ∃ H : ℕ, (Real.log x) ^ c < (H : ℝ) ∧ DistinctGapRun n H := ⊢ ∃ c, 0 < c ∧ ∀ᶠ (x : ℝ) in atTop, ∃ n, ↑n < x ∧ ∃ H, Real.log x ^ c < ↑H ∧ DistinctGapRun n H All goals completed! 🐙

Let $d_n = p_{n+1} - p_n$, where $p_n$ is the $n$th prime. Let $h(x)$ be maximal such that for some $n < x$ the numbers $d_n, d_{n+1}, \ldots, d_{n+h(x)-1}$ are all distinct [Er85c]. Estimate $h(x)$. In particular, is it true that $$h(x) = o(\log x)?$$

The statement avoids defining $h$. It says that for every $\varepsilon > 0$ and all large real $x$, every run of $H$ distinct gaps $d_n, \ldots, d_{n+H-1}$ with $n < x$ satisfies $H \leq \varepsilon \log x$. This is $h(x) \leq \varepsilon \log x$, because $h(x)$ is the longest such run.

The indexing is as in Erdos852.erdos_852.parts.i.

@[category research open, question, AMS 11] theorem erdos_852.parts.ii : ∀ ε : ℝ, 0 < ε → ∀ᶠ x : ℝ in atTop, ∀ n : ℕ, (n : ℝ) < x → ∀ H : ℕ, DistinctGapRun n H → (H : ℝ) ≤ ε * Real.log x := ⊢ ∀ (ε : ℝ), 0 < ε → ∀ᶠ (x : ℝ) in atTop, ∀ (n : ℕ), ↑n < x → ∀ (H : ℕ), DistinctGapRun n H → ↑H ≤ ε * Real.log x All goals completed! 🐙

Brun's sieve implies $h(x) \to \infty$ as $x \to \infty$ (remark on erdosproblems.com/852).

That is, for every $H$ and all large $x$ there is some $n < x$ such that $d_n, \ldots, d_{n+H-1}$ are all distinct. Since more values of $n$ are allowed as $x$ grows, this holds exactly when, for every $H$, some $n$ has $d_n, \ldots, d_{n+H-1}$ all distinct.

This also follows from Erdos6.erdos_6.variants.increasing, because strictly increasing prime gaps are distinct.

@[category research solved, AMS 11] theorem erdos_852.variants.tendsto_atTop : ∀ H : ℕ, ∀ᶠ x : ℝ in atTop, ∃ n : ℕ, (n : ℝ) < x ∧ DistinctGapRun n H := ⊢ ∀ (H : ℕ), ∀ᶠ (x : ℝ) in atTop, ∃ n, ↑n < x ∧ DistinctGapRun n H All goals completed! 🐙end Erdos852