[FOM] response to Harvey's posting on the reverse mathematics of Hindman's Theorem

[Henry Towsner]

On Tue, Sep 1, 2015 at 1:51 AM, Harvey Friedman <hmflogic at gmail.com> wrote:

> Doesn't Towsner adapt the ultrafilter proof more or less in tact more
> or less lower than even Pi11-CA0? What do you think about the
> possibility of preserving the ultrafilter proof more or less in tact
> working in ACA_0+?
>

The basic status of ultrafilters in reverse math, as I know it, goes as
follows.  It turns out that it depends heavily on *how* the ultrafilters
are used.  The first question you could ask is to simply have a
nonprincipal ultrafilter; this implies ACA0 over RCA0 (basically because a
nonprincipal ultrafilter can be easily used to prove Ramsey's Theorem), but
is conservative over ACA0 (this follows from a result in Enayat, "From
bounded arithmetic to second order arithmetic via automorphisms", and is
proven separately by Kreuzer, "Non-principal ultrafilters, program
extraction and higher-order reverse mathematics", and me "Ultrafilters in
reverse mathematics").



The ultrafilter proof of Hindman's theorem and its relatives requires the
structure of the ultrafilters as a topological semigroup.  After the work
by Hirst and me that Harvey mentions, that can be done somewhere below
Pi11-CA0 (specifically, Sigma11-TI0).  That method seems likely to work on
other proofs which need an idempotent ultrafilter.  In particular, there is
an extension of Hindman's theorem which follows basically for free from the
ultrafilter proof.

Consider a collection P of sets which is upwards closed, non-trivial (i.e.
contains some set, but not the empty set), partition regular (any finite
coloring of a set in P has a monochromatic set in P), and shift invariant.
 (The first three properties mean P is "divisible"; being divisible is the
dual property to being a filter---the collection of sets intersecting every
set in P is a shift invariant filter.)  (For explicitness, consider the
collection of sets such that the sum of their reciprocals is infinite.)
 Then, given any finite coloring of the natural numbers, there is a color
so that there are many (i.e. a set belonging to P) elements a_1, for each
a_1 there are many a_2, for each (a_1,a_2) there are many a_3, and so on,
so that every branch through this tree satisfies the conclusion of
Hindman's theorem.  To get this from the ultrafilter proof, one simply
adapts the proof to work with ultrafilters where every set belongs to P.

The reverse mathematical strength of this hasn't been considered directly,
but (at least for reasonable properties P), it seems likely that it goes
through in Sigma11-TI0 using the same techniques as Hindman's theorem.
 (Whether it can be pulled down to ACA0+ is open question---the only proofs
of this version are the ultrafilter proof and a proof based on
Baumgartner's proof.  A proof that it can't would be quite interesting,
possibly to combinatorists as well, if it demonstrated a real difference
that isn't being detected by the more powerful proofs.)

Another theorem in the same general category is the Milliken-Taylor
theorem, which is a sort of combination of Hindman's theorem and Ramsey's
theorem.  Like Ramsey's theorem, it stratifies into versions for each n.
Hirst ("Hindman's Theorem, Ultrafilters, and Reverse Mathematics" shows
that, for any fixed n>=3, Milliken-Taylor for n is equivalent to the
iterated Hindman's theorem.  The ultrafilter proof of the iterated
Hindman's theorem also goes through in Sigma11-TI0, so full Milliken-Taylor
goes through in, at worst, Pi12-TI0.  I don't think any lower bound (other
than those for Hindman's theorem) is known even for Milliken-Taylor.



A further class of results, largely unexamined in the reverse math
literature, are those which use even more of the topology of the
ultrafilters.  Most of these involve the minimal ideal---one can show that
there is a minimal two-sided ideal in the space of ultrafilters, and
specifically choose an idempotent ultrafilter from within this ideal.  The
elements of such an ultrafilter are called "central sets" (I believe they
were originally defined by Furstenberg with a definition based on their
dynamical properties).  There are combinatorial characterizations, but
they're fairly complicated.  (See Hindman and Strauss, "A simple
characterization of sets satisfying the Central Sets Theorem".)  The are
various results in this area one could investigate (most straightforwardly,
proving that any finite coloring of the natural numbers has a monochromatic
set satisfying the conclusion of the "central sets theorem", which is not
known to be as strong as containing an actual central set; if I remember
correctly, Hindman says in print somewhere that he does not expect his
grandchildren to live to see a combinatorial proof of this result).

Somewhere between these two discussions is a recent result McCutcheon and
Zhou; they have a notion related to both central sets and the Hindman trees
("D sets").  They prove that every finite coloring contains a monochromatic
tree with a stronger property than the tree I mentioned above; there is no
known combinatorial proof.  The ultrafilter argument involves selecting an
idempotent belonging to a particular ideal.  Again, it's not clear if the
methods which work for idempotents extend to idempotents with extra
structure.



Harvey mentioned a number of particular modifications of Hindman's theorem;
I'm only sure about the status of the first two:

> There are a number of weakenings and strenghenings of Hindman's
> theorem, I think some of them have names like Milliken attached to
> them, and I was wondering what the current RM status of them are as
> well. Could you help us with this? What is the state of the art?
>
> 1. Every finite coloring of N has an infinite S whose <= n sums have
> the same color. Here n is a variable.
> 2. Every finite coloring of N has an infinite S whose <= n sums have
> the same color. Here n is a standard integer (scheme).
>

It's an open question, discussed in the combinatorial literature, whether
one can prove that every finite coloring of N has an infinite S whose <=2
sums have the same color without just proving Hindman's theorem.  There are
a couple conjectures or questions in the literature which are attempts to
make this precise, all of which are open.  I think a reverse math proof
separating this problem from Hindman's theorem would be considered
interesting on the combinatorial side.  On the other hand, I think it would
be quite hard, because it would require solving the underlying soft
question.

Best,
Henry

-- 
Henry Towsner
Assistant Professor
Department of Mathematics
University of Pennsylvania
http://www.math.upenn.edu/~htowsner
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150918/9506d8b6/attachment.html>