Erdős Problem #1113

The question

Erdős Problem 1113. Do there exist Sierpiński numbers that possess no finite covering set of primes?

Erdős and Graham [ErGr80] conjectured that the answer is yes. A negative answer would imply that there are infinitely many Fermat primes.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«1113». answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem erdos_1113 :
    answer(sorry) ↔
      ∃ k, k.IsSierpinskiNumber ∧ ¬ HasFinitePrimeCoveringSet k

What counts as progress

• A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
• 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/1113. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

Variants

• erdos_1113.variants.filaseta_finch_kozek — Filaseta–Finch–Kozek conjecture (2008). Every Sierpiński number is either a perfect power or possesses a finite covering set of primes.

References

• erdosproblems.com/1113
• [ErGr80] Erdős, P. and Graham, R. L., Old and New Problems and Results in Combinatorial Number Theory. Monographie de l'Enseignement Mathématique, No. 28 (1980).
• [Si60] Sierpiński, W., Elementary Theory of Numbers. Państwowe Wydawnictwo Naukowe, Warsaw (1960).
• [FFK08] Filaseta, M., Finch, C., and Kozek, M., On powers associated with Sierpiński numbers, Riesel numbers and Polignac's conjecture. Journal of Number Theory 128 (2008), 1916–1940.

A positive odd integer $k$ is a Sierpiński number if $k\cdot 2^n+1$ is composite for all $n\ge 0$. A covering set for $k$ is a finite set of primes $P$ such that every number of the form $k\cdot 2^n+1$ is divisible by at least one prime in $P$.

Sierpiński (1960) proved that infinitely many Sierpiński numbers exist using covering systems. The smallest known Sierpiński number is 78557 (Selfridge). Erdős and Graham conjectured that there exist Sierpiński numbers with no finite covering set. A negative answer would imply infinitely many Fermat primes.

Note: The notion of a covering set for a Sierpiński number is closely related to a CoveringSystem of $\mathbb{Z}$ (see FormalConjecturesForMathlib.NumberTheory.CoveringSystem): a finite covering set of primes for $k$ works because the exponents $n$ for which each prime divides $k\cdot 2^n+1$ form residue classes whose union covers all of $\mathbb{Z}$, i.e. a covering system.

See also Erdős Problems 203 and 276.

Source and licence

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