# [FOM] 437: Twin Prime Polynomial

Harvey Friedman friedman at math.ohio-state.edu
Wed Sep 15 13:09:46 EDT 2010

```THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

######################################################################

INTEGER POLYNOMIAL DECISION PROBLEMS
September 15, 2010

The following result illustrates the difficulties inherent in
understanding the set of nonnegative values of rather simple
polynomials from N^3 into Z.

THEOREM. The Twin Prime Conjecture is equivalent to the assertion that
a particular polynomial P:N^3 into Z of degree 4 omits infinitely many
nonnegative values. Furthermore, the coefficients are 1,2,4,6,-1,-2.

To see this, note that

k is not a twin prime iff

1. (forall x,y >= 0)(k = (x+2)(y+2) or k = (x+2)(y+2)+2)

2. (forall x,y,z >= 0)(k = (x+2)(y+2)+z and z(z-2) = 0)

3. (forall x,y,z >= 0)(k = (x+2)(y+2)+2z and z(1-z)+1 = 1)

4. (forall x,y,z >= 0)(k = ((x+2)(y+2)+2z)(z(1-z)+1))

Set P(x) = ((x+2)(y+2)+2z)(z(1-z)+1)) = (xy+2x+2y+2z+4)(-z^2+z+1) =
-xyz^2+xyz+xy-2xz^2+2xz+2x-2yz^2+2yz+2y-2z^3+2z^2+2z-4z^2+4z+4 =
-xyz^2+xyz+xy-2xz^2+2xz+2x-2yz^2+2yz+2y-2z^3-2z^2+6z+4. QED

PROBLEM: Can we find a "simpler" polynomial for the above Theorem?

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

manuscripts. This is the 437th 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 athttp://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 1graham
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09  2:23PM
377: The Polynomial Shift Theorem  12/25/09  2:39PM
378: Upper Shift Clique Sequences and Large Cardinals  12/25/09 2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems  12/28/09  7:06AM
381: Trigonometric Shift Theorem  12/29/09  11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals  12/30/09 2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09  3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences  1/1/10  7:35PM
386: Terrifically and Extremely Long Finite Sequences  1/1/10 7:35PM
387: Better Polynomial Shift Translation/typos  1/6/10  10:41PM
388: Goedel's Second Again/definitive?  1/7/10  11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1 2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2 2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3 2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4 2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5 2/22/10
3:50AM
394: Free Reduction Theory 1  3/2/10  7:30PM
395: Free Reduction Theory 2  3/7/10  5:41PM
396: Free Reduction Theory 3  3/7/10  11:30PM
397: Free Reduction Theory 4  3/8/10  9:05AM
398: New Free Reduction Theory 1  3/10/10  5:26AM
399: New Free Reduction Theory 2  3/12/10  9:36AM
400: New Free Reduction Theory 3  3/14/10  11:55AM
401: New Free Reduction Theory 4  3/15/10  4:12PM
402: New Free Reduction Theory 5  3/19/10  12:59PM
403: Set Equation Tower Theory 1  3/22/10  2:45PM
404: Set Equation Tower Theory 2  3/24/10  11:18PM
405: Some Countable Model Theory 1  3/24/10  11:20PM
406: Set Equation Tower Theory 3  3/25/10  6:24PM
407: Kernel Tower Theory 1  3/31/10  12:02PM
408: Kernel tower Theory 2  4/1/10  6:46PM
409: Kernel Tower Theory 3  4/5/10  4:04PM
410: Kernel Function Theory 1  4/8/10  7:39PM
411: Free Generation Theory 1  4/13/10  2:55PM
412: Local Basis Construction Theory 1  4/17/10  11:23PM
413: Local Basis Construction Theory 2  4/20/10  1:51PM
414: Integer Decomposition Theory  4/23/10  12:45PM
415: Integer Decomposition Theory 2  4/24/10  3:49PM
416: Integer Decomposition Theory 3  4/26/10  7:04PM
417: Integer Decomposition Theory 4  4/28/10  6:25PM
418: Integer Decomposition Theory 5  4/29/10  4:08PM
419: Integer Decomposition Theory 6  5/4/10   10:39PM
420: Reduction Function Theory 1  5/17/10   2:53AM
421: Reduction Function Theory 2  5/19/10   12:00PM
422: Well Behaved Reduction Functions 1  5/23/10  4:12PM
423: Well Behaved Reduction Functions 2  5/27/10  3:01PM
424: Well Behaved Reduction Functions 3  5/29/10  8:06PM
425: Well Behaved Reduction Functions 4  5/31/10  5:05PM
426: Well Behaved Reduction Functions 5  6/2/10  12:43PM
427: Finite Games and Incompleteness 1  6/10/10  4:08PM
428: Typo Correction in #427  6/11/10  12:11AM
429: Finite Games and Incompleteness 2  6/16/10  7:26PM
430: Finite Games and Incompleteness 3  6/18/10  6:14PM
431: Finite Incompleteness/Combinatorially Simplest  6/20/10  11:22PM
432: Finite Games and Incompleteness 4  6/26/10  8:39PM
433: Finite Games and Incompleteness 5  6/27/10  3:33PM
434: Digraph Kernel Structure Theory 1  7/4/10  3:17PM
435: Kernel Structure Theory 1  7/5/10  5:55PM
436: Kernel Structure Theory 2  7/9/10  5:21PM

Harvey Friedman
```