[dead]
Not all elementary functions can be expressed with exp-minus-log
91–100 of 125 posts
Re: Not all elementary functions can be expressed with exp-minus-log
#92Earlier quoted context omitted.
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 al…
So the argument of the post is basically “this definition of elementary functions includes functions without closed form expression, and thus we cannot express these elementary functions with eml”, or sth more (that there exist elementary functions with closed form expressions that cannot be expressed by eml)?
FWIW I never thought that functions without closed form expressions were considered elementary functions, but i guess one could choose to allow this if they wanted
Re: Not all elementary functions can be expressed with exp-minus-log
#93> 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…
> The definition of "elementary function" typically includes functions which solve polynomials, like the Bring radical.
What. Does that "typical definition" of elementary function includes elliptic functions as well, by any chance?
Re: Not all elementary functions can be expressed with exp-minus-log
#94The 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…
> It's decidable whether two NAND circuits implement the same function
Well, sure. At least, until you have a loop that starts clocking for you, and now you've got the halting problem.
Re: Not all elementary functions can be expressed with exp-minus-log
#95The 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…
Upvoted back to not-greyed-out. You must have struck a nerve.
Re: Not all elementary functions can be expressed with exp-minus-log
#96How can an edit possibly be made on April 16 when today is the 15th?
Re: Not all elementary functions can be expressed with exp-minus-log
#97Earlier 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.
Yes, 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.
Re: Not all elementary functions can be expressed with exp-minus-log
#98How can an edit possibly be made on April 16 when today is the 15th?
It's already past midnight in New Zealand, e.g.
Re: Not all elementary functions can be expressed with exp-minus-log
#99Earlier quoted context omitted.
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?
How can you brute force real numbers?
Re: Not all elementary functions can be expressed with exp-minus-log
#100Earlier 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.
That’s a poor analogy because all polynomials can be solved to arbitrary precision with efficient algorithms.