Khuri-Makdisi algorithms for arithmetic in Jacobians

This module implements Khuri-Makdisi’s algorithms of [Khu2004].

In the implementation, we use notations close to the ones used by Khuri-Makdisi. We describe them below for readers of the code.

Let \(D_0\) be the base divisor of the Jacobian in Khuri-Makdisi model. So \(D_0\) is an effective divisor of appropriate degree \(d_0\) depending on the model. Let \(g\) be the genus of the underlying function field. For large and medium models, \(d_0\ge 2g+1\). For small model \(d_0\ge g+1\). A point of the Jacobian is a divisor class containing a divisor \(D - D_0\) of degree \(0\) with an effective divisor \(D\) of degree \(d_0\).

Let \(V_n\) denote the vector space \(H^0(O(nD_0))\) with a chosen basis, and let \(\mu_{n,m}\) is a bilinear map from \(V_n\times V_m\to V_{n+m}\) defined by \((f,g)\mapsto fg\). The map \(\mu_{n,m}\) can be represented by a 3-dimensional array as depicted below:

     f
   *------*
d /|e    /|
 *-|----* |
 | *----|-*
 |/     |/
 *------*

where \(d=\dim V_n\), \(e=\dim V_m\), \(f=\dim V_{n+m}\). In the implementation, we instead use a matrix of size \(d\times ef\). Each row of the matrix denotes a matrix of size \(e\times f\).

A point of the Jacobian is represented by an effective divisor \(D\). In Khuri-Makdisi algorithms, the divisor \(D\) is represented by a subspace \(W_D = H^0(O(n_0D_0 - D))\) of \(V_{n_0}\) with fixed \(n_0\) depending on the model. For large and small models, \(n_0=3\) and \(L = O(3D_0)\), and for medium model, \(n_0=2\) and \(L = O(2D_0)\).

The subspace \(W_D\) is the row space of a matrix \(w_D\). Thus in the implementation, the matrix \(w_D\) represents a point of the Jacobian. The row space of the matrix \(w_L\) is \(V_{n_0}=H^0(O(n_0D_0))\).

The function mu_image(w_D, w_E, mu_mat_n_m, expected_dim) computes the image \(\mu_{n,m}(W_D,W_E)\) of the expected dimension.

The function mu_preimage(w_E, w_F, mu_mat_n_m, expected_codim) computes the preimage \(W_D\) such that \(\mu_{n,m}(W_D,W_E)=W_F\) of the expected codimension \(\dim V_n - \dim W_D\), which is a multiple of \(d_0\).

AUTHORS:

• Kwankyu Lee (2022-01): initial version

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_base

Bases: object

add(wd1, wd2)

Theorem 4.5 (addition).

multiple(wd, n)

Compute multiple by additive square-and-multiply method.

negate(wd)

Theorem 4.4 (negation), first method.

subtract(wd1, wd2)

Theorem 4.6 (subtraction), first method.

zero_divisor()

Return the matrix \(w_L\) representing zero divisor.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_large

Bases: KhuriMakdisi_base

Khuri-Makdisi’s large model.

add_divisor(wd1, wd2, d1, d2)

Theorem 3.6 (addition of divisors, first method).

We assume that \(w_{D_1}\), \(w_{D_2}\) represent divisors of degree at most \(3d_0 - 2g - 1\).

addflip(wd1, wd2)

Theorem 4.3 (addflip).

equal(wd, we)

Theorem 4.1, second method.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_medium

Bases: KhuriMakdisi_base

Khuri-Makdisi’s medium model

add_divisor(wd1, wd2, d1, d2)

Theorem 3.6 (addition of divisors, first method).

We assume that \(w_{D_1}\), \(w_{D_2}\) represent divisors of degree at most \(4d_0 - 2g - 1\).

addflip(wd1, wd2)

Theorem 5.1 (addflip in medium model).

equal(wd, we)

Theorem 4.1, second method.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_small

Bases: KhuriMakdisi_base

Khuri-Makdisi’s small model

add_divisor(wd1, wd2, d1, d2)

Theorem 3.6 (addition of divisors, first method).

We assume that \(w_{D_1}\), \(w_{D_2}\) represent divisors of degree at most \(6d_0 - 2g - 1\).

addflip(wd1, wd2)

Theorem 5.3 (addflip in small model), second method.

equal(wd, we)

Theorem 4.1, second method.

negate(wd)

Theorem 5.4 (negation in small model).