Erdős #32: no O(log N) complement to the primes (Radomskii)

Erdős Problem #32 asks how thin a set A of non-negative integers can be if every large integer is a prime plus an element of A. Erdős showed in 1954 that about (log N)^2 elements up to N are enough. He asked whether o((log N)^2) or even O(log N) is possible, and offered $50 for the O(log N) question (erdosproblems.com, citing Guy’s Unsolved Problems). Ruzsa proved that at least e^γ·log N elements are needed and conjectured that the ratio to log N must tend to infinity.

On 9 Oct 2026 Artyom Radomskii of HSE University posted an eight-page paper proving that at least c·log X·log log X elements are needed. This answers the O(log N) question negatively and proves Ruzsa’s Conjecture 2 in a quantitative form. Given a candidate set B, he constructs a block of consecutive integers in [X/2, X] that avoids every p + b. The analytic input is a “large-shift lemma” from his 29 Sep paper on Romanoff numbers (integers of the form p + 2^n), where it improves a bound of Kalmynin and Konyagin.

That lemma is where the AI connection lies. In the Romanoff paper Radomskii writes that he uses “the weight construction in [5, §4]”, and in the new paper that the lemma’s proof “adapts the truncated divisor-sum construction of [2]”. Both references are OpenAI’s “Improved Long Gaps Between Primes”, the GPT-6 Astra write-up of the prime-gap improvement that a user generated with GPT-5.6 on erdosproblems.com in August 2026. Neither of Radomskii’s papers says that he used an AI model.

This is a second-generation effect: a technique that first appeared in an AI-generated proof is picked up by a human specialist and settles part of a different Erdős problem within weeks. The main question of #32, whether o((log N)^2) is achievable, is still open. The result is an unrefereed preprint and had not been reviewed on erdosproblems.com by 15 Oct.