COMPUTATIONS WITH WITT VECTORS AND THE GREENBERG TRANSFORM

LUÍS R. A. FINOTTI

Abstract. In this paper we give formulas for the coordinates of the Greenberg transform of a polynomial over rings of Witt vectors. Besides being of independent theoretical interest, these formulas can be used to obtain improvement on computations with Witt vectors of arbitrary length in cases where these cannot be reduced to computation on well known local rings.

Preliminary Version Last revised: April 20, 2011.

1. Introduction

Computations with Witt vectors can be quite demanding, as the polynomials that define the sum and product of Witt vectors are themselves often enormous. (We review some basic facts about Witt vectors in Section 2.) In some cases one can perform computations efficiently by identifying the ring of Witt vectors with a well known ring. This is the case, for example, for Witt vectors over finite fields, in which case the ring of Witt vectors is canonically isomorphic to an unramified extension of p-adic integers ℤ_{p}.

Unfortunately, in most other cases we lack this canonical isomorphism and need to resort to the defining polynomial equations to perform operations. One such case is when one is interested in computing the Greenberg transform of a polynomial. (See Section 3.) For instance, [Fin02] gives an algorithm that uses the Greenberg transform to compute canonical liftings (and the elliptic Teichmüller lift) of elliptic curves. (Notably, it does not use the modular polynomial.) Also, in [Fin10b] and [Fin10a] the Greenberg transform is used to obtain information about the coordinates of the j-invariant of canonical liftings as functions on ordinary j-invariants. (Some details on this can be found in Section 9.)

In fact, in [Fin10a] we give a precise formula for the first three coordinates of the Greenberg transform of a polynomial, making computations with Witt vectors of length at most 3 much more efficient. In particular, it makes it unnecessary to compute the potentially immense polynomials that define sums and products of Witt vectors in order to evaluate a polynomial at a Witt vector.

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

Key words and phrases. Witt vectors, Greenberg transform, computations.

The main goal of this paper is to generalize those results for Witt vectors of arbitrary length. It should be said upfront that even though this goal is attained and some great improvement over older methods are obtained, as we show in Section 9, computations can still be quite demanding for large length.

But, the author’s main motivation was the generalization of his previous results from

[Fin10b] and [Fin10a], which deal with question’s by B. Mazur and J. Tate on the coordinate function of the j-invariant of the canonical lifting of an ordinary elliptic curve. (See Section 9.) Some of these generalization were obtained in [Fin10c] by using the results of this paper.

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.

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! One way to make the computation of such polynomials more efficient is to perform most of the computations directly in characteristic p, i.e., to compute S̄_{n} and P̄_{n} without computing S_{n} and P_{n} by means of Eqs. (2.4) and (2.5). (See Section 7.)

More generally, one can even avoid computing S̄_{n} and P̄_{n} altogether by using the Greenberg transform to perform a series of computations with Witt vectors. Computing its coordinates almost entirely in characteristic p also yields considerable improvements on calculations. (See Section 6.)

Another way in which we can improve computations with Witt vectors is to avoid expanding unnecessary powers: if one wants to evaluate the polynomial (X + Y)^{100} at (a, b) with a computer, it is better to first add a + b and then take the 100-th power rather than ask the computer to expand the power, store the resulting polynomial, and then evaluate it at (a, b). This saves memory and computations. It is hard to avoid expanding unnecessary powers when dealing with Eqs. (2.4) and (2.5) though, as we need to expand powers to clear the denominators. But, by using some auxiliary functions (defined in Section 5), we are able to avoid expanding some of them.

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.6) and (2.7) below), we need to define some notation:

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 Teichmü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) 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.)

(4) 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.6)

and

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

(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 x_{0} = (x_{0}, x_{1}, …), y_{0} = (y_{0}, y_{1}, …) ∈ W(𝕜[x_{0}, y_{0}, x_{1}, y_{1}, …]), then f(x_{0}, y_{0}) = (f_{0}, f_{1}, …) ∈ W(𝕜[x_{0}, y_{0}, x_{1}, y_{1}, …]) (in fact, f_{n} ∈ 𝕜[x_{0}, …, x_{n}, y_{0}, …, y_{n}]) is 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 f_{n} of 𝒢 (f).

It is clear from the definition that there is a bijection between C(W(𝕜)) and 𝒢 (C)(𝕜), as f(a, b) = 0 if and only if f_{n}(a_{0}, …, a_{n}, b_{0}, …, b_{n}) = 0 for all n. 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, proved in Section 3 of [Fin10a].

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.

Theorem 3.2 above allows us to compute the coordinates Greenberg transform recursively, generalizing Eqs. (2.2) and (2.3). More precisely, let f_{0} = f, and recursively define

f_{n} = \frac{1}{p^{n}} [f^{σ^{n}}(W^{(n)}(x_{0}, …, x_{n}), W^{(n)}(y_{0}, …, y_{n})) − f_{0}^{p^{n}}] − ∑_{i=1}^{n−1} \frac{1}{p^{n−i}} f_{i}^{p^{n−i}}.  (3.2)

Then, f_{n} is the reduction modulo p of f_{n}.

One of our main goals here is to describe how one can compute the Greenberg transform, i.e., the f_{n}’s, more efficiently. In particular, how to do it mostly in characteristic p. In [Fin10a] this was accomplished for the first three coordinates. In Section 6 we generalize the result to all coordinates.

Note that a formula for the Greenberg transform allows us to evaluate any polynomial in two variables at a pair of Witt vectors directly, without having to perform the sums and products or even needing to compute the polynomials that give the sum and product. This makes computations considerably more efficient. See [Fin10a] for some comparison for length 3 and Section 9 for larger length.

4. Motivation

Although a formula for the Greenberg transform, as well as the improvement in concrete calculations that it yields, should be of independent interest, in this section we describe the problem that motivated the author to obtain a general formula for the Greenberg transform.

Given an ordinary elliptic curve E/𝕜 (with char(𝕜) = p > 0, as above), there is a unique elliptic curve (up to isomorphism), say E/W(𝕜), which reduces to E modulo p and 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.

It was proved in [Fin10b] that the functions J_{i} are rational functions over 𝔽_{p}. Tate’s question motivates the following definition:

Definition 4.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}.

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 by the same formulas. On the other hand, we’ve proved that pseudo-canonical liftings modulo p^{2} and p^{3} do exist for specific supersingular values. More precisely, we’ve studied J_{1} and J_{2} in detail in [Fin10b] (using many results from [KZ98]) and [Fin10a] respectively, proving the following:

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

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

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

(3) J_{2}(X) is always regular at X = 0, even if 0 is supersingular, and (0, J_{1}(0), J_{2}(0)) ≡ 0 (mod p^{3}).

(4) If j_{0} ∉ 𝕜^{ord} ∪ {0, 1728}, then J_{2} has a pole of order 2p + 1 at j_{0}.

In fact, more precise descriptions of J_{1} and J_{2} are given. All these results were proved using the formulas for the second and third coordinates of the Greenberg transform. Of course, the next natural question is to ask about what happens for J_{3}(X), i.e., can we give a precise description and find what are its poles? To use the same ideas of the proofs for J_{1} and J_{2}, one then needs the third coordinate of the Greenberg transform.

Moreover, initially to even get some examples of J_{3} for different characteristics (to obtain a conjecture, for instance) was nearly impossible due to how much memory and processing power computations with Witt vectors of length 4 over polynomial rings require. In fact, the only example we were able to compute with 24 gigabytes of memory (and using MAGMA) was for p = 5. So, this motivated the author to also try to improve computations with Witt vectors of length 4 or larger, as done for length 3 in [Fin10a] by means of the formula for the third coordinate of the Greenberg transform.

The applications of the results of this paper to these questions of Mazur and Tate are dealt with elsewhere. (See [Fin10c].) But with the formula for the third coordinate for the Greenberg transform, we were able to prove, for instance, that J_{2} has a pole at 1728 if 1728 ∉ 𝕜^{ord} and J_{3} has a pole at 0 if 0 ∉ 𝕜^{ord}, and therefore pseudo-canonical liftings do not exist modulo power greater than p^{3}, giving a final answer to Tate’s question. Also, with regard to Mazur’s question, the third coordinate of the Greenberg transform allows us to give a precise description of J_{3}.

5. Auxiliary Functions

As observed before, we are interested in computing the reductions S̄_{n} and P̄_{n} of S_{n} and P_{n} directly in characteristic p, or, more generally, we would like to compute the reductions f_{n} of f_{n} from Theorem 3.2 directly in characteristic p. In order to do that, we need a way to deal with the divisions by powers of p that appear in their recursive definitions, namely Eqs. (2.4), (2.5), and (3.2). We now introduce some auxiliary functions which will deal with this problem.

Definition 5.1. Let p be a prime. Define η_{0}(X_{1}, …, X_{r}) =^{def} X_{1} +⋯+X_{r} ∈ ℚ[X_{1}, …, X_{r}], and recursively for k ≥ 1

η_{k}(X_{1}, …, X_{r}) =^{def} \frac{X_{1}^{p^{k}} + ⋯ + X_{r}^{p^{k}}}{p^{k}} − ∑_{i=0}^{k−1} \frac{η_{i}(X_{1}, …, X_{r})^{p^{k−i}}}{p^{k−i}} .  (5.1)

Also, define η_{k}(X_{1}) = 0 for k ≥ 1.

These polynomials are in fact over ℤ, as we will see in Corollary 5.7, and can be computed and stored when performing computations with Witt vectors, and will replace the divisions by powers of p mentioned above. As before, we actually only need their reductions modulo p, and we will see how we can compute these almost entirely in characteristic p. In fact, seen as functions, rather than polynomials, we can evaluate these η_{k}’s “on the fly”, without having to first compute (and store in memory) the corresponding polynomials. (See Section 8.)

Remarks 5.2. We have the following immediate remarks about the η_{k}’s.

(1) If τ is a permutation of {1, …, r}, then η_{k}(X_{1}, …, X_{r}) = η_{k}(X_{τ(1)}, …, X_{τ(r)}). (2)

\frac{(X_{1} + ⋯ + X_{r})^{p^{k}}}{p^{k}} = \frac{X_{1}^{p^{k}} + ⋯ + X_{r}^{p^{k}}}{p^{k}} − ∑_{i=1}^{k} \frac{η_{i}(X_{1}, …, X_{r})^{p^{k−i}}}{p^{k−i}} .  (5.2)

(3) η_{k}(X_{1}, …, X_{r}, 0, …, 0) = η_{k}(X_{1}, …, X_{r}). (Together with the first item, this means we can remove any entry equal to zero when computing η_{k}.)

Less trivially:

Proposition 5.3. We have that η_{k}(X_{0}, Y_{0}) = S_{k}(X_{0}, 0, …, 0, Y_{0}, 0, … 0). In particular, η_{k}(X_{1}, X_{2}) ∈ ℤ[X_{1}, X_{2}].

Proof. We prove the statement by induction on k. For k = 0 the statement is trivial. Now, if the statement holds for η_{i}(X_{1}, X_{2}) for all i ∈ {0, …, k − 1}, then it also holds for i = k by evaluating Eq. (2.4) at (X_{0}, 0, …, 0, Y_{0}, 0, … 0). □

Although in practice we need η_{k}(X_{1}, …, X_{r}) with r ≥ 2, one can obtain these from η_{k}(X_{1}, X_{2}) by a recursion based on r. More precisely:

Proposition 5.4. For any i ≥ 1, let

ℳ_{i,1} = η_{i}(X_{1}, …, X_{n}), ℳ_{i,2} = η_{i}(X_{n+1}, …, X_{n+m}),
ℳ_{i,3} = η_{i}(X_{1} + ⋯ + X_{n}, X_{n+1} + ⋯ + X_{n+m}),

and, recursively for i > 1, define

ℳ_{i,3+j} = η_{j}(ℳ_{i−j,1}, …, ℳ_{i−j,i−j+2})

for j ∈ {1, …, i − 1}. Then,

η_{i}(X_{1}, …, X_{n+m}) = ∑_{j=1}^{i+2} ℳ_{i,j}.

Before we prove this proposition, it might be appropriate to make a few observations. Firstly, the notation is somewhat heavy, and it may make it a bit clearer if one write down the first few terms that appear. We have: let ℳ_{i} =^{def} (ℳ_{i,1}, …, ℳ_{i,i+2}), v_{1} =^{def} (X_{1}, …, X_{n}),

v_{2} =^{def} (X_{n+1}, …, X_{n+m}), s_{1} =^{def} X_{1} + ⋯ + X_{n}, and s_{2} =^{def} X_{n+1} + ⋯ + X_{n+m}. Then,

ℳ_{1} = (η_{1}(v_{1}), η_{1}(v_{2}), η_{1}(s_{1}, s_{2})),
ℳ_{2} = (η_{2}(v_{1}), η_{2}(v_{2}), η_{2}(s_{1}, s_{2}), η_{1}(ℳ_{1})),
ℳ_{3} = (η_{3}(v_{1}), η_{3}(v_{2}), η_{3}(s_{1}, s_{2}), η_{1}(ℳ_{2}), η_{2}(ℳ_{1})),
⋮

Also, we would like to observe that the proposition allows us to avoid expanding unnecessary powers (as explained in Section 1). This might be better understood with an example.

Example 5.5. Let 𝕜 be a field of characteristic p > 0 and a_{1}, a_{2}, a_{3}, a_{4} ∈ 𝕜. Suppose also that we have computed and stored the polynomials η_{i}(X_{1}, X_{2}) for i = 1, 2, which we assume for now have integer coefficients. (This is proved in Corollary 5.7 below.) For instance, we have

η_{1}(X, Y) = ∑_{i=1}^{p−1} (\frac{1}{p}\binom{p}{i}) X^{i}Y^{p−i}.

If we want to compute η_{2}(a_{1}, a_{2}, a_{3}, a_{4}), we can use Proposition 5.4, which gives us that

η_{2}(a_{1}, a_{2}, a_{3}, a_{4}) = η_{2}(a_{1}, a_{2}) + η_{2}(a_{3}, a_{4}) + η_{2}(a_{1} + a_{2}, a_{3} + a_{4})
+ η_{1}(η_{1}(a_{1}, a_{2}), η_{1}(a_{3}, a_{4}), η_{1}(a_{1} + a_{2}, a_{3} + a_{4}))
= η_{2}(a_{1}, a_{2}) + η_{2}(a_{3}, a_{4}) + η_{2}(a_{1} + a_{2}, a_{3} + a_{4})
+ η_{1}(η_{1}(a_{1}, a_{2}), η_{1}(a_{3}, a_{4}))
+ η_{1}(η_{1}(a_{1}, a_{2}) + η_{1}(a_{3}, a_{4}), η_{1}(a_{1} + a_{2}, a_{3} + a_{4})).

So, we compute η_{1}(a_{1}, a_{2}), η_{1}(a_{3}, a_{4}), η_{1}(a_{1} + a_{2}, a_{3} + a_{4}), which give results in 𝕜, thus simplifying the computations of other terms, e.g., η_{1}(η_{1}(a_{1}, a_{2}), η_{1}(a_{3}, a_{4})). If one would compute first the polynomial η_{2}(X_{1}, X_{2}, X_{3}, X_{4}), it would be necessary to perform similar computations with polynomials instead, e.g., we would need

η_{1}(η_{1}(X_{1}, X_{2}), η_{1}(X_{3}, X_{4})) = ∑_{i=1}^{p−1} (\frac{1}{p}\binom{p}{i}) η_{1}(X_{1}, X_{2})^{i}η_{1}(X_{3}, X_{4})^{p−i},

which would then expand powers of η_{1}(X_{1}, X_{2}) and η_{1}(X_{3}, X_{4}).

The example above illustrates, in a very simple particular case, how one can obtain η_{k}(a_{1}, …, a_{n}) from η_{k}(X, Y) in a very particular case. Algorithm 1 gives the general recursive procedure to compute ℳ_{i}(a_{1}, …, a_{n}), for i ∈ {1, …, k} using only η_{i}(X, Y). To obtain then η_{i}(a_{1}, …, a_{n}), one just need to add all the entries of the computed vector ℳ_{i}(a_{1}, …, a_{n}).

Before we proceed with the proof of Proposition 5.4, we need a little extra notation:

Definition 5.6. Let R be a ring of characteristic 0 and f ∈ R[X_{1}, …, X_{r}]. Then, define f^{[p^{n}]} to be the sum of the p^{n}-th powers of the terms of f. (We assume that the terms of f are collected together, e.g., (X + X + Y)^{[p]} = (2X)^{p} + Y^{p}, and not X^{p} + X^{p} + Y^{p}.)

Also, if f, g ∈ R[X_{1}, …, X_{r}], we say that f and g are disjoint if there is no monomial in R[X_{1}, …, X_{r}] having non-zero R-multiples appearing on both f and g (with terms collected).

Hence, 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}]}.

Proof of Proposition 5.4. We prove the proposition by induction on i. To simplify the nota-

tion, let v =^{def} (X_{1}, …, X_{n+m}), and as above, let v_{1} =^{def} (X_{1}, …, X_{n}), v_{2} =^{def} (X_{n+1}, …, X_{n+m}),

s_{1} =^{def} X_{1} + ⋯ + X_{n}, s_{2} =^{def} X_{n+1} + ⋯ + X_{n+m}, and ℳ_{j} =^{def} (ℳ_{j,1}, …, ℳ_{j,j+2}). For i = 1 we

Algorithm 1 Compute (ℳ_{1}(a_{1}, …, a_{n}), …, ℳ_{k}(a_{1}, …, a_{n})), using only η_{i}(X, Y)

function v-etas(v = (a_{1}, …, a_{n}), k)

if n = 1 then

return (0, …, 0) end if if n = 2 then

return (η_{1}(a_{1}, a_{2}), …, η_{k}(a_{1}, a_{2})) end if m ← ⌊n/2⌋ v_{1} ← (a_{1}, …, a_{m}) v_{2} ← (a_{m+1}, …, a_{n}) s_{1} ← a_{1} + ⋯ + a_{m} s_{2} ← a_{m+1} + ⋯ + a_{n} x_{1} ← v-etas((a_{1}, …, a_{m}), k) x_{2} ← v-etas((a_{m+1}, …, a_{n}), k) x_{3} ← v-etas((s_{1}, s_{2}), k) R ← () ▷ result for i ← 1, k do ▷ add first three entries to all ℳ_{i}

R[i] ← (x_{1}[i], x_{2}[i], x_{3}[i]) end for for i ← 2, k do ▷ add the remaining entries

T ← v-etas(R[i − 1], k − i + 1) ▷ temp. var. for t ← i, k do

append T [t − i + 1] to R[t] end for

end for return R

end function

have, since s_{1} and s_{2} are disjoint,

η_{1}(v) = \frac{(s_{1} + s_{2})^{[p]} − (s_{1} + s_{2})^{p}}{p}

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

= η_{1}(v_{1}) + η_{1}(v_{2}) + η_{1}(s_{1}, s_{2})

= ℳ_{1,1} + ℳ_{1,2} + ℳ_{1,3}.

12 LUÍS R. A. FINOTTI

Now, assume the result holds for j ∈ {1, …, (i − 1)}. We have

η_{i}(v) = \frac{(s_{1} + s_{2})^{[p^{i}]} − (s_{1} + s_{2})^{p^{i}}}{p^{i}} − ∑_{j=1}^{i−1} \frac{η_{j}(v)^{p^{i−j}}}{p^{i−j}} = \frac{s_{1}^{[p^{i}]} − s_{1}^{p^{i}}}{p^{i}} + \frac{s_{2}^{[p^{i}]} − s_{2}^{p^{i}}}{p^{i}}

+ \frac{s_{1}^{p^{i}} + s_{2}^{p^{i}} − (s_{1} + s_{2})^{p^{i}}}{p^{i}} − ∑_{j=1}^{i−1} \frac{(ℳ_{j,1} + ⋯ + ℳ_{j,j+2})^{p^{i−j}}}{p^{i−j}} . (5.3)

Now, for r = 1 or 2, by the definitions of η_{i} and ℳ_{i,r}, we have

\frac{s_{r}^{[p^{i}]} − s_{r}^{p^{i}}}{p^{i}} = ∑_{j=1}^{i} \frac{η_{j}(v_{r})^{p^{i−j}}}{p^{i−j}} = ℳ_{i,r} + ∑_{j=1}^{i−1} \frac{ℳ_{j,r}^{p^{i−j}}}{p^{i−j}}

and

\frac{s_{1}^{p^{i}} + s_{2}^{p^{i}} − (s_{1} + s_{2})^{p^{i}}}{p^{i}} = ∑_{j=1}^{i} \frac{η_{j}(s_{1}, s_{2})^{p^{i−j}}}{p^{i−j}} = ℳ_{i,3} + ∑_{j=1}^{i−1} \frac{ℳ_{j,3}^{p^{i−j}}}{p^{i−j}} .

Thus, Eq. (5.3) becomes

η_{i}(v) = ℳ_{i,1} + ℳ_{i,2} + ℳ_{i,3} + ∑_{j=1}^{i−1} \frac{ℳ_{j,1}^{p^{i−j}} + ℳ_{j,2}^{p^{i−j}} + ℳ_{j,3}^{p^{i−j}} − (ℳ_{j,1} + ⋯ + ℳ_{j,j+2})^{p^{i−j}}}{p^{i−j}} . (5.4)

Now,

\frac{ℳ_{j,1}^{p^{i−j}} + ℳ_{j,2}^{p^{i−j}} + ℳ_{j,3}^{p^{i−j}} − (ℳ_{j,1} + ⋯ + ℳ_{j,j+2})^{p^{i−j}}}{p^{i−j}} =

\frac{ℳ_{j,1}^{p^{i−j}} + ⋯ + ℳ_{j,j+2}^{p^{i−j}} − (ℳ_{j,1} + ⋯ + ℳ_{j,j+2})^{p^{i−j}}}{p^{i−j}} − \frac{ℳ_{j,4}^{p^{i−j}} + ⋯ + ℳ_{j,j+2}^{p^{i−j}}}{p^{i−j}} ,

and the first fraction of the right hand side above is, by the definitions of η_{i−j} and ℳ_{j+k,r}, equal to

∑_{k=1}^{i−j} \frac{η_{k}(ℳ_{j})^{p^{i−j−k}}}{p^{i−j−k}} = ∑_{k=1}^{i−j} \frac{ℳ_{j+k,k+3}^{p^{i−j−k}}}{p^{i−j−k}} .

Therefore, Eq. (5.4) becomes

η_{i}(v) = ℳ_{i,1} + ℳ_{i,2} + ℳ_{i,3} + ∑_{j=1}^{i−1} ∑_{k=1}^{i−j} \frac{ℳ_{j+k,k+3}^{p^{i−j−k}}}{p^{i−j−k}} − ∑_{j=2}^{i−1} ∑_{k=4}^{j+2} \frac{ℳ_{j,k}^{p^{i−j}}}{p^{i−j}} .  (5.5)

Now, simple manipulations of summations give us

∑_{j=1}^{i−1} ∑_{k=1}^{i−j} \frac{ℳ_{j+k,k+3}^{p^{i−j−k}}}{p^{i−j−k}} = ∑_{j=1}^{i−1} ∑_{l=j+1}^{i} \frac{ℳ_{l,l−j+3}^{p^{i−l}}}{p^{i−l}} = ∑_{l=2}^{i} ∑_{j=1}^{l−1} \frac{ℳ_{l,l−j+3}^{p^{i−l}}}{p^{i−l}} = ∑_{l=2}^{i} ∑_{m=4}^{l+2} \frac{ℳ_{l,m}^{p^{i−l}}}{p^{i−l}} .

This equation together with Eq. (5.5) finishes the proof. □

Corollary 5.7. We have that η_{i}(X_{1}, …, X_{r}) ∈ ℤ[X_{1}, …, X_{r}] for all r ≥ 2.

Proof. We prove the statement by induction on r. For r = 2 (and all i), the statement follows from Proposition 5.3. So, suppose that r > 2 and η_{i}(X_{1}, …, X_{j}) ∈ ℤ[X_{1}, …, X_{r}] for all j ∈ {2, …, (r − 1)} (and for all i).

The statement for r variables now follows from Proposition 5.4 by an induction on i: the case of i = 1 follows by the induction hypothesis on r since

η_{1}(X_{1}, …, X_{r}) = η_{1}(X_{1}, …, X_{r−1}) + η_{1}(X_{1} + ⋯ + X_{r−1}, X_{r}).

For the second step of the induction (on i) we use again n = 1 and m = r − 1 in Proposition 5.4, which gives η_{i}(X_{1}, …, X_{r}) as sums and compositions of η_{k}(X_{1}, …, X_{j}) where either k = i and j < r (and we use the induction hypothesis on r), or k < i (and we use the induction hypothesis on i). □

Although we will carry on with η_{k} over ℤ, as it will be convenient in the proofs that follow, what really is of interest to us are their reduction modulo p, which we shall denote by η̄_{k}, as these functions will always be evaluated in characteristic p. In Section 8 we discuss how one can compute the η̄_{k}’s almost entirely in characteristic p.

We introduce some extra notation.

Definition 5.8. If R is a ring of characteristic p and v = (a_{1}, …, a_{r}) ∈ R^{r}, we define η_{k}(v) = η_{k}(a_{1}, …, a_{r}) as the evaluation η_{k}(X_{1}, …, X_{r}) at v. (This makes sense as η_{k}(X_{1}, …, X_{r}) ∈ ℤ[X_{1}, …, X_{r}].)

Moreover, if f is a polynomial (possibly in many variables) with coefficients in R, we write vec (f) for the vector that contains the terms of f (after some choice of order for the monomials). We then may write η_{k}(f) for η_{k}(vec (f)). (It is important to observe that we are assuming that the terms are reduced, i.e., if f = 1 + X + 2X, then vec (f) = (1, 3X), not (1, X, 2X).)

With this notation, we have that ψ_{k}(f) (from [Fin10a]) is just η_{k}(f) as defined above. (The meanings of η_{k}(v) is the same here and in [Fin10a].)

6. The Formula for the Greenberg Transform

We will now give a formula for the Greenberg transform that can be computed, for the most part, directly in characteristic p.

Since the formula is quite involved, we will need to introduce a reasonable ammount of notation.

Definition 6.1. If g ∈ W(𝕜)[x, y] is given by g = ∑_{i,j} a_{i,j}x^{i}y^{j}, then we write

ξ_{k}(g) =^{def} ∑_{i,j} ξ_{k}(a_{i,j})x^{i}y^{j},

with ξ_{k} as in Definition 2.1. (Hence, g ≡ ∑_{k=0}^{r} ξ_{k}(g)p^{k} (mod p^{r+1}).) Furthermore, define

g^{(i,j)} =^{def} \frac{1}{i!j!} \frac{∂^{i+j}}{∂x^{i}∂y^{j}} g, and g_{i,j,k} =^{def} ξ_{k}(g^{(i,j)}).

Definition 6.2. We define D_{k,n}^{i,j} to be the coefficient of t^{k} in

(tx_{1}^{p^{n−1}} + t^{2}x_{2}^{p^{n−2}} + ⋯ + t^{n}x_{n})^{i}(ty_{1}^{p^{n−1}} + t^{2}y_{2}^{p^{n−2}} + ⋯ + t^{n}y_{n})^{j}.

(E.g., if n ≥ 2, then D_{4,n}^{1,2} = 2x_{1}^{p^{n−1}}y_{1}^{p^{n−1}}y_{2}^{p^{n−2}} +x_{2}^{p^{n−2}}y_{1}^{2p^{n−1}}.) Furthermore, we shall denote

D_{k,n,l}^{i,j} =^{def} ξ_{l}(D_{k,n}^{i,j}).

Note that if k < r (and r ≥ i), then D_{k,n}^{i,r−i} = 0 and if k ≠ 0, then D_{k,n}^{0,0} = 0. Also, observe that:

(px_{1}^{p^{n−1}} + p^{2}x_{2}^{p^{n−2}} + ⋯ + p^{n}x_{n})^{i}(py_{1}^{p^{n−1}} + p^{2}y_{2}^{p^{n−2}} + ⋯ + p^{n}y_{n})^{r−i}

= ∑_{k=r}^{∞} D_{k,n}^{i,r−i}p^{k} = ∑_{k=r}^{∞} ∑_{l=0}^{∞} D_{k,n,l}^{i,r−i}p^{k+l} = ∑_{k=r}^{∞} ∑_{j=k}^{∞} D_{k,n,j−k}^{i,r−i}p^{j} = ∑_{j=r}^{∞} ∑_{k=r}^{j} D_{k,n,j−k}^{i,r−i}p^{j}. (6.1)

Definition 6.3. Let f ∈ W(𝕜)[x, y]. Then, for a given n ≥ 0, let (𝒢_{n,1}, …, 𝒢_{n,N_{n}}) be the vector obtained by joining the vectors vec ((f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i}), for r ∈ {0, … n}, i ∈ {0, …, r}, j ∈ {r, … n}, and k ∈ {r, …, j}. (The ordering is not important.) Also, recursively, if n > 1, define

𝒢_{n,N_{n}+i+1} =^{def} η_{n−i}(𝒢_{i,1}, …, 𝒢_{i,N_{i}+i}),

for i ∈ {0, …, (n − 1)}. Then, define,

f_{n} =^{def} ∑_{i=1}^{N_{n}+n} 𝒢_{n,i},

and 𝒢_{n} =^{def} (𝒢_{n,1}, …, 𝒢_{n,N_{n}+n}).

Then, we have:

Theorem 6.4. With the notation above, we have that 𝒢 (f) = (f_{0}, f_{1}, …), where f_{n} is the reduction modulo p of

f_{n} = ∑_{i=1}^{N_{n}+n} 𝒢_{n,i} = ∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j}(f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i} + ∑_{i=0}^{n−1} η_{n−i}(𝒢_{i}). (6.2)

Note that although

∑_{i=1}^{N_{n}} 𝒢_{n,i} = ∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j}(f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i},

the vector (𝒢_{n,1}, …, 𝒢_{n,N_{n}}) is not, in general, just a reordering of

vec (∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j}(f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i})

as cancellations will likely occur when summing. Defining

(𝒢_{n,1}, …, 𝒢_{n,N_{n}}) = vec (∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j}(f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i})

does not work in general!

Although Eq. (6.2) is quite complicated, it simplifies greatly in some particular cases, such as if we just want up to the third coordinate. In that case, the reduction modulo p of f_{2} given here is just Eq. (6.1) in [Fin10a]. See also the examples in Section 7.

Moreover, since we are only interested in the reduction modulo p of the f_{n}, say f_{n}, we can compute these mostly in characteristic p. For instance, using the bar to denote reduction modulo p and assuming we have already computed 𝒢̄_{i} for i ∈ {1, …, (n − 1)}, we can compute 𝒢̄_{n,N_{n}+i+1} for i ∈ {0, …, (n − 1)} directly with 𝒢̄_{n,N_{n}+i+1} = η̄_{n−i}(𝒢̄_{i}).

For 𝒢̄_{n,i} with i ∈ {1, …, N_{n}} some computations not in characteristic p are necessary. We need to compute the reductions modulo p of (f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i}, for r ∈ {0, … n}, i ∈ {0, …, r}, j ∈ {r, … n}, and k ∈ {r, …, j}. Now,

(f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}}) = ξ_{n−j}((f^{(i,r−i)})^{σ^{n}})(x_{0}^{p^{n}}, y_{0}^{p^{n}}),

and if g = ∑_{i,j} b_{i,j}x^{i}y^{j} and b_{i,j} = (b_{i,j,0}, b_{i,j,1}, …), then

π(ξ_{k}(g^{σ^{n}}(x^{p^{n}}, y^{p^{n}}))) = ∑_{i,j,k} b_{i,j,k}^{p^{k+n}}x_{0}^{ip^{n}}y_{0}^{jp^{n}}.

Thus, we need to compute the coefficients of the partial derivatives f^{(i,r−i)} modulo p^{n−j+1}. So, one needs to convert integers to Witt vectors (of length p^{n−j}) and multiply then by the corresponding coefficients of (f^{(i,r−i)})^{σ^{n}}. If j = 0, then we must have that r = i = 0, and hence no partial derivative is needed. Therefore, the necessary products of Witt vectors are done with lengths less than or equal to n instead of (n + 1). More precisely, first order partial derivatives (i.e., r = 1) are needed only modulo p^{n}, second order ones (i.e,, r = 2) are needed only modulo p^{n−1}, and so on.

For the terms D_{k,n,j−k}^{i,r−i}, we also need some computations not in characteristic p. Since (j − k) ∈ {0, …, n − r}, we need to compute the products

(tx_{1}^{p^{n−1}} + t^{2}x_{2}^{p^{n−2}} + ⋯ + t^{n}x_{n})^{i}(ty_{1}^{p^{n−1}} + t^{2}y_{2}^{p^{n−2}} + ⋯ + t^{n}y_{n})^{r−i},

over ℤ/p^{n−r+1}ℤ and convert the coefficients to Witt vectors of length n − r + 1.

On the other hand, it should be observed that all these computations not in characteristic p are in fact relatively fast, and do not slow down the algorithm. (Most of the time is spent computing the η̄_{n−i}(𝒢̄_{i})’s.)

Before we proceed with the proof, we introduce some extra notation.

Definition 6.5. Let K be the field of fractions of W(𝕜). (Note that K = W(𝕜)[1/p].) If f, g ∈ K[x, y], then we write f ≡ g (mod p) if f − g ∈ (p) = pW(𝕜)[x, y].

Proof of Theorem 6.4. By Theorem 3.2, it suffices to show that f_{i}’s satisfy Eq. (3.1) for all n. We prove this by induction on n.

For n = 0 the result is clear. So, assume now that if r < n, then

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

To simplify the notation, let g =^{def} f^{σ^{n}}. To prove that the equation above holds for r = n it suffices to show that

f_{n} ≡ \frac{1}{p^{n}} g(x_{0}^{p^{n}} + ⋯ + p^{n}x_{n}, y_{0}^{p^{n}} + ⋯ + p^{n}y_{n}) − ∑_{i=0}^{n−1} \frac{f_{i}^{p^{n−i}}}{p^{n−i}} (mod p).  (6.3)

Using Eq. (5.2), we obtain

∑_{i=0}^{n−1} \frac{f_{i}^{p^{n−i}}}{p^{n−i}} = ∑_{i=0}^{n−1} [ ∑_{r=1}^{N_{i}+i} \frac{𝒢_{i,r}^{p^{n−i}}}{p^{n−i}} − ∑_{l=1}^{n−i} \frac{η_{l}(𝒢_{i})^{p^{n−i−l}}}{p^{n−i−l}} ] .  (6.4)

But

∑_{i=0}^{n−1} ∑_{l=1}^{n−i} \frac{η_{l}(𝒢_{i})^{p^{n−i−l}}}{p^{n−i−l}} = ∑_{i=0}^{n−1} ∑_{j=i+1}^{n} \frac{η_{j−i}(𝒢_{i})^{p^{n−j}}}{p^{n−j}}

= ∑_{j=1}^{n} ∑_{i=0}^{j−1} \frac{η_{j−i}(𝒢_{i})^{p^{n−j}}}{p^{n−j}} = ∑_{j=1}^{n} ∑_{i=0}^{j−1} \frac{𝒢_{j,N_{j}+i+1}^{p^{n−j}}}{p^{n−j}} = ∑_{j=1}^{n} ∑_{r=N_{j}+1}^{N_{j}+j} \frac{𝒢_{j,r}^{p^{n−j}}}{p^{n−j}} . (6.5)

COMPUTATIONS WITH WITT VECTORS AND THE GREENBERG TRANSFORM 17

Putting Eqs. (6.4) and (6.5) together, we obtain

∑_{i=0}^{n−1} \frac{f_{i}^{p^{n−i}}}{p^{n−i}} = ∑_{i=0}^{n−1} ∑_{r=1}^{N_{i}} \frac{𝒢_{i,r}^{p^{n−i}}}{p^{n−i}} + ∑_{i=1}^{n−1} ∑_{r=N_{i}+1}^{N_{i}+i} \frac{𝒢_{i,r}^{p^{n−i}}}{p^{n−i}} − ∑_{i=1}^{n} ∑_{r=N_{i}+1}^{N_{i}+i} \frac{𝒢_{i,r}^{p^{n−i}}}{p^{n−i}}
= ∑_{i=0}^{n−1} ∑_{r=1}^{N_{i}} \frac{𝒢_{i,r}^{p^{n−i}}}{p^{n−i}} − ∑_{r=N_{n}+1}^{N_{n}+n} 𝒢_{n,r}.  (6.6)

Using Taylor expansion and Eq. (6.1), and with the notation of Definition 6.5, we obtain:

\frac{1}{p^{n}} g(x_{0}^{p^{n}} + ⋯ + p^{n}x_{n}, y_{0}^{p^{n}} + ⋯ + p^{n}y_{n})

≡ \frac{1}{p^{n}} ∑_{r=0}^{n} ∑_{i=0}^{r} g^{(i,r−i)}(x_{0}^{p^{n}}, y_{0}^{p^{n}})(px_{1}^{p^{n−1}} + ⋯ p^{n}x_{n})^{i}(py_{1}^{p^{n−1}} + ⋯ + p^{n}y_{n})^{r−i}

≡ ∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j} g^{(i,r−i)}(x_{0}^{p^{n}}, y_{0}^{p^{n}})\frac{D_{k,n,j−k}^{i,r−i}}{p^{n−j}} (mod p).

Taking into account the factors of p in g^{(i,r−i)} and manipulating the summations, the above equation becomes

\frac{1}{p^{n}} g(x_{0}^{p^{n}}+ ⋯ + p^{n}x_{n}, y_{0}^{p^{n}} + ⋯ + p^{n}y_{n})

≡ ∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j} ∑_{s=0}^{n−j} g_{i,r−i,s}(x_{0}^{p^{n}}, y_{0}^{p^{n}})\frac{D_{k,n,j−k}^{i,r−i}}{p^{n−j−s}}

= ∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j} ∑_{l=j}^{n} g_{i,r−i,l−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})\frac{D_{k,n,j−k}^{i,r−i}}{p^{n−l}}

= ∑_{l=0}^{n} ∑_{r=0}^{l} ∑_{i=0}^{r} ∑_{j=r}^{l} ∑_{k=r}^{j} g_{i,r−i,l−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})\frac{D_{k,n,j−k}^{i,r−i}}{p^{n−l}} (mod p).

Now, by definition of 𝒢_{n,r}, for i ∈ {1, …, N_{i}}, we obtain

\frac{1}{p^{n}} g(x_{0}^{p^{n}} + ⋯ + p^{n}x_{n}, y_{0}^{p^{n}} + ⋯ + p^{n}y_{n}) ≡

∑_{i=1}^{N_{n}} 𝒢_{n,i} + ∑_{l=0}^{n−1} ∑_{r=0}^{l} ∑_{i=0}^{r} ∑_{j=r}^{l} ∑_{k=r}^{j} g_{i,r−i,l−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})\frac{D_{k,n,j−k}^{i,r−i}}{p^{n−l}} (mod p). (6.7)

Hence, by Eqs. (6.3), (6.6), and (6.7), it suffices to show that

∑_{r=0}^{l} ∑_{i=0}^{r} ∑_{j=r}^{l} ∑_{k=r}^{j}(f^{σ^{n}})_{i,r−i,l−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i} = ∑_{r=1}^{N_{l}} 𝒢_{l,r}^{p^{n−l}}.

Now, by the definition of the 𝒢_{l,i} (and with the notation from Definition 5.6), we have that

∑_{r=1}^{N_{l}} 𝒢_{l,r}^{p^{n−l}} = ∑_{r=0}^{l} ∑_{i=0}^{r} ∑_{j=r}^{l} ∑_{k=r}^{j}((f^{σ^{l}})_{i,r−i,l−j}(x_{0}^{p^{l}}, y_{0}^{p^{l}})D_{k,l,j−k}^{i,r−i})^{[p^{n−l}]}.

Moreover, since D_{j,l,j−k}^{i,r−i} and (f^{σ^{l}})_{i,r−i,l−j}(x_{0}^{p^{l}}, y_{0}^{p^{l}}) are disjoint and involve different variables, we have that

((f^{σ^{l}})_{i,r−i,l−j}(x_{0}^{p^{l}}, y_{0}^{p^{l}})D_{k,l,j−k}^{i,r−i})^{[p^{n−l}]} = ((f^{σ^{l}})_{i,r−i,l−j}(x_{0}^{p^{l}}, y_{0}^{p^{l}}))^{[p^{n−l}]}(D_{k,l,j−k}^{i,r−i})^{[p^{n−l}]}.

Thus, our problem reduces to proving that

(f^{σ^{n}})_{i,r−i,l−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}}) = ((f^{σ^{l}})_{i,r−i,l−j}(x_{0}^{p^{l}}, y_{0}^{p^{l}}))^{[p^{n−l}]}

and

D_{k,n,j−k}^{i,r−i} = (D_{k,l,j−k}^{i,r−i})^{[p^{n−l}]}.

For the former, first observe that the Frobenius homomorphism σ acts trivially on ℤ, and hence, (f^{σ^{s}})^{(i,r−i)} = (f^{(i,r−i)})^{σ^{s}}. Moreover, with the a_{i,j} ∈ W(𝕜) and a_{i,j,k} =^{def} ξ_{k}(a_{i,j}), we have that σ^{s}(a_{i,j}) = ∑_{k=0}^{∞} a_{i,j,k}^{p^{s}}p^{k}. So, (f^{σ^{s}})_{i,r−i,l−j} = ξ_{l−j}((f^{(i,r−i)})^{σ^{s}}) has as coefficients the p^{s}-powers of the coefficients of f_{i,r−i,l−j} = ξ_{l−j}(f^{(i,r−i)}). With these observations, the (first) desired equality follows immediately.

For the latter, first observe that if s > l (and since l ≥ k), then there is no term in either x_{s} or y_{s} from

(tx_{1}^{p^{n−1}} + t^{2}x_{2}^{p^{n−2}} + ⋯ + t^{n}x_{n})^{i}(ty_{1}^{p^{n−1}} + t^{2}y_{2}^{p^{n−2}} + ⋯ + t^{n}y_{n})^{r−i}

appearing in D_{k,n}^{i,r−i}, as such a term would have degree (in t) at least s > l ≥ k. So, D_{k,n}^{i,r−i} is the coefficient of the term of degree k (in t) of

(tx_{1}^{p^{n−1}} + t^{2}x_{2}^{p^{n−2}} + ⋯ + t^{l}x_{l}^{p^{n−l}})^{i}(ty_{1}^{p^{n−1}} + t^{2}y_{2}^{p^{n−2}} + ⋯ + t^{l}y_{l}^{p^{n−l}})^{r−i},

while D_{k,l}^{i,r−i} the coefficient of the term of degree k of

(tx_{1}^{p^{l−1}} + t^{2}x_{2}^{p^{l−2}} + ⋯ + t^{l}x_{l})^{i}(ty_{1}^{p^{l−1}} + t^{2}y_{2}^{p^{l−2}} + ⋯ + t^{l}y_{l})^{r−i}.

Now, since the coefficients of D_{k,l}^{i,r−i} are integers, the coefficients of D_{k,l,j−k}^{i,r−i} are invariant by powers of p. Therefore, it becomes clear that

D_{k,n,j−k}^{i,r−i} = (D_{k,l,j−k}^{i,r−i})^{[p^{n−l}]},

finishing the proof. □

7. Sums and Products

As seen in Section 3, the Greenberg transform generalizes the sum and products of Witt vectors. Thus, we can apply Theorem 6.4 to obtain the S̄_{i} and P̄_{i}.

It should be observed that these equations have less importance now, as they are not necessary, in general, to perform computations with Witt vectors. On the other hand, the propositions below also give a method to compute sums and products of Witt vectors directly, i.e., without computing the polynomials S_{i} and P_{i}, but using the auxiliary functions η_{i} instead. (See Example 7.2 below.)

Proposition 7.1. Define recursively for k ≥ 0 (and a given prime p):

𝒮_{k,1} =^{def} x_{k}, 𝒮_{k,2} =^{def} y_{k},

and for k > 0 and i ∈ {0, …, k − 1},

𝒮_{k,2+i} =^{def} η_{k−i}(𝒮_{i,1}, …, 𝒮_{i,i+2}).

Then:

S_{n} ≡ ∑_{i=1}^{n+2} 𝒮_{n,i} = x_{n} + y_{n} + ∑_{i=0}^{n−1} η_{n−i}(𝒮_{i,1}, …, 𝒮_{i,i+2}) (mod p).

Proof. We just apply Theorem 6.4 with f = x + y. So, f_{i,r−i,n−j}^{σ^{n}} is zero unless r is either 0 or 1, and j = n. Moreover, for r equal to 0 or 1 (and 0 ≤ i ≤ r), we have that D_{k,n,j−k}^{i,r−i} is zero unless k = j. Since j = n, we then have k = n. Hence, for n > 0,

∑_{i=1}^{N_{n}} 𝒢_{n,i} = ∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j}(f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i}
= (x_{0}^{p^{n}} + y_{0}^{p^{n}})D_{n,n,0}^{0,0} + D_{n,n,0}^{0,1} + D_{n,n,0}^{1,0}
= 0 + y_{n} + x_{n}.

Recalling now Remark 5.2, the proposition follows immediately. □

Maybe it is worth seeing an example of how one can use this proposition to perform sums of Witt vectors.

Example 7.2. Assume we have computed the polynomials η̄_{k}(X, Y) ∈ 𝔽_{p}[X, Y] for k = 1, 2. To add (1, 1, 1) and (2, 0, 1) in W_{3}(𝔽_{3}), say (c_{0}, c_{1}, c_{2}) = (1, 1, 1) + (2, 0, 1), we have 𝒮_{0,1} = 1 and 𝒮_{0,2} = 2. So,

c_{0} = 𝒮_{0,1} + 𝒮_{0,2} = 1 + 2 = 0.

Then, we compute η̄_{k}(𝒮_{0,1}, 𝒮_{0,2}) = η̄_{k}(1, 2), for k = 1, 2. In this particular case, both of these are equal to zero. Thus,

c_{1} = 𝒮_{1,1} + 𝒮_{1,2} + 𝒮_{1,3}
= 1 + 0 + η̄_{1}(1, 2) = 1 + 0 + 0 = 1.

Finally, we need η̄_{1}(𝒮_{1,1}, 𝒮_{1,2}, 𝒮_{1,3}) = η̄_{1}(1, 0, η̄_{1}(1, 2)) = η̄_{1}(1, 0, 0) = 0. Then,

c_{2} = 𝒮_{2,1} + 𝒮_{2,2} + 𝒮_{2,3} + 𝒮_{2,4}
= 1 + 1 + η̄_{1}(𝒮_{1,1}, 𝒮_{1,2}, 𝒮_{1,3}) + η̄_{2}(1, 2)
= 1 + 1 + 0 + 0 = 2.

The formula for P_{n} is similar.

Proposition 7.3. Define recursively for k ≥ 0 (and a given prime p): for i ∈ {1, …, k+1},

𝒫_{k,i} =^{def} x_{i}^{p^{k−i}}y_{k−i}^{p^{i}}

and for k > 1 and i ∈ {1, …, k − 1},

𝒫_{k,k+1+i} =^{def} η_{k−i}(𝒫_{i,1}, …, 𝒫_{i,2i}).

Then, for n > 0:

P_{n} ≡ ∑_{i=1}^{2n} 𝒫_{n,i} = ∑_{i=0}^{n} x_{i}^{p^{k−i}}y_{k−i}^{p^{i}} + ∑_{i=0}^{n−1} η_{n−i}(𝒫_{i,1}, …, 𝒫_{i,2i}) (mod p).

Proof. We just apply Theorem 6.4 with f = xy. So, f_{i,r−i,n−j}^{σ^{n}} is zero unless r is either 0, 1, or 2 (in which case we need i = 1), and j = n. Moreover, since i and r − i are either 0 or 1, we have that D_{k,n,j−k}^{i,r−i} is zero unless k = j. Since j = n, we then have k = n. Hence, for n > 0,

∑_{i=1}^{N_{n}} 𝒢_{n,i} = ∑_{r=0}^{n} ∑_{i=0}^{r} ∑_{j=r}^{n} ∑_{k=r}^{j}(f^{σ^{n}})_{i,r−i,n−j}(x_{0}^{p^{n}}, y_{0}^{p^{n}})D_{k,n,j−k}^{i,r−i}

= (x_{0}^{p^{n}}y_{0}^{p^{n}})D_{n,n,0}^{0,0} + x_{0}^{p^{n}}D_{n,n,0}^{0,1} + y_{0}^{p^{n}}D_{n,n,0}^{1,0} + D_{n,n,0}^{1,0}

= 0 + x_{0}^{p^{n}}y_{n} + x_{n}y_{0}^{p^{n}} + (∑_{i=1}^{n−1} x_{i}^{p^{n−i}}y_{n−i}^{p^{i}}) .

Recalling now Remark 5.2, the proposition follows immediately. □

8. Computing η̄_{k} in Characteristic p

In this section we show how one can compute η̄_{k}(X, Y) almost entirely in characteristic p. (We do need to convert some binomial coefficients to Witt vectors, which is not done in characteristic p.) In fact, this new method, together with Proposition 5.4, allows us to not have to store these polynomials at all and compute η̄_{k}(a_{1}, …, a_{r}), for a_{i}’s in a ring of characteristic p, on the fly.

We will need the following elementary lemmas:

Lemma 8.1. Let v_{p} denote the valuation at p. Then, if 1 < a < p^{k}, we have that

v_{p}\binom{p^{k}}{a} = k − v_{p}(a).

Proof. We prove it by induction on k. The case of k = 1 is trivial.

Now, suppose that for all q ∈ \{1, …, p^{k−1} − 1\}, we have v_{p}\binom{p^{k−1}}{q} = (k − 1) − v_{p}(q). Since

\binom{p^{k}}{a} = (∏_{i=1}^{a}(p^{k} − a + i)) (∏_{i=1}^{a} i)^{−1} ,

we have

v_{p}\binom{p^{k}}{a} = ∑_{i=1}^{a} v_{p}(p^{k} − a + i) − ∑_{i=1}^{a} v_{p}(i).  (8.1)

Let a = qp + r, with r ∈ {0, …, (p − 1)} and define ϵ as 1 if r = 0 and 0 otherwise. Thus, v_{p}(a) = ϵ(v_{p}(q) + 1). Then, Eq. (8.1) and the induction hypothesis give:

v_{p}\binom{p^{k}}{a} = ∑_{j=ϵ}^{q} v_{p}(p^{k} − a + (jp + r)) − ∑_{j=1}^{q} v_{p}(jp)

= (1 − ϵ)v_{p}(p^{k} − qp) + ∑_{j=1}^{q} v_{p}(p^{k−1} − q + j) − ∑_{j=1}^{q} v_{p}(j)

= (1 − ϵ)(v_{p}(q) + 1) + v_{p}\binom{p^{k−1}}{q}

= (1 − ϵ)(v_{p}(q) + 1) + (k − 1) − v_{p}(q)

= k − ϵ(v_{p}(q) + 1) = k − v_{p}(a).

□

Lemma 8.2. We have that if 0 < t ≤ k, then (X + 1)^{p^{k}} ≡ (X^{p^{k−t}} + 1)^{p^{t}} (mod p^{t+1}). In particular, if 0 < j ≤ t and i ∈ {1, …, p^{j} − 1} with p ∤ i, then

\frac{1}{p^{j}} \binom{p^{k}}{ip^{k−j}} ≡ \frac{1}{p^{j}} \binom{p^{t}}{ip^{t−j}} (mod p^{t−j+1}).

Proof. Clearly (X + 1)^{p^{k−t}} = X^{p^{k−t}} + 1 + pf(X) for some f ∈ ℤ[X]. The result follows from raising both sides to the p^{t}-th power.

For the second part, use the first part and Lemma 8.1 to compare the coefficients of X^{ip^{k−j}} from (X + 1)^{p^{k}} and (X^{p^{k−t}} + 1)^{p^{t}}. □

We now introduce yet some more notation. Definition 8.3. Let 0 < j ≤ k and i ∈ {1, …, p^{j} − 1} with p ∤ i, and define Bin_{i,j,k} =^{def} −\frac{1}{p^{j}} \binom{p^{k}}{ip^{k−j}}, bin_{i,j,k} =^{def} ξ_{k−j}(Bin_{i,j,k}), and bin_{i,j,k} =^{def} π(bin_{i,j,k}). (Remember π denotes the reduction modulo p.) Lemma 8.4. Let 0 < r < k and i ∈ {1, …, p^{r} − 1} with p ∤ i. We have that

Bin_{i,r,k} ≡ ∑_{l=0}^{k−r} bin_{i,r,r+l} p^{l} (mod p^{k−r+1}).

Proof. By Lemma 8.2, we have that Bin_{i,r,k} ≡ Bin_{i,r,r+l} (mod p^{l+1}) for 0 ≤ l < k − r. Then,

Bin_{i,r,k} ≡ ∑_{t=0}^{l} ξ_{t}(Bin_{i,r,k})p^{t} ≡ ∑_{t=0}^{l} ξ_{t}(Bin_{i,r,r+l})p^{t}

= ∑_{t=0}^{l−1} ξ_{t}(Bin_{i,r,r+l})p^{t} + bin_{i,r,r+l} p^{l} (mod p^{l+1}).

Thus, by the uniqueness of the representation, we have ξ_{l}(Bin_{i,r,k}) = bin_{i,r,r+l} for 0 ≤ l < k − r. Since also ξ_{k−r}(Bin_{i,r,k}) = bin_{i,r,k} by definition, the lemma follows. □ Definition 8.5. Let

(𝒩_{k,1}, …, 𝒩_{k,N_{k}}) = vec (∑_{j=1}^{k} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{j}−1} bin_{i,j,k}x_{0}^{ip^{k−j}}y_{0}^{p^{k}−ip^{k−j}} ) .

Inductively, for k > 1 and l ∈ {1, …, (k−1)}, let 𝒩_{k,N_{k}+l} =^{def} η_{l}(𝒩_{k−l,1}, …, 𝒩_{k−l,N_{k−l}+k−l−1}).

Also, let 𝒩_{k} =^{def} (𝒩_{k,1}, …, 𝒩_{k,N_{k}+k−1}), 𝒩̄_{k,i} =^{def} π(𝒩_{k,i}) ∈ 𝔽_{p}[x_{0}, y_{0}], and 𝒩̄_{k} =^{def} (𝒩̄_{k,1}, …, 𝒩̄_{k,N_{k}+k−1}).

Theorem 8.6. With the notation above, we have that

η̄_{k}(x_{0}, y_{0}) = ∑_{i=1}^{N_{k}+k−1} 𝒩̄_{k,i} = ∑_{j=1}^{k} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{j}−1} bin_{i,j,k}x_{0}^{ip^{k−j}}y_{0}^{p^{k}−ip^{k−j}} + ∑_{l=1}^{k−1} η̄_{l}(𝒩̄_{k−l}).

Remark 8.7. Note that

∑_{j=1}^{k} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{j}−1} bin_{i,j,k}x_{0}^{ip^{k−j}}y_{0}^{p^{k}−ip^{k−j}} = ∑_{i=1}^{p^{k}−1} π (ξ_{k} (−\binom{p^{k}}{i})) x_{0}^{i}y_{0}^{p^{k}−i}

= ∑_{i=1}^{p^{k}−1} π (ξ_{v_{p}(i)} (−\frac{1}{p^{k−v_{p}(i)}} \binom{p^{k}}{i})) x_{0}^{i}y_{0}^{p^{k}−i}.

Proof. We prove the theorem by induction on k. The case k = 1 is trivial.

Assume now that the statement is true for any integer from 1 to (k − 1). We then have, by the induction hypothesis and using Eq. (5.2), that

η_{k}(x, y) = \frac{x^{p^{k}} + y^{p^{k}} − (x + y)^{p^{k}}}{p^{k}} − ∑_{j=1}^{k−1} \frac{η_{j}(x, y)^{p^{k−j}}}{p^{k−j}}

= ∑_{j=1}^{k} \frac{1}{p^{k−j}} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{j}−1} Bin_{i,j,k}x^{ip^{k−j}}y^{p^{k}−ip^{k−j}} − ∑_{j=1}^{k−1} ( ∑_{r=1}^{N_{j}+j−1} \frac{𝒩_{j,r}^{p^{k−j}}}{p^{k−j}} − ∑_{l=1}^{k−j} \frac{η_{l}(𝒩_{j})^{p^{k−j−l}}}{p^{k−j−l}} ) .

We also have by definition of 𝒩_{j,r} that

∑_{r=1}^{N_{j}+j−1} \frac{𝒩_{j,r}^{p^{k−j}}}{p^{k−j}} = \frac{1}{p^{k−j}} (∑_{r=1}^{j} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{r}−1} bin_{i,r,j}^{p^{k−j}}x^{ip^{k−r}}y^{p^{k}−ip^{k−r}} + ∑_{l=1}^{j−1} η_{l}(𝒩_{j−l})^{p^{k−j}} ) .

Also, note that, again by definition, we have η_{l}(𝒩_{j−l}) = 𝒩_{j,N_{j}+l} and

∑_{l=1}^{k−j} \frac{η_{l}(𝒩_{j})^{p^{k−j−l}}}{p^{k−j−l}} = ∑_{t=j+1}^{k} \frac{η_{t−j}(𝒩_{j})^{p^{k−t}}}{p^{k−t}} = ∑_{t=j+1}^{k} \frac{𝒩_{t,N_{t}+t−j}^{p^{k−t}}}{p^{k−t}} .

Thus, we get

η_{k}(x, y) = ∑_{j=1}^{k} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{j}−1} \frac{Bin_{i,j,k}}{p^{k−j}} x^{ip^{k−j}}y^{p^{k}−ip^{k−j}} − ∑_{j=1}^{k−1} ∑_{r=1}^{j} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{r}−1} \frac{bin_{i,r,j}^{p^{k−j}}}{p^{k−j}} x^{ip^{k−r}}y^{p^{k}−ip^{k−r}}

− ∑_{j=1}^{k−1} ∑_{l=1}^{j−1} \frac{𝒩_{j,N_{j}+l}^{p^{k−j}}}{p^{k−j}} + ∑_{j=1}^{k−1} ∑_{t=j+1}^{k} \frac{𝒩_{t,N_{t}+t−j}^{p^{k−t}}}{p^{k−t}} . (8.2)

But,

− ∑_{j=1}^{k−1} ∑_{l=1}^{j−1} \frac{𝒩_{j,N_{j}+l}^{p^{k−j}}}{p^{k−j}} + ∑_{j=1}^{k−1} ∑_{t=j+1}^{k} \frac{𝒩_{t,N_{t}+t−j}^{p^{k−t}}}{p^{k−t}}

= − ∑_{j=2}^{k−1} ∑_{l=1}^{j−1} \frac{𝒩_{j,N_{j}+l}^{p^{k−j}}}{p^{k−j}} + ∑_{t=2}^{k} ∑_{j=1}^{t−1} \frac{𝒩_{t,N_{t}+t−j}^{p^{k−t}}}{p^{k−t}} = ∑_{j=1}^{k−1} 𝒩_{k,N_{k}+k−j} = ∑_{j=1}^{k−1} 𝒩_{k,N_{k}+j}. (8.3)

Also,

∑_{j=1}^{k} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{j}−1} \frac{Bin_{i,j,k}}{p^{k−j}} x^{ip^{k−j}}y^{p^{k}−ip^{k−j}} − ∑_{j=1}^{k−1} ∑_{r=1}^{j} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{r}−1} \frac{bin_{i,r,j}^{p^{k−j}}}{p^{k−j}} x^{ip^{k−r}}y^{p^{k}−ip^{k−r}}

= ∑_{j=1}^{k} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{j}−1} \frac{Bin_{i,j,k}}{p^{k−j}} x^{ip^{k−j}}y^{p^{k}−ip^{k−j}} − ∑_{r=1}^{k−1} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{r}−1} (∑_{j=r}^{k−1} \frac{bin_{i,r,j}}{p^{k−j}} ) x^{ip^{k−r}}y^{p^{k}−ip^{k−r}} (8.4)

= ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{k}−1} Bin_{i,k,k}x^{i}y^{p^{k}−i} + ∑_{r=1}^{k−1} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{r}−1} (\frac{Bin_{i,r,k}}{p^{k−r}} − ∑_{j=r}^{k−1} \frac{bin_{i,r,j}}{p^{k−j}} ) x^{ip^{k−r}}y^{p^{k}−ip^{k−r}}.

Now, applying Lemma 8.4,

\frac{Bin_{i,r,k}}{p^{k−r}} − ∑_{j=r}^{k−1} \frac{bin_{i,r,j}}{p^{k−j}} = \frac{1}{p^{k−r}} (Bin_{i,r,k} − ∑_{l=0}^{k−r−1} bin_{i,r,r+l} p^{l}) ≡ bin_{i,r,k} (mod p).

Since also Bin_{i,k,k} ≡ bin_{i,k,k} (mod p), Eq. (8.4) is congruent modulo p to

∑_{r=1}^{k} ∑_{\begin{matrix}i=1 \\ p∤i \end{matrix}}^{p^{r}−1} bin_{i,r,k}x^{ip^{k−r}}y^{p^{k}−ip^{k−r}} = ∑_{i=1}^{N_{k}} 𝒩_{k,i}.

Together with Eqs. (8.2) and (8.3), this gives the desired result. □

Theorem 8.6 gives an algorithm, made explicit as Algorithm 2 below, that allows us to compute η̄_{k}(a_{1}, …, a_{n}) directly in characteristic p, except for the bin_{i,j,k}, and without having to pre-compute or store in memory any auxiliary polynomials.

It should be noted Algorithm 2, as described, computes some terms many times over, due to the numerous recursions involved. One could probably improve it by storing the terms which will be needed later, but this is not entirely trivial. One could also just save all terms which have been computed, which might be wasteful, but could save some computing time. But, although there is certainly room for improvement, Algorithm 2 can still be useful, as one can see in the examples in Section 9.

9. Some Concrete Computations

In this section we show how the methods from the previous sections yield great improvements in some concrete examples. The computer used was a Dell Precision 690 server with two dual-core 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 (64 bit). The software used in the computations was MAGMA (versions 2.16-6 and 2.16-11). More examples can be Algorithm 2 Compute (ℳ_{1}(a_{1}, …, a_{n}), …, ℳ_{k}(a_{1}, …, a_{n})), given bin_{i,j,k} for j ∈ {1, …, k}, i ∈ {1, … p^{j} − 1} \ pℤ.

function v-etas-p(v = (a_{1}, …, a_{n}), k)

if n = 1 then

return (0, …, 0) end if if n = 2 then

R ← () ▷ result for t ← 1, k do

R[t] ← (bin_{i,j,t} a_{1}^{ip^{t−j}}a_{2}^{p^{t}−ip^{t−j}} : j ∈ {1, …, t} and i ∈ {1, …, p^{j} − 1} \ pℤ) end for for t = 1, k − 1 do

T ← v-etas-p(R, k − t) ▷ temp. var. for s = 1, k − t do

append T [s] to R[t + s] end for

end for

return R end if m ← ⌊n/2⌋ v_{1} ← (a_{1}, …, a_{m}) v_{2} ← (a_{m+1}, …, a_{n}) s_{1} ← a_{1} + ⋯ + a_{m} s_{2} ← a_{m+1} + ⋯ + a_{n} x_{1} ← v-etas-p((a_{1}, …, a_{m}), k) x_{2} ← v-etas-p((a_{m+1}, …, a_{n}), k) x_{3} ← v-etas-p((s_{1}, s_{2}), k) R ← () ▷ result for i ← 1, k do ▷ add first three entries to all ℳ_{i}

R[i] ← (x_{1}[i], x_{2}[i], x_{3}[i]) end for for i ← 2, k do ▷ add the remaining entries

T ← v-etas-p(R[i − 1], k − i + 1) ▷ temp. var. for t ← i, k do

append T [t − i + 1] to R[t] end for

end for return R

end function

found at [Fin10a] in the case of length 3, where the formulas and algorithms are particularly

simpler.

As we have seen there are two ways to compute η̄_{k}(a_{1}, …, a_{r}): using Algorithm 1, in

which we first have to compute and store the needed η̄_{i}’s, or using Algorithm 2, in which we just need to compute and store the bin_{i,j,k}, which is much faster and requires much less memory.

As a first example, for p = 11 we’ve computed S_{3} using the recursive formula (2.4) and using Proposition 7.1 with Algorithm 1. The former took approximately 130.56 hours, while the latter took approximately 7.20 hours. The computation of η̄_{i}(X, Y) for i = 1, 2, 3, necessary for this second method, takes only 0.19 seconds in this case.

The 24 gigabytes of memory available were not enough to compute S_{4} with either method. On the other hand, we do not need S_{4} to add Witt vectors with our new methods. Using Proposition 7.1, we can add Witt vectors using the η̄_{i}’s. For instance, we can add two vectors in W_{6}(𝔽_{11^{10}}) in about a second (on average) using Algorithm 1, after we spend approximately 3.61 hours to compute the η̄_{i}(X, Y) for i ∈ {1, 2, 3, 4, 5}. (Although this might seem as long time, remember that it took 7.20 hours to compute S_{3} and we cannot even compute S_{4} with the memory available.) Using Algorithm 2, we need only 5.750 seconds to compute the necessary bin_{i,j,k} (from Theorem 8.6), but then it takes us about 26 seconds on average to add two Witt vectors in W_{6}(𝔽_{11^{10}}). So, in this case Algorithm 2 would certainly be more efficient if we ones does not need too many additions.

Also, as observed in Section 3, one can evaluate a polynomial in two variables at a pair of Witt vectors directly using Theorem 6.4, thus avoiding computing sums and power of Witt vectors. Let then

f(x, y) = ∑_{0≤i,j≤d} a_{i,j}x^{i}x^{j} ∈ W_{n+1}(𝕜)[x, y]  (9.1)

and x_{0}, y_{0} ∈ W_{n+1}(𝕜). Table 9.1 shows the time and memory usage in examples with a_{i,j}’s, x_{0}, and y_{0} randomly chosen in the finite field 𝕜 with the two approaches, i.e., performing the sums and products of Witt vectors and using the formula for the Greenberg transform. Note that the addition and multiplication of Witt vectors performed in these tests were done in the improved way described above, i.e., using the η̄_{i}’s instead of computing the S_{i}’s and P_{i}’s. We’ve used Algorithm 1 for both, and it should also be observed that the times to compute the η̄_{i}’s (for i ≤ n), which are then used in both methods, are shown separately in Table 9.1.

As observed above, there are more efficient methods to perform operation with Witt vector over finite fields, namely, by identifying W_{n+1}(𝔽_{q}) with ℤ_{q}/p^{n+1}, as observed in Section 1 and made explicit in Section 2. If it then seems somewhat artificial to use Witt vector over finite fields in our examples, note that the running time of the algorithm basically depends on the number of operations in the field (or ring) of the entries of the Witt vector, and therefore these examples give an idea of how these new methods require fewer operations. In the case of, say, polynomial rings, the operations will demand a lot more time, but

Sum and Prod.  GT form.
𝕜 n d η̄_{i} time (sec) time (sec) mem. (MB) time (sec) mem. (MB)
𝔽_{3^{10}} 9 20  108.78  433.31  12.22  130.28  16.40
𝔽_{7^{10}} 6 20  3554.78  2410.49  28.00  600.23  28.62
𝔽_{11^{10}} 5 20  5794.89  3564.62  37.44  839.37  30.88
𝔽_{13^{10}} 5 15 29854.75  4608.84  70.63  1045.08  49.00
𝔽_{19^{10}} 4 15  2760.36  2301.17  32.44  983.08  26.72

Table 9.1. Times and memory usages to evaluate random f ∈ W_{n+1}(𝕜)[x, y], where deg_{x}f, deg_{y} f ≤ d, at random (x_{0}, y_{0}).

Characteristic time (in sec.) memory usage (in MB)
7  7.300  40.97
11  421.09  1010.03
13  6542.590  4175.28

Table 9.2. Times and memory usages to compute J_{3}.

one can expect comparable improvements in relative terms. (It will also be more efficient in terms of memory!) Choosing finite fields for these tests allowed us to have some quick examples, as computations can take a long time and a lot of memory in other examples.

In any event, we now provide some examples over different rings. As an example over polynomial rings, we computed the Greenberg transform of a polynomial as in Eq. (9.1) with 𝕜 = 𝔽_{3}, n = 3, and d = 5, again with coefficients a_{i,j}’s randomly chosen. In this case, using sums and products of Witt vectors (with x = (x_{0}, x_{1}, x_{2}, x_{3}) and y = (y_{0}, y_{1}, y_{2}, y_{3}), where x_{i} and y_{j} are indeterminates) the computation took 6590.43 seconds and used 636.44 megabytes of memory. On the other hand, using the formula for the Greenberg, it took 359.07 seconds and used 255.59 megabytes of memory. So, the gains are even more significant in this case.

Another example would be the one mentioned in Section 4. As mentioned there, using simply the polynomials for sums and products of Witt vectors, we could only compute J_{3} for p = 5. (Remember that the J_{i}’s are the rational functions such that given an ordinary j-invariant j_{0}, the j-invariant of its canonical lifting is (j_{0}, J_{1}(j_{0}), J_{2}(j_{0}), …). This computation involves computing the Greenberg transform of the modular polynomial.) This computation took 407.089 seconds and used 376.78 megabytes of memory. Now, with Theorem 6.4 above, we can compute J_{3} in 0.480 seconds and using only 21.28 megabytes, and we could compute some new examples. The time and memory usage for these are shown in Table 9.2. (The case of p = 17 used over 24 gigabytes of memory and therefore crashed still incomplete.) In particular, these computations were useful to show that Conjecture 10.1 from [Fin10a] holds p = 11, i.e., J_{3} has a pole of order 11^{2} at zero in this case.)

It should be also noted that these computations of the J_{3}’s can be improved by studying what happens with the Greenberg transform of Φ_{p}(X, Y) when evaluated at ((x_{0}, …, x_{3}), (x_{0}^{p}, …, x_{3}^{p})), as likely many of the terms that appear will vanish, as happens for J_{2}. (See Theorem 5.5 and Table 5.1 of [Fin10c].) These improvements come from analyzing the fourth coordinate of the Greenberg transform in this particular case, and therefore Theorem 6.4 was crucial.

Thus, despite still often requiring a lot of resources, the results presented here can still yield considerable improvements over previous methods. The MAGMA routines that were used on the tests presented here, including implementations of Algorithm 1 and Algorithm 2, are available at the time of writing at

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

Acknowledgment. The author would like to thank the Centre de Recherches Mathématiques for the hospitality and during the preparation of this manuscript.

References

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

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

[Fin10a] L. R. A. Finotti. Computations with Witt vectors of length 3. To appear at the “Journal de Théorie des Nombres de Bordeaux”. Available at http://www.math.utk.edu/~finotti/, 2010.

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

[Fin10c] L. R. A. Finotti. Nonexistence of pseudo-canonical liftings. Submitted. Available at

        http://www.math.utk.edu/~finotti/, 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.

[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.

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

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