From Roots to Polynomials(blog.pkh.me)
blog.pkh.me
From Roots to Polynomials
http://blog.pkh.me/p/31-from-roots-to-polynomials.html
7 comments
A side note - these types of problems (finding patterns) tend to be fun and very approachable math problems. You can almost guarantee that the exact same thing has been solved before, but like solving cross-words, sudoku, or whatever - it's easy to get drawn to them.
I thought this part was interesting:
Formally, if one expands <math>(x-r_1) (x-r_2) \cdots (x-r_n),</math> the terms are precisely <math>(-1)^{n-k}r_1^{b_1}\cdots r_n^{b_n} x^k,</math> where <math>b_i</math> is either 0 or 1, accordingly as whether <math>r_i</math> is included in the product or not, and ''k'' is the number of <math>r_i</math> that are excluded, so the total number of factors in the product is ''n'' (counting <math>x^k</math> with multiplicity ''k'') – as there are ''n'' binary choices (include <math>r_i</math> or ''x''), there are <math>2^n</math> terms – geometrically, these can be understood as the vertices of a hypercube. Grouping these terms by degree yields the elementary symmetric polynomials in <math>r_i</math> – for ''x<sup>k</sup>,'' all distinct ''k''-fold products of <math>r_i.</math>And a proof of the platonic theory of the Ideas. Is math real(kicks back)?
Math is the subset of fiction that, for some reason inherent in the human brain and\or the universe, is always invented/re-invented with the exact same essential details across several non-colluding minds.
Mathematical mental artifacts are special stories with incredible mutation-resistent properties, memes which compel their host with astonishing power and insistence to interpret and extract from them the same conclusions and patterns and behaviours that other hosts infected with the same meme did\do, or at least prevent one host from interpreting or concluding the opposite of what most other hosts interpreted\concluded.
That is, Mathematical Reasoning is a distributed mind-consensus 0-communication algorithm, a way for minds (instantiated in brains, silicon chips,spacetime foams,...) to agree on something while never actually explicitly arguing or debating or handshaking in any way. The set of all objects and states Mathematical Reasoning is capable of agreeing on is by definition Mathematics.
Discovering sentient aliens would shed much light on this.
Mathematical mental artifacts are special stories with incredible mutation-resistent properties, memes which compel their host with astonishing power and insistence to interpret and extract from them the same conclusions and patterns and behaviours that other hosts infected with the same meme did\do, or at least prevent one host from interpreting or concluding the opposite of what most other hosts interpreted\concluded.
That is, Mathematical Reasoning is a distributed mind-consensus 0-communication algorithm, a way for minds (instantiated in brains, silicon chips,spacetime foams,...) to agree on something while never actually explicitly arguing or debating or handshaking in any way. The set of all objects and states Mathematical Reasoning is capable of agreeing on is by definition Mathematics.
Discovering sentient aliens would shed much light on this.
There's a distinction between whether the objects of mathematics are "invented" vs. whether they are subjective. These arent equivalent notions.
It's possible to maintain mathematics is discovered and its objects are subjective. This would be akin to the kantian position, in which mathematics constitues something like the formal structure of subjective experience itself. ' Either way, the options arent "invented subjectivity, vs. discovered platonism
It's possible to maintain mathematics is discovered and its objects are subjective. This would be akin to the kantian position, in which mathematics constitues something like the formal structure of subjective experience itself. ' Either way, the options arent "invented subjectivity, vs. discovered platonism
Yay, that means I'm a genius!
Joke aside, yeah various people pointed that out to me so I quickly added an edit at the end of the post. Thanks :)
Joke aside, yeah various people pointed that out to me so I quickly added an edit at the end of the post. Thanks :)
[deleted]
Nice work on this post. It was easy to follow your line of exploration and thinking. May I suggest a couple of simplifications.
The generator expression in the sum() just applies a one-argument function so it can be replaced with map(). And instead of computing a sign at each step, it is simpler and faster to negate the roots at the outset.
There actually is a combinations(..., 0) in Python, and it returns [()] which is consistent with math.comb(4, 0) returning 1. Also, prod([]) returns 1. Putting those facts together helps eliminate special case at the end point.
Here's the simplified code:
The generator expression in the sum() just applies a one-argument function so it can be replaced with map(). And instead of computing a sign at each step, it is simpler and faster to negate the roots at the outset.
There actually is a combinations(..., 0) in Python, and it returns [()] which is consistent with math.comb(4, 0) returning 1. Also, prod([]) returns 1. Putting those facts together helps eliminate special case at the end point.
Here's the simplified code:
from itertools import combinations
from operator import neg
from math import prod
def coeffs_from_roots(roots):
roots = list(map(neg, roots))
return [
sum(map(prod, combinations(roots, k)))
for k in range(len(roots) + 1)
]I'm not sure why I missed the combinations(..., 0), I'm pretty certain to have tested in a previous iteration (maybe because I wasn't using math.prod() initially); code and text adjusted.
For the map yeah I thought it wasn't recommended by Python style but I personally prefer it so I'm adopting that change as well.
For the sign change, your initial comment (before your edits) was proposing the (1, -1)[i & 1] trick, which I actually like better than negating all the roots. At least for clarity in understanding the blog post (which mentions the sign juggling), I think it's better to keep it that way. I added a link to your comment for anyone looking for further improvement.
Thanks for the all the suggestions :)
For the map yeah I thought it wasn't recommended by Python style but I personally prefer it so I'm adopting that change as well.
For the sign change, your initial comment (before your edits) was proposing the (1, -1)[i & 1] trick, which I actually like better than negating all the roots. At least for clarity in understanding the blog post (which mentions the sign juggling), I think it's better to keep it that way. I added a link to your comment for anyone looking for further improvement.
Thanks for the all the suggestions :)
Note that using Numpy this is quite straightforward:
from numpy.polynomial import Polynomial
print(Polynomial.fromroots([-1, 1]))"Starting degree 5 it is proven that no analytical solution can exist and we must rely on trial and error methods."
Not quite. No solution exists that uses a very restricted set of functions deemed "closed-form", in particular sums, products, quotients and n'th radicals. These polynomials can still be solved analytically and in closed-form by introducing some additional special functions. Certainly there are many ways forward rather than "trial and error methods," which I interpret as meaning the answer must be approximated numerically.
For instance, all polynomials can be solved analytically and in closed form if elliptic functions are allowed to exist in the solution.
Or as a simpler example, the quintic x⁵+x+a has no closed form solution in radicals, and is in some sense the prototypical example of an unsolvable quintic. This polynomial has one unique real root, which is a function of the variable a. In fact, we can look at this root as a function of a; this is called the "Bring radical" of a, denoted BR(a), and easily see it is a very simple, well-behaved, and perfectly "valid" analytic function of a. It is in some sense a sister function to the ordinary real fifth root of a, denoted ⁵√a, which would instead be the unique real root of the polynomial x⁵-a. The two are also just about equally easy to compute numerically to arbitrary precision. If we allow BR(a) to "exist" as a function worthy of being deemed "closed-form," "analytic" or what have you, then every quintic now has a closed form solution in terms of radicals and this one extra special function.
This somewhat important detail is often omitted when explaining this. People often write the idea that there "is no general solution" to the quintic, which is misleading at best or wrong at worst. Perhaps a good analogy is to think back to the days when all numbers were thought to be rational. In such a system, even quadratic polynomials "have no analytic solution", one needs to invent the square root function to express the roots of the quadratic in closed form. The same thing happens for cubic and quartic polynomials, where we add cube roots and fourth roots; it just so happens for quintics we need to add two additional functions rather than one.
Not quite. No solution exists that uses a very restricted set of functions deemed "closed-form", in particular sums, products, quotients and n'th radicals. These polynomials can still be solved analytically and in closed-form by introducing some additional special functions. Certainly there are many ways forward rather than "trial and error methods," which I interpret as meaning the answer must be approximated numerically.
For instance, all polynomials can be solved analytically and in closed form if elliptic functions are allowed to exist in the solution.
Or as a simpler example, the quintic x⁵+x+a has no closed form solution in radicals, and is in some sense the prototypical example of an unsolvable quintic. This polynomial has one unique real root, which is a function of the variable a. In fact, we can look at this root as a function of a; this is called the "Bring radical" of a, denoted BR(a), and easily see it is a very simple, well-behaved, and perfectly "valid" analytic function of a. It is in some sense a sister function to the ordinary real fifth root of a, denoted ⁵√a, which would instead be the unique real root of the polynomial x⁵-a. The two are also just about equally easy to compute numerically to arbitrary precision. If we allow BR(a) to "exist" as a function worthy of being deemed "closed-form," "analytic" or what have you, then every quintic now has a closed form solution in terms of radicals and this one extra special function.
This somewhat important detail is often omitted when explaining this. People often write the idea that there "is no general solution" to the quintic, which is misleading at best or wrong at worst. Perhaps a good analogy is to think back to the days when all numbers were thought to be rational. In such a system, even quadratic polynomials "have no analytic solution", one needs to invent the square root function to express the roots of the quadratic in closed form. The same thing happens for cubic and quartic polynomials, where we add cube roots and fourth roots; it just so happens for quintics we need to add two additional functions rather than one.
> If we allow BR(a) to "exist" as a function worthy of being deemed "closed-form," "analytic" or what have you, then every quintic now has a closed form solution in terms of radicals and this one extra special function.
At first I thought this was smoke and mirrors: define a function R(a, b, c, d, e, f) to be the (say, smallest) root of ax^5 + bx^4 + cx^3 + dx^2 + ex + f and now have a solution to every quintic (if we allow R in your solution)!
But your point about BR(a) being about as easy to numerically compute as ⁵√a is really where you started to change my mind, because of course that's what we end up caring about if we want to solve any real-world problem that involves finding the roots of a quintic.
Are you saying that we could write down one unique "quintic formula" that is the same for every quintic, using sums, products, quotients, n'th radicals, and BR? If so, this is a really important point that everyone who studies polynomials should understand. Or do you still need some "trial and error" to reduce an arbitrary quintic to a form that can be solved using BR?
At first I thought this was smoke and mirrors: define a function R(a, b, c, d, e, f) to be the (say, smallest) root of ax^5 + bx^4 + cx^3 + dx^2 + ex + f and now have a solution to every quintic (if we allow R in your solution)!
But your point about BR(a) being about as easy to numerically compute as ⁵√a is really where you started to change my mind, because of course that's what we end up caring about if we want to solve any real-world problem that involves finding the roots of a quintic.
Are you saying that we could write down one unique "quintic formula" that is the same for every quintic, using sums, products, quotients, n'th radicals, and BR? If so, this is a really important point that everyone who studies polynomials should understand. Or do you still need some "trial and error" to reduce an arbitrary quintic to a form that can be solved using BR?
Yes, using a purely mechanical process every quintic can be solved in closed form this way. The usual method isn't all that different from the way the quartic is solved. You do a change of variables to eliminate the x⁴ term, and then a few more simple changes of variables will get it to the Bring normal form, for which the solution is the Bring Radical. Then you can unwind the changes of variables to get a closed form expression in the original variable x. Each step is totally mechanical and involves no "trial and error" at all.
The only issue is that the resulting expression can be extremely large once you unwind the change of variables. It's kind of similar to taking (for instance) a small C++ program and explicitly expanding every macro or function with a copy of the entire function body, producing a huge space increase. You are usually better off leaving things in terms of the transformed variable, along with the formulas to convert back to the each previous variable. This is also an issue with the solution to the general quartic, though, so it's neither here nor there regarding Bring radicals.
The only issue is that the resulting expression can be extremely large once you unwind the change of variables. It's kind of similar to taking (for instance) a small C++ program and explicitly expanding every macro or function with a copy of the entire function body, producing a huge space increase. You are usually better off leaving things in terms of the transformed variable, along with the formulas to convert back to the each previous variable. This is also an issue with the solution to the general quartic, though, so it's neither here nor there regarding Bring radicals.
He's stumbled onto the symmetric polynomials from Newton. It's part of a deeply fascinating area of mathematics with an astounding number of non-trivial results.
Knowing stuff about them let's you get powers of polynomials easily, or know certain things about roots (is there a real one? What can you tell about the signs? Lots of neat identities for special kinds of matrices...)
The "coeffs from roots" stuff is pretty straightforward to prove.
"Symmetric polynomials arise naturally in the study of the relation between the roots of a polynomial in one variable and its coefficients" [1]
[1] https://en.wikipedia.org/wiki/Symmetric_polynomial
Knowing stuff about them let's you get powers of polynomials easily, or know certain things about roots (is there a real one? What can you tell about the signs? Lots of neat identities for special kinds of matrices...)
The "coeffs from roots" stuff is pretty straightforward to prove.
"Symmetric polynomials arise naturally in the study of the relation between the roots of a polynomial in one variable and its coefficients" [1]
[1] https://en.wikipedia.org/wiki/Symmetric_polynomial
The formula given on the page appears to take an exponential number of multiplications. That seems excessively inefficient.
In a finite field, at least, one could compute 2n syndromes (sums of the roots raised to 1st through 2n-th power) and then use the berlekamp massey to recover the polynomial. Would take O(n^2) operations overall. If it works over the reals I'm not sure how stable it would be numerically.
But I'm sure there has to be an more efficient approach than an exponential one. :)
In a finite field, at least, one could compute 2n syndromes (sums of the roots raised to 1st through 2n-th power) and then use the berlekamp massey to recover the polynomial. Would take O(n^2) operations overall. If it works over the reals I'm not sure how stable it would be numerically.
But I'm sure there has to be an more efficient approach than an exponential one. :)
Pieter Wuille pointed out to me that you can:
def coeffs_from_roots(roots):
coefs=[1]
for r in roots:
coefs=[-r*coefs[0]] + [coefs[i]-r*coefs[i+1] for i in range(len(coefs)-1)] + [1]
coefs.reverse()
return coefs
It's not hard to intuit why this formula works, it's basically a combinatorial proof.
For every summand, we select either x or the negated root from every factor. This explains the alternating signs as well as the fact that adding up the exponent of x and the number of factors that go into the coefficient always results in the number of roots.
Then, of course, we still need to group summands with the same exponent.
For every summand, we select either x or the negated root from every factor. This explains the alternating signs as well as the fact that adding up the exponent of x and the number of factors that go into the coefficient always results in the number of roots.
Then, of course, we still need to group summands with the same exponent.
https://en.wikipedia.org/wiki/Vieta%27s_formulas