Fantastic short article with some tidbits and puzzle pieces of this oft-told story that I had not known about before. Also, due to an outside writer, kind of a respite from the typical Quanta breathless tone. (They do an excellent job, but sometimes I feel they push too hard on the significance of discoveries.)
One such interesting tidbit is the notion of a different mathematical culture at the time, which valued “duels” — exchanges of mathematical puzzles. Whoever solves the most, wins. This practice (we read) incentivized keeping some clever problem solutions secret, as ammo for a future contest.
These mathematical duels still happen today. The field of cryptoeconomics is full of online debaters trying to prove/disprove who amongst them understands the most economic game theory.
I knew that it was in general impossible to analytically solve equations of degree 5 or higher, but this is the first time I heard you can't even express the solutions in terms of sums of nth roots. I had assumed that a fifth order polynomial would have solutions which were 5th roots, you just couldn't find them.
It goes a bit further than that even, it's not just sums of nth roots it's all formulae involving just sums, products and roots (basically any of the familiar algebraic operations). This includes nested roots etc.
Of course you can write them as a limit of such operations, but that's true for all numbers.
If by "write them as a limit" you mean "give an algorithm for computing the i-th element of a sequence of rational numbers whose limit is the desired real number", then this is not true for almost all real numbers, since there are only a countable number of such algorithms.
Most operations for defining real numbers are computable. The reason for this is that, in practice, continuous functions and functionals are the same thing as computable functions and functionals. Continuous functions which aren't computable are generally pathological curiosities. One consequence of this heuristic is that since the Riemann integral is a continuous functional, one might guess that it is also computable. Indeed it is (but the proof isn't obvious). This then implies the computability of the constant pi because pi is equal to the integral
1
⌠
⎮ ________
⎮ ╱ 2
⎮ 2⋅╲╱ 1 - x dx
⌡
-1
The computability of integration implies the computability of root-finding because one can use the argument principle to do it.
> Most operations for defining real numbers are computable.
Isn’t that a tautology or at least selection bias? “Operation” seems to imply we can carry it out, which means the number can be computed.
Even if we give “operation” a wider meaning to include those that can’t be carried out, are we deceiving ourselves that most of them are computable because most of those we have thought of in the history of mathematics are?
Or do we really know something about the cardinalities of those sets?
And the total number of such definitions is countable (since each definition is a finite sequence of symbols from a finite alphabet). Therefore, the number of such definable real numbers is countable. Any real number will be arbitrarily close to a definable number (all rational numbers are definable in this sense) though.
In domains like applied physics that's often true, but as programmers there are plenty of interesting questions we can't hope to answer in many real-world situations because of uncomputability:
- Probability that a bit flip will introduce a bug
- Number of reasonable ways to solve a problem in a given language for some measure of reasonableness (e.g., as a heuristic when examining whether two similar programs are similar out of necessity or if there might have been influence from one to the other or via some joint hidden variable)
- (generally, most statistics over a space of programs)
- Optimal super-optimization with jumps allowed
- Minimal boilerplate complexity to describe an algorithm in a language
- (generally, most questions about optimizing some target over a space of programs)
- ...We don't care about all of them, but a vast array of questions about classes of programs are simply not answerable in any finite period of time.
You might be able to answer the above for sufficiently small and well-behaved inputs (e.g., in restricted languages whose constraints enable certain sorts of static analyses), but in general you cannot, and it happens often enough to definitely be a problem for real-world programs.
Some fifth order equations have solutions that may be expressed as radicals. An example of such an equation is x^5=2, for which the fifth root of 2 as a solution.
We know from school that there is a solution for any equation of degree 1 (linear) with integer coefficients using plain arithmetic, and degree 2 using radicals and arithmetic. The linked article mentions that the same holds for degrees 3 and 4.
What Abel proved for degree 5 and Galois for any degree >= 5, is that for some equations of these degrees there's no expression involving radicals and arithmetic (*) that is a solution.
To reiterate, Abel and Galois' results are about the very existence of a specific form of a solution, not "findability".
(*) More technically: any finite formula involving composition of radicals, arithmetic operations and natural numbers.
For anyone searching for more examples of similarly trivial higher-order equations, x^n-1=0 is a classic. X=1 is trivially a solution for any space with a reasonable definition of 1, and in the complex numbers you have the "roots of unity" if you'd care for a short (or long) mathematical rabbit-hole. Higher-order equations don't necessarily have solutions over radicals, but some of them demonstrably do.
If you'd like to learn the math behind that result and have not studied abstract algebra, a good book is Pinter's "A Book of Abstract Algebra" [1]. That will take you from beginning group theory through rings and fields culminating in the insolvability of the quintic.
The chapters are usually short, maybe 8-12 pages, with about half that being lots of exercises to help cement your understanding of the material. This greatly helps with self-study. And it's a Dover edition so is inexpensive.
On the other hand, for a say fourth degree equation, it just says that some solution expressible in terms of higher roots exists, but not how to find it. To find the expression, one needs to study the "generic" equation.
linearity is an illusion created by the bias of being trapped at one level of cognition and perception. if something can not work with abstract geometrical vector rules in an exponential way, then we got something wrong at the local level. even if it makes sense from that local perspective, in that local frame of reference. biggest example of this is our lack of theory of time that is compatible with quantum mechanics.
23 comments
[ 5.1 ms ] story [ 66.5 ms ] threadOne such interesting tidbit is the notion of a different mathematical culture at the time, which valued “duels” — exchanges of mathematical puzzles. Whoever solves the most, wins. This practice (we read) incentivized keeping some clever problem solutions secret, as ammo for a future contest.
https://dergigi.com/2021/01/14/bitcoin-is-time/
https://blockstream.com/eltoo.pdf
Of course you can write them as a limit of such operations, but that's true for all numbers.
Most operations for defining real numbers are computable. The reason for this is that, in practice, continuous functions and functionals are the same thing as computable functions and functionals. Continuous functions which aren't computable are generally pathological curiosities. One consequence of this heuristic is that since the Riemann integral is a continuous functional, one might guess that it is also computable. Indeed it is (but the proof isn't obvious). This then implies the computability of the constant pi because pi is equal to the integral
The computability of integration implies the computability of root-finding because one can use the argument principle to do it.Isn’t that a tautology or at least selection bias? “Operation” seems to imply we can carry it out, which means the number can be computed.
Even if we give “operation” a wider meaning to include those that can’t be carried out, are we deceiving ourselves that most of them are computable because most of those we have thought of in the history of mathematics are?
Or do we really know something about the cardinalities of those sets?
- Probability that a bit flip will introduce a bug - Number of reasonable ways to solve a problem in a given language for some measure of reasonableness (e.g., as a heuristic when examining whether two similar programs are similar out of necessity or if there might have been influence from one to the other or via some joint hidden variable) - (generally, most statistics over a space of programs) - Optimal super-optimization with jumps allowed - Minimal boilerplate complexity to describe an algorithm in a language - (generally, most questions about optimizing some target over a space of programs) - ...We don't care about all of them, but a vast array of questions about classes of programs are simply not answerable in any finite period of time.
You might be able to answer the above for sufficiently small and well-behaved inputs (e.g., in restricted languages whose constraints enable certain sorts of static analyses), but in general you cannot, and it happens often enough to definitely be a problem for real-world programs.
For what it's worth the numbers in question are computable.
It's the probability of a randomly generated program halting. One can imagine it being of interest, at least among theorists.
That said, I struggle to think of other useful non-computable numbers, save contrived examples.
We know from school that there is a solution for any equation of degree 1 (linear) with integer coefficients using plain arithmetic, and degree 2 using radicals and arithmetic. The linked article mentions that the same holds for degrees 3 and 4.
What Abel proved for degree 5 and Galois for any degree >= 5, is that for some equations of these degrees there's no expression involving radicals and arithmetic (*) that is a solution.
To reiterate, Abel and Galois' results are about the very existence of a specific form of a solution, not "findability".
(*) More technically: any finite formula involving composition of radicals, arithmetic operations and natural numbers.
The chapters are usually short, maybe 8-12 pages, with about half that being lots of exercises to help cement your understanding of the material. This greatly helps with self-study. And it's a Dover edition so is inexpensive.
[1] https://www.amazon.com/Book-Abstract-Algebra-Second-Mathemat...
On the other hand, for a say fourth degree equation, it just says that some solution expressible in terms of higher roots exists, but not how to find it. To find the expression, one needs to study the "generic" equation.
https://www.youtube.com/watch?v=cUzklzVXJwo