# 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