Wildberger: Solving the General Polynomial Equation

Welcome! This topic is dedicated to the series of videos Explore Research Levels Maths: Solving Polynomial Equations by Norman Wildberger, launched in early 2021. Here’s a link to the YouTube playlist:

I applied a similar algebraic proof for BiTriQuad as in the BiTrinomial(see comments in Norman’s video Solving Equations 14)in order to prove that is an integer number.

Note that our BiTriQuad formula can be written also as:

A= \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} } \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{m_{3}+m_{4}}{m_{3}} \frac{1}{1 + m_{2} + 2m_{3} + 3m_{4}}

First of all I form, as before the following terms:

A_1 = \binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} }

A_2 = \binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}+1}{m_{2}+2m_{3}+3m_{4}+1 }

Then, I form the term:

2A_{1}- A_{2}= 2\binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} } - \frac{2m_{2} + 3m_{3}+4m_{4}+1 }{1 + m_{2} + 2m_{3} + 3m_{4}} \binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} } =

\frac{m_{3}+2m_{4}+1 }{1 + m_{2} + 2m_{3} + 3m_{4}} \binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} } =
\frac{m_{3}+2m_{4} }{1 + m_{2} + 2m_{3} + 3m_{4}} \binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} } + \frac{1}{1 + m_{2} + 2m_{3} + 3m_{4}} \binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} } =

Then  I define,


A_0 =\binom{m_{3}+m_{4}}{m_{3}} \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} }

\frac{m_{3}+2m_{4} }{1 + m_{2} + 2m_{3} + 3m_{4}} A_0 + A = \frac{m_{3} }{1 + m_{2} + 2m_{3} + 3m_{4}} A_0 + 2\frac{m_{4} }{1 + m_{2} + 2m_{3} + 3m_{4}} A_{0} + A =

Now, in the following step I expand the
A_0 term and I get,

\frac{(2m_{2}+ 3m_{3}+4m_{4})! m_{3} }{(1 + m_{2} + 2m_{3} + 3m_{4})! m_{2}! m_{3}! m_{4}!} + 2\frac{(2m_{2}+ 3m_{3}+4m_{4})! m_{4} }{(1 + m_{2} + 2m_{3} + 3m_{4})! m_{2}! m_{3}! m_{4}!} + A =

\frac{(2m_{2}+ 3m_{3}+4m_{4})! }{(1 + m_{2} + 2m_{3} + 3m_{4})! m_{2}! (m_{3}-1)! m_{4}!} + 2\frac{(2m_{2}+ 3m_{3}+4m_{4})! }{(1 + m_{2} + 2m_{3} + 3m_{4})! m_{2}! m_{3}! (m_{4}-1)!} + A

Finally, I define: A_{3} =\frac{(2m_{2}+ 3m_{3}+4m_{4})! }{(1 + m_{2} + 2m_{3} + 3m_{4})! m_{2}! (m_{3}-1)! m_{4}!} and

A_{4} = \frac{(2m_{2}+ 3m_{3}+4m_{4})! }{(1 + m_{2} + 2m_{3} + 3m_{4})! m_{2}! m_{3}! (m_{4}-1)!}

If I add up the denominators and nominators for the A_3 and A_{4} terms they are equal. As a result, they can be expressed as Binomials coefficients and they are integers(see Norman’s Solving Polynomial Eqns 10 at 18 minute) ).

So, we have 2A_{1} - A_{2}= A_{3} + A_{4} + A
Since, A_{1}, A_{2}, A_{3}, A_{4} are integers. As a result, A is an integer which represents the BiTriQuad formula as it is defined above.

1 Like

I know It is alot of details but I want to share within the community since mistakens can happen or there can be a better proof.

That looks about right to me.

And I’ve just spotted your comment about [1401.7194] Polygonal Dissections and Reversions of Series Just skimming through it I can see they got a similar formula that I’ve found too (and Chris found a slightly simplified version of it in [1404.3395] Nested sets, set partitions and Kirkman-Cayley dissection numbers, see comments under The Quartic equation and BiTriQuad numbers | Solving Polynomial Eqns 15 | Wild Egg Maths - YouTube ):

This was my version:

n = 1 + m1 + 2*m2 + 3*m3 + ....  # (n+1)-gon with m1 triangles, m2 quads, etc
k = m1 + m2 + m3 + ...  # (k-1) diagonals
n+k = 1 + 2*m1 + 3*m2 + ...
multinomial(m1,m2,m3,...) * binomial(n+k, k) / (n+k)


And in theirs n just appears to be shifted by one:

n = m1 + 2*m2 + 3*m3 + ....  # (n+2)-gon with m1 triangles, m2 quads, etc
k = m1 + m2 + m3 + ...  # (k-1) diagonals
multinomial(m1,m2,m3,...) * binomial(n+k, k) / (n+1)  # instead of m1 they are using k1 in the paper


When calculating some concrete values both give the same results.

[1401.7194] Polygonal Dissections and Reversions of Series seems to be the most relevant paper to this subject so far!

(Sorry about the formatting, I just copied these from earlier replies and I don’t know latex too well either)

Re [1401.7194] Polygonal Dissections and Reversions of Series the formula I mentioned above is the a_{λ} term (i.e. one specific dissection) and they also talk about a_{n} (and later it’s also referred to as s_{n}) that gives all possible dissections. But I can’t decipher how exactly they compute a_{n}.

One way is that the integer solutions for n = m1 + 2*m2 + 3*m3 + ... for an (n+2)-gon will give all possible dissections, so you can calculate a_{λ} for each of those and add it up. I’ve tried this method already but SymPy gives only parametric solutions, which is not helpful. It might work with Sage or some more serious CAS though. Brute forcing it works too but gets slow very quickly. But this might not be the most interesting thing to do because it’s easier to sum up the Kirkman-Cayley formulas instead which seems to give a_{n} as well: https://colab.research.google.com/drive/1whYFIjz19bvRnvZOYEQ2t94MDwHPBWh8#scrollTo=3JAfY8xn9pHT&line=1&uniqifier=1

Anyway, it might be more interesting now to start getting back to solving equations somehow. This is slightly beyond my comprehension but in Theorem 3.4 it’s spelled out how a_{n} is related to the inversion of a simple power series. Looking into what “reverse series” are exactly this is similar to the transformation we’ve started with at the beginning with c_{0}t: Series Reversion -- from Wolfram MathWorld

I don’t know what you mean by saying “to start getting back to solving equations somehow” . But in the video 6 : On to the quartic equation! | Solving Polynomial Equations 6 | Wild Egg I gave a python program which calculates all the coefficients to solve an equation of degree n. Only small modifications are needed to calculate the terms and add them.

Hi Alain, I was thinking that we have at least two papers now that say that this formula is in fact the dissection of polygons, so that seems well established at this point (in the videos published so far that’s still only a conjecture) and I’m just eager to figure out what’s the next step.

Looking at your program: I can run it and the numbers in it look familiar but I’m not entirely sure what’s it calculating. It has factors of c_{i} so it’s similar to the terms that appear in a given solution but there’s no c_{0} and it’s not dividing by c_{1} either. So if I try order=4 and max_n=9 that looks similar to the terms in the quartic solution that appears here: https://youtu.be/t-X6i2uiTo8?t=219 but it’s not the same. Do you mean that it could be modified to match that?

Outch !

You’re 100% right. I made a mistake with the powers of Ci.
Here the new version of the program. I have checked with an equation of degree 5.
The python program and the SAGEmath proc give the same results.
And I solved equation. It works (when the serie converges of course)

After this double check, it should be ok !

######################### PYTHON VERSION ###################################
#
# integer partitions (sum = n, number of term = k, maximal integer in the partition = m
#
def partitions(n, k, m):
if k == 1:
yield [n]
return
for f in range(n-k+1 if (m > n-k+1) else m, (n-1)//k, -1):
for p in partitions(n-f, k-1, f): yield [f] + p
#
# n!
#
def fact(n):
r=1
while (n>1):
r=r*n
n-=1
return (r)
#
# generation of a monomial of rank n in the polynomial of degree dim
#
def list_monomials(n,dim):
for i in partitions(2*n-1,n,dim):
ni=[]
for ii in range(dim):
t=0
for j in i:
if j==ii+1:
t+=1
ni.append(t)
num=2*n-2
r=1
for ii in range(1,dim):
num-=(ii-1)*ni[ii]
r*=fact(ni[ii])
if ni[0]%2==0:
coef=fact(num)//r//fact(n)
else:
coef=-fact(num)//r//fact(n)
li="="+str(coef)
ss=n
li=li+"*c0^"+str(n)
for kk in range(1,dim):
ss+=ni[kk]
li=li+"*c"+str(kk+1)+"^"+str(ni[kk])
li=li+'/c1^'+str(ss)
print (li)
#
# list of all nomonial (from 1 to x)
#
degree=4
order=9
for i in range(1,order):
list_monomials(i,degree)

############################# SAGE MATHS Proc  ###############################
[var("c%d" % i) for i in [0..5]]
[var("a%d" % i) for i in [0..20]]
t,x,y = var('t','x','y')
x=a0+a1*t+a2*t^2+a3*t^3+a4*t^4+a5*t^5+a6*t^6+a7*t^7+a8*t^8+a9*t^9+a10*t^10+a11*t^11+a12*t^12+a13*t^13+a14*t^14
y=t+c1*x+c2*x^2+c3*x^3+c4*x^4+c5*x^5
z=y.expand().collect(t)
li1=[a0==0]
for i in range(14):
li1.append(z.coefficient(t,i+1)==0)
zz=solve(li1,a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14)
for j in range(14):
a= zz[0][j]
b=(a*c0^j).right().expand()
print(b)

Hi all. I think we’ve started with a good summary of contributions so far. And I’m glad we have your code here, Alain. I missed this on YouTube. (I’m also quite pleased with the scrolling code box provided on this forum!).

In my recent explorations I’ve been interested in the fact that integer partitions come into play in our general equation. I’ve been wondering about the relationship between integer partitions and our m-values in the BiTriQuad…equation, and I’ve happened upon a connection that I can describe but cannot explain.

The general pattern of our coefficients, as they relate to polygonal dissections, is becoming clear to us. As we increase the degree of the polynomial, finding our coefficients requires that we dissect a polygon to a greater degree of refinement. If the degree of our equation is larger than the size of a polygon, then we achieve the complete decomposition of that polygon. For the case of the 7-gon, if the degree of our equation is greater than 7, our coefficients will include 1, 7, 7, 28, 28, 84, 42 where 1 is the polygon dissected by 0 diagonals leaving the 7-gon whole……all the way to our Catalan dissection into all triangles.

I’ve been looking at these complete polygonal dissections (which appear a few places in OEIS, like A111785) and noticed a pattern. If you count the number of terms in the complete polygonal decompositions, we get the sequence 1, 1, 2, 3, 5, 7, 11, 15, which appears to be A000041, the number of integer partitions of n. If we wanted to calculate the coefficients corresponding to a particular polygon using the BiTriQuad, we would need a similar number of collections of m-values. I wondered if there might be a way that these two sets of values correspond. Here are the m-values needed to calculate the dissections of the 7-gon along with a speculative pairing with the partitions of 5.

Partition m-values Coefficient
{5} 5, 0, 0, 0, 0 42
{4, 1} 3, 1, 0, 0, 0 84
{3, 2} 1, 2, 0, 0, 0 28
{3, 1, 1} 2, 0, 1, 0, 0 28
{2, 2, 1} 0, 1, 1, 0, 0 7
{2, 1, 1, 1} 1, 0, 0, 1, 0 7
{1, 1, 1, 1, 1, 1}} 0, 0, 0, 0, 1 1

Staring at this table, I notice that you can map partitions to m-values with this simple algorithm: subtract all the partition numbers pairwise.

i.e, with partition {3,1,1} → 3-1,1-1,1-0,0-0,0-0 → 2,0,1,0,0

So the conjecture is that there is a one-to-one mapping of partitions of n-2 and the m-values corresponding to the dissections of the n^{th} polygon.

I have no idea why this is.

[UPDATE] This entry Partition -- from Wolfram MathWorld has clarified the issue for me. Partitions are the set of all solutions to the Diophantine equation 1j_1+2j_2+3j_3+...+nj_n=n, which we recognize from our coefficient expressions (and which Balazs points out are also the dissections of a poly). Our m-values are just the j-values.

Apologies for the long-winded route to my understanding.

Yes, it looks like Norman’s technique is a truncated version of this reversion of series.

Thank you, that program does give the same results now! (only in different order compared to the video)

I don’t fully understand how exactly it’s doing it yet but looks interesting!

Re A000041 - OEIS I wasn’t aware of these and it does give the number of different kinds of dissections! It also matches the numbers I’m getting in the google colab script I’ve linked earlier (in the all_tilings_for_ngon function I added a note). I thought this was just a random diophantine equation but it’s quite well known apparently.

Re A111785 - OEIS “Array used for power series inversion (sometimes called reversion)”

This is quite interesting too! It has very similar values compared to what we get when writing out a solution for x but it’s not exactly same (e.g. https://youtu.be/t-X6i2uiTo8?t=219 or when running Alain’s script).

Well, at least for me, this a lot to read up on already!

Yes, I feel like I’m drowning in ideas and don’t know which way to swim.

I suspect that the values don’t match Norman’s because he’s only calculating the BiTriQuad coefficients in this video. To get all the terms that correspond to, say, the complete 7-gon decomposition, I think we’d need to be computing the values for the BiTriQuadPentHexHept equation. That’s how I’m imagining the generalization, but that’s just unverified intuition at this point.

I think you’re right, looks like I’m getting more and more similar values to A111785 as I increase the degree variable in Alain’s script.

1 Like

More explanations on my python program.

1) def partitions(n, k, m):
This is the creation of an iterator. It creates loops. And for each iteration, this iterator generates a integer partition with constraints:

Example of usage, if you run the following program:

for i in partitions (11,6,4):
print(i)


The result is:

[4, 3, 1, 1, 1, 1]
[4, 2, 2, 1, 1, 1]
[3, 3, 2, 1, 1, 1]
[3, 2, 2, 2, 1, 1]
[2, 2, 2, 2, 2, 1]

For each iteration, the print fonction displays an integer partition of 11, containing 6 integers less or equal 4.

2) def fact(n):
This is the definition of the factorial function. No special comment on it here.

3) def list_monomials(n,dim):
It generates for a given degree (dim=3 for cubic equation for instance) all terms of rank n. In this case, n is the power of the term c_0 in the generated monomials.

As you can see, the heart of this program is a loop on the integer partitions of 2n-1 with n integers less than dim. And of course, for each partition, a monomial is generated as follow:

Block 1 :

ni=[]
for ii in range(dim):
t=0
for j in i:
if j==ii+1:
t+=1
ni.append(t)


This part counts how many times each integer appears in the partition and store the results in an array. For instance, if we want to display all monomials of a equation of degree 4 of rank 6 (with c_0^6), it iterates with partitions(11,6,4) and produces (as already shown) partitions and corresponding arrays:

[4, 3, 1, 1, 1, 1] => array = [4,0,1,1]: four 1, zero 2, 1 three, 1 four
[4, 2, 2, 1, 1, 1] => array = [3,2,0,1]
[3, 3, 2, 1, 1, 1] => array = [3,1,2,0]
[3, 2, 2, 2, 1, 1] => array = [2,3,1,0]
[2, 2, 2, 2, 2, 1] => array = [1,5,0,0]

Except for the first one, these numbers are our m, m_2, m_3, m_4, … m_{dim}

Block 2
This is the generation of the integer coefficient BiTriQ…:

num=2*n-2
r=1
for ii in range(1,dim):
num-=(ii-1)*ni[ii]
r*=fact(ni[ii])
if ni[0]%2==0:
coef=fact(num)//r//fact(n)
else:
coef=-fact(num)//r//fact(n)

Coef = \frac{(-1)^m \times (2n-2 - m_2 - 2m_3 - 3m_4...-(dim-1)\times m_{dim})!} { n! \times m_1! \times m_2! ... \times m_{dim}!}

Block 3
This is the set up of mononial. Nothing really special here…

Coef \times \frac {c_0^n \times c_2^{m_2} \times c_3^{m_3}.....* c_{dim}^{m_{dim}}} {c_1^{n+m_2+m_3+...m_{dim}}}

4) General loop
Loop for all mononials of a given degree

1 Like

Thanks for the clarification, Alain. Can you recommend a simple Python environment for a newcomer to Python?

The syntax for displaying math is nicely explained here: Discourse Math Plugin - plugin - Discourse Meta. In short, just replace  with dollar signs.

Thanks for the latex help. I will update my post with nice expressions in latex.
Concerning Python, it’s not very complicated. Download the last python version 3.9.x. I work with IDLE (the standard environnement). Already installed with Python.
You can find a first introduction here Python - A first introduction to the Python IDLE Interface - YouTube

Best,

Hi guys!

I think, I have clarified some stuff relative to the paper Polygonal dissections and reversions of series by Alison Schuetz and Gwyn Whieldon and matched our

Note, that our BiTriQuad formula can be written is:

A= \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+2m_{3}+3m_{4} } \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{m_{3}+m_{4}}{m_{3}} \frac{1}{1 + m_{2} + 2m_{3} + 3m_{4}}

which can be written also as :

A= \binom{2m_{2}+ 3m_{3}+4m_{4}}{m_{2}+m_{3}+m_{4} } \binom{m_{2}+ m_{3}+m_{4}}{m_{2} } \binom{m_{3}+m_{4}}{m_{3}} \frac{1}{1 + m_{2} + 2m_{3} + 3m_{4}}.

Our polygon is the m_{2} + 2 + 2m_{3} + 3m_{4} - gon while in the paper is the n+2-gon with m_{2},m_{3},m_{4} representing the number of triangles, quadrilaterals and pentagons, respectively.
So, n= m_{2} +2m_{3} + 3m_{4}. Then, specific values of m_{2},m_{3},m_{4} correspond to a specific partition λ of n. Note, that the dissection is the set (d_1=2,d_2=3,d_3=4) with j being j ={1,2,3}.
Then, goto to formula in Lemma 3.2. The k variable then can be identified as k = m_{2} + m_{3} + m_{4} where k_{1} -> m_{2} , k_{2} -> m_{3} and k_{3} -> m_{4}. As a result, the above formula our BitTriQuad ,corresponds to a specific partition of λ.

Let me also explain the right most figure 7 which corresponds to a pentagon. So, n+2=5 => n=3 and the set of dissections we choose is (d_1=2,d_2=3) and j ={1,2}.
So, n according to the condition in Lemma 3.2 becomes, n=k_1 + 2 k_2 or 3 = k_1 + 2 k_2 with k_1, k_2 being the number of triangles and quadrilaterals, respectively. Then, there are two λ partitions of n=3 and that is λ_1 = 3+0 and λ_2 = 1+2 which can be written as λ_1 = 3 (2-1)+0(3-1) and λ_2 = 1(2-1) +1(3-1). As a result, we can recognize two possible sets of k_1, k_2 which corresponds to two partititions and that sets are k_1=3, k_2=0 and k_1=1, k_2=1. So, the total number of cases will be the sum of the corresponding binomial formula (or if you prefer our BiTri formula) for these two partitions!

I hope it is clarified, if there is a mistake, please let know!

Let’s see you matrix example! You are examining a 7 degree polynomial since you have 5 m-values , that means the variables m_1 for triangles, m_2 for quadrilaterals , m_3 for pentagons, m_4 for hexagons and m_5 for ceptagons. Also your polygon example is a ceptagon that is a 5+2gon so, according to the paper where they are examining a n+2 gon . The value n in general satisfies the equation in Lemma 3.2 which in our case is :

n = m_1(d_1-1) + m_2(d_2-1) + m_3(d_3-1) + m_4(d_4-1) + m_5(d_5-1)

but the set of dissections is d=(d_1=2, d_2=3,d_3=3, d_4=4, d_5=5). So, the above equation for n =5 becomes:

5= m_1+ 2m_2 + 3m_3 + 4 m_4 + 5m_5

Now, we are searching the partitons of 5 into m_1,m_2,m_3,m_4,m_5 according to the above equation which are the m- values that you are showing. Note, that the factors in front of m_1,m_2,m_3,m_4,m_5 are just the number of dissections e .g . for triangles you have d_1=2 so the factor in front of m_1 is just d_1-1=2-1=1 . The number d_1=2 represents the d_1+1 =2+1=3 -gon (triangle) that appears in our polygon. The same idea of course applies for the cases d_2=3, d_3=4, d_4=5, d_5=6.

I agree also with ur comment that the BiTriQuad formula is a truncated version relative to reverse series version. I think it corresponds to one specific partition λ relative to the factor \alpha_λ

1 Like