6 ms·
Not all elementary functions can be expressed with exp-minus-log
- lotaezenwa 6mo agoThe 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.
- DevelopingElk 6mo agoHis 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 6mo agoThe 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 6mo agoWell 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.
- reikonomusha 6mo agoCombinations 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.
- meindnoch 6mo agoSolving polynomials over finite fields is trivial. Just try all combinations.
- eru 6mo agoYou probably want a fast algorithm. Compare https://arxiv.org/abs/1108.1791 https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.
- bawolff 6mo agoSure, i guess i should have said something like with a polynomial circuit size or something. However by the same token couldn't you use the same brute force approach with exp minus log? What im really asking, are NAND gates really different here?
- zeroonetwothree 6mo agoHow can you brute force real numbers?
- bawolff 6mo agoI meant for finite fields like the person i was responding to said.
- zeroonetwothree 6mo agoYes, 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.
- petters 6mo agoYes, that blog post could have been much shorter….
- AlotOfReading 6mo agoThe 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 6mo ago[deleted]
- deleted 6mo ago[deleted]
- markgall 6mo agoCan 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 6mo agoIt'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 https://news.ycombinator.com/item?id=47746610 [2] https://www.reddit.com/r/math/comments/1sk63n5/all_elementary_functions_from_a_single_binary/ https://www.reddit.com/r/math/comments/1sk63n5/all_elementar...
- renewiltord 6mo agoThis 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 https://news.ycombinator.com/item?id=47775105
- seanhunter 6mo agoWhy on earth would it upend all of mathematics? Secondly, even if it did that, why would that be concerning for mathematics?
- renewiltord 6mo ago
- reikonomusha 6mo ago"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).
- lotaezenwa 6mo agoCool explanation, thanks!
- cyberax 6mo agoBring radicals are just cheating. You can't solve an equation? Why not just introduce a function that is equal to the solution of the equation! Problem solved.
- reikonomusha 6mo agoThis fundamental "cheat" gave rise to some of the most important pure and applied mathematics known. Can't solve the differential equation x^2 - a = 0? Why not just introduce a function sqrt(a) as its solution! Problem solved. Can't solve the differential equation y'' = -y? Why not just introduce a function sin(x) as its solution! Problem solved. A lot of 19th century mathematics was essentially this: discover which equations had solutions in terms of things we already knew about, and if they didn't and it seemed important or interesting enough, make a new name. This is the whole field of so-called "special functions". It's where we also get the elliptic functions, Bessel functions, etc. The definition of "elementary function" comes exactly from this line in inquiry: define a set of functions we think are nice and algebraically tractable, and answer what we can express with them. The biggest classical question was: Do integrals of elementary functions give us elementary functions? The answer is "no" and Liouville gave us a result which tells us what the answer does look like when the result is elementary. Risch gave us an algorithm to compute the answer, when it exists in elementary form.
- saithound 6mo agoThe 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 6mo agoYes, 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.
- reikonomusha 6mo agoYou are correct, it is undecidable by Richardson's theorem [1]. [1] https://en.wikipedia.org/wiki/Richardson%27s_theorem https://en.wikipedia.org/wiki/Richardson%27s_theorem
- DoctorOetker 6mo agothat result does not apply for EML: EML doesn't have the | . | absolute value function, a prerequisite for Richardson's theorem.
- vintermann 6mo agoIf I understand the page correctly, the extension by Miklós Laczkovich should be enough to show that it's undecidable.
- avmich 6mo agoI'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.
- deleted 6mo ago[deleted]
- markgall 6mo agoI 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.
- avmich 6mo agoI'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 6mo agoBut 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
- bawolff 6mo 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.
- deleted 6mo ago[deleted]
- js8 6mo agoI 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.
- reikonomusha 6mo agoIt 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 https://en.wikipedia.org/wiki/Hilbert%27s_thirteenth_problem
- js8 6mo agoThanks, actually https://en.wikipedia.org/wiki/Elementary_function 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.
- NetMageSCW 6mo agoElementary function is also a general English phrase that can very much be used to represent the functions on a scientific calculator.
- SabrinaJewson 6mo agoRelated 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 https://en.wikipedia.org/wiki/Schanuel%27s_conjecture What is a closed-form number?: http://timothychow.net/closedform.pdf http://timothychow.net/closedform.pdf omega constant: https://en.wikipedia.org/wiki/Omega_constant https://en.wikipedia.org/wiki/Omega_constant
- DoctorOetker 6mo ago1) > 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. is that a typo / accidental mis-phrasing? exp-minus-log construction is closed for the operations it supports, and spans both exp and log, so E must be either identical to or a subset of exp-minus-log; not the other way around. 2) EML is spanned by a single binary operator, while the article you reference describing ("what is a closed-form number") just tacitly assumes +, -, x, / are available for free, so even in just this sense the EML construction is superior. Since EML can construct the larger presumed basic operations of E, E must be contained in it, but since the E implicitly has +, - besides exp(x) and ln(x) the reverse can also be said, so the sets and functions spanned by E and EML should be equivalent. So what is novel? precisely what the recent article describes: all the tacitly (+,-,x,/) and explicitly assumed (exp and ln) operations can be spanned with just 1 (non-unique) binary operation; and on top of that: 3) the recent article describes freely available code to conduct such searches and find alternative binary operations, search for functions or constants. The EML paper provides code and machinery to conduct a search for the value x in exp(-x)=x : use a multiprecision library to get an arbitrarily precise representation, and search for some EML expression to find candidates.
- zarzavat 6mo agoThis 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 6mo agoIf this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.
- rnhmjoj 6mo 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.
- reikonomusha 6mo agoThe 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/math4010-spring2016-differential_algebra.pdf 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.
- thaumasiotes 6mo ago> See e.g. Page 2 and the following example of https://billcookmath.com/courses/math4010-spring2016/math4010-spring2016-differential_algebra.pdf https://billcookmath.com/courses/math4010-spring2016/math401... (2016) There appears to be a typo in that example; I assume "Essentially elementary functions are the functions that can be built from ℂ and f(x) = x" should say something more like "the functions that can be built from ℂ and f(x) = y".
- reikonomusha 6mo ago
- derriz 6mo agoWhen 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).
- kqr 6mo agoThis is similar to the idea of generating functions, if you would like more to read!
- eru 6mo agoYou might like https://www2.math.upenn.edu/~wilf/gfology2.pdf https://www2.math.upenn.edu/~wilf/gfology2.pdf
- cyberax 6mo agoWhy would it be surprising? And if you want something truly surprising, Riemann's zeta function can approximate any holomorphic function arbitrarily well on the critical strip. So technically you need only _one_ argument.
- derriz 6mo ago> Why would it be surprising? Because I don’t know as much mathematics as you.
- adrian_b 6mo agoWhen you may use functions of 3 or more arguments, it becomes trivial to find a single function that can be used to express large classes of other functions. These tricks break when you are restricted to use one binary function, like in the EML paper. The second argument cannot be used as a selector, because you cannot make binary functions from unary functions (while from binary functions you can make functions with an arbitrary number of parameters, by composing them in a tree). If you used an argument as a function selector in a binary function, which transforms the binary function into a family of unary functions, then you would need at least one other auxiliary binary function, to be able to make functions with more than one parameter. The auxiliary binary function could be something like addition or subtraction, or at the minimum a function that makes a tuple from its arguments, like the function CONS of LISP I. The EML paper can also be understood that the elementary functions as defined by it can be expressed using a small family of unary functions (exponential, logarithmic and negation), together with one binary function: addition. Then this set of 4 simple functions is reduced to one complex function, which can regenerate any of those 4 functions by composition with itself. This is the same trick used to reduce the set of 2 simple functions, AND & NOT, which are sufficient to write any logical function, to a single function, NAND, which can generate both simpler functions.
- aixpert 6mo agotangenially it would be interesting to analyze what infinite structures can be represented with infinite EML trees
- throwaway81523 6mo agoIt'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.
- traes 6mo agoabs(x) = sqrt(x*x), no?
- throwaway81523 6mo agoI think the issue might be the branch cut in the sqrt function. Per the wiki article, elementary functions have to be differentiable in the complex plane at all but a finite number of points.
- gus_massa 6mo agoThe origianl article use complex numbers, in particular to get sin and cos from eml: > e^{iφ} = cosφ + i sin φ So x may be a complex number and sqrt(x*x) is a complex number that sometimes is equal to x and sometimes to -x depending on how lucky you were selecting the branches of sqrt.
- reikonomusha 6mo agoEML 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. :)
- ogogmad 6mo agoOn 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.
- cubefox 6mo agoWhere would EML expressions sit in this fascinating table? https://en.wikipedia.org/wiki/Template:Mathematical_expressions https://en.wikipedia.org/wiki/Template:Mathematical_expressi...
- arowthway 6mo agoClosed-form expressions, I guess? "For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions."
- cubefox 6mo agoMaybe I'm misunderstanding, but the table says that the "root of a polynomial that is not an algebraic solution" doesn't count as closed-form.
- arowthway 6mo agohttps://en.wikipedia.org/wiki/Closed-form_expression https://en.wikipedia.org/wiki/Closed-form_expression "Commonly, the basic functions that are allowed in closed forms are nth root, exponential function, logarithm, and trigonometric functions.[a] However, the set of basic functions depends on the context. For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions." It's only maths, don't expect things to be so black and white.
- shiandow 6mo agoThat's a kind of weak criticism. What functions are considered elementary was always going to be arbitrary, picking the set you can generate from exp, log, and some complex algebra is not the worst choice. If nothing else you could solve simple differential equations with them. And it gives you the 'power' function. The very fact that the set of functions is largely arbitrary is a much bigger issue. Or at least it limits the use of the fact that you can represent those functions. Edit: I feel the need to add that just because it is a weak critique doesn't mean the argument itself is not interesting.
- timschmidt 6mo agoCodex and I whipped this up based on the paper: https://github.com/timschmidt/emlmath https://github.com/timschmidt/emlmath Tests for the trig functions aren't passing yet due to an issue with the derived eml form in some mirrored cases.
- randomtoast 6mo ago[dead]
- dukezzz 6mo agoHow can an edit possibly be made on April 16 when today is the 15th?
- mmarx 6mo agoIt's already past midnight in New Zealand, e.g.
- empath75 6mo agoI wish i had seen this a few days ago i spent days on this before arriving at the following: It’s completely wrong, for multiple reasons. First, and immediately, none of the derived total functions are the functions they appear to be, because they are all partial functions. Worse than that the domain over which these trees are defined is undecidable by Richardson. You can encode Hilbert’s 10th with elementary functions. Which means you can’t algorithmically decide if a tree evaluates to zero so you never know if ln(y) is undefined So the central claim is done right off the bat. Secondly and probably more importantly, these trees have exponential blow up problems because even fairly shallow trees involve tetrations of e that don’t cancel. Even in float64 you can‘t add 800+800 without overflow. Clamping it just gives you wrong answers and clamped exp A) isn’t elementary and B) gives bounded growth so can’t generate all elementary functions. The consequences for his claimed practical application is disastrous. the loss function is NaN everywhere once you get to around depth 6 in his trees. If you clamp it you just get a flat plateau. Even if you had infinite precision the gradient would be unusable and wouldn’t converge. As a second note, he frequently in the paper talks about using positive reals as inputs. First, positive reals aren’t even part of his generating set (and if they are his whole central claim is wrong, it has uncountably many constants), but even if they are, fundamentally his operations are complex, and you have subtraction so it is not hard to construct trees that should be total but which never the less are undefined at undecideably many points. Using extended reals doesn’t save it either. There are just different undefined values that lead to undecideability. None of these arguments are really specific to EML either. Any binary operator that hopes to generate elementary functions must include exp and ln, must be partial and must be able to encode hilbert’s 10th. There is no fix for this. You might ask why his tests didn’t find any of this but if you look at his code, they do. He just carefully restricts them to a narrow domain where they happen to work and even then he does things like drop imaginary components and filters out undefined results. He doesn‘t even really hide this in the paper, he just dismisses them as implementation details that can be fixed but the problems are structural So what we are left with is a generator that can generate exp(x) cleanly and essentially nothing else.