FOM: 117:Discrepancy Theory

[Harvey Friedman]

Discrepancy Theory is an offshoot of Boolean Relation Theory. Both theories
apply in very general contexts and have simple instances which correspond
to large cardinals (equivalence with the 1-consistency of Mahlo cardinals
of finite order). Both theories very likely have the property that all of
the finitely many statements involving a few functions and a few sets can
be solved with large cardinals but not in ZFC.

The nicest particular instances of Boolean Relation Theory that are
independent of ZFC are striking in that they are very simple. However, one
would like them to be not only simple but also more thematic. I.e., they
convey a mathematical message. E.g., that there are lots of things such
that blah blah blah, or the things such that blah blah blah are rich or
barren, etcetera.

Discrepancy Theory purports to be not only simple but also thematic.

Discrepancy Theory concerns the "discrepancy" of functions on sets.
Specifically, let k >= 1, f:N^k into N, and A containedin N, where N is the
set of all nonnegative integers. Recall that in Boolean Relation Theory, we
write fA for the set of all values of f at arguments from A.

The discrepancy of f on A is A delta fA, where delta indicates symmetric
difference. This indicates the extent to which f transforms A.

Let f_1,...,f_n be multivariate functions from N into N and A_1,...,A_m be
subsets of N. In this context, the discrepancy sets are the nm sets

f_i delta A_j.

We treat these sets as distinct, thereby counting multiplicities.

In Discrepancy Theory, we are interested in the inclusion relations between
the discrepancy sets.

As in Boolean Relation Theory, we say that f is expansively trapped (on N)
if and only if

i) for some k >= 1, f:N^k into N;
ii) there exists p,q >1 such that for all x in N^k, p|x| <= f(x) <= q|x|.

We say that A containedin N has arbitrarily long finite consecutive runs if
and only if for all n >= 1 there exists m such that m,m+1,...,m+n all lie
in A.

THEOREM 1. Let f,g,h be expansively trapped. There exists A containedin B
containedin C containedin N, each with arbitrarily long finite consecutive
runs,
such that some discrepancy set properly contains at least 6 discrepancy sets.

The 6 is best possible out of the 9 discrepancy sets. Note that we must
count multiplicities, for otherwise 3 would be best possible. To see this,
note that if f = g = h then there are at most 3 unequal discrepancy sets.

PROPOSITION 2. Let f,g,h be expansively trapped. There exists A containedin
B containedin C containedin N with arbitrarily long finite consecutive runs
such that some discrepancy set properly contains at least 6 discrepancy
sets, at least one of which properly contains at least 3 discrepancy sets.

The 6,3 are best possible.

Let MAH = ZFC + {there exists an n-Mahlo cardinal}_n.

THEOREM 3. Proposition 2 is provably equivalent to MAH over ACA_0.

The theme is that there are always discrepancy sets with lots of other
discrepancy sets properly included in it.

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

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

This is the 117th 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