Status
On this page
Status
Topics
Status
On this page
Status
Topics
If is a multiset of integers such that
for all then must be subcomplete? That is, must
contain an infinite arithmetic progression?
Is there a constant such that if is a multiset of integers such that
for all sufficiently large then must be subcomplete? That is, such that
must contain an infinite arithmetic progression?
Source: erdosproblems.com/343
An accepted solution exists. The statement is true.
The site labels the problem PROVED (LEAN) (page last edited 2025-12-02), and the community database has listed it as proved (Lean) since its commit of 2026-09-26; the label describes the corrected Statement. Szemerédi and Vu [SzVu06] answered it in the affirmative, after Folkman [Fo66] had proved the case of counting function and shown that does not suffice. The accepted full claim is Szemerédi and Vu 2005, and the accepted partial claim is Folkman 1966. The "(LEAN)" qualification rests on Collin Yuanjie Ren's file, described under Formalization, which this corpus has not built.
The site's wording leaves the implied constant in
unquantified, and the question changes with it. The site's source, Erdős and
Graham's monograph [ErGr80], p. 54, asks Folkman's question for a
nondecreasing sequence with "for some and all ", and Folkman's
own closing question ([Fo66], p. 655) is whether for all
forces subcompleteness; in both the constant may depend on the sequence. The
site labels the problem PROVED and its commentary says that "the original
question was answered by Szemerédi and Vu [SzVu06] (who proved that the answer
is yes)"; its thread has no comments. The curator's reading is therefore the
statement Szemerédi and Vu prove, which they state as Folkman's conjecture
(Conjecture 6.1, proved as Theorem 6.3): there is a constant such that
every infinite nondecreasing sequence of positive integers with
for all sufficiently large is subcomplete, where counts the terms
at most with multiplicity. The corrected Statement is that form: it asks
for the constant before and replaces " for all " by "
for all sufficiently large ". The two changes go together. With one
constant required for every the question is trivial: gives
for every , so and , and Brown's criterion
then makes every natural number a finite subset sum. The answer under each
reading: the corrected Statement is proved by Theorem 6.3, whose constant is
one absolute constant that the proof takes large (it needs
and a lemma that holds for sufficiently large); the question as Folkman
and Erdős and Graham printed it, with a constant depending on , is answered
yes only for multisets with at least terms up to for all large ,
that is for in Folkman's form, and is open for smaller constants as
far as the cited sources show; the universal-constant form for every is
trivially true. Boris Alexeev's lean-proofs file Erdos343.lean (pinned
commit of 2026-08-17; formal authors the AI systems Codex and GPT-5.6 Sol)
proves that trivial form with by Brown's criterion and says so; it is
credited here and counts for nothing. Collin Yuanjie Ren's submission
jsp-000285-cyr (pinned commit of 2026-09-16), which the community database
credits for the site's "(LEAN)" qualification, states the corrected Statement
as erdos_343_eventual with the explicit constant ,
; this corpus has not built it, so it gives no
formalized evidence. Unread: Section 6 of [ErGr80] beyond p. 54.