FOM: 133:BRT/polynomials/affine maps

[Harvey Friedman]

We have found a new strategy for all statements involving integral
polynomials and integral affine transformations. We use only one absolutely
arbitrary multidimensional integral polynomial and only one
multidimensional affine transformation. In the disjoint union inclusions,
we use a standard forward image of f on the left side, and the forward
image of an "upper restriction" of f on the right side.

We give a self contained treatment of these new statements, starting with
the infinitary versions.

*INFINITARY STATEMENTS*

A multidimensional integral function is a function of the form f:Z^k into Z^p.

The upper restriction of a multidimensional integral function f is the
restriction f* of f to {x in Z^k: f(x) in N^p and min(f(x)) > 2max(x)}.

Let f be any restriction of a multidimensional integral function, and A
containedin Z. The image of f on A, written fA, is the set of all
coordinates of values of f at arguments from A.

PROPOSITION 1. For all multidimensional integral polynomials P, there exist
infinite A,B,C containedin Z such that
A U. PA containedin C U.P*B
A U. PB containedin C U. P*C.

We now consider multidimensional integral affine transformations.

The magnitude increasing upper restriction of a multidimensional integral
function f is the restriction f# of f to {x: f(x) in N^p and min(f(x)) >
2max(x) and the coordinates of x are strictly increasing in magnitude}.

PROPOSITION 2. For all multidimensional integral affine transformations T,
there exist infinite A,B,C containedin Z such that
A U. TA containedin C U. T#B
A U. TB containedin C U. T#C.

*FINITARY STATEMENTS*

PROPOSITION 3. For all multidimensional integral polynomials P and
sufficiently large n,r, there exist A,B,C containedin Z such that
A U. PA containedin C U.P*B
A U. PB containedin C U. P*C
log(n,A) = log(n,B) = log(n,C) = {0,...,r}.

PROPOSITION 4. For all k,p,n,r >= 8 and affine transformations T:Z^k into
Z^p with coefficients from [-n,n], there exist A,B,C containedin Z such
that
A U. TA containedin C U. T#B
A U. TB containedin C U. T#C
log(k+p+n,A) = log(k+p+n,B) = log(k+p+n,C) = {0,...,r}.

*RESULTS*

THEOREM. Propositions 1,3 are provably equivalent to the 1-consistency of
MAH over ACA. Propositions 2.4 are provably equivalent to the consistency
of MAH over ACA.

Propositions 2 and 4 get around those special difficulties that we
discussed in posting 129 related to hedged claims.

*NEW TEMPLATE*

Obviously we have the following new template:

TEMPLATE. For all f in V there exists infinite A,B,C containedin Z such that
A U. fA containedin C U. f'B
A U. fB containedin C U. f'C.

Here V is a class of multidimensional functions on Z and f' is some kind of
restriction of f. The idea is to study natural V and natural restriction
operators. In fact, there appears to be a general theory of this. E.g.,
note that in the above, we use a "semilinear" restriction operator on the
class of integral polynomials and on the class of integral affine
trasnformations. We have sought to find the simplest ones where we get
independence from ZFC. We can hope to classify all "semilinear" restriction
operators according to whether the statements hold; and in fact, we can
also introduce as a parameter, the particular pair of disjoint union
inclusions used.

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

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

This is the 132nd 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
119:Discrepancy Theory/3  1/22.02  5:27PM
120:Discrepancy Theory/4  1/26/02  1:33PM
121:Discrepancy Theory/4-revised  1/31/02  11:34AM
122:Communicating Minds IV-revised  1/31/02  2:48PM
123:Divisibility  2/2/02  10:57PM
124:Disjoint Unions  2/18/02  7:51AM
125:Disjoint Unions/First Classifications  3/1/02  6:19AM
126:Correction  3/9/02  2:10AM
127:Combinatorial conditions/BRT  3/11/02  3:34AM
128:Finite BRT/Collapsing Triples  3/11/02  3:34AM
129:Finite BRT/Improvements  3/20/02  12:48AM
130:Finite BRT/More  3/21/02  4:32AM
131:Finite BRT/More/Correction  3/21/02  5:39PM
132: 132:Finite BRT/cleaner