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
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 .
Computationally, I find working with connected planar bipartite graphs very difficult, so instead let me work with its valency list. Denote
and denote the positive integer
each as elements of
Proposition 1. Continue notation as above.
The basic idea behind this result is that we have the identity
Finding All Points
Given a degree sequence
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
- 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
where we must have
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
Worked Examples of Shabat Polynomials
Given a collection of
Consider the star graph
We have already seen this when
We are interested in an identity of the form
then we recover the identity
Now consider any tree with
in terms of
Question. Can Bertini find all solutions to
I only know that one solution corresponds to
Using the substitution
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