FOM: 134:BRT/summation/polynomials

[Harvey Friedman]

The notion of "magnitude increasing upper restriction" in connection with
the linear form of BRT in posting #134 is not beautiful enough. Actually,
(almost) nothing is "beautiful enough".

For this reason, we have been looking for a nicer way to do "linear BRT".

We have chosen to use alternating summation. Instead of a an affine
function with a cumbersome notion of upper restriction, we use a semilinear
set with a simple notion of "upper alternating summation".

We also revisit the case of polynomials, and use a somewhat more natural
notion of upper restriction.

SUMMATION STATEMENTS

Let k >= 1 and x in Z^k. Define Sigma(x) as the sum of the coordinates of x.

Define Sigma*(x) as the sum of the greatest [k/2] coordinates of x.

Let V containedin N^k. Define Sigma(V) = {Sigma(x): x in V}. Define
Sigma*(V) = {Sigma*(x): x in V}.

PROPOSITION 1. For all k >= 3 and integral semilinear E containedin Z^k,
there exist infinite A,B,C containedin Z+ containing 1 such that
A U. Sigma(A^k) containedin C U. Sigma*(B^k intersect E)
A U. Sigma(B^k) containedin C U. Sigma*(C^k intersect E).

One might prefer to use only one notion of sum:

PROPOSITION 2. For all k >= 3 and integral semilinear E containedin Z^k,
there exist infinite A,B,C containedin Z+ containing 1 such that
A U. Sigma*(A^k) containedin C U. Sigma*(B^k intersect E)
A U. Sigma*(B^k) containedin C U. Sigma*(C^k intersect E).

We now come to finite forms.

PROPOSITION 3. Let k,n,r >= 8 and E containedin Z^k be semlinear with
coefficients from {-n,...,n}. There exist A,B,C containedin Z+ containing 1
such that
A U. Sigma(A^k) containedin C U. Sigma*(B^k intersect E)
A U. Sigma(B^k) containedin C U. Sigma*(C^k intersect E)
log(k+n,A) = log(k+n,B) = log(k+n,C) = {0,...,r}.

PROPOSITION 4. Let k,n,r >= 8 and E containedin Z^k be semlinear with
coefficients from {-n,...,n}. There exist A,B,C containedin Z+ containing 1
such that
A U. Sigma*(A^k) containedin C U. Sigma*(B^k intersect E)
A U. Sigma*(B^k) containedin C U. Sigma*(C^k intersect E)
log(k+n,A) = log(k+n,B) = log(k+n,C) = {0,...,r}.

We can remove the parameter n as follows. We say "semilinear without
coefficients" in case all coefficients on variables are among -1,0,1.

PROPOSITION 5. Let k,r >= 8 and E containedin Z^k be semlinear without
coefficients. There exist A,B,C containedin Z+ containing 1 such that
A U. Sigma(A^k) containedin C U. Sigma*(B^k intersect E)
A U. Sigma(B^k) containedin C U. Sigma*(C^k intersect E)
log(k,A) = log(k,B) = log(k,C) = {0,...,r}.

PROPOSITION 6. Let k,r >= 8 and E containedin Z^k be semlinear without
coefficients. There exist A,B,C containedin Z+ containing 1 such that
A U. Sigma*(A^k) containedin C U. Sigma*(B^k intersect E)
A U. Sigma*(B^k) containedin C U. Sigma*(C^k intersect E)
log(k,A) = log(k,B) = log(k,C) = {0,...,r}.

POLYNOMIAL STATEMENTS

We use a cleaner notion of upper restriction.

Let f:Z^k into Z^p. The upper restriction f* is f restricted to {x in Z^k:
min(f*(x)) > 2|x|}.

PROPOSITION 7. 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.

PROPOSITION 8. 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}.

RESULTS

THEOREM. Propositions 1-6 are provably equivalent to the consistency
of MAH over ACA. Propositions 7,8 are provably equivalent to the
1-consistency of
MAH over ACA.

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

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

This is the 134th 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: Finite BRT/cleaner  3/25/02  12:08AM
133:BRT/polynomials/affine maps  3/25/02  12:08AM


what about adding just the biggest terms? put in 1 as usual. everything
positive. then just intersect with semilinear set?