Use analytic expressions of constraints in sums or integrals

Quick description

In dealing with sums or integrals involving several parameters linked with constraints of the type $A=B$ , it is often useful to rephrase these by inserting an extra sum or integral which is zero whenever the constraint is not satisfied. In particular, this may help to prove existence of solutions to certain equations by replacing the number of solutions of these equations with an analytic expression which may be successfully manipulated further.

This article is incomplete. This article needs more links and references inside.

Prerequisites

Real analysis and integration theory, complex analysis for some applications. Elementary harmonic analysis (such as Fourier transforms, or Mellin transforms, depending on the type of applications). Some knowledge of the basic properties of elementary arithmetic functions, including Möbius inversion.

General discussion

The idea of the trick is to replace expressions like

$S=\sum_{a,b;\ a=b}{f(a,b)}$

with

$S=\sum_{a,b}{f(a,b)\sum_{c}{g_c(a,b)}}$

where the inner sum has the property that it represents analytically the "Kronecker delta symbol" $\delta(a,b)$ . Recall that $\delta(a,b)=1$ if $a=b$ , while $\delta(a,b)=0$ if $a\not=b$ .

$\sum_{c}{g_c(a,b)}=\delta(a,b).$ (Delta symbol)

The sum over $c$ is often interpreted in terms of harmonic analysis as a sum over suitable harmonics. Different choices might be available, and a crucial part of the argument might be to select the "right" harmonics for the situation at hand. In that case, the relations (Delta symbol) are frequently examples of orthogonality relations.

To go further, one typically will interchange the sums, getting

$S=\sum_{c}{\sum_{a,b}{f(a,b)g_c(a,b)}}$

and then one has to be able to say something about the inner sums. Often, the issue of uniformity with respect to the "harmonic" $c$ will be crucial. Also, it often turns out that there is a "special" harmonic $c_0$ for which the sum

$\sum_{a,b}{f(a,b)g_{c_0}(a,b)}$

is particularly easy to work with, and may represent a "main term" for counting the solution to some equation. Then the main work is to establish that the other sums

$\sum_{a,b}{f(a,b)g_{c}(a,b)}$

are of smaller order of magnitude for $c\not= c_0$ .

It is not necessarily the case that two variables (or more) are involved; similar tricks can be useful to express analytically a single condition (see for instance Example 2).

Example 1: Detecting coprimality conditions

Very often in analytic number theory, one has to deal with (positive) integer variables related by a condition that they be coprime. The Möbius identity below gives a way of treating such conditions.

As an example, a classical question is: "What is the probability that two positive integers be coprime?" Although it is not a probability in the modern sense (and "density" might be a better word), is it somewhat natural to identify this with the limit, as $N\rightarrow +\infty$ , if it exists, of

$S(N)=\frac{1}{N^2}\sum_{a,b\leq N;\ (a,b)=1}{1}$

where $(a,b)$ denotes the gcd of the positive integers $a$ and $b$ .

The conditions $(a,b)=1$ can be detected by the Möbius function $\mu$ which is defined by $\mu(n)=0$ if $n$ is divisible by the square of a prime, and otherwise $\mu(p_1\cdots p_k)=(-1)^k$ for distinct primes $p_i$ , and $\mu(1)=1$ , through the formula

$\delta(n)=\sum_{d\mid n}{\mu(d)}$ (Möbius identity)

where $\delta(n)=\delta(n,1)$ tells whether a positive integer is equal to $1$ or not. (This formula is a special case of the Möbius inversion formula).

Inserting this with $n=(a,b)$ in the sum $S(N)$ and continuing by interchanging the sum, we obtain

$S(N)=\frac{1}{N^2}\sum_{a,b\leq N}{\sum_{d\mid (a,b)}{1}}=N^2\sum_{d\leq N}{\mu(d)\sum_{a,b\leq N; d\mid (a,b)}{1}}.$

For a fixed $d$ , the inner sum counts pairs of integers up to $N$ which are both divisible by $d$ , so it is equal to $(N/d+O(1))^2=N^2/d^2+O(N/d)$ , uniformly for all $d$ , and this gives

$S(N)=\sum_{d\leq N}{\frac{\mu(d)}{d^2}}+O(N^{-1}\sum_{d\leq N}{d^{-1}})$

Since it is well known that

$\sum_{d\leq N}{\frac{1}{d}}=O(\log N)$

and that

$\sum_{d\leq N}{\frac{\mu(d)}{d^2}}=\sum_{n\geq 1}{\frac{\mu(d)}{d^2}}+O(N^{-1})$

we see that

$\lim_{N\rightarrow +\infty}{S(N)}=\sum_{n\geq 1}{\frac{\mu(d)}{d^2}},$

and this is therefore the intuitive probability that two positive integers be coprime. (It is also well-known that

$\sum_{n\geq 1}{\frac{\mu(d)}{d^2}}=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}$

but this is not needed to prove the existence of the limit).

Note. The equation (Möbius identity) is the most common way to treat sums involving coprimality conditions of the variables in analytic number theory. It should be the first thing to try whenever such a condition arises.

Example 2: Detecting squarefreeness

This example is quite similar to the previous one. We now wish to incorporate the constraint that a positive integer $a$ be squarefreewhich means that it is not divisible by $p^2$ for any prime number $p$ and for this we use the Möbius function again by writing

$\sum_{d;\ d^2\mid n}{\mu(d)}=\delta(\square,n)$

which is $1$ if $n$ is the square of an integer, and $0$ otherwise. For instance, for $n=12=2^2\cdot 3$ , the sum is $\mu(1)+\mu(2)=1-1=0$ , and for $n=30=2\cdot 3\cdot 5$ , it is $\mu(1)=1$ .

As an example, consider the probability that $n\geq 1$ be squarefree, interpreted as the limit of

$T(N)=\frac{1}{N}\sum_{n\leq N}{\delta(\square,n)}.$

Introducing the expression above, and exchanging the sum, we obtain

$T(N)=\frac{1}{N}\sum_{d\leq \sqrt{N}}{\mu(d)\sum_{n\leq N/d;\ d^2\mid n}{1}}=\frac{1}{N}\sum_{d\leq \sqrt{N}}{\mu(d)(N/d^2+O(1))}$

and therefore

$\lim_{N\rightarrow +\infty}{T(N)}=\sum_{n\geq 1}{\frac{\mu(d)}{d^2}}=\frac{6}{\pi^2}$

(again!)

Example 3: Detecting congruence conditions

To compute a sum

$\sum_{n\equiv a\text{ mod } q}{a_n}$

restricted by a congruence condition, one may use the orthogonality relations

$\frac{1}{q}\sum_{x\text{ mod } q}{e^{2i\pi x(n-a)/q}}=\delta(n\text{ mod } q,a)$

for "additive" characters.

If, in addition, the sequence $a_n$ is supported on integers coprime with $q$ , one may instead use "multiplicative" characters: those are the group homomorphisms

$\, (\mathbf{Z}/q\mathbf{Z})^{\times}\rightarrow \mathbf{C}^{\times}$

from the finite group of integers coprime with $q$ to the multiplicative group of non-zero complex numbers. There are $\varphi(q)$ distinct such homomorphisms, where $\varphi(q)$ is the Euler function (the cardinality of $(\mathbf{Z}/q\mathbf{Z})^{\times}$ ), and the corresponding orthogonality relation is

$\frac{1}{q}\sum_{\chi}{\chi(x)\overline{\chi(a)}}=\delta(n\text{ mod } q,a)$

for $a$ coprime with $q$ .

This relation is used for instance in proofs of Dirichlet's Theorem that there are infinitely many primes $p\equiv a\text{ mod } q$ if $(a,q)=1$ : one starts by writing that

$\sum_{p\equiv a\text{ mod } q,\ p\leq x}{1}= \frac{1}{\varphi(q)}\sum_{\chi}{\sum_{p\leq x}{\chi(p)\overline{\chi(a)}}}$

and then the inner sums are studied (for instance using Dirichlet generating series).

Example 4: Orthogonality relations

The previous example involves a special case, corresponding to finite cyclic groups, of using the orthogonality relations of characters of a finite group $G$ to expand the delta function at the identity of $G$ in terms of irreducible characters.

For a finite group $G$ , an irreducible linear representation of $G$ is a group homomorphism

$\, G\rightarrow GL(n,\mathbf{C})$

for some $n$ , or equivalently an action of $G$ on $\mathbf{C}^n$ by linear automorphisms, such that there is no subspace $V\subset \mathbf{C}^n$ , except $V=0$ and $V=\mathbf{C}^n$ , which is invariant under all operators $\rho(g)$ , $g\in G$ .

Two such representations $\rho$ and $\tau$ are said to be equivalent if there exists map $T\in GL(n,\mathbf{C})$ such that

$\rho(g)=T\tau(g)T^{-1}$

for all $g\in G$ . It is known that, up to equivalence, there are only finitely many irreducible linear representations of $G$ , in fact exactly as many as there are conjugacy classes in $G$ . They are in fact characterized by their characters, which are the functions

$g\mapsto Tr(\rho(g))$

(clearly, those functions are the same for equivalent representations). Those characters provide a decomposition of the Dirac delta at the identify $1$ of the group

$\delta(g,1)=\frac{1}{|G|}\sum_{\rho}{Tr(\rho(g))}$

for all $g\in G$ , where the sum runs over all irreducible linear representations of $G$ up to conjugacy.

This type of decomposition is very useful, for instance, in applications of the Chebotarev Density Theorem.

Example 5: The Circle Method

The circle method is based on the use of the orthogonality relations on the circle (or equivalently, for $1$ -periodic functions) to detect equalities: for an integer $n\in\mathbf{Z}$ , we have

$\delta(n,0)=\int_0^{1}{e^{2i\pi nt}dt},$

and therefore, for arbitrary integer-valued functions $f$ and $g$ , the number $N$ of solutions of the equation

$f(n_1,\ldots, n_k)=g(n_1,\ldots,n_k)$

with, for instance, $1\leq n_i\leq N$ , is given by

$N=\int_0^1{S_f(t)S_g(-t)dt}$

where

$S_f(t)=\sum_{n_1}\cdots\sum_{n_k}{e^{2i\pi f(n_1,\ldots, n_k)t}},\quad S_g(t)=\sum_{n_1}\cdots\sum_{n_k}{e^{2i\pi g(n_1,\ldots, n_k)t}}.$

Since the set of harmonics (the whole circle $\mathbf{R}/\mathbf{Z}$ , identified with the interval $[0,1[$ ) is not discrete, one can not isolate a single specific point to give a main term. However, the basic idea of the Circle Method, as developed by Hardy and Ramanujan to estimate the partition function, and by Hardy and Littlewood to solve the Waring Problem (i.e., solving the equation

$N=x_1^k+\cdots + x_g^k$

for $N$ large enough, $k$ fixed, and $g$ as small as possible), is that the main contributions to the integral should arise from suitable neighborhoods of rational points $t=a/q$ with $q$ small in some sense. The quantification of this involves issues related to Dirichlet's Theorem on Diophantine approximation. There are further refinements due to Kloosterman in particular which handle the decomposition of the interval $[0,1[$ in subtler ways.

The Circle Method has also been successful, through the work of Vinogradov in particular, to solve the ternary Goldbach problem: every odd integer large enough is the sum of three primes.

Example 6: Completing sums

This is described in the page Getting rid of nasty cutoffs.

References

For the representation theory of finite groups, the first chapters of Serre's book are the best introduction. For the Circle Method, Vaughan's tract is the best known source, and the book of Davenport (edited by T. Browning) is also highly readable. For the basic theory of arithmetic functions and the type of manipulations involving the Möbius function, Tenenbaum's book or the book of Hardy and Wright are excellent references.