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

mmmastrac about 6 hours ago 48 commentsRead Article on stylewarning.com

DE version is available. Content is displayed in original English for accuracy.

⚡ Community Insights

Discussion Sentiment

83% Positive

Analyzed from 1734 words in the discussion.

Discussion (48 Comments)Read Original on HackerNews

rnhmjoj•about 2 hours ago

> My concern is that the word “elementary” in the title carries a much broader meaning in standard mathematical usage, and in this meaning, the paper’s title does not hold.

> 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.

burnished•about 1 hour ago

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

reikonomusha•about 2 hours ago

The definition of "elementary function" typically includes functions which solve polynomials, like the Bring radical. The definition is most fitting in algebraic contexts where algebraic structure is meaningful (like Liouvillian structure theorems). 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.

SabrinaJewson•about 2 hours ago

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.

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

saithound•about 3 hours ago

The original article explicitly acknowledged this limitation, that while in "the classical differential-algebraic setting, one often works with a broader notion of elementary function, defined relative to a chosen field of constants and allowing algebraic adjunctions, i.e., adjoining roots of polynomial equations," the author works with the less general definition.

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.

vintermann•about 2 hours ago

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.

derriz•about 2 hours ago

When I first read the exp-minus-log paper, I found it extremely surprising - even shocking that such a function could exist.

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).

throwaway81523•28 minutes ago

It's news to me that "elementary functions" include roots of arbitrary polynomials, but the wiki article in fact says that they're included at least some of the time. I remember reading about the Risch algorithm (for finding closed form antiderivatives) a long time ago and elementary functions were just the ordinary ones found on calculators.

Interestingly, the abs (absolute value) function is non-elementary. I wonder if exp-minus-log can represent it.

reikonomusha•18 minutes ago

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. :)

traes•20 minutes ago

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

lotaezenwa•about 3 hours ago

The author essentially says that the quintic has no closed form solution which is true regardless of the exp-minus-log function. The purpose of this blog post is lost on me.

Can anyone please explain this further? It seems like he’s moving the goalposts.

reikonomusha•about 2 hours ago

"The quintic has no closed form solution" is a theorem that is more precisely stated 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 the Bring radical. The post's argument different than the usual Galois theory result about the unsolvability of the quintic, in that it shows that even with a transcendental function like EML(x, y), we still don't get a solution.

lotaezenwa•about 1 hour ago

Cool explanation, thanks!

markgall•about 3 hours ago

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...

saithound•about 2 hours ago

It's a fun, but unsurprising undergrad-level result. It got picked up and overhyped on HN [1] and /r/math [2] earlier this week.

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...

renewiltord•about 2 hours ago

This result itself is being described in those terms[1]:

> If this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.

This is very concerning for mathematics in general.

1: https://news.ycombinator.com/item?id=47775105

AlotOfReading•about 3 hours ago

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.

DevelopingElk•about 3 hours ago

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".

throwanem•about 2 hours ago

The author discusses this in his third paragraph, and states explicitly in his fourth that he considers the result faulty for its unrealistically narrow definition of elementarity.

(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.)

bawolff•about 2 hours ago

Well the author saysin that paragraph:

> 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.

But is there actually a combination of NANDs that find the roots of an arbitrary quintic? I always thought the answer was no but admittedly this is above my math level.

petters•about 3 hours ago

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

bawolff•about 2 hours ago

> Elementary functions typically include arbitrary polynomial roots

Admittedly this may be above my math level, but this just seems like a bad definition of elementary functions, given the context.

cubefox•17 minutes ago

Where would EML expressions sit in this fascinating table?

https://en.wikipedia.org/wiki/Template:Mathematical_expressi...

avmich•about 3 hours ago

I'd really like more details on the terminology used.

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.

markgall•about 2 hours ago

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.

teo_zero•about 2 hours ago

I feel that saying that EML can't generate all the elementary functions because it can't express the solution of the quintic is like saying that NAND gates can't be the basis of modern computing because they can't be used to solve Turing's halting problem.

reikonomusha•about 2 hours ago

As is usual with these kinds of "structure theorems" (as they're often called), we need to precisely define what set of things we seek to express.

A function which solves a quintic is reasonably ordinary. We can readily compute it to arbitrary precision using any number of methods, just as we can do with square roots or cosines. Not just the quintic, but any polynomial with rational coefficients can be solved. But the solutions can't be expressed with a finite number of draws from a small repertoire of functions like {+, -, *, /}.

So the question is, does admitting a new function into our "repertoire" allow us to express new things? That's what a structure theorem might tell us.

The blog post is exploring this question: Does a repertoire of just the EML function, which has been shown by the original author to be able to express a great variety of functions (like + or cosine or ...) also allow us to express polynomial roots?

avmich•about 2 hours ago

I've thought something like that, but I'm interested more in details of the argument.

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.

Aardwolf•about 2 hours ago

But can you even express this function with the elementary operator symbols, exp, log, power and trig functions? It seems to me like no, you can't express "largest real solution" with those (and what's the intended result for complex inputs?)

At least eml can express the quintic itself, just like the above mentioned operators can

tliltocatl•about 2 hours ago

Author and EML are using different definitions of elementary functions, EML's definition being the school textbooks' one (polynomials, sin, exp, log, arcsin, arctan, closed under multiplication, division and composition). The author's definition I've never met before, it apparently includes some multi-valued functions, which are quite unusual.

aixpert•about 1 hour ago

tangenially it would be interesting to analyze what infinite structures can be represented with infinite EML trees

ogogmad•25 minutes ago

On a tangent: I've tried to connect Euclid's Elements with quantifier elimination theorems. It looks like most of the geometry follows from QE of real-closed fields. Some of the number theory relates to Presburger arithmetic. Some other number theory, including the irrationality of sqrt(2), is down to Skolem. The Pythagorean triples relate to extending Skolem to the Gaussian integers. I suspect some of the "embryonic" integral calculus could be related to holonomic functions, which seem like they admit a form of QE.

Don't have anything for the perfect numbers though.

zarzavat•about 2 hours ago

This is a bit like invalidating a result based on 0^0 := 1 because you work in a field of mathematics where 0^0 is an indeterminate form. Not very interesting.

AFAIU the original paper is a result in the field of symbolic regression. What definition of elementary function do they use?

renewiltord•about 2 hours ago

If this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.