Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Polynomial value sets

Closely related to issues of solving Diophantine equations is the question of what set of positive values a polynomial can achieve when fed all possible positive integer values for its variables. A polynomial with a single variable must always yield either be a finite set, or a simple polynomial progression of values. But already the sequence of values for x2*y - x*y3 or even x (y2+1) seem quite complicated. And for example from the fact that x2 == y2 + x y ±1 has solutions Fibonacci[n] it follows that the positive values of (2 - (x2 - y2 - x y)2)x are just Fibonacci[n] (achieved when {x,y} is Fibonacci[{n,n-1}]). This is the simplest polynomial giving Fibonacci[n], and there are for example no polynomials with 2 variables, up to 4 terms, total degree less than 4, and integer coefficients between -2 and +2, that give any of 2n, 3n or Prime[n]. Nevertheless, from the representation for PrimeQ in the note above it has been shown that the positive values of a particular polynomial with 26 variables, 891 terms and total degree 97 are exactly the primes. (Polynomials with 42 variables and degree 5, and 10 variables and degree 1045, are also known to work, while it is known that one with 2 variables cannot.) And in general the existence of a universal Diophantine equation implies that any set obtained by any finite computation must correspond to the positive values of some polynomial. The analog of doing a long computation to find a result is having to go to large values of variables to find a positive polynomial value. Note that one can imagine, say, emulating the evolution of a cellular automaton by having the tth positive value of a polynomial represent the tth step of evolution. That universality can be achieved just in the positive values of a polynomial is already remarkable. But I suspect that in the end it will take only a surprisingly simple polynomial, perhaps with just three variables and fairly low degree.

(See also page 1165.)


From Stephen Wolfram: A New Kind of Science [citation]