Erdős Problem #854

The question

erdos_854.parts.i. Let $n_k$ denote the $k$th primorial, i.e. the product of the first $k$ primes.

If $1=a_1<a_2<\cdots <a_{\varphi (n_k)}=n_k-1$ is the sequence of integers coprime to $n_k$, then estimate the smallest even integer not of the form $a_{i+1}-a_i$. Are there $$\gg \underset{i}{\max }(a_{i+1}-a_i)$$ many even integers of the form $a_{j+1}-a_j$?

This is the first part. A problem of Erdős [Er85c, p. 80], who writes "integer" instead of "even integer"; all differences $a_{i+1}-a_i$ are even, so only even integers are meaningful. Here "estimate" is read as $\Theta$. Erdős first thought that for large $k$ every even $t \leq \max_i(a_{i+1}-a_i)$ is a gap, but [Ob1] reports computations of Lacampagne and Selfridge showing this fails for $n_6=30030$ (OEIS A389839 and A048670 give $20$ and $22$).

erdos_854.parts.ii. Let $n_k$ denote the $k$th primorial, i.e. the product of the first $k$ primes.

If $1=a_1<a_2<\cdots <a_{\varphi (n_k)}=n_k-1$ is the sequence of integers coprime to $n_k$, then estimate the smallest even integer not of the form $a_{i+1}-a_i$. Are there $$\gg \underset{i}{\max }(a_{i+1}-a_i)$$ many even integers of the form $a_{j+1}-a_j$?

This is the second part. We read it as: there is an absolute constant $c>0$ such that, for all large $k$, the number of distinct gap values is at least $c$ times the largest gap.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«854» (2 statements).

theorem erdos_854.parts.i :
    (fun k ↦ (minEvenNonGap k : ℝ)) =Θ[atTop] erdos_854.parts.i.answer

theorem erdos_854.parts.ii :
    ∃ c > (0 : ℝ), ∀ᶠ k : ℕ in atTop,
      c * (maxGap (kthPrimorial k) : ℝ) ≤ ((gapSet (kthPrimorial k)).card : ℝ)

What counts as progress

• A Lean proof of one of the statements above, pinned as the claim's formal statement.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already — check erdosproblems.com/854. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

• erdosproblems.com/854
• [Er85c] Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984), Lecture Notes in Math. 1122 (1985), 74-84. PDF
• [Ob1] Erdős, P., Oberwolfach Mathematical Problems, Volume 1. Mathematisches Forschungsinstitut Oberwolfach.
• OEIS A389839: smallest even number which cannot be written as the difference of two consecutive numbers which are relatively prime to the $n$th primorial. It agrees with minEvenNonGap k for $k\ge 3$.
• OEIS A048670: Jacobsthal's function of the product of the first $n$ primes, which is the largest gap.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.