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

61–70 of 125 posts

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

#61

Post by thaumasiotes »

reikonomusha wrote: post #25
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/math40…

> See e.g. Page 2 and the following example of 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".

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

#62

Post by cyberax »

reikonomusha wrote: post #47
cyberax wrote: post #45

Earlier quoted context omitted.

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

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.

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

#63

Post by adrian_b »

mcmoor wrote: post #50
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…

I don't know if I read this right, but I thought it's proven that "elementary functions" can't solve 5th degree or higher polynomial, so I'm confused how it's interpreted if elementary functions also include arbitrary polynomial roots. Or is it different elementary functions?

That theorem is not formulated about "elementary functions".

It says that polynomial equations of the 5th degrees or higher cannot, in general, be solved using "radicals".

While something like "polynomials" or "radicals" has a clear meaning, which are the "elementary functions" is a matter of convention.

The usual convention is to include all algebraic functions and a few selected transcendental functions.

In "all algebraic functions", are included the rational functions, the radicals and the functions that compute solutions of arbitrary polynomial equations.

Some conventions used for "elementary functions" describe the expressions that you can use to write such "elementary functions", in which case not all algebraic functions are included, but only those written by combining rational functions with radicals.

For an algebraic function that computes a solution of a general polynomial equation, which cannot be expressed with radicals, you cannot write an explicit formula, but you can write the function only implicitly, by writing the corresponding polynomial equation.

So the difference between the 2 kinds of conventions about which are "the elementary functions" is usually based on whether only explicitly-written functions are considered, or also implicit functions.

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

#64

Post by quchen »

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.

Algebraic too.

There's also the opposite in physics though, "modern" means from the 60s with square roots drawn in manually.

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

#65

Post by thaumasiotes »

reikonomusha wrote: post #47
cyberax wrote: post #45

Earlier quoted context omitted.

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

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

Heck, you can tell this just by looking at the names of the functions you mentioned. "Sine" is called "sine", which appears to have originated as an attempted calque of a Sanskrit term (referring to the same function) meaning "bowstring".

"Square root" is named after the squaring function that was used to define it.

Introducing an answer-by-definition gives us negative numbers, rational numbers, imaginary numbers, and nth roots... but not sines, come on. You can just measure sines.

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

#66

Post by eru »

kqr wrote: post #39
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!

You might like https://www2.math.upenn.edu/~wilf/gfology2.pdf

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

#67

Post by reikonomusha »

mr_mitm wrote: post #58
TeMPOraL wrote: post #56

Earlier quoted context omitted.

No. It's code for the thickest, densest book on the subject that you're ever gonna not read, as it actually assumes you're experienced in the subject and goes into everything except intro level topics. See e.g. Petzold, et al.

I'm getting flashbacks to Spivak, who wrote a 2000 page "introduction" to differential geometry.

To be fair to Spivak, he did say it was comprehensive introduction. :)

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

#68

Post by eru »

reikonomusha wrote: post #47
cyberax wrote: post #45

Earlier quoted context omitted.

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

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…

That's one way to get at complex numbers and the sine function. But it's not the only one.

Eg you can get complex numbers from matrices.

But if you want to go in your direction: you can say we get fractions and negative numbers this way.

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

#69

Post by eru »

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.

You probably want a fast algorithm.

Compare https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.

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

#70

Post by reikonomusha »

thaumasiotes wrote: post #61
reikonomusha wrote: post #25

Earlier quoted context omitted.

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/math40…

> See e.g. Page 2 and the following example of 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".

Not a typo! Think of f(x) = x as a seed function that can be used to build other functions. It's one way to avoid talking about "variables" as a "data type" and just keep everything about functions. We can make a function like x + x*exp(log(x)) by "formally" writing

    f + f*(exp∘log)
where + and * are understood to produce new functions. Sort of Haskell-y.
Post reply on HN