Erdős Problem #26

Erdős problem #26 · erdosproblems.com/26

Let $A\subset\mathbb{N}$ be infinite. Must there exist some $k\geq 1$ such that almost all integers have a divisor of the form $a+k$ for some $a\in A$? The question as posed follows negatively from Davenport–Erdős (1951). The AI result settles Tenenbaum's harder variant, also negatively: there is an infinite $A$ such that for every $k\geq 1$ the set of multiples of $A+k$ has upper density below $0.34$.

Result

Disproved(see note)

Status

Variant only

AI contribution

AI-discovered

Method

Construction

Field

Number Theory, Divisors

Posed by

Paul Erdős, Gérald Tenenbaum

Year posed

1995

Years open

31y

Solved

2026-04-06

Model

DeepMind prover agent

Vendor

Google DeepMind

Collaborators

—

Verification

Site-confirmed

Publication

Announced

Significance

10 / 100*

Disclosed cost

—

Wikipedia

No dedicated article