Computing the Valuation Divisor

I am currently implementing an algorithm for computing the valuation divisor of a differential on a Riemann surface. The valuation divisor

$(\omega)_{val} = p_1 P_1 + \cdots + p_m P_m - q_1 Q_1 - \cdots - q_n Q_n$

is a formal sum of places $P_i$ and $Q_j$ on the surface such that $\omega$ is zero at each $P_i$ with multiplicity $p_i$ and has a pole at each $Q_j$ of order $q_j$. Valuation divisors of differentials play a key role in computing the Riemann constant vector, a major goal of my code.

Mathematics Background

The way in which I find these places depends whether the place is discriminant or not. That is, if the x-projection of the place onto the curve is a discriminant point of the curve.

If $P$ is discriminant, meaning that $P$ is a place that might share an x- or y-projection with some other place onto the curve, then $P$ is given in terms of a Puiseux series expansion, $P(t) = (x(t), y(t))$. The strategy is to then “localize” $\omega$ at this place by writing

$\omega\big|_P = \frac{p(t) dt}{q(t)} = \left( ct^m + O\left(t^{m+1}\right) \right)dt$

using the technique discussed in my previous post.

So in the discriminant case, if $m$ above is less than zero then $P$ is a pole of order $m$ and if it’s greater than zero then it’s a zero of order $m$.

In the case when $P$ is regular we can also use Puiseux series expansions. However, it may be more computationally efficient to use Hasse derivatives.

Hasse Derivatives

Let $x = (x_1, \ldots, x_n)$ and $f = f(x)$ be a polynomial in the $x_i$. Consider another vector of indeterminants $z = (z_1, \ldots, z_n)$ and the polynomial

$f(x+z) = \sum_{k=(k_1, \ldots, k_n)} D^{k}(x) z_1^{k_1} \cdots z_n^{k_n}.$

where each of the $D^{k}$’s are polynomials in $x$. These polynomials are called the k’th Hasse derivatives of the polynomial $f$. The notion of a Hasse derivative extends to all analytic functions and even functions defined over finite fields.

The multiplicity of $f$ at $x=a=(a_1,\ldots,a_n)$ is the smallest integer $m$ such that $D^k(a) = 0$ for all $k_1 + \cdots + k_n < m$ but $D^k(a) \neq 0$ for some $k_1 + \cdots + k_n = m$.

The code for efficiently doing this in Sympy is very clean:

def mult(f,x,a):
    # reuse variables 'x' as 'z'
    xpa = map(sum,zip(x,a))
    subs = dict(zip(x,xpa))
    p = sympy.poly(f.subs(subs),*x)
    degs = map(sum, p.monoms())
    return min(degs)

From my tests it’s 20-200 times faster than a “naive approach” using partial derivative evaluation at $x = a$.

Software Design

Note that the “strategy” used to determine the membership and multiplicity of $P$ in the valuation divisor is strongly dependent of what kind of place we’re looking at. Therefore, the Place class and subclasses RegularPlace and DiscriminantPlace should contain the logic for this membership. I realized this after attempting to implement the algorithm within the Differential class as Differential.valuation_divisor() and ran into a bunch of conditional statements that looked like this:

class Differential:
    def valuation_divisor(self):
        D = ZeroDivisor()
        for P in places_we_need_to_consider:
            if P.is_discriminant():
                # use Taylor series approach to
                # determine order
            else:
                # use Hasse derivative approach

This is a clear violation of the Open/Closed Principle (pdf): suppose I were to add another Place type, say, InfinitePlace. I would then have to add another set of conditionals wherever they may appear in this algorithm. Suppose later someone who isn’t as familiar with my code wants to add yet another place type. Although I (currently) remember where these lines sit this poor contributor would have to hunt and peck or receive numerous runtime errors until they add conditionals wherever one should exist for their new type.

Hence, the code should look more like this:

class Differential:
    def valuation_divisor(self):
        D = ZeroDivisor()
        for P in places_we_need_to_consider:
            # pass self in as param to Place
            multiplicity = P.valuation(self)
            D += multiplicity * P

class Place(object):
    def valuation(self,omega):
        raise NotImplementedError()

class RegularPlace(object):
    def valuation(self,omega):
        # compute and return valuation using Hasse

class DiscriminantPlace(object):
    def valuation(self,omega):
        # compute and return valuation using Puiseux

(Let’s set aside the fact that I’ve already implemented artihmetic on divisors so that the statement D += multiplicity * P makes sense and works.) This way, a new Place can immediately be used in computing valuation divisors by simply defining the valuation() method.

At this stage in my career this is practically obvious to me and probably to any programmer reading this. However, I would not have thought of this two years ago. Plus, I wanted to share because it’s exciting seeing abstract mathematical objects become completely explicit and solidified in well-organized code.