© Hindawi Publishing Corp.
NOTE ON THE QUADRATIC GAUSS SUMS
GEORGE DANAS (Received 17 March 2000)
Abstract.Let pbe an odd prime and {χ(m)=(m/p)},m=0,1,...,p−1 be a finite arithmetic sequence with elements the values of a Dirichlet characterχmodpwhich are defined in terms of the Legendre symbol(m/p),(m,p)=1. We study the relation between the Gauss and the quadratic Gauss sums. It is shown that the quadratic Gauss sumsG(k;p) are equal to the Gauss sumsG(k,χ)that correspond to this particular Dirichlet charac- terχ. Finally, using the above result, we prove that the quadratic Gauss sumsG(k;p), k=0,1,...,p−1 are the eigenvalues of the circulantp×pmatrixXwith elements the terms of the sequence{χ(m)}.
2000 Mathematics Subject Classification. Primary 11L05; Secondary 11T24, 11L10.
1. Introduction. The notions of Gauss and quadratic Gauss sums play an important role in number theory with many applications [10]. In particular, they are used as tools in the proofs of quadratic, cubic, and biquadratic reciprocity laws [5, 7].
In this article, we study the relation between the quadratic Gauss sums and the Gauss sums related to a particular Dirichlet character defined in terms of the Legendre symbol and prove that the Gauss sumsG(k,χ),k=0,1,...,p−1 which correspond to the Dirichlet characterχ(m)=(m/p)are actually the quadratic Gauss sumsG(k;p), (k,p)=1.
More precisely, consider the finite arithmetic sequence{χ(m)=(m/p)}with ele- ments the values of a Dirichlet characterχmodpwhich are defined in terms of the Legendre symbol (m/p), (m,p)=1 and a circulantp×p matrixX with elements these values. Iff (x)is a polynomial of degreep−1 with coefficients the elements of the arithmetic sequence{χ(m)},m=0,1,...,p−1, then X=f (T ), whereT is a suitablep×pcirculant matrix, namely the rotational matrix;T is orthogonal, diago- nalizable with eigenvalues thepth roots of unity. In addition, the matricesX,Thave the same eigenvectors while ifλis an eigenvalue ofT, thenf (λ)is the eigenvalue of Xthat corresponds to the same eigenvector [3, 12, 13].
Finally, using the above results, we give an algebraic interpretation of the quadratic Gauss sums, which also leads to a different way of computing them, by proving that they are the eigenvalues of the circulantp×pmatrixX.
2. Preliminaries. For an extended overviewon eigenvalues and eigenvectors the reader may consult [4, 8, 11] while for quadratic residues, Legendre symbol, character functions, and Dirichlet characters [1, 5, 7].
LetCbe the set of complex numbers,Aann×nmatrix with entries inCand f (x)=anxn+···+a1x+a0, ai∈C, i=0,1,...,n (2.1) be a polynomial of degreen, wherenis an integer greater than 1.
Proposition2.1. Ifλis an eigenvalue of then×nmatrixAthat corresponds to the eigenvectorv, then then×nmatrix
f (A)=anAn+···+a1A+a0In (2.2) has
f (λ)=anλn+···+a1λ+a0 (2.3) as an eigenvalue that corresponds to the same eigenvectorv.
Corollary2.2. If
PA(λ)= λ−λ1
···
λ−λn
(2.4) is the characteristic polynomial of the matrixAwith eigenvaluesλ1,...,λn, then
Pf (A)(λ)= λ−f
λ1
···
λ−f λn
(2.5) is the characteristic polynomial of the matrixf (A).
Proposition2.3. If ann×nmatrixAhasndistinct eigenvalues, then so has the matrixf (A). Moreover, if the matrixAis diagonalized by ann×nmatrixS, thenf (A) is also diagonalized byS.
Definition2.4. Letmbe an integer greater than 1, and suppose that(m,n)=1.
Ifx2≡n modmis soluble, then we callna quadratic residue modm; otherwise we callna quadratic nonresidue modm.
Definition 2.5(Legendre’s symbol). Let p be an odd prime, and suppose that pn. We let
n p
=
1 ifnis a quadratic residue modp,
−1 ifnis a quadratic nonresidue modp. (2.6) It is easy to see that ifn≡n modpandpn, then(n/p)=(n/p)which implies that the Legendre symbol is periodic with periodp.
Let now{ai},i=0,1,...,n−1 be a finite arithmetic sequence inC.
Definition2.6. Ann×nmatrix
A=
a0 a1 · · an−1
an−1 a0 · · an−2
· · · · ·
a1 a2 · · a0
(2.7)
whose rows come by cyclic permutations to the right of the terms of the arithmetic sequence{ai},i=0,1,...,n−1 is called a circulant matrix.
In case that
ai=
1 ifi=1,
0 otherwise, (2.8)
the matrixAbecomes
T=
0 1 0 · · 0
0 0 1 · · 0
· · · · · ·
0 0 0 · 0 1
1 0 0 · · 0
. (2.9)
Then×n matrixT, which is called the rotational matrix, is orthogonal, that is, T−1=T, such thatTn=Inand having as eigenvalues thenth roots of unity [3, 12].
Moreover,T is diagonalizable and ifW is then×nmatrix whose columns are the eigenvectors ofT,
W(k)=
1wkw2k···w(n−1)k
, k=0,1,...,n−1, (2.10)
wherew=e2πi/n, then
W−1T W=
1 0 0 · · 0
0 w 0 · · 0
0 0 w2 · · 0
· · · · · ·
0 0 0 · · wn−1
. (2.11)
3. Gauss and quadratic Gauss sums. In this section, we study the relation between the quadratic Gauss sums and the Gauss sums related to a particular Dirichlet char- acter defined in terms of the Legendre symbol.
Definition3.1. For every Dirichlet characterχmodnthe sum
G(k,χ)=
n−1
m=0
χ(m)e2πimk/n, k=0,1,...,n−1, (3.1)
is called the Gauss sum that corresponds toχ.
Definition3.2. Ifk,nare integers withn >0, then the trigonometric sum
G(k;n)=
n−1
r=0
e2πir2k/n, (k,n)=1, (3.2)
is called quadratic Gauss sum.
Theorem3.3. Ifpis an odd prime withχ(m)=(m/p),(m,p)=1, then
G(k;p)=
p−1
r=0
e2πir2k/p=
p−1
m=0
χ(m)e2πimk/p=G(k,χ), (k,p)=1, (3.3)
Proof. The number of solutions of the congruence
r2≡mmodp (3.4)
is
1+
m p
(3.5) and therefore
G(k;p)=
p−1
r=0
e2πir2k/p=
p−1
m=0
1+
m p
e2πimk/p
=
p−1
m=0
m p
e2πimk/p=
p−1
m=0
χ(m)e2πimk/p=G(k,χ)
(3.6)
which is the required result.
4. The quadratic Gauss sums as eigenvalues of a suitable circulant matrix. In this section, we give an algebraic interpretation of the quadratic Gauss sums that correspond to a Dirichlet characterχmodpwhich is defined in terms of the Legendre symbol(m/p),(m,p)=1. In fact, we prove that the quadratic Gauss sumsG(k;p), (k,p)=1, are the eigenvalues of the circulantp×pmatrixXwith elements the values χ(m)=(m/p),(m,p)=1.
Let nown=p be an odd prime, χ(m)=(m/p) be a Dirichlet character modp that is defined in terms of the Legendre symbol(m/p),(m,p)=1 and consider the circulantp×pmatrix
X=
χ(0) χ(1) · · χ(p−1) χ(p−1) χ(0) · · χ(p−2)
· · · · ·
χ(1) χ(2) · · χ(0)
(4.1)
whose rows come by cyclic permutation to the right of the terms of the arithmetic sequence{χ(m)},m=0,1,...,p−1.
Proposition 4.1. If f (x)= χ(0)+χ(1)x+ ··· +χ(p−1)xp−1 is a polynomial with coefficients the terms of the arithmetic sequence{χ(m)},m=0,1,...,p−1, then X=f (T ).
Proof. We can writeT=(epe1···ep−1), since the columns of T are the vectors ep,e1,...,ep−1relative to the standard basis ofCp.
Observe also that T2=
ep−1ep···ep−2
, ..., Tp=
e1e2···ep
=Ip. (4.2)
Therefore,
f (T )=χ(0)Ip+χ(1)T+···+χ(p−1)Tp−1
=χ(0)
e1e2···ep +χ(1)
epe1···ep−1
+···+χ(p−1)
e2e3···e1
=
χ(0) χ(1) · · χ(p−1) χ(p−1) χ(0) · · χ(p−2)
· · · · ·
χ(1) χ(2) · · χ(0)
=X.
(4.3)
Thus, according to Proposition 2.1, the matrixXhas the same eigenvectors withT, which are the row vectors
v0=(11···1), v1=
1w···wp−1
, ..., vp−1=
1wp−1···w(p−1)2
, (4.4) wherew=e2πi/p, while its corresponding eigenvalues are
f (1)=χ(0)+χ(1)+···+χ(p−1) f (w)=χ(0)+χ(1)w+···+χ(p−1)wp−1 f
w2
=χ(0)+χ(1)w2+···+χ(p−1)w2(p−1) ...
f wp−1
=χ(0)+χ(1)wp−1+···+χ(p−1)w(p−1)2.
(4.5)
Combining now the above results and Theorem 3.3, we obtain the following theorem.
Theorem4.2. The eigenvalues of thep×pcirculant matrixXare G(k;p)=G(k,χ)=f
wk
=
p−1
m=0
χ(m)e2πimk/p, k=0,1,...,p−1, (4.6)
the quadratic Gauss sums.
Notice that, equations (4.5) can be written in matrix notation as
f (1) f (w) f
w2
·
· f
wp−1
=
1 1 1 · · 1
1 w w2 · · wp−1
1 w2 w4 · · w2(p−1)
· · · · · ·
· · · · · ·
1 wp−1 w2(p−1) · · w(p−1)2
χ(0) χ(1) χ(2)
·
· χ(p−1)
. (4.7)
Furthermore, thep×pmatrix
W=
1 1 1 · · 1
1 w w2 · · wp−1
1 w2 w4 · · w2(p−1)
· · · · · ·
· · · · · ·
1 wp−1 w2(p−1) · · w(p−1)2
(4.8)
whose columns are the eigenvectors ofX, diagonalizeX, that is,
W−1XW=
f (1) 0 0 · · 0
0 f (w) 0 · · 0
0 0 f
w2
· · 0
· · · · · ·
· · · · · ·
0 0 0 · · f
wp−1
. (4.9)
Remark4.3. Since every Dirichlet characterχ modp is periodic modp, it has a finite Fourier expansion [1, 7],
χ(m)=
p−1
k=0
αp(k)e2πimk/p, m=0,1,...,p−1, (4.10)
where the coefficientsαp(k)are given by
αp(k)=1 p
p−1
m=0
χ(m)e−2πimk/p, k=0,1,...,p−1 (4.11)
or equivalently
αp(k)= 1
pG(−k,χ). (4.12)
If we consider now the Dirichlet characterχ(m)=(m/p)which is defined in terms of the Legendre symbol(m/p),(m,p)=1, then we deduce that the quadratic Gauss sumG(k;p)=G(k,χ), k=0,1,...,p−1 is the Fourier transform ofχevaluated atk.
5. Conclusion. We have shown that the quadratic Gauss sums G(k;p), (k,p)=1 can be considered as the eigenvalues of a suitable circulantp×p matrixXwith el- ements the terms of the arithmetic sequence{χ(m)=(m/p)}. This leads both to an algebraic characterization and also to a different way of computing the quadratic Gauss sums by calculating the roots of the characteristic polynomial that correspond to the matrixX.
Moreover, this newpoint of viewfor the quadratic Gauss sums gives, in many cases, an easier way to calculate them (to my best knowledge) instead of a direct computa- tion, since one can find several methods for computing the eigenvalues of a matrix or the roots of a polynomial [2, 6, 9].
References
[1] T. M. Apostol,Introduction to Analytic Number Theory, Undergraduate Texts in Mathe- matics, Springer-Verlag, NewYork, Heidelberg, 1976. MR 55#7892. Zbl 335.10001.
[2] A. Björck and G. Dahlquist,˙ Numerical Methods, Translated from the Swedish by Ned Anderson. Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., En- glewood Cliffs, N.J., 1974. MR 51#4620.
[3] P. J. Davis,Circulant Matrices, A Wiley-Interscience Publication. Pure and Applied Math- ematics, John Wiley & Sons, NewYork, Chichester, Brisbane, 1979. MR 81a:15003.
Zbl 418.15017.
[4] W. Greub,Linear Algebra, 4th ed., Graduate Texts in Mathematics, no. 23, Springer- Verlag, NewYork, Berlin, 1975. MR 51#5615. Zbl 317.15002.
[5] K. F. Ireland and M. I. Rosen,AClassical Introduction to Modern Number Theory.Revised edition ofElements of Number Theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, NewYork, Berlin, 1982. MR 83g:12001. Zbl 482.10001.
[6] M. L. James, G. M. Smith, and J. C. Wolford,Applied Numerical Methods for Digital Com- putation, Harper & Row, New York, 1985.
[7] S. Lang,Algebraic Number Theory, Addison-Wesley Publishing Co., Inc., Reading, Mass., London, Don Mills, Ont., 1970. MR 44#181. Zbl 211.38404.
[8] D. Lay,Linear Algebra and its Applications, Addison-Wesley, 1994.
[9] W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling,Numerical Recipes in Pascal, The art of scientific computing, Cambridge University Press, Cambridge, NewYork, 1989. MR 91a:65001. Zbl 698.65001.
[10] M. R. Schroeder, Number Theory in Science and Communication. With applications in cryptography, physics, biology, digital information, and computing, Springer Series in Information Sciences, vol. 7, Springer-Verlag, Berlin, NewYork, 1984.
MR 85j:11003. Zbl 542.10001.
[11] G. E. Shilov, Linear Algebra. Revised English edition. Translated from the Russian and edited by Richard A. Silverman, Dover Publications, Inc., NewYork, 1977.
MR 57#6043.
[12] H. Terzidis and G. Danas,The spectral analysis of the discrete Fourier transform, submit- ted.
[13] ,The spectral analysis of the periods of the inverses of integers, J. Inst. Math. Com- put. Sci. Comput. Sci. Ser.10(1999), no. 1, 61–69. CMP 1 704 539.
George Danas: Technological Educational Institution of Thessaloniki, School of Sciences, Department of Mathematics, P.O. Box14561, GR-54101Thessaloniki, Greece
E-mail address:[email protected]
Special Issue on
Time-Dependent Billiards
Call for Papers
This subject has been extensively studied in the past years for one-, two-, and three-dimensional space. Additionally, such dynamical systems can exhibit a very important and still unexplained phenomenon, called as the Fermi acceleration phenomenon. Basically, the phenomenon of Fermi accelera- tion (FA) is a process in which a classical particle can acquire unbounded energy from collisions with a heavy moving wall.
This phenomenon was originally proposed by Enrico Fermi in 1949 as a possible explanation of the origin of the large energies of the cosmic particles. His original model was then modified and considered under different approaches and using many versions. Moreover, applications of FA have been of a large broad interest in many different fields of science including plasma physics, astrophysics, atomic physics, optics, and time-dependent billiard problems and they are useful for controlling chaos in Engineering and dynamical systems exhibiting chaos (both conservative and dissipative chaos).
We intend to publish in this special issue papers reporting research on time-dependent billiards. The topic includes both conservative and dissipative dynamics. Papers dis- cussing dynamical properties, statistical and mathematical results, stability investigation of the phase space structure, the phenomenon of Fermi acceleration, conditions for having suppression of Fermi acceleration, and computational and numerical methods for exploring these structures and applications are welcome.
To be acceptable for publication in the special issue of Mathematical Problems in Engineering, papers must make significant, original, and correct contributions to one or more of the topics above mentioned. Mathematical papers regarding the topics above are also welcome.
Authors should follow the Mathematical Problems in Engineering manuscript format described at
http://www .hindawi.com/journals/mpe/. Prospective authors shouldsubmit an electronic copy of their complete manuscript through the journal Manuscript Tracking System at
http://mts.hindawi.com/
according to the following timetable:
Manuscript Due December 1, 2008 First Round of Reviews March 1, 2009 Publication Date June 1, 2009
Guest Editors
Edson Denis Leonel,
Departamento de Estatística, Matemática Aplicada e Computação, Instituto de Geociências e Ciências Exatas, Universidade Estadual Paulista, Avenida 24A, 1515 Bela Vista, 13506-700 Rio Claro, SP, Brazil ; [email protected]
Alexander Loskutov,
Physics Faculty, Moscow State University, Vorob’evy Gory, Moscow 119992, Russia;
[email protected]
Hindawi Publishing Corporation http://www.hindawi.com
