--- id: "2026-10-09-erdos-32-additive-complements-primes-radomskii" url: "https://postcutoff.com/e/2026-10-09-erdos-32-additive-complements-primes-radomskii/" as_of: "2026-10-16T02:16:00+02:00" date: "2026-10-09" date_precision: day category: science importance: 3 confidence: medium status: [Awaiting review] verification: Preprint only sources: 4 editor: human editor human_review: null version: "2026-10-15" --- As of: 2026-10-16 02:16 CEST. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-10-09-erdos-32-additive-complements-primes-radomskii/ # Erdős #32: no O(log N) complement to the primes (Radomskii) Full title: Erdős Problem #32 ($50 part): additive complements to the primes cannot have size O(log N), using a sieve weight from OpenAI's AI-generated prime-gaps proof In an arXiv preprint posted on 9 Oct 2026, Artyom Radomskii (HSE University) proves that every set B for which every large integer is a prime plus an element of B has at least c·log X·log log X elements up to X. This answers negatively the question Erdős attached a $50 prize to (Erdős Problem #32: can O(log N) be achieved?) and proves a quantitative form of Ruzsa's Conjecture 2. The key lemma comes from his 29 Sep paper, which adapts the "truncated divisor-sum" weight construction of OpenAI's AI-generated "Improved Long Gaps Between Primes" preprint. Neither paper has an AI-use statement; the AI link is the borrowed method. Unrefereed; erdosproblems.com had not updated the problem by 15 Oct. ## Key facts - Paper: A. Radomskii, 'A lower bound for additive complements to the primes', arXiv 2610.14127 [math.NT], 9 Oct 2026; single author, HSE University Basic Research Program - Result (Corollary 1): every asymptotic additive complement B to the primes satisfies B(X) ≥ c·log X·log log X for an absolute c > 0. 'Corollary 1 gives a negative answer to the O(log X) question in Problem 32' - Not settled: the paper says its bound 'does not decide the separate question whether a complement can satisfy B(X) = o((log X)^2)', the main question of #32, and does not prove Ruzsa's density-1 Conjecture 1 - Previous knowledge (erdosproblems.com/32): Erdős (1954) built complements with B(N) ≪ (log N)^2; Ruzsa proved liminf B(N)/log N ≥ e^γ ≈ 1.781; the site records that Erdős offered $50 for deciding whether O(log N) is possible - AI lineage: the analytic input is the 'large-shift lemma' (Lemma 3.1) of Radomskii's 'Large gaps between Romanoff numbers' (arXiv 2609.38408, 29 Sep), whose proof 'adapts the truncated divisor-sum construction of [2]', where [2] is 'OpenAI. Improved Long Gaps Between Primes', github.com/openai/LongGapsBetweenPrimes, the GPT-6 Astra write-up of the GPT-5.6 prime-gap result - The Romanoff paper itself improves the Kalmynin–Konyagin bound for the longest block of integers in [1, X] not of the form p + 2^n to ≫ log log X, 'using the weight construction in [5, §4]' (the same OpenAI preprint) - AI disclosure: none in either PDF (acknowledgements thank only the HSE program); this entry does not claim the author used an AI model - Status: preprint, not refereed; erdosproblems.com/32 still showed 'Proof claims (0)' and a last edit of 23 Jan 2026 on 15 Oct; no Hacker News thread found ## What happened 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. ## Why it matters 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. ## What is disputed or not yet verified - Verification: unverified claim (arXiv preprint, not refereed) ## Your AI and this story - GPT-6 Astra (training cutoff April 2026): 162 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 101 days after its cutoff - Gemini 4 Argon (training cutoff March 2026): 192 days after its cutoff - Grok 4.7 (training cutoff May 2026): 131 days after its cutoff ## Sources 1. [arXiv 2610.14127: Radomskii, A lower bound for additive complements to the primes](https://arxiv.org/abs/2610.14127) (arxiv.org, paper) 2. [arXiv 2609.38408: Radomskii, Large gaps between Romanoff numbers](https://arxiv.org/abs/2609.38408) (arxiv.org, paper) 3. [OpenAI: Improved Long Gaps Between Primes (GitHub)](https://github.com/openai/LongGapsBetweenPrimes) (github.com, code) 4. [Erdős Problem #32 (erdosproblems.com)](https://www.erdosproblems.com/32) (erdosproblems.com, discussion) ## Changes - 2026-10-15 (filed): Created (both PDFs read, erdosproblems.com/32 checked, HN Algolia searched) ## Related - 2026-10-14: [Mid-October 2026: arXiv results with disclosed AI help](https://postcutoff.com/e/2026-10-14-ai-assisted-results-mid-october-2026/index.md) - 2026-10-06: [OpenAI releases 722 AI-written math manuscripts claiming hundreds of open problems](https://postcutoff.com/e/2026-10-06-openai-math-release-722-manuscripts/index.md) - 2026-08-26: [GPT-5.6 improves the Erdős–Rankin / Ford–Green–Konyagin–Maynard–Tao bound for large prime gaps](https://postcutoff.com/e/2026-08-26-erdos-rankin-large-prime-gaps-improved/index.md)