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

31–40 of 125 posts

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

#31

Post by reikonomusha »

teo_zero wrote: post #27
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…

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.

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?

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

#32

Post by reikonomusha »

tliltocatl wrote: post #30
Aardwolf wrote: post #23

Earlier quoted context omitted.

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.

Wikipedia says:

> More generally, in modern mathematics, elementary functions comprise the set of functions previously enumerated, all algebraic functions (not often encountered by beginners), and all functions obtained by roots of a polynomial whose coefficients are elementary. [...] This list of elementary functions was originally set forth by Joseph Liouville in 1833.

which seems to be what the blog post references.

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

#33

Post by lotaezenwa »

reikonomusha wrote: post #15
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 di…

Cool explanation, thanks!

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

#34

Post by burnished »

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…

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

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

#35

Post by reikonomusha »

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…

Arnold (as reported by Goldmakher [1]) does prove the unsolvability of the quintic in finite terms of arithmetic and single-valued continuous functions (which does not include the complex logarithm). TFA's result is stronger, which is something about the solvability of the monodromy groups of all EML-derived functions. So it doesn't seem to be a "rehash", even if their specific counterexample could have been achieved either in fewer steps or with less machinery.

[1] https://web.williams.edu/Mathematics/lg5/394/ArnoldQuintic.p...

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

#36

Post by DoctorOetker »

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…

:)

I still consider the article important, as it demonstrates techniques to conduct searches, and emphasizes the very early stage of the research (establishes non-uniqueness for example), openly wonders which other binary operators exist and which would have more desirable properties, etc.

Sometimes articles are important not for their immediate result, but for the tools and techniques developed to solve (often artificial or constrained) problems. The history of mathematics is filled with mathematicians studying at-the-time-rather-useless-constructions which centuries or millennia later become profound to human interaction. Think of the "value" of Euclid's greatest common divisor algorithm. What starts out as a curiosity with 0 immediate relevance for society, is now routinely used by everyone who enjoys the world wide web without their government or others MitM'ing a webpage.

If the result was the main claimed importance for the article, there would be more emphasis on it than on the methodology used to find and verify candidates, but the emphasis throughout the article is on the methodology.

It is far from obvious that the tricks used would have converged at all. Before this result, a lot of people would have been skeptical that it is even possible to do search candidates this way. While the gradual early-out tightening in verification could speed up the results, many might have argued that the approach to be used doesn't contain an assurance that the false positive rate wouldn't be excessively high (i.e. many would have said "verifying candidates does not ensure finding a solution, reality may turn out that 99.99999999999999999% of candidates turn out not to pass deeper inspection").

It is certainly noteworthy to publish these results as they establish the machinery for automated search of such operations.

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

#37

Post by [deleted] »

AlotOfReading wrote: post #6
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 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.

[deleted]

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

#38

Post by reikonomusha »

vintermann wrote: post #26
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 implem…

You are correct, it is undecidable by Richardson's theorem [1].

[1] https://en.wikipedia.org/wiki/Richardson%27s_theorem

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

#39

Post by kqr »

derriz wrote: post #29

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

This is similar to the idea of generating functions, if you would like more to read!

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

#40

Post by TeMPOraL »

burnished wrote: post #34
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…

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

Introduction to ...
Post reply on HN