Erdős Problem 1113

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 \geq 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.

def Erdos1113.HasFinitePrimeCoveringSet (k : ℕ) : Prop

A covering set for a positive odd integer $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$.

Equations

• Erdos1113.HasFinitePrimeCoveringSet k = ∃ (P : Finset ℕ), (∀ p ∈ P, Nat.Prime p) ∧ ∀ (n : ℕ), ∃ p ∈ P, p ∣ k * 2 ^ n + 1

theorem Erdos1113.erdos_1113.variants.infinitely_many_sierpinski : {k : ℕ | k.IsSierpinskiNumber}.Infinite

Sierpiński [Si60] proved that there are infinitely many Sierpiński numbers, using covering systems to construct suitable covering sets for any $k$ satisfying a certain congruence.

theorem Erdos1113.erdos_1113 : True ↔ ∃ (k : ℕ), k.IsSierpinskiNumber ∧ ¬HasFinitePrimeCoveringSet k

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.

theorem Erdos1113.erdos_1113.variants.filaseta_finch_kozek (k : ℕ) : k.IsSierpinskiNumber → k.IsPerfectPower ∨ HasFinitePrimeCoveringSet k

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