COMPUTATIONS WITH WITT VECTORS OF LENGTH 3

LUÍS R. A. FINOTTI

Abstract. In this paper we describe how to perform computations with Witt vectors of length 3 in an efficient way and give a formula that allows us to compute the third coordinate of the Greenberg transform of a polynomial directly. We apply the results to obtain information on the third coordinate of the j-invariant of the canonical lifting as a function on the j-invariant of the ordinary elliptic curve in characteristic p.

1. Introduction

Let 𝕜 be a perfect field of characteristic p > 0, W(𝕜) be the ring of Witt vectors over 𝕜, and W_{n}(𝕜) denote the ring of Witt vectors of length n, which in this case can be seen as the quotient of W(𝕜) modulo the principal ideal generated by p^{n}. (See section 2 for a quick review of Witt vectors.) Then, given an ordinary elliptic curve E/𝕜, there is a unique elliptic curve (up to isomorphism), say E/W(𝕜), which reduces to E modulo p for which we can lift the Frobenius. E is then called the canonical lifting of E. (See, for instance,

[Deu41] or [LST64].) Hence, given an ordinary j-invariant j_{0} ∈ 𝕜, the canonical lifting gives us a unique j ∈ W(𝕜). Therefore, if 𝕜^{ord} denotes the set of ordinary values of j-invariants in 𝕜, then we have functions J_{i} : 𝕜^{ord} → 𝕜, for i = 1, 2, 3, …, such that the j-invariant of the canonical lifting of an elliptic curve with j-invariant j_{0} ∈ 𝕜^{ord} is (j_{0}, J_{1}(j_{0}), J_{2}(j_{0}), …).

B. Mazur asked about the nature of these functions J_{i} and J. Tate asked about the possibility of extending them to supersingular values. (See [Fin10].)

Tate’s question motivates the following definition:

Definition 1.1. Suppose that j_{0} ∉ 𝕜^{ord} and J_{i} is regular at j_{0} for all i ≤ n. Then, we call an elliptic curve over W(𝕜) whose the j-invariant reduces to (j_{0}, J_{1}(j_{0}), …, J_{n}(j_{0})) modulo p^{n+1} a pseudo-canonical lifting modulo p^{n+1} (or over W_{n+1}(𝕜)) of the elliptic curve associated to j_{0}.

If J_{i} is regular for all i, we call the elliptic curve with j-invariant (j_{0}, J_{1}(j_{0}), J_{2}(j_{0}), …) the pseudo-canonical lifting of the elliptic curve associated to j_{0}.

2000 Mathematics Subject Classification. Primary 11G20; Secondary 11Y16.

Key words and phrases. witt vectors, elliptic curves, canonical lifting, pseudo-canonical lifting, modular polynomial.

Hence, Tate asks about the existence of such pseudo-canonical liftings. One would not expect pseudo-canonical liftings to exist, as they would yield curves which although are not canonical liftings, as those do not exist in the supersingular case, are obtained through the same formulas. On the other hand, we’ve proved that pseudo-canonical liftings modulo p^{2} do exist. More precisely, we’ve studied J_{1} in detail in [Fin10] (using many results from [KZ98]), proving the following:

Theorem 1.2. With the notation above and p ≥ 5:

(1) J_{i} ∈ 𝔽_{p}(X) for all i.

(2) J_{1}(X) is always regular at X = 0 and X = 1728, even when those values are supersingular.

(3) We always have that (0, J_{1}(0)) ≡ 0 (mod p^{2}) and (1728, J_{1}(1728)) ≡ 1728 (mod p^{2}).

(4) If j_{0} ∉ 𝕜^{ord} ∪ {0, 1728}, then J_{1} has a simple pole at j_{0}.

(5) J_{1}(X) has a zero of order ⌊(2p + 1)/3⌋ at X = 0.

In particular, this theorem tells us that only 0 and 1728 yield pseudo-canonical liftings modulo p^{2} (and they always do!), and hence we can only possibly have pseudo-canonical liftings for those values.

Before proving the result above, we were able to conjecture it to be true from computational evidence. In the same way, we wanted to have some computational data on J_{2} to form a proper conjecture in that case. The problem is that computations with Witt vectors of length 3 demand a lot more computer power than with length 2.

At first, the author computed J_{1} and J_{2} by computing the canonical lifting of the elliptic curve E given by y_{0}^{2} = x_{0}^{3} + a_{0}x_{0} + b_{0} over 𝔽_{p}(a_{0}, b_{0}), where a_{0} and b_{0} were variables, i.e., algebraically independent transcendental elements over 𝔽_{p}, using the algorithm described in [Fin02]. (Note that the algorithm gives more than just the canonical lifting E of E. It also gives a lifting of points from E(𝕜̄) to E(W_{3}(𝕜̄)) called the elliptic Teichmüller lift.) The algorithm gives the coefficients of the Weierstrass equation of the canonical lifting over W_{3}(𝔽_{p}(a_{0}, b_{0})), say a = (a_{0}, a_{1}, a_{2}) and b = (b_{0}, b_{1}, b_{2}), where a_{i}, b_{i} ∈ 𝔽_{p}(a_{0}, b_{0}) for i = 1, 2. Thus, we can compute its j-invariant using the operations of Witt vectors. The resulting formula can then be easily be put in 𝔽_{p}(j_{0}), where j_{0} = 1728(4a_{0}^{3})/(4a_{0}^{3} + 27b_{0}^{2}), thus giving us J_{1}(X) and J_{2}(X).

But, since a_{0} and b_{0} were taken as variables in a field of rational functions, the computations get quite demanding. While we were able to compute the reduction modulo p^{2} of the canonical lifting, i.e., a_{1} and b_{1}, for several values of p, we could only initially compute a_{2} and b_{2} for p ≤ 13. With the methods used at the time, the computation of the third coordinate of the canonical lifting (and elliptic Teichmüller lift) for p = 17 in this situation used almost 24 gigabytes of memory (16 gigabytes of RAM and 8 gigabytes of swap) before it crashed still unfinished. Formulas for the canonical lifting and elliptic Teichmüller lift modulo p^{3} for p ≤ 13 can be found, at the time of writing, at

                http://www.math.utk.edu/~finotti/can_lifts/.

On the other hand, as seen in [Fin10], one can compute J_{1} much more efficiently by using the (classical) modular polynomial. More precisely, we have:

Theorem 1.3. Let Φ_{p}(X, Y) denote the modular polynomial and H̄_{p}(X) be the reduction modulo p of Φ_{p}(X, X^{p})/p. Then, J_{1}(X) = −H̄_{p}(X)/(X^{p^{2}} − X).

The goal here is then twofold: on the one hand, we would like to find a more efficient way to perform computation with Witt vectors of length 3 in general. (We have special interest on Witt vectors over polynomial rings. Over finite fields computations can be done quickly by working with the proper extension of ℤ_{p} instead.) On the other hand, we would like to find an efficient way to compute J_{2}, in the same vein as Theorem 1.3, so that we can obtain more precise information on its nature, in the same vein as Theorem 1.2.

It should be mentioned up front that we will not be able to prove a full analogue of Theorem 1.2 to J_{2} here. Theorem 9.6 gets pretty close, while Conjecture 9.3 gives what we believe, from numerical evidence, to be the missing pieces. In particular, Theorem 9.6 tells us that j = 0 yields pseudo-canonical liftings modulo p^{3}, while Conjecture 9.3 states that j = 1728 does not.

Also, Theorem 9.1 gives a precise description of how to obtain J_{2} from the modular polynomial as done in Theorem 1.3, although the formula is not nearly as simple. More precisely, Eq. (9.1) gives us

J_{2}(X) = \frac{F (X)}{(X^{p^{2}} − X)^{2p+1}}

for some polynomial F (X) that can be explicitly obtained from Φ_{p}(X, X^{p}). Theorem 9.6 and Conjecture 9.3 describe J_{2}(X) as reduced rational function, thus giving information about possible pseudo-canonical liftings.

It should also be mentioned that the method from [Fin02] used to obtain the initial examples of J_{2} mentioned above is not the most efficient. There are better methods to compute the canonical lifting if we are not also interested in the elliptic Teichmüller lift. (In fact, Theorem 9.1 below gives us one such method.) One of the difficulties of this method is the computation of the Greenberg transform (see section 3) of an elliptic curve over a ring of Witt vectors of length 3, and we study here also an efficient way to compute the Greenberg transform. (See Theorem 6.1.)

We should emphasize that our result on the Greenberg transform is not just of importance to our algorithm to compute the canonical lifting together with the Teichmüller lift, although it is still relevant as one might actually need the elliptic Teichmüller lift (e.g., to construct error-correcting codes as in [VW00] and [Fin06]). It also has theoretical implications, namely, it is the most important step in obtaining Theorems 9.1 and 9.6 mentioned above.

Moreover, the formula for the third coordinate of the Greenberg transform given here is necessary if one wants to attempt to generalize the method to prove Theorem 1.2 in [Fin10] to try to prove Conjecture 9.3.

We now give a brief description of the content of the next sections. Section 2 and 3 give brief reviews of Witt vectors and Greenberg transform, respectively. Section 4 introduces many auxiliary functions that are necessary to describe the third coordinate of the Greenberg transform of a polynomial. Section 5 gives efficient methods to compute these auxiliary functions, giving also an efficient method to compute the polynomials that give the third coordinates of sums and products of Witt vectors. Section 6 gives the formula for the third coordinate of the Greenberg transform of a polynomial. Section 7 briefly analyzes the complexity of the computations using the new methods introduced, while Section 8 gives explicit examples of how much time and memory is saved when computing the first three coordinates of the Greenberg with these methods in some specific cases. Section 9 gives the results and conjectures on J_{2}. Finally, section 10 has a brief discussion and speculations on what happens with J_{3}.

The reader will notice that we need to introduce a lot of notation and that proofs, although mostly straight forward, sometimes are done by long and involved computations. Although this might make it tedious and laborious to follow some proofs, hopefully it will not prevent one from appreciating the results themselves.

2. Witt Vectors

In this section we will review some of the basic facts about Witt vectors. More details, including motivation and proofs, can be found in [Ser79] or [Jac84]. Let p be a prime, and and for each non-negative integer n consider

W^{(n)}(X_{0}, …, X_{n}) =^{def} X_{0}^{p^{n}} + pX_{1}^{p^{n−1}} + ⋯ + p^{n−1}X_{n−1}^{p} + p^{n}X_{n},  (2.1)

the corresponding Witt polynomial. Then, there exist polynomials S_{i}, P_{i} ∈ ℤ[X_{0}, …, X_{i}, Y_{0}, …, Y_{i}] satisfying:

W^{(n)}(S_{0}, …, S_{n}) = W^{(n)}(X_{0}, …, X_{n}) + W^{(n)}(Y_{0}, …, Y_{n})  (2.2)

and

W^{(n)}(P_{0}, …, P_{n}) = W^{(n)}(X_{0}, …, X_{n}) · W^{(n)}(Y_{0}, …, Y_{n}).  (2.3)

More explicitly, we have the following recursive formulas:

S_{n} = (X_{n} + Y_{n}) + \frac{1}{p}(X_{n−1}^{p} + Y_{n−1}^{p} − S_{n−1}^{p}) + ⋯ + \frac{1}{p^{n}} (X_{0}^{p^{n}} + Y_{0}^{p^{n}} − S_{0}^{p^{n}}),  (2.4)

and

P_{n} = \frac{1}{p^{n}} [(X_{0}^{p^{n}} + ⋯ + p^{n}X_{n})(Y_{0}^{p^{n}} + ⋯ + p^{n}Y_{n})− ; (P_{0}^{p^{n}} + ⋯ + p^{n−1}P_{n−1}^{p})] ; = (X_{0}^{p^{n}}Y_{n} + X_{1}^{p^{n−1}}Y_{n−1}^{p} + ⋯ + X_{n}Y_{0}^{p^{n}}) ; + \frac{1}{p}(X_{0}^{p^{n}}Y_{n−1}^{p} + ⋯ + X_{n−1}^{p}Y_{0}^{p^{n}}) ; ⋮ ; + \frac{1}{p^{n}} (X_{0}^{p^{n}}Y_{0}^{p^{n}}) − \frac{1}{p^{n}} P_{0}^{p^{n}} − ⋯ − \frac{1}{p}P_{n−1}^{p} ; + p (X_{1}^{p^{n−1}}Y_{n} + X_{2}^{p^{n−2}}(Y_{n−1}^{p} + pY_{n}) + …) .  (2.5)

(Note that despite the denominators in the formulas, cancellations yield polynomials with integer coefficients.)

We can then define sums and products of infinite vectors in A^{ℤ_{≥0}}, where A is a commutative ring (with 1), say a = (a_{0}, a_{1}, …) and b = (b_{0}, b_{1}, …), by

a + b =^{def} (S_{0}(a_{0}, b_{0}), S_{1}(a_{0}, a_{1}, b_{0}, b_{1}), …)

and

a · b =^{def} (P_{0}(a_{0}, b_{0}), P_{1}(a_{0}, a_{1}, b_{0}, b_{1}), …).

These operations make A^{ℤ_{≥0}} into a commutative ring (with 1) called the ring of Witt vectors over A and denoted by W(A).

Since we will deal with Witt vectors over fields of characteristic p, we may use S̄_{n}, P̄_{n} ∈ 𝔽_{p}[X_{0}, …, X_{n}, Y_{0}, …, Y_{n}], defined to be the reductions modulo p of S_{n}, P_{n} respectively, to define the addition and the product of Witt vectors.

Then, we obtain:

S̄_{1} = X_{1} + Y_{1} + \frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} ,  (2.6)
P̄_{1} = X_{1}Y_{0}^{p} + X_{0}^{p}Y_{1},  (2.7)

and

S̄_{2} = X_{2} + Y_{2} + \frac{1}{p} (X_{1}^{p} + Y_{1}^{p} − (X_{1} + Y_{1} + \frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} )^{p})
+ \frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0} + Y_{0})^{p^{2}}}{p^{2}} ,  (2.8)
P̄_{2} = X_{2}Y_{0}^{p^{2}} + X_{1}^{p}Y_{1}^{p} + X_{0}^{p^{2}}Y_{2} + \frac{X_{1}^{p}Y_{0}^{p^{2}} + X_{0}^{p^{2}}Y_{1}^{p} − (X_{1}Y_{0}^{p} + X_{0}^{p}Y_{1})^{p}}{p} .  (2.9)

Observe that we are abusing the notation here, as it seems that we are dividing by p in rings of characteristic p. But the meaning should be clear, as we have all terms divided by p are in fact congruent to zero modulo p over ℤ. Hence, we should interpret those terms as the reduction modulo p after the division by p. For instance,

\frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} = ∑_{i=1}^{p−1} c_{i}X_{0}^{i}Y_{0}^{p−i},

where c_{i} is the reduction modulo p of the integer −\frac{1}{p} \binom{p}{i} for i = 1, …, (p − 1). Also, observe that although

X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0} + Y_{0})^{p^{2}} ≢ 0 (mod p^{2}),

we have that

p (X_{1}^{p} + Y_{1}^{p} − (X_{1} + Y_{1} + \frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} )^{p})

+ X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0} + Y_{0})^{p^{2}} ≡ 0 (mod p^{2}),

and hence we should interpret Eq. (2.8) accordingly. On section 4 we shall describe how we can define (and compute) those terms without having to refer to computations in characteristic zero, thus avoiding this clumsy notation.

One should observe that simply computing S_{2} can take a lot of time and memory. For instance, for p = 31 the polynomial S_{2} has 152994 monomials! In MAGMA creating a ring of Witt vectors of length 3, which computes the S_{i} and P_{i} for i = 1, 2, can take a long time. The command “W:=WittRing(GF(31),3);”, which creates a ring of Witt vectors of length 3 over 𝔽_{31}, takes about 150.31 seconds on a server with two 64 bit 3.2 gigahertz Inter Xeon processors and 16 gigabytes of RAM. With the methods that we describe below, we can compute the S_{1}, S_{2}, P_{1}, and P_{2} for p = 31 in 1.39 seconds on the same computer.

Before we proceed, we review a few more results about Witt vectors that shall be used later on. Let 𝕜 be a perfect field of characteristic p, where p is the same prime as used in W^{(n)} above. Since 𝕜 has characteristic p, it can be shown that W(𝕜) has characteristic 0 and p is represented by the Witt vector (0, 1, 0, 0, …) of W(𝕜), while p^{n} is represented by the Witt vector that has 1 on its (n+1)-th coordinate and zeros in all others. This allows us to deduce that, since 𝕜 is perfect, saying that (a_{0}, a_{1}, …) is congruent to (b_{0}, b_{1}, …) modulo p^{n} (or modulo the principal ideal generated by p^{n}) is equivalent to saying that a_{i} = b_{i} for all i ∈ {0, 1, …, n − 1}. Hence, we can represent the elements of the quotient of W(𝕜) by the principal ideal generated by p^{n} by vectors of length n in a unique way, i.e., we can identify this quotient with the ring Witt vectors of length n, which we denote by W_{n}(𝕜).

Also, one can show that W(𝕜) is a strict p-ring (as defined in [Ser79]) with residue field 𝕜. (Hence, any perfect field of characteristic p is a residue field of a strict p-ring.) For example, if q = p^{r} and if we denote by ℤ_{q} the ring of integers of the unramified extension of ℚ_{p} of degree r, then we have ℤ_{q} ≅ W(𝔽_{q}).

Moreover, W(𝕜) has a natural lift of the (p-th power) Frobenius σ of 𝕜 defined by σ(a_{0}, a_{1}, …) = (σ(a_{0}), σ(a_{1}), …), and the group of units of W(𝕜) is the set W(𝕜)^{×} = {(a_{0}, a_{1}, …) ∈ W(𝕜) : a_{0} ≠ 0}.

Before we can make the isomorphism between ℤ_{q} and W(𝔽_{q}) explicit (with Eqs. (2.10) and (2.11) below), we need the following definitions:

Definition 2.1. (1) We denote by π the reduction modulo p map, i.e., π((a_{0}, a_{1}, …)) =

a_{0}.

(2) Let a ∈ 𝕜. Then, the Teichüller lift of a is the Witt vector τ(a) =^{def} (a, 0, 0, …). (Hence, τ is a section of π and when restricted to 𝕜^{×} yields a group homomorphism.)

(3) We also define the Teichmüller lift of polynomial over f ∈ 𝕜[x_{0}, y_{0}] as the polynomial τ(f) ∈ W(𝕜)[x, y] obtained by applying the Teichmüller lift to the coefficients of f.

(4) Define W(𝕜)^{∗} =^{def} {(a_{0}, 0, 0, …) ∈ W(𝕜) : a_{0} ∈ 𝕜}. (This is a multiplicative set. E.g., if 𝕜 = 𝔽_{q}, than W(𝕜)^{∗} is made of all (q − 1)-th roots of unity and zero.)

(5) Let a ∈ W(𝕜). Define ξ_{k}(a), for k ∈ ℤ_{≥0}, as the unique element of W(𝕜)^{∗} such that a = ∑_{k=0}^{∞} ξ_{k}(a)p^{k}. (This is well defined since W(𝕜) is a strict p-ring and W(𝕜)^{∗} is a complete set of representatives of 𝕜 = W(𝕜)/(p) in W(𝕜).)

With the notation above, we have

a = ∑_{k=0}^{∞} ξ_{k}(a)p^{k} = (π(ξ_{0}(a)), π(ξ_{1}(a))^{p}, π(ξ_{2}(a))^{p^{2}}, …)  (2.10)

and

(a_{0}, a_{1}, …) = ∑_{k=0}^{∞} τ(a_{k})^{1/p^{k}}p^{k}.  (2.11)

(Remember we are assuming that 𝕜 is perfect.)

3. The Greenberg Transform

In this section we briefly review the definition of the Greenberg transform. (See also [Lan52] and [Gre61].) We will deal only with polynomials in two variables here in order to make the notation and exposition simpler, but one can easily generalize the obtained results for more variables.

Definition 3.1. Let f(x, y) ∈ W(𝕜)[x, y]. If we replace x and y by (x_{0}, x_{1}, …) and (y_{0}, y_{1}, …) seen as Witt vectors of unknowns, and expand the resulting expression using sums and products of Witt vectors, we obtain a Witt vector (f_{0}, f_{1}, …), with f_{i} ∈ 𝕜[x_{0}, …, x_{i}, y_{0}, …, y_{i}]. This resulting vector is called the Greenberg transform of f and will be denoted by 𝒢 (f).

Moreover, if

C/W(𝕜) : f(x, y) = 0,

we define the Greenberg transform 𝒢 (C) of C to be the (infinite dimensional) variety over 𝕜 defined by the zeros of the coordinates of 𝒢 (f).

It is clear from the definition that there is a bijection between C(W(𝕜)) and 𝒢 (C)(𝕜). Also, we clearly have

𝒢 (x + y) = (S_{0}, S_{1}, …)  and  𝒢 (x · y) = (P_{0}, P_{1}, …).

One can recursively compute the coordinates of the Greenberg transform using the following theorem:

Theorem 3.2. Let f(x, y) ∈ W(𝕜)[x, y] and suppose that 𝒢 (f) = (f_{0}, f_{1}, …). If

W^{(n)}(f_{0}, …, f_{n}) ≡ f^{σ^{n}}(W^{(n)}(x_{0}, …, x_{n}), W^{(n)}(y_{0}, …, y_{n})) (mod p^{n+1})  (3.1)

(with W^{(n)} as in Eq. (2.1)) for some f_{i} ∈ W(𝕜)[x_{0}, …, x_{i}, y_{0}, …, y_{i}], then f_{i} reduces to f_{i} modulo p.

Proof. First, we observe that if g_{i} ≡ f_{i} (mod p) for i ∈ {0, …, n}, then W^{(n)}(f_{0}, …, f_{n}) ≡ W^{(n)}(g_{0}, …, g_{n}) (mod p^{n+1}).

If f = a = (a_{0}, a_{1}, …) ∈ W(𝕜), then the theorem is true by Eq. (2.11). Also, the theorem is clearly true for f equal to either x or y. So, it suffices to show that if the theorem is true for f and g, then it is also true for their sum and product. But these follow from Eqs. (2.2) and (2.3) respectively. □

Theorem 3.2 above allows us to compute the coordinates Greenberg transform recursively, generalizing Eqs. (2.2) and (2.3).

The algorithm described in [Fin02] to compute the second and third coordinates of the canonical lifting of an ordinary elliptic curve starts by computing the Greenberg transform. But this requires a lot of computer power when the coefficients are left as unknowns, and that is exactly the problem we first encountered when trying to compute J_{2}(X) for p ≥ 17.

Observe, on the other hand, that Lemma 8.1 from [Fin04], restated below as Proposition 4.5, allows us to compute the second coordinate of 𝒢 (f) directly, without using sums and products of Witt vectors or the recursive method from Theorem 3.2. In fact, although simple in the case of the second coordinate, this was crucial to the proof of Theorem 1.3. Hence, we need to find an analogue for the the third coordinate. (This analogue is stated as Theorem 6.1 below.)

4. Auxiliary Functions

In this section we introduce auxiliary functions that will be used to compute sums and products of Witt vectors. We will again let 𝕜 be a perfect field of characteristic p > 0 and use the notation introduced in Definition 2.1.

We shall use also the following terminology:

Definition 4.1. We say that two polynomials f_{1} and f_{2} are disjoint if no monomial has non-zero multiples appearing in both f_{1} and f_{2}. (In other words, if m is a monomial of f_{1}, there is no α ≠ 0 such that αm is a monomial of f_{2}, and vice-versa.)

Definition 4.2. Given f = ∑_{i,j} a_{i,j}x^{i}y^{j} ∈ W(𝕜)[x, y] and a positive integer n, define

f^{(p^{n})} =^{def} ∑_{i,j} a_{i,j}^{p^{n}}x^{ip^{n}}y^{jp^{n}}.

Note that if f and g are disjoint, then (f + g)^{(p^{n})} = f^{(p^{n})} + g^{(p^{n})}. For products we need different requirements. If f, g, and f · g have exactly m_{1}, m_{2}, and m_{1}m_{2} monomials of distinct degrees, then (f · g)^{(p^{n})} = f^{(p^{n})} · g^{(p^{n})}.

Definition 4.3. Given f ∈ W(𝕜)[x, y], define

ψ_{1}(f) =^{def} π (\frac{f^{(p)} − f^{p}}{p} ) .

Also, given f ∈ 𝕜[x_{0}, y_{0}], let f denote its Teichmüller lift. Then, we define ψ_{1}(f) =^{def} ψ_{1}(f). We define ψ_{1} in the analogous way for polynomials in more variables.

The function ψ_{1} was introduced in Definition 2.6 of [Fin04]. As observed there, one can easily compute ψ_{1}(f) without having to lift it: if f is a single monomial, then ψ_{1}(f) = 0 and if f = f_{1} + f_{2}, where f_{1} and f_{2} are disjoint, then one can easily check that

ψ_{1}(f) = ψ_{1}(f_{1}) + ψ_{1}(f_{2}) − ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i}.  (4.1)

In particular, we have that S̄_{1} = X_{1} + Y_{1} + ψ_{1}(X_{0} + Y_{0}).

This allows us to compute ψ_{1}(f) recursively, and in trying to speed up the computation of ψ_{1}, one could try writing f = f_{1} + f_{2} where f_{2} is a single monomial from f, which would give us ψ_{1}(f_{2}) = 0 in the equation above, and hence we would not need to compute this term. But in fact, the most efficient way is to actually split f as the sum of two polynomial with about half of its monomials each, as the powers that show up in the summation are taken from polynomials with less terms. Moreover, this approach allows the algorithm to use multiple processors in parallel, by sending ψ_{1}(f_{1}) and ψ_{1}(f_{2}) to different processors.

Note that we have to interpret formula (4.1) with care, as again we are in characteristic p, while it seems that we are dividing by p. But obviously, for i = 1, …, (p − 1), we have that \binom{p}{i} is divisible by p. To avoid any further confusion of this sort, we introduce some extra notation:

Definition 4.4. We define,

bin_{a}(i) =^{def} \frac{1}{a}\binom{a}{i},

and (with p implicit)

w_{2}(i) =^{def} \frac{i − i^{p}}{p} .

Finally, we write bin_{p}^{(2)}(i) =^{def} −w_{2}(bin_{p}(i)).

Hence, for all i ∈ ℤ we have w_{2}(i) ∈ ℤ, and if p does not divide i, we also have bin_{p}(i), bin_{p^{2}}(i), bin_{p}^{(2)}(i) ∈ ℤ.

Besides allowing us to compute S̄_{1}, the function ψ_{1} also can be used to compute the second coordinate of the Greenberg transform without performing sums and products of Witt vectors. More precisely, Lemma 8.1 from [Fin04] gives us:

Proposition 4.5. Let

f(x, y) = ∑_{i,j} a_{i,j} x^{i}y^{j} ∈ W_{2}(𝕜)[x, y],

and f(x_{0}, y_{0}) ∈ 𝕜[x_{0}, y_{0}] be its reduction modulo p. Then, if a_{i,j} = (a_{i,j,0}, a_{i,j,1}), we have that the second coordinate of the Greenberg transform of f is

(f_{x_{0}})^{p}x_{1} + (f_{y_{0}})^{p}y_{1} + ∑_{i,j} a_{i,j,1} x_{0}^{ip}y_{0}^{jp} + ψ_{1}(f),

where f_{x_{0}} and f_{y_{0}} denote the partial derivatives of f.

As we shall see later, computing the Greenberg transform directly makes the process much more efficient and uses much less memory. So, the initial goal is to obtain a similar result for the third coordinate of the Greenberg transform.

We shall need a function ψ_{2} similar to ψ_{1}, which we break down into a few auxiliary functions to simplify the exposition.

Definition 4.6. Let f, f_{1}, f_{2}, … ∈ 𝕜[x_{0}, y_{0}] and f, f_{1}, f_{2}, … ∈ W(𝕜)[x, y] be their respective Teichmüller lifts. (Also remember that π denotes the reduction modulo p.) Define:

(1)

θ(f_{1}, f_{2}, i) =^{def} θ(f_{1}, f_{2}, i) =^{def} π (\frac{(f_{1}^{(p)})^{i} (f_{2}^{(p)})^{p−i} − f_{1}^{ip}f_{2}^{p(p−i)}}{p} );

(2)

μ(f) =^{def} μ(f) =^{def} π (\frac{(f^{(p)})^{p} − f^{p^{2}}}{p^{2}} );

(3)

λ(f) =^{def} λ(f) =^{def} π (\frac{1}{p} [\frac{f^{(p^{2})} − (f^{(p)})^{p}}{p} − (\frac{f^{(p)} − f^{p}}{p} )^{p}]);

(4)

ψ_{2}(f) =^{def} μ(f) + λ(f).

(5) Define

η_{1}(f_{1}, f_{2}) =^{def} − ∑_{i=1}^{p−1} bin_{p}(i)f_{1}^{i}f_{2}^{p−i}.

Inductively, define for n ≥ 3,

η_{1}(f_{1}, …, f_{n}) =^{def} η_{1}(f_{1}, f_{2} + ⋯ + f_{n}) + η_{1}(f_{2}, …, f_{n}).

We shall also define η_{1}(f) =^{def} 0. (Note that

η_{1}(f_{1}, …, f_{n}) = ψ_{1}(X_{1} + ⋯ + X_{n})|_{X_{1}=f_{1},...,X_{n}=f_{n}} ,

where we compute ψ_{1}(X_{1} + ⋯ + X_{n}) before evaluating X_{i} at f_{i}.)

(6) Finally, similarly to η_{1}, we define

η_{2}(f_{1}, …, f_{n}) =^{def} ψ_{2}(X_{1} + ⋯ + X_{n})|_{X_{1}=f_{1},...,X_{n}=f_{n}} .

One should observe that the p^{i}’s appearing in the denominators above will not cause problems with the reductions modulo p, as one can easily verify that the corresponding numerators are congruent to zero modulo p^{i}. (This also follows from the recursive formulas in the next section.)

5. Computations in Characteristic p

As we shall see in Theorem 6.1, the function ψ_{2} appears in the computation of the third coordinate of the Greenberg transform of a polynomial. But, computing ψ_{2}(f) by lifting f, as in the definition, can be quite demanding. Computations are greatly improved if one stays in characteristic p. We now show how we can compute μ(f), λ(f), and ψ_{2}(f) without having to lift f. The idea is the same as with ψ_{1}, i.e., to use a recursion based on the number of monomials.

Proposition 5.1. Let f ∈ 𝕜[x_{0}, y_{0}]. If f has a single monomial, then μ(f) = 0. If f has two or more monomials, let f = f_{1} + f_{2}, where f_{1} and f_{2} are disjoint. Then,

μ(f) = μ(f_{1}) + μ(f_{2}) − ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{2}−1}bin_{p^{2}}(i)f_{1}^{i}f_{2}^{p^{2}−i} + ∑_{i=1}^{p−1} bin_{p}(i)θ(f_{1}, f_{2}, i).

Proof. Let f, f_{1}, and f_{2} be the Teichmüller lifts of f, f_{1} and f_{2} respectively. Then, observing that \binom{p^{2}}{ip} ≡ \binom{p}{i} (mod p^{3}) (see, for instance, Theorem 1 of [DW93]) and f_{1} and f_{2} are disjoint, we have

\frac{(f^{(p)})^{p} − (f)^{p^{2}}}{p^{2}} = \frac{(f_{1}^{(p)} + f_{2}^{(p)})^{p} − (f_{1} + f_{2})^{p^{2}}}{p^{2}}

= \frac{(f_{1}^{(p)})^{p} − f_{1}^{p^{2}}}{p^{2}} + \frac{(f_{2}^{(p)})^{p} − f_{2}^{p^{2}}}{p^{2}} − ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{2}−1} \frac{1}{p^{2}} \binom{p^{2}}{i}f_{1}^{i}f_{2}^{p^{2}−i}

+ \frac{1}{p^{2}} [∑_{i=1}^{p−1} \binom{p}{i}(f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − ∑_{i=1}^{p−1} \binom{p^{2}}{ip}f_{1}^{ip}f_{2}^{p^{2}−ip}]

≡ \frac{(f_{1}^{(p)})^{p} − f_{1}^{p^{2}}}{p^{2}} + \frac{(f_{2}^{(p)})^{p} − f_{2}^{p^{2}}}{p^{2}} − ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{2}−1} \frac{1}{p^{2}} \binom{p^{2}}{i}f_{1}^{i}f_{2}^{p^{2}−i}

+ ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}\frac{(f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − f_{1}^{ip}f_{2}^{p(p−i)}}{p} (mod p).

Since all coefficients are integers, reducing the equation modulo p gives us the desired formula. □

Now, on to λ:

Proposition 5.2. Let f ∈ 𝕜[x_{0}, y_{0}]. If f has a single monomial, then λ(f) = 0. If f has two or more monomials, let f = f_{1} + f_{2}, where f_{1} and f_{2} are disjoint. Also, let

v =^{def} (− bin_{p}(1)f_{1}f_{2}^{p−1}, − bin_{p}(2)f_{1}^{2}f_{2}^{p−2}, …, − bin_{p}(p − 1)f_{1}^{p−1}f_{2}) .

Then,

λ(f) = λ(f_{1}) + λ(f_{2}) + η_{1}(ψ_{1}(f_{1}), ψ_{1}(f_{2})) + η_{1}(ψ_{1}(f_{1}) + ψ_{1}(f_{2}), η_{1}(f_{1}, f_{2}))

+ η_{1}(v) + ∑_{i=1}^{p−1} bin_{p}^{(2)}(i)f_{1}^{ip}f_{2}^{(p−i)p} − ∑_{i=1}^{p−1} bin_{p}(i)θ(f_{1}, f_{2}, i).

Proof. Let f, f_{1}, and f_{2} be the Teichmüller lifts of f, f_{1} and f_{2} respectively. Then,

\frac{1}{p} [\frac{f_{1}^{(p^{2})} + f_{2}^{(p^{2})} − (f_{1}^{(p)} + f_{2}^{(p)})^{p}}{p} − (\frac{(f_{1}^{(p)} + f_{2}^{(p)}) − (f_{1} + f_{2})^{p}}{p} )^{p}]

= \frac{1}{p} [\frac{f_{1}^{(p^{2})} − (f_{1}^{(p)})^{p}}{p} + \frac{f_{2}^{(p^{2})} − (f_{2}^{(p)})^{p}}{p} − ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}(f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i}

− (\frac{f_{1}^{(p)} − f_{1}^{p}}{p} + \frac{f_{2}^{(p)} − f_{2}^{p}}{p} − ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p}]

= \frac{1}{p} [\frac{f_{1}^{(p^{2})} − (f_{1}^{(p)})^{p}}{p} + \frac{f_{2}^{(p^{2})} − (f_{2}^{(p)})^{p}}{p} − (\frac{f_{1}^{(p)} − f_{1}^{p}}{p} + \frac{f_{2}^{(p)} − f_{2}^{p}}{p} )^{p}

− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}(f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p}]

− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i} (\frac{f_{1}^{(p)} − f_{1}^{p}}{p} + \frac{f_{2}^{(p)} − f_{2}^{p}}{p} )^{i} (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p−i}

= \frac{1}{p} [\frac{f_{1}^{(p^{2})} − (f_{1}^{(p)})^{p}}{p} − (\frac{f_{1}^{(p)} − f_{1}^{p}}{p} )^{p} + \frac{f_{2}^{(p^{2})} − (f_{2}^{(p)})^{p}}{p} − (\frac{f_{2}^{(p)} − f_{2}^{p}}{p} )^{p}]

+ \frac{1}{p} [− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}(f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p}]

− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i} (\frac{f_{1}^{(p)} − f_{1}^{p}}{p} )^{i} (\frac{f_{2}^{(p)} − f_{2}^{p}}{p} )^{p−i}

− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i} (\frac{f_{1}^{(p)} − f_{1}^{p}}{p} + \frac{f_{2}^{(p)} − f_{2}^{p}}{p} )^{i} (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p−i} .

Now, the first bracket clearly reduces to λ(f_{1}) + λ(f_{2}), while the last two sums reduce to η_{1}(ψ_{1}(f_{1}), ψ_{1}(f_{2})) and η_{1}(ψ_{1}(f_{1}) + ψ_{1}(f_{2}), η_{1}(f_{1}, f_{2})).

Now,

\frac{1}{p} [− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}(f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p}]

= ∑_{i=1}^{p−1} \frac{1}{p} [(\frac{1}{p}\binom{p}{i})^{p} − \frac{1}{p}\binom{p}{i}] (f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i}

+ \frac{1}{p} [− ∑_{i=1}^{p−1} (\frac{1}{p}\binom{p}{i})^{p} (f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p}] .

The first term then clearly reduces to

∑_{i=1}^{p−1} bin_{p}^{(2)}(i)f_{1}^{ip}f_{2}^{(p−i)p}.

So, to finish the proof we need to show that the second term reduces to

η_{1}(v) − ∑_{i=1}^{p−1} bin_{p}(i)θ(f_{1}, f_{2}, i).

But, if p ≠ 2,

\frac{1}{p} [− ∑_{i=1}^{p−1} (\frac{1}{p}\binom{p}{i})^{p} (f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p}]

= − ∑_{i=1}^{p−1} (\frac{1}{p}\binom{p}{i})^{p} \frac{(f_{1}^{(p)})^{i}(f_{2}^{(p)})^{p−i} − f_{1}^{pi}f_{2}^{(p−i)p}}{p}

+ \frac{1}{p} [− ∑_{i=1}^{p−1} (\frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p} − (− ∑_{i=1}^{p−1} \frac{1}{p}\binom{p}{i}f_{1}^{i}f_{2}^{p−i})^{p}]

Reducing modulo p gives the desired result. For p = 2, this term is zero, which yields the correct result in this case. □

The previous propositions give the following immediate corollary:

Corollary 5.3. Let f ∈ 𝕜[x_{0}, y_{0}]. If f has a single monomial, then ψ_{2}(f) = 0. If f has two or more monomials, let f = f_{1} + f_{2}, where f_{1} and f_{2} are disjoint. Also, let

v =^{def} (− bin_{p}(1)f_{1}f_{2}^{p−1}, − bin_{p}(2)f_{1}^{2}f_{2}^{p−2}, …, − bin_{p}(p − 1)f_{1}^{p−1}f_{2}) .

Then,

ψ_{2}(f) = ψ_{2}(f_{1}) + ψ_{2}(f_{2}) + η_{1}(ψ_{1}(f_{1}), ψ_{1}(f_{2})) + η_{1}(ψ_{1}(f_{1}) + ψ_{1}(f_{2}), η_{1}(f_{1}, f_{2}))

+ η_{1}(v) − ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{2}−1}bin_{p^{2}}(i)f_{1}^{i}f_{2}^{p^{2}−i} + ∑_{i=1}^{p−1} bin_{p}^{(2)}(i)f_{1}^{ip}f_{2}^{(p−i)p}.

One should observe that the optimal way to split f as f_{1} + f_{2} in this case depends on the number of terms. Our experiments seem to indicate that if f has few elements, then it is faster to take f_{1} as one of the monomials of f, as then ψ_{2}(f_{1}) and η_{1}(ψ_{1}(f_{1}), ψ_{1}(f_{2})) are both automatically zero. On the other hand, if f has many terms, it is better again to have f_{1} and f_{2} have roughly half as many terms as f.

Now, using η_{1} and η_{2}, we can compute S̄_{2} and P̄_{2} directly in characteristic p:

Proposition 5.4. Let S̄_{i} and P̄_{i} be the polynomials over 𝔽_{p} that give sum and product of Witt vectors in characteristic p (as in Eqs. (2.6) to (2.9)). We have:

S̄_{1} = X_{1} + Y_{1} + η_{1}(X_{0}, Y_{0}),  (5.1)
P̄_{1} = X_{1}Y_{0}^{p} + X_{0}^{p}Y_{1},  (5.2)

and

S̄_{2} = X_{2} + Y_{2} + η_{1}(X_{1}, Y_{1}) + η_{1}(X_{1} + Y_{1}, η_{1}(X_{0}, Y_{0})) + η_{2}(X_{0}, Y_{0}),  (5.3)
P̄_{2} = X_{2}Y_{0}^{p^{2}} + X_{1}^{p}Y_{1}^{p} + X_{0}^{p^{2}}Y_{2} + η_{1}(X_{1}Y_{0}^{p}, X_{0}^{p}Y_{1}).  (5.4)

Proof. The first two formulas are immediate, observing that ψ_{1}(X_{0} + Y_{0}) = η_{1}(X_{0}, Y_{0}). Also, the fourth formula follows from Eq. (2.9) and the definition of η_{1}.

To prove formula (5.3) we use formula (2.8). We shall consider

\frac{1}{p} (X_{1}^{p} + Y_{1}^{p} − (X_{1} + Y_{1} + \frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} )^{p}) + \frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0} + Y_{0})^{p^{2}}}{p^{2}}

in characteristic 0 and show that it reduces modulo p to η_{1}(X_{1}, Y_{1})+η_{1}(X_{1}+Y_{1}, η_{1}(X_{0}, Y_{0}))+ η_{2}(X_{0}, Y_{0}). Since

η_{1}(X, Y) = − ∑_{i=1}^{p−1} bin_{p}(i)X^{i}Y^{p−i}

(also in characteristic 0), we have that the above expression can be simplified as:

\frac{1}{p} (X_{1}^{p} + Y_{1}^{p} − (X_{1} + Y_{1} + η_{1}(X_{0}, Y_{0}))^{p}) + \frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0} + Y_{0})^{p^{2}}}{p^{2}}

= \frac{1}{p} (X_{1}^{p} + Y_{1}^{p} − (X_{1} + Y_{1})^{p}) + η_{1} (X_{1} + Y_{1}, η_{1}(X_{0}, Y_{0}))

+ \frac{1}{p} (\frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0} + Y_{0})^{p^{2}}}{p} − (\frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} )^{p})

= η_{1}(X_{1}, Y_{1}) + η_{1} (X_{1} + Y_{1}, η_{1}(X_{0}, Y_{0}))

+ \frac{1}{p} (\frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0} + Y_{0})^{p^{2}}}{p} − \frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0}^{p} + Y_{0}^{p})^{p}}{p} )

+ \frac{1}{p} (\frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0}^{p} + Y_{0}^{p})^{p}}{p} − (\frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} )^{p})

= η_{1}(X_{1}, Y_{1}) + η_{1} (X_{1} + Y_{1}, η_{1}(X_{0}, Y_{0}))

+ \frac{1}{p} (\frac{(X_{0}^{p} + Y_{0}^{p})^{p} − (X_{0} + Y_{0})^{p^{2}}}{p} )

+ \frac{1}{p} (\frac{X_{0}^{p^{2}} + Y_{0}^{p^{2}} − (X_{0}^{p} + Y_{0}^{p})^{p}}{p} − (\frac{X_{0}^{p} + Y_{0}^{p} − (X_{0} + Y_{0})^{p}}{p} )^{p}) ,

which reduces to η_{1}(X_{1}, Y_{1}) + η_{1}(X_{1} + Y_{1}, η_{1}(X_{0}, Y_{0})) + μ(X_{0} + Y_{0}) + λ(X_{0} + Y_{0}), yielding the desired formula. □

It is worth mentioning that we also have

P̄_{3} = X_{0}^{p^{3}}Y_{3} + X_{1}^{p^{2}}Y_{2}^{p} + X_{2}^{p}Y_{1}^{p^{2}} + X_{3}Y_{0}^{p^{3}}

+ η_{1}(X_{0}^{p^{2}}Y_{2}, X_{2}Y_{0}^{p^{2}}) + η_{1}(X_{0}^{p^{2}}Y_{2} + X_{2}Y_{0}^{p^{2}}, η_{1}(X_{0}^{p}Y_{1}, X_{1}Y_{0}^{p}))

+ η_{1}(X_{0}^{p^{2}}Y_{2} + X_{2}Y_{0}^{p^{2}} + η_{1}(X_{0}^{p}Y_{1}, X_{1}Y_{0}^{p}), X_{1}^{p}Y_{1}^{p}) + η_{2}(X_{0}^{p}Y_{1}, X_{1}Y_{0}^{p}). (5.5)

The proof is not too hard if one realizes that many terms similar to Eq. (2.8) appear with X_{0}, Y_{0}, X_{1}, and Y_{1} replaced by X_{0}^{p}Y_{1}, X_{1}Y_{0}^{p}, X_{0}^{p^{2}}Y_{2}, and X_{2}Y_{0}^{p^{2}} respectively. Then, the same ideas that led Eq. (2.8) to Eq. (5.3), with only a small manipulation involved, give us Eq. (5.5). (The formula for S̄_{3} should be much more involved.)

6. The Third Coordinate of the Greenberg Transform

We now give the formula for the third coordinate of the Greenberg transform of a polynomial.

Theorem 6.1. Let f ∈ W(𝕜)[x, y] be given by

f(x, y) = ∑_{i,j} a_{i,j}x^{i}y^{j},

with partial derivatives with respect to x and y

f_{x}(x, y) = ∑_{i,j} b_{i,j}x^{i}y^{j},  and  f_{y}(x, y) = ∑_{i,j} c_{i,j}x^{i}y^{j},

respectively. Also, let f be the reduction modulo p of f (and use subscripts x_{0} and y_{0} to denote its partial derivatives), and

a_{i,j} ≡ (a_{i,j,0}, a_{i,j,1}, a_{i,j,2}) (mod p^{3}),
b_{i,j} ≡ (b_{i,j,0}, b_{i,j,1}, b_{i,j,2}) (mod p^{3}),
c_{i,j} ≡ (c_{i,j,0}, c_{i,j,1}, c_{i,j,2}) (mod p^{3}).

Then, the third coordinate of the Greenberg transform of f is given by

f_{x_{0}}^{p^{2}}x_{2} + f_{y_{0}}^{p^{2}}y_{2} + (∑_{i,j} b_{i,j,1}x_{0}^{ip}y_{0}^{jp})^{p} x_{1}^{p} + (∑_{i,j} c_{i,j,1}x_{0}^{ip}y_{0}^{jp})^{p} y_{1}^{p}

+ (f_{x_{0}x_{0}}/2)^{p^{2}}x_{1}^{2p} + f_{x_{0}y_{0}}^{p^{2}}x_{1}^{p}y_{1}^{p} + (f_{y_{0}y_{0}}/2)^{p^{2}}y_{1}^{2p} + ∑_{i,j} a_{i,j,2}x_{0}^{ip^{2}}y_{0}^{jp^{2}}

+ ψ_{1}(f_{x_{0}}^{p}x_{1} + f_{y_{0}}^{p}y_{1} + ∑_{i,j} a_{i,j,1}x_{0}^{ip}y_{0}^{jp})

+ η_{1}(f_{x_{0}}^{p}x_{1} + f_{y_{0}}^{p}y_{1} + ∑_{i,j} a_{i,j,1}x_{0}^{ip}y_{0}^{jp}, ψ_{1}(f)) + ψ_{2}(f). (6.1)

Note that since for all n ∈ ℤ we have that

n ≡ (n, w_{2}(n)) (mod p^{2}),  (6.2)

(with w_{2} as in Definition 4.4) we obtain

b_{i,j,1} = (i+1)^{p}a_{i+1,j,1}+w_{2}(i+1)a_{i+1,j,0}^{p},  c_{i,j,1} = (j +1)^{p}a_{i,j+1,1}+w_{2}(j +1)a_{i,j+1,0}^{p}. (6.3)

Also, observe that the formula does work for p = 2 if we interpret the division by 2 as an abuse of notation with the natural meaning, i.e, if we consider the terms i(i − 1)/2 that appear in the second order derivatives as the reduction modulo 2 of this integer.

Proof of Theorem 6.1. Let f_{0} be the Teichmüller lift of f, a_{i,j,k}, b_{i,j,k}, and c_{i,j,k} be the Teichmüller lifts of a_{i,j,k}, b_{i,j,k} and c_{i,j,k} respectively, and

f_{1} =^{def} (∑_{i,j} b_{i,j,0}^{p}x_{0}^{ip}y_{0}^{jp}) x_{1} + (∑_{i,j} c_{i,j,0}^{p}x_{0}^{ip}y_{0}^{jp}) y_{1} + ∑_{i,j} a_{i,j,1}x_{0}^{ip}y_{0}^{jp} + (\frac{f_{0}^{(p)} − f_{0}^{p}}{p} ) .

Hence, by Proposition 4.5, f_{0} and f_{1} reduce the first two coordinates of the Greenberg transform of f.

Thus, by Theorem 3.2, it suffices to show that

f_{2} =^{def} \frac{1}{p^{2}} [f^{σ^{2}}(x_{0}^{p^{2}} + px_{1}^{p} + p^{2}x_{2}, y_{0}^{p^{2}} + py_{1}^{p} + p^{2}y_{2}) − f_{0}^{p^{2}} − pf_{1}^{p}]

is in W(𝕜)[x_{0}, x_{1}, x_{2}, y_{0}, y_{1}, y_{2}] and reduces to Eq. (6.1) modulo p.

To simplify the notation, let g =^{def} f^{σ^{2}}. Then, using Taylor expansion, we obtain

g(x_{0}^{p^{2}} + px_{1}^{p} + p^{2}x_{2}, y_{0}^{p^{2}} + py_{1}^{p} + p^{2}y_{2}) ≡ g(x_{0}^{p^{2}}, y_{0}^{p^{2}})

+ g_{x_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})(px_{1}^{p} + p^{2}x_{2}) + g_{y_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})(py_{1}^{p} + p^{2}y_{2}) + \frac{1}{2}g_{x_{0}x_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})(px_{1}^{p})^{2}

+ g_{x_{0}y_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})(px_{1}^{p})(py_{1}^{p}) + \frac{1}{2}g_{y_{0}y_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})(py_{1}^{p})^{2} (mod p^{3}).

By Eq. (2.11), a_{i,j} ≡ a_{i,j,0} + pa_{i,j,1}^{1/p} + p^{2}a_{i,j,2}^{1/p^{2}} (mod p^{3}), and hence, σ^{2}(a_{i,j}) ≡ a_{i,j,0}^{p^{2}} + pa_{i,j,1}^{p} + p^{2}a_{i,j,2} (mod p^{3}). Then, we have that

g(x_{0}^{p^{2}}, y_{0}^{p^{2}}) ≡ f_{0}^{σ^{2}}(x_{0}^{p^{2}}, y_{0}^{p^{2}}) + p ∑_{i,j} a_{i,j,1}^{p}x_{0}^{ip^{2}}y_{0}^{jp^{2}} + p^{2} ∑_{i,j} a_{i,j,2}x_{0}^{ip^{2}}y_{0}^{jp^{2}} (mod p^{3}).

Now, since σ is a homomorphism which fixes ℤ, we have that (f^{σ^{2}})_{x_{0}} = (f_{x_{0}})^{σ^{2}} and (f^{σ^{2}})_{y_{0}} = (f_{y_{0}})^{σ^{2}}. Thus,

g_{x_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}}) ≡ ∑_{i,j} b_{i,j,0}^{p^{2}}x_{0}^{ip^{2}}y_{0}^{jp^{2}} + p ∑_{i,j} b_{i,j,1}^{p}x_{0}^{ip^{2}}y_{0}^{jp^{2}} (mod p^{2})

and

g_{y_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}}) ≡ ∑_{i,j} c_{i,j,0}^{p^{2}}x_{0}^{ip^{2}}y_{0}^{jp^{2}} + p ∑_{i,j} c_{i,j,1}^{p}x_{0}^{ip^{2}}y_{0}^{jp^{2}} (mod p^{2}).

Therefore,

f_{2} ≡ \frac{1}{p^{2}} [f_{0}^{σ^{2}}(x_{0}^{p^{2}}, y_{0}^{p^{2}}) − f_{0}^{p^{2}}]

+ \frac{1}{p} [∑_{i,j} a_{i,j,1}^{p}x_{0}^{ip^{2}}y_{0}^{jp^{2}} + (∑_{i,j} b_{i,j,0}^{p^{2}}x_{0}^{ip^{2}}y_{0}^{jp^{2}} ) x_{1}^{p} + (∑_{i,j} c_{i,j,0}^{p^{2}}x_{0}^{ip^{2}}y_{0}^{jp^{2}} ) y_{1}^{p} − f_{1}^{p}]

+ ∑_{i,j} a_{i,j,2}x_{0}^{ip^{2}}y_{0}^{jp^{2}} + (∑_{i,j} b_{i,j,0}^{p^{2}}x_{0}^{ip^{2}}y_{0}^{jp^{2}} ) x_{2} + (∑_{i,j} b_{i,j,1}^{p}x_{0}^{ip^{2}}y_{0}^{jp^{2}} ) x_{1}^{p}

+ (∑_{i,j} c_{i,j,0}^{p^{2}}x_{0}^{ip^{2}}y_{0}^{jp^{2}} ) y_{2} + (∑_{i,j} c_{i,j,1}^{p}x_{0}^{ip^{2}}y_{0}^{jp^{2}} ) y_{1}^{p} + \frac{1}{2}g_{x_{0}x_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})x_{1}^{2p}

+ g_{x_{0}y_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})x_{1}^{p}y_{1}^{p} + \frac{1}{2}g_{y_{0}y_{0}}(x_{0}^{p^{2}}, y_{0}^{p^{2}})y_{1}^{2p} (mod p), (6.4)

where the congruence sign means that the difference between the left hand and right hand sides is in pW(𝕜)[x_{0}, x_{1}, x_{2}, y_{0}, y_{1}, y_{2}]. Now, clearly, the last three lines of Eq. (6.4) reduce modulo p to the first two lines of Eq. (6.1).

If, again to simplify notation, we let

h =^{def} (∑_{i,j} b_{i,j,0}^{p}x_{0}^{ip}y_{0}^{jp}) x_{1} + (∑_{i,j} c_{i,j,0}^{p}x_{0}^{ip}y_{0}^{jp}) y_{1} + ∑_{i,j} a_{i,j,1}x_{0}^{ip}y_{0}^{jp},

then we can rewrite the first two lines of the right hand side of Eq. (6.4) as

\frac{f_{0}^{(p^{2})} − f_{0}^{p^{2}}}{p^{2}} + \frac{1}{p} [h^{(p)} − (h + (\frac{f_{0}^{(p)} − f_{0}^{p}}{p} ))^{p}]

= \frac{f_{0}^{(p^{2})} − f_{0}^{p^{2}}}{p^{2}} − \frac{1}{p} (\frac{f_{0}^{(p)} − f_{0}^{p}}{p} )^{p} + \frac{h^{(p)} − h^{p}}{p} − ∑_{i=1}^{p−1} \frac{1}{p}\binom{i}{p}h^{i} (\frac{f_{0}^{(p)} − f_{0}^{p}}{p} )^{p−i} .

Now, using Definition 4.6, it is clear that the expression above is in W(𝕜)[x_{0}, x_{1}, x_{2}, y_{0}, y_{1}, y_{2}] and reduces to

ψ_{2}(f) + ψ_{1}(f_{x_{0}}^{p}x_{1} + f_{y_{0}}^{p}y_{1} + ∑_{i,j} a_{i,j,1}x_{0}^{ip}y_{0}^{jp}) + η_{1}(f_{x_{0}}^{p}x_{1} + f_{y_{0}}^{p}y_{1} + ∑_{i,j} a_{i,j,1}x_{0}^{ip}y_{0}^{jp}, ψ_{1}(f))

modulo p, concluding the proof. □

7. Complexity Analysis

We now give a brief analysis of the complexity of the new method to compute the Greenberg transform of a polynomial. Some explicit comparisons are made in Section 8.

The main difficulty here is that the complexity is based on the number of (non-zero) terms of the polynomial, and it is difficult to give precise bounds for this number after a few operations.

We will consider that the polynomials are stored as sparse, i.e., the zero terms are not stored and do not affect the number of operations. Furthermore, we will disregard the additions of the degrees of the variables when counting operations, i.e., the multiplication of two monomials will be counted as a single operation.

Then, if f_{1} and f_{2} are polynomials of n_{1} and n_{2} terms respectively, then the product f_{1} · f_{2} requires n_{1}n_{2} products and (n_{1}n_{2} − 1) sums, and so O(n_{1}n_{2}) operations on the base ring. The largest possible number of terms for f_{1} · f_{2} is n_{1}n_{2}. In particular, for k ∈ ℤ_{>0}, we have that f_{1}^{k} requires O(n_{1}^{k}) operations and has at most n_{1}^{k} terms. In fact, it is easy to prove that it will have necessarily less terms than that, but in the worst case scenario it would still have O(n_{1}^{k}) terms. On the other hand, if f_{1} is a polynomial of degree (n_{1} − 1) in one variable, it would have at most (kn_{1} − k + 1) terms, which in general is considerably less than n_{1}^{k}.

We now look at the complexity of computing ∑_{i=1}^{p−1} bin_{p}(i)f_{1}^{i}f_{2}^{p−i}. We need, in the worst case, O(n_{i}^{p−1}) operations to compute the f_{i}^{2}, …, f_{i}^{p−1}. Let’s assume that n_{1} ≤ n_{2}. Then, we need at most O(n_{1}n_{2}^{p−1}) operations to compute the products f_{1}^{i}f_{2}^{p−i}, and p operations to sum, yielding O(n_{1}n_{2}^{p−1}) operations total.

Now, let N_{1}(f) be the number of operations performed in computing ψ_{1}(f), where f has n terms. Then, by Eq. (4.1), we have that N_{1}(f) = N_{1}(f_{1}) + N_{1}(f_{2}) + O(n_{1}n_{2}^{p−1}), where f = f_{1} + f_{2} and n = n_{1} + n_{2}. (We shall keep this notation through out this section.) Although in practice it seems that it is best to take n_{1} and n_{2} as approximately n/2, the number of operations is always O(n^{p}). Of course, in this case the operations are in characteristic p, i.e., in 𝕜. Observe that to compute ψ_{1}(f) by lifting it (as in Definition 4.3) requires O(n^{p}) operations in (a ring of) characteristic p^{2}, i.e., in W_{2}(𝕜).

We now look at terms that appear in Corollary 5.3, so that we can then analyze ψ_{2}(f). We start with η_{1}(v). Let v = (g_{1}, …, g_{k}) and assume that g_{i} has m_{i} monomials with m_{1} ≤ m_{2} ≤ ⋯ ≤ m_{k}, and let m = m_{1} + ⋯ + m_{k}. Now, partition the indices {1, …, k} into two (disjoint) subsets and let h_{1} and h_{2} be the sums of the g_{i}’s with respect to these two subsets. (Hence, h_{1} + h_{2} = g_{1} + ⋯ + g_{k}.) After possible reordering, we can assume h_{1} = g_{1} + ⋯ + g_{r} and h_{2} = g_{r+1} + ⋯ + g_{k}. Let l_{i} be the number of terms of h_{i}, and assume l_{1} ≤ l_{2}. In the worst case, we have that l_{1} +l_{2} = m. So, if N_{2}(v) is the number of operations necessary to compute η_{1}(v), then, since

η_{1}(v) = η_{1}(g_{1}, …, g_{r}) + η_{1}(g_{r+1}, …, g_{k}) + η_{1}(g_{1} + ⋯ + g_{r}, g_{r+1} + ⋯ + g_{k}),

we have that N_{2}(v) = N_{2}(g_{1}, …, g_{r}) + N_{2}(g_{r+1}, …, g_{k}) + O(l_{1}l_{2}^{p−1}). As before, this gives us O(m^{p}) operations. Hence, if k = (p − 1) and g_{i} = f_{1}^{i}f_{2}^{(p−i)}, with f, n, f_{i}, and n_{i} as above, and if n_{1} and n_{2} are approximately n/2 again, then we have that η_{1}(v) requires O(n^{p^{2}}) operations.

Now, let g_{i} =^{def} ψ_{1}(f_{i}), for i = 1, 2. As observed, we have that the number of terms of g_{i}, say m_{i} with m_{1} ≤ m_{2}, is O(n_{i}^{p}). So, η_{1}(g_{1}, g_{2}) requires O(m_{1}m_{2}^{p−1}) operations. If n_{1} and n_{2} are again approximately n/2, we need at most O(n^{p^{2}}) operations to compute η_{1}(g_{1}, g_{2}).

To compute η_{1}(g_{1} + g_{2}, η_{1}(f_{1}, f_{2})), with the g_{i}’s as above, we have that g_{1} + g_{2} and η_{1}(f_{1}, f_{2}) will have O(n^{p}) terms, requiring then O(n^{p^{2}}) operations.

Finally, computing

∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{2}−1}bin_{p^{2}}(i)f_{1}^{i}f_{2}^{p^{2}−i}  and  ∑_{i=1}^{p−1} bin_{p}^{(2)}(i)f_{1}^{ip}f_{2}^{(p−i)p}

require O(n^{p^{2}}) and O(n^{p}) operations respectively. (Note that if f has n terms, computing f^{p} requires at most O(n(p−1)), even without using successive squaring.) Hence, computing ψ_{2}(f) requires O(n^{p^{2}}) operations.

Thus, by Eq. (6.1), we have that computing the Greenberg transform of f when its reduction modulo p, say f, has n terms and f itself has less that n^{p} terms, takes O(n^{p^{2}}) operations in 𝕜. Computing using Eq. (6.4) takes O(n^{p^{2}}) operations in W_{3}(𝕜).

8. Performance Improvements

We show some concrete the improvements in processing and memory usage obtained from the results in the previous sections. All the tests were performed on a Dell Precision 690 server with two dual-core 64 bit 3.2 gigahertz Inter Xeon processors, 16 gigabytes of RAM, and 8 gigabytes of swap, running Fedora Core 11 (GNU/Linux) with kernel 2.6.30. Also, we used the softwares MAGMA (version 2.16-1) and Sage (version 4.3) in the tests. Most of the files used to run the tests described in here can be found, at the time of writing, at

                  http://www.math.utk.edu/~finotti/comp/.

Note that neither MAGMA nor Sage takes advantage of the four cores available when processing the computations (a single core is used), which could speed up the computations even further, as observed before. (It should be mentioned that those softwares might make it possible to use more than one core, but if so, the author is unfamiliar with the proper methods.)

We start by the computations of the polynomials S_{1} and S_{2} for various primes p. The computations of P_{1} and P_{2} are, relatively speaking, much faster, enough for them to be Table 8.1. Time and memory usage on computation of S_{1} and S_{2} in MAGMA.

char. t_{1} (sec) t_{2} (sec) m_{1} (MB) m_{2} (MB)
23  5.589  0.590  26.06  11.96
31  56.100  1.389  68.72  18.38
41 638.029 4.259  210.56  57.80
53 8560.129 14.160  545.75  81.75
71  −−  59.810  −−  240.28
101  −−  363.689  −−  964.91
151  −−  3010.380  −−  4810.53

Table 8.2. Time and memory usage on computation of S_{1} and S_{2} in Sage.

char. t_{1} (sec) t_{2} (sec) m_{1} (MB) m_{2} (MB)
23 211.64 0.57  53.16  4.0
31 3450.87 1.17  115.40  10.5
41  −−  2.99  −−  25.0
53  −−  8.54  −−  63.0
71  −−  31.53  −−  197.5
101  −−  170.04  −−  808.22
151  −− 1266.82  −−  4032.82

considered irrelevant in comparison. (While P_{2} needs O(p) computations in either 𝔽_{p} or W_{3}(𝔽_{p}) ≅ ℤ/p^{3}ℤ, depending on the method used, S_{2} needs O(p^{p}) computations over the same ring.) Tables 8.1 and 8.2 show the time and memory usage to compute these polynomials, in MAGMA and Sage respectively, in two different ways:

(1) Using formulas (2.6) and (2.8) to expand the p · S_{1} and p^{2} · S_{2} in polynomial rings over ℤ/p^{2}ℤ and ℤ/p^{3}ℤ respectively (instead of ℤ), dividing the results by p and p^{2} respectively, and finally reducing modulo p. The time taken in seconds is denoted by t_{1} in Tables 8.1 and 8.2, while the memory usage in megabytes is denoted by m_{1}. (This method is already considerably more efficient than creating a ring of Witt vectors using MAGMA’s built in function. Judging by the comparable times produced in tests, it seems that MAGMA performs the operations above over ℤ.)

(2) Using Proposition 5.4 and computing η_{1} and η_{2} using recursion (as in Corollary 5.3). The time taken in seconds is denoted by t_{2} in Tables 8.1 and 8.2, while the memory usage in megabytes is denoted by m_{2}.

As one can see, the first method is not very efficient in Sage, to the point that we did not bother in even computing many of the values of t_{1} and m_{1}. On the other hand, one can see that Sage is more efficient with the second method.

In any event, Tables 8.1 and 8.2 show considerable improvements in both time and memory usage with the second method. Moreover, it should be observed that one can Table 8.3. Average times to sum two Witt vectors of length 3 in MAGMA.

Field evaluating S_{1} and S_{2} recursive method
𝔽_{11^{15}}  0.017 sec.  0.004 sec.
𝔽_{13^{7}}  0.125 sec.  0.014 sec.
𝔽_{23^{10}}  0.709 sec.  0.058 sec.
𝔽_{43^{4}}  3.475 sec.  0.847 sec.
𝔽_{53^{4}}  8.489 sec.  2.428 sec.
𝔽_{61^{4}}  15.413 sec.  5.055 sec.
𝔽_{101^{20}}  2027.190 sec.  85.779 sec.

Table 8.4. Average times to sum two Witt vectors of length 3 in Sage.

Field evaluating S_{1} and S_{2} recursive method
𝔽_{11^{15}}  4.188 sec.  0.282 sec.
𝔽_{13^{7}}  5.192 sec.  0.271 sec.
𝔽_{23^{10}}  88.346 sec.  1.167 sec.
𝔽_{43^{4}}  782.754 sec.  3.111 sec.
𝔽_{53^{4}}  1959.466 sec.  4.953 sec.
𝔽_{61^{4}}  3509.918 sec.  6.992 sec.
𝔽_{101^{20}}  −−  61.317 sec.

use Proposition 5.4 and the recursive computations of η_{1} and η_{2} to perform sums and products of Witt vectors without computing (and storing in memory) the potentially large polynomials S_{i} and P_{i} (for i = 1, 2). This also often yield considerable improvements when computing sums and products of Witt vectors over finite fields. As the fields get larger, computing sums and products this way outperforms the traditional way of evaluating the polynomials S_{i} and P_{i}, even though both require O(p^{2}) operations in the finite field. For instance, in MAGMA, while over W(𝔽_{31^{4}}) the recursive method computes sums in 0.280 seconds (on average), in this situation evaluating S_{1} and S_{2} computes sums in 0.083 seconds. But, for W(𝔽_{31^{5}}) the recursive method computes (on average) sums in 0.359 seconds, while evaluating S_{1} and S_{2} computes sums in 5.090 seconds. In Sage the second method is already much more efficient over 𝔽_{31^{4}}. It takes in average 1.600 seconds, while evaluation takes in average 192.681 seconds.

Note that those times do not take into account the extra time needed to compute S_{1} and S_{2}, which will also use more memory. Tables 8.3 and 8.4 show average times to sum two vectors over a finite field using these two methods for some relatively large finite fields in MAGMA and Sage respectively. We computed the times using a few random elements (between 7 and 20, depending on the size of the field), but the individual times don’t seem vary much at all from the average shown above.

Table 8.5. Time and memory usage on the computation of the Greenberg transform of quadratic polynomial in MAGMA.

char. t_{1} (sec) t_{2} (sec) t_{3} (sec) m_{1} (MB) m_{2} (MB) m_{3} (MB)
7  0.420 0.410  0.360  11.57  11.28  10.31
11  9.730 4.570  1.909  130.62  107.69  36.38
13 39.929 20.800 7.730  520.12  383.88  94.28
17 758.480 262.910 74.620 4647.69 3032.72 529.75
19  −− 988.269 187.659  −−  7208.94 1124.44
23  −−  −− 1086.250  −−  −−  4185.97

As one can see, Sage is much less efficient than MAGMA, especially with the first method. But still, one can see a great improvement with the second method. (It seems that MAGMA is just much faster performing computations with finite fields, at least at the time of writing.)

Finally we look at computations of Greenberg transform of polynomials with coefficients in rings of Witt vectors over rational function fields, similarly to what is done when computing generic formulas for the canonical liftings. (As mentioned before, we computed J_{i}’s initially using these general formulas.)

First, we consider a quadratic polynomial

x^{2} + (a_{0}, a_{1}, a_{2})x + (b_{0}, b_{1}, b_{2})

over W(𝔽_{p}(a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2})), where the a_{i}’s and b_{i}’s are taken to be algebraically independent transcendental elements over 𝔽_{p}. We computed the Greenberg transform in three different ways:

(1) computing S_{i} and P_{i} (with the faster method described above) for i = 1, 2, and expanding the expression;

(2) computing sums and products of Witt vectors using recursions, as done above;

(3) using the formula given by Theorem 6.1. Tables 8.5 and 8.6 shows the time taken in seconds and memory usage in megabytes for different p in MAGMA and Sage, respectively, with these three different methods. These are denoted by t_{1}, t_{2}, and t_{3}, and m_{1}, m_{2}, and m_{3} respectively.

Also, one can see that although MAGMA is more efficient with respect to time with the first two methods, Sage is more efficient with the third (and best) method. (It is also more efficient with respect to memory in all tests.)

Note that for p = 23, the third coordinate of the Greenberg transform is a polynomial in nine variables, namely the x_{i}’s, a_{i}’s, and b_{i}’s, and has 65553940 terms.

As a second example, we look at the case of a cubic:

x^{3} + (a_{0}, a_{1}, a_{2})x^{2} + (b_{0}, b_{1}, b_{2})x + (c_{0}, c_{1}, c_{2})

Table 8.6. Time and memory usage on the computation of the Greenberg transform of quadratic polynomial in Sage.

char. t_{1} (sec) t_{2} (sec) t_{3} (sec) m_{1} (MB) m_{2} (MB) m_{3} (MB)
7  0.89  0.31  0.29  4.82  5.32  4.32
11  117.84  7.96  1.22  50.32  70.82  27.32
13  833.49 40.47  3.64  153.32  217.82  78.32
17 15559.63 668.95 49.43  922.63 1354.32 458.82
19  −−  2092.06 142.43  −−  2907.32 976.32
23  −−  −− 633.81  −−  −−  3570.12

Table 8.7. Time and memory usage on the computation of the Greenberg transform of cubic polynomial in MAGMA.

char. t_{1} (sec) t_{2} (sec) t_{3} (sec) m_{1} (MB) m_{2} (MB) m_{3} (MB)
5  0.420  0.410  0.370  11.53  13.6  10.62
7  5.490  4.150  1.810  94.12  90.50  44.44
11 2517.389 987.440 240.849 8380.22 7209.50 2110.59
13  −−  −− 2579.769  −−  −−  10516.19

Table 8.8. Time and memory usage on the computation of the Greenberg transform of cubic polynomial in Sage.

char. t_{1} (sec) t_{2} (sec) t_{3} (sec) m_{1} (MB) m_{2} (MB) m_{3} (MB)
5  0.50  0.32  0.29  5.82  6.82  4.82
7  27.48  6.69  1.30  65.82  72.82  33.82
11 10265.87 2211.73 196.01 3566.32 4999.32 1721.82
13  −−  −− 1368.54  −−  −−  8416.57

over W(𝔽_{p}(a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}, c_{0}, c_{1}, c_{2})). Tables 8.7 and 8.8 show the times and memory usage obtained when using the same three methods described above with MAGMA and Sage, respectively.

It is also worth observing that t_{1} > t_{2} > t_{3} in MAGMA and Sage in all cases, with some significant improvement. But while in MAGMA we always have m_{1} > m_{2} > m_{3}, with Sage we have that m_{2} > m_{1} > m_{3}.

Note that the third coordinate of the Greenberg transform is a polynomial in twelve variables with 153065983 terms!

9. The Function J_{2}

Finally, we return to the question about the nature of J_{2}. We shall use the same ideas that gave us Theorem 1.3 to find a simplified formula for J_{2} which also allows us to compute it in an efficient way. More precisely:

Theorem 9.1. Let Φ_{p}(X, Y) ∈ ℤ[X, Y] be the modular polynomial and suppose that over W_{3}(𝔽_{p}) we have

Φ_{p} = ∑_{i,j} a_{i,j}X^{i}Y^{j},  (Φ_{p})_{X} = ∑_{i,j} b_{i,j}X^{i}Y^{j},  and  (Φ_{p})_{Y} = ∑_{i,j} c_{i,j}X^{i}Y^{j},

respectively, with a_{i,j} = (a_{i,j,0}, a_{i,j,1}, …), b_{i,j} = (b_{i,j,0}, b_{i,j,1}, …), c_{i,j} = (c_{i,j,0}, c_{i,j,1}, …). Also, let f(X_{0}, Y_{0}) denote the reduction modulo p of Φ_{p} and

g(X_{0}, Y_{0}, Y_{1}) =^{def} ψ_{1}((Y_{0}^{p} − X_{0})^{p}Y_{1} + ∑_{i,j} a_{i,j,1}X_{0}^{ip}Y_{0}^{jp}).

Then, g(X, X^{p}, J_{1}(X)^{p}) is a p-power and

J_{2}(X) = \frac{−1}{(X^{p^{2}} − X)^{p}} [(∑_{i,j} b_{i,j,1}X^{ip+jp^{2}} ) J_{1}(X) + (∑_{i,j} c_{i,j,1}X^{ip+jp^{2}} ) J_{1}(X)^{p}

−J_{1}(X)^{p+1} + ∑_{i,j} a_{i,j,2}X^{ip+jp^{2}} + g(X, X^{p}, J_{1}(X)^{p})^{1/p}] . (9.1)

(Note that when computing g, we first expand ψ_{1}((Y_{0}^{p} − X_{0})^{p}Y_{1} + ∑ a_{i,j,1}X_{0}^{ip}Y_{0}^{jp}), and then evaluate it, instead of first evaluating (Y_{0}^{p} − X_{0})^{p}Y_{1} + ∑ a_{i,j,1}X_{0}^{ip}Y_{0}^{jp} and then computing ψ_{1}.)

Proof. By Theorem 3 of [LST64], we have that

Φ_{p}((J_{0}, J_{1}, …), (J_{0}^{p}, J_{1}^{p}, …)) = 0.  (9.2)

Also, Kronecker’s congruence relation tells us that f = (X_{0} − Y_{0}^{p})(X_{0}^{p} − Y_{0}).

As observed in [Fin10], this gives us that ψ_{1}(f) when evaluated at (j_{0}, j_{0}^{p}) yields zero. In a similar way, we also have that ψ_{2}(f) is zero when evaluated at (j_{0}, j_{0}^{p}). Indeed, we have that the Teichmüller lift of f is f =^{def} (X −Y^{p})(X^{p} −Y). Note that f^{(p)} = (X^{p} −Y^{p^{2}})(X^{p^{2}} −Y^{p}), and let (X^{p^{2}} − Y^{p}) = (X^{p} − Y) · g. Then, μ(f) is the reduction modulo p of

\frac{(X^{p} − Y^{p^{2}})^{p}(X^{p^{2}} − Y^{p})^{p} − (X − Y^{p})^{p^{2}}(X^{p} − Y)^{p^{2}}}{p^{2}} =

(X^{p} − Y)\frac{(X^{p} − Y^{p^{2}})^{p}(X^{p} − Y)^{p−1}g^{p} − (X − Y^{p})^{p^{2}}(X^{p} − Y)^{p^{2}−1}}{p^{2}} ,

and hence μ(f)(j_{0}, j_{0}^{p}) = 0. In a similar manner it is easy to show that λ(f)(j_{0}, j_{0}^{p}) = 0, and hence ψ_{2}(f)(j_{0}, j_{0}^{p}) = 0.

This already reasonably simplifies to computations of J_{2}, as the last two terms of Eq. (6.1) in the case of f = Φ_{p}, which are the most demanding in terms of computer power, are irrelevant to the computation of J_{2}, and hence can be dropped.

Moreover, note that f_{X_{0}} = (X_{0}^{p} − Y_{0}) and f_{Y_{0}} = (Y_{0}^{p} − X_{0}), and so the term

ψ_{1}(f_{X_{0}}^{p}X_{1} + f_{Y_{0}}^{p}Y_{1} + ∑_{i,j} a_{i,j,1}X_{0}^{ip}Y_{0}^{jp})

in Eq. (6.1) gives us

ψ_{1}((X_{0}^{p} − Y_{0})^{p}X_{1} + (Y_{0}^{p} − X_{0})^{p}Y_{1} + ∑_{i,j} a_{i,j,1}X_{0}^{ip}Y_{0}^{jp}).

Letting f_{1} =^{def} (X_{0}^{p} −Y_{0})^{p}X_{1} and f_{2} =^{def} (Y_{0}^{p} −X_{0})^{p}Y_{1} +∑_{i,j} a_{i,j,1}X_{0}^{ip}Y_{0}^{jp}, Eq. (4.1) gives that

ψ_{1}(f_{1} + f_{2})(j_{0}, j_{0}^{p}) = ψ_{1}(f_{2})(j_{0}, j_{0}^{p}), as f_{1} and f_{2} are disjoint and ψ_{1}(f_{1})(j_{0}, j_{0}^{p}) = 0 (which can be seen with a computation in characteristic zero similar to the one above), which also somewhat simplifies the computation of J_{2}. So, applying Theorem 6.1 with f = Φ_{p}, we have:

J_{2}(X)^{p} = \frac{−1}{(X^{p^{2}} − X)^{p^{2}}} [(∑_{i,j} b_{i,j,1}X^{ip+jp^{2}} )^{p} J_{1}(X)^{p} + (∑_{i,j} c_{i,j,1}X^{ip+jp^{2}} )^{p} J_{1}(X)^{p^{2}}

−J_{1}(X)^{p+p^{2}} + ∑_{i,j} a_{i,j,2}X^{ip^{2}+jp^{3}} + g(X, X^{p}, J_{1}(X)^{p})] , (9.3)

with g(X_{0}, Y_{0}, Y_{1}) as in the statement.

Observe that since J_{2}(X) ∈ 𝔽_{p}(X), we must have that g(X, X^{p}, J_{1}^{p}) is a p-th power in 𝔽_{p}(X), and the theorem follows. □

Remark 9.2. It should be observed that when using Theorem 9.1 to compute J_{2}, the only demanding piece is the computation of g(X, X^{p}, J_{1}(X)^{p}) (assuming we have Φ_{p}).

To make the computation more efficient, it is better to avoid first computing g(X_{0}, Y_{0}, Y_{1}) and then evaluating the result at (X, X^{p}, J_{1}^{p}), and instead evaluate at (X, X^{p}, J_{1}^{p}) as we perform the necessary recursion. More precisely, define ψ̃_{1}(f(X_{0}, Y_{0}, Y_{1})) =^{def} 0 if f is a monomial, and if f = f_{1} + f_{2}, where f_{1} and f_{2} are disjoint, then define

ψ̃_{1}(f) = ψ̃_{1}(f_{1}) + ψ̃_{1}(f_{2}) − ∑_{i=1}^{p} bin_{p}(i)f_{1}(X, X^{p}, J_{1}^{p})^{i}f_{2}(X, X^{p}, J_{1}^{p})^{p−i}.

This gives us

g(X, X^{p}, J_{1}^{p}) = ψ̃_{1}((Y_{0}^{p} − X_{0})^{p}Y_{1} + ∑_{i,j} a_{i,j,1}X_{0}^{ip}Y_{0}^{jp}),

and since this computation essentially uses rational functions on one variable, it is much more efficient than computing g(X_{0}, Y_{0}, Y_{1}) and then evaluate it at (X, X^{p}, J_{1}^{p}).

With this method we were able to compute J_{2}(X) for p ≤ 37. The results can be found

at http://www.math.utk.edu/~finotti/can_lifts/. The formulas allowed us to obtain

the following conjecture:

Conjecture 9.3. Let p ≥ 5 and

S_{p}(X) =^{def} \frac{ss_{p}(X)}{X^{δ}(X − 1728)^{ϵ}} ,

where ss_{p}(X) is the supersingular polynomial (as in, for instance, [Fin09]),

δ =^{def} \begin{cases}0, & if p ≡ 1 (mod 4); \\ 1, & if p ≡ 3 (mod 4), \end{cases}  and  ϵ =^{def} \begin{cases}0, & if p ≡ 1 (mod 6); \\ 1, & if p ≡ 5 (mod 6). \end{cases}

(Hence, S_{p}(X) ∈ 𝔽_{p}[X], and S_{p}(0), S_{p}(1728) ≠ 0. See, for instance, [Fin09].) Then,

J_{2}(X) = \frac{F (X)}{(X − 1728)^{pδ}S_{p}(X)^{2p+1}} ,  (9.4)

where F (X) ∈ 𝔽_{p}[X] and satisfies the following conditions:

(1) (F (X), (X − 1728)^{δ}S_{p}(X)) = 1;

(2) F (X) has a zero of order (2 ⌊(p − 1)/6⌋ + 1)p at X = 0.

(A lower bound of the order of zero at X = 0 of F and an upper bound for its degree is given in Theorem 9.6 below.)

Although not as precise as the conjecture, a few results on J_{2}(X) can be derived from Eq. (9.1). It should be observed that the main difficulty in proving the conjecture lies on obtaining information on the term ∑ a_{i,j,2}X^{ip+jp^{2}} from Eq. (9.1). In fact, the results on ∑ a_{i,j,1}X^{i+jp} (which is in fact equal to H̄_{p}(X)) from Kaneko and Zagier in [KZ98], obtained by analytic methods, allowed us to prove Theorems 1.2 and 1.3. (In [Fin10] a different proof, more computational and algebraic in nature, is also given.) We do have the following:

Proposition 9.4. Let p ≥ 5, v_{p} denote the valuation at p, Φ_{p}(X, Y) = ∑ a_{i,j}X^{i}Y^{j} be the modular polynomial, r =^{def} ⌊(2p + 1)/3⌋, and s =^{def} (2 ⌊(p − 1)/6⌋ + 1). Then:

(1) If p ≡ 1 (mod 6), then a_{0,0} = a_{1,0} = 0.

(2) a_{0,i}, a_{i,0} ≡ 0 (mod p^{2}) for i ∈ {0, …, r}. In particular, with the notation of Theorem 9.1, we have that a_{i,0,1} = a_{0,i,1} = 0 for i ∈ {0, …, r}, b_{i,0,1} = c_{0,i,1} = 0 for

i ∈ {0, …, r − 1}.

(3) v_{p}(a_{i,0}) ≥ 3 for i ∈ 0, …, s, i.e., a_{i,0,2} = 0 for i ∈ {0, …, s}.

Before proving the first item of the Proposition, we need to introduce a little notation. Let K be a quadratic imaginary field, z_{0} ∈ K with imaginary part positive, Γ =^{def} ℤ + z_{0}ℤ, and 𝒪 =^{def} {α ∈ K : αΓ ⊆ Γ}. We say that α ∈ 𝒪 is primitive if α ∉ n𝒪 for any n ∈ ℤ_{≥2}. We say that α, β ∈ 𝒪 are equivalent if α/β ∈ 𝒪^{×}. Then, here is Theorem 10.11 of [Lan86]:

Theorem 9.5 (Kronecker). Let z_{0}, Γ, and 𝒪 be as above, and j(z) be the modular function. Then, the multiplicity of j(z_{0}) as a root of Φ_{m}(X, X) is equal to the number of primitive 𝒪-equivalence classes of α ∈ 𝒪 such that N(α) = m.

Proof of Proposition 9.4. We start with item 1. Since p ≡ 1 (mod 6), we have that 0 is ordinary. (This is well known. See, for instance, [Fin09].) Then, since in this case the canonical lifting of the elliptic curve given by j_{0} = 0 is the curve with j = 0 = (0, 0, …), we have that 0 = Φ_{p}((0, 0, …), (0^{p}, 0^{p}, …)) = Φ_{p}(0, 0) = a_{0,0}. Hence, 0 = j(ρ), where ρ =^{def} e^{2πi/3}, is a root of Φ_{p}(X, X).

Since Φ_{p}(X, X) = a_{0,0} + 2a_{1,0}X + ⋯, where the omitted terms have degree greater than one, it suffices to show now that 0 is zero of order at least two.

We will apply Theorem 9.5 with z_{0} = ρ, K = ℚ[ρ], and m = p. In this case, we have 𝒪 = 𝒪_{K} = ℤ[ρ], where 𝒪_{K} is the ring of integers of K. Indeed, we always have that 𝒪 ⊆ 𝒪_{K}, and clearly in this case Γ = 𝒪_{K}. Also, since we are taking m = p prime, any α ∈ 𝒪 such that N(α) = p is automatically primitive.

Since, j(ρ) = 0 is a root of Φ_{p}(X, X), there exists α ∈ 𝒪 such that N(α) = p. Then, clearly N(ᾱ) = p. So, by Theorem 9.5, it suffices to show that α/ᾱ ∉ 𝒪 = ℤ[ρ].

Let α = a + bρ, with a, b ∈ ℤ. Then

\frac{α}{ᾱ} = \frac{α^{2}}{p} = \frac{(a^{2} − b^{2})}{p} + \frac{b(2a + b)}{p}ρ.

A simple elementary analysis shows then that if α/ᾱ ∈ ℤ[ρ], then a, b ≡ 0 (mod p), which is a contradiction.

We now look at item 2. This is basically a corollary of Theorems 1.2 and 1.3. (In fact, this can be deduced directly from the results of [KZ98].)

First, we have that Kronecker’s congruence relation tells us that a_{i,0}, a_{0,i} ≡ 0 (mod p) for i ∈ {0, …, p}. Now, observe that by Theorems 1.2 and 1.3 we have that H̄_{p}(X) has a zero at X = 0 of order (r + 1). Thus, since (r + 1) < p, we obtain

H_{p}(X) = \frac{1}{p}Φ_{p}(X, X^{p}) = \frac{a_{0,0}}{p} + \frac{a_{1,0}}{p} X + ⋯ + \frac{a_{r+1,0}}{p} X^{r+1} + ⋯,

where all omitted terms have degrees larger than (r + 1). Therefore, we must then have that a_{i,0} ≡ 0 (mod p^{2}) for i ∈ {0, …, r}, and by the symmetry of Φ_{p}, we also have that a_{0,i} ≡ 0 (mod p^{2}) for i ∈ {0, …, r}. The second part of this item then follows immediately.

We now prove item 3. This result was conjectured by the author and the following proof was then given by A. V. Sutherland. The idea is to work with the third roots of the jinvariants, as proposed by Atkin, which yields the much simpler polynomial, which we shall denote by Ψ_{p}(X, Y), and satisfies Ψ_{p}(j^{1/3}, (j′)^{1/3}) = 0 if the elliptic curves associated to j and j′ have an isogeny of degree p. (See, for instance, [Elk98]. The notation used in this reference for Ψ_{p} is Φ_{p}^{(3)}, but we shall avoid it to not cause any confusion with Definition 4.2.)

This polynomial also satisfies:

Φ_{p}(X^{3}, Y^{3}) = Ψ_{p}(X, Y)Ψ_{p}(X, ωY)Ψ_{p}(X, ω^{2}Y),  (9.5)

where ω =^{def} e^{2πi/3}. (This is Eq. (23) of [Elk98].) This clearly implies that

Φ_{p}(X^{3}, 0) = (Ψ_{p}(X, 0))^{3}  (9.6)

and, by Kronecker’s relation,

Ψ_{p}(X, 0) ≡ X^{p+1} (mod p)  (9.7)

(as Φ_{p}(X, 0) ≡ X^{p+1} (mod p)). Then, Eq. (9.7) implies that all coefficients of Ψ_{p}(X, 0) are divisible by p, except for the coefficient of X^{p+1}. Thus, by Eq. (9.6), we have that v_{p}(a_{i,0}) ≥ 3 for all i < (p + 1)/3. This suffices for the proof in the case of p ≡ 2 (mod 3).

If p ≡ 1 (mod 3), then we have that a_{0,0} = a_{0,1} = 0 by item 1. Then, Eq. (9.6) implies that the coefficients of degree less than or equal to one of Ψ_{p}(X, 0) must also be equal to zero. This implies that the term of degree (p + 2)/3 of Φ_{p}(X, 0) must also be divisible by p^{3}, which finishes the proof. □

With Proposition 9.4, we can now prove the main theorem of this section:

Theorem 9.6. Let p ≥ 5 and

J_{2}(X) = F (X)/G(X), with F, G ∈ 𝔽_{p}[X] and (F, G) = 1,

S_{p}(X) as in Conjecture 9.3, and suppose that the modular polynomial is given by Φ_{p}(X, Y) = ∑ a_{i,j}X^{i}Y^{j}. We have:

(1)

deg F − deg G = \begin{cases}p^{2} − 2, & if p = 31, \\ p^{2} − 1, & if p ≠ 31. \end{cases}

(2) F (and hence J_{2}) has a zero at 0 of order greater than or equal to sp, where s =^{def} (2 ⌊(p − 1)/6⌋+1). In particular, if 0 ∉ 𝕜^{ord}, then it yields a pseudo-canonical lifting modulo p^{3} with j-invariant (0, 0, 0).

(3) G(X) = S_{p}(X)^{2p+1}G_{1}(X), where G_{1}(X) | (X − 1728)^{δp} (with δ as in Conjecture 9.3). (Hence G is known if δ = 0, i.e., if p ≡ 1 (mod 4)).

(4)

deg F ≤ \begin{cases}p^{2} − 2 + (2p + 1) deg S_{p}(X) + pδ, & if p = 31, \\ p^{2} − 1 + (2p + 1) deg S_{p}(X) + pδ, & if p ≠ 31. \end{cases}

(Note that deg S_{p}(X) = ⌊(p − 1)/4⌋ − ⌈(p − 1)/6⌉. See, for instance, [Fin09].)

Proof. All items follow from the proper analysis Eq. (9.1), which we reproduce here for quicker reference:

J_{2}(X) = \frac{−1}{(X^{p^{2}} − X)^{p}} [(∑_{i,j} b_{i,j,1}X^{ip+jp^{2}} ) J_{1}(X) + (∑_{i,j} c_{i,j,1}X^{ip+jp^{2}} ) J_{1}(X)^{p}

−J_{1}(X)^{p+1} + ∑_{i,j} a_{i,j,2}X^{ip+jp^{2}} + g(X, X^{p}, J_{1}(X)^{p})^{1/p}] .

To prove item 1, it suffices to show that the order of the pole of J_{2} at infinity is either p^{2} −1 or p^{2} −2, which shall be done my checking the order of poles of the terms of Eq. (9.1).

We know from Theorem 1.3 that J_{1}(X) = H̄_{p}(X)/(X^{p^{2}} − X). Assume that p ≠ 31, i.e., that p doesn’t divide 744. As observed in [dS94], we then have that deg H̄_{p} = p^{2} + p − 1, and hence J_{1} has a pole of order p − 1 at infinity in this case.

Also, one can easily deduced from the degrees that appear in Φ_{p} that

deg(Φ_{p})_{X}(X, X^{p}) ≤ p^{2} + p − 1  and  deg(Φ_{p})_{Y} (X, X^{p}) ≤ p^{2},

and hence the polynomials

∑_{i,j} b_{i,j,1}X^{ip+jp^{2}}  and  ∑_{i,j} c_{i,j,1}X^{ip+jp^{2}}

from Eq. (9.1) have degrees less than or equal to p^{3} + p^{2} − p and p^{3} respectively. In the same way we see that

deg (∑_{i,j} a_{i,j,2}X^{ip^{2}+jp^{3}} ) ≤ p^{4} + p^{3}.

On the other hand, since

Φ_{p}(X, Y) = X^{p+1} + Y^{p+1} − X^{p}Y^{p} + ⋯  (9.8)

(for instance, use Theorem 5.3 of [Lan86] together with Kronecker’s congruence relation) we have that a_{p,p,2} = a_{0,p+1,2} = 0, and hence deg(∑ a_{i,j,2}X^{ip^{2}+jp^{3}}) ≤ p^{4} + p^{3} − p^{2}.

Moreover, Eq. (9.8) gives us that the coefficient of X^{p−1}Y^{p} in (Φ_{p})_{X} is −p ≡ (0, −1) (mod p^{2}), and thus we have that deg(∑ b_{i,j,1}X^{ip+jp^{2}}) = p^{3} + p^{2} − p.

Finally, observe that the order of the pole of g(X, X^{p}, J_{1}^{p}) is strictly less than the order of the pole of

[(X^{p^{2}} − X)^{p}J_{1}^{p} + ∑_{i,j} a_{i,j,1}X^{ip+jp^{2}}]^{p} = [(X^{p^{2}} − X)^{p}J_{1}^{p} + (H̄_{p}(X))^{p}]^{p}.

With these observations on the degrees (and order of poles) of the terms of Eq. (9.1), one can see that if p ≠ 31, then the order of the pole of J_{2} is indeed p^{2} − 1.

The case p = 31 follows from the same analysis observing only that the order of the pole of J_{1} in this case is p − 2.

For item 2, we look at the order of the zeros of the terms in Eq. (9.1) at X = 0.

We have, by item 2 of Proposition 9.4, that the term ∑ c_{i,j,1}X^{ip+jp^{2}} in Eq. (9.1) has zero of order at least p, ∑ b_{i,j,1}X^{ip+jp^{2}} has a zero of order at least rp, and ∑ a_{i,j,2}X^{ip+jp^{2}} has a zero of order at least (s + 1)p.

We now look at the term g(X, X^{p}, J_{1}^{p}). Using the recursion of ψ̃_{1} (as in Remark 9.2), we have

g(X, X^{p}, J_{1}^{p}) = ψ̃_{1}((Y_{0}^{p} − X_{0})^{p}Y_{1} + ∑_{i,j} a_{i,j,1}X_{0}^{ip}Y_{0}^{jp})
= J_{1}^{p^{2}} ψ̃_{1}(Y_{0}^{p^{2}} − X_{0}^{p}) + ψ̃_{1} (∑ a_{i,j,1}X_{0}^{ip}Y_{0}^{jp})

− ∑_{t=1}^{p−1} bin_{p}(t)(J_{1}^{p}(X^{p^{3}} − X^{p}))^{t}H̄_{p}(X^{p})^{p−t}.

Clearly, by Theorems 1.2 and 1.3, the first and last summand have zeros of order at least rp^{2} and (r + 1)p^{2} respectively. For the second summand, since a_{0,0,1} = ⋯ = a_{r,0,1} = 0 (by item 2 of Proposition 9.4), we obtain

ψ̃_{1} (∑ a_{i,j,1}X_{0}^{ip}Y_{0}^{jp}) = X^{p^{3}} ψ̃_{1} (∑_{j≥1} a_{i,j,1}X_{0}^{ip}Y_{0}^{(j−1)p})+X^{(r+1)p^{2}} ψ̃_{1} ( ∑_{i≥r+1} a_{i,0,1}X_{0}^{(i−r−1)p})

− X^{(r+1)p^{2}} ∑_{t=1}^{p−1} bin_{p}(t)X^{pt(p−r−1)} (∑_{j≥1} a_{i,j,1}X^{ip+(j−1)p^{2}} )^{t} ( ∑_{i≥r+1} a_{i,0,1}X^{(i−r−1)p})^{p−t} .

Thus, this term has a zero of order at least (r + 1)p^{2}, and we have that g(X, X^{p}, J_{1}^{p}) has a zero of order greater than rp^{2}.

Hence, since ∑ a_{i,j,2}X^{ip+jp^{2}} has a zero of order at least (s + 1)p, and s < (r − 1), by Eq. (9.1) we have that J_{2} has a zero of order at least sp, which finishes the proof of item 2.

We now prove item 3. By the nature of J_{2}, we know that J_{2} is regular at all ordinary values of j_{0}. Hence, the zeros of G, which correspond to poles of J_{2}, have to be among the supersingular values.

Now, by Theorems 1.2 and 1.3, we can write J_{1}(X) = F_{1}(X)/S_{p}(X), with F_{1} ∈ 𝔽_{p}[X] and (F_{1}, S_{p}) = 1. Using then Eq. (9.1), we obtain that G(X) | (X^{p^{2}} − X)^{p} · S_{p}(X)^{p+1}. But since G has only supersingular values as its zeros, we obtain that G | ss_{p}^{p} · S_{p}^{p+1} = X^{ϵp}(X −1728)^{δp} ·S_{p}^{2p+1}. (Remember that ss_{p} | (X^{p^{2}} −X). See , for instance Theorem V.3.1 of [Sil85].)

To show that S_{p}^{2p+1} | G, it suffices to show that if S_{p}(α) = 0, then α is a pole of order 2p + 1 of J_{2}. But this follows again from Eq. (9.1), as the term J_{1}^{p+1} has a pole of order p + 1 at such α, while all other terms inside the brackets have poles of smaller order.

Finally, since by item 2 we have that X ∤ G, the result follows.

Item 4 now follows immediately from items 1 and 3. □

Note that the proof of item 2 allows us to reformulate the second item of Conjecture 9.3 in the following way:

Conjecture 9.7. With the notation of Proposition 9.4, we have that v_{p}(a_{s+1,0}) = 2.

The pattern from this conjecture was observed by the author using the formulas for the modular polynomials Φ_{p}(X, Y) for p ≤ 353 computed by M. Rubinstein, which are available at

    http://www.math.uwaterloo.ca/~mrubinst/modularpolynomials/phi_l.html

Later, A. V. Sutherland, using methods from [BLS10], was able to verify it for p < 2500. (He also observed that his methods would actually allow him go much further.)

In conclusion, regarding pseudo-canonical liftings, Theorem 9.6 above gives us:

(1) J_{2}(X) always has a zero of order at least (2⌊(p − 1)/6⌋ + 1) at X = 0 (even if 0 ∉ 𝕜^{ord}) and (0, J_{1}(0), J_{2}(0)) ≡ 0 (mod p^{3}), i.e., 0 always yields pseudo-canonical liftings modulo p^{3}.

(2) If j_{0} ∉ 𝕜^{ord} ∪ {0, 1728}, then J_{2}(X) has a pole at X = j_{0} of order 2p + 1. Also, Conjecture 9.3 states that if 1728 ∉ 𝕜^{ord}, then J_{2}(X) has a pole of order p at X = 1728, and hence there would be no pseudo-canonical lifting modulo p^{3} in this case.

10. Pseudo-Canonical Liftings Modulo p^{4}

As seen in the previous section, unlike what happens to J_{1}, we have that J_{2} has poles at X = 1728 whenever this value is supersingular, at least for p ≤ 37 (or in general if Conjecture 9.3 is true). In the language of [Fin10], this says that a pseudo-canonical can possibly exist only for j_{0} = 0. But the failure of j_{0} = 1728 to yield these pseudo-canonical liftings strengthens any suspicion that j_{0} = 0 (when supersingular) will also eventually fail to yield pseudo-canonical liftings, i.e., that J_{n} will have a pole at j_{0} = 0 for some n large enough.

Although computations modulo p^{4} are mostly beyond our reach at this point (except for Eq. (5.5)), Conjecture 9.7 seems to indicate j_{0} = 0 will already yield poles for J_{3}. In fact, we have the following conjecture:

Conjecture 10.1. If 0 ∉ 𝕜^{ord}, then J_{3}(X) has a pole of order p^{2} at X = 0.

Although we do not have the equivalent formulas as the ones given by Theorems 6.1 and 9.6, it seems it would be likely that we would have an equation analogous to Eq. (9.3), i.e., J_{3}^{p} will be a quotient of a term involving J_{1}, J_{2}, ∑ b_{i,j,2}X^{ip^{2}+jp^{3}}, ∑ c_{i,j,2}X^{ip^{2}+jp^{3}}, etc., and the crucial term ∑_{i,j} a_{i,j,3}X^{ip^{3}+jp^{4}}, divided by (X^{p^{2}} − X)^{p^{3}}. More precisely, we expect to have something like:

J_{3}(X)^{p} = [(∑_{i,j} b_{i,j,2}X^{ip^{2}+jp^{3}} )^{p} J_{1}(X)^{p^{2}} + (∑_{i,j} c_{i,j,2}X^{ip^{2}+jp^{3}} )^{p^{2}} J_{1}(X)^{p^{3}}

+ (∑_{i,j} b_{i,j,1}X^{ip+jp^{2}} )^{p^{2}} J_{2}(X)^{p} + (∑_{i,j} c_{i,j,1}X^{ip+jp^{2}} )^{p^{2}} J_{2}(X)^{p^{2}}

+ ∑_{i,j} a_{i,j,3}X^{ip^{3}+jp^{4}} + ⋯] \frac{−1}{(X^{p^{2}} − X)^{p^{3}}} , (10.1)

where the omitted terms can get quite complicated. But, if Conjecture 9.7 holds, then all explicit terms inside the brackets above, expect for ∑_{i,j} a_{i,j,3}X^{ip^{3}+jp^{4}}, have zeros of order high enough at X = 0, while the latter does not have a zero. We also believe that the omitted terms will have zeros of order greater than p^{3}, and hence we would have a pole if, and only if, a_{0,0,3} ≠ 0, and in this case, which is predicted by Conjecture 9.7, we would have a pole of order p^{2}.

This assumption that the omitted terms above would have zeros of order greater than p^{3} is indeed quite a leap, but it is reinforced by the fact that when we know j_{0} = 0 is ordinary (i.e., p ≡ 1 (mod 6)), and hence J_{i} is regular at X = 0 for all i, we have, by item 1 of Proposition 9.4, that a_{0,0} and a_{1,0} both to be zero. This is relevant as it tells us that ∑ a_{i,j,k}X^{ip^{k}+jp^{k+1}}, ∑ b_{i,j,k}X^{ip^{k}+jp^{k+1}}, ∑ c_{i,j,k}X^{ip^{k}+jp^{k+1}} will always yield zeros at X = 0, and hence this seems to be a necessary condition to not have a pole.

We could confirm that this is indeed the case when p = 5, the only case we were able to compute J_{3} directly from the modular polynomial. The formula is also available at

                http://www.math.utk.edu/~finotti/can_lifts/.

In any event, we have to admit that we have much less evidence for Conjecture 10.1.

Acknowledgement. The author would like to thank A. V. Sutherland for his invaluable contribution, W. M. Miyata for the help with a Python script to read Rubinstein’s modular polynomials which were stored as compressed binary files, and the Centre de Recherches Mathématique for its hospitality during the final stages of the writing.

References

[BLS10] R. Broker, K. Lauter, and A. V. Sutherland. Modular polynomials via isogeny volcanoes. Available

        at http://arxiv.org/abs/1001.0402v1, 2010.

[Deu41] M. Deuring. Die typen der multiplikatorenringe elliptischer funktionenköper. Abh. Math. Sem. Univ. Hamburg, 14:197–272, 1941.

[dS94] E. de Shalit. Kronecker’s polynomial, supersingular elliptic curves, and p-adic periods of modular curves. In p-adic monodromy and the Birch and Swinnerton-Dyer conjecture (Boston, MA, 1991), volume 165 of Contemp. Math., pages 135–148. Amer. Math. Soc., Providence, RI, 1994.

[DW93] K. Davis and W. Webb. A binomial coefficient congruence modulo prime powers. J. Number Theory, 43(1):20–23, 1993.

[Elk98] N. D. Elkies. Elliptic and modular curves over finite fields and related computational issues. In Computational perspectives on number theory (Chicago, IL, 1995), volume 7 of AMS/IP Stud. Adv. Math., pages 21–76. Amer. Math. Soc., Providence, RI, 1998.

[Fin02] L. R. A. Finotti. Degrees of the elliptic Teichmüller lift. J. Number Theory, 95(2):123–141, 2002.

[Fin04] L. R. A. Finotti. Minimal degree liftings of hyperelliptic curves. J. Math. Sci. Univ. Tokyo, 11(1):1– 47, 2004.

[Fin06] L. R. A. Finotti. Minimal degree liftings in characteristic 2. J. Pure Appl. Algebra, 207(3):631–673, 2006.

[Fin09] L. R. A. Finotti. A formula for the supersingular polynomial. Acta Arith., 139(3):265–273, 2009.

[Fin10] L. R. A. Finotti. Lifting the j-invariant: Questions of mazur and tate. J. Number Theory, 130(3):620 – 638, 2010.

[Gre61] M. J. Greenberg. Schemata over local rings. Ann. of Math. (2), 73:624–648, 1961.

[Jac84] N. Jacobson. Basic Algebra, volume 2. W. H. Freeman and Company, second edition, 1984.

[KZ98] M. Kaneko and D. Zagier. Supersingular j-invariants, hypergeometric series, and Atkin’s orthogonal polynomials. In Computational perspectives on number theory (Chicago, IL, 1995), volume 7 of AMS/IP Stud. Adv. Math., pages 97–126. Amer. Math. Soc., Providence, RI, 1998.

[Lan52] S. Lang. On quasi algebraic closure. Ann. of Math. (2), 55:373–390, 1952.

[Lan86] S. Lang. Elliptic Functions, volume 112 of Garduate Texts in Mathematics. Springer-Verlag, second edition, 1986.

[LST64] J. Lubin, J-P. Serre, and J. Tate. Elliptic curves and formal groups. Proc. of Woods Hole summer institute in algebraic geometry, 1964. Unpublished. Available at

http://www.ma.utexas.edu/users/voloch/lst.html.

[Ser79] J-P. Serre. Local Fields, volume 67 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1979.

[Sil85] J. H. Silverman. The Arithmetic of Elliptic Curves, volume 106 of Graduate Texts in Mathematics. Springer-Verlag, 1985.

[VW00] J. F. Voloch and J. L. Walker. Euclidean weights of codes from elliptic curves over rings. Trans. Amer. Math. Soc., 352(11):5063–5076, 2000.

Department of Mathematics, University of Tennessee, Knoxville, TN 37996

E-mail address: finotti@math.utk.edu
URL: http://www.math.utk.edu/~finotti/