Chris Swierczewski's Website

Computing the Valuation Divisor

Nov 22, 2014

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

(ω)val=p1P1++pmPmq1Q1qnQn (\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 PiP_i and QjQ_j on the surface such that ω\omega is zero at each PiP_i with multiplicity pip_i and has a pole at each QjQ_j of order qjq_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 PP is discriminant, meaning that PP is a place that might share an x- or y-projection with some other place onto the curve, then PP is given in terms of a Puiseux series expansion, P(t)=(x(t),y(t))P(t) = (x(t), y(t)). The strategy is to then “localize” ω\omega at this place by writing

ωP=p(t)dtq(t)=(ctm+O(tm+1))dt \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 mm above is less than zero then PP is a pole of order mm and if it’s greater than zero then it’s a zero of order mm.

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

Hasse Derivatives

Let x=(x1,,xn)x = (x_1, \ldots, x_n) and f=f(x)f = f(x) be a polynomial in the xix_i. Consider another vector of indeterminants z=(z1,,zn)z = (z_1, \ldots, z_n) and the polynomial

f(x+z)=k=(k1,,kn)Dk(x)z1k1znkn. 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 DkD^{k}’s are polynomials in xx. These polynomials are called the k’th Hasse derivatives of the polynomial ff. The notion of a Hasse derivative extends to all analytic functions and even functions defined over finite fields.

The multiplicity of ff at x=a=(a1,,an)x=a=(a_1,\ldots,a_n) is the smallest integer mm such that Dk(a)=0D^k(a) = 0 for all k1++kn<mk_1 + \cdots + k_n < m but Dk(a)0D^k(a) \neq 0 for some k1++kn=mk_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=ax = a.

Software Design

Note that the “strategy” used to determine the membership and multiplicity of PP 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
                # 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.