Skip to main content
London Tutorsby KnowledgeDottCom

15 November 2026 · London Tutors

You Can't Complete the Prime Numbers on the Cheap — Erdős's Question Answered

Primes are the building blocks of numbers, but on their own they leave gaps. A new paper by Artyom Radomskii shows you need far more extra numbers than Erdős hoped to fill every gap — settling a question from his famous problem list.

You Can't Complete the Prime Numbers on the Cheap — Erdős's Question Answered

Prime numbers — 2, 3, 5, 7, 11 and so on — are the building blocks of all whole numbers. Every number can be made by multiplying primes together. But what if you try to reach every number by adding instead? Take the primes, add a second set of numbers to them, and ask: can the two sets together reach every whole number? The second set is called an "additive complement" of the primes, and mathematicians have long wondered how small it can be.

The great Hungarian mathematician Paul Erdős, who posed hundreds of problems in his lifetime, asked a version of this question in his Problem 32: could a complement be as small as roughly log X — that is, growing only as slowly as the number of digits of X? It would be a remarkably economical way to fill all the gaps between primes.

The answer is no — and the proof is quantitative

A new paper by Artyom Radomskii, posted on arXiv on 9 October 2026 with a revised version on 1 November, gives a definite answer: no. Radomskii proved that any set that completes the primes must contain at least on the order of log X times log log X numbers up to X — noticeably more than Erdős's hoped-for log X. In doing so he proved a quantitative form of a conjecture by Imre Ruzsa, another giant of number theory.

The proof works by finding long stretches of numbers that the primes plus a small complement simply cannot reach. As a bonus, the same argument improves what is known about "Romanoff numbers" — numbers of the form a prime plus a power of two, like 3 + 8 = 11 — showing that there are longer and longer gaps with no Romanoff number at all.

This is a preprint, so it has not yet been through peer review, and other mathematicians will now check the argument carefully. But the result itself is exactly the kind of clean, decisive answer number theorists love: a question Erdős asked decades ago, settled with a firm lower bound.

For students, the story shows what maths really is: not just sums, but asking how small a thing can be — and proving the answer. If your child enjoys puzzles about primes and patterns, find a maths tutor who can make number theory feel like detective work, or post a tutoring request and compare tutors for your child.

Book your first lesson in maths and start tackling puzzles like the primes with a tutor who makes them click: Book your first lesson

Sources:

  • Artyom Radomskii, "Additive complements to the primes and large gaps between Romanoff numbers", arXiv:2610.14127v3, revised 1 November 2026: https://arxiv.org/abs/2610.14127

Curious about maths? Post a request on London Tutors and compare verified maths tutors — online, in person or in a group class.

Ready to find the right tutor?

Browse verified tutors, compare profiles, and book a trial lesson — free to sign up.

Find a tutor — sign up free

Related guides