FOM: 134:BRT/summation/polynomials
Harvey Friedman
friedman at math.ohio-state.edu
Tue Mar 26 19:26:07 EST 2002
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?
More information about the FOM
mailing list