# 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. steviefaulkner says:

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.