Skip to main content

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. 



2.4 The p-adic gamma function 

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