Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let and and continue the sequence by appending to all possible values of with . Is it true that the set of integers which eventually appear has positive density?
Let and and continue the sequence by appending to all possible values of with . Is it true that the set of integers which eventually appear has positive lower density?
Source: erdosproblems.com/424
An accepted solution exists. The statement is true.
The site labels the problem OPEN (page last edited 31 March 2026;
proof-claims thread accessed 2026-10-06). A proof claim by Samuel Korsky, posted
as a full claim to the site's proof-claims tab on 20 July 2026 after a partial
claim of 18 July 2026 for a variant, claims a proof of positive lower density,
which is the precise Statement. It was
written with GPT 5.6-Pro, is on arXiv (August 2026), and was formalized in Lean
4 by Codex, with Boris Alexeev as formal co-author (the file in
plby/lean-proofs, built and audited here on 2026-10-07). The
formal-conjectures statement of the lower-density reading is tagged solved. The
site has not accepted the claim: its proof-claims tab says that a claim's
appearing there does not mean that anyone associated with the site has examined
any part of the proof, and the site's curator commented in the thread only on
the write-up's style. No refereed version exists. The claim page
Korsky's proof
records it as an accepted full claim on formalized evidence, so the precise
Statement is proved and the problem's derived standing is settled. That standing
departs from the site's label OPEN, which predates the claims; the acceptance
rests on the kernel-checked formalization, not on the site.
The site's wording does not say which density it asks for: "positive
density" can ask that the set of integers that appear have an asymptotic
density and that it be positive, or only that its lower density be positive,
and the two readings differ for a set whose density need not exist. The change
replaces "positive density" by "positive lower density"; nothing else changes.
Erdős printed the question without a qualifier: [Er77c], p. 71 (library card:
Erdos 1977),
reports Hofstadter's problem and asks "Does this sequence have positive
density?", while the preceding page (p. 70) asks of another sequence whether its
"density (lower density)" is and expects different answers for the two, so
Erdős's text distinguishes the densities where Erdős wanted to and fixes no
reading here. Erdős and Graham's 1980 wording ([ErGr80], p. 84, as the site
reports it) and Guy's section E31 ask instead whether almost all integers
appear; that is false, since the residues and modulo are closed
under (an observation the site credits to Steinerberger),
and the site treats that wording as a misstatement of the [Er77c] question. The
reading is the site's curator's. The site's commentary says: "As with many of
Erdős' questions, by 'positive density' he most likely meant 'positive lower
density' - in other words, does there exist such that for all large
the number of values of in is at least ?" The evidence Thomas
Bloom gives is Erdős's general usage; in the thread of Problem 1201 (1 May
2026) Bloom wrote that reading a density bound as a lower-density bound "is
generally how Erdős used these terms", that Erdős was "generally clear" when
asking whether a density exists, and that the curator had tried to update all
the site's problem descriptions to reflect this. The formal-conjectures
statement follows the site: its erdos_424 asks for positive lower density and
its variant exact_density for a positive natural density. Under the precise
Statement the answer is yes: Samuel Korsky's proof, recorded on
its claim page (Korsky, 2026),
gives a with at least members in for all large , and the
Lean formalization of that statement by Codex and Boris Alexeev was built and
audited in this corpus. Under the natural-density reading the question is open:
no source shows that the density exists, and formal-conjectures tags
exact_density as open.