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

Yes, this article is kicking in open doors, the original article was quite clear about the scope.

The present article could rather have spent time arguing why this isn't like NAND gate functional completeness.

I would have thought the differences lie in the other direction: not that trees of EML and 1 can describe too little, but that they can describe too much already. It's decidable whether two NAND circuits implement the same function, I'm pretty sure it's not decidable if two EML trees describe the same function.

> Neither the present article, nor the original one has much mathematical originality, though: Odrzywolek's result is immediately obvious, [...]

Maybe. But I found it a nice piece of recreational mathematics nevertheless.

Arnold (as reported by Goldmakher [1]) does prove the unsolvability of the quintic in finite terms of arithmetic and single-valued continuous functions (which does not include the complex logarithm). TFA's result is stronger, which is something about the solvability of the monodromy groups of all EML-derived functions. So it doesn't seem to be a "rehash", even if their specific counterexample could have been achieved either in fewer steps or with less machinery.

[1] https://web.williams.edu/Mathematics/lg5/394/ArnoldQuintic.p...

> Odrzywolek's result is immediately obvious

Many things that in retrospect seem immediately obvious weren't obvious before, let alone immediately obvious.

> Odrzywolek's result is immediately obvious

This may or may not be true; but the burden of proof should not lay with the reader.

Please provide (in absence of which every reader can draw their own conclusions) a reference which simultaneously:

1) predates Odrzywolek's result

2) and demonstrates the other unary and binary operations typically tacitly assumed can be expressed in terms of a single binary operation and a constant.

(in other news: I can spontaneously levitate, I just don't feel like demonstrating it to you right now...)

All I know is that when a class starts with 'elementary' or 'fundamentals of' you had best buckle up.

> If you take a real analysis class, the elementary functions will be defined exactly as the author of the EML paper does.

I just looked through many of the best known real analysis texts, and not a single one defines them this way. This list included the texts by

Royden, Terence Tao, Rudin, Spivak, Bartle & Sherbert, Pugh, and a few others....

Can you cite a single text book that has this definition you claim is in every real analysis course? I find all evidence points to the opposite.

The definition of "elementary function" typically includes functions which solve polynomials, like the Bring radical. The definition was developed and is most fitting in algebraic contexts where algebraic structure is meaningful, like Liouvillian structure theorems, algorithmic integration, and computer algebra. See e.g.

- Page 2 and the following example of https://billcookmath.com/courses/math4010-spring2016/math401... (2016)

- Ritt's Integration in Finite Terms: Liouville's Theory of Elementary Methods (1948)

It's not frequent that analysis books will define the class of elementary functions rigorously, but instead refer to examples of them informally.

    f + f*(exp∘log)

jargon are words being used that don't carry the typical laymen definition, but a specific one from the domain of said jargon.

If a written piece is intended for an audience who knows the jargon, then it's fine to use jargon - in fact it's appropriate and succinct. If it was intended for the laymen, then jargon is inappropriate.

But it seems you're lamenting that this jargon is wrong and that it shouldn't be jargon!?

I don't know if I read this right, but I thought it's proven that "elementary functions" can't solve 5th degree or higher polynomial, so I'm confused how it's interpreted if elementary functions also include arbitrary polynomial roots. Or is it different elementary functions?

In math elementary usually means fundamental or foundational not elementary school. The root word is element and the relationship to “simple subject” is tangential and more related to its teaching the elemental topics for a lifetime education than definitionally cross discipline.

1)

> Related is the paper [What is a closed-form number?], which explores the field E, defined as the smallest subfield of ℂ closed under exp and log. I believe the set of numbers that can be generated using exp-minus-log is a strict subset of this.

is that a typo / accidental mis-phrasing?

exp-minus-log construction is closed for the operations it supports, and spans both exp and log, so E must be either identical to or a subset of exp-minus-log; not the other way around.

2)

EML is spanned by a single binary operator, while the article you reference describing ("what is a closed-form number") just tacitly assumes +, -, x, / are available for free, so even in just this sense the EML construction is superior. Since EML can construct the larger presumed basic operations of E, E must be contained in it, but since the E implicitly has +, - besides exp(x) and ln(x) the reverse can also be said, so the sets and functions spanned by E and EML should be equivalent. So what is novel? precisely what the recent article describes: all the tacitly (+,-,x,/) and explicitly assumed (exp and ln) operations can be spanned with just 1 (non-unique) binary operation; and on top of that:

3)

the recent article describes freely available code to conduct such searches and find alternative binary operations, search for functions or constants.

The EML paper provides code and machinery to conduct a search for the value x in exp(-x)=x : use a multiprecision library to get an arbitrarily precise representation, and search for some EML expression to find candidates.

When you may use functions of 3 or more arguments, it becomes trivial to find a single function that can be used to express large classes of other functions.

These tricks break when you are restricted to use one binary function, like in the EML paper.

The second argument cannot be used as a selector, because you cannot make binary functions from unary functions (while from binary functions you can make functions with an arbitrary number of parameters, by composing them in a tree).

If you used an argument as a function selector in a binary function, which transforms the binary function into a family of unary functions, then you would need at least one other auxiliary binary function, to be able to make functions with more than one parameter.

The auxiliary binary function could be something like addition or subtraction, or at the minimum a function that makes a tuple from its arguments, like the function CONS of LISP I.

The EML paper can also be understood that the elementary functions as defined by it can be expressed using a small family of unary functions (exponential, logarithmic and negation), together with one binary function: addition.

Then this set of 4 simple functions is reduced to one complex function, which can regenerate any of those 4 functions by composition with itself.

This is the same trick used to reduce the set of 2 simple functions, AND & NOT, which are sufficient to write any logical function, to a single function, NAND, which can generate both simpler functions.

This is similar to the idea of generating functions, if you would like more to read!

Why would it be surprising?

And if you want something truly surprising, Riemann's zeta function can approximate any holomorphic function arbitrarily well on the critical strip. So technically you need only _one_ argument.

"The quintic has no closed form solution" is a theorem that is more precisely stated (in the usual capstone Galois proof) as follows: The quintic has no closed form solution in terms of arbitrary compositions of rational numbers, arithmetic, and Nth roots. We can absolutely express closed form solutions to the quintic if we broaden our repertoire of functions, such as with the Bring radical.

The post's argument is different than the usual Galois theory result about the unsolvability of the quintic, in that it shows a property that must be true about all EML(x,y)-derived functions, and a hypothetical quintic-solver-function does not have that property, so no function we add to our repertoire via EML will solve it (or any other function, elementary or not, that lacks this property).

    Do integrals of elementary functions give us elementary functions?

    sum(k = 0 to inf) binom(5k,k) (-1)^(k+1) a^(4k+1) / (4k+1)

    x <- x - (x^5 + x + a)/(5x^4 + 1)

Can anyone provide a link that "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", or anything similarly grandiose?

I am a professional mathematician, though nowhere near this kind of thing. The result seems amusing enough, but it doesn't really strike me as something that would be surprising. I confess that this thread is the first I've heard of it...

His claim is that we exp-minus-log cannot compute the root of an arbitrary quintic. If you consider the root of an arbitrary quintic "elementary" the exp-minus-log can't represent all elementary functions.

I think it really comes down to what set of functions you are calling "elementary".

The argument is that a universal basis would be capable of solving arbitrary polynomial roots. The rest is an argument that the group constructed by eml is solveable, and hence not all the standard elementary functions.

It wouldn't be a math discussion without people using at least two wildly different definitions.

Yes, that blog post could have been much shorter….

I would agree, it makes them anything but elementary. I am honestly not even sure if there is a finite constructible basis of the functions that can express any solution of single-variable integer polynomials.

And for multivariate polynomials, the roots are uncomputable due to MRDP theorem.

EML can represent the real absolute value, so long as we agree with the original author's proviso that we define log(0) and exp(-∞), by way of sqrt(x^2) as f(x) = exp((1/2)log x). Traditionally, log(0) isn't defined, but the original author stipulated it to be -∞, and that all arithmetic works over the "extended reals", which makes

    abs(0)
    = f(0)            ; by defn
    = exp(1/2 log 0)  ; by defn
    = exp(-∞/2)       ; log 0 rule
    = exp(-∞)         ; extended real arith
    = 0               ; exp(-∞) rule

If we don't agree with this, then abs() could be defined with a hole punched out of the real line. The logarithm function isn't exactly elegant in this regard with its domain restrictions. :)

abs(x) = sqrt(x*x), no?

I only skimmed the article, but I think the idea is to use some variation on:

f(a,b,c,d,e) = the largest real solution x of the quintic equation x^5 + ax^4 + bx^3 + cx^2 + dx + e = 0

There's not a simple formula for this function (which is the basic point), but certainly it is a function: you feed it five real numbers as input, and it spits out one number as output. The proof that you can't generate this function using the single one given looks like some fairly routine Galois theory.

Whether this function is "considered elementary" depends on who you ask. Most people would not say this is elementary, but the author would like to redefine the term to include it, which would make the theorem not true anymore.

Why any of this would shake the foundations of computer engineering I do not know.

It's already past midnight in New Zealand, e.g.

Closed-form expressions, I guess?

"For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions."