Use analytic expressions of constraints in sums or integrals

a repository of mathematical know-how

Use analytic expressions of constraints in sums or integrals

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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.

[note article incomplete]This article needs more links and references inside.[/note]

[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

[maths] S=\sum_{a,b;\ a=b}{f(a,b)} [/maths]

with

[maths] S=\sum_{a,b}{f(a,b)\sum_{c}{g_c(a,b)}}[/maths]

where the inner sum has the property that it represents analytically [add]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$.}}[/add]

[maths delta|Delta symbol] \sum_{c}{g_c(a,b)}=\delta(a,b). [/maths]

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 [eqref delta] are frequently examples of ''orthogonality relations''.

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

[maths] S=\sum_{c}{\sum_{a,b}{f(a,b)g_c(a,b)}} [/maths]

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

[maths] \sum_{a,b}{f(a,b)g_{c_0}(a,b)} [/maths]

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

[maths] \sum_{a,b}{f(a,b)g_{c}(a,b)} [/maths]

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 [ref Example #e2]).

[EXAMPLE e1|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

[maths] S(N)=\frac{1}{N^2}\sum_{a,b\leq N;\ (a,b)=1}{1}[/maths]

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

The conditions $(a,b)=1$ can be detected by the [add]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$,}}[/add] through the formula

[maths mobius1|Möbius identity] \delta(n)=\sum_{d\mid n}{\mu(d)} [/maths]

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

[maths] 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}}. [/maths]

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

[maths] S(N)=\sum_{d\leq N}{\frac{\mu(d)}{d^2}}+O(N^{-1}\sum_{d\leq N}{d^{-1}})[/maths]

Since it is well known that

[maths] \sum_{d\leq N}{\frac{1}{d}}=O(\log N)[/maths]

and that

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

we see that

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

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

[maths] \sum_{n\geq 1}{\frac{\mu(d)}{d^2}}=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}[/maths]

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

'''Note.''' The equation [eqref mobius1] 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 e2|Detecting squarefreeness]

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

[maths]\sum_{d;\ d^2\mid n}{\mu(d)}=\delta(\square,n)[/maths]

[add]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$.}}[/add]

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

[maths] T(N)=\frac{1}{N}\sum_{n\leq N}{\delta(\square,n)}.[/maths]

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

[maths] 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))}[/maths]

and therefore

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

(again!)

[EXAMPLE e5|Detecting congruence conditions]

To compute a sum

[maths] \sum_{n\equiv a\text{ mod } q}{a_n} [/maths]

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

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

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

[maths] \chi\,:\, (\mathbf{Z}/q\mathbf{Z})^{\times}\rightarrow \mathbf{C}^{\times}[/maths]

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

[maths] \frac{1}{q}\sum_{\chi}{\chi(x)\overline{\chi(a)}}=\delta(n\text{ mod } q,a)[/maths]

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

[maths] \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)}}}[/maths]

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

[EXAMPLE e6|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

[maths] \rho\,:\, G\rightarrow GL(n,\mathbf{C})[/maths]

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

[maths] \rho(g)=T\tau(g)T^{-1} [/maths]

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

[maths] g\mapsto Tr(\rho(g)) [/maths]

(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

[maths] \delta(g,1)=\frac{1}{|G|}\sum_{\rho}{Tr(\rho(g))}[/maths]

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 e7|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

[maths] \delta(n,0)=\int_0^{1}{e^{2i\pi nt}dt}, [/maths]

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

[maths] f(n_1,\ldots, n_k)=g(n_1,\ldots,n_k) [/maths]

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

[maths] N=\int_0^1{S_f(t)S_g(-t)dt}[/maths]

where

[maths] 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}}.[/maths]

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

[maths] N=x_1^k+\cdots + x_g^k[/maths]

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 e8|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.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Use analytic expressions of constraints in sums or integrals

Recent articles

Active forum topics

Recent comments