Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

stylewarning.com

Post reply on HN
Print view View original

11–20 of 125 posts

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

#11

Post by markgall »

avmich wrote: post #8

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.

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.

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

#12

Post by throwanem »

DevelopingElk wrote: post #3
lotaezenwa wrote: post #2

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.

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

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

#14

Post by saithound »

markgall wrote: post #9
lotaezenwa wrote: post #2

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.

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…

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

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

#15

Post by reikonomusha »

lotaezenwa wrote: post #2

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.

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

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

#16

Post by SabrinaJewson »

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

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

#17

Post by zarzavat »

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?

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

#18

Post by bawolff »

throwanem wrote: post #12
DevelopingElk wrote: post #3

Earlier quoted context omitted.

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

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.

Post reply on HN