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

21–30 of 125 posts

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

#21

Post by renewiltord »

saithound wrote: post #14
markgall wrote: post #9

Earlier quoted context omitted.

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…

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

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

#22

Post by avmich »

markgall wrote: post #11
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 usi…

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.

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

#23

Post by Aardwolf »

markgall wrote: post #11
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 usi…

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

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

#24

Post by rnhmjoj »

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

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

#25

Post by reikonomusha »

rnhmjoj wrote: post #24

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

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.

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

#26

Post by vintermann »

saithound wrote: post #5

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

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.

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

#27

Post by teo_zero »

markgall wrote: post #11
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 usi…

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.

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

#28

Post by reikonomusha »

bawolff wrote: post #18
throwanem wrote: post #12

Earlier quoted context omitted.

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.

Combinations of the NAND gate can express any Boolean function. The Toffoli (CCNOT) or Fredkin (CSWAP) can express any reversible Boolean function, which is important in quantum computing where all gates must be unitary (and therefore reversible). The posited analog is that EML would be the "universal operator" for continuous functions.

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

#29

Post by derriz »

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

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

#30

Post by tliltocatl »

Aardwolf wrote: post #23
markgall wrote: post #11

Earlier quoted context omitted.

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

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

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.
Post reply on HN