Erdős Problem a Daythe open tracker
ERDŐS #531 · READER SUBMISSION

A verified partial result (a case, a bound, an exact value)

VERIFIED2026-10-22 · Atakan Akbaba
Community database OPENas of 2025-08-31tags number theory, ramsey theoryproblem page · erdosproblems.com/531
Our review · 2026-10-22

Verdict: VERIFIED — as a certificate: the colouring of {1,…,396} in w396.txt has no 4-set A = {a<b<c<d} with a+b+c+d ≤ 396 whose 15 nonempty subset sums are one colour, so F(4) ≥ 397. That is nearly double the F(4) ≥ 201 in our own July report, which now carries a dated note pointing here.

Convention. The sums must lie in {1,…,N}, i.e. sum(A) ≤ N, and A is a set (distinct elements). This is how Erdős and Spencer define F(k) (Monochromatic sumsets, JCTA 50, 1989: "Let F(k) denote the least n so that if [n] (={1,…,n}) is two colored there is a k-set S with P(S)⊂[n] and P(S) monochromatic", P(S) being the sums of distinct elements of S) and how BENTW (arXiv:1703.02473) and our July report read it. A proper colouring of {1,…,396} shows the least forcing N exceeds 396, i.e. F(4) ≥ 397.

What we checked (our code, written without reading the submitter's; none of theirs was run):

  • fs4_direct.c enumerates every eligible a<b<c<d and tests all 15 sums: 40,781,268 eligible sets (the submission's count; an independent partition-count DP gives the same number), 0 monochromatic.
  • fs_extend.py, a different algorithm, grows monochromatic sets instead (A extends by d only if d and every s+d, s a subset sum of A, stay in A's colour): 396 / 9,503 / 22,488 monochromatic 1-, 2-, 3-sets, no 4-set.
  • Controls: the all-zero colouring gives all 40,781,268. On 12 random colourings and on all 396 single-bit flips of the witness the two checkers report identical monochromatic counts (zero disagreements). 372 of the 396 flips break the colouring; 24 positions can be flipped alone. Neither colour extends it to 397 (colour 0 makes 35 monochromatic sets, e.g. {8,15,163,211}; colour 1 makes 140, e.g. {1,6,37,353}). The same grower reproduces F(2) = 9 exhaustively and accepts our July 53-colouring for k = 3.
  • Every witness in the repository (w331, w372–w396) checks clean.

A file-format note: w396.txt is 395 characters, a newline, then the 396th (1) — it is w395.txt with one colour appended. Checkers that skip newlines (theirs, ours) read N = 396; one that reads only the first line gets 395.

Hostile referee. A separately briefed seat, told to refute and kept away from our checkers, returned HOLDS WITH CAVEATS. Its own bitmask checker and a numpy brute force both give 0 monochromatic sets on the witness (and all 40,781,268 on all-zero and all-one); it quoted the convention above from the rendered Erdős–Spencer page; and the only reading under which the witness fails is to allow repeated elements (e.g. 1, 6, 6, 37), which both sources exclude. Its caveats are about the repository, not the bound. Besides the file format, the README says every witness w200–w396 (149 files) was re-checked with verify/f4_check.c, every file reporting mono_cubes=0. validation.log does not show that: it has 146 OK lines, they are in a different checker's output format, and most predate commit 31cde83 (18 October), which changed int lo=0, hi=1; to hi=0. Before that fix f4_check could only flag sets monochromatic in colour 0. We confirmed all three points. w396 itself is verified directly above.

Novelty. We found no value of F(4) in the literature (Erdős–Spencer 1989, Taylor 1981, BENTW 2017, Balogh–Lavrov–Shakan–Wagner 2019), in OEIS, or on erdosproblems.com/531 (no comments or proof claims as of 22 October 2026). As far as we know this is the best lower bound on record. The same bound is proposed for the community database in teorth/erdosproblems PR #490.

Scope. A lower bound only: nothing here bounds F(4) from above, and the asymptotic question of #531 (BENTW's 2^(2^(k−1)/k) below, Taylor's tower above) is untouched. Files: verification/531/reader-f4-397 in our repository (private at the time of writing; files available on request).

Tools, as declared by the submitter: DeepSeek (DeepSeek-V4 family, driving an autonomous search agent) wrote and tuned the local-search code and produced the witness chain. Claude (Anthropic, Claude Code / Claude Sonnet-Opus family, Oct 2026) wrote the independent verifiers (verify/check.c, verify/check.py, verify/f4_check.c), re-checked all 149 witnesses w200-w396 and maintains the repository. The models' own claims were never used

The submission

F(4) >= 397 (explicit witness, independently checkable)

Statement worked on: F(k) = least N such that every 2-colouring of {1,...,N} contains a k-element set A whose nonempty subset sums are all the same colour (Erdős #531, Folkman). Convention: A counts only when sum(A) <= N (the colouring is defined on {1,...,N} only) and the elements of A are distinct.

What was known: your working report gives an explicit checked colouring for F(4) >= 201. We found no value of F(4) on erdosproblems.com, in the OEIS, or in the published literature; corrections welcome.

Result (label: lower bound): a 2-colouring of {1,...,396} with no set A = {a<b<c<d}, a+b+c+d <= 396, whose 15 nonempty subset sums are monochromatic. Hence F(4) >= 397.

How to check it: witnesses/w396.txt (SHA-256 a0ca6789beb0fb831a914ad03a817d5b6e74d4a56a16d2788addba536a673c3d). cc -O2 -o check verify/check.c && ./check witnesses/w396.txt prints N=396 tested=40781268 mono=0 in about a second; a dependency-free Python checker (verify/check.py) and a separately written brute-force verifier (verify/f4_check.c, mono_cubes=0) agree. Sanity of the convention: the same encoding reproduces F(2) = 9 and F(3) = 54 (N = 53 satisfiable with a checked model, N = 54 unsatisfiable with a DRAT proof verified by drat-trim).

Method: computer search extending the witness one value at a time. From N-1 to N the only new sets are those with a+b+c+d = N, whose other 14 subset sums are already coloured; when both colours are forbidden for N (a wall), earlier values are recoloured. Up to N = 380 min-conflicts/tabu local search; from N = 381 Configuration Checking with aspiration; at some walls (from N = 387) the search was seeded by recolouring a value common to every conflicting set and repairing locally.

This is a lower bound only and says nothing about the exact value of F(4). What is ours: the witness chain w200-w396, the search code and the checkers. What is not: the problem, the convention check against your F(3) = 54 report.

Reviewed by Claude with Patrick White — an AI and a regular dude, not mathematicians. The verdict says what was checked; it is not community acceptance. ← problem page