101–110 of 125 posts
Earlier quoted context omitted.
You are correct, it is undecidable by Richardson's theorem [1]. [1] https://en.wikipedia.org/wiki/Richardson%27s_theorem
that result does not apply for EML: EML doesn't have the | . | absolute value function, a prerequisite for Richardson's theorem.
Earlier quoted context omitted.
that result does not apply for EML: EML doesn't have the | . | absolute value function, a prerequisite for Richardson's theorem.
If I understand the page correctly, the extension by Miklós Laczkovich should be enough to show that it's undecidable.
> 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.
Perhaps, perhaps not, same function so basically is this question solvable:
A(x[,y,...]) = f(x[,y,...])-g(x[,y,...]) == 0 everywhere?
if a user brings EML functions f and g; given their binary EML trees; can we decide if they represent the same function, so the question form is
A(x)=0 EVERYWHERE?
(like given 2 fractions a/b == c/d ? do the fractions represent the same fraction?)
From Wikipedia link reikonomusha gave:
> Miklós Laczkovich removed also the need for π and reduced the use of composition.[5] In particular, given an expression A(x) in the ring generated by the integers, x, sin xn, and sin(x sin xn) (for n ranging over positive integers), both the question of whether A(x) > 0 for some x and whether A(x) = 0 for some x are unsolvable.
Here the question forms are
1) exist x such that A(x) > 0 (does there exist an x where A(x) becomes positive?)
2) exist x such that A(x) = 0 (does there exist a value such that A(x) becomes 0? or basically find real roots
so at least the forms on WikiPedia don't generate the results both of you claim it does.
it does present undecidability results, but not straightforwardly in the context of this EML work.
second the Richardson's theorem is about the function on the reals, not complex functions (I mean the roots must lay somewhere)
> 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…
> If you take a real analysis class, the elementary functions will be defined exactly as the author of the EML paper does. I just looked through many of the best known real analysis texts, and not a single one defines them this way. This list included the texts by Royden, Terence Tao, Rudin, Spivak, Bartle & Sherbert, Pugh, and a few others.... Can you cite a single text book that has this definition you claim is in…
> The elementary functions of analysis, that is powers, roots, exponentials, logarithms and their inverses, functions obtained from the former by arithmetic operations or composition, admit the limit f(p) for x → p, for any p in their set of definition. The study of such functions, which is not limited to the sole real functions of real variable, is carried out naturally in the setting of metric spaces.
That said, I'm relatively sure that a definition was given in class and it didn't include arbitrary roots: despite being notoriously difficult, the exam didn't require students to draw the graph of any elementary function including implicitly-defined algebraic roots.
I picked up another one of the old recommended books [2] and it seems to be similarly vague; while the book currently taught in my university [3], gives this definition:
> The following functions (from ℂ to ℂ) are called the elementary functions of the Analysis:
> 1) Rational functions (integral or fractional)
> 2) Algebraic functions (explicit or implicit)
> 3) The exponential function
> 4) The logarithm function
> 5) All those functions that can be obtained by combining a finite number of times the functions of kind 1)...4).
So, roots of arbitrary polynomials implicitly defined are indeed considered elementary. I never knew this.
[1]: https://search.worldcat.org/title/1261811544
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?
> 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.
Earlier quoted context omitted.
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…
This 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
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…
You can find thousands of such questions on Math StackExchange. Take e.g. [1]: never been asked anywhere else, interesting enough, yet answered pretty much immediately by two separate mathematicians.
"Is there a single constant and function with connected domain that can express all of $\log, \exp, \sin, \dots$?" would have made a fine question there too, the type that gets a thorough answer very quickly if anyone bothers to ask it.
> the burden of proof should not lay with the reader
You were the one who made the claim that "this is one of the most significant discoveries in years". Feel free to substantiate that claim first, according to the same standards. Are there any authors who ask this question, and/or suggest that they don't know an answer?
[1] https://math.stackexchange.com/questions/2308587/is-the-set-...
Earlier quoted context omitted.
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?
> 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…
Earlier quoted context omitted.
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 eve…
Erm... No. It's not great.
> Why not invite it to the table of functions?
Because it's too arbitrary.
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…
> 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?