Dedekind sum

Last updated

In mathematics, Dedekind sums are certain sums of products of a sawtooth function, and are given by a function D of three integer variables. Dedekind introduced them to express the functional equation of the Dedekind eta function. They have subsequently been much studied in number theory, and have occurred in some problems of topology. Dedekind sums have a large number of functional equations; this article lists only a small fraction of these.

Contents

Dedekind sums were introduced by Richard Dedekind in a commentary on fragment XXVIII of Bernhard Riemann's collected papers.

Definition

Define the sawtooth function as

We then let

be defined by

the terms on the right being the Dedekind sums. For the case a =1, one often writes

s(b, c) = D(1, b; c).

Simple formulae

Note that D is symmetric in a and b, and hence

and that, by the oddness of (( )),

D(−a, b; c) = −D(a, b; c),
D(a, b; −c) = D(a, b; c).

By the periodicity of D in its first two arguments, the third argument being the length of the period for both,

D(a, b; c) = D(a+kc, b+lc; c), for all integers k,l.

If d is a positive integer, then

D(ad, bd; cd) = dD(a, b; c),
D(ad, bd; c) = D(a, b; c), if (d, c) = 1,
D(ad, b; cd) = D(a, b; c), if (d, b) = 1.

There is a proof for the last equality making use of

Furthermore, az = 1 (mod c) implies D(a, b; c) = D(1, bz; c).

Alternative forms

If b and c are coprime, we may write s(b, c) as

where the sum extends over the c-th roots of unity other than 1, i.e. over all such that and .

If b,c > 0 are coprime, then

Reciprocity law

If b and c are coprime positive integers then

Rewriting this as

it follows that the number 6c s(b,c) is an integer.

If k = (3, c) then

and

A relation that is prominent in the theory of the Dedekind eta function is the following. Let q = 3, 5, 7 or 13 and let n = 24/(q 1). Then given integers a, b, c, d with ad  bc = 1 (thus belonging to the modular group), with c chosen so that c = kq for some integer k> 0, define

Then nδ is an even integer.

Rademacher's generalization of the reciprocity law

Hans Rademacher found the following generalization of the reciprocity law for Dedekind sums: [1] If a, b, and c are pairwise coprime positive integers, then

Hence, the above triple sum vanishes if and only if (a, b, c) is a Markov triple, i.e. a solution of the Markov equation

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

<span class="mw-page-title-main">Chinese remainder theorem</span> Theorem for solving simultaneous congruences

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

<span class="mw-page-title-main">Quadratic reciprocity</span> Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

<i>p</i>-adic number Number system extending the rational numbers

In number theory, given a prime number p, the p-adic numbers form an extension of the rational numbers which is distinct from the real numbers, though with some similar properties; p-adic numbers can be written in a form similar to decimals, but with digits based on a prime number p rather than ten, and extending to the left rather than to the right. Formally, given a prime number p, a p-adic number can be defined as a series

<span class="mw-page-title-main">Floor and ceiling functions</span> Nearest integers from a number

In mathematics and computer science, the floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x, denoted x or floor(x). Similarly, the ceiling function maps x to the smallest integer greater than or equal to x, denoted x or ceil(x).

In number theory, an additive function is an arithmetic function f(n) of the positive integer variable n such that whenever a and b are coprime, the function applied to the product ab is the sum of the values of the function applied to a and b:

<span class="mw-page-title-main">Root of unity</span> Number that has an integer power equal to 1

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

In analytic number theory and related branches of mathematics, a complex-valued arithmetic function is a Dirichlet character of modulus if for all integers and :

  1. that is, is completely multiplicative.
  2. ; that is, is periodic with period .

The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size N = N1N2 as a two-dimensional N1×N2 DFT, but only for the case where N1 and N2 are relatively prime. These smaller transforms of size N1 and N2 can then be evaluated by applying PFA recursively or by using some other FFT algorithm.

<span class="mw-page-title-main">Modular group</span> Orientation-preserving mapping class group of the torus

In mathematics, the modular group is the projective special linear group of 2 × 2 matrices with integer coefficients and determinant 1. The matrices A and A are identified. The modular group acts on the upper-half of the complex plane by fractional linear transformations, and the name "modular group" comes from the relation to moduli spaces and not from modular arithmetic.

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.

<span class="mw-page-title-main">Weierstrass elliptic function</span> Class of mathematical functions

In mathematics, the Weierstrass elliptic functions are elliptic functions that take a particularly simple form. They are named for Karl Weierstrass. This class of functions are also referred to as ℘-functions and they are usually denoted by the symbol ℘, a uniquely fancy script p. They play an important role in the theory of elliptic functions. A ℘-function together with its derivative can be used to parameterize elliptic curves and they generate the field of elliptic functions with respect to a given period lattice.

The Basel problem is a problem in mathematical analysis with relevance to number theory, concerning an infinite sum of inverse squares. It was first posed by Pietro Mengoli in 1650 and solved by Leonhard Euler in 1734, and read on 5 December 1735 in The Saint Petersburg Academy of Sciences. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate fame when he was twenty-eight. Euler generalised the problem considerably, and his ideas were taken up more than a century later by Bernhard Riemann in his seminal 1859 paper "On the Number of Primes Less Than a Given Magnitude", in which he defined his zeta function and proved its basic properties. The problem is named after Basel, hometown of Euler as well as of the Bernoulli family who unsuccessfully attacked the problem.

In mathematics, a Kloosterman sum is a particular kind of exponential sum. They are named for the Dutch mathematician Hendrik Kloosterman, who introduced them in 1926 when he adapted the Hardy–Littlewood circle method to tackle a problem involving positive definite diagonal quadratic forms in four as opposed to five or more variables, which he had dealt with in his dissertation in 1924.

In mathematics, a Witt vector is an infinite sequence of elements of a commutative ring. Ernst Witt showed how to put a ring structure on the set of Witt vectors, in such a way that the ring of Witt vectors over the finite field of order is isomorphic to , the ring of -adic integers. They have a highly non-intuitive structure upon first glance because their additive and multiplicative structure depends on an infinite set of recursive formulas which do not behave like addition and multiplication formulas for standard p-adic integers.

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x3p is solvable if and only if x3q is solvable.

In number theory, quadratic integers are a generalization of the usual integers to quadratic fields. Quadratic integers are algebraic integers of degree two, that is, solutions of equations of the form

In number theory, the prime omega functions and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. That is, if we have a prime factorization of of the form for distinct primes , then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.

References

  1. Rademacher, Hans (1954). "Generalization of the reciprocity formula for Dedekind sums". Duke Mathematical Journal . 21: 391–397. doi:10.1215/s0012-7094-54-02140-7. Zbl   0057.03801.

Further reading