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 . The vertices
consist of “black” vertices
as well as “white” vertices
, and the “midpoints” of the faces are
. I am interested in the following
Problem. Given a connected planar bipartite graph
, find a rational function
which satisfies the following:
- Its only critical values are
.
are the “black” vertices.
are the “white” vertices.
are the “midpoints” of the faces.
as the edges is the inverse image of the interval from
to
.
We say is a Belyi map, and
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 as the number of edges adjacent to each “black” vertex as indexed by
,
as the number of edges adjacent to each “white” vertex as indexed by
, and
as the number of edges adjacent to each face as indexed by
. Define the degree sequence as a valency list:
and denote the positive integer . Define the
polynomials
in
in
variables
by the
determinants
for , each expressed in terms of the coefficients of the polynomials
each as elements of . The following is relatively trivial to prove.
Proposition 1. Continue notation as above.
- The Euler Characteristic and the Degree Sum Formula together imply
.
- The following algebraic variety has dimension 0:
In particular, Bezout’s theorem implies
.
- Every point
in
gives rise to a Belyi map
such that
is its Dessin d’Enfant, and we have the explicit points
Rather explicitly,
The basic idea behind this result is that we have the identity
Finding All Points
using Bertini
Given a degree sequence , one can list the polynomials
in
very quickly. I would like to find the points
in
using the following
Algorithm. Denote
as that extension of
which is the field generated by the coordinates of the points
.
- Using both the Homotopy Continuation and Newton’s Method, numerically find all of the points
in
.
- Using LLL, find a monic polynomial
such that
. Note that the roots
of
are in one-to-one correspondence with the points
in
.
- Also using LLL, find polynomials
in
such that
for
. Then
for each root
of
.
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.
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 vertices and hence
edges, its degree sequence is in the form
where we must have . Here
,
, and
, so that
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
nontrivial complex numbers
such that
is identically zero as a polynomial in
, then the tree of interest is the Dessin d’Enfant of the Belyi map
.
This Belyi map is not just a rational function of degree ; it is a polynomial. We say that such a Belyi map is a Shabat Polynomial. Note that there are
equations
in
variables
, so again we can construct an algebraic variety
of dimension 0 and ask for all points
.
Worked Examples of Shabat Polynomials
Given a collection of positive integers
such that
, one can list the polynomials
in
very quickly. Remember that the goal is to find the
variables
such that we have the
equations
.
Example 1
Say that so that
. We have a degree sequence
such that
, so we must have
. We have the polynomial
where
. Setting
, we find
. Hence the Shabat polynomial must be
Example 2
Say that so that
. We have a degree sequence
such that
, so up to permutation we must have
and
. We have the polynomial
where
Setting , we find two solutions: either
or
. We throw out the first solution because we will need to divide by
, so from the second solution we find the Shabat polynomial
Example 3
Consider the star graph on
edges. It has degree sequence
We have already seen this when as in the two previous examples.
We are interested in an identity of the form for all
. Let
denote a primitive
th root of unity. If we choose
then we recover the identity . Hence the corresponding Shabat polynomial is
.
Example 4
Now consider any tree with edges having the degree sequence
Since , we have the polynomial
in terms of
Question. Can Bertini find all solutions to
?
I only know that one solution corresponds to
,
,
,
,
, and
. In particular, one set of identities which works is as follows:
Using the substitution we find a corresponding Shabat polynomial
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
it is easy to verify that a completely different set of identities is as follows:
Using the substitution , we find that a completely different polynomial: