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 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 2 days ago | parent | next [-]

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 implement the same function, I'm pretty sure it's not decidable if two EML trees describe the same function.

▲

reikonomusha 2 days ago | parent | next [-]

You are correct, it is undecidable by Richardson's theorem [1].

[1] https://en.wikipedia.org/wiki/Richardson%27s_theorem

▲

DoctorOetker 2 days ago | parent [-]

that result does not apply for EML: EML doesn't have the | . | absolute value function, a prerequisite for Richardson's theorem.

▲

ComplexSystems 18 hours ago | parent | next [-]

Yes it does; you can build the absolute value as sqrt(x²), and sqrt(x) and x² are both constructible using eml.

▲

vintermann 2 days ago | parent | prev [-]

If I understand the page correctly, the extension by Miklós Laczkovich should be enough to show that it's undecidable.

▲

DoctorOetker 2 days ago | parent [-]

You wrote:

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

▲

vintermann 2 days ago | parent [-]

> an expression in the ring generated by the integers, x, sin xn, and sin(x sin xn)

We can always write AML trees for expressions generated by the integers, x, sin xn, and sin(x sin xn), right?

So we should be able to write EML trees for any two such expressions, A and B. If they're equal everywhere, then A - B = 0 everywhere. A - B is also in the aforementioned ring.

If there was a decision procedure always to determine if EML trees represent the same function, then that contradicts Miklós Laczkovich's extension, right?

▲

DoctorOetker 2 days ago | parent [-]

no Miklós Laczkovich's extension as described on wikipedia only says that both of the following questions are proven undecidable:

1) is there some value x such that some function F(x)=A(x)-B(x)=0?

2) is there some value x such that F(x)>0?

while you asked:

> I'm pretty sure it's not decidable if two EML trees describe the same function.

that would be

3) is for every x F(x)=A(x)-B(x)==0?

which Miklós Laczkovich's extension does not provide.

And you ignore the fact that Miklós Laczkovich's extension applies to real numbers and functions...

▲

vintermann a day ago | parent [-]

If it's undecidable whether it's 0 at even ONE point, clearly you can't prove that it's 0 everywhere.

Likewise, if it's not decidable for real-valued functions, clearly it's not decidable for complex valued functions.

	▲	DoctorOetker a day ago \| parent [-]
		thats not how this works decidability does not distribute over pointwise question asking on sets, or if you believe it does, show us the proof. Telling if an EML(x,y),1 constructed expression is identically 0 is in the gray zone, as far as I can tell, it has neither been proven decidable nor been proven undecidable. Nevertheless regardless of decidability the authors clearly show the multipoint sampling/testing is a decent filter, and the shorter resulting expressions have been proven correct in the results for the construction at least.

▲

zephen 2 days ago | parent | prev [-]

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

▲

eru 2 days ago | parent | prev | next [-]

> Neither the present article, nor the original one has much mathematical originality, though: Odrzywolek's result is immediately obvious, [...]

Maybe. But I found it a nice piece of recreational mathematics nevertheless.

▲

reikonomusha 2 days ago | parent | prev | next [-]

Arnold (as reported by Goldmakher [1]) does prove the unsolvability of the quintic in finite terms of arithmetic and single-valued continuous functions (which does not include the complex logarithm). TFA's result is stronger, which is something about the solvability of the monodromy groups of all EML-derived functions. So it doesn't seem to be a "rehash", even if their specific counterexample could have been achieved either in fewer steps or with less machinery.

[1] https://web.williams.edu/Mathematics/lg5/394/ArnoldQuintic.p...

	▲	saithound 2 days ago \| parent [-]
		Arnold's proof can be used to show that certain classes of functions are insufficient to express a quintic formula. These classes can always safely include all single-valued continuous functions (you cannot even write the _quadratic_ formula in terms of arithmetic and single-valued continuous functions!), but also plenty of non-single-valued functions (e.g. the +-sqrt function which appears in the well-known quadratic formula). Applying Arnold's proof to the class given by arithmetic and all complex nth root functions (also multivalued) gives the usual Abel-Ruffini theorem. But Arnold's proof applies to the class "all elm-expressible functions" without modification.

▲

cubefox 2 days ago | parent | prev | next [-]

> Odrzywolek's result is immediately obvious

Many things that in retrospect seem immediately obvious weren't obvious before, let alone immediately obvious.

	▲	DoctorOetker 2 days ago \| parent [-]
		and its depressing when the rare actual progress is made, a collection of jealous practitioners comes to party-poop all over the place, for bringing the insights that make the result from then on immediately obvious.

▲

DoctorOetker 2 days ago | parent | prev [-]

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

▲

saithound 2 days ago | parent | next [-]

Questions which have never been asked or answered before, but to which practitioners have immediately obvious answers, are dime a dozen in mathematics.

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

	▲	2 days ago \| parent [-]
		[deleted]

▲

zephen 2 days ago | parent | prev [-]

Upvoted back to not-greyed-out. You must have struck a nerve.