A weak variant of Hindman's Theorem stronger than Hilbert's Theorem

2016/10/18 by Lorenzo Carlucci, Carlucci, Lorenzo · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.1610.05445

openalex publication_date 2016/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Hirst investigated a slight variant of Hindman's Finite Sums Theorem -- called Hilbert's Theorem -- and proved it equivalent over \RCA₀ to the Infinite Pigeonhole Principle for all colors. This gave the first example of a natural restriction of Hindman's Theorem provably much weaker than Hindman's Theorem itself. We here introduce another natural variant of Hindman's Theorem -- which we name the Adjacent Hindman's Theorem -- and prove it to be provable from Ramsey's Theorem for pairs and strictly stronger than Hirst's Hilbert's Theorem. The lower bound is obtained by a direct combinatorial implication from the Adjacent Hindman's Theorem to the Increasing Polarized Ramsey's Theorem for pairs introduced by Dzhafarov and Hirst. In the Adjacent Hindman's Theorem homogeneity is required only for finite sums of adjacent elements.

Cited by

• Finitely additive measures on \mathbb Z and additive combinatorics

Related

• The adjacent Hindman's theorem and the \mathbb Z-Ramsey's theorem
• New bounds on the strength of some restrictions of Hindman's Theorem
• The reverse mathematics of Hindman's theorem for sums of exactly two elements
• Adjacent Ramsey theory and Higman's lemma
• "Weak yet strong" restrictions of Hindman's Finite Sums Theorem