FOM: 118:Discrepancy Theory/2

[Harvey Friedman]

We begin by correcting a bad typo in posting #117:Discrepancy Theory, 1/6/02.

There I wrote

f_i delta A_j.

This should have been

f_iA_j delta A_j.

Sorry for the confusion.

#######################

This posting is a restatement of the kind of results announced in posting
#117, but in a form that I like better.

Firstly, note that thoughout Boolean relation theory we use a notion of
largness. Most commonly, lately, it has been bi-infinite set of integers;
i.e., infinite in both directions.

There are many alternative notions of largeness that can be used. In fact,
as a side topic, there is a lot that can be said about what notions of
largeness create statements corresponding to Mahlo cardinals of finite
order.

But let me mention a notion of largeness that is very familiar from
combinatorics (Szemeredi's theorem):

*A containedin N is of positive upper density.*

The upper density of A contained in N is the lim sup of the densities
within initial segments of N. (Here N is the set of all nonnegative
integers).

Throughout Boolean relation theory we can use subsets of N and positive
upper density. Furthermore, if we use above linear growth conditions on the
given multivariate functions, then we can also use "upper density 1".

We will use upper density 1 for this new version of discrepancy
theory in this posting.

Suppose we are given multivariate functions f1,...,fn from N into N and
subsets A1,...,Am of N. We form the nm discrepancy sets

fiAj delta Aj.

There may be duplications, but we always count multiplicities, so that
there are exactly nm discrepancy sets.

We now take a step that we didn't take in posting #117. We form what we
call the discrepancy poset, which is a strict partial ordering whose
vertices are the nm discrepancy sets and where < is proper inclusion. I.e.,
V < W if and only if V is a proper subset of W.

We study the structure of this dag. Given appropriate f,g,h, we want to
find appropriate A,B,C such that the discrepancy poset is rich.

We say that one strict poset <1 contains a copy of another strict poset <2
if and only if there is a one-one function h from the vertices of <2 into
the vertices of <1 such that

x <2 y implies h(x) <1 h(y).

Recall the notion of expansively trapped. We can also use expansive linear
growth.

PROPOSITION 1.   Let f,g,h be multivariate functions from N into N that are
of quadratic growth. There exist 3 sets A containedin B containedin C
containedin N of upper density 1 such that the 9 vertex discrepancy poset
contains a copy of the inverted tree
     *
  / | \
*  *  *
  / | \
*  *  *

This is provably equivalent to the 1-consistency of ZFC + {there exists an
n-Maho cardinal}_n over ACA.

Of course, we can use "for all n, there are n consecutive elements" instead
of "upper density 1" as in posting #117.

**********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.

This is the 118th in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:

100:Boolean Relation Theory IV corrected  3/21/01  11:29AM
101:Turing Degrees/1  4/2/01  3:32AM
102: Turing Degrees/2  4/8/01  5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01  11:10AM
104:Turing Degrees/3   4/12/01  3:19PM
105:Turing Degrees/4   4/26/01  7:44PM
106.Degenerative Cloning  5/4/01  10:57AM
107:Automated Proof Checking  5/25/01  4:32AM
108:Finite Boolean Relation Theory   9/18/01  12:20PM
109:Natural Nonrecursive Sets  9/26/01  4:41PM
110:Communicating Minds I  12/19/01  1:27PM
111:Communicating Minds II  12/22/01  8:28AM
112:Communicating MInds III   12/23/01  8:11PM
113:Coloring Integers  12/31/01  12:42PM
114:Borel Functions on HC  1/1/02  1:38PM
115:Aspects of Coloring Integers  1/3/02  10:02PM
116:Communicating Minds IV  1/4/02  2:02AM
117:Discrepancy Theory   1/6/02  12:53AM