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.
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.
> 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:
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)
> 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?
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.
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.
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.
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.
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...)
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?
> 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 learnt that some consider roots of arbitrary polynomials being part of the elementary functions before, but I'm a physicist and only ever took some undergraduate mathematics classes.
Nonetheless, calling these elementary feels a bit of stretch considering that the word literally means basic stuff, something that a beginner will learn first.
I guess you're right, I was probably mislead this whole time. I went through my old analysis class book [1] and there doesn't seem to be an explicit definition of elementary functions. The best I can find is this paragraph (I translate from italian):
> 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.
So, I did a bit of research and I wasn't going crazy: there are apparently two competing definitions of "elementary" in use [1]:
> the class of functions [...] is what I would call exponential-logarithmic functions or EL functions; that is, they are the functions that can be expressed using some finite combination of constant functions, the identity function, exp, log, composition, and arithmetic operations (+−×÷). Some authors call this class of functions elementary functions, but that term is now more commonly used in a different sense, which includes algebraic functions.
Evidently my professor was in the exponential-logarithmic camp.
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.
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.
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.
jargon are words being used that don't carry the typical laymen definition, but a specific one from the domain of said jargon.
If a written piece is intended for an audience who knows the jargon, then it's fine to use jargon - in fact it's appropriate and succinct. If it was intended for the laymen, then jargon is inappropriate.
But it seems you're lamenting that this jargon is wrong and that it shouldn't be jargon!?
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.
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
The term 'elementary function' doesn't really have a single universally agreed on strict definition.
Definitions are either a bit fuzzy, or not universally agreed on.
Though interestingly https://en.wikipedia.org/wiki/Elementary_function says "More generally, in modern mathematics, elementary functions comprise the set of [...]". Though at least Wikipedia thinks that 'modern mathematics' has a consensus; of course, there's no guarantee that whoever you are talking to uses the 'modern mathematics' definition that Wikipedia brings up.
In math elementary usually means fundamental or foundational not elementary school. The root word is element and the relationship to “simple subject” is tangential and more related to its teaching the elemental topics for a lifetime education than definitionally cross discipline.
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 intriguing is that we don’t even know whether many simple equations like exp(-x) = x (i.e. the [omega constant]) have solutions in E. We of course suspect they don’t, but this conjecture is not proven: https://en.wikipedia.org/wiki/Schanuel%27s_conjecture
> 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.
> 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.
SabrinaJewson claims it is a STRICT subset: EML ⊂ E
I remind the trivial results that both E ⊆ EML and EML ⊆ E and hence EML = E
apart from construction: which is minimal for EML but highly redundant for E.
the EML paper shows that this minimal construction for EML is not unique so other binary operations may be found with perhaps more interesting properties, or admitting shorter binary trees for commonly used functions and values (which may reflect subjective "simplification" of expressions in mathematics.
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.
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 the reals - just as long as the domain has a multiplicative zero available) as a sort of "selector":
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.
And if you want something truly surprising, Riemann's zeta function can approximate any holomorphic function arbitrarily well on the critical strip. So technically you need only _one_ argument.
The author essentially says that the quintic has no closed form solution which is true regardless of the exp-minus-log function. The purpose of this blog post is lost on me.
Can anyone please explain this further? It seems like he’s moving the goalposts.
"The quintic has no closed form solution" is a theorem that is more precisely stated (in the usual capstone Galois proof) as follows: The quintic has no closed form solution in terms of arbitrary compositions of rational numbers, arithmetic, and Nth roots. We can absolutely express closed form solutions to the quintic if we broaden our repertoire of functions, such as with the Bring radical.
The post's argument is different than the usual Galois theory result about the unsolvability of the quintic, in that it shows a property that must be true about all EML(x,y)-derived functions, and a hypothetical quintic-solver-function does not have that property, so no function we add to our repertoire via EML will solve it (or any other function, elementary or not, that lacks this property).
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 equations had solutions in terms of things we already knew about, and if they didn't and it seemed important or interesting enough, make a new name. This is the whole field of so-called "special functions". It's where we also get the elliptic functions, Bessel functions, etc.
The definition of "elementary function" comes exactly from this line in inquiry: define a set of functions we think are nice and algebraically tractable, and answer what we can express with them. The biggest classical question was:
Do integrals of elementary functions give us elementary functions?
The answer is "no" and Liouville gave us a result which tells us what the answer does look like when the result is elementary.
Risch gave us an algorithm to compute the answer, when it exists in elementary form.
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 <- x - (x^5 + x + a)/(5x^4 + 1)
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.
> 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.
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?
For me, what makes the square root more “natural” is that, although it’s usually introduced as an “answer by definition”, it can also be arrived at by wondering what happens if you take something to the halfth power.
Can anyone provide a link that "Some are going as far as to suggest that the entire foundations of computer engineering and machine learning should be re-built as a result of this", or anything similarly grandiose?
I am a professional mathematician, though nowhere near this kind of thing. The result seems amusing enough, but it doesn't really strike me as something that would be surprising. I confess that this thread is the first I've heard of it...
I still consider the article important, as it demonstrates techniques to conduct searches, and emphasizes the very early stage of the research (establishes non-uniqueness for example), openly wonders which other binary operators exist and which would have more desirable properties, etc.
Sometimes articles are important not for their immediate result, but for the tools and techniques developed to solve (often artificial or constrained) problems. The history of mathematics is filled with mathematicians studying at-the-time-rather-useless-constructions which centuries or millennia later become profound to human interaction. Think of the "value" of Euclid's greatest common divisor algorithm. What starts out as a curiosity with 0 immediate relevance for society, is now routinely used by everyone who enjoys the world wide web without their government or others MitM'ing a webpage.
If the result was the main claimed importance for the article, there would be more emphasis on it than on the methodology used to find and verify candidates, but the emphasis throughout the article is on the methodology.
It is far from obvious that the tricks used would have converged at all. Before this result, a lot of people would have been skeptical that it is even possible to do search candidates this way. While the gradual early-out tightening in verification could speed up the results, many might have argued that the approach to be used doesn't contain an assurance that the false positive rate wouldn't be excessively high (i.e. many would have said "verifying candidates does not ensure finding a solution, reality may turn out that 99.99999999999999999% of candidates turn out not to pass deeper inspection").
It is certainly noteworthy to publish these results as they establish the machinery for automated search of such operations.
His claim is that we exp-minus-log cannot compute the root of an arbitrary quintic. If you consider the root of an arbitrary quintic "elementary" the exp-minus-log can't represent all elementary functions.
I think it really comes down to what set of functions you are calling "elementary".
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.)
> 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.
Combinations of the NAND gate can express any Boolean function. The Toffoli (CCNOT) or Fredkin (CSWAP) can express any reversible Boolean function, which is important in quantum computing where all gates must be unitary (and therefore reversible). The posited analog is that EML would be the "universal operator" for continuous functions.
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.
The argument is that a universal basis would be capable of solving arbitrary polynomial roots. The rest is an argument that the group constructed by eml is solveable, and hence not all the standard elementary functions.
It wouldn't be a math discussion without people using at least two wildly different definitions.
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".
Nevertheless, it is a horrible definition. Mathematicians have often taken care to define things as close to everyday intuition as they could (and then proving an equivalence). The "elementary function" in this definition is just a weird mix of concerns.
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 wonder if exp-minus-log can represent it.
EML can represent the real absolute value, so long as we agree with the original author's proviso that we define log(0) and exp(-∞), by way of sqrt(x^2) as f(x) = exp((1/2)log x). Traditionally, log(0) isn't defined, but the original author stipulated it to be -∞, and that all arithmetic works over the "extended reals", which makes
abs(0)
= f(0) ; by defn
= exp(1/2 log 0) ; by defn
= exp(-∞/2) ; log 0 rule
= exp(-∞) ; extended real arith
= 0 ; exp(-∞) rule
If we don't agree with this, then abs() could be defined with a hole punched out of the real line. The logarithm function isn't exactly elegant in this regard with its domain restrictions. :)
It's ok for elementary functions to have singularities, like 1/x at x=0. But I'm not sure what happens with your version of abs, since the log function has branches. log(1) is any of 0, 2*pi*i, 4*pi*i, etc.
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.
The origianl article use complex numbers, in particular to get sin and cos from eml:
> 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.
This is a bit like invalidating a result based on 0^0 := 1 because you work in a field of mathematics where 0^0 is an indeterminate form. Not very interesting.
AFAIU the original paper is a result in the field of symbolic regression. What definition of elementary function do they use?
On a tangent: I've tried to connect Euclid's Elements with quantifier elimination theorems. It looks like most of the geometry follows from QE of real-closed fields. Some of the number theory relates to Presburger arithmetic. Some other number theory, including the irrationality of sqrt(2), is down to Skolem. The Pythagorean triples relate to extending Skolem to the Gaussian integers. I suspect some of the "embryonic" integral calculus could be related to holonomic functions, which seem like they admit a form of QE.
Don't have anything for the perfect numbers though.
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 using the single one given looks like some fairly routine Galois theory.
Whether this function is "considered elementary" depends on who you ask. Most people would not say this is elementary, but the author would like to redefine the term to include it, which would make the theorem not true anymore.
Why any of this would shake the foundations of computer engineering I do not know.
I've thought something like that, but I'm interested more in details of the argument.
As for why this could be important... we sometimes find new ways of solving old problems, when we formulate them in a different language. I remember how i was surprised to learn how representation of numbers as a tuple (ordered list of numbers), where each element is the remainder for mutually prime dividers - as many dividers as there are elements in the tuple - reduces the size of tables of division operation, and so the hardware which does the operation using thise tables may use significantly less memory. Here we might have some other interesting advantages.
But can you even express this function with the elementary operator symbols, exp, log, power and trig functions? It seems to me like no, you can't express "largest real solution" with those (and what's the intended result for complex inputs?)
At least eml can express the quintic itself, just like the above mentioned operators can
Author and EML are using different definitions of elementary functions, EML's definition being the school textbooks' one (polynomials, sin, exp, log, arcsin, arctan, closed under multiplication, division and composition). The author's definition I've never met before, it apparently includes some multi-valued functions, which are quite unusual.
> More generally, in modern mathematics, elementary functions comprise the set of functions previously enumerated, all algebraic functions (not often encountered by beginners), and all functions obtained by roots of a polynomial whose coefficients are elementary. [...] This list of elementary functions was originally set forth by Joseph Liouville in 1833.
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.
As is usual with these kinds of "structure theorems" (as they're often called), we need to precisely define what set of things we seek to express.
A function which solves a quintic is reasonably ordinary. We can readily compute it to arbitrary precision using any number of methods, just as we can do with square roots or cosines. Not just the quintic, but any polynomial with rational coefficients can be solved. But the solutions can't be expressed with a finite number of draws from a small repertoire of functions like {+, -, *, /}.
So the question is, does admitting a new function into our "repertoire" allow us to express new things? That's what a structure theorem might tell us.
The blog post is exploring this question: Does a repertoire of just the EML function, which has been shown by the original author to be able to express a great variety of functions (like + or cosine or ...) also allow us to express polynomial roots?
"Commonly, the basic functions that are allowed in closed forms are nth root, exponential function, logarithm, and trigonometric functions.[a] However, the set of basic functions depends on the context. For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions."
It's only maths, don't expect things to be so black and white.
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.
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.
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.
Yes it does; you can build the absolute value as sqrt(x²), and sqrt(x) and x² are both constructible using eml.
If I understand the page correctly, the extension by Miklós Laczkovich should be enough to show that it's undecidable.
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)
> 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?
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...
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.
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.
> 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.
> 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.
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...
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.
> Odrzywolek's result is immediately obvious
Many things that in retrospect seem immediately obvious weren't obvious before, let alone immediately obvious.
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.
> 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...)
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-...
Upvoted back to not-greyed-out. You must have struck a nerve.
> 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 learnt that some consider roots of arbitrary polynomials being part of the elementary functions before, but I'm a physicist and only ever took some undergraduate mathematics classes. Nonetheless, calling these elementary feels a bit of stretch considering that the word literally means basic stuff, something that a beginner will learn first.
> 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 every real analysis course? I find all evidence points to the opposite.
I guess you're right, I was probably mislead this whole time. I went through my old analysis class book [1] and there doesn't seem to be an explicit definition of elementary functions. The best I can find is this paragraph (I translate from italian):
> 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
[2]: https://search.worldcat.org/title/801297519
[3]: https://search.worldcat.org/title/935666878
So, I did a bit of research and I wasn't going crazy: there are apparently two competing definitions of "elementary" in use [1]:
> the class of functions [...] is what I would call exponential-logarithmic functions or EL functions; that is, they are the functions that can be expressed using some finite combination of constant functions, the identity function, exp, log, composition, and arithmetic operations (+−×÷). Some authors call this class of functions elementary functions, but that term is now more commonly used in a different sense, which includes algebraic functions.
Evidently my professor was in the exponential-logarithmic camp.
[1]: https://mathoverflow.net/a/442656
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.
Introduction to ...
That's code for 101.
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. :)
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/math401... (2016)
- Ritt's Integration in Finite Terms: Liouville's Theory of Elementary Methods (1948)
It's not frequent that analysis books will define the class of elementary functions rigorously, but instead refer to examples of them informally.
> 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
where + and * are understood to produce new functions. Sort of Haskell-y.> 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?
Not that I've seen.
jargon are words being used that don't carry the typical laymen definition, but a specific one from the domain of said jargon.
If a written piece is intended for an audience who knows the jargon, then it's fine to use jargon - in fact it's appropriate and succinct. If it was intended for the laymen, then jargon is inappropriate.
But it seems you're lamenting that this jargon is wrong and that it shouldn't be jargon!?
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.
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
The term 'elementary function' doesn't really have a single universally agreed on strict definition.
Definitions are either a bit fuzzy, or not universally agreed on.
Though interestingly https://en.wikipedia.org/wiki/Elementary_function says "More generally, in modern mathematics, elementary functions comprise the set of [...]". Though at least Wikipedia thinks that 'modern mathematics' has a consensus; of course, there's no guarantee that whoever you are talking to uses the 'modern mathematics' definition that Wikipedia brings up.
In math elementary usually means fundamental or foundational not elementary school. The root word is element and the relationship to “simple subject” is tangential and more related to its teaching the elemental topics for a lifetime education than definitionally cross discipline.
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 intriguing is that we don’t even know whether many simple equations like exp(-x) = x (i.e. the [omega constant]) have solutions in E. We of course suspect they don’t, but this conjecture is not proven: https://en.wikipedia.org/wiki/Schanuel%27s_conjecture
What is a closed-form number?: http://timothychow.net/closedform.pdf omega constant: https://en.wikipedia.org/wiki/Omega_constant
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.
> 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.
SabrinaJewson claims it is a STRICT subset: EML ⊂ E
I remind the trivial results that both E ⊆ EML and EML ⊆ E and hence EML = E
apart from construction: which is minimal for EML but highly redundant for E.
the EML paper shows that this minimal construction for EML is not unique so other binary operations may be found with perhaps more interesting properties, or admitting shorter binary trees for commonly used functions and values (which may reflect subjective "simplification" of expressions in mathematics.
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.
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 the reals - just as long as the domain has a multiplicative zero available) as a sort of "selector":
g(x_0, c_0, x_1, c_1, ... , x_n, c_n) = c_0 * f_0(x_0) + ... + c_n * f_n(x_n)
The trick is to minimize the number of arguments and complexity of the RHS - but that there's a trivial upper-bound (in terms of number of arguments).
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.
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
Why would it be surprising?
And if you want something truly surprising, Riemann's zeta function can approximate any holomorphic function arbitrarily well on the critical strip. So technically you need only _one_ argument.
> Why would it be surprising?
Because I don’t know as much mathematics as you.
The author essentially says that the quintic has no closed form solution which is true regardless of the exp-minus-log function. The purpose of this blog post is lost on me.
Can anyone please explain this further? It seems like he’s moving the goalposts.
"The quintic has no closed form solution" is a theorem that is more precisely stated (in the usual capstone Galois proof) as follows: The quintic has no closed form solution in terms of arbitrary compositions of rational numbers, arithmetic, and Nth roots. We can absolutely express closed form solutions to the quintic if we broaden our repertoire of functions, such as with the Bring radical.
The post's argument is different than the usual Galois theory result about the unsolvability of the quintic, in that it shows a property that must be true about all EML(x,y)-derived functions, and a hypothetical quintic-solver-function does not have that property, so no function we add to our repertoire via EML will solve it (or any other function, elementary or not, that lacks this property).
Cool explanation, thanks!
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 equations had solutions in terms of things we already knew about, and if they didn't and it seemed important or interesting enough, make a new name. This is the whole field of so-called "special functions". It's where we also get the elliptic functions, Bessel functions, etc.
The definition of "elementary function" comes exactly from this line in inquiry: define a set of functions we think are nice and algebraically tractable, and answer what we can express with them. The biggest classical question was:
The answer is "no" and Liouville gave us a result which tells us what the answer does look like when the result is elementary.Risch gave us an algorithm to compute the answer, when it exists in elementary form.
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.
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:
We can compute its digits with the very rapidly convergent Newton iteration 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.
> The Bring radical has a great geometric interpretation
Erm... No. It's not great.
> Why not invite it to the table of functions?
Because it's too arbitrary.
> 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.
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?
For me, what makes the square root more “natural” is that, although it’s usually introduced as an “answer by definition”, it can also be arrived at by wondering what happens if you take something to the halfth power.
Can anyone provide a link that "Some are going as far as to suggest that the entire foundations of computer engineering and machine learning should be re-built as a result of this", or anything similarly grandiose?
I am a professional mathematician, though nowhere near this kind of thing. The result seems amusing enough, but it doesn't really strike me as something that would be surprising. I confess that this thread is the first I've heard of it...
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 continuous math, not ones and zeroes. Assuming peer review proves it out, this is outstanding."
[1] https://news.ycombinator.com/item?id=47746610
[2] https://www.reddit.com/r/math/comments/1sk63n5/all_elementar...
:)
I still consider the article important, as it demonstrates techniques to conduct searches, and emphasizes the very early stage of the research (establishes non-uniqueness for example), openly wonders which other binary operators exist and which would have more desirable properties, etc.
Sometimes articles are important not for their immediate result, but for the tools and techniques developed to solve (often artificial or constrained) problems. The history of mathematics is filled with mathematicians studying at-the-time-rather-useless-constructions which centuries or millennia later become profound to human interaction. Think of the "value" of Euclid's greatest common divisor algorithm. What starts out as a curiosity with 0 immediate relevance for society, is now routinely used by everyone who enjoys the world wide web without their government or others MitM'ing a webpage.
If the result was the main claimed importance for the article, there would be more emphasis on it than on the methodology used to find and verify candidates, but the emphasis throughout the article is on the methodology.
It is far from obvious that the tricks used would have converged at all. Before this result, a lot of people would have been skeptical that it is even possible to do search candidates this way. While the gradual early-out tightening in verification could speed up the results, many might have argued that the approach to be used doesn't contain an assurance that the false positive rate wouldn't be excessively high (i.e. many would have said "verifying candidates does not ensure finding a solution, reality may turn out that 99.99999999999999999% of candidates turn out not to pass deeper inspection").
It is certainly noteworthy to publish these results as they establish the machinery for automated search of such operations.
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
Why on earth would it upend all of mathematics? Secondly, even if it did that, why would that be concerning for mathematics?
Yes or no, it's too early to tell.
His claim is that we exp-minus-log cannot compute the root of an arbitrary quintic. If you consider the root of an arbitrary quintic "elementary" the exp-minus-log can't represent all elementary functions.
I think it really comes down to what set of functions you are calling "elementary".
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.
Combinations of the NAND gate can express any Boolean function. The Toffoli (CCNOT) or Fredkin (CSWAP) can express any reversible Boolean function, which is important in quantum computing where all gates must be unitary (and therefore reversible). The posited analog is that EML would be the "universal operator" for continuous functions.
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.
Surely you can use EML to do root finding approximations also.
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.
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?
I meant for finite fields like the person i was responding to said.
The argument is that a universal basis would be capable of solving arbitrary polynomial roots. The rest is an argument that the group constructed by eml is solveable, and hence not all the standard elementary functions.
It wouldn't be a math discussion without people using at least two wildly different definitions.
Yes, that blog post could have been much shorter….
> 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
Thanks, actually https://en.wikipedia.org/wiki/Elementary_function confirms your claim.
Nevertheless, it is a horrible definition. Mathematicians have often taken care to define things as close to everyday intuition as they could (and then proving an equivalence). The "elementary function" in this definition is just a weird mix of concerns.
Elementary function is also a general English phrase that can very much be used to represent the functions on a scientific calculator.
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 wonder if exp-minus-log can represent it.
EML can represent the real absolute value, so long as we agree with the original author's proviso that we define log(0) and exp(-∞), by way of sqrt(x^2) as f(x) = exp((1/2)log x). Traditionally, log(0) isn't defined, but the original author stipulated it to be -∞, and that all arithmetic works over the "extended reals", which makes
If we don't agree with this, then abs() could be defined with a hole punched out of the real line. The logarithm function isn't exactly elegant in this regard with its domain restrictions. :)It's ok for elementary functions to have singularities, like 1/x at x=0. But I'm not sure what happens with your version of abs, since the log function has branches. log(1) is any of 0, 2*pi*i, 4*pi*i, etc.
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.
The origianl article use complex numbers, in particular to get sin and cos from eml:
> 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.
This is a bit like invalidating a result based on 0^0 := 1 because you work in a field of mathematics where 0^0 is an indeterminate form. Not very interesting.
AFAIU the original paper is a result in the field of symbolic regression. What definition of elementary function do they use?
On a tangent: I've tried to connect Euclid's Elements with quantifier elimination theorems. It looks like most of the geometry follows from QE of real-closed fields. Some of the number theory relates to Presburger arithmetic. Some other number theory, including the irrationality of sqrt(2), is down to Skolem. The Pythagorean triples relate to extending Skolem to the Gaussian integers. I suspect some of the "embryonic" integral calculus could be related to holonomic functions, which seem like they admit a form of QE.
Don't have anything for the perfect numbers though.
Codex and I whipped this up based on the paper: https://github.com/timschmidt/emlmath
Tests for the trig functions aren't passing yet due to an issue with the derived eml form in some mirrored cases.
I'd really like more details on the terminology used.
Also I'd be glad to see a specific example of a function, considered elementary, which is not representable by EML.
It could be hard, and in any case, thanks for the article. I wish it would be more accessible to me.
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 using the single one given looks like some fairly routine Galois theory.
Whether this function is "considered elementary" depends on who you ask. Most people would not say this is elementary, but the author would like to redefine the term to include it, which would make the theorem not true anymore.
Why any of this would shake the foundations of computer engineering I do not know.
I've thought something like that, but I'm interested more in details of the argument.
As for why this could be important... we sometimes find new ways of solving old problems, when we formulate them in a different language. I remember how i was surprised to learn how representation of numbers as a tuple (ordered list of numbers), where each element is the remainder for mutually prime dividers - as many dividers as there are elements in the tuple - reduces the size of tables of division operation, and so the hardware which does the operation using thise tables may use significantly less memory. Here we might have some other interesting advantages.
But can you even express this function with the elementary operator symbols, exp, log, power and trig functions? It seems to me like no, you can't express "largest real solution" with those (and what's the intended result for complex inputs?)
At least eml can express the quintic itself, just like the above mentioned operators can
Author and EML are using different definitions of elementary functions, EML's definition being the school textbooks' one (polynomials, sin, exp, log, arcsin, arctan, closed under multiplication, division and composition). The author's definition I've never met before, it apparently includes some multi-valued functions, which are quite unusual.
Wikipedia says:
> More generally, in modern mathematics, elementary functions comprise the set of functions previously enumerated, all algebraic functions (not often encountered by beginners), and all functions obtained by roots of a polynomial whose coefficients are elementary. [...] This list of elementary functions was originally set forth by Joseph Liouville in 1833.
which seems to be what the blog post references.
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.
As is usual with these kinds of "structure theorems" (as they're often called), we need to precisely define what set of things we seek to express.
A function which solves a quintic is reasonably ordinary. We can readily compute it to arbitrary precision using any number of methods, just as we can do with square roots or cosines. Not just the quintic, but any polynomial with rational coefficients can be solved. But the solutions can't be expressed with a finite number of draws from a small repertoire of functions like {+, -, *, /}.
So the question is, does admitting a new function into our "repertoire" allow us to express new things? That's what a structure theorem might tell us.
The blog post is exploring this question: Does a repertoire of just the EML function, which has been shown by the original author to be able to express a great variety of functions (like + or cosine or ...) also allow us to express polynomial roots?
That’s a poor analogy because all polynomials can be solved to arbitrary precision with efficient algorithms.
How can an edit possibly be made on April 16 when today is the 15th?
It's already past midnight in New Zealand, e.g.
Where would EML expressions sit in this fascinating table?
https://en.wikipedia.org/wiki/Template:Mathematical_expressi...
Closed-form expressions, I guess?
"For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions."
Maybe I'm misunderstanding, but the table says that the "root of a polynomial that is not an algebraic solution" doesn't count as closed-form.
https://en.wikipedia.org/wiki/Closed-form_expression
"Commonly, the basic functions that are allowed in closed forms are nth root, exponential function, logarithm, and trigonometric functions.[a] However, the set of basic functions depends on the context. For example, if one adds polynomial roots to the basic functions, the functions that have a closed form are called elementary functions."
It's only maths, don't expect things to be so black and white.
tangenially it would be interesting to analyze what infinite structures can be represented with infinite EML trees
[dead]
If this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.