# Full text of "Some Congruences of Kloosterman Sums and their Minimal Polynomials"

## See other formats

```Some Congruences of Kloosterman Sums and their Minimal

Polynomials

Faruk Gologlu* Gary McGuire*, Richard Moloney^
School of Mathematical Sciences
University College Dublin
Ireland

Abstract

We prove two results on Kloosterman sums over finite fields, using Stickelberger's
theorem and the Gross-Koblitz formula. The first result concerns the minimal polyno-
mial over Q of a Kloosterman sum, and the second result gives a characterisation of
ternary Kloosterman sums modulo 27.

1 Introduction

Let p be an odd prime, n > 1 an integer, q = and Q a primitive p^^ root of unity. We
let Fq denote the finite field with q elements, and let Tr denote the absolute trace function
Tr : ^ Fp,

Tr(a) = a + aP + aP^ +■■■+ a^""' .
The Kloosterman sum of a € F^ is defined to be

where we interpret as 0. We remark that some authors do not include in the definition
of Kloosterman sum.

Obviously K,q{a) is an algebraic integer lying in the cyclotomic field Q(C)- It is well known
that

Gal(Q(C)/Q) = {C ^ C M e (Z/pZ)*},

* Research supported by Claude Shannon Institute, Science Foundation Ireland Grant 06/MI/006
^Research supported by Claude Shannon Institute, Science Foundation Ireland Grant 06/MI/006, and
the Irish Research Council for Science, Engineering and Technology

1

and it is easy to show (see [5]) that the Galois automorphism C C* has the effect
K,q{a) I— )• K.q{i^a), for any integer i. If we let

2

1=1

it follows that Ca{x) (which has degree {p — l)/2) is the characteristic polynomial of lCq{a)
over Q. If ma{x) is the minimal polynomial of fCq{a) over Q, then

Ca{x) = maixY"

for some Ca dividing Most of the time, it is true that = 1. For example, Wan [11]
showed that ea = 1 if Tr(a) ^ 0.

Moisio [8] considered the reduction of the minimal polynomial ma{x) modulo p. He showed
that all coefficients, apart from the leading coefficient, are divisible by p.

In this paper, our ffi'st result concerns the reduction of the minimal polynomial ma{x)
modulo p^. In Section 3, we prove the following result about the constant term.

Theorem 1. Let p be an odd prime, and let ^-^ he the Legendre symbol. Then

p-1

f[}Cq{^a)^p(^^^ (modp2).
As a consequence, the constant term of the characteristic polynomial, which is

(-I)^n(/C,(z2a)),

is always congruent to either or ±p mod p'^.

In the case that p = 3, Theorem 1 becomes the following theorem.
Theorem 2. Let n > 1. For a € Fan,

r (mod 9) if Tr(a) = 0,
K.3n{a) = < 3 (mod 9) if Tv{a) = 1,
( 6 (mod 9) if Tr(a) = 2.

This is precisely the modulo 9 characterisation of the ternary Kloosterman sum which we
previously proved in [2]. The second result of this paper, see Corollary 18 in Section 4, is to
extend this result to a modulo 27 characterisation of the ternary Kloosterman sum.

2

2 Background

In this section we present the background information that is used in our proofs.
2.1 Teichmiiller characters and Gauss sums

Consider multiphcative characters taking their values in an algebraic extension of Qp. Let
be a primitive {q — 1)**^ root of unity in a fixed algebraic closure of Qp. The group of

multiplicative characters of ¥q (denoted Fg ) is cyclic of order q — 1. The group ¥q is
generated by the Teichmiiller character w : Fg — )■ Qp(^), which, for a fixed generator t
of Fg , is defined by uj{t^) = We set a;(0) to be 0. An equivalent definition is that oj

for ah a e Fg.

Let C be a fixed primitive p-th root of unity in the fixed algebraic closure of Qp. Let ^ be
the canonical additive character of Fg,

satisfies

uj{a) = a (mod p)

H{x) = C

■Tr[x)

The Gauss sum (see [7, 12]) of a character x G Fg is defined as

r{x)

We define

9(3)

For any positive integer j, let wtp(j) denote the p-weight of j, i.e.

where '^^jiP^ is the p-ary expansion of j.

2.2 Trace and similar objects

Consider again the trace function Tr : Fg — ?• F.

,n-l

3

We wish to generalise this definition to a larger class of finite field sums, which includes
the usual trace function special case.

Definition 3. Let p be a prime, let n > 1 be an integer and let q = p^. For any S C
Z/ {q — 1)Z satisfying 3^ = 3 where 3^ := {s^ \ s € 3}, we define the function : — ^ ¥p
by

Definition 4. Let p be a prime, let n > 1 be an integer and let q = p". For any 3 C I,/[q —
1)Z satisfying 3^ = 3 where 3^ := {s^ \ s G 3}, we define the function T5 : Fg — > Qp{^) by

^■s(c) ■.= ^uj'{c).

s&S

Remark 5. For the set W = {p' \ i S {0, . . . , n — 1}}, tw is the usual trace function.
Remark 6. By the definition of the Teichmiiller character, for any set 3 we have ts = ts
(mod p). Thus we may consider T5 to be a lift of r^, and this explains the notation. For
the set W defined in the previous remark, we let Tr denote the function f^/. Sometimes
we call Tr the lifted trace.

Other than the set W, for the case p = 3, we will be particularly concerned with the
following sets:

X := {r £ {0, . . . ,q — 2}\r = 3' + 3^}, not necessarily distinct)
Y ■.= {r £ {0, ... ,g- 2}|r = 3' + 3^ + 3^ ,i, j,k distinct},
Z := {r G {0, . . . , g - 2}|r = 2 • 3^ + 3^ z / j}.

2.3 Stickelberger's theorem and the Gross-Kobhtz formula

Let vr be the unique {p — l)th root of —p in Qp(^, C) satisfying

TT = C — 1 (mod vr^) .

Wan [11] noted that the following improved version of Stickelberger's theorem is a direct
consequence of the Gross-Koblitz formula (Theorem 8).

Theorem 7. [11] Let 1 < j < q — 1 be an integer and let j = jo + jip + • • • + jn-ip"'^^ ■
Then

g{j) ^ ; (mod TT-^M+P-^) .

Jo' ■ • -Jn-l!

4

Stickelberger's theorem, as usually stated, is the same congruence modulo n^^p^^^^^.

We have (see [3, 10]) that (vr) is the unique prime ideal of Qp(C)0 lying above p. Since
Qp(C)C) is an unramified extension of Qp(C); which is a totally ramified (degree p — 1)
extension of Qp, it follows that ('/r)^"^ = (p) and fp('/r) = Here Up denotes the p-adic
valuation.

Theorem 7 implies that v-wigij)) = ^^pii), and because Vp{g{j)) = i^n{g{j)) • ^pi"^) we
get

Wtp(j)

p-1

vp{9m = ^:^- (1)

A generalisation of Stickelberger's theorem is the Gross-Koblitz formula.
Theorem 8. (Gross-Koblitz formula) [3].

Let 1 < j < q — 1 he an integer. Then

n-l

1=0 ^ ^ ^ ' ^

where (x) is the fractional part of x, and Tp is the p-adic gamma function.

Our proof in Section 3 studies the vr-adic expansion of the Kloosterman sum, and uses the
Gross-Koblitz formula to get information on the coefficients.

The p-adic gamma function Tp, introduced in [9], is defined over N by

t<k

and extends to Tp : Zp — )■ Zp according to Theorem 10 below.

The following are two classical results (they appear in [1]) which can be rephrased in terms
of the p-adic gamma function. Theorem 10 appears in this form in [9].
Theorem 9 (Wilson's theorem). Let p be an odd prime. Then

Tp{p-l) = l (modp).

Theorem 10 (Generalised Wilson's theorem). Let p be a prime, and suppose x = y
(mod p^) for some integer k. If p^ ^ 4, then

Tp{x)=rp{y) (modp^).

5

2.5 Fourier coefficients

Recall that n{x) = The Fourier transform of a function / : Fg — )• C at a € Fg is

defined to be

/(a) = /(^)/^("^) •
The complex number /(a) is called the Fourier coefficient of / at a.

Consider monomial functions defined by f{x) = fi{x'^). When d = —1 we have /(a) =
lCpn[a). By Fourier analysis [4, 6] we have for any d

/(a) = ^ + ^ r{Cj^) t{J'^) u^\a)

i=i

and hence

q-2

f{a) = -Yl ^('^^^ ^(^^"^^ •
Putting (i = — l=p" — 2, this congruence becomes

q-2

K,{a) ^ -Y,{g{j)f uj\a) (mod g). (2)
i=i

We will use this in Section 4.

3 Proof of Theorem 1

Moisio [8] considered the reduction of the minimal polynomial ma{x) modulo p, and proved
the following.

Lemma 11. [8] For a € Fg, let m{x) be the minimal polynomial of JCq{a) over Q and let
t be the degree of m. Then

m{x) = X* (mod p).
Our first result concerns the reduction of the minimal polynomial ma{x) modulo p^.

6

Theorem 1. Let p be an odd prime, and let ^-^ be the Legendre symbol. Then

p-i

fl{JC,{^'a))^p(^) (mod/).

1=1 \ 1 /

Proof: For j E {1, . . . , g — 2}, Theorem 7 implies that

I'nigUf) = 2wtp(j),

so taking equation (2) mod vr^ gives

}Cq{a) = - ^ g{jf uj^{a) (mod vr"^)
wtp(i)=i

= -g{lfTr{a) (mod vr^).

Equation (3) imphes that //^^(^(l)^) = 2. Therefore we can write /Cg(a) as

ICq{a) = aivr^ + a27r^ H ,

where

«. = -(^)'lv(«)

n ((^)) j '^(«) Theorem
Reducing this expression modulo p gives that

1

ai = - I^Fp {^-^—^j j Tr(a) (mod p)

= — {Tp{p — 1))^ Tr(a) (mod p) (by Theorem 10)
= — Tr(a) (mod p) (by Theorem 9),

and thus

/Cq(a) = — vr^ Tr(a) (mod vr^).

7

So

p—1 p—1
2 2

J|(/Cg(i2a)) =7rP-i J](-i2Tr(a)) (mod vrf+i)

i=l i=l

p-l

2

pTr(a)'^ J](-i2) (modvrP+i)

i=l

But HiJi i^qi^"^^)) G ^ by the remarks in Section 1, so

p—1 p—1

2 2

p-l

JJ(;C,(^2a)) ^ -pTT{aY— Wi-i") (mod p^).

1=1 i=l

Using Wilson's Theorem (as usually stated), we have that

JJ(-i2) = JJi = -1 (modp).

i=l i=l

Thus

p-l

2

J{{Kq{i^a))=pTT{a)'^ =p(^^^^ (mod

□

Corollary 12. The constant term of the characteristic polynomial Ca{x) is always congru-
ent to either or ±p mod p^ .

The following result is due to Wan.

Theorem 13. [11] Let a G ¥q. IfTi:{a) ^ 0, the minimal polynomial of K,q{a) has degree

p-l

2 ■

Thus if Tr(a) 7^ 0, the minimal polynomial m(x) of /Cq(a) is precisely the characteristic
polynomial c(x). In this case (and in the case that deg(m(3;)) = 2z_ where Tr(a) = 0)
Theorem 1 gives a statement about the constant term of m(x) mod p'^.

If Tr(a) = and deg(m(x)) < then the result in Theorem 1 is implied by Lemma
11. In this case, our result gives us no extra information about the constant term of the
minimal polynomial.

8

4 Ternary Kloosterman sums modulo 27

In this section we use the same techniques to improve the modulo 9 Kloosterman sum
characterisation in [2] to a modulo 27 characterisation. First let us prove a lemma on
evaluations of the p-adic gamma function. This lemma will allow us to evaluate Gauss
sums for higher moduli and find Kloosterman congruences modulo 27.

Lemma 14. Let n > 3 g = 3" and let i be an integer in the range 0, ... n — 1. Then

r f/JL\'\ = S 13 (mod 27) ifi = l,
^[\q-l/J^\l (mod 27) if i > 1.

Proof. For any 3 < j < ?i, we have 3-' < g', and
so

((^)) = ^3(26 • 3^) (mod 27).
If i > 3, then 26 ■ 3^ = (mod 27), and

= 1 (mod 27) ,

Now r3(26-3) = r3(24) (mod 27) using Theorem 10. And r3(24) = 13 (mod 9). Similarly:

r3(26-9) = 1 (mod 27).

□

Lemma 14 allows us to compute Gauss sums modulo 27:
Lemma 15. Let n > 3 and let q = 3^. Then

{6 (mod 27) if wtp(j) = 1,
9 (mod 27) i/wtp(j)=2,
(mod 27) if wtp(j) > 3.

Proof. Suppose wt3(j) = 1. By Theorem 8 and Lemma 14,

gij) = l37T (mod 27).

9

Let

g{j) = 27 A + Utt

for some A € Z3[^,,^]. Then

£,(j)2 = 27'^A^ + 2 • 27 • 13^ + leOvr^
= leQvr^ (mod 27)
= 6 (mod 27)

since vr^ = —3. Now suppose wt3(j) = 2. By Theorem 8,

aU) = -3 (mod 9).

Thus g{j) =9B -3 for some B € Zg^, C], so

5(i)2 = 81^2 - 54B + 9 = 9 (mod 27).

It is clear from Theorem 8 that if wt3(j) > 2, then

271^2 wt3(j)|^^^.)2_

Now we are ready to prove our result on Kloosterman sums modulo 27.

Theorem 16. Let n > 3, g = 3" and let Tr and tx he as defined in Section 2.2. Then

IC3n{a) = 21TV(a) + 187^(0) (mod 27). (4)
Proof. Using (2) and Lemma 15, we get

q-2

^(«) = -Yl Siif (a) (mod l)

= - E 9(j-)V(a)- 9{jf^'{a) (mod 27)

Wt3(j)=l Wt3(i)=2

= -6 Y J {a) -9 E J {a) (mod 27)

wt3(i) = l wt3(j)=2

= 2m(a) + 18fJ(a) (mod 27). □

□

10

Next we shall express the above result in terms of operations within ¥q itself, i.e., using
functions ts directly, and not their lifts. Note that in (4) we only need Tr(a) modulo 9 and
Tx{a) modulo 3. We have

Txid) = (mod 3)

so this takes care of the "fx (a) term. For the other term we need to find a condition for
Tr(a) modulo 9 using functions from Fg to F3. We will do that in the proof of the following
corollary.

Corollary 17. Let n > 3, q = 3", a € Fg and let tx, ty and tz he as defined in Section
2.2. Let Tr(a) be the trace of a, but considered as an integer. Then

ICq{a) = 21Tr{af + 18x^(0) + Dry (a) + 18Tx(a) (mod 27).

Proof. First recall that Tx(a) = Tx{a) (mod 3).
To determine Tr(a) mod 9, we compute

j,i,fce{o,...,n-i}
= Tr(a) + 3Tz{a) + dry (a) ,

and note the elementary fact that if x = y (mod m), then x™' = (mod m^). This means
that Tr(a)^ mod 9 is given by Tr(a) mod 3 = Tr(a), i.e. Tr(a)'^ mod 9 = Tr(o)'^.

Since

Tzia) = Tz{a) (mod 3)

and

ry(a) = Tyia) (mod 3) ,

we have that

Tr{a) = Tr{af - 3Tz{a) - 6ry(a) (mod 9),
proving the result. □

The next corollary combines Corollary 17 and Theorem 16 and enumerates the possible
values of ternary Kloosterman sums mod 27.

11

Corollary 18. Let n > 3, and let q = 3"". Let Ti, tx and Ty he as defined in Section 2.2.
Then

Kq{a) = <

r

3
6
9
12
15
18
21
24

mod 27) if Tr(a

mod 27) if Tr(a

mod 27) if Tr(a

mod 27) if Tr(a

mod 27) if Tr(a

mod 27) if Tr(a

mod 27) if Tr(a

mod 27) if Tr(a

mod 27) if Tr(a

and Ty(a) +2Tx{a) =

1 and Ty(a) = 2

2 and Ty(a) +Tx(a) = 2

anc? Ty(a) +2rx(a) = 1

1 and Ty(a) =

2 and Ty(a) +rx(a) =

and Ty(a) +2Tx(a) = 2

1 and ry(a) = 1

2 and ry(a) +Tx(a) = 1-

Proof. Note that

Tr(a)rx(a) =Tr(a) + 2rz(a).

Thus Corollary 17 can be rewritten as

/C9(a) = 21Tr(a)^ + 18Tr(a) + 18Tx(a) + 9Tr(a)rx(a) + 9Ty(a) (mod 27). (5)

We remark that a characterisation like in Corollary 18 of Kloosterman sums modulo
for p > 3 does not seem to be straightforward. The estimates given by the Gross-Koblitz
formula are weaker.

References

[1] C.F. Gauss. Disquisitiones Arithmeticae. Springer-Verlag, 1986.

[2] Faruk Gologlu, Gary McGuire, and Richard Moloney. Ternary Kloosterman sums
modulo 18 using Stickelberger's theorem. In Claude Carlet and Alexander Pott, ed-
itors, Sequences and Their Applications - SETA 2010, volume 6338 of Lecture Notes
in Computer Science, pages 196-203. Springer, 2010.

[3] Benedict H. Gross and Neal Koblitz. Gauss sums and the p-adic F-function. Ann. of
Math. (2), 109(3):569-581, 1979.

[4] Nicholas M. Katz. Gauss sums, Kloosterman sums, and monodromy groups, volume
116 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ,

The result is an enumeration of the cases in equation (5).

□

1988.

12

K.P. Kononen, M.J. Rinta-aho, and K.O. Vaananen. On integer values of Kloosterman
sums. IEEE Transactions on Information Theory, 56(8):4011-4013, Aug 2010.

Philippe Langevin and Gregor Leander. Monomial bent functions and Stickelberger's
theorem. Finite Fields and Their Applications, 14:727-742, 2008.

Rudolf Lidl and Harald Niederreiter. Introduction to Finite Fields and Their Appli-
cations. Cambridge University Press, 1986.

M.J. Moisio. On certain values of Kloosterman sums. IEEE Transactions on Infor-
mation Theory, 55(8):3563 -3564, Aug 2009.

Yasuo Morita. A p-adic analogue of the P-function. J. Fac. Sci. Univ. Tokyo Sect. lA
Math., 22(2):255-266, 1975.

Alain Robert. The Gross-Koblitz formula revisited. Rendiconti del Seminario Matem-
atico della Universitd di Padova, 105:157 - 170, 2001.

Da Qing Wan. Minimal polynomials and distinctness of Kloosterman sums. Finite
Fields AppL, l(2):189-203, 1995. Special issue dedicated to Leonard Carlitz.

Lawrence C. Washington. Introduction to Cyclotomic Fields. Springer, 1982.

13

```