Exponential sum
Encyclopedia
In mathematics
, an exponential sum may be a finite Fourier series
(i.e. a trigonometric polynomial
), or other finite sum formed using the exponential function
, usually expressed by means of the function
Therefore a typical exponential sum may take the form
summed over a finite sequence of real number
s xn.
it is the same as allowing exponents that are complex number
s. Both forms are certainly useful in applications. A large part of twentieth century analytic number theory
was devoted to finding good estimates for these sums, a trend started by basic work of Hermann Weyl
in diophantine approximation
.
is trivially estimated by the number N of terms. That is, the absolute value
by the triangle inequality
, since each summand has absolute value 1. In applications one would like to do better. That involves proving some cancellation takes place, or in other words that this sum of complex numbers on the unit circle
is not of numbers all with the same argument
. The best that is reasonable to hope for is an estimate of the form
which signifies, up to the implied constant in the big O notation
, that the sum resembles a random walk
in two dimensions.
Such an estimate can be considered ideal; it is unattainable in many of the major problems, and estimates
have to be used, where the o(N) function represents only a small saving on the trivial estimate. A typical 'small saving' may be a factor of log(N), for example. Even such a minor-seeming result in the right direction has to be referred all the way back to the structure of the initial sequence xn, to show a degree of randomness
. The techniques involved are ingenious and subtle.
A variant of 'Weyl differencing' investigated by Weyl involving a generating exponential sum
Was previously studied by Weyl himself, he developed a method to express the sum as the value
, where 'G' can be defined via a linear differential equation similar to Dyson equation obtained via summation by parts.
where ƒ is a smooth function, you could use the Euler–Maclaurin formula to convert the series into an integral, plus some corrections involving derivatives of S(x), then for large values of a you could use "stationary phase" method to calculate the integral and give an approximate evaluation of the sum. Major advances in the subject were Van der Corput's method (c. 1920), related to the principle of stationary phase, and the later Vinogradov method (c.1930).
The large sieve method (c.1960), the work of many researchers, is a relatively transparent general principle; but no one method has general application.
A basic distinction is between a complete exponential sum, which is typically a sum over all residue classes modulo
some integer N (or more general finite ring
), and an incomplete exponential sum where the range of summation is restricted by some inequality. Examples of complete exponential sums are Gauss sum
s and Kloosterman sums; these are in some sense finite field
or finite ring analogues of the gamma function
and some sort of Bessel function
, respectively, and have many 'structural' properties. An example of an incomplete sum is the partial sum of the quadratic Gauss sum (indeed, the case investigated by Gauss
). Here there are good estimates for sums over shorter ranges than the whole set of residue classes, because, in geometric terms, the partial sums approximate a Cornu spiral; this implies massive cancellation.
Auxiliary types of sums occur in the theory, for example character sum
s; going back to Harold Davenport
's thesis. The Weil conjectures
had major applications to complete sums with domain restricted by polynomial conditions (i.e., along an algebraic variety
over a finite field).
One of the most general types of exponential sum is the Weyl sum, with exponents 2πif(n) where f is a fairly general real-valued smooth function
. These are the sums implicated in the distribution of the values
according to Weyl's equidistribution criterion. A basic advance was Weyl's inequality for such sums, for polynomial f.
There is a general theory of exponent pairs, which formulates estimates. An important case is where f is logarithmic, in relation with the Riemann zeta function. See also equidistribution theorem
.
. Then
the quadratic Gauss sum
is given by
where the square roots are taken to be positive.
This is the ideal degree of cancellation one could hope for without any a priori knowledge of the structure of the sum, since it matches the scaling of a random walk
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, an exponential sum may be a finite Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...
(i.e. a trigonometric polynomial
Trigonometric polynomial
In the mathematical subfields of numerical analysis and mathematical analysis, a trigonometric polynomial is a finite linear combination of functions sin and cos with n a natural number. The coefficients may be taken as real numbers, for real-valued functions...
), or other finite sum formed using the exponential function
Exponential function
In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...
, usually expressed by means of the function
Therefore a typical exponential sum may take the form
summed over a finite sequence of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s xn.
Formulation
If we allow some real coefficients an, to get the formit is the same as allowing exponents that are complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
s. Both forms are certainly useful in applications. A large part of twentieth century analytic number theory
Analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Dirichlet's introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic...
was devoted to finding good estimates for these sums, a trend started by basic work of Hermann Weyl
Hermann Weyl
Hermann Klaus Hugo Weyl was a German mathematician and theoretical physicist. Although much of his working life was spent in Zürich, Switzerland and then Princeton, he is associated with the University of Göttingen tradition of mathematics, represented by David Hilbert and Hermann Minkowski.His...
in diophantine approximation
Diophantine approximation
In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers....
.
Estimates
The main thrust of the subject is that a sumis trivially estimated by the number N of terms. That is, the absolute value
Absolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
by the triangle inequality
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....
, since each summand has absolute value 1. In applications one would like to do better. That involves proving some cancellation takes place, or in other words that this sum of complex numbers on the unit circle
Unit circle
In mathematics, a unit circle is a circle with a radius of one. Frequently, especially in trigonometry, "the" unit circle is the circle of radius one centered at the origin in the Cartesian coordinate system in the Euclidean plane...
is not of numbers all with the same argument
Parameter
Parameter from Ancient Greek παρά also “para” meaning “beside, subsidiary” and μέτρον also “metron” meaning “measure”, can be interpreted in mathematics, logic, linguistics, environmental science and other disciplines....
. The best that is reasonable to hope for is an estimate of the form
which signifies, up to the implied constant in the big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
, that the sum resembles a random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
in two dimensions.
Such an estimate can be considered ideal; it is unattainable in many of the major problems, and estimates
have to be used, where the o(N) function represents only a small saving on the trivial estimate. A typical 'small saving' may be a factor of log(N), for example. Even such a minor-seeming result in the right direction has to be referred all the way back to the structure of the initial sequence xn, to show a degree of randomness
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
. The techniques involved are ingenious and subtle.
A variant of 'Weyl differencing' investigated by Weyl involving a generating exponential sum
Was previously studied by Weyl himself, he developed a method to express the sum as the value
, where 'G' can be defined via a linear differential equation similar to Dyson equation obtained via summation by parts.History
If the sum is of the formwhere ƒ is a smooth function, you could use the Euler–Maclaurin formula to convert the series into an integral, plus some corrections involving derivatives of S(x), then for large values of a you could use "stationary phase" method to calculate the integral and give an approximate evaluation of the sum. Major advances in the subject were Van der Corput's method (c. 1920), related to the principle of stationary phase, and the later Vinogradov method (c.1930).
The large sieve method (c.1960), the work of many researchers, is a relatively transparent general principle; but no one method has general application.
Types of exponential sum
Many types of sums are used in formulating particular problems; applications require usually a reduction to some known type, often by ingenious manipulations. Partial summation can be used to remove coefficients an, in many cases.A basic distinction is between a complete exponential sum, which is typically a sum over all residue classes modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
some integer N (or more general finite ring
Finite ring
In mathematics, more specifically abstract algebra, a finite ring is a ring that has a finite number of elements....
), and an incomplete exponential sum where the range of summation is restricted by some inequality. Examples of complete exponential sums are Gauss sum
Gauss sum
In mathematics, a Gauss sum or Gaussian sum is a particular kind of finite sum of roots of unity, typicallyG := G= \sum \chi\cdot \psi...
s and Kloosterman sums; these are in some sense finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
or finite ring analogues of the gamma function
Gamma function
In mathematics, the gamma function is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers...
and some sort of Bessel function
Bessel function
In mathematics, Bessel functions, first defined by the mathematician Daniel Bernoulli and generalized by Friedrich Bessel, are canonical solutions y of Bessel's differential equation:...
, respectively, and have many 'structural' properties. An example of an incomplete sum is the partial sum of the quadratic Gauss sum (indeed, the case investigated by Gauss
Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...
). Here there are good estimates for sums over shorter ranges than the whole set of residue classes, because, in geometric terms, the partial sums approximate a Cornu spiral; this implies massive cancellation.
Auxiliary types of sums occur in the theory, for example character sum
Character sum
In mathematics, a character sum is a sum\Sigma \chi\,of values of a Dirichlet character χ modulo N, taken over a given range of values of n. Such sums are basic in a number of questions, for example in the distribution of quadratic residues, and in particular in the classical question of finding an...
s; going back to Harold Davenport
Harold Davenport
Harold Davenport FRS was an English mathematician, known for his extensive work in number theory.-Early life:...
's thesis. The Weil conjectures
Weil conjectures
In mathematics, the Weil conjectures were some highly-influential proposals by on the generating functions derived from counting the number of points on algebraic varieties over finite fields....
had major applications to complete sums with domain restricted by polynomial conditions (i.e., along an algebraic variety
Algebraic variety
In mathematics, an algebraic variety is the set of solutions of a system of polynomial equations. Algebraic varieties are one of the central objects of study in algebraic geometry...
over a finite field).
One of the most general types of exponential sum is the Weyl sum, with exponents 2πif(n) where f is a fairly general real-valued smooth function
Smooth function
In mathematical analysis, a differentiability class is a classification of functions according to the properties of their derivatives. Higher order differentiability classes correspond to the existence of more derivatives. Functions that have derivatives of all orders are called smooth.Most of...
. These are the sums implicated in the distribution of the values
- ƒ(n) modulo 1,
according to Weyl's equidistribution criterion. A basic advance was Weyl's inequality for such sums, for polynomial f.
There is a general theory of exponent pairs, which formulates estimates. An important case is where f is logarithmic, in relation with the Riemann zeta function. See also equidistribution theorem
Equidistribution theorem
In mathematics, the equidistribution theorem is the statement that the sequenceis uniformly distributed on the unit interval, when a is an irrational number...
.
Example: the quadratic Gauss sum
Let p be an odd prime and let. Thenthe quadratic Gauss sum
Gauss sum
In mathematics, a Gauss sum or Gaussian sum is a particular kind of finite sum of roots of unity, typicallyG := G= \sum \chi\cdot \psi...
is given by
where the square roots are taken to be positive.
This is the ideal degree of cancellation one could hope for without any a priori knowledge of the structure of the sum, since it matches the scaling of a random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
.