SPE22

In [22]:

import numpy as np
import sympy as sp
import pickle
from IPython.display import HTML, Image
import ipywidgets as widgets
import matplotlib as mpl
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
mpl.rcParams['legend.fontsize'] = 10
import pandas as pd
import itertools
pd.set_option('display.max_colwidth', None)
import treelib as tr


# function to print latex
def renderListToLatex(e):
    latex_rendering = []

    for i in range(len(e)):
        latex_rendering.append("$$" + sp.latex(e[i]) + "$$")
    
    return(HTML("".join(latex_rendering[0:])))

Solving Polynomial Equations (22)¶

Aim: Explore bridge between BiTri numbers and polygonal subdivisions

Methodology: Consider the structure of the first row of numbers in the matrix of coefficients returned by the function $C$

Observe: Recall the solution to a general cubic equation from a previous notebook.

$$C(m, n) \equiv \frac{(2m + 3n)!}{(1 + m + 2n)!m!n!}$$

Let $F1$ for a function that implements $C$.

In [23]:

def F1(m2, m3, returnCoefficientsOnly = False, returnCoefficientsOnlyWithoutSigns = True, returnCoefficientsAsFactorialStrings = False):
    c_0, c_1, c_2, c_3 = sp.symbols('c_0, c_1, c_2, c_3')
    s1 = (-1)**(m3 + 1)
    s2 = sp.factorial(2 * m2 + 3 * m3)
    s3 = sp.factorial(1 + m2 + 2 * m3) * sp.factorial(m2) * sp.factorial(m3)

    
    s4 = c_0**(1 + m2 + 2 * m3) * c_2**m2 *c_3**m3
    s5 = c_1**(2 * m2 + 3 * m3 + 1)
    
    s7 = str(2 * m2 + 3 * m3) + "!"
    s8 = str(1 + m2 + 2 * m3) + "!" + str(m2) + "!"  + str(m3) + "!"
    
    if returnCoefficientsOnly:
        s6 = s1 * (s2 / s3)
    elif returnCoefficientsOnlyWithoutSigns:
        s6 = (s2 / s3)
    elif returnCoefficientsAsFactorialStrings:
        s6 = str(s7 + " | " + s8)
    else:
        s6 = s1 * (s2 / s3) * (s4 / s5)

    return(s6)

Let $P3$ be a matrix of values relating the part of the formula that calculates unsigned coefficients: $ \frac{(2m + 3n)!}{(1 + m + 2n)!m!n!}$

In [24]:

P1 = np.arange(8)
P2 = np.array([[F1(j, i) for i in P1] for j in P1])
P3 = sp.Matrix(P2)
P3

Out[24]:

$\displaystyle \left[\begin{matrix}1 & 1 & 3 & 12 & 55 & 273 & 1428 & 7752\\1 & 5 & 28 & 165 & 1001 & 6188 & 38760 & 245157\\2 & 21 & 180 & 1430 & 10920 & 81396 & 596904 & 4326300\\5 & 84 & 990 & 10010 & 92820 & 813960 & 6864396 & 56241900\\14 & 330 & 5005 & 61880 & 678300 & 6864396 & 65615550 & 600900300\\42 & 1287 & 24024 & 352716 & 4476780 & 51482970 & 551170620 & 5588372790\\132 & 5005 & 111384 & 1899240 & 27457584 & 354323970 & 4206302100 & 46835886240\\429 & 19448 & 503880 & 9806280 & 159352050 & 2283421140 & 29804654880 & 361913666400\end{matrix}\right]$

Observe: It is not a given that the solutions to cubic equation should be related to BiTri numbers and more investigation is needed.

Definition: A BiTri Roofed Polygon consists of a polygon subdivided diagonally into traingles, with a distinguised (top) edge.

Conjecture: The numbers $C(n, m)$ give us a power series solution to a general cubic equation, and they count the number of BiTri polygons with $m$ triangles and $n$ quadrilaterals, with $1 + m + 2n$ vertices

Let $F2$ be a function that returns the number of vertices for polygons in $P3$.

Let $P6$ be an $8 \times 8$ array of the number or vertices in $P3$

In [26]:

P4 = np.arange(8)
P5 = np.array([[F2(j, i) for i in P4] for j in P4])
P6 = sp.Matrix(P5)
P6

Out[26]:

$\displaystyle \left[\begin{matrix}2 & 4 & 6 & 8 & 10 & 12 & 14 & 16\\3 & 5 & 7 & 9 & 11 & 13 & 15 & 17\\4 & 6 & 8 & 10 & 12 & 14 & 16 & 18\\5 & 7 & 9 & 11 & 13 & 15 & 17 & 19\\6 & 8 & 10 & 12 & 14 & 16 & 18 & 20\\7 & 9 & 11 & 13 & 15 & 17 & 19 & 21\\8 & 10 & 12 & 14 & 16 & 18 & 20 & 22\\9 & 11 & 13 & 15 & 17 & 19 & 21 & 23\end{matrix}\right]$

Observe: The above matrices show that there are, for example, 10010 ways to subdivide roofed 11-gons into 3 triangles and 3 quadrilaterals.

Observe: The above conjecture proposes a way to to unify a fundamental problem of algebra with large scale extension of Catalan and Fuss numbers.

Observe: To investigate further it will be required to extend the binary and ternary operations seen in previous notebooks to BiTri roofed polygons.

Observe: Recall that $ \overline{\triangledown} \text{ }(P, Q) = P \text{ } \overline{\triangledown} \text{ } Q $ is a binary operation that appends $P$ and $Q$ to left and right sides of a roofed central triangle, where $P$ and $Q$ are BiTri rooted polygons.

Observe: It is possible to extend the operation, $\overline { \triangledown }$ to BiTri rooted polygons.

Observe: To make this extension a symbol$ \overline{\square}$ can be used.

Observe: The symbol can be used in the context of the operation $ \overline{\square} \text{ }(P, Q, R) $ relating to BiTri roofed polygons, where 3 polygons can be be glued on to central quadrilateral.

Observe: The BiTri roofted polygons are then closed under the two operations, $\overline{\triangledown}$ and $\overline{\square}$.

Todo: Create functions for both of these operations, notign that vertical is showing how many triangles, and horizontal is showing how many quadrilaterals.

Observe: These polygons can be viewed in a multset array and it is possible to do consistent arithmetic with them.

Reference: The approach is related to Q22 of Ch. 7 in Concrete Mathematics (Knuth et al) which considers multiset operations of the BiTri roof polygons.

Aim: Demonstrate an identity of multisets

Let $A$ be the entire Mset of BiTri rootfted polygons. It follows that:

$$A = | + \overline{\triangledown}(A, A) + \overline{\square}\text{ }(A, A, A)$$

Observe: This is a fundamental identity of multisets.

Observe: Both operations can be used to compute all numbers in this array.

Observe: It is possible to link the abstract algebra of MSets to polynomials. To make this link, the symbol $\psi$ can be used to count the number of triangles, and the symbol $q$ can be used to count the number of quadrilaterals.

Observe: The $\psi$ mapping from BiTri roofed polygons can be extended to polynomials in $t$ and $q$:

$$ \psi(P) \equiv t^m q^n $$

where$P$ has $m$ triangles and $n$ quadrilaterals

Example

$$ \psi \text{ (some polygon with 2 triangles and 2 quadrilaterals)} = t^2 q^2 $$

Observe: This will lead to the following properties (and note the extra $t$ and extra $q$ that arises here).

$$ \psi(\overline{\triangledown}(P, Q) = t \psi (P) \psi(Q) $$

$$\psi(\overline{\square} \text{ }(P, Q, R) = q \psi(P) \psi(Q) \psi(R) $$

Observe: If $\psi(A) \equiv F$ where $F$ is an MSet, and noting that $A = | + \overline{\triangledown}(A, A) + \overline{\square}\text{ }(A, A, A)$, the $\psi$ operation will replace each polygon in the array with powers of $t$ and $q$ where those powers represent the number of triangles and quadrilaterals.

Example: The number $28$ in the above array becomes $tq^2$ under this $\psi$ mapping.

Observe: the operation $F = 1 + tF^2 + qF^3 $ capures all the operations plus addtional triangle.

Observe The expression above cubic equation in $F$. Note this is close to a general cubic equation, and helps to explain why there is a relationship between solutions to cubic equations and the BiTri roofed polygons.

Aim: Check to see if the BiTri Array satisfies the above identities.

In [27]:

P7 = np.arange(6)
P8 = np.array([[F1(j, i) for i in P7] for j in P7])
P9 = sp.Matrix(P8)
P9

Out[27]:

$\displaystyle \left[\begin{matrix}1 & 1 & 3 & 12 & 55 & 273\\1 & 5 & 28 & 165 & 1001 & 6188\\2 & 21 & 180 & 1430 & 10920 & 81396\\5 & 84 & 990 & 10010 & 92820 & 813960\\14 & 330 & 5005 & 61880 & 678300 & 6864396\\42 & 1287 & 24024 & 352716 & 4476780 & 51482970\end{matrix}\right]$

Let $t$ and $q$ be unknown types

Let $P10$ and $P11$ be matrices.

Let $P12$ be the matrix multiplication of $P10 \times P9 \times P11$.

In [31]:

P12 = sp.expand(P10 * P9 * P11)[0]
P12

Out[31]:

$\displaystyle 51482970 q^{5} t^{5} + 6864396 q^{5} t^{4} + 813960 q^{5} t^{3} + 81396 q^{5} t^{2} + 6188 q^{5} t + 273 q^{5} + 4476780 q^{4} t^{5} + 678300 q^{4} t^{4} + 92820 q^{4} t^{3} + 10920 q^{4} t^{2} + 1001 q^{4} t + 55 q^{4} + 352716 q^{3} t^{5} + 61880 q^{3} t^{4} + 10010 q^{3} t^{3} + 1430 q^{3} t^{2} + 165 q^{3} t + 12 q^{3} + 24024 q^{2} t^{5} + 5005 q^{2} t^{4} + 990 q^{2} t^{3} + 180 q^{2} t^{2} + 28 q^{2} t + 3 q^{2} + 1287 q t^{5} + 330 q t^{4} + 84 q t^{3} + 21 q t^{2} + 5 q t + q + 42 t^{5} + 14 t^{4} + 5 t^{3} + 2 t^{2} + t + 1$

Let $P12$ be the identity $$F = 1 + tF^2 + qF^3 $$

Let $P13$ be a verification that this holds up to degree 5

In [32]:

P13 = sp.expand(1 + t * P12**2 + q * P12**3).series(q, 0, 6).removeO()
P13

Out[32]:

$\displaystyle q^{5} \left(330184434888 t^{15} + 247546793655 t^{14} + 126113913900 t^{13} + 55511341386 t^{12} + 56669944821 t^{11} + 26492266317 t^{10} + 8573240311 t^{9} + 2452174534 t^{8} + 690892315 t^{7} + 257709636 t^{6} + 51482970 t^{5} + 6864396 t^{4} + 813960 t^{3} + 81396 t^{2} + 6188 t + 273\right) + q^{4} \left(11789879751 t^{15} + 9429920370 t^{14} + 5141401668 t^{13} + 2428662489 t^{12} + 2982944547 t^{11} + 1477086369 t^{10} + 517154188 t^{9} + 161691066 t^{8} + 50285736 t^{7} + 20974575 t^{6} + 4476780 t^{5} + 678300 t^{4} + 92820 t^{3} + 10920 t^{2} + 1001 t + 55\right) + q^{3} \left(335837502 t^{15} + 287837550 t^{14} + 168778863 t^{13} + 86023326 t^{12} + 134393307 t^{11} + 70879854 t^{10} + 27042746 t^{9} + 9325552 t^{8} + 3237501 t^{7} + 1532286 t^{6} + 352716 t^{5} + 61880 t^{4} + 10010 t^{3} + 1430 t^{2} + 165 t + 12\right) + q^{2} \left(6810804 t^{15} + 6286896 t^{14} + 3987144 t^{13} + 2206512 t^{12} + 4872150 t^{11} + 2754870 t^{10} + 1155250 t^{9} + 444241 t^{8} + 174610 t^{7} + 95577 t^{6} + 24024 t^{5} + 5005 t^{4} + 990 t^{3} + 180 t^{2} + 28 t + 3\right) + q \left(74088 t^{15} + 74088 t^{14} + 51156 t^{13} + 30968 t^{12} + 126546 t^{11} + 77322 t^{10} + 36011 t^{9} + 15654 t^{8} + 7095 t^{7} + 4609 t^{6} + 1287 t^{5} + 330 t^{4} + 84 t^{3} + 21 t^{2} + 5 t + 1\right) + 1764 t^{11} + 1176 t^{10} + 616 t^{9} + 308 t^{8} + 165 t^{7} + 132 t^{6} + 42 t^{5} + 14 t^{4} + 5 t^{3} + 2 t^{2} + t + 1$

In [33]:

P14 = sp.expand(sp.expand(P13).series(t, 0, 6).removeO())
P14

Out[33]: