Written by mkoconnor

The Undecidability of Identities Involving Sine, Exponentiation, and Absolute Value

In the book A=B, the authors point out that while the identity

\displaystyle{\sin^2(|10 + \pi x|) + \cos^2(|10 + \pi x|) = 1}

is provable (by a very simple proof!), it’s not possible to prove the truth or falsity of all such identities. This is because Daniel Richardson proved the following:

Let \mathcal{R} denote the class of expressions generated by

  1. The rational numbers, and \pi.
  2. The variable x
  3. The operations of addition, multiplication, and composition.
  4. The sine, exponential, and absolute value functions.

Then the problem of deciding whether or not an expression E in \mathcal{R} is identically zero is undecidable. This means as well that the problem of deciding whether or not two expressions E_1, E_2\in \mathcal{R} are always equal is also undecidable, since this is equivalent to deciding if E_1 - E_2 = E_1 + (-1)\cdot E_2 is identically zero.

A summary of Richardson’s proof (mostly from Richardson’s paper itself) is below.

The proof depends on the MRDP theorem, which says that for any recursively enumerable set S\subset \mathbb{N}, there is a polynomial p(y,x_1,\ldots, x_n) such that

For all y\in\mathbb{N}, y\in S iff there exist x_1\ldots, x_n\in\mathbb{N} such that p(y,x_1,\ldots, x_n) = 0.

At the time that Richardson proved his result, the MDRP theorem was not proven. Instead, only the weaker result where p is allowed to be an exponential polynomial (i.e., the x_i are allowed to appear as exponents in p) had been proven, and so that’s what he used. I haven’t read Richardson’s proof closely enough to determine if his result can be improved using the full MDRP theorem.

In any case, since there are recursively enumerable sets which are not decidable, we may let p(y,x_1,\ldots, x_n) be an exponential polynomial such that the problem of deciding, given y\in\mathbb{N}, whether or not there are x_1,\ldots, x_n\in \mathbb{N} such that p(y,x_1,\ldots, x_n)=0 is undecidable.

Therefore, the problem of deciding, given y\in\mathbb{N}, whether or not there are non-negative real numbers x_1,\ldots, x_n such that

(p(y,x_1,\ldots,x_n))^2 + \sum_{i=1}^n \sin^2 \pi x_i = 0

is undecidable.

Now, let q(y,x_1,\ldots, x_n) be an exponential polynomial which grows very fast (and such that q(0,\ldots,0) is very large). Then, if y is a natural number and there are non-negative reals x_1,\ldots, x_n such that

\displaystyle{q(y,x_1,\ldots, x_n)\cdot ((p(y,x_1,\ldots, x_n))^2 + \sum_{i=1}^n \sin^2 \pi x_i})

is less than one, then both |p(y,x_1,\ldots, x_n)| and \sum_{i=1}^n \sin^2 \pi x_i are small. From this last fact, we conclude that each x_i is close to a natural number. Let \langle x_i\rangle be the natural number closest to x_i. Then, |p(y,\langle x_1\rangle, \ldots, \langle x_n\rangle)| will be small. But then, because it’s an integer, it will be zero.

Therefore, we have an expression G(y,x_1\ldots,x_n) formed from sine and exponential functions (and rational numbers, addition, and multiplication) such that for each y\in\mathbb{N}, there exist non-negative reals x_1,\ldots, x_n such that G(y,x_1,\ldots, x_n) < 1 iff there exist natural numbers x_1,\ldots, x_n such that p(y,x_1,\ldots x_n) = 0 (which is an undecidable problem).

By an argument which I won’t reproduce here, we can replace G(y,x_1,\ldots, x_n) with G_0(y,x) with the property that for each y\in\mathbb{N} there exists a real x such that G_0(y,x) < 0 iff there exist natural numbers x_1,\ldots, x_n such that p(y,x_1,\ldots, x_n)= 0. (Notice that x now ranges over all reals.) But now, consider the sequence of functions

|G_0(0,x)| - G_0(0,x), |G_0(1,x)| - G_0(1,x), |G_0(2,x)| - G_0(2,x), \ldots

Each is identically zero iff the corresponding G(n,x) is ever less than zero, which is an undecidable problem.

The reference for Richardson’s paper is: Daniel Richardson, “Some unsolvable problems involving elementary functions of a real variable,” Journal of Symbolic Logic, Volume 33, 1968, pages 514–520

Another reference is: B.F. Caviness, “On canonical forms and simplification,” Journal of the ACM, volume 17, 1970, pages 385–396.

2 thoughts on “The Undecidability of Identities Involving Sine, Exponentiation, and Absolute Value”

  1. I do not have enough knowledge to follow your work closely, but I find what you are doing very interesting indeed. I see similarity in it to questions I am considering. The fact you are considering the undecidability in an identity that implies orthogonality is of interest and also the fact you are considering irrational numbers.

    It looks as though you are not considering field variables but am I right in believing that under the Field Axioms, formulae proposing the existence of non-rational numbers are undecidable due to combined effects of Soundness and Completeness Theorems? If so, you might find this an interesting connection to your work.

    Reply

  2. If you are interested in the origins of indeterminacy in Quantum Mechanics, read my newly finished paper titled:

    “The Mathematical Undecidability within Quantum Physics: The Origin of Indeterminacy and Mechanism of Decision at Measurement”

    To get a copy click on the following link:

    Click to access undecidability-in-qm_1034.pdf

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s