[FOM] 377: The Polynomial Shift Theorem

[Harvey Friedman]

This abstract is at the level of PA. The new development is that it  
only involves polynomials with integer coefficients.

I will restate below some shift theorems from http://www.cs.nyu.edu/pipermail/fom/2008-January/012582.html

These were used to get independence results involving polynomials with  
integer coefficients, in http://www.cs.nyu.edu/pipermail/fom/2008-January/012611.html

However, the new way I do this now is more natural and convincing.

One of the many forms of my combinatorial shift theorem goes like this.

THEOREM 1. For all f:N^k into N, there exist distinct x_1,...,x_k+1  
such that f(x_2,...,x_k+1) - f(x_1,...,x_k) lies in 2N.

THEOREM 2. Theorem 1 is provably equivalent to "epsilon_0 is well  
ordered" over RCA_0. Theorem 1 for recursive f's is provably  
equivalent to the 2-consistency of PA, over EFA. Theorem 1 for  
primitive recursive (or elementary recursive or poly time in bit  
representations or linear time/log space in bit representations) is  
provably equivalent to the 1-consistency of PA, over EFA. Theorem 1  
for polynomials is provable in EFA.

These same results hold if we use other forms of Theorem 1. E.g.,

THEOREM 1'. For all f,g:N^k into N, there exist distinct x_1,...,x_k+1  
such that f(x_1,...,x_k) <= f(x_2,...,x_k+1) and g(x_1,...,xk) <=  
g(x_2,...,x_k+1).

However, Theorem 1' with just f is obviously provable in RCA_0.

We now come to the new idea.

The multiplicity of f at x is the number of times f achieves the value  
x. This number is among 0,1,2,...,infinity.

POLYNOMIAL SHIFT THEOREM. For all polynomials P:Z^k into Z^k, there  
exist distinct positive n_1,...,n_k+1 such that the number of times P  
achieves (n_2,...,n_k+1) exceeds the the number of times P achieves  
(n_1,...,n_k) by a nonnegative even integer.

QUADRATIC SHIFT THEOREM. For all quadratic P:Z^k into Z^k, there exist  
distinct positive n_1,...,n_k+1 such that the number of times P  
achieves (n_2,...,n_k+1) exceeds the the number of times P achieves  
(n_1,...,n_k) by a nonnegative even integer.

THEOREM 3. The Polynomial Shift Theorem and The Quadratic Shift  
THeorem are provable in ACA' but not in Peano Arithmetic. They imply 2- 
Con(PA) over EFA.

Here ACA' is ACA_0 + "for all x,n, the n-th jump of x exists".

I think that they are equivalent to 3-Con(PA) over EFA.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 377th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-349 can be found at http://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
in the FOM archives.

350: one dimensional set series  7/23/09  12:11AM
351: Mapping Theorems/Mahlo/Subtle  8/6/09  10:59PM
352: Mapping Theorems/simpler  8/7/09  10:06PM
353: Function Generation 1  8/9/09  12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1  8/9/09  6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2  8/10/09  6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem  8/14/09  9:31AM
357: HIGH SCHOOL Games/Update  8/20/09  10:42AM
358: clearer statements of HIGH SCHOOL Games  8/23/09  2:42AM
359: finite two person HIGH SCHOOL games  8/24/09  1:28PM
360: Finite Linear/Limited Memory Games  8/31/09  5:43PM
361: Finite Promise Games  9/2/09  7:04AM
362: Simplest Order Invariant Game  9/7/09  11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1  9/24/09  1:06PM
366: Free Reductions and Large Cardinals/polished  9/28/09  2:19PM
367: Upper Shift Fixed Points and Large Cardinals  10/4/09  2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction  10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement  10/29/09  2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09  12:14PM
371: Vector Reduction and Large Cardinals  11/21/09  1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09  5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals  12/7/09  9:17AM
374: Upper Shift Greedy Chain Games  12/12/09  5:56AM
375: Upper Shift Clique Games and Large Cardinals 1
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals   
12/24/09  2:23PM

Harvey Friedman