Neither the present article, nor the original one has much mathematical originality, though: Odrzywolek's result is immediately obvious, while this blog post is a rehash of Arnold's proof of the unsolvability of the quintic.
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.
Well, sure. At least, until you have a loop that starts clocking for you, and now you've got the halting problem.
Maybe. But I found it a nice piece of recreational mathematics nevertheless.
[1] https://web.williams.edu/Mathematics/lg5/394/ArnoldQuintic.p...
These classes can always safely include all single-valued continuous functions (you cannot even write the _quadratic_ formula in terms of arithmetic and single-valued continuous functions!), but also plenty of non-single-valued functions (e.g. the +-sqrt function which appears in the well-known quadratic formula).
Applying Arnold's proof to the class given by arithmetic and all complex nth root functions (also multivalued) gives the usual Abel-Ruffini theorem. But Arnold's proof applies to the class "all elm-expressible functions" without modification.
Many things that in retrospect seem immediately obvious weren't obvious before, let alone 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...)
You can find thousands of such questions on Math StackExchange. Take e.g. [1]: never been asked anywhere else, interesting enough, yet answered pretty much immediately by two separate mathematicians.
"Is there a single constant and function with connected domain that can express all of $\log, \exp, \sin, \dots$?" would have made a fine question there too, the type that gets a thorough answer very quickly if anyone bothers to ask it.
> the burden of proof should not lay with the reader
You were the one who made the claim that "this is one of the most significant discoveries in years". Feel free to substantiate that claim first, according to the same standards. Are there any authors who ask this question, and/or suggest that they don't know an answer?
[1] https://math.stackexchange.com/questions/2308587/is-the-set-...
> Elementary functions typically include arbitrary polynomial roots, and EML terms cannot express them.
If you take a real analysis class, the elementary functions will be defined exactly as the author of the EML paper does.
I've actually just learnt that some consider roots of arbitrary polynomials being part of the elementary functions before, but I'm a physicist and only ever took some undergraduate mathematics classes. Nonetheless, calling these elementary feels a bit of stretch considering that the word literally means basic stuff, something that a beginner will learn first.
There's also the opposite in physics though, "modern" means from the 60s with square roots drawn in manually.
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 elementary functions of analysis, that is powers, roots, exponentials, logarithms and their inverses, functions obtained from the former by arithmetic operations or composition, admit the limit f(p) for x → p, for any p in their set of definition. The study of such functions, which is not limited to the sole real functions of real variable, is carried out naturally in the setting of metric spaces.
That said, I'm relatively sure that a definition was given in class and it didn't include arbitrary roots: despite being notoriously difficult, the exam didn't require students to draw the graph of any elementary function including implicitly-defined algebraic roots.
I picked up another one of the old recommended books [2] and it seems to be similarly vague; while the book currently taught in my university [3], gives this definition:
> The following functions (from ℂ to ℂ) are called the elementary functions of the Analysis:
> 1) Rational functions (integral or fractional)
> 2) Algebraic functions (explicit or implicit)
> 3) The exponential function
> 4) The logarithm function
> 5) All those functions that can be obtained by combining a finite number of times the functions of kind 1)...4).
So, roots of arbitrary polynomials implicitly defined are indeed considered elementary. I never knew this.
[1]: https://search.worldcat.org/title/1261811544
- 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.
There appears to be a typo in that example; I assume "Essentially elementary functions are the functions that can be built from ℂ and f(x) = x" should say something more like "the functions that can be built from ℂ and f(x) = y".
What. Does that "typical definition" of elementary function includes elliptic functions as well, by any chance?
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!?
It says that polynomial equations of the 5th degrees or higher cannot, in general, be solved using "radicals".
While something like "polynomials" or "radicals" has a clear meaning, which are the "elementary functions" is a matter of convention.
The usual convention is to include all algebraic functions and a few selected transcendental functions.
In "all algebraic functions", are included the rational functions, the radicals and the functions that compute solutions of arbitrary polynomial equations.
Some conventions used for "elementary functions" describe the expressions that you can use to write such "elementary functions", in which case not all algebraic functions are included, but only those written by combining rational functions with radicals.
For an algebraic function that computes a solution of a general polynomial equation, which cannot be expressed with radicals, you cannot write an explicit formula, but you can write the function only implicitly, by writing the corresponding polynomial equation.
So the difference between the 2 kinds of conventions about which are "the elementary functions" is usually based on whether only explicitly-written functions are considered, or also implicit functions.
Definitions are either a bit fuzzy, or not universally agreed on.
Though interestingly https://en.wikipedia.org/wiki/Elementary_function says "More generally, in modern mathematics, elementary functions comprise the set of [...]". Though at least Wikipedia thinks that 'modern mathematics' has a consensus; of course, there's no guarantee that whoever you are talking to uses the 'modern mathematics' definition that Wikipedia brings up.
Can anyone please explain this further? It seems like he’s moving the goalposts.
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).
You can't solve an equation? Why not just introduce a function that is equal to the solution of the equation! Problem solved.
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...
Some of my favorites:
DoctorOetker: "I'm still reading this, but if this checks out, this is one of the most significant discoveries in years."
cryptonektor: "Given this amazing work, an efficient EML operator HW implementation could revolutionize a bunch of things."
zephen: "This is about continuous math, not ones and zeroes. Assuming peer review proves it out, this is outstanding."
[1] https://news.ycombinator.com/item?id=47746610
[2] https://www.reddit.com/r/math/comments/1sk63n5/all_elementar...
I think it really comes down to what set of functions you are calling "elementary".
(I'm not a mathematician, so don't expect me to have an opinion as far as that goes. But the author also writes well in English, and that language we do share.)
It wouldn't be a math discussion without people using at least two wildly different definitions.
But the fact that a single function can represent a large number of other functions isn't that surprising at all.
It's probably obvious to anyone (it wasn't initially to me), but given enough arguments I can represent any arbitrary set of n+1 functions (they don't even have to be functions on the reals - just as long as the domain has a multiplicative zero available) as a sort of "selector":
g(x_0, c_0, x_1, c_1, ... , x_n, c_n) = c_0 * f_0(x_0) + ... + c_n * f_n(x_n)
The trick is to minimize the number of arguments and complexity of the RHS - but that there's a trivial upper-bound (in terms of number of arguments).
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.
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.
Because I don’t know as much mathematics as you.
Interestingly, the abs (absolute value) function is non-elementary. I wonder if exp-minus-log can represent it.
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
> e^{iφ} = cosφ + i sin φ
So x may be a complex number and sqrt(x*x) is a complex number that sometimes is equal to x and sometimes to -x depending on how lucky you were selecting the branches of sqrt.
Also I'd be glad to see a specific example of a function, considered elementary, which is not representable by EML.
It could be hard, and in any case, thanks for the article. I wish it would be more accessible to me.
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.
As for why this could be important... we sometimes find new ways of solving old problems, when we formulate them in a different language. I remember how i was surprised to learn how representation of numbers as a tuple (ordered list of numbers), where each element is the remainder for mutually prime dividers - as many dividers as there are elements in the tuple - reduces the size of tables of division operation, and so the hardware which does the operation using thise tables may use significantly less memory. Here we might have some other interesting advantages.
At least eml can express the quintic itself, just like the above mentioned operators can
In a similar vein to this post, the paper points out that general polynomials do not have solutions in E, so of course exp-minus-log is similarly incomplete.
What is intriguing is that we don’t even know whether many simple equations like exp(-x) = x (i.e. the [omega constant]) have solutions in E. We of course suspect they don’t, but this conjecture is not proven: https://en.wikipedia.org/wiki/Schanuel%27s_conjecture
What is a closed-form number?: http://timothychow.net/closedform.pdf omega constant: https://en.wikipedia.org/wiki/Omega_constant
> 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.
Since E is by definition closed under exp, log and subtraction, it is clearly also closed under EML.
Admittedly this may be above my math level, but this just seems like a bad definition of elementary functions, given the context.
And for multivariate polynomials, the roots are uncomputable due to MRDP theorem.
Nonetheless, "elementary function" is a technical term dating back to the 19th century; it's very much not a general adjective whose synonym is "basic".
[1] https://en.wikipedia.org/wiki/Hilbert%27s_thirteenth_problem
https://en.wikipedia.org/wiki/Template:Mathematical_expressi...
"For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions."
If nothing else you could solve simple differential equations with them. And it gives you the 'power' function.
The very fact that the set of functions is largely arbitrary is a much bigger issue. Or at least it limits the use of the fact that you can represent those functions.
Edit: I feel the need to add that just because it is a weak critique doesn't mean the argument itself is not interesting.
AFAIU the original paper is a result in the field of symbolic regression. What definition of elementary function do they use?
Don't have anything for the perfect numbers though.
It’s completely wrong, for multiple reasons.
First, and immediately, none of the derived total functions are the functions they appear to be, because they are all partial functions.
Worse than that the domain over which these trees are defined is undecidable by Richardson. You can encode Hilbert’s 10th with elementary functions. Which means you can’t algorithmically decide if a tree evaluates to zero so you never know if ln(y) is undefined
So the central claim is done right off the bat.
Secondly and probably more importantly, these trees have exponential blow up problems because even fairly shallow trees involve tetrations of e that don’t cancel. Even in float64 you can‘t add 800+800 without overflow. Clamping it just gives you wrong answers and clamped exp A) isn’t elementary and B) gives bounded growth so can’t generate all elementary functions.
The consequences for his claimed practical application is disastrous. the loss function is NaN everywhere once you get to around depth 6 in his trees. If you clamp it you just get a flat plateau. Even if you had infinite precision the gradient would be unusable and wouldn’t converge.
As a second note, he frequently in the paper talks about using positive reals as inputs. First, positive reals aren’t even part of his generating set (and if they are his whole central claim is wrong, it has uncountably many constants), but even if they are, fundamentally his operations are complex, and you have subtraction so it is not hard to construct trees that should be total but which never the less are undefined at undecideably many points.
Using extended reals doesn’t save it either. There are just different undefined values that lead to undecideability.
None of these arguments are really specific to EML either. Any binary operator that hopes to generate elementary functions must include exp and ln, must be partial and must be able to encode hilbert’s 10th. There is no fix for this.
You might ask why his tests didn’t find any of this but if you look at his code, they do. He just carefully restricts them to a narrow domain where they happen to work and even then he does things like drop imaginary components and filters out undefined results. He doesn‘t even really hide this in the paper, he just dismisses them as implementation details that can be fixed but the problems are structural
So what we are left with is a generator that can generate exp(x) cleanly and essentially nothing else.
Tests for the trig functions aren't passing yet due to an issue with the derived eml form in some mirrored cases.