The reverse mathematics of Hindman’s Theorem for sums of exactly two elements
Bibliographic record
Abstract
Hindman’s Theorem (HT) states that for every coloring of N with finitely many colors, there is an infinite set H⊆N such that all nonempty sums of distinct elements of H have the same color. The investigation of restricted versions of HT from the computability-theoretic and reverse-mathematical pers pectives has been a productive line of research recently. In particular, HTk⩽n is the restriction of HT to sums of at most n many elements, with at most k colors allowed, and HTk=n is the restriction of HT to sums of exactly n many elements and k colors. Even HT2⩽2 appears to be a strong principle, and may even imply HT itself over RCA0. In contrast, HT2=2 is known to be strictly weaker than HT over RCA0, since HT2=2 follows immediately from Ramsey’s Theorem for 2-colorings of pairs. In fact, it was open for several years whether HT2=2 is computably true. We show that HT2=2 and similar results with addition replaced by subtraction and other operations are not provable in RCA0, or even WKL0. In fact, we show that there is a computable instance of HT2=2 such that all solutions can compute a function that is diagonally noncomputable relative to ∅′. It follows that there is a computable instance of HT2=2 with no Σ20 solution, which is the best possible result with respect to the arithmetical hierarchy. Furthermore, a careful analysis of the proof of the result above about solutions DNC relative to ∅′ shows that HT2=2 implies RRT22, the Rainbow Ramsey Theorem for colorings of pairs for which there are most two pairs with each color, over RCA0. The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lovász Local Lemma due to Rumyantsev and Shen.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.003 | 0.010 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.003 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.003 | 0.007 |
| Scholarly communication | 0.004 | 0.015 |
| Open science | 0.002 | 0.005 |
| Research integrity | 0.001 | 0.007 |
| Insufficient payload (model declined to judge) | 0.008 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".