Erdős Problem #872

Partial progress by GPT-5.2 Pro (16 Feb 2026): partial result. 3 AI contributions are recorded in all.

Problem
Erdős problem #872 (number theory, primitive sets); current status: open
Credit
GPT-5.2 Pro · AI on its own
Checked
Listed in Tao's wiki
Timeline
First AI contribution 2026-02-16 · wiki data as of 2026-06-30
Sources
Problem page (erdosproblems.com)Tao's AI-contributions wiki
PARTIALPer Tao's AI-contributions wiki

The problem

Consider the two-player game in which players alternately choose integers from {2,3,…,n}\{2,3,\ldots,n\} to be included in some set AA (the same set for both players) such that no a∣ba\mid b for a≠b∈Aa\neq b\in A.

The game ends when no legal move is possible. One player wants the game to last as long as possible, the other wants the game to end quickly. How long can the game be guaranteed to last for?

At least ϵn\epsilon n moves? (For ϵ>0\epsilon>0 and nn sufficiently large.) At least (1−ϵ)n2(1-\epsilon)\frac{n}{2} moves?

Statement quoted from erdosproblems.com/872, maintained by Thomas Bloom. Original source: [Er92c,p.47]. Current status there: open.

AI contributions

As recorded in Terence Tao's wiki AI contributions to Erdős problems (data as of 30 Jun 2026). 🟢 full, 🟡 partial, ⚪ unverified, 🔴 incorrect.

Date Kind AI systems Humans Outcome
16 Feb, 2026 AI on its own GPT-5.2 Pro — 🟡 Partial result
16 Apr, 2026 AI working with humans GPT-5.4 Pro Om_Buddhdev_sensho 🟡 Partial result
29 Apr, 2026 AI working with humans GPT-5.5 Pro Jonas Silva ⚪ Candidate partial result

Caveats

The wiki's classifications are provisional and are not a benchmark. Many Erdős problems have never had a thorough literature review, so a result that looks new may later turn out to be known; some problems were also stated ambiguously or incorrectly. See the problem page for the full discussion.

∎