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

71–80 of 125 posts

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

#71

Post by adrian_b »

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…

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

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

#72

Post by throwaway81523 »

traes wrote: post #51
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…

abs(x) = sqrt(x*x), no?

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

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

#73

Post by reikonomusha »

cyberax wrote: post #62
reikonomusha wrote: post #47

Earlier quoted context omitted.

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

Sure. But the square root and the sine function also have nice geometric interpretations. Bring radicals don't. They're just defined as a solution to this particular quintic. Kinda the similar story with the Lambert function.

The Bring radical has a great geometric interpretation: BR(a) is where the curve x^5 + x + a crosses the x axis.

Like sine or exp, it also has a nice series representation:

    sum(k = 0 to inf) binom(5k,k) (-1)^(k+1) a^(4k+1) / (4k+1)
We can compute its digits with the very rapidly convergent Newton iteration

    x
and so on.

Why not invite it to the table of functions?

Ellipses are simple and beautiful figures known to every child, but why do we rarely invite the elliptic integrals to the table too?

I guess my point is that "nice geometric interpretation" is a little subjective and hasn't led to much consistency in our choice of which functions are popular or obscure.

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

#74

Post by DoctorOetker »

SabrinaJewson wrote: post #16

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

1)

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

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

#75

Post by bawolff »

meindnoch wrote: post #57
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.

Solving polynomials over finite fields is trivial. Just try all combinations.

Sure, 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?

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

#76

Post by DoctorOetker »

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…

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

(in other news: I can spontaneously levitate, I just don't feel like demonstrating it to you right now...)

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

#77

Post by reikonomusha »

thaumasiotes wrote: post #65
reikonomusha wrote: post #47

Earlier quoted context omitted.

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

> This fundamental "cheat" gave rise to some of the most important pure and applied mathematics known. > Can't solve the differential equation y'' = -y? Why not just introduce a function sin(x) as its solution! Problem solved. But that's not how sine was introduced. It's been around since classical geometry. It was always easy to solve the differential equation y'' = -y, because the sine had that property, and we kne…

You can calculate, measure, draw, construct, write a power series for, express as hypergeometric function, etc. the Bring radical too.

All of these concepts, from sine to real numbers, Bring radicals to complex exponentials, can all be defined in different, equivalent ways. What is interesting are the properties invariant to these definitions.

It still doesn't seem to me that a square root should be any more or less contrived than a Bring radical. Maybe we should call it a ultraradical instead?

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

#78

Post by xigoi »

DoctorOetker wrote: post #74
SabrinaJewson wrote: post #16

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

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

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

Since E is by definition closed under exp, log and subtraction, it is clearly also closed under EML.

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

#79

Post by shiandow »

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

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

#80

Post by reikonomusha »

js8 wrote: post #44
bawolff wrote: post #13

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

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

Post reply on HN