Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums
In this paper, we construct two binary linear codes associated with multi-dimensional and m-multiple power Kloosterman sums (for any fixed m) over the finite field Fq. Here q is a power of two. The former codes are dual to a subcode of the binary hyper-Kloosterman code. Then we obtain two recurs...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2015
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/154253 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums / D.S. Kim // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 2. — С. 213-228 . — Бібліогр.: 18 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154253 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1542532019-06-16T01:26:52Z Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums Kim, D.S. In this paper, we construct two binary linear codes associated with multi-dimensional and m-multiple power Kloosterman sums (for any fixed m) over the finite field Fq. Here q is a power of two. The former codes are dual to a subcode of the binary hyper-Kloosterman code. Then we obtain two recursive formulas for the power moments of multi-dimensional Kloosterman sums and for the m-multiple power moments of Kloosterman sums in terms of the frequencies of weights in the respective codes. This is done via Pless power moment identity and yields, in the case of power moments of multi-dimensional Kloosterman sums, much simpler recursive formulas than those associated with finite special linear groups obtained previously. 2015 Article Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums / D.S. Kim // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 2. — С. 213-228 . — Бібліогр.: 18 назв. — англ. 1726-3255 2010 MSC:11T23, 20G40, 94B05. http://dspace.nbuv.gov.ua/handle/123456789/154253 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper, we construct two binary linear codes associated with
multi-dimensional and m-multiple power Kloosterman sums (for any
fixed m) over the finite field Fq. Here q is a
power of two. The former codes are dual to a subcode of the binary
hyper-Kloosterman code. Then we obtain two recursive formulas for
the power moments of multi-dimensional Kloosterman sums and for the
m-multiple power moments of Kloosterman sums in terms of the
frequencies of weights in the respective codes. This is done via
Pless power moment identity and yields, in the case of power moments
of multi-dimensional Kloosterman sums, much simpler recursive
formulas than those associated with finite special linear groups
obtained previously. |
| format |
Article |
| author |
Kim, D.S. |
| spellingShingle |
Kim, D.S. Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums Algebra and Discrete Mathematics |
| author_facet |
Kim, D.S. |
| author_sort |
Kim, D.S. |
| title |
Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums |
| title_short |
Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums |
| title_full |
Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums |
| title_fullStr |
Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums |
| title_full_unstemmed |
Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums |
| title_sort |
recursive formulas generating power moments of multi-dimensional kloosterman sums and m-multiple power moments of kloosterman sums |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2015 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154253 |
| citation_txt |
Recursive formulas generating power moments of multi-dimensional Kloosterman sums and m-multiple power moments of Kloosterman sums / D.S. Kim // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 2. — С. 213-228 . — Бібліогр.: 18 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT kimds recursiveformulasgeneratingpowermomentsofmultidimensionalkloostermansumsandmmultiplepowermomentsofkloostermansums |
| first_indexed |
2025-07-14T05:54:41Z |
| last_indexed |
2025-07-14T05:54:41Z |
| _version_ |
1837600585672556544 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 19 (2015). Number 2, pp. 213–228
© Journal “Algebra and Discrete Mathematics”
Recursive formulas generating power moments
of multi-dimensional Kloosterman sums and
m-multiple power moments of Kloosterman
sums∗
Dae San Kim
Communicated by V. V. Kirichenko
Abstract. In this paper, we construct two binary linear
codes associated with multi-dimensional and m−multiple power
Kloosterman sums (for any fixed m) over the finite field Fq. Here
q is a power of two. The former codes are dual to a subcode of
the binary hyper-Kloosterman code. Then we obtain two recursive
formulas for the power moments of multi-dimensional Kloosterman
sums and for the m-multiple power moments of Kloosterman sums
in terms of the frequencies of weights in the respective codes. This
is done via Pless power moment identity and yields, in the case
of power moments of multi-dimensional Kloosterman sums, much
simpler recursive formulas than those associated with finite special
linear groups obtained previously.
1. Introduction and Notations
Let ψ be a nontrivial additive character of the finite field Fq with
q = pr elements (p a prime), and let m be a positive integer. Then the
∗This work was supported by National Research Foundation of Korea Grant funded
by the Korean Government 2009-0072514.
2010 MSC: 11T23, 20G40, 94B05.
Key words and phrases: Index terms-recursive formula, multi-dimensional
Kloosterman sum, Kloosterman sum, Pless power moment identity, weight distribution.
214 m-multiple power moments of Kloosterman sums
m-dimensional Kloosterman sum Km(ψ; a)([10]) is defined by
Km(ψ; a) =
∑
α1,··· ,αm∈F∗
q
ψ(α1 + · · · + αm + aα−1
1 · · ·α−1
m ) (a ∈ F∗
q).
For this, we have the Deligne bound
|Km(ψ; a)| 6 (m+ 1)q
m
2 . (1.1)
In particular, if m = 1, then K1(ψ; a) is simply denoted by K(ψ; a),
and is called the Kloosterman sum. The Kloosterman sum was introduced
in 1926 [8] to give an estimate for the Fourier coefficients of modular
forms. It has also been studied to solve various problems in coding theory
and cryptography over finite fields of characteristic two.
For each nonnegative integer h, we denote by MKm(ψ)h the h-th
moment of the m-dimensional Kloosterman sum Km(ψ; a), i.e.,
MKm(ψ)h =
∑
a∈F∗
q
Km(ψ; a)h.
If ψ = λ is the canonical additive character of Fq, then MKm(λ)h
will be simply denoted by MKh
m. If futher m = 1, for brevity MKh
1 will
be indicated by MKh. The power moments of Kloosterman sums can be
used, for example, to give an estimate for the Kloosterman sums.
Explicit computations on power moments of Kloosterman sums were
initiated in the paper [17] of Salié in 1931, where it is shown that for any
odd prime q,
MKh = q2Mh−1 − (q − 1)h−1 + 2(−1)h−1 (h > 1).
Here M0 = 0, and, for h ∈ Z>0,
Mh = |{(α1, · · · , αh) ∈ (F∗
q)h|
h
∑
j=1
αi = 1 =
h
∑
j=1
α−1
i }|.
For q = p an odd prime, Salié obtained MK1, MK2, MK3, MK4
in that same paper by determining M1, M2, M3. On the other hand,
MK5 can be expressed in terms of the p-th eigenvalue for a weight 3
newform on Γ0(15) (cf. [11], [16]). MK6 can be expressed in terms of the
p-th eigenvalue for a weight 4 newform on Γ0(6) (cf.[4]). Also, based on
numerical evidence, in [3] Evans was led to propose a conjecture which
D. S. Kim 215
expresses MK7 in terms of Hecke eigenvalues for a weight 3 newform on
Γ0(525) with quartic nebentypus of conductor 105.
From now on, let us assume that q = 2r. Carlitz [1] evaluated MKh
for h 6 4. Recently, Moisio was able to find explicit expressions of MKh,
for h 6 10 (cf. [13]). This was done, via Pless power moment identity, by
connecting moments of Kloosterman sums and the frequencies of weights
in the binary Zetterberg code of length q + 1, which were known by the
work of Schoof and Vlugt in [18].
Also, Moisio considered binary hyper-Kloosterman codes C(r,m) and
determined the weight distributions of C(r,m) and C⊥(r,m), for r = 2
and all m > 2, and for all r > 2 and m = 3 (cf. [14]). In [15], these results
were further extended to the case of r = 3, 4 and all m > 2.
In this paper, we construct two binary linear codes Cn−1 and Dm,
respectively connected with multi-dimensional and m-multiple power
Kloosterman sums (for any fixed m) over the finite field Fq. Here q is
a power of two. The code C⊥
n−1 is a subcode of the hyper-Kloosterman
code C(r, n), which is mentioned above. Then we obtain two recursive
formulas for the power moments of multi-dimensional Kloosterman sums
and the m-multiple power moments of Kloosterman sums in terms of
the frequencies of weights in the respective codes. This is done via Pless
power moment identity and yields, in the case of power moments of multi-
dimensional Kloosterman sums, much simpler recursive formulas than
those obtained previously in [5]. As for the case of q a power of three,
in [6] two infinite families of ternary linear codes associated with double
cosets in the symplectic group Sp(2n, q) were constructed in order to
generate infinite families of recursive formulas for the power moments
of Kloosterman sums with square arguments and for the even power
moments of those in terms of the frequencies of weights in those codes.
Theorem 1.1. (1) Let n = 2s, q = 2r. For r > 3, and h = 1, 2, · · · ,
MKh
n−1 =
h−1
∑
l=0
(−1)h+l+1
(
h
l
)
(q − 1)(n−1)(h−l)MK l
n−1
+ q
min{(q−1)n−1, h}
∑
j=0
(−1)h+jCn−1,j
h
∑
t=j
t!S(h, t)2h−t
(
(q − 1)n−1 − j
(q − 1)n−1 − t
)
.
(1.2)
Here S(h, t) indicates the Stirling number of the second kind given by
S(h, t) =
1
t!
t
∑
j=0
(−1)t−j
(
t
j
)
jh. (1.3)
216 m-multiple power moments of Kloosterman sums
In addition, {Cn−1,j}(q−1)n−1
j=0 denotes the weight distribution of the binary
linear code Cn−1, given by
Cn−1,j =
∑ ∏
β∈Fq
(
δ(n− 1, q;β)
νβ
)
, (1.4)
where the sum runs over all the sets of integers {νβ}β∈Fq
(0 6 νβ 6
δ(n− 1, q;β)) satisfying
∑
β∈Fq
νβ = j,
∑
β∈Fq
νββ = 0 (1.5)
and δ(n− 1, q;β) = |{(α1, · · · , αn−1) ∈ (F∗
q)n−1|
α1 + · · · + αn−1 + α−1
1 · · ·α−1
n−1 = β}|
=
{
q−1{(q − 1)n−1 + 1}, if β = 0,
Kn−2(λ;β−1) + q−1{(q − 1)n−1 + 1}, if β ∈ F∗
q .
Here we understand that K0(λ;β−1) = λ(β−1).
(2) Let q = 2r. For r > 3, and m,h = 1, 2, · · · ,
MKmh =
h−1
∑
l=0
(−1)h+l+1
(
h
l
)
(q − 1)m(h−l)MKml
+ q
min{(q−1)m,h}
∑
j=0
(−1)h+jDm,j
h
∑
t=j
t!S(h, t)2h−t
(
(q − 1)m − j
(q − 1)m − t
)
.
(1.6)
Here {Dm,j}(q−1)m
j=0 is the weight distribution of the binary linear code Dm,
given by
Dm,j =
∑ ∏
β∈Fq
(
σ(m, q;β)
νβ
)
, (1.7)
where the sum runs over all the sets of integers {νβ}β∈Fq
(0 6 νβ 6
σ(m, q;β)) satisfying (1.5), and
σ(m, q;β) = |{(α1, · · · , αm) ∈ (F∗
q)m|
α1 + · · · + αm + α−1
1 + · · · + α−1
m = β}|
=
∑
λ(α1 + · · · + αm) + q−1{(q − 1)m + (−1)m+1},
(1.8)
with the sum running over all α1,· · ·, αm ∈F∗
q, satisfying α−1
1 +· · ·+α−1
m =β.
D. S. Kim 217
(1) and (2) of the following are respectively n = 2 and n = 4 cases
of Theorem 1.1 (1) (cf. (3.3), (3.4)), and (3) and (4) are equivalent and
n = 2 case of Theorem 1.1 (2) ((cf. (5.4), (5.8)).
Corollary 1.2. (1) Let q = 2r. For r > 3, and h = 1, 2, · · · ,
MKh =
h−1
∑
l=0
(−1)h+l+1
(
h
l
)
(q − 1)h−lMK l
+ q
min{(q−1),h}
∑
j=0
(−1)h+jC1,j
h
∑
t=j
t!S(h, t)2h−t
(
q − 1 − j
q − 1 − t
)
,
(1.9)
where {C1,j}q−1
j=0 is the weight distribution of the binary linear code C1,
with
C1,j =
∑
(
1
ν0
)
∏
tr(β−1)=0
(
2
νβ
)
(j = 0, · · · , N1).
Here the sum is over all the sets of nonnegative integers {ν0}⋃{νβ}tr(β−1)=0
satisfying ν0 +
∑
tr(β−1)=0 νβ = j and
∑
tr(β−1)=0 νββ = 0.
(2) Let q = 2r. For r > 3, and h = 1, 2, · · · ,
MKh
3 =
h−1
∑
l=0
(−1)h+l+1
(
h
l
)
(q − 1)3(h−l)MK l
3
+ q
min{(q−1)3,h}
∑
j=0
(−1)h+jC3,j
h
∑
t=j
t!S(h, t)2h−t
(
(q − 1)3 − j
(q − 1)3 − t
)
,
(1.10)
where {C3,j}(q−1)3
j=0 is the weight distribution of the binary linear code C3,
with
C3,j =
∑
(
m0
ν0
)
∏
|t|<2
√
q
t≡−1(4)
∏
K(λ;β−1)=t
(
mt
νβ
)
.
Here the sum runs over all the sets of nonnegative integers {νβ}β∈Fq
satisfying (1.5),
m0 = q2 − 3q + 3,
and
mt = t2 + q2 − 4q + 3,
218 m-multiple power moments of Kloosterman sums
for every integer t satisfying |t| < 2
√
q and t ≡ −1(4).
(3) Let q = 2r. For r > 3, and h = 1, 2, · · · ,
MK2h =
h−1
∑
l=0
(−1)h+l+1
(
h
l
)
(q − 1)2(h−l)MK2l
+ q
min{(q−1)2,h}
∑
j=0
(−1)h+jD2,j
h
∑
t=j
t!S(h, t)2h−t
(
(q − 1)2 − j
(q − 1)2 − t
)
,
(1.11)
where {D2,j}(q−1)2
j=0 is the weight distribution of the binary linear code D2,
with
D2,j =
∑
(
2q − 3
ν0
)
∏
β∈F∗
q
(
K(λ;β−1) + q − 3
νβ
)
=
∑
(
2q − 3
ν0
)
∏
|t|<2
√
q
t≡−1(4)
∏
K(λ;β−1)=t
(
t+ q − 3
νβ
)
,
(1.12)
with the sum running over all the sets of nonnegative integers {νβ}β∈Fq
satisfying (1.5).
(4) Let q = 2r. For r > 3, and h = 1, 2, · · · ,
MKh
2 =
h−1
∑
l=0
(−1)h+l+1
(
h
l
)
(q2 − 3q + 1)(h−l)MK l
2
+ q
min{(q−1)2,h}
∑
j=0
(−1)h+jD2,j
h
∑
t=j
t!S(h, t)2h−t
(
(q − 1)2 − j
(q − 1)2 − t
)
,
(1.13)
where D2,j(0 6 j 6 (q − 1)2)’s are just as in (1.12).
The next two theorems will be of use later.
Theorem 1.3 ([9]). Let q = 2r, with r > 2. Then the range R of K(λ; a),
as a varies over F∗
q, is given by
R = {t ∈ Z | |t| < 2
√
q, t ≡ −1(mod4)}.
In addition, each value t ∈ R is attained exactly H(t2 − q) times,
where H(d) is the Kronecker class number of d.
D. S. Kim 219
Theorem 1.4 ([2]). For the canonical additive character λ of Fq, and
a ∈ F∗
q,
K2(λ; a) = K(λ; a)2 − q. (1.14)
Before we proceed further, we will fix the notations that will be used
throughout this paper:
q = 2r (r ∈ Z>0),
Fq = the finite field with q elements,
tr(x) = x+ x2 + · · · + x2r−1
the trace function Fq → F2,
λ(x) = (−1)tr(x) the canonical additive character of Fq.
Note that any nontrivial additive character ψ of Fq is given by ψ(x) =
λ(ax), for a unique a ∈ F∗
q .
2. Construction of codes associated
with multi-dimensional Kloosterman sums
We will construct binary linear codes Cn−1 of length N1 = (q− 1)n−1,
connected with the (n− 1)-dimensional Kloosterman sums. Here n = 2s,
with s ∈ Z>0.
Let
vn−1 = (· · · , α1 + · · · + αn−1 + α−1
1 · · ·α−1
n−1, · · · ), (2.1)
where α1, α2, · · · , αn−1 run respectively over all elements of F∗
q . Here we
do not specify the ordering of the components of vn−1, but we assume
that some ordering is fixed.
Proposition 2.1 ([5], Proposition 11). For each β ∈ Fq, let
δ(n− 1, q;β)
= |{(α1, · · · , αn−1) ∈ (F∗
q)n−1|α1 + · · · ,+αn−1 + α−1
1 · · ·α−1
n−1 = β}|
(Note that δ(n− 1, q;β) is the number of components with those equal to
β in the vector vn−1(cf.(2.1))). Then
δ(n− 1, q; 0) = q−1{(q − 1)n−1 + 1},
and, for β ∈ F∗
q,
δ(n− 1, q;β) = Kn−2(λ;β−1) + q−1{(q − 1)n−1 + 1},
where K0(λ;β−1) = λ(β−1) by convention.
220 m-multiple power moments of Kloosterman sums
Corollary 2.2.
(1) δ(1, q;β) =
2, if tr(β−1) = 0,
1, if β = 0,
0, if tr(β−1) = 1.
(2.2)
(2) δ(3, q;β) =
{
q2 − 3q + 3, if β = 0,
K(λ;β−1)2+q2−4q+3, if β∈F∗
q (cf.(1.14)).
(2.3)
The binary linear code Cn−1 is defined as
Cn−1 = {u ∈ F
N1
2 |u · vn−1 = 0}, (2.4)
where the dot denotes the usual inner product in FN1
q .
The following Delsarte’s theorem is well-known.
Theorem 2.3 ([12]). Let B be a linear code over Fq. Then
(B|F2
)⊥ = tr(B⊥).
In view of this theorem, the dual C⊥
n−1 of Cn−1 is given by
C⊥
n−1 ={c(a)=(· · · , tr(a(α1+· · ·+αn−1+α−1
1 · · ·α−1
n−1)), · · · )|a ∈ Fq}.
(2.5)
Lemma 2.4. (q − 1)n−1 > nq
n−1
2 , for all n = 2s (s ∈ Z>0), and q =
2r > 8.
Proof. This can be proved, for example, by induction on s.
Proposition 2.5. For q = 2r, with r > 3, the map Fq → C⊥
n−1(a 7→ c(a))
is an F2-linear isomorphism.
Proof. The map is clearly F2-linear and onto. Let a be in the kernel
of the map. Then tr(a(α1 + · · · + αn−1 + α−1
1 · · ·α−1
n−1)) = 0, for all
α1, · · · , αn−1 ∈ F∗
q . Suppose that a 6= 0. Then, on the one hand,
∑
α
1
,··· ,α
n−1
∈F∗
q
(−1)tr(a(α
1
+···+αn−1
+α−1
1
···α−1
n−1
)) = (q − 1)n−1 = N1. (2.6)
On the other hand, (2.6) is equal to Kn−1(λ; a) (cf. proof of Proposition 11
in [5]), and so from Deligne’s estimate in (1.1) we get
(q − 1)n−1
6 nq
n−1
2 .
But this is impossible for q > 8, in view of Lemma 2.4.
D. S. Kim 221
3. Recursive formulas for power moments
of multi-dimensional Kloostermann sums
We are now ready to derive, via Pless power moment identity, a recur-
sive formula for the power moments of multi-dimensional Kloosterman
sums in terms of the frequencies of weights in Cn−1.
Theorem 3.1 (Pless power moment identity, [12]). Let B be an q-ary
[n, k] code, and let Bi(resp. B⊥
i ) denote the number of codewords of weight
i in B(resp. in B⊥). Then, for h = 0, 1, 2, · · · ,
n
∑
i=0
ihBi =
min{n,h}
∑
i=0
(−1)iB⊥
i
h
∑
t=i
t!S(h, t)qk−t(q − 1)t−i
(
n− i
n− t
)
, (3.1)
where S(h, t) is the Stirling number of the second kind defined in(1.3).
For the following lemma, observe that (n, q − 1) = 1.
Lemma 3.2. The map a 7→ an : F∗
q → F∗
q is a bijection.
Lemma 3.3. For a ∈ F∗
q, the Hamming weight w(c(a))(cf. (2.5)) of c(a)
can be expressed as follows:
w(c(a)) =
N1
2
− 1
2
Kn−1(λ; a), with N1 = (q − 1)n−1. (3.2)
Proof.
w(c(a)) =
1
2
∑
α
1
,··· ,α
n−1
∈F∗
q
(1 − (−1)tr(a(α
1
+···+αn−1
+α−1
1
···α−1
n−1
)))
=
1
2
{N1 −
∑
α
1
,··· ,α
n−1
∈F∗
q
λ(a(α1 + · · · + αn−1 + α−1
1 · · ·α−1
n−1))}
=
N1
2
− 1
2
∑
α
1
,··· ,α
n−1
∈F∗
q
λ(α1 + · · · + αn−1 + anα−1
1 · · ·α−1
n−1)
=
N1
2
− 1
2
∑
α
1
,··· ,α
n−1
∈F∗
q
λ(αn
1 + · · · + αn
n−1 + anα−n
1 · · ·α−n
n−1)
(by Lemma 3.2)
=
N1
2
− 1
2
∑
α
1
,··· ,α
n−1
∈F∗
q
λ((α1 + · · · + αn−1 + aα−1
1 · · ·α−1
n−1)n)
=
N1
2
− 1
2
∑
α
1
,··· ,α
n−1
∈F∗
q
λ(α1 + · · · + αn−1 + aα−1
1 · · ·α−1
n−1)
222 m-multiple power moments of Kloosterman sums
([10], Theorem 2.23(v))
=
N1
2
− 1
2
Kn−1(λ; a).
Denote for the moment vn−1 in (2.1) by vn−1 = (g1, g2, · · · , gN1
). Let
u = (u1, · · · , uN1
) ∈ F
N1
2 , with νβ 1’s in the coordinate places where
gl = β, for each β ∈ Fq. Then we see from the definition of the code Cn−1
(cf. (2.4)) that u is a codeword with weight j if and only if
∑
β∈Fq
νβ = j
and
∑
β∈Fq
νββ = 0 (an identity in Fq). As there are
∏
β∈Fq
(δ(n−1,q;β)
νβ
)
(cf. Proposition 2.1) many such codewords with weight j, we obtain the
following result.
Proposition 3.4. Let {Cn−1,j}N1
j=0 be the weight distribution of Cn−1,
where Cn−1,j denotes the frequency of the codewords with weight j in
Cn−1. Then
Cn−1,j =
∑ ∏
β∈Fq
(
δ(n− 1, q;β)
νβ
)
,
where the sum runs over all the sets of integers {νβ}β∈Fq
(0 6 νβ 6
δ(n− 1, q;β)) satisfying
∑
β∈Fq
νβ = j, and
∑
β∈Fq
νββ = 0.
Corollary 3.5. (1) Let {C1,j}q−1
j=0 be the weight distribution of C1. Then
C1,j =
∑
(
1
ν0
)
∏
tr(β−1)=0
(
2
νβ
)
(j = 0, · · · , q − 1), (3.3)
where the sum is over all the sets of nonnegative integers {ν0}∪{νβ}tr(β−1)=0
satisfying ν0 +
∑
tr(β−1)=0 νβ = j and
∑
tr(β−1)=0 νββ = 0 (cf.(2.2)).
(2) Let {C3,j}(q−1)3
j=0 be the weight distribution of C3. Then
C3,j =
∑
(
m0
ν0
)
∏
|t|<2
√
q
t≡−1(4)
∏
K(λ;β−1)=t
(
mt
νβ
)
, (3.4)
where the sum runs over all the sets of integers {νβ}β∈Fq
satisfying
∑
β∈Fq
νβ = j, and
∑
β∈Fq
νββ = 0,
D. S. Kim 223
m0 = q2 − 3q + 3,
and
mt = t2 + q2 − 4q + 3,
for every integer t satisfying |t|<2
√
q and t≡−1(4) (cf.Theorem1.3,(2.3)).
Remark 3.6. This shows that the weight distribution of C1 is the same
as that of C(SO+(2, q)) (cf. [7]).
From now on, we will assume that r > 3, and hence every codeword
in C⊥
n−1 can be written as c(a), for a unique a ∈ Fq (cf. Proposition 2.5).
We now apply the Pless power moment identity in (3.1) to C⊥
n−1, in
order to obtain the result in Theorem 1.1 (1) about a recursive formula.
Then the left hand side of that identity in (3.1) is equal to
∑
a∈F∗
q
w(c(a))h, (3.5)
with w(c(a)) given by (3.2). So (3.5) is
∑
a∈F∗
q
w(c(a))h =
1
2h
∑
a∈F∗
q
(N1 −Kn−1(λ; a))h
=
1
2h
∑
a∈F∗
q
h
∑
l=0
(−1)l
(
h
l
)
Nh−1
1 Kn−1(λ; a)l
=
1
2h
h
∑
l=0
(−1)l
(
h
l
)
Nh−1
1 MK l
n−1.
(3.6)
On the other hand, noting that dimF2
Cn−1 = r (cf. Proposition 2.5)
the right hand side of the Pless moment identity(cf. (3.1)) becomes
q
min{N1,h}
∑
j=0
(−1)jCn−1,j
h
∑
t=j
t!S(h, t)2−t
(
N1 − j
N1 − t
)
. (3.7)
Our result in (1.2) follows now by equating (3.6) and (3.7).
Remark 3.7. A recursive formula for the power moments of multi-
dimensional Kloosterman sums was obtained in [5] by constructing binary
linear codes C(SL(n, q)) and utilizing explicit expressions of Gauss sums
for the finite special linear group SL(n, q). However, our result in (1.2) is
better than that in (1) of [5]. Because our formula here is much simpler
than the one there. Indeed, the length of the code Cn−1 here is N1 =
(q − 1)n−1, whereas that of C(SL(n, q)) there is N = q(
n
2)
∏n
j=2(qj − 1),
both of which appear in their respective expressions of recursive formulas.
224 m-multiple power moments of Kloosterman sums
4. Construction of codes associated
with powers of Kloosterman sums
We will construct binary linear codes Dm of length N2 = (q − 1)m,
connected with the m-th powers of (the ordinary) Kloosterman sums.
Here m ∈ Z>0.
Let
wm = (· · · , α1 + · · · + αm + α−1
1 + · · · + α−1
m , · · · ), (4.1)
where α1, α2, · · · , αm run respectively over all elements of F∗
q . Here we do
not specify the ordering of the components of wm, but we assume that
some ordering is fixed.
Theorem 4.1 ([7]). Let λ be the canonical additive character of Fq, and
let β ∈ F∗
q. Then
∑
α∈Fq−{0,1}
λ(
β
α2 + α
) = K(λ;β) − 1. (4.2)
Proposition 4.2. For each β ∈ Fq, let
σ(m, q;β) = |{(α1, · · · , αm) ∈ (F∗
q)m|α1+· · ·+αm+α−1
1 +· · ·+α−1
m =β}|
(Note that σ(m, q;β) is the number of components with those equal to β
in the vector wm (cf. (4.1)). Then
(1) σ(m, q;β) =
∑
λ(α1+· · ·+αm)+q−1{(q−1)m+(−1)m+1}, (4.3)
where the sum in (4.3) runs over all α1, · · · , αm ∈ F∗
q, satisfying α−1
1 +
· · · + α−1
m = β.
(2) σ(2, q;β) =
{
2q − 3, if β = 0,
K(λ;β−1) + q − 3, if β 6= 0.
(4.4)
Proof. (1) can be proved just as Proposition 2.1(cf. [5], Proposition 11).
The details are left to the reader.
(2) If m = 2, from (4.3)
σ(2, q;β) =
∑
λ(α1 + α2) + q − 2, (4.5)
where α1 and α2 run over all elements in F∗
q , satisfying α−1
1 + α−1
2 = β.
D. S. Kim 225
If β = 0, then the result is clear. Assume now that β 6= 0. Then the sum
in (4.5) is
∑
α1∈Fq−{0,β−1}
λ(α1 + (α−1
1 + β)−1)
=
∑
α1∈Fq−{0,β}
λ(α−1
1 + (α1 + β)−1) (α1 → α−1
1 )
=
∑
α1∈Fq−{0,1}
λ(
β−1
α2
1 + α1
) (α1 → βα1)
= K(λ;β−1) − 1 (cf.(4.2)).
The binary linear code Dm is defined as
Dm = {u ∈ F
N2
2 |u · wm = 0},
where the dot denotes the usual inner product in FN2
q .
Remark 4.3. Clearly, the binary linear codes C1 and D1 coincide.
In view of Theorem 2.3, the dual D⊥
m of Dm is given by
D⊥
m = {d(a)=(· · ·, tr(a(α1+· · ·+αm+α−1
1 +· · ·+α−1
m )), · · · )|a∈Fq}.
(4.6)
Lemma 4.4. (q − 1)m > 2mq
m
2 , for all m ∈ Z>0 and q = 2r > 8.
Proof. This can be shown, for example, by induction on m.
Proposition 4.5. For q = 2r, with r > 3, the map Fq → D⊥
m(a 7→ d(a))
is an F2-linear isomorphism.
Proof. The map is clearly F2-linear and onto. Let a be in the kernel
of the map. Then tr(a(α1 + · · · + αm + α−1
1 + · · · + α−1
m )) = 0, for all
α1, · · · , αm ∈ F∗
q . Suppose that a 6= 0. Then, on the one hand,
∑
α
1
,··· ,αm∈F∗
q
(−1)tr(a(α
1
+···+αm+α−1
1
+···+α−1
m )) = (q − 1)m = N2. (4.7)
On the other hand, (4.7) is equal to K(λ; a)m, and so from Weil’s estimate
(i.e. (1.1) with m = 1) we get
(q − 1)m
6 2mq
m
2 .
But this is impossible for q > 8, in view of Lemma 4.4.
226 m-multiple power moments of Kloosterman sums
5. Recursive formulas for m-multiple power moments
of Kloostermann sums
We are now ready to derive, via Pless power moment identity, a
recursive formula for the m-multiple power moments of Kloosterman
sums in terms of the frequencies of weights in Dm.
Lemma 5.1. For a ∈ F∗
q, the Hamming weight w(d(a)) of d(a) (cf. (4.6))
can be expressed as follows:
w(d(a)) =
N2
2
− 1
2
K(λ; a)m, with N2 = (q − 1)m. (5.1)
Proof. This can be shown exactly as the proof of Lemma 3.3.
Corollary 5.2. For m = 2,
w(d(a)) =
1
2
(q2 − 3q + 1 −K2(λ; a)) (cf.(1.14)). (5.2)
The same argument leading to Proposition 3.4 shows the next propo-
sition.
Proposition 5.3. Let {Dm,j}N2
j=0 be the weight distribution of Dm, where
Dm,j denotes the frequency of the codewords with weight j in Dm. Then
Dm,j =
∑ ∏
β∈Fq
(
σ(m, q;β)
νβ
)
, (5.3)
where the sum runs over all the sets of integers {νβ}β∈Fq
(0 6 νβ 6
σ(m, q;β)), satisfying
∑
β∈Fq
νβ = j, and
∑
β∈Fq
νββ = 0.
Corollary 5.4. Let {D2,j}(q−1)2
j=0 be the weight distribution of D2, and let
q = 2r, with r > 2. Then, in view of Theorem 1.3 and (4.4), we have
D2,j =
∑
(
2q − 3
ν0
)
∏
β∈F∗
q
(
K(λ;β−1) + q − 3
νβ
)
=
∑
(
2q − 3
ν0
)
∏
|t|<2
√
q
t≡−1(4)
∏
K(λ;β−1)=t
(
t+ q − 3
νβ
)
,
(5.4)
D. S. Kim 227
where the sum runs over all the sets of nonnegative integers {νβ}β∈Fq
satisfying
∑
β∈Fq
νβ = j and
∑
β∈Fq
νββ = 0.
From now on, we will assume that r > 3, and hence every codeword
in D⊥
m can be written as d(a), for a unique a ∈ Fq(cf. Proposition 4.5).
We now apply the Pless power moment identity in (3.1) to D⊥
m, in
order to obtain the result in Theorem 1.1 (1) about a recursive formula.
Then the left hand side of that identity in (3.1) is equal to
∑
a∈F∗
q
w(d(a))h, (5.5)
with w(d(a)) given by (5.1). So (5.5) is seen to be equal to
∑
a∈F∗
q
w(d(a))h =
1
2h
h
∑
l=0
(−1)l
(
h
l
)
Nh−l
2 MKml. (5.6)
On the other hand, noting that dimF2
Dm = r(cf. Proposition 4.5) the
right hand side of the Pless moment identity(cf. (3.1)) becomes
q
min{N2,h}
∑
j=0
(−1)jDm,j
h
∑
t=j
t!S(h, t)2−t
(
N2 − j
N2 − t
)
. (5.7)
Our result in (1.6) follows now by equating (5.6) and (5.7).
Remark 5.5. If m = 2, from the alternative expression of w(d(a)) in (5.2)
we see that (5.5) can also be given as
∑
a∈F∗
q
w(d(a))h =
1
2h
h
∑
l=0
(−1)l
(
h
l
)
(q2 − 3q + 1)h−lMK l
2. (5.8)
References
[1] L. Carlitz, Gauss sums over finite fields of order 2n, Acta. Arith. 15(1969), 247–265.
[2] L. Carlitz, A note on exponential sums, Pacific J. Math. 30(1969), 35–37.
[3] R. J. Evans, Seventh power moments of Kloosterman sums, Israel J. Math.
175(2010), 349–362.
[4] K. Hulek, J. Spandaw, B. van Geemen, and D. van Straten, The modularity of
the Barth-Nieto quintic and its relatives, Adv. Geom. 1(2001), 263-289.
228 m-multiple power moments of Kloosterman sums
[5] D. S. Kim, Codes associated with special linear groups and power moments of
multi-dimensional Kloosterman sums, Ann. Mat. Pura Appli. 190(2011), 61-76.
[6] D. S. Kim, Infinite families of recursive formulas generating power moments of
ternary Kloosterman sums with square arguments arising from symplectic groups,
Adv. Math. Commun. 3(2009), 167–178.
[7] D. S. Kim, Codes associated with O+(2n, 2r) and power moments of Kloosterman
sums, Integers 12(2012), 237–257.
[8] H. D. Kloosterman, On the representation of numbers in the form ax2 + by2 +
cz2 + dt2, Acta Math. 49(1926), 407-464.
[9] G. Lachaud and J. Wolfmann, The weights of the orthogonals of the extended
quadratic binary Goppa codes, IEEE Trans. Inform. Theory 36(1990), 686-692.
[10] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia Math. Appl.20, Cambridge
University Pless, Cambridge, 1987.
[11] R. Livné, Motivic orthogonal two-dimensional representations of Gal(Q/Q), Israel
J. Math. 92(1995), 149-156.
[12] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes,
North-Holland, Amsterdam, 1998.
[13] M. Moisio, The moments of a Kloosterman sum and the weight distribution of a
Zetterberg-type binary cyclic code, IEEE Trans. Inform. Theory 53(2007), 843-847.
[14] M. Moisio, On the duals of binary hyper-Kloosterman codes, SIAM J. Disc. Math.
22(2008), 273-287.
[15] M. Moisio, K. Ranto, M. Rinta-aho and Väänänen, On the weight distribution of the
duals of irreducible cyclic codes, cyclic codes with two zeros and hyper-Kloosterman
codes, Adv. Appl. Discrete Math. 3(2009), 155-164.
[16] C. Peters, J. Top, and M. van der Vlugt, The Hasse zeta function of a K3 surface
related to the number of words of weight 5 in the Melas codes, J. Reine Angew.
Math. 432(1992), 151-176.
[17] H. Salié, Über die Kloostermanschen Summen S(u, v; q),Math. Z. 34(1931), 91-109.
[18] R. Schoof and M. van der Vlugt, Hecke operators and the weight distributions of
certain codes, J. Combin. Theory Ser. A 57(1991), 163-186.
Contact information
Dae San Kim Department of Mathematics, Sogang University,
Seoul 121-742, South Korea
E-Mail(s): dskim@sogang.ac.kr
Received by the editors: 23.10.2010
and in final form 25.01.2015.
|