Not all elementary functions can be expressed with exp-minus-log

By Robert Smith

All Elementary Functions from a Single Operator is a paper by Andrzej Odrzywołek that has been making rounds on the internet lately, being called everything from a “breakthrough” to “groundbreaking”. Some are going as far as to suggest that the entire foundations of computer engineering and machine learning should be re-built as a result of this. The paper says that the function

$$ E(x,y) := \exp x - \log y $$

together with variables and the constant $1$, which we will call EML terms, are sufficient to express all elementary functions, and proceeds to give constructions for many constants and functions, from addition to $\pi$ to hyperbolic trigonometry.

I think the result is neat and thought-provoking. Odrzywołek is explicit about his definition of “elementary function”. His Table 1 fixes “elementary” as 36 specific symbols, and under that definition his theorem is correct and clever, so long as we accept some of his modifications to the conventional $\log$ function.

My concern is that the word “elementary” in the title carries a much broader meaning in standard mathematical usage, and under two reasonable other interpretations of “elementary”, the paper’s title does not hold. In layman’s terms, I do not consider the “Exp-Minus-Log” function to be the continuous analog of the Boolean NAND gate or the universal quantum CCNOT/CSWAP gates.

In the first section, I’ll make a quick observation: a very basic scientific function cannot be expressed with EML terms alone if we use the standard definitions of $\exp$ and $\log$. In the second section, I’ll give a relatively technical but independent argument that EML terms are not sufficient to express what I consider standard elementary functions.

Disclaimer: I audited graduate-level mathematics courses almost 20 years ago, and I am not a professional mathematician. Please email me if my statements are clumsy or incorrect.

The “Scientific Calculator Basis” and the absolute value

The author refers to his definition of elementary functions as the “scientific calculator basis”, that is, “the standard repertoire of a scientific calculator”. One function not included is the absolute value function, an “elementary” function known to middle schoolers that is present on many scientific calculators. The rub: It is an example of a function that cannot be built out of EML terms if we assume the standard mathematical definition of $\exp$ and $\log$..

Theorem: There is no EML term $T(x)$ such that $T(x)=\vert x\vert$ for all $x\in\mathbb R$.

Proof: First observe that every EML term is real-analytic on its domain. This is proved by structural induction on terms. The basic terms $1$ and $x$ are real-analytic. If $A(x)$ and $B(x)$ are real-analytic on an open interval $I$, then $\exp A(x)$ is real-analytic on $I$, and $\log B(x)$ is real-analytic on every open subinterval of $I$ on which $B(x)$ is positive. Hence $$ E(A(x),B(x)) = \exp A(x) - \log B(x) $$ is real-analytic wherever it is defined. Therefore every EML term is real-analytic on its domain.

Now suppose some EML term $T(x)$ satisfies $T(x)=\vert x\vert$ for all real $x$. Then $\mathrm{dom}(T)=\mathbb R$, so by the previous paragraph, $T$ is real-analytic on all of $\mathbb R$, in particular at $0$. Hence $\vert x\vert$ is real-analytic at $0$. But $\vert x\vert$ is not even differentiable at $0$, so it cannot be real-analytic there. This is a contradiction. ∎

The author works around this by making non-standard definitions, or, ostensibly, operating in the extended reals.

What about in the complex domain though? The author is clear that for the machinery to work, we should extend past the real numbers.

Theorem: There is no EML term $T(z)$ and nonempty open set $U\subseteq\mathbb C$ such that some branch of $T$ equals $\vert z\vert$ on $U$.

Proof: An EML term may be multivalued because of $\log$, but on any open set $U\subseteq\mathbb C$ on which a consistent choice of branch exists, the resulting single-valued function is holomorphic. This is immediate by induction: $1$ and $z$ are holomorphic; if $A$ is holomorphic on $U$ then so is $\exp A$; and every branch of $\log B$ is holomorphic wherever it is defined.

Now assume some branch of an EML term $T$ satisfies $T(z)=\vert z\vert$ on a nonempty open set $U\subseteq\mathbb C$. Then $\vert z\vert$ would be holomorphic on $U$. But writing $u(x,y)=\sqrt{x^2+y^2}$ and $v(x,y)=0$, we have for $(x,y)\neq(0,0)$, $$ u_x=\frac{x}{\sqrt{x^2+y^2}},\qquad u_y=\frac{y}{\sqrt{x^2+y^2}},\qquad v_x=v_y=0, $$ so the Cauchy–Riemann equations fail throughout $U\setminus\{0\}$. Contradiction. ∎

“Standard” elementary functions

The 19th century is where all modern understanding of elementary functions was developed, Liouville being one of the big names with countless theorems of analysis and algebra named after him. In this setting, the elementary functions, informally, are defined by starting with rational functions and closing under arithmetic operations, composition, exponentiation, logarithms, and polynomial roots. In particular, algebraic functions are elementary in this modern sense. The argument that follows is an instance of Khovanskii’s topological Galois theory: the monodromy group of a function built from rational functions by composition with $\exp$ and $\log$ is solvable.

First, let’s be more precise by what we mean by an EML term and by a standard elementary function.

Definition (EML Term): An EML term in the variables $x_1,\dots,x_n$ is any expression obtained recursively, starting from $\{1, x_1,\dots,x_n\}$, by the rule $$ T,S \mapsto \exp T-\log S. $$ Each such term, evaluated at a point where all the $\log$ arguments are nonzero, determines an analytic germ; we take $\mathcal T_n$ to be the class of germs representable this way, together with their maximal analytic continuations.

Definition (Standard Elementary Function): The standard elementary functions $\mathcal{E}_n$ are the smallest class of multivalued analytic functions on domains in $\mathbb{C}^n$ containing the rational functions and closed under

What we will show is that the class of elementary functions defined this way is strictly larger than the class induced by EML terms.

Lemma: Every EML term has solvable monodromy group. In particular, if $f\in\mathcal T_n$ is algebraic over $\mathbb C(x_1,\dots,x_n)$, then its monodromy group is a finite solvable group.

Proof: We prove by induction on EML term construction. Constants and coordinate functions have trivial monodromy.

For the inductive step, suppose $f = \exp A-\log B$ with $A,B\in\mathcal T_n$, and assume that $\mathrm{Mon}(A)$ and $\mathrm{Mon}(B)$ are solvable. We argue in three steps.

Step 1: $\mathrm{Mon}(\exp A)$ is solvable. The germs of $\exp A$ are images under $\exp$ of the germs of $A$, with germs of $A$ differing by $2\pi i\mathbb Z$ collapsing to the same value. So there is a surjection $\mathrm{Mon}(A)\twoheadrightarrow\mathrm{Mon}(\exp A)$, and a quotient of a solvable group is solvable.

Step 2: $\mathrm{Mon}(\log B)$ is solvable. At a generic point $p$, germs of $\log B$ are parameterized by pairs $(b,k)$ where $b$ is a germ of $B$ at $p$ and $k\in\mathbb Z$ selects the branch of $\log$. A loop $\gamma$ acts by $$ (b,k)\mapsto\bigl(\rho_B(\gamma)(b), k+n(\gamma,b)\bigr), $$ where $\rho_B(\gamma)$ is the monodromy action of $\gamma$ on germs of $B$, and $n(\gamma,b)\in\mathbb Z$ is the winding number around $0$ of the analytic continuation of $b$ along $\gamma$. The projection $\mathrm{Mon}(\log B)\to\mathrm{Mon}(B)$ onto the first component is a surjective homomorphism. Its kernel consists of the elements of $\mathrm{Mon}(\log B)$ induced by loops $\gamma$ with $\rho_B(\gamma)=\mathrm{id}$, which then act only by integer shifts on the $k$-coordinate. Let $S_B$ be the set of germs of $B$ at $p$. For each $b\in S_B$, such a loop determines an integer shift $n(\gamma,b)$, so the kernel embeds in the direct product $\mathbb Z^{S_B}$. In particular, the kernel is abelian. Hence $\mathrm{Mon}(\log B)$ is an extension of $\mathrm{Mon}(B)$ by an abelian group, and extensions of solvable groups by abelian groups are solvable.

Step 3: $\mathrm{Mon}(f)$ is solvable. At a generic point, a germ of $f=\exp A-\log B$ is obtained by subtraction from a pair (germ of $\exp A$, germ of $\log B$), and analytic continuation acts componentwise on such pairs. This gives a surjection of $\pi_1$ onto some subgroup $$ H \le \mathrm{Mon}(\exp A)\times\mathrm{Mon}(\log B), $$ and, since $f$ is obtained from the pair by subtraction, this descends to a surjection $H\twoheadrightarrow\mathrm{Mon}(f)$. So $\mathrm{Mon}(f)$ is a quotient of a subgroup of a direct product of solvable groups, hence solvable.

The second statement of the lemma follows: an algebraic function has finitely many branches, so its monodromy group is finite; a solvable group that is finite is, well, finite and solvable. ∎

Remark. This is the core of Khovanskii’s topological Galois theory; see Topological Galois Theory: Solvability and Unsolvability of Equations in Finite Terms.

Theorem: $\mathcal T_n \subsetneq \mathcal E_n$.

Proof: $\mathcal E_n$ is closed under algebraic adjunction, so any local branch of an algebraic function is elementary. In particular, a branch of a root of the generic quintic $$ f^5+a_1f^4+a_2f^3+a_3f^2+a_4f+a_5=0 $$ is elementary.

Suppose for contradiction that at some point $p$ a germ of a branch of this root agrees with a germ of an EML term $T$. By uniqueness of analytic continuation, the Riemann surfaces obtained by maximally continuing these two germs coincide, so in particular their monodromy groups coincide. The monodromy group of the generic quintic is $S_5$, which is not solvable. But by the lemma, the monodromy group of any EML term is solvable. Contradiction.

Hence $\mathcal T_n$ is a strict subset of $\mathcal E_n$. ∎