POINT COUNTING ON K3 SURFACES AND AN APPLICATION CONCERNING REAL AND COMPLEX MULTIPLICATION

ANDREAS-STEPHAN ELSENHANS AND JÖRG JAHNEL

Abstract. We report on our project to find explicit examples of K3 surfaces having real or complex multiplication. Our strategy is to search through the arithmetic consequences of RM and CM. In order to do this, an efficient method is needed for point counting on surfaces defined over finite fields. For this, we describe algorithms that are p-adic in nature.

1. Introduction

Let X be a quasi-projective variety over a finite field 𝔽_{q} of characteristic p > 0. One of the most natural questions concerning the arithmetic of X is certainly to pinpoint the number of points that X has over its base field 𝔽_{q}. For example, let X := V (f) ⊂ P^{N} be given for f ∈ 𝔽_{q}[T_{0}, …, T_{N}] a homogeneous polynomial. Then this means just to count the number of solutions in 𝔽_{q}^{N+1} of the equation f(T_{0}, …, T_{N}) = 0, ignoring about (0, …, 0) and up to scaling.

More generally, one asks for the sequence (#X(𝔽_{q^{i}}))_{i≥1} of integers associated with X that is composed of the numbers of points on X that are defined over the extension fields 𝔽_{q^{i}}. This sequence is of practical as well as theoretical interest. For example, it is known since the days when E. Artin wrote his Ph.D. thesis [2, §22] that it is wise to form the generating function

Z_{X}(t) := exp (∑_{i=1}^{∞} #X(𝔽_{q^{i}})\frac{t^{i}}{i} ) ,  (1)

which is called the zeta function of the variety X. In fact, Z_{X} is always a rational function. According to [24, Exp. XV, §3, n^{∘}2 and 3], it is the alternating product of the Weil polynomials χ_{i} associated with X, the characteristic polynomials of the operation of the geometric Frobenius Frob on the l-adic cohomology vector spaces H_{c,ét}^{i}(X_{\overline{𝔽}_{q}}, ℚ_{l}) with compact support,

Z_{X}(t) = ∏_{j=0}^{2 dim X}det (1 − t Frob |H_{c,ét}^{j}(X_{\overline{𝔽}_{q}}, ℚ_{l}))^{(−1)^{j+1}} =: \frac{χ_{1}(t)χ_{3}(t) ⋯ χ_{2 dim X−1}(t)}{χ_{0}(t)χ_{2}(t)χ_{4}(t) ⋯ χ_{2 dim X}(t)} . (2)

Moreover, at least when X is proper and smooth, the Weil polynomials χ_{j} have remarkable properties. For example, as was conjectured by A. Weil and proven by P. Deligne in [8, Théorème (1.6)] and [10, Corollaire (3.3.9)], every complex root of χ_{j} is of absolute value q^{j/2}. In particular, no cancellations occur in formula (2).

Assume now that the geometry of the variety X_{\overline{𝔽}_{q}} is well understood. By which we mean that at least all its l-adic Betti numbers are known. This is usually the case in practice, as the varieties considered are curves of known genus, abelian varieties of known dimension, nonsingular complete intersections of known multidegree, K3 surfaces, etc. From the algorithmic point of view, formula (2) then shows that it is easy to calculate #X(𝔽_{q^{i}}) for some very large i, provided that #X(𝔽_{q}), #X(𝔽_{q^{2}}), …, #X(𝔽_{q^{k}}) have been found. Thereby, the bound k only depends on the geometry of X_{\overline{𝔽}_{q}}. Indeed, once k is properly chosen, (1) and (2) allow to compute all coefficients of the polynomials χ_{j} from the numbers of points known. Then to pinpoint #X(𝔽_{q^{i}}) is just the calculation of the i-th power series coefficient of ∑_{j}(−1)^{j+1} log χ_{j}.

Date: Mai 17, 2016.

2010 Mathematics Subject Classification. 14J28 (primary), 11G15, 11Y16, 11M38 (secondary).

Key words and phrases. point counting, Harvey’s p-adic method, Weil polynomial, K3 surface, real and complex multiplication.

Unfortunately, for most nontrivial types of varieties, the bound k turns out to be too large, such that it is not feasible to count #X(𝔽_{q}), #X(𝔽_{q^{2}}), …, #X(𝔽_{q^{k}}) in a naive way, even for medium-sized values of q. For instance, when X is a K3 surface, things are relatively simple. In fact, χ_{1}(t) = χ_{3}(t) = 1, χ_{0}(t) = 1 − t, χ_{4}(t) = 1 − q^{2}t, and only χ_{2} varies, which is of degree 22. Nevertheless, one may only hope that k = 10 is sufficient. It is known that there are cases where k has to be chosen larger [17, Table 6].

Our motivation. Real and complex multiplication for K3 surfaces. Our motivation comes from projective varieties X that are defined over a number field K. As was first noticed by R. van Luijk, from point counts on the reductions X_{𝔭_{1}}, X_{𝔭_{2}} modulo two primes [31, 32, 16, 19] of good reduction or sometimes only one [18], one may determine the geometric Néron-Severi rank of X. This applies well even to varieties of general type [15], but a nontrivial case is provided already by K3 surfaces.

The very basic idea behind van Luijk’s method is that, in the case of a K3 surface, rk Pic X_{\overline{𝔽}_{𝔭}} is always even and one has rk Pic X_{\overline{𝔽}_{𝔭}} ≥ rk Pic X\overline{K}. Moreover, one hopes to find a prime such that rk Pic X_{\overline{𝔽}_{𝔭}} is actually equal to rk Pic X\overline{K} or rk Pic X\overline{K} + 1. As was observed by F. Charles [5], the existence of such primes is related to whether X has real multiplication or not. More precisely, existence is provided unless X has real multiplication and (22 − rk Pic X\overline{K})/[E : ℚ] is odd, for E the endomorphism field.

We say that a K3 surface X has real or complex multiplication when the endomorphism algebra of the transcendental part T ⊂ H^{2}(X(ℂ), ℚ), considered as a pure ℚ-Hodge structure, is strictly larger than ℚ. It is then either a totally real field or a CM field [41, Theorem 1.6.a) and Theorem 1.5.1]. Starting from this definition, it seems, however, hard to conclude anything for concrete examples. One may deduce [23] at least that having RM or CM is a property of positive codimension in the analytic moduli space of K3 surfaces of fixed Picard rank (unless the Picard rank is 20, in which case every K3 surface has CM). Thus, having RM or CM should be thought of as being exceptional.

In particular, it seems that one does not find examples of RM or CM surfaces just by accident. Our approach is therefore to perform our searches through the arithmetic consequences of RM and CM. These include that, for all primes 𝔭 that are (at least partially) inert in E, the reduction X_{𝔭} is non-ordinary. I.e., that one has #X_{𝔭}(𝔽_{𝔭}) ≡ 1 (mod p) for p the prime number below 𝔭. Moreover, the transcendental factors of the corresponding Weil polynomials are all partially split over the same field, the endomorphism field E. Cf. the top of Section 5 for a more precise statement. In order to detect the very few surfaces showing such a behaviour within a large family, efficient methods for point counting are asked for.

Harvey’s p-adic method for counting points. The most efficient methods for counting points on a variety over a finite field that are known today are p-adic in nature. One of them was originally developed by K. Kedlaya in [28]. Kedlaya’s point of view was cohomological. This means, he computed the characteristic polynomial of the Frobenius operation on the Monsky-Washnitzer cohomology, a well-behaved cohomology theory with p-adic coefficients for affine varieties in characteristic p. This approach seems to be very natural. It is, however, still limited to curves, and in fact to particular types of them. T. Satoh’s p-adic algorithm [35] for ordinary elliptic curves could perhaps be seen as a predecessor of this method.

POINT COUNTING ON K3 SURFACES AND APPLICATIONS 3

On the other hand, as was shown by D. Harvey [26], an entirely elementary approach is possible, as well as a generalisation to arbitrary schemes of finite type over a finite field. Harvey’s method is, at least partially, based on earlier ideas. We are most likely unaware of some of its predecessors, but the work of D. Wan [39, 40], as well as that of A. Lauder and D. Wan [30], certainly should be mentioned. Probably, B. Dwork [13, 14] is the very first, to whom the ideas behind [26] may be traced back.

We report on a variation of Harvey’s p-adic method for double covers of the projective space, which we implemented as far as required for the needs of our search for K3 surfaces of degree two having RM or CM. Although it was never mentioned in print, this variation was certainly known, or at least obvious, to D. Harvey before. Generally speaking, it seems that the algorithm described in [26], although general in theory, may practically be implemented only in a form specialised to particular types of varieties. Our code will be available within magma [4], version 2.22.

Acknowledgement. We wish to thank David Harvey for valuable one-to-one talks, as well as the two anonymous referees for their suggestions on how to improve this note.

2. Counting points on varieties over finite fields–Elementary methods

Let us assume that X ⊂ A_{𝔽_{q}}^{N} is an affine hypersurface. I.e., that X = V (f) for an arbitrary polynomial f ∈ 𝔽_{q}[T_{1}, …, T_{N}]. At least in theory, this is not a serious restriction as every variety over a base field is birationally equivalent to a hypersurface [25, Chap. I, Prop. 4.9], cf. [26, §1.3]. In practice, of course, too complicated transformations are undesirable, as they obviously reduce the speed of the method. Even if that concerns only a constant factor.

2.1 (Determination of the points). The most naive approach to point counting is certainly to determine all the points. If, for whatever application, the actual points are asked for then there is no alternative to such a method. Moreover, to have some code available that realises a naive approach is useful for testing more advanced algorithms.

In order to determine the 𝔽_{q^{i}}-rational points on X, one has to run an iterated loop over all (N −1)-tuples (x_{1}, …, x_{N−1}) ∈ 𝔽_{q^{i}}^{N−1}. Each time, the roots in 𝔽_{q^{i}} of a univariate polynomial g have to be found, which just means to compute gcd(g, T^{q^{i}} − T). Thus, the complexity to determine the 𝔽_{q^{i}}-rational points is essentially O(q^{(N−1)i}).

Remark 2.2. When X is defined over 𝔽_{q}, but points over 𝔽_{q^{i}} for i > 1 are sought for, one may gain a factor of i by dealing with Frobenius orbits instead of points.

2.3 (FFT point counting). Assume that X is given by a decoupled polynomial f. I.e., that f = f_{1}(T_{1}, …, T_{M}) + f_{2}(T_{M+1}, …, T_{N}) for some 1 < M < N. Then #X(𝔽_{q^{i}}) = (c_{1} ∗ c_{2})(0) in terms of the two counting functions c_{1} and c_{2}, given by

c_{1}(c) := #{(x_{1}, …, x_{M}) ∈ 𝔽_{q^{i}}^{M} | f_{1}(x_{1}, …, x_{M}) = c}  and
c_{2}(c) := #{(x_{M+1}, …, x_{N}) ∈ 𝔽_{q^{i}}^{N−M} | f_{2}(x_{M+1}, …, x_{N}) = c} .

In order to compute #X(𝔽_{q^{i}}), one first compiles look-up tables for c_{1} and c_{2} and then calculates (c_{1}∗c_{2})(0), according to the definition. The complexity of this method to count the 𝔽_{q^{i}}-rational points is O(q^{max{M,N−M}i}).

Similarly, for the double cover of A^{N} given by W^{2} = f, one has

#X(𝔽_{q^{i}}) = q^{iN} + ∑_{c∈𝔽_{q^{i}}} χ(c)·(c_{1} ∗ c_{2})(c) ,

where χ: 𝔽_{q^{i}} → {−1, 0, 1} denotes the quadratic character. The convolution c_{1} ∗c_{2} then has to be computed using the FFT method [22, Sätze 20.2 and 20.3] or [6, Theorem 32.8]. Here, again, the complexity is essentially O(q^{max{M,N−M}i}), with an additional log-factor coming from the Fourier transforms. Cf. [16, Algorithm 17] for more details on this method.

Example 2.4 (cf. [21, Example 3.13]). Consider the K3 surface X of degree 2 over 𝔽_{7}, given by

W^{2} = 6T_{0}^{6} + 6T_{0}^{5}T_{1} + 2T_{0}^{5}T_{2} + 6T_{0}^{4}T_{1}^{2} + 5T_{0}^{4}T_{2}^{2} + 5T_{0}^{3}T_{1}^{3} + T_{0}^{2}T_{1}^{4} + 6T_{0}T_{1}^{5} + 5T_{0}T_{2}^{5}

+ 3T_{1}^{6} + 5T_{2}^{6} .

The polynomial on the right hand side does not contain any monomial involving both T_{1} and T_{2}. Thus, over the affine plane P_{\overline{𝔽}_{7}}^{2}\V (T_{0}), the double cover X is given by a decoupled polynomial. The numbers of points over 𝔽_{7}, …, 𝔽_{7^{10}} are

60, 2 488, 118 587, 5 765 828, 282 498 600, 13 841 656 159, 678 225 676 496,
33 232 936 342 644, 1 628 413 665 268 026, 79 792 266 679 604 918.

Using the FFT method, it took about 2 hours of CPU time and required approximately 5 GB of memory to compute these numbers on an AMD 248 Opteron processor running at 2.2 GHz.

2.5 (Making étale cohomology explicit). For a general variety, it is probably a tough ask to make its l-adic cohomology vector spaces explicit, including the Frobenius operation on them. There are, however, certain special types of varieties, for which this is possible. For example, for an elliptic curve, one has H_{ét}^{1}(X_{\overline{𝔽}_{q}}, ℚ_{l}) ≅ \underleftarrow{lim}_{n} E(\overline{𝔽}_{q})[l^{n}]⊗_{ℤ_{l}} ℚ_{l}, which is the starting point of Schoof’s algorithm [36].

A different kind are those varieties, for which all the cycle maps [9, Cycle, §2.2.10]

cl: CH^{j}(X_{\overline{𝔽}_{q}})⊗_{ℤ} ℚ_{l} ⟶ H_{ét}^{2j}(X_{\overline{𝔽}_{q}}, ℚ_{l}(j))

are surjective and, moreover, H_{ét}^{j}(X_{\overline{𝔽}_{q}}, ℚ_{l}) = 0 for every odd integer j. These assumptions are fulfilled, for instance, for surfaces that are geometrically rational.

A case for which this approach is implemented in magma is that of a cubic surface. Here, CH^{1}(X_{\overline{𝔽}_{q}}) = Pic(X_{\overline{𝔽}_{q}}) ≅ ℤ^{7} is generated by the 27 lines. One has to determine the lines by a Gröbner base calculation. From the operation of Frob on the lines, one deduces the operation on H_{ét}^{2}(X_{\overline{𝔽}_{q}}, ℚ_{l}(1)).

Example 2.6.

> p := NextPrime(31^31);
> p;
17069174130723235958610643029059314756044734489
> rr<x,y,z,w> := PolynomialRing(GF(p),4);
> gl := x^3 + 2*y^3 + 3*z^3 + 5*w^3 - 7*(x+y+z+w)^3;
> time NumberOfPointsOnCubicSurface(gl);
291356705504951337929728147720395643095420441743546148074332970578622743757660955298550825611
Time: 1.180

Remark 2.7. The list of methods given in the section is by no means meant to be exhaustive. There is at least one further idea, which we can mention only in passing, namely the use of a fibration. For more information, we advise the reader to consult the articles [29] of A. Lauder and [34] of S. Pancratz and J. Tuitman.

3. Harvey’s p-adic method

As above, we assume that 𝔽_{q} is a finite field of characteristic p > 0. The method is p-adic in nature. It finds an approximation of #X(𝔽_{q^{i}}) with respect to the p-adic valuation. Thus, in order to pinpoint #X(𝔽_{q^{i}}) exactly, one needs, in addition, an estimate for the number of points.

Characteristic functions.

Notation 3.1. i) We continue to assume that X is an affine hypersurface. However, we now suppose that X := V (f) ∩ 𝔾_{m,𝔽_{q}}^{N} ⊂ 𝔾_{m,𝔽_{q}}^{N} is a subscheme of an affine torus. Again, this restriction is not serious as A_{𝔽_{q}}^{N} is a finite union of affine tori. For varieties more general than hypersurfaces, one might, in principle, simplify the situation by iteratively projecting away from points, cf. [26, §1.3]. ii) For every natural number i, let us denote by μ_{q^{i}−1} the group of all (q^{i} − 1)-th roots of unity and write ℤ_{q^{i}} for the integer ring of the local field ℚ_{p}(μ_{q^{i}−1}), which is an unramified extension of ℚ_{p}. ℤ_{q^{i}} is thus a complete discrete valuation ring with residue field 𝔽_{q^{i}}. Furthermore, μ_{q^{i}−1} ⊂ ℤ_{q^{i}} is bijectively mapped onto 𝔽_{q^{i}}^{∗} under the residue map

π = π_{i}: ℤ_{q^{i}} ↠ 𝔽_{q^{i}} .

This is, of course, an instance of taking Teichmüller representatives. iii) Moreover, one has ℤ_{q^{i}} ⊆ ℤ_{q^{i′}} if and only if 𝔽_{q^{i}} ⊆ 𝔽_{q^{i′}}. In this case, we introduce the quasi norm map

N_{ℤ_{q^{i′}} /ℤ_{q^{i}}} : ℤ_{q^{i}}[T_{1}, …, T_{N}] ⟶ ℤ_{q^{i}}[T_{1}, …, T_{N}] ,
g ↦ g·g^{(q^{i})}·g^{(q^{2i})} ⋯ g^{(q^{i′−i})} ,

for g^{(n)} the quasi power, given by g^{(n)}(T_{1}, …, T_{N}) := g(T_{1}^{n}, …, T_{N}^{n}). The quasi norm is compatible with the usual norm map N_{𝔽_{q^{i′}} /𝔽_{q^{i}}} : 𝔽_{q^{i′}} → 𝔽_{q^{i}} between the finite residue fields in the sense that, for arbitrary g ∈ ℤ_{q^{i}}[T_{1}, …, T_{N}] and z_{1}, …, z_{N} ∈ ℤ_{q^{i′}}, one has N_{ℤ_{q^{i′}} /ℤ_{q^{i}}} g(z_{1}, …, z_{N}) ∈ ℤ_{q^{i}} and

π_{i}(N_{ℤ_{q^{i′}} /ℤ_{q^{i}}} g(z_{1}, …, z_{N})) = N_{𝔽_{q^{i′}} /𝔽_{q^{i}}} (\overline{g}(π_{i′}(z_{1}), …, π_{i′}(z_{N}))) .

Here, \overline{g} ∈ 𝔽_{q^{i}}[T_{1}, …, T_{N}] denotes the reduction of g modulo (p). iv) We choose a lift F ∈ ℤ_{q}[T_{1}, …, T_{N}] of f.

Definition 3.2. We call a function Φ: μ_{q^{i}−1}^{N} → ℤ_{q} a characteristic function of X(𝔽_{q^{i}}) modulo p^{l} if, for every (z_{1}, …, z_{N}) ∈ μ_{q^{i}−1}^{N},

Φ(z_{1}, …, z_{N}) ≡ 0 (mod p^{l}) if (π(z_{1}), …, π(z_{N})) ∉ X(𝔽_{q^{i}}) and
Φ(z_{1}, …, z_{N}) ≡ 1 (mod p^{l}) if (π(z_{1}), …, π(z_{N})) ∈ X(𝔽_{q^{i}}) .

Proposition 3.3. Let a be a positive integer such that a(q − 1) ≥ l and i ∈ ℕ be arbitrary. Then

Φ := (1 − N_{ℤ_{q^{i}} /ℤ_{q}} F^{a(q−1)})^{l}
= 1 + ∑_{k=1}^{l}(−1)^{k}\binom{l}{k}N_{ℤ_{q^{i}} /ℤ_{q}} F^{ka(q−1)}

is a characteristic function of X(𝔽_{q^{i}}) modulo p^{l}.

Proof. By definition, (π(z_{1}), …, π(z_{N})) ∈ X(𝔽_{q^{i}}) if and only if f(π(z_{1}), …, π(z_{N})) = 0 ∈ 𝔽_{q^{i}}, which is equivalent to N_{𝔽_{q^{i}} /𝔽_{q}} (f(π(z_{1}), …, π(z_{N}))) = 0 ∈ 𝔽_{q} and

N_{ℤ_{q^{i}} /ℤ_{q}} F (z_{1}, …, z_{N}) ≡ 0 (mod p) .

If this is true then N_{ℤ_{q^{i}} /ℤ_{q}} F^{a(q−1)}(z_{1}, …, z_{N}) ≡ 0 (mod p^{a(q−1)}), hence the same modulo p^{l}, which implies 1 − N_{ℤ_{q^{i}} /ℤ_{q}} F^{a(q−1)}(z_{1}, …, z_{N}) ≡ 1 (mod p^{l}), and

(1 − N_{ℤ_{q^{i}} /ℤ_{q}} F^{a(q−1)}(z_{1}, …, z_{N}))^{l} ≡ 1 (mod p^{l}) .

On the other hand, in the opposite case, one has N_{ℤ_{q^{i}} /ℤ_{q}} F^{q−1}(z_{1}, …, z_{N}) ≡ 1 (mod p) and, consequently, 1 − N_{ℤ_{q^{i}} /ℤ_{q}} F^{a(q−1)}(z_{1}, …, z_{N}) ≡ 0 (mod p), which shows

(1 − N_{ℤ_{q^{i}} /ℤ_{q}} F^{a(q−1)}(z_{1}, …, z_{N}))^{l} ≡ 0 (mod p^{l}) ,

as required. □

Remarks 3.4. i) According to the definition, if Φ is a characteristic function of X(𝔽_{q^{i}}) modulo p^{l} then

#X(𝔽_{q^{i}}) ≡ ∑_{(z_{1},...,z_{N})∈μ_{q^{i}−1}^{N}} Φ(z_{1}, …, z_{N}) (mod p^{l}) .  (3)

ii) One has

∑_{z∈μ_{q^{i}−1}}z^{e} = 0

unless e is a multiple of q^{i} − 1. Therefore, the right hand side of (3) is (q^{i} − 1)^{N} times the sum of the coefficients of Φ at the monomials of the form (T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}})^{q^{i}−1}, for e_{1}, …, e_{N} ∈ ℤ_{≥0}. iii) For l = 1, these facts are known for a long time, cf. [3, Sec. 1.1, Theorem 4]. iv) One might want to take the step from l = 1 to a larger value in a more naive manner as follows. For (π(z_{1}), …, π(z_{N})) ∉ X(𝔽_{q^{i}}), one has N_{ℤ_{q^{i}} /ℤ_{q}} F^{a(q−1)}(z_{1}, …, z_{N}) = 1 + sp, for some unknown s ∈ ℤ_{q^{i}}. This yields

N_{ℤ_{q^{i}} /ℤ_{q}} F^{2a(q−1)}(z_{1}, …, z_{N}) = 1 + 2sp + s^{2}p^{2} ,
N_{ℤ_{q^{i}} /ℤ_{q}} F^{3a(q−1)}(z_{1}, …, z_{N}) = 1 + 3sp + 3s^{2}p^{2} + s^{3}p^{3} ,
⋮
N_{ℤ_{q^{i}} /ℤ_{q}} F^{la(q−1)}(z_{1}, …, z_{N}) = 1 + lsp + \binom{l}{2}s^{2}p^{2} + \binom{l}{3}s^{3}p^{3} + ⋯ + \binom{l}{l−1}s^{l−1}p^{l−1} + \binom{l}{l}s^{l}p^{l} .

There is a linear combination of these expressions that eliminates all terms containing p, p^{2}, …, p^{l−1}. Namely, one needs to take as the coefficient vector the first row of the Pascal-like matrix

( \begin{matrix}1 & 1 & 0 & ⋯ & 0 \\ 1 & 2 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & l−1 & \binom{l−1}{2} & ⋯ & \binom{l−1}{l−1} \\ 1 & l & \binom{l}{2} & ⋯ & \binom{l}{l−1} \end{matrix} )^{−1} .

However, well-known relations between binomial coefficients reveal that the first row of this matrix is exactly (l, −\binom{l}{2}, \binom{l}{3}, …, (−1)^{l+1}\binom{l}{l}), in agreement with Proposition 3.3.

Linear operators.

Notation 3.5. i) We consider the polynomial ring ℤ_{q}[T_{1}, …, T_{N}] as a free ℤ_{q}-module and equip it with the symmetric bilinear form ⟨., .⟩, given by

⟨ ∑_{i_{1},...,i_{N}}a_{i_{1},...,i_{N}} T_{1}^{i_{1}} ⋯ T_{N}^{i_{N}} , ∑_{i_{1},...,i_{N}}b_{i_{1},...,i_{N}} T_{1}^{i_{1}} ⋯ T_{N}^{i_{N}} ⟩ := ∑_{i_{1},...,i_{N}}a_{i_{1},...,i_{N}} b_{i_{1},...,i_{N}} .

Then the monomials form an orthonormal basis. Furthermore, the bilinear form ⟨., .⟩ yields a norm ∥.∥ on ℤ_{q}[T_{1}, …, T_{N}] such that ∥g∥ := [∥⟨g, g⟩∥_{p}]^{1/2}, for ∥.∥_{p} the usual normalised p-adic valuation. The completion ℤ_{q}{{T_{1}, …, T_{N}}} is a ℤ_{q}-Hilbert space. ii) There is the bounded linear operator φ: ℤ_{q}{{T_{1}, …, T_{N}}} → ℤ_{q}{{T_{1}, …, T_{N}}}, provided by taking the quasi power h ↦ h^{(q)}. Its adjoint

κ: ℤ_{q}{{T_{1}, …, T_{N}}} ⟶ ℤ_{q}{{T_{1}, …, T_{N}}}

maps the monomial (T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}})^{q} to T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}} and all monomials not being of this particular type to zero. In particular, κ is a retraction for φ. I.e., one has κ∘φ = id.

On the other hand, for i ∈ ℕ, the composition φ^{i}∘κ^{i}: ℤ_{q}{{T_{1}, …, T_{N}}} → ℤ_{q}{{T_{1}, …, T_{N}}} is the orthogonal projection to the sub-ℤ_{q}-Hilbert space spanned by all monomials of the type (T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}})^{q^{i}}. iii) For every polynomial g ∈ ℤ_{q}[T_{1}, …, T_{N}], the multiplication map

m_{g}: ℤ_{q}{{T_{1}, …, T_{N}}} ⟶ ℤ_{q}{{T_{1}, …, T_{N}}} , h ↦ gh ,

is a bounded linear operator. Fact 3.6. Let g ∈ ℤ_{q}[T_{1}, …, T_{N}] and i ∈ ℕ be arbitrary. Then

κ^{i}∘m_{g^{(q^{i})}} ∘φ^{i} = m_{g} .  □

Definition 3.7 (Linear operator associated with a polynomial). Given a positive integer i and a polynomial g ∈ ℤ_{q}[T_{1}, …, T_{N}], we consider the linear operator

M_{g,i} := κ^{i}∘m_{g} .

This operator is of interest because of the two results below. Lemma 3.8. For every positive integer i and every polynomial g ∈ ℤ_{q}[T_{0}, …, T_{N}], one has

M_{N_{ℤ_{q^{i}} /ℤq} g, i} = (M_{g,1})^{i} .  (4)

Proof. We will show this inductively. The assertion is clearly true for i = 1. For the inductive step, let us assume that equation (4) is true for a certain value of i. Then, by 3.1.iii), we have N_{ℤ_{q^{i+1}} /ℤ_{q}} g = g^{(q^{i})}·N_{ℤ_{q^{i}} /ℤ_{q}} g. Hence, Definition 3.7 shows that

M_{N_{ℤ_{q^{i+1}} /ℤq} g, i+1} = κ^{i+1}∘m_{N_{ℤ_{q^{i+1}} /ℤq} g}
= κ^{i+1}∘m_{g^{(q^{i})}} ∘m_{N_{ℤ_{q^{i}} /ℤq} g}
= κ^{i+1}∘m_{g^{(q^{i})}} ∘φ^{i}∘κ^{i}∘m_{N_{ℤ_{q^{i}} /ℤq} g} .

Observe that the projection φ^{i}∘κ^{i} has no effect here. Indeed, it is followed by the multiplication with a polynomial, all of whose monomials have exponents only divisible by q^{i}, and the retraction κ^{i}. Thus, according to Fact 3.6, Definition 3.7, and the induction hypothesis,

M_{N_{ℤ_{q^{i+1}} /ℤq} g, i+1} = κ∘m_{g} ∘M_{N_{ℤ_{q^{i}} /ℤq} g, i}
= M_{g,1}∘ (M_{g,1})^{i}
= (M_{g,1})^{i+1} ,

as required. □

Proposition 3.9. Let i be a positive integer and g ∈ ℤ_{q}[T_{0}, …, T_{N}] be any polynomial.

a) Then the linear operator M_{g,i} is trace class.

b) Its trace tr M_{g,i} is equal to the sum of all coefficients of g at the monomials of the form (T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}})^{q^{i}−1}.

Proof. We will only prove b), as this immediately implies a). By definition,

tr M_{g,i} = ∑_{k∈K}⟨M_{g,i}(v_{k}), v_{k}⟩ ,

for (v_{k})_{k∈K} any complete orthonormal system. In particular, for the system of all monomials.

For the monomial T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}}, the pairing ⟨M_{g,i}(T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}}), T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}} ⟩ yields the coefficient of M_{g,i}(T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}}) = κ^{i}(gT_{1}^{e_{1}} ⋯ T_{N}^{e_{N}}) at the monomial T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}}. This is nothing but the coefficient of gT_{1}^{e_{1}} ⋯ T_{N}^{e_{N}} at (T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}})^{q^{i}} and, hence, the coefficient of g at (T_{1}^{e_{1}} ⋯ T_{N}^{e_{N}})^{q^{i}−1}. The assertion follows. □

Remark 3.10. For general information on p-adic Hilbert spaces, linear operators, and the concept of the trace, the interested reader might compare Chapters 2 and 3 of the textbook [12] of T. Diagana.

An algorithm.

Algorithm 3.11. Given a projective hypersurface X = V (f) ⊂ P_{𝔽_{q}}^{N} and a positive integer n, this algorithm computes the numbers of points #X(𝔽_{q}), #X(𝔽_{q^{2}}), …, #X(𝔽_{q^{n}}).

i) Choose a lift F̃ ∈ ℤ_{q}[T_{0}, …, T_{N}] of f. Decompose X into X^{c} := [V (T_{0}) ∪ … ∪ V (T_{N})] ∩ X and X^{0} := X \X^{c}. For the lower dimensional closed subscheme X^{c}, either use naive point counting methods or apply the method recursively. For X^{0}, do the following. ii) Use elementary arguments or the Weil conjectures or both to find estimates for #X^{0}(𝔽_{q}), #X^{0}(𝔽_{q^{2}}), …, #X^{0}(𝔽_{q^{n}}). From these, deduce a p-adic precision l that suffices to determine these numbers exactly. Put, finally, a := ⌈l/(q − 1)⌉. iii) Define F ∈ ℤ_{q}[T_{1}, …, T_{N}] by putting F (T_{1}, …, T_{N}) := F̃(1, T_{1}, …, T_{N}). iv) Find matrix representations of the operators M_{F^{a(q−1)},1}, M_{F^{2a(q−1)},1}, …, M_{F^{la(q−1)},1}. Work on finite dimensional subspaces that are large enough to get the traces right. For a polynomial of total degree d, as a basis one may use all monomials of total degree ≤⌈d/(q −1)⌉.

v) For i := 1 to n, do the following. Calculate the matrix powers M_{F^{a(q−1)},1}^{i}, M_{F^{2a(q−1)},1}^{i}, …, M_{F^{la(q−1)},1}^{i} and eventually their traces tr M_{F^{ka(q−1)},1}^{i}. Then

#X^{0}(𝔽_{q^{i}}) ≡ (q^{i} − 1)^{N} [1 + ∑_{k=1}^{l}(−1)^{k}\binom{l}{k} tr M_{F^{ka(q−1)},1}^{i}] (mod p^{l}) .  (5)

Determine the exact value of #X^{0}(𝔽_{q^{i}}) from this congruence and the estimate established in step ii). Add #X^{c}(𝔽_{q^{i}}) and output the integer found.

Remarks 3.12. i) Formula (5) is essentially the same as the “trace formula” in [26, Theorem 3.1]. ii) (Cohomological interpretation) The matrix M_{F^{q−1},1} appears for the first time in [13, §2] and later in [33, Corollaries 1 and 2], where it is shown to be the natural generalisation of the classical Hasse-Witt matrix [27]. In other words, it represents the Frobenius homomorphism on the middle coherent cohomology H^{N−1}(X, 𝒪_{X}). The characteristic polynomial of M_{F^{q−1},1} is hence congruent modulo p to the Weil polynomial χ_{N−1} [11, Exp. XXII, Théorème 3.1]. Unfortunately, the algorithm above does not provide a canonical lift representing the crystalline Frobenius, but only successive p-adic approximations of the proper eigenvalues, so that (5) finally holds due to many cancellations.

4. A variation adapted to double covers

The variation.

Notation 4.1. i) We assume in this section that 𝔽_{q} is a finite field of characteristic p ≠ 2. ii) Furthermore, let X be a double cover of an affine torus 𝔾_{m,𝔽_{q}}^{N} , given by an equation of the form w^{2} = f for a polynomial f ∈ 𝔽_{q}[T_{1}, …, T_{N}]. Our interest stems from double covers of projective space of P_{𝔽_{q}}^{N} , but, as before, going over from projective space to an affine torus is not a serious modification. One may at the very end cover P_{𝔽_{q}}^{N} by affine tori. iii) We choose a lift F ∈ ℤ_{q}[T_{1}, …, T_{N}] of f. iv) For a positive integer l and k = 1, …, l, let us put

A_{k}^{(l)} := \frac{(2l)!}{2^{2l−1}l!(l − 1)!} · \frac{(−1)^{k+1}}{2k − 1} \binom{l − 1}{k − 1} .  (6)

Lemma 4.2. Let l > 0 and b be integers.

a) Then the Pascal-like matrix

P_{b}^{(l)} := ( \begin{matrix}1 & b & \binom{b}{2} & \binom{b}{3} & ⋯ & \binom{b}{l−1} \\ 1 & b + 2 & \binom{b+2}{2} & \binom{b+2}{3} & ⋯ & \binom{b+2}{l−1} \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & b+2l−4 & \binom{b+2l−4}{2} & \binom{b+2l−4}{3} & ⋯ & \binom{b+2l−4}{l−1} \\ 1 & b+2l−2 & \binom{b+2l−2}{2} & \binom{b+2l−2}{3} & ⋯ & \binom{b+2l−2}{l−1} \end{matrix} ) ∈ M_{l×l}(ℚ)  (7)

is invertible.

b) All coefficients of its inverse (P_{b}^{(l)})^{−1} are p-adic integers.

c) The first row of (P_{1}^{(l)})^{−1} is (A_{1}^{(l)}, A_{2}^{(l)}, …, A_{l}^{(l)}).

Proof. a) and b) Column transformations convert P_{b}^{(l)} essentially into a Vandermonde matrix. This shows det P_{b}^{(l)} = \frac{(2l−2)!!(2l−4)!!...2!!}{1!2!...(l−1)!} = 2^{(l−1)+(l−2)+···+1} = 2^{\binom{l}{2}} ≠ 0, which immediately implies a). Assertion b) follows from this together with Cramer’s rule.

c) The assertion is that the linear combination with coefficients (A_{1}^{(l)}, A_{2}^{(l)}, …, A_{l}^{(l)}) of the rows of the matrix P_{1}^{(l)} yields (1, 0, …, 0). Here, the occurrence of the zeroes is a consequence of the standard relation ∑_{k=1}^{l}(−1)^{k}\binom{l−1}{k−1}k^{e} = 0 among binomial coefficients, for e = 0, …, l − 2. It is a trivial, but tedious work to adjust the constant factor. □

Definition 4.3. We call a function Φ: μ_{q^{i}−1}^{N} → ℤ_{q} an Eulerian function for X(𝔽_{q^{i}}) modulo p^{l} if, for every (z_{1}, …, z_{N}) ∈ μ_{q^{i}−1}^{N},

Φ(z_{1}, …, z_{N}) ≡ 1 (mod p^{l}) if f(π(z_{1}), …, π(z_{N})) is a square in 𝔽_{q^{i}}^{∗} ,
Φ(z_{1}, …, z_{N}) ≡ −1 (mod p^{l}) if f(π(z_{1}), …, π(z_{N})) is a non-square in 𝔽_{q^{i}}^{∗} , and
Φ(z_{1}, …, z_{N}) ≡ 0 (mod p^{l}) if f(π(z_{1}), …, π(z_{N})) = 0 .

Theorem 4.4. Suppose that p is an odd prime and that b is odd such that b(q − 1)/2 ≥ l. Put A_{b,k}^{(l)} := ((P_{b}^{(l)})^{−1})_{1,k}. Then

Φ := ∑_{k=1}^{l} A_{b,k}^{(l)}·N_{ℤ_{q^{i}} /ℤ_{q}} F^{(b+2k−2)(q−1)/2}

is an Eulerian function for X(𝔽_{q^{i}}) modulo p^{l}.

Proof. Recall that each of the coefficients A_{b,1}^{(l)} := ((P_{b}^{(l)})^{−1})_{1,1}, …, A_{b,l}^{(l)} := ((P_{b}^{(l)})^{−1})_{1,l} is a p-adic integer. Furthermore, one has that f(π(z_{1}), …, π(z_{N})) = 0 ∈ 𝔽_{q^{i}} if and only if N_{𝔽_{q^{i}} /𝔽_{q}} (f(π(z_{1}), …, π(z_{N}))) = 0 ∈ 𝔽_{q}, which, in turn, is equivalent to N_{ℤ_{q^{i}} /ℤ_{q}} F (z_{1}, …, z_{N}) being a non unit in ℤ_{q}. If this is true then N_{ℤ_{q^{i}} /ℤ_{q}} F^{(b+2k−2)(q−1)/2}(z_{1}, …, z_{N}) is of p-adic valuation at least (b + 2k − 2)(q − 1)/2 ≥ b(q − 1)/2 ≥ l. Consequently,

∑_{k=1}^{l} A_{b,k}^{(l)}·N_{ℤ_{q^{i}} /ℤ_{q}} F^{(b+2k−2)(q−1)/2} ≡ 0 (mod p^{l}) .

Otherwise, f(π(z_{1}), …, π(z_{N})) ∈ (𝔽_{q^{i}}^{∗})^{2} precisely when N_{𝔽_{q^{i}} /𝔽_{q}} (f(π(z_{1}), …, π(z_{N}))) ∈ 𝔽_{q}^{∗} is a square. Then

N_{𝔽_{q^{i}} /𝔽_{q}} (f^{(q−1)/2}(π(z_{1}), …, π(z_{N}))) = 1 ∈ 𝔽_{q} ,

while the same expression is equal to (−1) in the case of a non-square. By construction, this means N_{ℤ_{q^{i}} /ℤ_{q}} F^{(q−1)/2}(z_{1}, …, z_{N}) ≡ ±1 (mod p), respectively.

Write N_{ℤ_{q^{i}} /ℤ_{q}} F^{(q−1)/2}(z_{1}, …, z_{N}) = ±(1 + sp) for some unknown s ∈ ℤ_{q^{i}}. This yields

N_{ℤ_{q^{i}} /ℤ_{q}} F^{3(q−1)/2}(z_{1}, …, z_{N}) = ±(1 + 3sp + 3s^{2}p^{2} + s^{3}p^{3}) ,
N_{ℤ_{q^{i}} /ℤ_{q}} F^{5(q−1)/2}(z_{1}, …, z_{N}) = ±(1 + 5sp + 10s^{2}p^{2} + 10s^{3}p^{3} + 5s^{4}p^{4} + s^{5}p^{5}) ,
⋮
N_{ℤ_{q^{i}} /ℤ_{q}} F^{(b+2l−2)(q−1)/2}(z_{1}, …, z_{N}) = ±(1 + (b+2l−2)sp + \binom{b+2l−2}{2}s^{2}p^{2} +

\binom{b+2l−2}{3}s^{3}p^{3} + ⋯ + \binom{b+2l−2}{l−1}s^{l−1}p^{l−1} + …) .

Lemma 4.2.a) and b) now show ∑_{k=1}^{l} A_{b,k}^{(l)}·N_{ℤ_{q^{i}} /ℤ_{q}} F^{(b+2k−2)(q−1)/2}(z_{1}, …, z_{N}) ≡ ±1 (mod p^{l}),

as required. □

Remark 4.5. According to the definition, if Φ is an Eulerian function for X(𝔽_{q^{i}}) modulo p^{l} then

#X(𝔽_{q^{i}}) ≡ (q^{i} − 1)^{N} + ∑_{(z_{1},...,z_{N})∈μ_{q^{i}−1}^{N}} Φ(z_{1}, …, z_{N}) (mod p^{l}) .  (8)

This leads to the algorithm below.

Algorithm 4.6. Given a polynomial f ∈ 𝔽_{q}[T_{0}, …, T_{N}] and a positive integer n, this algorithm computes the numbers of points #X(𝔽_{q}), #X(𝔽_{q^{2}}), …, #X(𝔽_{q^{n}}) on the double cover of P_{𝔽_{q}}^{N} , given by w^{2} = f.

i) Choose a lift F̃ ∈ ℤ_{q}[T_{0}, …, T_{N}] of f. Decompose P_{𝔽_{q}}^{N} into P^{c} := V (T_{0}) ∪ … ∪ V (T_{N}) and P^{0} := P_{𝔽_{q}}^{N} \P^{c}. Then P^{0} ≅ 𝔾_{m,𝔽_{q}}^{N} . For the restriction X^{c} of the double cover to the lower dimensional closed subscheme P^{c}, either use naive point counting methods or apply the method recursively. For X^{0}, the restriction to P^{0}, do the following. ii) Use elementary arguments or the Weil conjectures or both to find estimates for #X^{0}(𝔽_{q}), #X^{0}(𝔽_{q^{2}}), …, #X^{0}(𝔽_{q^{n}}). From these, deduce a p-adic precision l that suffices to determine these numbers exactly. Put, finally, b := ⌊2l/(q − 1)⌋.

iii) If b > 1 then determine the coefficient vector (A_{b,1}^{(l)}, …, A_{b,l}^{(l)}) by inverting the matrix P_{b}^{(l)} from (7). Otherwise, calculate first

C_{l} := \frac{(2l)!}{2^{2l−1}l!(l − 1)!}

and then the coefficients A_{k}^{(l)} :=C_{l}· \frac{(−1)^{k+1}}{2k−1} \binom{l−1}{k−1}. Finally, set (A_{1,1}^{(l)}, …, A_{1,l}^{(l)}):=(A_{1}^{(l)}, …, A_{l}^{(l)}). iv) Define F ∈ ℤ_{q}[T_{1}, …, T_{N}] by putting F (T_{1}, …, T_{N}) := F̃(1, T_{1}, …, T_{N}).

v) Find matrix representations of the operators M_{F^{(q−1)/2},1}, M_{F^{3(q−1/2)},1}, …, M_{F^{(b+2l−2)(q−1/2)},1}. Work on finite dimensional subspaces that are large enough to get the traces right. For a polynomial of total degree d, as a basis one may use all monomials of total degree ≤⌈d/(q −1)⌉. vi) For i := 1 to n, do the following. Calculate the matrix powers M_{F^{(q−1)/2},1}^{i}, M_{F^{3(q−1)/2},1}^{i}, …, M_{F^{(b+2l−2)(q−1)/2},1}^{i} and eventually their traces tr M_{F^{(b+2k−2)(q−1)/2},1}^{i}. Then

#X^{0}(𝔽_{q^{i}}) ≡ (q^{i} − 1)^{N} [1 + ∑_{k=1}^{l} A_{b,k}^{(l)}·tr M_{F^{(b+2k−2)(q−1)/2},1}^{i}] (mod p^{l}) .

Determine the exact value of #X^{0}(𝔽_{q^{i}}) from this congruence and the estimate established in step ii). Add #X^{c}(𝔽_{q^{i}}) and output the integer found.

Remarks 4.7. i) (Complexity.) The algorithm contains two time consuming operations. The first is the computation of the powers of F and the second is the multiplication of matrices. We tested our implementation in magma on one core of an Intel i5-4690 processor running at 3.5 GHz.

For a K3 surface of degree two, in order to compute the whole Weil polynomial, the algorithm has to work with a p-adic precision of at least 11 digits. For this, it has to compute F^{k(p−1)/2} for all odd integers 1 ≤ k ≤ 21. This results in matrices of size up to 2080×2080 having entries in ℤ/p^{11}ℤ. The table below lists the time used for a randomly chosen surface in a test modulo four representative primes of good reduction. The computation required about 13 GB of memory.

p powers of F matrix build matrix operations
31  12.65  21.05  55.36
61  76.91  21.63  71.00
97  236.92  22.30  73.53
127  489.92  22.36  73.97

Table 1. Time (in s) for the steps of the algorithm

The figures show that the time for the computation of the powers of F is approximately cubic in p. This is explained by the fact that the number of terms of the final result is quadratic in p, while the number of multiplications necessary to approach it is linear in p. The time for the matrix operations is almost constant as the size of the matrices is constant. The variation of the time is explained completely by the change of the ring the matrix entries are taken from. In theory, there exists an algorithm that is quadratic in p. This is, however, not yet implemented in magma and, reportedly, it is not easy to implement. ii) We incorporated the variable b only for completeness. In practice, the algorithm is of interest particularly when q is not very small. Then q − 1 ≥ 2l and b = 1. The same applies to the variable a in Algorithm 3.11. iii) One might as well determine the coefficient vector (A_{b,1}^{(l)}, …, A_{b,l}^{(l)}) by a matrix inversion, also when b = 1. This step is in fact not time-critical. Nevertheless, we find it interesting that it is possible to give an explicit formula.

Remark 4.8 (The moving simplex idea). The idea behind most of the operator calculus above is that only very few of the coefficients of the powers of F are actually needed. An extreme case is the following. Assume that a K3 surface X is given as a double cover of P_{ℚ}^{2} , by the equation W^{2} = F (T_{0}, T_{1}, T_{2}) for F a homogeneous polynomial of degree 6. Moreover, one only wants to decide for which primes p up to a certain bound B the reduction X_{p} is ordinary. This means that only (#X_{p}(𝔽_{p}) mod p) is asked for. Thus, for each prime, just a single coefficient is to be computed, that of F^{\frac{p−1}{2}} at T_{0}^{p−1}T_{1}^{p−1}T_{2}^{p−1}.

This might be done as follows. Consider just a small triangle of coefficients of F^{e}, those at T_{0}^{a_{0}}T_{1}^{a_{1}}T_{2}^{a_{2}} such that |a_{i} − \frac{a_{0}+a_{1}+a_{2}}{3} | ≤ c_{i} for i = 0, 1, 2 and some constants c_{0}, c_{1}, and c_{2}. These triangles may be calculated inductively for e = 1, …, (B − 1)/2. For F homogeneous of degree d, any choice such that c_{0} + c_{1} + c_{2} := 2(d − 1) should work.

Indeed, F is given and therefore \frac{dF}{dT_{0}} , \frac{dF}{dT_{1}} , and \frac{dF}{dT_{2}} are known. When the triangle for F^{e} has been established, computing F^{e+1} naively one would lose some of the coefficients. But the coefficients of F^{e+1} have massive linear relations. A single coefficient of F^{e+1} appears as a linear combination of the coefficients of F^{e}, when evaluating the formula F^{e+1} = F ·F^{e}. It appears as well in \frac{dF^{e+1}}{dT_{0}} =(e + 1)F^{e} \frac{dF}{dT_{0}} and the analogous formulae involving T_{1} and T_{2}. Hence, each hypothetical coefficient yields three linear relations. One may thus reconstruct some neighbouring coefficients using the linear relations and therefore keep the size of the triangle constant under iteration. This approach stems from [26, §4.1] and is implemented in

the function NonOrdinaryPrimes.

On the other hand, WeilPolynomialOfDegree2K3Surface does not use the moving simplex idea, but the approach described above in this section. The point is that, for example for p = 127, one has to compute F^{63·21}, which results in a sum of 31 517 830 terms. Thereby, from the coefficients, about 14% are used as matrix entries. Thus, computing only the used coefficients of the powers of F would speed up the algorithm only for considerably larger values of p. Remark 4.9. There are improvements to the moving simplex idea, which we did not implement. The point is that instead of keeping track of the coefficients of F^{e} on the entire simplex, one may sometimes, and probably often, get by with working only on a relatively small subset. For example, the idea has been worked out for smooth space quartics, in which case 64 coefficients suffice out of the 220, one would naively have. This is called the controlled reduction Abbott–Kedlaya–Roe algorithm [1, Algorithm 3.4.10]. Cf. [7].

5. Families of K3 surfaces that are highly likely to have real or complex multiplication

5.1. Based on the Mumford-Tate conjecture, which was proven for K3 surfaces by S. G. Tankeev [37, 38], we established in [20] certain arithmetic consequences of real or complex multiplication for K3 surfaces defined over ℚ. Assume for simplicity that the endomorphism field E is a quadratic number field. Then these consequences include the following.

i) If p is inert in E then #X_{p}(𝔽_{p}) ≡ 1 (mod p). I.e. X_{p} is non-ordinary. ii) For every prime p of good reduction, the transcendental factor χ_{p}^{tr} of the Weil polynomial of X_{p} either splits over E into two factors conjugate to each other or becomes a square under raising all its roots to the f-th power, for some f > 0. During the last few years, we systematically searched for K3 surfaces, the reductions of which show such an unusually regular behaviour. So far, we have the following conjectural list of suspicious surfaces.

Conjectures 5.2. Consider the following K3 surfaces and families of such,

V_{a}^{(2)} : W^{2} = [(\frac{1}{8}a^{2}− \frac{1}{2}a+ \frac{1}{4})T_{1}^{2} + (a^{2}−2a+2)T_{1}T_{2} + (a^{2}−4a+2)T_{2}^{2}]

[(\frac{1}{8}a^{2}+ \frac{1}{2}a+ \frac{1}{4})T_{0}^{2} + (a^{2}+2a+2)T_{0}T_{2} + (a^{2}+4a+2)T_{2}^{2}][2T_{0}^{2} + (a^{2}+2)T_{0}T_{1} + a^{2}T_{1}^{2}],

V_{a}^{(5)} : W^{2} = [T_{1}^{2} + aT_{1}T_{2} + (\frac{5}{16}a^{2}+ \frac{5}{4}a+ \frac{5}{4})T_{2}^{2}][T_{0}^{2} + T_{0}T_{2} + (\frac{1}{320}a^{2}+ \frac{1}{16}a+ \frac{5}{16})T_{2}^{2}]

[T_{0}^{2} + T_{0}T_{1} + \frac{1}{20}T_{1}^{2}],

V^{(13)} : W^{2} = (25T_{1}^{2} + 26T_{1}T_{2} + 13T_{2}^{2})(T_{0}^{2} + 2T_{0}T_{2} + 13T_{2}^{2})(9T_{0}^{2} + 26T_{0}T_{1} + 13T_{1}^{2}) ,
V_{a,b}^{(2)} : W^{2} = T_{0}T_{1}T_{2}f_{a,b} for

f_{a,b}:= a(−T_{0}^{2}T_{1}+T_{0}^{2}T_{2}+2T_{0}T_{1}^{2}−3T_{0}T_{1}T_{2}+T_{0}T_{2}^{2}+T_{1}^{3}−4T_{1}^{2}T_{2}+5T_{1}T_{2}^{2}−2T_{2}^{3})

+ b(T_{0}^{3} − 2T_{0}^{2}T_{1} − T_{0}T_{1}^{2} + 3T_{0}T_{1}T_{2} − T_{0}T_{2}^{2} + T_{1}^{2}T_{2} − T_{1}T_{2}^{2}) ,
V_{a,b}^{(3)} : W^{2} = T_{0}T_{1}T_{2}f_{a,b} for
f_{a,b} := (T_{0}^{3} − 2T_{0}^{2}T_{2} − T_{0}T_{1}^{2} − T_{0}T_{2}^{2} − 2T_{1}^{2}T_{2} + 2T_{2}^{3})a^{2}
+ (6T_{0}^{2}T_{1} + 6T_{0}^{2}T_{2} + 6T_{0}T_{1}^{2} + 6T_{1}^{2}T_{2} − 6T_{2}^{3})ab
+ (−3T_{0}^{2}T_{1} − 6T_{0}^{2}T_{2} + 3T_{1}^{3} − 6T_{1}^{2}T_{2} − 3T_{1}T_{2}^{2} + 6T_{2}^{3})b^{2},
V_{a,b}^{(−1)} : W^{2} = T_{0}T_{1}T_{2}(T_{0} + T_{1} + T_{2})(a_{1}T_{0} + a_{2}T_{1} + a_{3}T_{2})(b_{1}T_{0} + b_{2}T_{1} + b_{3}T_{2})

for a, b ∈ ℂ^{3} such that a_{1}b_{3}+a_{2}b_{1}−2a_{3}b_{1} = 0 and a_{1}b_{2}+a_{2}b_{3}−2a_{3}b_{2} = 0 .

V^{(−1,μ_{7})} : W^{2} = T_{0}T_{1}T_{2}(7T_{0}^{3} − 7T_{0}^{2}T_{1} + 49T_{0}^{2}T_{2} − 21T_{0}T_{1}T_{2} + 98T_{0}T_{2}^{2} + T_{1}^{3} − 7T_{1}^{2}T_{2}+49T_{2}^{3}) ,
V^{(−1,μ_{9})} : W^{2} = T_{0}T_{1}T_{2}(T_{0}^{3} − 3T_{0}^{2}T_{2} − 3T_{0}T_{1}^{2} − 3T_{0}T_{1}T_{2} + T_{1}^{3} + 9T_{1}^{2}T_{2} + 6T_{1}T_{2}^{2} + T_{2}^{3}) ,
V^{(−1,μ_{19})} : W^{2} = T_{0}T_{1}T_{2}(49T_{0}^{3} − 304T_{0}^{2}T_{1} + 570T_{0}^{2}T_{2} + 361T_{0}T_{1}^{2} − 2793T_{0}T_{1}T_{2} + 2033T_{0}T_{2}^{2}

+ 361T_{1}^{3} + 2888T_{1}^{2}T_{2} − 5415T_{1}T_{2}^{2} + 2299T_{2}^{3}) . a) Then the generic fibre of each family, as well as each of the four individual surfaces has geometric Picard rank 16.

b) Moreover, the generic fibre of V_{a}^{(2)} has real multiplication by ℚ(\sqrt{2}), that of V_{a}^{(5)} RM by ℚ(\sqrt{5}), that of V_{a,b}^{(2)} RM by ℚ(\sqrt{2}), that of V_{a,b}^{(3)} RM by ℚ(\sqrt{3}), and that of V_{a,b}^{(−1)} complex multiplication by ℚ(\sqrt{−1}). Finally, V^{(13)} has RM by ℚ(\sqrt{13}), V^{(−1,μ_{7})} CM by ℚ(ζ_{28} + ζ_{28}^{13}) = ℚ(i, ζ_{7} + ζ_{7}^{−1}), V^{(−1,μ_{9})} CM by ℚ(ζ_{36} + ζ_{36}^{17}) = ℚ(i, ζ_{9} + ζ_{9}^{−1}), and V^{(−1,μ_{19})} CM by L(i), for L ⊂ ℚ(μ_{19}) the unique cubic subfield.

Remarks 5.3. i) The equations given actually describe singular models of the K3 surfaces to be considered. ii) (Evidence.) Thanks to Harvey’s p-adic point counting method, we can now give a lot more numerical evidence for our conjectures than before [20]. iii) (Proven cases.) The first three examples were already published in [20]. For the family V_{a}^{(2)}, both a) and b) were proven in [20, Theorem 6.6]. The same method applies to V_{a,b}^{(−1)} and provides a proof also for this family. As far as only a) is concerned, using van Luijk’s method one shows in each case that the geometric Picard rank is 16 or 17, and 16 as soon as b) is true. iv) In particular, for each family or surface, we explicitly know 16 divisors that are linearly independent in the Picard group. In neither case, all of them are defined over ℚ. For instance, for V^{(−1,μ_{7})}, V^{(−1,μ_{9})}, and V^{(−1,μ_{19})}, the fields of definition are ℚ(ζ_{7} + ζ_{7}^{−1}), ℚ(ζ_{9} + ζ_{9}^{−1}), and the unique cubic subfield of ℚ(μ_{19}), respectively. On the other hand, for V_{a}^{(2)}, the field of definition of the known divisors is ℚ(\sqrt{2}), while it is ℚ(\sqrt{5}, \sqrt{a^{2} − 20a − 20}) for V_{a}^{(5)}, ℚ(\sqrt{13}, \sqrt{−3}) for V^{(13)}, ℚ(\sqrt{2}, \sqrt{a}, \sqrt{b}, \sqrt{a^{2} − 6ab + b^{2}}) for V_{a,b}^{(2)} and ℚ(\sqrt{3}, \sqrt{a^{4} − 12a^{3}b + 30a^{2}b^{2} − 36ab^{3} + 9b^{4}}, \sqrt{2a^{2} − 6ab + 6b^{2}}) for V_{a,b}^{(3)}. We do not know whether the following is more than a coincidence.

Experimental observation 5.4. All the examples listed in Conjectures 5.2 that are supposed to have real multiplication have the property that the endomorphism field is contained in the field of definition of the Picard group.

Numerical evidence. Data for the real multiplication examples.

For each prime p ∈ {19, …, 499}, we inspected all the possible specialisations of the families after reduction modulo p. Whenever this resulted in a non-singular surface, we computed the Weil polynomial and derived the geometric Picard rank. This confirmed properties 5.1.i) and ii) in every case. In particular, only the Picard ranks 18 and 22 are occurring. There is the following statistics.

Family  # relative frequency (in %) of rank 22 per prime
inert primes  split primes
min average max  min average max
V_{a}^{(2)}  0.00 7.42 25.00  0.00 6.14 25.00
V_{a}^{(5)}  2.33 9.32 24.24  0.00 5.84 16.00
V_{a,b}^{(2)}  4.75 12.66 38.89  1.50 7.39 22.73
V_{a,b}^{(3)}  0.00 0.00 0.000  2.33 7.40 20.59

Table 2. Frequency of reduction to geometric Picard rank 22

One might want to look more closely at the primes that result in reduction to geometric Picard rank 22. In the case of the family V_{a}^{(2)}, 77 of 88 primes are occurring. The missing ones are 23, 29, 31, 47, 97, 127, 193, 241, 401, 433, and 449. The reductions of these primes modulo 8 are 1^{6}, 5, 7^{4}. The only one being inert in the endomorphism field ℚ(\sqrt{2}) is 29. For the family V_{a,b}^{(2)}, all 88 inspected primes do occur, while for V_{a}^{(5)} 87 of the 88 primes occur and only 29 is missing. However, in the example V_{a,b}^{(3)}, only 44 of the 88 primes result in reductions to rank 22 and in fact exactly those splitting in the endomorphism field ℚ(\sqrt{3}), a phenomenon we have no explanation for.

Primes of reduction to rank 18. In the case of reduction to Picard rank 18, the transcendental factor split off the Weil polynomial is of degree four. In our families, it was never a perfect power, cf. [42, Theorem 1.1], but always turned out to be irreducible. It was either the norm of a quadratic polynomial g ∈ E[t] over the endomorphism field or turned into a square under the operation of squaring all its roots. The first alternative occurred precisely at the primes split in E, while the second option came up at the inert primes.

Numerical evidence. Data for the complex multiplication examples.

Let us report only on the numerical evidence for the three isolated examples. These are contained in the family V_{a,b}^{(−1)}. Thus, at least CM by ℚ(\sqrt{−1}) is proven. As the surfaces have geometric Picard rank 16, the transcendental part of the cohomology is of relative dimension one. Thus, one should expect phenomena that are very close to those known to occur for elliptic curves with complex multiplication.

To verify this, we run the point counting for all the primes below 1000. It turns out that all the reductions have geometric Picard rank either 16 or 22, where rank 16 appears exactly for the primes 1 mod 4. A prime is ordinary if and only if it completely splits in the endomorphism field. Furthermore, the Frobenius eigenvalues on the transcendental part of H_{ét}^{2}(V_{\overline{𝔽}_{p}}, ℚ_{l}) are closely related to the endomorphism field E. More precisely,

a) In the case that p completely splits in E, the eigenvalues of Frob are contained in E. They are of the form ±p\frac{\overline{π}}{π} for (π) a prime above p. Note that the endomorphism fields have class number 1, such that the ideals above p are principal.

b) In the case that p splits into three primes, the characteristic polynomial of Frob on the transcendental lattice is t^{6} − 3p^{2}t^{4} + 3p^{4}t^{2} − p^{6} = (t^{2} − p^{2})^{3}.

c) In the case that p splits into two primes, the characteristic polynomial of Frob on the transcendental lattice is of the form t^{6} + ap^{2}t^{3} + p^{6}, for a ∈ ℤ having the property that the discriminant of t^{2} + at + p^{2} is minus a square. Thus, the Weil polynomial of X_{𝔽_{p^{3}}} is a cube of a quadratic polynomial having its roots in ℚ(i). These are of the form p^{2}ϱ^{2}, for ϱ ∈ ℚ(i) a prime above p. Let us note here once again that ℚ(i) ⊂ E.

d) In the case that p is totally inert, the degree six transcendental factor of the Weil polynomial is equal to t^{6} − p^{6}. The total computation took about 110 days of CPU-time on one Intel Xeon E5-4650 processor running at 2.7 GHz.

References

[1] Abbott, T. G., Kedlaya, K. S., and Roe, D.: Bounding Picard numbers of surfaces using p-adic cohomology, in: Arithmetics, geometry, and coding theory (AGCT 2005), Séminaires et Congrès 21, Soc. Math. France, Paris 2010, 125–159

[2] Artin, E.: Quadratische Körper im Gebiete der höheren Kongruenzen II, Math. Z. 19 (1924), 207–246 [3] Borevich, Z. I. and Shafarevich, I. R.: Number theory, Academic Press, New York-London 1966

[4] Bosma, W., Cannon, J., and Playoust, C.: The Magma algebra system I. The user language, J. Symbolic Comput. 24 (1997), 235–265

[5] Charles, F.: On the Picard number of K3 surfaces over number fields, Algebra Number Theory 8 (2014), 1–17

[6] Cormen, T., Leiserson, C., and Rivest, R.: Introduction to algorithms, MIT Press and McGraw-Hill, Cambridge and New York 1990

[7] Costa, E.: Effective computations of Hasse–Weil zeta functions, Ph.D. Thesis, New York University, New York 2015 [8] Deligne, P.: La conjecture de Weil I, Publ. Math. IHES 43 (1974), 273–307

[9] Deligne, P. (avec la collaboration de Boutot, J. F., Grothendieck, A., Illusie, L. et Verdier, J.-L.): Cohomologie Étale, Séminaire de Géométrie Algébrique du Bois Marie (SGA4 \frac{1}{2} ), Lecture Notes in Math. 569, Springer, Berlin, Heidelberg, New York 1977

[10] Deligne, P.: La conjecture de Weil II, Publ. Math. IHES 52 (1980), 137–252

[11] Deligne, P. et Katz, N.: Groupes de Monodromie en Géométrie Algébrique, Séminaire de Géométrie Algébrique du Bois Marie 1967–1969 (SGA 7), Lecture Notes in Math. 288, 340, Springer, Berlin, Heidelberg, New York 1973

[12] Diagana, T.: Non-Archimedean linear operators and applications, Nova Science Publishers, Huntington 2007

[13] Dwork, B. M.: On the congruence properties of the zeta function of algebraic varieties, J. Reine Angew. Math. 203 (1960), 130–142

[14] Dwork, B. M.: On the rationality of the zeta function of an algebraic variety, Amer. J. Math. 82 (1960), 631–648

[15] Elkies, N. and Kumar, A.: K3 surfaces and equations for Hilbert modular surfaces, Algebra & Number Theory 8 (2014), 2297–2411

[16] Elsenhans, A.-S. and Jahnel, J.: K3 surfaces of Picard rank one and degree two, in: Algorithmic number theory (ANTS 8), Lecture Notes in Computer Science 5011, Springer, Berlin 2008, 212–225

[17] Elsenhans, A.-S. and Jahnel, J.: On Weil polynomials of K3 surfaces, in: Algorithmic number theory (ANTS 9), Lecture Notes in Computer Science 6197, Springer, Berlin 2010, 126–141

[18] Elsenhans, A.-S. and Jahnel, J.: The Picard group of a K3 surface and its reduction modulo p, Algebra & Number Theory 5 (2011), 1027–1040

[19] Elsenhans, A.-S. and Jahnel, J.: Kummer surfaces and the computation of the Picard group, LMS Journal of Computation and Mathematics 15 (2012), 84–100

[20] Elsenhans, A.-S. and Jahnel, J.: Examples of K3 surfaces with real multiplication, in: Proceedings of ANTS 11, LMS Journal of Computation and Mathematics 17 (2014), 14–35

[21] Elsenhans, A.-S. and Jahnel, J.: On the characteristic polynomial of the Frobenius on étale cohomology, Duke Mathematical Journal 164 (2015), 2161–2184

[22] Forster, O.: Algorithmische Zahlentheorie, Vieweg, Braunschweig 1996

[23] van Geemen, B.: Real multiplication on K3 surfaces and Kuga-Satake varieties, Michigan Math. J. 56 (2008), 375–399

[24] Grothendieck, A. (avec la collaboration de Bucur, I., Houzel, C., Illusie, L. et Serre, J.-P.): Cohomologie l-adique et Fonctions L, Séminaire de Géométrie Algébrique du Bois Marie 1965–1966 (SGA 5), Lecture Notes in Math. 589, Springer, Berlin, Heidelberg, New York 1977

[25] Hartshorne, R.: Algebraic Geometry, Graduate Texts in Math. 52, Springer, New York, Heidelberg, Berlin 1977

[26] Harvey, D.: Computing zeta functions of arithmetic schemes, Proc. Lond. Math. Soc. 111 (2015), 1379–1401 [27] Hasse, H. and Witt, E.: Zyklische unverzweigte Erweiterungskörper vom Primzahlgrade p über einem

algebraischen Funktionenkörper der Charakteristik p, Monatsh. Math. Phys. 43 (1936), 477-492

[28] Kedlaya, K.: Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, Journal of the Ramanujan Mathematical Society 16 (2001), 323–338

[29] Lauder, A. G. B.: A recursive method for computing zeta functions of varieties, LMS J. Comput. Math. 9 (2006), 222–269

[30] Lauder, A. G. B. and Wan, D.: Counting points on varieties over finite fields of small characteristic, in: Algorithmic number theory: lattices, number fields, curves and cryptography, MSRI Publ. 44, Cambridge Univ. Press, Cambridge 2008, 579–612

[31] van Luijk, R.: Rational points on K3 surfaces, Ph.D. thesis, Berkeley 2005

[32] van Luijk, R.: K3 surfaces with Picard number one and infinitely many rational points, Algebra & Number Theory 1 (2007), 1–15

[33] Miller, L.: The Hasse-Witt-matrix of special projective varieties, Pacific J. Math. 43 (1972), 443–455 [34] Pancratz, S. and Tuitman, J.: Improvements to the deformation method for counting points on smooth

projective hypersurfaces, Found. Comput. Math. 15 (2015), 1413–1464

[35] Satoh, T.: The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), 247–270

[36] Schoof, R.: Counting points on elliptic curves over finite fields, in: Les Dix-huitièmes Journées Arithmétiques (Bordeaux 1993) J. Theor. Nombres Bordeaux 7 (1995), 219–254

[37] Tankeev, S. G.: Surfaces of K3 type over number fields and the Mumford-Tate conjecture (Russian), Izv. Akad. Nauk SSSR Ser. Mat. 54 (1990), 846–861

[38] Tankeev, S. G.: Surfaces of K3 type over number fields and the Mumford-Tate conjecture II (Russian), Izv. Ross. Akad. Nauk Ser. Mat. 59 (1995), 179–206 [39] Wan, D.: Computing zeta functions over finite fields, in: Finite fields: theory, applications, and algorithms

(Waterloo 1997), Contemp. Math. 225, Amer. Math. Soc. Providence 1999, 131–141

[40] Wan, D.: Algorithmic theory of zeta functions over finite fields, in: Algorithmic number theory: lattices, number fields, curves and cryptography, MSRI Publ. 44, Cambridge Univ. Press, Cambridge 2008, 551–578

[41] Zarhin, Yu. G.: Hodge groups of K3 surfaces, J. Reine Angew. Math. 341 (1983), 193–220

[42] Zarhin, Yu. G.: Transcendental cycles on ordinary K3 surfaces over finite fields, Duke Math. J. 72 (1993), 65–83

Institut für Mathematik, Warburger Straße 100, D-33098 Paderborn, Germany

E-mail address: Stephan.Elsenhans@math.upb.de
URL: http://www.staff.uni-bayreuth.de/~bt270951/

Department Mathematik, Univ. Siegen, Walter-Flex-Str. 3, D-57068 Siegen, Germany

E-mail address: ~jjahnel@mathematik.uni-siegen.de
URL: http://wwwuser.gwdg.de/~jjahnel