Introduction
The Four Methods

Introduction
The Four Methods

Quasi-diagonal Hypersurfaces I
Point Counting on Quasi-DiagonalHypersurfaces
Henri Cohen(Talk given by Atsuko Miyaji)

ECC, Osaka, November 2018

LFANT INRIA, IMB, Université de Bordeaux

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Let Fq be a finite field with q = pf elements for some prime p. A
quasi-diagonal hypersurface V in Pm−1 is a variety given by aprojective equation
YX
ai xim − b
xi = 0 ,1≤i≤mwith ai ∈ F∗q and b ∈ Fq (note: the number of variables is equal

to the degree). We want to compute |V (Fq )|, its number of(projective) points over Fq .

Important tool: we denote by ω a generator of the group ofcharacters of F∗q (with values in some algebraically closed
field): recall that F∗q is a cyclic group, so ω exists and can be
defined by ω(g) = ζq−1 for g a generator of F∗q and ζq−1 aprimitive (q − 1)-th root of unity.
Henri Cohen (Talk given by Atsuko Miyaji)

1≤i≤m

1≤i≤m

with ai ∈ F∗q and b ∈ Fq (note: the number of variables is equal
to the degree). We want to compute |V (Fq )|, its number of(projective) points over Fq .
Important tool: we denote by ω a generator of the group ofcharacters of F∗q (with values in some algebraically closed
field): recall that F∗q is a cyclic group, so ω exists and can be
defined by ω(g) = ζq−1 for g a generator of F∗q and ζq−1 aprimitive (q − 1)-th root of unity.
Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Quasi-diagonal Hypersurfaces I

1≤i≤m

Let Fq be a finite field with q = pf elements for some prime p. A
quasi-diagonal hypersurface V in Pm−1 is a variety given by aprojective equation
YX
ai xim − b
xi = 0 ,Point Counting on Quasi-Diagonal Hypersurfaces

Quasi-diagonal Hypersurfaces II
ThenQtheorem: if gcd(m, q − 1) = 1 and b 6= 0, set
B = 1≤i≤m (ai /b). We have|V (Fq )| = (A(Fq ) − 1)/(q − 1) with
A(Fq ) = (−1)m−1 +Xω −n (B)Jm (ω n , . . . , ω n ) ,0≤n≤q−2

Jm is an m-variable Jacobi sum defined as follows:
Jm (χ1 , . . . , χm ) =X

x1 +···+xm =1

χ1 (x1 ) · · · χm (xm )for characters χi of F∗q . The proof is not difficult.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

Quasi-diagonal Hypersurfaces II
ThenQtheorem: if gcd(m, q − 1) = 1 and b 6= 0, set
B = 1≤i≤m (ai /b). We have|V (Fq )| = (A(Fq ) − 1)/(q − 1) with
A(Fq ) = (−1)m−1 +X

Thus, we need preliminaries on Gauss and Jacobi sums. Let χ
be a character of F∗q . The Gauss sum is defined byX
g(χ) =
χ(x) exp(2πi TrFq /Fp (x)/p)x∈F∗qω −n (B)Jm (ω n , . . . , ω n ) ,0≤n≤q−2

Jm is an m-variable Jacobi sum defined as follows:
Jm (χ1 , . . . , χm ) =Gauss and Jacobi Sums I

X

x1 +···+xm =1

χ1 (x1 ) · · · χm (xm )(TrFq /Fp denotes the trace from Fq to Fp ). If χ is the trivial
character ε, we have g(χ) = −1, otherwise it is easy to provethat |g(χ)| = q 1/2 .
Q
Gauss–Jacobi sum relation: if χi 6= ε for all i and i χi 6= ε, thenJm (χ1 , . . . , χm ) =for characters χi of F∗q . The proof is not difficult.

g(χ1 ) · · · g(χm ).
g(χ1 · · · χm )Q
If some χi = ε or i χi = ε, there are other, simpler, formulas,for instance, Jm (ε, . . . , ε) = q m−1 .
Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Henri Cohen (Talk given by Atsuko Miyaji)

Introduction
The Four Methods

Introduction
The Four Methods

Gauss and Jacobi Sums I

Gauss and Jacobi Sums II

Thus, we need preliminaries on Gauss and Jacobi sums. Let χ
be a character of F∗q . The Gauss sum is defined byX
g(χ) =
χ(x) exp(2πi TrFq /Fp (x)/p)x∈F∗q(TrFq /Fp denotes the trace from Fq to Fp ). If χ is the trivial
character ε, we have g(χ) = −1, otherwise it is easy to provethat |g(χ)| = q 1/2 .
Q
Gauss–Jacobi sum relation: if χi 6= ε for all i and i χi 6= ε, thenJm (χ1 , . . . , χm ) =g(χ1 ) · · · g(χm ).
g(χ1 · · · χm )Q

If some χi = ε or i χi = ε, there are other, simpler, formulas,for instance, Jm (ε, . . . , ε) = q m−1 .
Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Point Counting on Quasi-Diagonal Hypersurfaces

So if everything is different from the trivial character ε, we havean immediate recursion
Jm (χ1 , . . . , χm ) = Jm−1 (χ1 , . . . , χm−1 )J2 (ψ, χm )with ψ = χ1 · · · χm−1 (and even simpler recursions if some χi orψ is equal to ε).
Naive computation of Jm requires summing over (x1 , . . . , xm )such that x1 + · · · + xm = 1, so q m−1 operations.
Use of the recursion requires (m − 1) times computation of J2 ,hence essentially (m − 1)q operations, so much faster.
We writeJ(χ1 , χ2 ) := J2 (χ1 , χ2 ) =Xx∈Fq
Henri Cohen (Talk given by Atsuko Miyaji)

χ1 (x)χ2 (1 − x) .

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

Gauss and Jacobi Sums II

Gauss and Jacobi Sums II

So if everything is different from the trivial character ε, we havean immediate recursion

So if everything is different from the trivial character ε, we havean immediate recursion

Jm (χ1 , . . . , χm ) = Jm−1 (χ1 , . . . , χm−1 )J2 (ψ, χm )Jm (χ1 , . . . , χm ) = Jm−1 (χ1 , . . . , χm−1 )J2 (ψ, χm )with ψ = χ1 · · · χm−1 (and even simpler recursions if some χi orψ is equal to ε).

with ψ = χ1 · · · χm−1 (and even simpler recursions if some χi orψ is equal to ε).

Naive computation of Jm requires summing over (x1 , . . . , xm )such that x1 + · · · + xm = 1, so q m−1 operations.
Use of the recursion requires (m − 1) times computation of J2 ,hence essentially (m − 1)q operations, so much faster.

Naive computation of Jm requires summing over (x1 , . . . , xm )such that x1 + · · · + xm = 1, so q m−1 operations.
Use of the recursion requires (m − 1) times computation of J2 ,hence essentially (m − 1)q operations, so much faster.

We write

We writeJ(χ1 , χ2 ) := J2 (χ1 , χ2 ) =Xx∈Fq
Henri Cohen (Talk given by Atsuko Miyaji)

χ1 (x)χ2 (1 − x) .

Point Counting on Quasi-Diagonal Hypersurfaces

J(χ1 , χ2 ) := J2 (χ1 , χ2 ) =Xx∈Fq
Henri Cohen (Talk given by Atsuko Miyaji)

Introduction
The Four Methodsχ1 (x)χ2 (1 − x) .

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

A Complete Example I

A Complete Example I

Recall that ω is a generator of the group of characters of F∗q .
We write for simplicity

Recall that ω is a generator of the group of characters of F∗q .
We write for simplicity

Jm (n1 , . . . , nm ) := Jm (ω n1 , . . . , ω nm )Jm (n1 , . . . , nm ) := Jm (ω n1 , . . . , ω nm )(since any character is a power of ω, this is the general Jacobi
sum).

(since any character is a power of ω, this is the general Jacobisum).

We consider the quasi-diagonal
hypersurface
Q V as above, i.e.
Pwith projective equation 1≤i≤m ai xim − b 1≤i≤m xi = 0. By theabove theorem, if gcd(m, q − 1) = 1 and b 6= 0, the number ofprojective points V (Fq ) is equal to (A(Fq ) − 1)/(q − 1), whereY
A(Fq ) = (−1)m−1 + S(q; B) with B =(ai /b) andWe consider the quasi-diagonal
hypersurface
Q V as above, i.e.
Pwith projective equation 1≤i≤m ai xim − b 1≤i≤m xi = 0. By theabove theorem, if gcd(m, q − 1) = 1 and b 6= 0, the number ofprojective points V (Fq ) is equal to (A(Fq ) − 1)/(q − 1), whereY
A(Fq ) = (−1)m−1 + S(q; B) with B =(ai /b) and1≤i≤mS(q; B) =

X

ω

−n

(B)Jm (n, . . . , n) .

0≤n≤q−2
Henri Cohen (Talk given by Atsuko Miyaji)

1≤i≤mS(q; B) =

X

ω

−n

(B)Jm (n, . . . , n) .

0≤n≤q−2
Point Counting on Quasi-Diagonal Hypersurfaces

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

A Complete Example II

The Direct Method

We choose the reasonably nontrivial example m = 5, and wewill study several methods for computing
X
S(q; B) =ω −n (B)J5 (n, n, n, n, n) :0≤n≤q−2

A direct method using the definition of J(n, n).
Using the fact that all the character values are in thecyclotomic ring Z[ζq−1 ], and in fact in the ring with zero
divisors R = Z[X ]/(X q−1 − 1), we can work with simple
polynomials.
3
Using theta functions.
4
Using Morita’s p-adic gamma function and theGross–Koblitz formula.
This last method is the most sophisticated, but by far the best,
so I will spend some time describing it in detail.
1
2

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

In this method we compute each J5 (n, n, n, n, n) independently.
Recall that generically (in this case, exactly when (q − 1) ∤ 5n)
we have J5 (n, n, n, n, n) = J(n, n)J(2n, n)J(3n, n)J(4n, n),which thus require approximately 4q operations, so essentially
4q 2 to compute S(q; B). No need to give the exact formula
since this is the slowest method.
Sample timings (all timings given in this talk are with a standardIntel 2.4 Ghz Core i7 processor using the Pari/GP library): for qof the order of 10k with k = 2, 3, 4, requires 0.03, 1.46, 149
seconds respectively, compatible with O(q 2 ) time. Prohibitive.

Henri Cohen (Talk given by Atsuko Miyaji)

Introduction
The Four Methods

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

The Direct Method

Working with Polynomials I

In this method we compute each J5 (n, n, n, n, n) independently.
Recall that generically (in this case, exactly when (q − 1) ∤ 5n)
we have J5 (n, n, n, n, n) = J(n, n)J(2n, n)J(3n, n)J(4n, n),which thus require approximately 4q operations, so essentially
4q 2 to compute S(q; B). No need to give the exact formula
since this is the slowest method.
Sample timings (all timings given in this talk are with a standardIntel 2.4 Ghz Core i7 processor using the Pari/GP library): for qof the order of 10k with k = 2, 3, 4, requires 0.03, 1.46, 149
seconds respectively, compatible with O(q 2 ) time. Prohibitive.

Recall that ω(x) ∈ Z[ζq−1 ], where ζq−1 is a primitive (q − 1)-throot of unity, so all operations can be done in this ring. However,slightly expensive. More efficient: work in R = Z[X ]/(X q−1 − 1),with the natural surjective map from R to Z[ζq−1 ] given by
X 7→ ζq−1 . The ring R has zero divisors, but no problem.

Let g be the unique generator of F∗q such that ω(g) = ζq−1 .
Generically, we haveJ(n, an) =Xω n (g u )ω an (1−g u ) =1≤u≤q−2

Xnu+na logg (1−g u )ζq−1

1≤u≤q−2

where logg is the discrete logarithm (g logg (x) = x) modulo q − 1.
Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces,

Introduction
The Four Methods

Introduction
The Four Methods

Working with Polynomials I

Working with Polynomials II
Thus for 1 ≤ a ≤ 4 we define the polynomials of degree q − 2XuX (u+a logg (1−g )) mod q−1 ∈ Z[X ] ,Pa (X ) =Recall that ω(x) ∈ Z[ζq−1 ], where ζq−1 is a primitive (q − 1)-throot of unity, so all operations can be done in this ring. However,slightly expensive. More efficient: work in R = Z[X ]/(X q−1 − 1),with the natural surjective map from R to Z[ζq−1 ] given by
X 7→ ζq−1 . The ring R has zero divisors, but no problem.

1≤u≤q−2n ) when (q − 1) ∤ an, and more generally
so J(n, an) = Pa (ζq−1

Let g be the unique generator of F∗q such that ω(g) = ζq−1 .
Generically, we haveJ(n, an) =Xω n (g u )ω an (1−g u ) =1≤u≤q−2

Xnu+na logg (1−g u )ζq−1

1≤u≤q−2

where logg is the discrete logarithm (gHenri Cohen (Talk given by Atsuko Miyaji)

logg (x)= x) modulo q − 1.

Point Counting on Quasi-Diagonal Hypersurfaces,
0 if (q − 1) ∤ an ,nJ(n, an) = Pa (ζq−1 ) + 1 if (q − 1) | an but (q − 1) ∤ n ,
2 if (q − 1) | n .
Since generically we haveJ5 (n, n, n, n, n) = J(n, n)J(n, 2n)J(n, 3n)J(n, 4n), it follows that
if we set P(X ) = P1 (X )P2 (X )P3 (X )P4 (X ) we have (generically)n ).
J5 (n, n, n, n, n) = P(ζq−1
Henri Cohen (Talk given by Atsuko Miyaji)

Introduction
The Four Methods

Introduction
The Four Methods

Working with Polynomials II

Working with Polynomials II

Thus for 1 ≤ a ≤ 4 we define the polynomials of degree q − 2XuX (u+a logg (1−g )) mod q−1 ∈ Z[X ] ,Pa (X ) =1≤u≤q−2n ) when (q − 1) ∤ an, and more generally
so J(n, an) = Pa (ζq−1
0 if (q − 1) ∤ an ,nJ(n, an) = Pa (ζq−1 ) + 1 if (q − 1) | an but (q − 1) ∤ n ,
2 if (q − 1) | n .
Since generically we haveJ5 (n, n, n, n, n) = J(n, n)J(n, 2n)J(n, 3n)J(n, 4n), it follows that
if we set P(X ) = P1 (X )P2 (X )P3 (X )P4 (X ) we have (generically)n ).
J5 (n, n, n, n, n) = P(ζq−1
Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Point Counting on Quasi-Diagonal Hypersurfaces

Write P(X ) =Pj0≤j≤q−2 aj X , and set ℓ = logg (B). We have−nℓ
ω −n (B)J5 (n, n, n, n, n) = ζq−1

X0≤j≤q−2nj
aj ζq−1=Xn(j−ℓ)

aj ζq−1.

0≤j≤q−2

The whole point of this method is that when we sum on n thePn(j−ℓ)
expression 0≤n≤q−2 ζq−1 almost always vanishes, more
precisely it vanishes if j 6= ℓ and otherwise it equals q − 1. Thus
(if all terms were generic) we would have S(q; B) = (q − 1)aℓ ,so instead of computing the J5 (n, n, n, n, n) individually, we
immediately have the sum.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

Working with Polynomials II
Write P(X ) =P

Working with Polynomials IIj0≤j≤q−2 aj X , and set ℓ = logg (B). We have−nℓ
ω −n (B)J5 (n, n, n, n, n) = ζq−1

X0≤j≤q−2nj
aj ζq−1=Xn(j−ℓ)

aj ζq−1.

0≤j≤q−2

The whole point of this method is that when we sum on n thePn(j−ℓ)
expression 0≤n≤q−2 ζq−1 almost always vanishes, more
precisely it vanishes if j 6= ℓ and otherwise it equals q − 1. Thus
(if all terms were generic) we would have S(q; B) = (q − 1)aℓ ,so instead of computing the J5 (n, n, n, n, n) individually, we
immediately have the sum.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

We must take care of the nongeneric terms, but this is simple
bookkeeping. The final result is the following (same notation aj
and ℓ):
S(q; B) = (q − 1)(aℓ + T1 + T2 + T3 + T4 )with Tm = 0 if m ∤ (q − 1), and otherwise
T1 = 8(q 2 − 2q + 2) ,T2 = χ2 (B)(q + 1) ,−1
2
T3 = 2ℜ(χ3 (B)J(χ3 , χ3 )2 ) , T4 = 2ℜ(χ−1
4 (B)J(χ4 , χ4 ) ) ,where χm is any character of F∗q of order exactly m. Note that
J(χm , χm ) can be computed in a special very fast way.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Working with Polynomials III

Working with Polynomials III

This requires essentially O(q) time, much faster than the direct
method. Main drawback of this method: although O(q) time, it
has also O(q) storage, so useless if q > 108 , say. For many
applications, it is sufficient.

This requires essentially O(q) time, much faster than the direct
method. Main drawback of this method: although O(q) time, it
has also O(q) storage, so useless if q > 108 , say. For many
applications, it is sufficient.

Sample timings: for q of the order 10k with k = 2, 3, 4, 5, 6, 7,
requires 0.002, 0.02, 0.08, 0.85, 9.9, 123 seconds respectively,
compatible with O(q) time and of course much faster than the
direct method; however already needs several gigabytes ofstorage for q ≈ 107 .

Sample timings: for q of the order 10k with k = 2, 3, 4, 5, 6, 7,
requires 0.002, 0.02, 0.08, 0.85, 9.9, 123 seconds respectively,
compatible with O(q) time and of course much faster than the
direct method; however already needs several gigabytes ofstorage for q ≈ 107 .

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

Using Theta Functions I

Using Theta Functions I

Assume that q = p. For χ a character on F∗p and t > 0 we
define the theta functionX
2
Θ(χ, t) = 2
me χ(m)e−πm t/p ,Assume that q = p. For χ a character on F∗p and t > 0 we
define the theta functionX
2
Θ(χ, t) = 2
me χ(m)e−πm t/p ,where e = 0 or 1 is the parity of χ (χ(−1) = (−1)e ).

where e = 0 or 1 is the parity of χ (χ(−1) = (−1)e ).

Main properties: first, it is very rapidly convergent (essentiallyO(p1/2 ) terms to compute numerical values). Second and mostimportantly, it has a functional equation for t ∈ R>0

Main properties: first, it is very rapidly convergent (essentiallyO(p1/2 ) terms to compute numerical values). Second and mostimportantly, it has a functional equation for t ∈ R>0m≥1

Θ(χ, 1/t) = W (χ)t 1/2+e Θ(χ, t) ,where

W (χ) = g(χ)/(i e p1/2 ) .

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Θ(χ, 1/t) = W (χ)t 1/2+e Θ(χ, t) ,where

W (χ) = g(χ)/(i e p1/2 ) .

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Using Theta Functions II

Using Theta Functions II

Thus, if for instance Θ(χ, 1) 6= 0 (otherwise use t 6= 1 or apply
L’Hospital’s rule) we haveg(χ) = i e p1/2 Θ(χ, 1)/Θ(χ, 1) .
Thus (for q = p) the Gauss sum g(χ) can be computed in timeessentially O(q 1/2 ) (more precisely O(q 1/2+ε ) for all ε > 0, but
we ignore ε). Since Jacobi sums can be expressed in terms of
products of Gauss sums, it follows that they also can becomputed in O(q 1/2 ). Much faster than the direct method which
requires O(q).

Henri Cohen (Talk given by Atsuko Miyaji)m≥1

Point Counting on Quasi-Diagonal Hypersurfaces

Using this, we can compute S(q; B) (for q = p) in time O(q 3/2 ).
Slower than the polynomial version above which was in O(q),but big advantage: essentially no storage. For q > 108 , much
too slow however.
Sample timings: for q = p of the order 10k with k = 2, 3, 4, 5,
requires 0.02, 0.4, 16.2, 663 seconds, compatible with O(q 3/2 )time. Much slower than the polynomial method, but very little
storage.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

Using Theta Functions II

Morita’s p-adic Gamma Function I

Using this, we can compute S(q; B) (for q = p) in time O(q 3/2 ).
Slower than the polynomial version above which was in O(q),but big advantage: essentially no storage. For q > 108 , much
too slow however.
Sample timings: for q = p of the order 10k with k = 2, 3, 4, 5,
requires 0.02, 0.4, 16.2, 663 seconds, compatible with O(q 3/2 )time. Much slower than the polynomial method, but very little
storage.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

We now come to the most efficient method, but also the mostsophisticated method to compute S(q; B). Since behind thescenes there are variants of crystalline cohomology theories,
this is a distant cousin of Kedlaya’s algorithm for counting
points on hyperelliptic curves. But don’t be afraid of these dirty
words, you will see that at the end of the day everything iscompletely elementary.
We assume some familiarity with p-adic numbers: recall simply
that in the p-adic topology pj → 0 when j → ∞. We denote by
Zp the ring of p-adic integers s = a0 + a1 p + a2 p2 + · · · with0 ≤ ai ≤ p − 1.

Henri Cohen (Talk given by Atsuko Miyaji)

Introduction
The Four Methods

Introduction
The Four Methods

Morita’s p-adic Gamma Function I
We now come to the most efficient method, but also the mostsophisticated method to compute S(q; B). Since behind thescenes there are variants of crystalline cohomology theories,
this is a distant cousin of Kedlaya’s algorithm for counting
points on hyperelliptic curves. But don’t be afraid of these dirty
words, you will see that at the end of the day everything iscompletely elementary.
We assume some familiarity with p-adic numbers: recall simply
that in the p-adic topology pj → 0 when j → ∞. We denote by
Zp the ring of p-adic integers s = a0 + a1 p + a2 p2 + · · · with0 ≤ ai ≤ p − 1.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Point Counting on Quasi-Diagonal Hypersurfaces

Morita’s p-adic Gamma Function II
We need to define the p-adic analogue of the ordinary gammafunction, called Morita’s p-adic gamma function and denotedΓp . Its definition is very simple (all limits p-adic):Ym!
Γp (s) = lim (−1)mk = lim (−1)m+1 ⌊m/p⌋
.
m→s
m→s−1
p
(⌊m/p⌋)!
m∈Z>00≤k <mp∤k

m∈Z>0Observe this definition: eliminating terms k such that p | k isnatural. But why the (−1)m ? this is due to Wilson’s theorem(p − 1)! ≡ −1 (mod p). Need to show convergence:
immediately follows from the following lemma (exercise!):YNk ≡ (−1)a·p(mod pN ) .
m≤k <m+a·pNp∤kHenri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

Morita’s p-adic Gamma Function II
We need to define the p-adic analogue of the ordinary gammafunction, called Morita’s p-adic gamma function and denotedΓp . Its definition is very simple (all limits p-adic):Ym!
Γp (s) = lim (−1)mk = lim (−1)m+1 ⌊m/p⌋
.
m→s
m→s−1
p
(⌊m/p⌋)!
m∈Z>00≤k <mp∤k

m∈Z>0Observe this definition: eliminating terms k such that p | k isnatural. But why the (−1)m ? this is due to Wilson’s theorem(p − 1)! ≡ −1 (mod p). Need to show convergence:
immediately follows from the following lemma (exercise!):YNk ≡ (−1)a·p(mod pN ) .
m≤k <m+a·pNp∤kHenri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Morita’s p-adic Gamma Function III
Properties completely analogous (but slightly different from) the
ordinary gamma function Γ(s) (expression of Γp (m) in terms offactorials for m ∈ Z, recursion formula giving Γp (s + 1) in termsof Γp (s), reflection formula giving Γp (1 − s) in terms of Γp (s),duplication and more generally distribution formula giving
Q0≤j<N Γp (s + j/N), explicit expression for Γp (1/2), explicit
power series expansion of logp (Γp (s + 1)), Raabe’s formula).
As a consequence: easy algorithms for computing it
implemented in most computer algebra systems.
There is a more sophisticated formula for the ordinary gammafunction called the Lerch, Chowla–Selberg formula which I will
not state. The p-adic analogue is what concerns us here, called
the Gross–Koblitz formula.
Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Morita’s p-adic Gamma Function III

The Gross–Koblitz Formula I

Properties completely analogous (but slightly different from) the
ordinary gamma function Γ(s) (expression of Γp (m) in terms offactorials for m ∈ Z, recursion formula giving Γp (s + 1) in termsof Γp (s), reflection formula giving Γp (1 − s) in terms of Γp (s),duplication and more generally distribution formula giving
Q0≤j<N Γp (s + j/N), explicit expression for Γp (1/2), explicit
power series expansion of logp (Γp (s + 1)), Raabe’s formula).
As a consequence: easy algorithms for computing it
implemented in most computer algebra systems.

We have a surprise: some natural values are algebraic: forexample one computes thatq√
Γ5 (1/4) = −2 + −1

There is a more sophisticated formula for the ordinary gammafunction called the Lerch, Chowla–Selberg formula which I will
not state. The p-adic analogue is what concerns us here, called
the Gross–Koblitz formula.

The general Gross–Koblitz formula says in rough terms that:
Any Gauss sum over Fpf is equal to an (explicit) product off values of Γp (si ) at rational arguments (si )1≤i≤f , up to a
known sign and rational power of p.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

for suitable signs of square roots. This is totally different fromthe ordinary gamma (Γ(1/4) is known to be transcendental),
but is a special case of the Gross-Koblitz formula. Moregenerally, Γp (r /(p − 1)) is an algebraic number.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

The Gross–Koblitz Formula I
We have a surprise: some natural values are algebraic: forexample one computes thatq√
Γ5 (1/4) = −2 + −1
for suitable signs of square roots. This is totally different fromthe ordinary gamma (Γ(1/4) is known to be transcendental),
but is a special case of the Gross-Koblitz formula. Moregenerally, Γp (r /(p − 1)) is an algebraic number.
The general Gross–Koblitz formula says in rough terms that:
Any Gauss sum over Fpf is equal to an (explicit) product off values of Γp (si ) at rational arguments (si )1≤i≤f , up to a
known sign and rational power of p.
Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Consequence: to compute Gauss sums (and Jacobi sums,
since they can be expressed in terms of Gauss sums), it issufficient to be able to compute Γp (s).
As mentioned, there exist efficient algorithms for this (see mybook Springer GTM 240). Can now forget about p-adic
numbers: one can obtain the result modulo p, or modulo p2 ,etc... This is sufficient because of the Deligne–Weil bounds.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

The Gross–Koblitz Formula II

Consequence: to compute Gauss sums (and Jacobi sums,
since they can be expressed in terms of Gauss sums), it issufficient to be able to compute Γp (s).
As mentioned, there exist efficient algorithms for this (see mybook Springer GTM 240). Can now forget about p-adic
numbers: one can obtain the result modulo p, or modulo p2 ,etc... This is sufficient because of the Deligne–Weil bounds.

Henri Cohen (Talk given by Atsuko Miyaji)

The Gross–Koblitz Formula II

Point Counting on Quasi-Diagonal Hypersurfaces

A Sample Pari/GP Session? gamma(1/4+O(5^12))% = 1 + 4*5 + 3*5^4 + 5^6 + 5^7 + 4*5^9 + 5^10 + O(5^12)? algdep(%,4)% = x^4 + 4*x^2 + 5 /* algebraic number */? gamma(1/3+O(7^20))% = 4 + 3*7 + 5*7^2 + 7^3 + 7^4 + 2*7^5 + 7^6 + 5*7^7 + ...
? algdep(%,6)% = x^6 - x^3 + 7 /* algebraic number */? gamma(1/6+O(7^20))% = 1 + 4*7 + 4*7^2 + 6*7^3 + 6*7^4 + 7^5 + 4*7^6 + ...
? algdep(%,6)% = x^6 + 13*x^3 + 49 /* algebraic number */? gamma(1/6+O(7^1000));
time = 96 ms. /* Very fast, even for 1000 p-adic digits. */Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

The Method using Gross–Koblitz I

The Method using Gross–Koblitz II

Using the Gross–Koblitz formula, it is easy to prove thefollowing
P result for our problem: let Hn be the nth harmonic sum
Hn = 1≤j≤n 1/j. Then
S(p; B) ≡X

0<r ≤(p−1)/5−p(5r )!
(1 + 5pr (H5r − Hr ))B pr
r !5X(p−1)/5<r ≤2(p−1)/5(5r − (p − 1))! rBr !5(mod p2 ) .

Now we have seen above that (p − 1) | S(p; B). Thus theabove congruence determines S(p; B) modulo p2 (p − 1). On
the other hand, the Weil conjectures (more precisely the
Riemann hypothesis for varieties, Deligne’s theorem) tells usthat |S(p; B) − p4 | < 4p5/2 . A small computation shows that forp ≥ 67 the congruence modulo (p − 1)p2 determines
completely S(p; B).

Note that this requires only O(p) operations and essentially no
storage.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

The Method using Gross–Koblitz II

The Method using Gross–Koblitz II

Thus this is a O(p) method, much faster than everything else
(even the implicit constant in the O() is very small), and notneeding much storage. Example in 2 seconds we obtain

Thus this is a O(p) method, much faster than everything else
(even the implicit constant in the O() is very small), and notneeding much storage. Example in 2 seconds we obtain

S(106 + 3; 2) = 1000012000056356142712140 .

S(106 + 3; 2) = 1000012000056356142712140 .

Sample timings: for q = p of the order 10k with k = 2, 3, 4, 5,
6, 7, 8 requires 0.001, 0.01, 0.03, 0.21, 2.13, 21.9, 229
seconds respectively, compatible with time O(q) (and 5 to 6
times faster than the polynomial method), but requiring
essentially no storage.
Therefore it is the best available method.

Sample timings: for q = p of the order 10k with k = 2, 3, 4, 5,
6, 7, 8 requires 0.001, 0.01, 0.03, 0.21, 2.13, 21.9, 229
seconds respectively, compatible with time O(q) (and 5 to 6
times faster than the polynomial method), but requiring
essentially no storage.
Therefore it is the best available method.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Introduction
The Four Methods

Conclusion I

Conclusion II

We have presented four algorithms for computing the numberof points of a quasi-diagonal hypersurface. A summary of thetimings (in seconds) for a prime q of the order of 10k is given in
the following table, where ∗ means that I have not been patientenough for the program to terminate:k
DirectTheta
Mod X q−1 − 1
Gross–Koblitz

2
0.03
0.02
0.00
0.00

3
1.56
0.40
0.02
0.01

Henri Cohen (Talk given by Atsuko Miyaji)

4
149.
16.2
0.08
0.03

5
∗
663.
0.85
0.21

6
∗
∗
9.90
2.13

7
∗
∗
123
21.9

8
∗
∗
∗
229.

Point Counting on Quasi-Diagonal Hypersurfaces

The definite conclusion is that the method using theGross–Koblitz formula is both by far the best in terms of speed,
but also in terms of storage since it does not need much.
Two additional remarks. First, note that this method can beused in point-counting for much more general varieties thanquasi-diagonal hypersurfaces, for instance for varieties comingfrom hypergeometric motives.
Second, computing |V (Fq )| for all small prime powers q allows
the construction of the global L-function attached to the variety
V , and in particular permits the experimental testing of
numerous conjectures (generalizing the Taniyama–Weilconjecture, i.e., Wiles’s theorem).

Henri Cohen (Talk given by Atsuko Miyaji)

Introduction
The Four Methods

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Conclusion II

Conclusion II

The definite conclusion is that the method using theGross–Koblitz formula is both by far the best in terms of speed,
but also in terms of storage since it does not need much.

The definite conclusion is that the method using theGross–Koblitz formula is both by far the best in terms of speed,
but also in terms of storage since it does not need much.

Two additional remarks. First, note that this method can beused in point-counting for much more general varieties thanquasi-diagonal hypersurfaces, for instance for varieties comingfrom hypergeometric motives.

Two additional remarks. First, note that this method can beused in point-counting for much more general varieties thanquasi-diagonal hypersurfaces, for instance for varieties comingfrom hypergeometric motives.

Second, computing |V (Fq )| for all small prime powers q allows
the construction of the global L-function attached to the variety
V , and in particular permits the experimental testing of
numerous conjectures (generalizing the Taniyama–Weilconjecture, i.e., Wiles’s theorem).

Second, computing |V (Fq )| for all small prime powers q allows
the construction of the global L-function attached to the variety
V , and in particular permits the experimental testing of
numerous conjectures (generalizing the Taniyama–Weilconjecture, i.e., Wiles’s theorem).

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces

Introduction
The Four Methods

Thank you for your attention.

Henri Cohen (Talk given by Atsuko Miyaji)

Point Counting on Quasi-Diagonal Hypersurfaces