Not all elementary functions can be expressed with exp-minus-log • Hacker News Board

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

#111

Post by rnhmjoj » Wed, Apr 15, 2026, 5:26 PM UTC

rnhmjoj wrote: post #103

SideQuark wrote: post #88

Earlier quoted context omitted.

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

I guess you're right, I was probably mislead this whole time. I went through my old analysis class book [1] and there doesn't seem to be an explicit definition of elementary functions. The best I can find is this paragraph (I translate from italian): > The elementary functions of analysis, that is powers, roots, exponentials, logarithms and their inverses, functions obtained from the former by arithmetic operations o…

So, I did a bit of research and I wasn't going crazy: there are apparently two competing definitions of "elementary" in use [1]:

> the class of functions [...] is what I would call exponential-logarithmic functions or EL functions; that is, they are the functions that can be expressed using some finite combination of constant functions, the identity function, exp, log, composition, and arithmetic operations (+−×÷). Some authors call this class of functions elementary functions, but that term is now more commonly used in a different sense, which includes algebraic functions.

Evidently my professor was in the exponential-logarithmic camp.

[1]: https://mathoverflow.net/a/442656

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

#112

Post by renewiltord » Wed, Apr 15, 2026, 5:44 PM UTC

seanhunter wrote: post #105

renewiltord wrote: post #21

Earlier quoted context omitted.

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

Why on earth would it upend all of mathematics? Secondly, even if it did that, why would that be concerning for mathematics?

Yes or no, it's too early to tell.

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

#113

Post by vintermann » Wed, Apr 15, 2026, 6:02 PM UTC

DoctorOetker wrote: post #102

vintermann wrote: post #101

Earlier quoted context omitted.

If I understand the page correctly, the extension by Miklós Laczkovich should be enough to show that it's undecidable.

You wrote: > 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. Perhaps, perhaps not, same function so basically is this question solvable: A(x[,y,...]) = f(x[,y,...])-g(x[,y,...]) == 0 everywhere? if a user brings EML functions f and g; given their binary EML trees; can we decide if they represent the same function, so…

> an expression in the ring generated by the integers, x, sin xn, and sin(x sin xn)

We can always write AML trees for expressions generated by the integers, x, sin xn, and sin(x sin xn), right?

So we should be able to write EML trees for any two such expressions, A and B. If they're equal everywhere, then A - B = 0 everywhere. A - B is also in the aforementioned ring.

If there was a decision procedure always to determine if EML trees represent the same function, then that contradicts Miklós Laczkovich's extension, right?

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

#114

Post by [deleted] » Wed, Apr 15, 2026, 7:53 PM UTC

saithound wrote: post #106

DoctorOetker wrote: post #76

Earlier quoted context omitted.

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

Questions which have never been asked or answered before, but to which practitioners have immediately obvious answers, are dime a dozen in mathematics. 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…

[deleted]

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

#115

Post by floxy » Wed, Apr 15, 2026, 7:56 PM UTC

zeroonetwothree wrote: post #97

bawolff wrote: post #18

Earlier quoted context omitted.

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.

Yes, NAND gates can implement root finding algorithms for arbitrary polynomials. For example a variant of Newton’s method can be used (there are also better algorithms for circuits specifically). This can be done in polynomial time as well. This is fairly obvious if you think about that your computer can do the same thing and it’s just a fancy circuit.

Surely you can use EML to do root finding approximations also.

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

#116

Post by DoctorOetker » Wed, Apr 15, 2026, 8:20 PM UTC

vintermann wrote: post #113

DoctorOetker wrote: post #102

Earlier quoted context omitted.

You wrote: > 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. Perhaps, perhaps not, same function so basically is this question solvable: A(x[,y,...]) = f(x[,y,...])-g(x[,y,...]) == 0 everywhere? if a user brings EML functions f and g; given their binary EML trees; can we decide if they represent the same function, so…

> an expression in the ring generated by the integers, x, sin xn, and sin(x sin xn) We can always write AML trees for expressions generated by the integers, x, sin xn, and sin(x sin xn), right? So we should be able to write EML trees for any two such expressions, A and B. If they're equal everywhere, then A - B = 0 everywhere. A - B is also in the aforementioned ring. If there was a decision procedure always to deter…

no Miklós Laczkovich's extension as described on wikipedia only says that both of the following questions are proven undecidable:

1) is there some value x such that some function F(x)=A(x)-B(x)=0?

2) is there some value x such that F(x)>0?

while you asked:

> I'm pretty sure it's not decidable if two EML trees describe the same function.

that would be

3) is for every x F(x)=A(x)-B(x)==0?

which Miklós Laczkovich's extension does not provide.

And you ignore the fact that Miklós Laczkovich's extension applies to real numbers and functions...

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

#117

Post by js8 » Thu, Apr 16, 2026, 2:37 AM UTC

reikonomusha wrote: post #80

js8 wrote: post #44

Earlier quoted context omitted.

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.

It is not known, and the model problem for this is Hilbert's 13th [1]. 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

Thanks, actually https://en.wikipedia.org/wiki/Elementary_function confirms your claim.

Nevertheless, it is a horrible definition. Mathematicians have often taken care to define things as close to everyday intuition as they could (and then proving an equivalence). The "elementary function" in this definition is just a weird mix of concerns.

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

#118

Post by vintermann » Thu, Apr 16, 2026, 4:55 AM UTC

DoctorOetker wrote: post #116

vintermann wrote: post #113

Earlier quoted context omitted.

> an expression in the ring generated by the integers, x, sin xn, and sin(x sin xn) We can always write AML trees for expressions generated by the integers, x, sin xn, and sin(x sin xn), right? So we should be able to write EML trees for any two such expressions, A and B. If they're equal everywhere, then A - B = 0 everywhere. A - B is also in the aforementioned ring. If there was a decision procedure always to deter…

no Miklós Laczkovich's extension as described on wikipedia only says that both of the following questions are proven undecidable: 1) is there some value x such that some function F(x)=A(x)-B(x)=0? 2) is there some value x such that F(x)>0? while you asked: > I'm pretty sure it's not decidable if two EML trees describe the same function. that would be 3) is for every x F(x)=A(x)-B(x)==0? which Miklós Laczkovich's exte…

If it's undecidable whether it's 0 at even ONE point, clearly you can't prove that it's 0 everywhere.

Likewise, if it's not decidable for real-valued functions, clearly it's not decidable for complex valued functions.

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

#119

Post by throwaway81523 » Thu, Apr 16, 2026, 4:55 AM UTC

reikonomusha wrote: post #52

throwaway81523 wrote: post #48

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 wonde…

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(-∞)…

It's ok for elementary functions to have singularities, like 1/x at x=0. But I'm not sure what happens with your version of abs, since the log function has branches. log(1) is any of 0, 2*pi*i, 4*pi*i, etc.

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

#120

Post by DoctorOetker » Thu, Apr 16, 2026, 12:16 PM UTC

vintermann wrote: post #118

DoctorOetker wrote: post #116

Earlier quoted context omitted.

no Miklós Laczkovich's extension as described on wikipedia only says that both of the following questions are proven undecidable: 1) is there some value x such that some function F(x)=A(x)-B(x)=0? 2) is there some value x such that F(x)>0? while you asked: > I'm pretty sure it's not decidable if two EML trees describe the same function. that would be 3) is for every x F(x)=A(x)-B(x)==0? which Miklós Laczkovich's exte…

If it's undecidable whether it's 0 at even ONE point, clearly you can't prove that it's 0 everywhere. Likewise, if it's not decidable for real-valued functions, clearly it's not decidable for complex valued functions.

thats not how this works

decidability does not distribute over pointwise question asking on sets, or if you believe it does, show us the proof.

Telling if an EML(x,y),1 constructed expression is identically 0 is in the gray zone, as far as I can tell, it has neither been proven decidable nor been proven undecidable.

Nevertheless regardless of decidability the authors clearly show the multipoint sampling/testing is a decent filter, and the shorter resulting expressions have been proven correct in the results for the construction at least.