FOM: 119:Discrepancy Theory/3

[Harvey Friedman]

I have been using too strong a notion of largeness in postings in #117 and
#118. I have been using

1. Arbitrarily long runs in subsets of N.
2. Positive upper density in subsets of N.
3. Upper density 1 in subsets of N.

These have a much stronger flavor than the old standby of Boolean relation
theory: bi-infinite subsets of Z.

The appropriate notion of largeness for discrepancy theory seems to be:

*containing infinitly many 16 point intervals*

where subsequent investigation will reveal how much 16 can be lowered.
Certainly 16 can be raised to any specific positive integer. (An interval
in N is just a set of consecutive elements of N).

The first Proposition is in the style of posting #118, correcting earlier
versions.

PROPOSITION A. Let f,g,h be multivariate functions from N into N that are
expansively trapped (expansive linear growth, quadratic growth, etcetera).
There exist A containedin B containedin C containedin N containing
infinitely many 16 point intervals, such that the 9 element discrepancy
poset contains a copy of the inverted tree
     *
  / | \
*  *  *
  / | \
*  *  *

Things simplify nicely if we involve the Boolean combinations of the 3 sets
as follows. Note the symmetry.

PROPOSITION B. Let f,g,h be multivariate functions from N into N that are
expansively trapped (expansive linear growth, quadratic growth, etcetera).
There exist nonempty A,B,C containedin N whose nonempty Boolean
combinations each contain infinitely many 16 point intervals, such that the
9 element discrepancy poset contains a copy of the inverted tree
     *
  / | \
*  *  *
  / | \
*  *  *

Here is a more general statement. Note the symmetry.

PROPOSITIOIN C. Let n,m,r >= 1 and f1,...,fn be multivariate functions from
N into N that are expansively trapped (expansive linear growth, quadratic
growth, etcetera). There exist A1,...,Am containedin N whose nonempty
Boolean combinations each contain infinitely many r point intervals, such
that the nm element discrepancy poset contains a copy of the inverted tree
with exactly m levels, where in each of the upper m-1 levels, one vertex
sits above exactly n immediate predecessors, and the remaining vertices are
minimal.

THEOREM. Propositions A,B,C are provably equivalent to the 1-consistency of
ZFC + {there exists an n-Mahlo cardinal}_n over ACA.

We can get away without saying that the A's are nonempty here but not in
Proposition B.

Note that the inverted tree in Proposition C for n = m = 3 is the same as
the one diagrammed in Propositions A,B.

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

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
118:Discrepancy Theory/2   1/20/02  1:31PM