4 ms·

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 so

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.

contravariant 4y ago
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.
- pfdietz 4y ago
  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.
  - ogogmad 4y ago
    That's technically correct. But all real numbers in practice are computable.
    - pfdietz 4y ago
      I looked at your statement for a while and I can't figure out how it could be made to make any sense.
      - ogogmad 4y ago
        This might not be the best written or best sourced article, but I would start here: https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis 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.
        Someone 4y ago
        > 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?
        pfdietz 4y ago
        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.
    - hansvm 4y ago
      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.
  - contravariant 4y ago
    Well, I didn't mean that, but sure. For what it's worth the numbers in question are computable.
    - cs137 4y ago
      Chaitin's constant (which is actually a family of constants, one that exists for each programming language) is not 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.
YouWhy 4y ago
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.
- hansvm 4y ago
  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.
tzs 4y ago
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. [1] https://www.amazon.com/Book-Abstract-Algebra-Second-Mathematics/dp/0486474178 https://www.amazon.com/Book-Abstract-Algebra-Second-Mathemat...
Rerarom 4y ago
Yeah, it's a very strong result. 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.

contravariant 4y ago

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.

pfdietz 4y ago
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.
- ogogmad 4y ago
  That's technically correct. But all real numbers in practice are computable.
  - pfdietz 4y ago
    I looked at your statement for a while and I can't figure out how it could be made to make any sense.
    - ogogmad 4y ago
      This might not be the best written or best sourced article, but I would start here: https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis 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.
      - Someone 4y ago
        > 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?
      - pfdietz 4y ago
        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.
  - hansvm 4y ago
    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.
- contravariant 4y ago
  Well, I didn't mean that, but sure. For what it's worth the numbers in question are computable.
  - cs137 4y ago
    Chaitin's constant (which is actually a family of constants, one that exists for each programming language) is not 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.

YouWhy 4y ago

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.

hansvm 4y ago
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.

tzs 4y ago

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. [1] https://www.amazon.com/Book-Abstract-Algebra-Second-Mathematics/dp/0486474178 https://www.amazon.com/Book-Abstract-Algebra-Second-Mathemat...

Rerarom 4y ago

Yeah, it's a very strong result. 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.