System of Equations for Computing Shabat Polynomials

A few weeks ago, Dong Quan Ngoc Nguyen (University of Notre Dame) came to visit here at Purdue.  We spoke a little about the computer package Bertini (created by Daniel Bates, Jonathan Hauenstein, Andrew Sommese and Charles Wampler) and whether the homotopy continuation method can be used to compute Belyi maps and Shabat Polynomials.  I’ve been working on setting up a system of polynomial equations whose solutions give the coefficients of the Belyi maps, so it really comes down to actually finding the solutions to these equations.  The hope is that a polynomial homotopy continuation method will be much more efficient than say, using Groebner bases, to find all solutions!

Let me try and set up how this would work by working through some explicit examples.

Belyi Maps and Dessins d’Enfants

Say that we have a connected planar bipartite graph \Gamma = \bigl( V, \, E \bigr). The vertices V = B \cup W consist of “black” vertices B as well as “white” vertices W, and the “midpoints” of the faces are F. I am interested in the following

Problem. Given a connected planar bipartite graph \Gamma, find a rational function \beta which satisfies the following:

  • Its only critical values are \{ 0, \, 1, \, \infty \} \subseteq \mathbb P^1(\mathbb C).
  • B = \beta^{-1}(0) are the “black” vertices.
  • W = \beta^{-1}(1) are the “white” vertices.
  • F = \beta^{-1}(\infty) are the “midpoints” of the faces.
  • E = \beta^{-1} \bigl( [0,1] \bigr) as the edges is the inverse image of the interval from 0 to 1.

We say \beta: \mathbb P^1(\mathbb C) \to \mathbb P^1(\mathbb C) is a Belyi map, and \Gamma is said to be a Dessin d’Enfant.

Computationally, I find working with connected planar bipartite graphs very difficult, so instead let me work with its valency list. Denote b_i as the number of edges adjacent to each “black” vertex as indexed by i \in I, w_j as the number of edges adjacent to each “white” vertex as indexed by j \in J, and f_k as the number of edges adjacent to each face as indexed by k \in K. Define the degree sequence as a valency list:

\mathcal D = \biggl \{ \left \{ b_i \, \bigl| \, i \in I \right \}, \ \left \{ w_j \, \bigl| \, j \in J \right \}, \ \left \{ f_k \, \bigl| \, k \in K \right \} \biggr \}; 

and denote the positive integer n = |I| + |J| + |K| - 3. Define the n polynomials y_1, \, y_2, \, \dots, \, y_n in \mathbb Z[x_1, x_2, \dots, x_n] in n variables x_1, \, x_2, \, \dots, \, x_n by the 3 \times 3 determinants

y_e = \left| \begin{matrix} B_0 & W_0 & F_0 \\[5pt] B_e & W_e & F_e \\[5pt] B_{n+1} & W_{n+1} & F_{n+1} \end{matrix} \right|

for e = 1, \, 2, \, \dots, \, n, each expressed in terms of the coefficients of the polynomials

\begin{matrix} \displaystyle z^{b_{|I|}} \prod_{i = 1}^{|I|-1} \biggl( z - x_i \biggr)^{b_i} & = &\displaystyle \sum_{e = 0}^{n+1} B_e \, z^e \\[15pt] \displaystyle \bigl( z - 1 \bigr)^{w_{|J|}} \prod_{j = 1}^{|J|-1} \biggl( z - x_{|I|+j-1} \biggr)^{w_j} & = &\displaystyle \sum_{e = 0}^{n+1} W_e \, z^e \\[15pt] \displaystyle \prod_{k = 1}^{|K|-1} \biggl( z - x_{|I|+|J|+k-2} \biggr)^{f_k} & = &\displaystyle \sum_{e = 0}^{n+1} F_e \, z^e \end{matrix}

each as elements of \mathbb Z[x_1, x_2, \dots, x_n][z].  The following is relatively trivial to prove.

Proposition 1. Continue notation as above.

  • The Euler Characteristic and the Degree Sum Formula together imply
    n +1 = \displaystyle  \sum_{i \in I} b_i = \sum_{j \in J} w_j = \sum_{k \in K} f_k = |I| + |J| + |K| - 2.
  • The following algebraic variety has dimension 0: X = \left \{ P = (x_1, \, x_2, \, \dots, \, x_n) \in \mathbb A^n \ \biggl| \ y_1(P) = y_2(P) = \cdots = y_n(P) = 0 \right \}. In particular, Bezout’s theorem implies \#X(\mathbb C) \leq \deg(y_1) \cdot \deg(y_2) \cdots \deg(y_n).
  • Every point P = (x_1, \, x_2, \, \dots, \, x_n) in X(\mathbb C) gives rise to a Belyi map \beta: \mathbb P^1(\mathbb C) \to \mathbb P^1(\mathbb C) such that \Gamma is its Dessin d’Enfant, and we have the explicit points \begin{matrix} B & = & \beta^{-1}(0) & = & \biggl \{ (0:1), \, (x_1:1), \, \dots, \, (x_{|I|-1}:1) \biggr \}, \\[15pt] W & = & \beta^{-1}(1) & = & \biggl \{ (1:1), \, (x_{|I|}:1), \, \dots, \, (x_{|I|+|J|-2}:1) \biggr \}, \\[15pt] F & = & \beta^{-1}(\infty) & =&  \biggl \{ (1:0), \, (x_{|I|+|J|-1}:1), \, \dots, \, (x_{|I|+|J|+|K|-3}:1) \biggr \} \end{matrix} Rather explicitly, \beta(z) = \dfrac {\left| \begin{matrix} F_0 & W_0 \\[5pt] F_{n+1} & W_{n+1} \end{matrix} \right|}{\left| \begin{matrix} B_0 & W_0 \\[5pt] B_{n+1} & W_{n+1} \end{matrix} \right|} \cdot \dfrac {\displaystyle z^{b_{|I|}} \prod_{i = 1}^{|I|-1} \biggl( z - x_i \biggr)^{b_i}}{\displaystyle \prod_{k = 1}^{|K|-1} \biggl( z - x_{|I|+|J|+k-2} \biggr)^{f_k}}.

The basic idea behind this result is that we have the identity

\begin{aligned} \displaystyle \sum_{e = 1}^n y_e \, z^e & = \left| \begin{matrix} B_0 & W_0 & F_0 \\[15pt] \displaystyle \sum_{e = 0}^{n+1} B_e \, z^e & \displaystyle \sum_{e = 0}^{n+1} W_e \, z^e & \displaystyle \sum_{e = 0}^{n+1} F_e \, z^e \\[15pt] B_{n+1} & W_{n+1} & F_{n+1} \end{matrix} \right| \\[10pt] & = \left| \begin{matrix} F_0 & W_0 \\[5pt] F_{n+1} & W_{n+1} \end{matrix} \right| \cdot z^{b_{|I|}} \prod_{i = 1}^{|I|-1} \biggl( z - x_i \biggr)^{b_i} \\[10pt] & \quad - \left| \begin{matrix} F_0 & B_0 \\[5pt] F_{n+1} & B_{n+1} \end{matrix} \right| \cdot \bigl( z - 1 \bigr)^{w_{|J|}} \prod_{j = 1}^{|J|-1} \biggl( z - x_{|I|+j-1} \biggr)^{w_j} \\[10pt] & \qquad - \left| \begin{matrix} B_0 & W_0 \\[5pt] B_{n+1} & W_{n+1} \end{matrix} \right| \cdot \prod_{k = 1}^{|K|-1} \biggl( z - x_{|I|+|J|+k-2} \biggr)^{f_k}. \end{aligned}

Finding All Points P \in X(\mathbb C) using Bertini

Given a degree sequence \mathcal D, one can list the polynomials y_1, \, y_2, \, \dots, \, y_n in \mathbb Z[x_1, x_2, \dots, x_n] very quickly. I would like to find the points P in X(\mathbb C) using the following

Algorithm.  Denote F as that extension of \mathbb Q which is the field generated by the coordinates of the points P \in X(\mathbb C).

  1. Using both the Homotopy Continuation and Newton’s Method, numerically find all of the points P in X(\mathbb C).
  2. Using LLL, find a monic polynomial \phi(z) \in \mathbb Z[z] such that F \simeq \mathbb Q[z] / \bigl( \phi(z) \bigr). Note that the roots z_P of \phi(z) are in one-to-one correspondence with the points P = (x_1, \, x_2, \, \dots, \, x_n) in X(\mathbb C).
  3. Also using LLL, find polynomials \phi_1, \, \phi_2, \, \dots, \, \phi_n in \mathbb Q[z] such that y_e \bigl( \phi_1(z), \, \phi_2(z), \, \dots, \, \phi_n(z) \bigr) \equiv 0 \quad \text{mod} \ \phi(z) for e = 1, \, 2, \, \dots, \, n. Then P = \bigl( \phi_1(z_P), \, \phi_2(z_P), \, \dots, \, \phi_n(z_P) \bigr) for each root z_P of \phi(z).

I would like to use Bertini to complete Step #1. My graduate student Jacob Bond has code which can perform Steps #2 and #3 relatively quickly.  I’ll say a few more words below when I discuss some examples.

Shabat Polynomials and Trees

Let me discuss a class of examples in some detail. We say that a connected planar graph is a tree if it has only one face.

180px-tree_graph-svg

From Wikipedia

I will view it as a bipartite graph by coloring its vertices “black” and placing “white” vertices at the midpoints of the edges. Assuming there are d+1 vertices and hence d edges, its degree sequence is in the form

\mathcal D = \left \{ \{ m_0, \, m_1, \, \dots, \, m_d \},\ \{ 2, \, 2, \, \dots, \, 2 \}, \ \{ 2 \, d \} \right \}

where we must have m_0 + m_1 + m_2 + \cdots + m_d = 2 \, d. Here |I| = d+1, |J| = d, and |K|= 1, so that n = 2 \, d - 1 is odd. The following result is closely related to the one above, but the notation is not quite the same.

Proposition 2. Continue notation as above. If we can find n = 2 \, d - 1 nontrivial complex numbers x_1, \, x_2, \, \dots, \, x_n such that
z^{m_d} \, \bigl( z-1 \bigr)^{m_0} \, \bigl( z - x_1 \bigr)^{m_1} \, \cdots \, \bigl( z - x_{d-1} \bigr)^{m_{d-1}} + x_d^2 - \left( z^d + \sum_{j=0}^{d-1} x_{j+d} \, z^j \right)^2 = \displaystyle \sum_{e = 1}^{n} y_e \, z^e is identically zero as a polynomial in z, then the tree of interest is the Dessin d’Enfant of the Belyi map \beta(z) = - \dfrac {1}{x_d^2} \cdot z^{m_d} \, \bigl( z-1 \bigr)^{m_0} \, \bigl( z - x_1 \bigr)^{m_1} \, \cdots \, \bigl( z - x_{d-1} \bigr)^{m_{d-1}}.

This Belyi map is not just a rational function of degree n + 1 = 2 \, d; it is a polynomial. We say that such a Belyi map is a Shabat Polynomial. Note that there are n equations y_1 = y_2 = \cdots = y_n = 0 in n variables x_1, \, x_2, \, \dots, \, x_n, so again we can construct an algebraic variety X of dimension 0 and ask for all points P \in X(\mathbb C).

Worked Examples of Shabat Polynomials

Given a collection of d+1 positive integers m_0, \, m_1, \, \dots, \, m_d such that m_0 + m_1 + m_2 + \cdots + m_d = 2 \, d, one can list the polynomials y_1, \, y_2, \, \dots, \, y_n in \mathbb Z[x_1, x_2, \dots, x_n] very quickly. Remember that the goal is to find the n variables x_1, \, x_2, \, \dots, \, x_n such that we have the n equations y_1 = y_2 = \cdots = y_n = 0.

Example 1

Say that d = 1 so that n = 1. We have a degree sequence \mathcal D = \bigl \{ \{ m_0, \, m_1\}, \ \{ 2 \}, \ \{ 2 \} \bigr \} such that m_0 + m_1 = 2, so we must have m_0 = m_1 = 1. We have the polynomial z^{m_1} \, (z - 1)^{m_0} + x_1^2 - (z + x_1)^2 = y_1 \, z where y_1 = - 1 - 2 \, x_1. Setting y_1 = 0, we find x_1 = -1/2. Hence the Shabat polynomial must be

\beta(z) = - \dfrac {1}{x_1^2} \cdot z^{m_1} \, ( z-1)^{m_0} = 4 \, z \, (1 - z).

Example 2

Say that d = 2 so that n = 3. We have a degree sequence \mathcal D = \bigl \{ \{ m_0, \, m_1, \, m_2 \}, \ \{ 2, \, 2 \}, \ \{ 4 \} \bigr \} such that m_0 + m_1 + m_2 = 4, so up to permutation we must have m_0 = m_1 = 1 and m_2 = 2. We have the polynomial

z^{m_2} \, (z - 1)^{m_0} \, (z - x_1)^{m_1} + x_2^2 - (z^2 + x_3 \, z + x_2)^2 = y_1 \, z + y_2 \, z^2 + y_3 \, z^3

where

\begin{matrix} y_1 & = & - 2 \, x_2 \, x_3 \\[15pt] y_2 & = & - 2 \, x_2 - x_3^2 \\[15pt] y_3 & = & 1 - x_1 - 2 \, x_3 \end{matrix}

Setting y_1 = y_2 = y_3 = 0, we find two solutions: either (x_1, \, x_2, \, x_3) = (1, \, 0, \, -1) or (x_1, \, x_2, \, x_3) = ( -1, \, -1/2, \, 0). We throw out the first solution because we will need to divide by x_2, so from the second solution we find the Shabat polynomial

\beta(z) = - \dfrac {1}{x_2^2} \cdot z^{m_2} \, ( z-1)^{m_0} \, ( z - x_1)^{m_1} = 4 \, z^2 \, (1 - z^2).

Example 3

Consider the star graph K_{1,d} on d edges. It has degree sequence

\mathcal D = \left \{ \{1, \, \dots, \, 1, \, d \},\ \{ 2, \, 2, \, \dots, \, 2 \}, \ \{ 2 \, d \} \right \}.

We have already seen this when d = 1, \, 2 as in the two previous examples.

600px-star_graphs-svg

From Wikipedia

We are interested in an identity of the form z^d \, ( z-1)^{1} \, ( z - x_1)^{1} \, \cdots \, \bigl( z - x_{d-1} \bigr)^{1} + x_d^2 - \left( z^d + \sum_{j=0}^{d-1} x_{j+d} \, z^j \right)^2 = 0 for all z. Let \zeta = e^{2 \pi \sqrt{-1}/d} denote a primitive dth root of unity. If we choose

x_k = \left \{ \begin{matrix} \zeta^k & k = 1, \, 2, \, \dots, \, (d-1), \\[15pt] -1/2 &k = d, \\[15pt] 0 &k = (d+1), \, \dots, \, (2 \, d - 1); \end{matrix} \right.

then we recover the identity z^d \, (z^d - 1) + \left( \dfrac {1}{2} \right)^2 - \left( z^d - \dfrac 12 \right)^2 = 0. Hence the corresponding Shabat polynomial is \beta(z) = 4 \, z^d \, (1 - z^d).

Example 4

Now consider any tree with d = 5 edges having the degree sequence

\mathcal D = \left \{ \{ 2, \, 2, \, 1, \, 1, \, 1, \, 3 \},\ 2, \, 2, \, 2, \, 2, \, 2 \}, \ \{ 10 \} \right \}.

Since n = 2 \, d - 1 = 9, we have the polynomial

z^3 \, ( z-1)^2 \, ( z - x_1)^2 \, ( z - x_2)^1 \, ( z - x_3)^1 \, ( z - x_4)^1  + x_5^2 - \left( z^5 + x_9 \, z^4 + x_8 \, z^3 + x_7 \, z^2 + x_6 \, z + x_5 \right)^2 = y_1 \, z + y_2 \, z^2 + y_3 \, z^3 + y_4 \, z^4 + y_5 \, z^5 + y_6 \, z^6 + y_7 \, z^7 + y_8 \, z^8 + y_9 \, z^9

in terms of

\begin{matrix} y_1 & = & -2 \, x_5 \, x_6 \\[5pt] y_2 & = & -x_6^2 - 2 \, x_5 \, x_7 \\[10pt] y_3 & = & -x_1^2 \, x_2 \, x_3 \, x_4 - 2 \, x_6 \, x_7 - 2 \, x_5 \, x_8 \\[10pt] y_4 & = & x_1^2 \, x_2 \, x_3 + x_1^2 \, x_2 \, x_4 + x_1^2\, x_3 \, x_4 + 2 \, x_1 \, x_2 \, x_3 \, x_4 + 2 \, x_1^2 \, x_2 \, x_3 \, x_4 \\[5pt] & & \quad - x_7^2 - 2 \, x_6 \, x_8 - 2 \, x_5 \, x_9 \\[10pt] y_5 & = & - x_1^2 \, x_2 - x_1^2 \, x_3 - 2 \, x_1\, x_2 \, x_3 - 2 \, x_1^2 \, x_2 \, x_3 - x_1^2\, x_4 -2 \, x_1\, x_2 \, x_4 \\[5pt] & & \quad - 2 \, x_1^2 \, x_2 \, x_4 - 2 \, x_1 \, x_3 \, x_4 - 2 \, x_1^2 \, x_3 \, x_4 - x_2 \, x_3 \, x_4 - 4 \, x_1\, x_2 \, x_3 \, x_4 \\[5pt] & & \qquad - x_1^2 \, x_2 \, x_3 \, x_4 - 2 \, x_5 -2 \, x_7 \, x_8 - 2 \, x_6 \, x_9 \\[10pt] y_6 & = & 2 \, x_1^2 \, x_2 + x_1^2 \, x_2 \, x_3 + 2 \, x_1^2 \, x_3 + x_1^2 \, x_2 \, x_4 + x_1^2 \, x_3 \, x_4 + 2 \, x_1^2 \, x_4 + x_1^2 + 2 \, x_1 \, x_2 \\[5pt] & & \quad + 4 \, x_1 \, x_2 \, x_3 + 2 \, x_1 \, x_3 + 4 \, x_1 \, x_2 \, x_4 + 2 \, x_1 \, x_2 \, x_3 \, x_4 + 4 \, x_1 \, x_3 \, x_4 + 2 \, x_1 \, x_4 \\[5pt] & & \qquad - x_8^2 + x_2 \, x_3 + x_2 \, x_4 + 2 \, x_2 \, x_3 \, x_4 + x_3 \, x_4 - 2 \, x_6 - 2 \, x_7 \, x_9 \\[10pt] y_7 & = & -x_1^2 \, x_2 - x_1^2 \, x_3 - x_1^2 \, x_4 - 2 \, x_1^2 - 4 x_1 \, x_2 - 2 \, x_1 \, x_2 \, x_3 - 4 \, x_1 \, x_3 \\[5pt] & & \quad - 2 \, x_1 \, x_2 \, x_4 - 2 \, x_1 \, x_3 \, x_4 - 4 \, x_1 \, x_4 - 2 \, x_1 - x_2 - 2 \, x_2 \, x_3 - x_3 \\[5pt] & & \qquad - 2 \, x_2 \, x_4 - x_2 \, x_3 \, x_4 - 2 \, x_3 \, x_4 - x_4 - 2 \, x_7 - 2 \, x_8 \, x_9 \\[10pt] y_8 & = & x_1^2 + 2 \, x_1 \, x_2 + 2 \, x_1 \, x_3 + 2 x_1\, x_4 + 4 \, x_1 - x_9^2 + 2 \, x_2 + x_2 \, x_3 + 2 \, x_3 \\[5pt] & & \quad + x_2 \, x_4 + x_3 \, x_4 + 2 \, x_4 - 2 \, x_8 + 1 \\[10pt] y_9 & = & -2 - 2 \, x_1 - x_2 - x_3 - x_4 - 2 \, x_9 \end{matrix}

Question. Can Bertini find all solutions to y_1 = y_2 = \cdots = y_9 = 0?

I only know that one solution corresponds to

x_1 = \dfrac {5}{3}x_5 = - \dfrac {2}{9}x_6 = 0x_7 = 0x_8 = \dfrac {25}{9}, and x_9 = - \dfrac {10}{3}. In particular, one set of identities which works is as follows:

z^3 \, \bigl( z-1 \bigr)^2 \left( z - \dfrac {5}{3} \right)^2 \left( z^3 - \dfrac {4}{3} \, z^2 - \dfrac {8}{9} \, z - \dfrac {4}{9} \right)^1 + \left( \dfrac {2}{9} \right)^2 - \left( z^5 - \dfrac {10}{3} \, z^4 + \dfrac {25}{9} \, z^3 - \dfrac {2}{9} \right)^2 = 0.

Using the substitution z \mapsto (4-z)/3 we find a corresponding Shabat polynomial

\beta(z) = -\dfrac { (z^2 - 1)^2 \, (z^3 - 8 \, z^2 + 8 \, z + 44) \, (z-4)^3}{2916}.

However, this isn’t the only Shabat polynomial because this isn’t the only tree with this degree sequence! By using a slight permutation of the degree sequence above, say

\mathcal D = \left \{ \{ 1, \, 1, \, 1, \, 2, \, 2, \, 3 \},\ \{ 2, \, 2, \, 2, \, 2, \, 2 \}, \ \{ 10 \} \right \},

it is easy to verify that a completely different set of identities is as follows:

z^3 \, \bigl( z-1 \bigr)^1 \left( z^2 + \dfrac {5}{3} \, z + \dfrac {40}{9} \right)^1 \left( z^2 + \dfrac {4}{3} \, z + \dfrac {8}{3} \right)^2 + \left( \dfrac {32}{9} \right)^2 - \left( z^5 + \dfrac {5}{3} \, z^4 + \dfrac {40}{9} \, z^3 - \dfrac {32}{9} \right)^2 = 0.

Using the substitution z \mapsto (z-2)/3, we find that a completely different polynomial:

\beta(z) = -\dfrac {(z^2 + 20)^2 \, (z-5) \, (z^2 + z + 34) \, (z-2)^3}{746496}.

 

Advertisements

About Edray Herber Goins, Ph.D.

Edray Herber Goins grew up in South Los Angeles, California. A product of the Los Angeles Unified (LAUSD) public school system, Dr. Goins attended the California Institute of Technology, where he majored in mathematics and physics, and earned his doctorate in mathematics from Stanford University. Dr. Goins is currently an Associate Professor of Mathematics at Purdue University in West Lafayette, Indiana. He works in the field of number theory, as it pertains to the intersection of representation theory and algebraic geometry.
This entry was posted in General Remarks, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s