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} \geq 2 g + 1$ . For small model $d_{0} \geq 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 (n D_{0}))$ with a chosen basis, and let $μ_{n, m}$ is a bilinear map from $V_{n} \times V_{m} \to V_{n + m}$ defined by $(f, g) \mapsto f g$ . The map $μ_{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 e f$ . 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_{0} D_{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 (3 D_{0})$ , and for medium model, $n_{0} = 2$ and $L = O (2 D_{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_{0} D_{0}))$ .

The function mu_image(w_D, w_E, mu_mat_n_m, expected_dim) computes the image $μ_{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 $μ_{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)[source]¶: Theorem 4.5 (addition).

multiple(wd, n)[source]¶: Compute multiple by additive square-and-multiply method.

negate(wd)[source]¶: Theorem 4.4 (negation), first method.

subtract(wd1, wd2)[source]¶: Theorem 4.6 (subtraction), first method.

zero_divisor()[source]¶: Return the matrix $w_{L}$ representing zero divisor.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_large[source]¶

Bases: KhuriMakdisi_base

Khuri-Makdisi’s large model.

add_divisor(wd1, wd2, d1, d2)[source]¶

Theorem 3.6 (addition of divisors, first method).

We assume that $w_{D_{1}}$ , $w_{D_{2}}$ represent divisors of degree at most $3 d_{0} - 2 g - 1$ .

addflip(wd1, wd2)[source]¶: Theorem 4.3 (addflip).

equal(wd, we)[source]¶: Theorem 4.1, second method.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_medium[source]¶

Bases: KhuriMakdisi_base

Khuri-Makdisi’s medium model

add_divisor(wd1, wd2, d1, d2)[source]¶

Theorem 3.6 (addition of divisors, first method).

We assume that $w_{D_{1}}$ , $w_{D_{2}}$ represent divisors of degree at most $4 d_{0} - 2 g - 1$ .

addflip(wd1, wd2)[source]¶: Theorem 5.1 (addflip in medium model).

equal(wd, we)[source]¶: Theorem 4.1, second method.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_small[source]¶

Bases: KhuriMakdisi_base

Khuri-Makdisi’s small model

add_divisor(wd1, wd2, d1, d2)[source]¶

Theorem 3.6 (addition of divisors, first method).

We assume that $w_{D_{1}}$ , $w_{D_{2}}$ represent divisors of degree at most $6 d_{0} - 2 g - 1$ .

addflip(wd1, wd2)[source]¶: Theorem 5.3 (addflip in small model), second method.

equal(wd, we)[source]¶: Theorem 4.1, second method.

negate(wd)[source]¶: Theorem 5.4 (negation in small model).