Not all elementary functions can be expressed with exp-minus-log
lotaezenwa
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.
DevelopingElk
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".
petters
Yes, that blog post could have been much shorter….
AlotOfReading
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.
markgall
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...
reikonomusha
"The quintic has no closed form solution" is a theorem that is more precisely stated 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 the Bring radical.
The post's argument different than the usual Galois theory result about the unsolvability of the quintic, in that it shows that even with a transcendental function like EML(x, y), we still don't get a solution.
saithound
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
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
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.
Many things that seem immediately obvious in retrospect weren't obvious before.
avmich
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.
markgall
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.
bawolff
> 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.
js8
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.
SabrinaJewson
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
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?
renewiltord
If this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.
rnhmjoj
> 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.
reikonomusha
The definition of "elementary function" typically includes functions which solve polynomials, like the Bring radical. The definition is most fitting in algebraic contexts where algebraic structure is meaningful (like Liouvillian structure theorems). See e.g.
- 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.
burnished
All I know is that when a class starts with 'elementary' or 'fundamentals of' you had best buckle up.
chii
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!?
mcmoor
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?
derriz
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":
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).
kqr
This is similar to the idea of generating functions, if you would like more to read!
cyberax
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.
aixpert
tangenially it would be interesting to analyze what infinite structures can be represented with infinite EML trees
throwaway81523
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.
traes
abs(x) = sqrt(x*x), no?
reikonomusha
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. :)
ogogmad
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.
cubefox
Where would EML expressions sit in this fascinating table?
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.
DevelopingElk
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".
petters
Yes, that blog post could have been much shorter….
AlotOfReading
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.
markgall
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...
reikonomusha
"The quintic has no closed form solution" is a theorem that is more precisely stated 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 the Bring radical.
The post's argument different than the usual Galois theory result about the unsolvability of the quintic, in that it shows that even with a transcendental function like EML(x, y), we still don't get a solution.
saithound
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
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
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.
Many things that seem immediately obvious in retrospect weren't obvious before.
avmich
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.
markgall
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.
bawolff
> 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.
js8
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.
SabrinaJewson
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
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?
renewiltord
If this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.
rnhmjoj
> 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.
reikonomusha
The definition of "elementary function" typically includes functions which solve polynomials, like the Bring radical. The definition is most fitting in algebraic contexts where algebraic structure is meaningful (like Liouvillian structure theorems). See e.g.
- 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.
burnished
All I know is that when a class starts with 'elementary' or 'fundamentals of' you had best buckle up.
chii
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!?
mcmoor
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?
derriz
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":
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).
kqr
This is similar to the idea of generating functions, if you would like more to read!
cyberax
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.
aixpert
tangenially it would be interesting to analyze what infinite structures can be represented with infinite EML trees
throwaway81523
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.
traes
abs(x) = sqrt(x*x), no?
reikonomusha
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. :)
ogogmad
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.
cubefox
Where would EML expressions sit in this fascinating table?
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.
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".
Yes, that blog post could have been much shorter….
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.
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...
"The quintic has no closed form solution" is a theorem that is more precisely stated 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 the Bring radical. The post's argument different than the usual Galois theory result about the unsolvability of the quintic, in that it shows that even with a transcendental function like EML(x, y), we still don't get a solution.
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.
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...
> Odrzywolek's result is immediately obvious
Many things that seem immediately obvious in retrospect weren't obvious before.
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.
> 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.
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
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?
If this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.
> 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.
The definition of "elementary function" typically includes functions which solve polynomials, like the Bring radical. The definition is most fitting in algebraic contexts where algebraic structure is meaningful (like Liouvillian structure theorems). 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.
All I know is that when a class starts with 'elementary' or 'fundamentals of' you had best buckle up.
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?
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).
This is similar to the idea of generating functions, if you would like more to read!
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.
tangenially it would be interesting to analyze what infinite structures can be represented with infinite EML trees
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.
abs(x) = sqrt(x*x), no?
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. :)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.
Where would EML expressions sit in this fascinating table?
https://en.wikipedia.org/wiki/Template:Mathematical_expressi...
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.
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".
Yes, that blog post could have been much shorter….
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.
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...
"The quintic has no closed form solution" is a theorem that is more precisely stated 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 the Bring radical. The post's argument different than the usual Galois theory result about the unsolvability of the quintic, in that it shows that even with a transcendental function like EML(x, y), we still don't get a solution.
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.
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...
> Odrzywolek's result is immediately obvious
Many things that seem immediately obvious in retrospect weren't obvious before.
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.
> 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.
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
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?
If this is true, then this blog post debunking EML is going to up-end all of mathematics for the next century.
> 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.
The definition of "elementary function" typically includes functions which solve polynomials, like the Bring radical. The definition is most fitting in algebraic contexts where algebraic structure is meaningful (like Liouvillian structure theorems). 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.
All I know is that when a class starts with 'elementary' or 'fundamentals of' you had best buckle up.
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?
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).
This is similar to the idea of generating functions, if you would like more to read!
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.
tangenially it would be interesting to analyze what infinite structures can be represented with infinite EML trees
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.
abs(x) = sqrt(x*x), no?
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. :)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.
Where would EML expressions sit in this fascinating table?
https://en.wikipedia.org/wiki/Template:Mathematical_expressi...