Use basic examples to calibrate exponents

This article is in need of attention. The markup in this article needs changing to be in line with standards on the Tricki. See the page Formatting on the Tricki.

Quick description

When trying to quickly work out what an exponent $p$ in an estimate, identity, or inequality should be without deriving that statement line-by-line, test that statement with a simple example which has non-trivial behaviour with respect to that exponent $p$ , but trivial behaviour with respect to as many other components of that statement as one is able to manage. The "non-trivial" behaviour should be parametrised by some very large or very small parameter. By matching the dependence on this parameter on both sides of the estimate, identity, or inequality, one should recover $p$ (or at least a good prediction as to what $p$ should be).

Prerequisites

Undergraduate analysis and combinatorics.

Motivation

In the more quantitative areas of mathematics, such as analysis and combinatorics, one has to frequently keep track of a large number of exponents in one's identities, inequalities, and estimates. For instance, if one is studying a set of $N$ elements, then many expressions that one is faced with will often involve some power $N^p$ of $N$ ; if one is instead studying a function $f$ on a measure space $X$ , then perhaps it is an $L^p$ norm $\|f\|_{L^p(X)}$ which will appear instead. The exponent $p$ involved will typically evolve slowly over the course of the argument, as various algebraic or analytic manipulations are applied. In some cases, the exact value of this exponent is immaterial, but at other times it is crucial to have the correct value of $p$ at hand. One can (and should) of course carefully go through one's arguments line by line to work out the exponents correctly, but it is all too easy to make a sign error or other mis-step at one of the lines, causing all the exponents on subsequent lines to be incorrect. However, one can guard against this (and avoid some tedious line-by-line exponent checking) by continually calibrating these exponents at key junctures of the arguments by using basic examples of the object of study (sets, functions, graphs, etc.) as test cases. This is a simple trick, but it lets one avoid many unforced errors with exponents, and also lets one compute more rapidly.

General discussion

The test examples should be as basic as possible; ideally they should have trivial behaviour in all aspects except for one feature that relates to the exponent $p$ that one is trying to calibrate, thus being only "barely" non-trivial. When the object of study is a function, then (appropriately rescaled, or otherwise modified) bump functions are very typical test objects, as are Dirac masses, constant functions, Gaussians, or other functions that are simple and easy to compute with. In additive combinatorics, when the object of study is a subset of a group, then subgroups, arithmetic progressions, or random sets are typical test objects. In graph theory, typical examples of test objects include complete graphs, complete bipartite graphs, and random graphs. And so forth.

This trick is closely related to that of using dimensional analysis to recover exponents; indeed, one can view dimensional analysis as the special case of exponent calibration when using test objects which are non-trivial in one dimensional aspect (e.g. they exist at a single very large or very small length scale) but are otherwise of a trivial or "featureless" nature. But the calibration trick is more general, as it can involve parameters (such as probabilities, angles, or eccentricities) which are not commonly associated with the physical concept of a dimension. And personally, I find example-based calibration to be a much more satisfying (and convincing) explanation of an exponent than a calibration arising from formal dimensional analysis.

When one is trying to calibrate an inequality or estimate, one should try to pick a basic example which one expects to saturate that inequality or estimate, i.e. an example for which the inequality is close to being an equality. Otherwise, one would only expect to obtain some partial information on the desired exponent $p$ (e.g. a lower bound or an upper bound only). Knowing the examples that saturate an estimate that one is trying to prove is also useful for several other reasons - for instance, it strongly suggests that any technique which is not efficient when applied to the saturating example, is unlikely to be strong enough to prove the estimate in general, thus eliminating fruitless approaches to a problem and (hopefully) refocusing one's attention on those strategies which actually have a chance of working.

Calibration is best used for the type of quick-and-dirty calculations one uses when trying to rapidly map out an argument that one has roughly worked out already, but without precise details; in particular, I find it particularly useful when writing up a rapid prototype. When the time comes to write out the paper in full detail, then of course one should instead carefully work things out line by line, but if all goes well, the exponents obtained in that process should match up with the preliminary guesses for those exponents obtained by calibration, which adds confidence that there are no exponent errors have been committed.

Example 1

(Elementary identities) There is a familiar identity for the sum of the first $n$ squares:

$\displaystyle 1^2 + 2^2 + 3^2 + \ldots + n^2 = ???$ (1)

But imagine that one has forgotten exactly what the RHS of (1) was supposed to be... one remembers that it was some polynomial in $n$ , but can't remember what the degree or coefficients of the polynomial were. Now one can of course try to rederive the identity, but there are faster (albeit looser) ways to reconstruct the right-hand side. Firstly, we can look at the asymptotic test case $n \to \infty$ . On the LHS, we are summing n terms of size at most $n^2$ , so the LHS is at most $n^3$ ; thus, if we believe the RHS to be a polynomial in $n$ , it should be at most cubic in $n$ . We can do a bit better by approximating the sum in the LHS by the integral $\int_0^n x^2\ dx = n^3/3$ , which strongly suggests that the cubic term on the RHS should be $n^3/3$ . So now we have

$\displaystyle 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{1}{3} n^3 + a n^2 + b n + c$

for some coefficients $a$ , $b$ , $c$ that we still have to work out.

We can plug in some other basic cases. A simple one is $n=0$ . The LHS is now zero, and so the constant coefficient $c$ on the RHS should also vanish. A slightly less obvious base case is $n=-1$ . The LHS is still zero (note that the LHS for $n-1$ should be the LHS for $n$ , minus $n^2$ ), and so the RHS still vanishes here; thus by the factor theorem, the RHS should have both $n$ and $n+1$ as factors. We are now looking at

$\displaystyle 1^2 + 2^2 + 3^2 + \ldots + n^2 = n(n+1) ( \frac{1}{3} n + d )$

for some unspecified constant $d$ . But now we just need to try one more test case, e.g. $n=1$ , and we learn that $d = 1/6$ , thus recovering the correct formula

$\displaystyle 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n+1) (2n+1)}{6}$ . (1')

Once one has the formula (1') in hand, of course, it is not difficult to verify by a textbook use of mathematical induction that the formula is in fact valid. (Alternatively, one can prove a more abstract theorem that the sum of the first $n$ $k^{th}$ powers is necessarily a polynomial in $n$ for any given $k$ , at which point the above analysis actually becomes a rigorous derivation of (1').)

Note that the optimal strategy here is to start with the most basic test cases ( $n \to \infty, n = 0, n = -1$ ) first before moving on to less trivial cases. If instead one used, e.g. $n=1$ , $n=2$ , $n=3$ , $n=4$ as the test cases, one would eventually have obtained the right answer, but it would have been more work.

Exercise

(Partial fractions) If $w_1,\ldots,w_k$ are distinct complex numbers, and $P(z)$ is a polynomial of degree less than $k$ , establish the existence of a partial fraction decomposition

$\displaystyle \frac{P(z)}{(z-w_1) \ldots (z-w_k)} = \frac{c_1}{z-w_1} + \ldots + \frac{c_k}{z-w_k},$

(Hint: use the remainder theorem and induction) and use the test cases $z \to w_j$ for $j=1,\ldots,k$ to compute the coefficients $c_1,\ldots,c_k$ . Use this to deduce the Lagrange interpolation formula. $\diamond$

Example 2

(Counting cycles in a graph) Suppose one has a graph $G$ on $N$ vertices with an edge density of $\delta$ (thus, the number of edges is $\delta \binom{N}{2}$ , or roughly $\delta N^2$ up to constants). There is a standard Cauchy-Schwarz argument that gives a lower bound on the number of four-cycles $C_4$ (i.e. a circuit of four vertices connected by four edges) present in $G$ , as a function of $\delta$ and $N$ . It only takes a few minutes to reconstruct this argument to obtain the precise bound, but suppose one was in a hurry and wanted to guess the bound rapidly. Given the "polynomial" nature of the Cauchy-Schwarz inequality, the bound is likely to be some polynomial combination of $\delta$ and $N$ , such as $\delta^p N^q$ (omitting constants and lower order terms). But what should $p$ and $q$ be?

Well, one can test things with some basic examples. A really trivial example is the empty graph (where $\delta = 0$ ), but this is too trivial to tell us anything much (other than that $p$ should probably be positive). At the other extreme, consider the complete graph on $N$ vertices, where $\delta = 1$ ; this renders $p$ irrelevant, but still makes $q$ non-trivial (and thus, hopefully, computable). In the complete graph, every set of four points yields a four-cycle $C_4$ , so the number of four-cycles here should be about $N^4$ (give or take some constant factors, such as $4!$ - remember that we are in a hurry here, and are ignoring these sorts of constant factors). This tells us that $q$ should be at most $4$ , and if we expect the Cauchy-Schwarz bound to be saturated for the complete graph (which is a good bet - arguments based on the Cauchy-Schwarz inequality tend to work well in very "uniformly distributed" situations) - then we would expect $q$ to be exactly $4$ .

To calibrate $p$ , we need to test with graphs of density $\delta$ less than $1$ . Given the previous intuition that Cauchy-Schwarz arguments work well in uniformly distributed situations, we would want to use a test graph of density $\delta$ that is more or less uniformly distributed. A good example of such a graph is a random graph $G$ on $N$ vertices, in which each edge has an independent probability of $\delta$ of lying in $G$ . By the law of large numbers, we expect the edge density of such a random graph to be close to $\delta$ on the average. On the other hand, each one of the roughly $N^4$ four-cycles $C_4$ connecting the $N$ vertices has a probability about $\delta^4$ of lying in the graph, since the $C_4$ has four edges, each with an independent probability of $\delta$ of lying in the edge. The events that each of the four-cycles lies in the graph $G$ aren't completely independent of each other, but they are still close enough to being so that one can guess using the law of large numbers that the total number of $4$ -cycles should be about $\delta^4 N^4$ on the average (up to constants). [Actually, linearity of expectation will give us this claim even without any independence whatsoever.] So this leads one to predict $p=4$ , thus the number of $4$ -cycles in any graph on $N$ vertices of density $\delta$ should be $\geq c \delta^4 N^4$ for some absolute constant $c>0$ , and this is indeed the case (provided that one also counts degenerate cycles, in which some vertices are repeated).

If one is nervous about using the random graph as the test graph, one could try a graph at the other end of the spectrum - e.g. the complete graph on about $\sqrt{\delta} N$ vertices, which also has edge density about $\delta$ . Here one quickly calculates that the number of $4$ -cycles is about $\delta^2 N^4$ , which is a larger quantity than in the random case (and this fits with the intuition that this graph is packing the same number of edges into a tighter space, and should thus increase the number of cycles). So the random graph is still the best candidate for a near-extremiser for this bound. (Actually, if the number of $4$ -cycles is close to the Cauchy-Schwarz lower bound, then the graph becomes pseudorandom, which roughly speaking means any randomly selected small subgraph of that graph is indistinguishable from a random graph.)

One should caution that sometimes the random object is not the extremiser, and so does not always calibrate an estimate correctly. For instance, consider Szemerédi's theorem, that asserts that given any $0 < \delta < 1$ and $k > 1$ , that any subset of $\{1,\ldots,N\}$ of density $\delta$ should contain at least one arithmetic progression of length $k$ , if $N$ is large enough. One can then ask what is the minimum number of $k$ -term arithmetic progressions such a set would contain. Using the random subset of $\{1,\ldots,N\}$ of density $\delta$ as a test case, we would guess that there should be about $\delta^k N^2$ (up to constants depending on $k$ ). However, it turns out that the number of progressions can be significantly less than this (basically thanks to the old counterexample of Behrend): given any constant $C$ , one can get significantly fewer than $\delta^C N^2$ $k$ -term progressions. But, thanks to an averaging argument of Varnavides, it is known that there are at least $c(k,\delta) N^2$ $k$ -term progressions (for $N$ large enough), where $c(k,\delta) > 0$ is a positive quantity. (Determining the exact order of magnitude of $c(k,\delta)$ is still an important open problem in this subject.) So one can at least calibrate the correct dependence on $N$ , even if the dependence on $\delta$ is still unknown.

Example 3

Example 3. (Sobolev embedding) Given a reasonable function ${\Bbb R}^n \to {\Bbb R}$ (e.g. a Schwartz class function will do), the Sobolev embedding theorem gives estimates such as

$\displaystyle \| f \|_{L^q({\Bbb R}^n)} \leq C_{n,p,q} \|\nabla f\|_{L^p({\Bbb R}^n)}$ (2)

for various exponents $p$ , $q$ . Suppose one has forgotten the exact relationship between $p$ , $q$ , and $n$ and wants to quickly reconstruct it, without rederiving the proof of the theorem or looking it up. One could use dimensional analysis to work out the relationship (and we will come to that shortly), but an equivalent way to achieve the same result is to test the inequality (2) against a suitably basic example, preferably one that one expects to saturate (2).

To come as close to saturating (2) as possible, one wants to keep the gradient of $f$ small, while making $f$ large; among other things, this suggests that unnecessary oscillations in $f$ should be kept to a minimum. A natural candidate for an extremiser, then, would be a rescaled bump function $f(x) = A\phi(x/L)$ , where $\phi \in C^\infty_0({\Bbb R}^n)$ is some fixed bump function, $A > 0$ is an amplitude parameter, and $L > 0$ is a parameter, thus $f$ is a rescaled bump function of bounded amplitude $O(A)$ that is supported on a ball of radius $O(r)$ centred at the origin. [As the estimate (2) is linear, the amplitude $A$ turns out to ultimately be irrelevant here, but the amplitude plays a more crucial role in nonlinear estimates; for instance, it explains why nonlinear estimates typically have the same number of appearances of a given unknown function $f$ in each term. Also, it is sometimes convenient to carefully choose the amplitude in order to attain a convenient normalisation, e.g. to set one of the norms in (2) equal to $1$ .]

The ball that $f$ is supported on has volume about $O(L^n)$ (allowing implied constants to depend on $n$ ), and so the $L^q$ norm of $f$ should be about $O(L^{n/q} )$ (allowing implied constants to depend on $q$ as well). As for the gradient of $f$ , since $f$ oscillates by $O(A)$ over a length scale of $O(L)$ , one expects $\nabla f$ to have size about $O(A/L)$ on this ball (remember, derivatives measure "rise over run"!), and so the $L^p$ norm of $\nabla f$ should be about $O( \frac{A}{L} L^{n/p} )$ . Inserting this numerology into (2), and equating powers of $L$ (note $A$ cancels itself into irrelevance, and could in any case be set to equal $1$ ), we are led to the relation

$\displaystyle \frac{n}{p} - 1 = \frac{n}{q}$ (2)

which is indeed one of the necessary conditions for (2). (The other necessary conditions are that $p$ and $q$ lie strictly between $1$ and infinity, but these require a more complicated test example to establish.)

One can efficiently perform the above argument using the language of dimensional analysis. Giving $f$ the units of amplitude $A$ , and giving space the units of length $L$ , we see that the $n$ -dimensional integral $\int_{{\Bbb R}^n}\ dx$ has units of $L^n$ , and thus $L^p({\Bbb R}^n)$ norms have units of $L^{n/p}$ . Meanwhile, from the rise-over-run interpretation of the derivative, $\nabla f$ has units of $A/L$ , thus the LHS and RHS of (2) have units of $A L^{n/q}$ and $\frac{A}{L} L^{n/p}$ respectively. Equating these dimensions gives (3). Observe how this argument is basically a shorthand form of the argument based on using the rescaled bump function as a test case; with enough practice one can use this shorthand to calibrate exponents rapidly for a wide variety of estimates.

Exercise

Convert the above discussion into a rigorous proof that (3) is a necessary condition for (2). (Hint: exploit the freedom to send $L$ to zero or to infinity.) What happens to the necessary conditions if ${\Bbb R}^n$ is replaced with a bounded domain (such as the unit cube ${}[0,1]^n$ , assuming Dirichlet boundary conditions) or a discrete domain (such as the lattice ${\Bbb Z}^n$ , replacing the gradient with a discrete gradient of course)? $\diamond$

Exercise

If one replaces (2) by the variant estimate

$\displaystyle \| f \|_{L^q({\Bbb R}^n)} \leq C_{n,p,q} (\|f\|_{L^p({\Bbb R}^n)} + \|\nabla f\|_{L^p({\Bbb R}^n)})$ (2')

establish the necessary condition

$\displaystyle \frac{n}{p} - 1 \leq \frac{n}{q} \leq \frac{n}{p}$ . (3')

What happens to the dimensional analysis argument in this case? $\diamond$

Remark

There are many other estimates in harmonic analysis which are saturated by some modification of a bump function; in addition to the isotropically rescaled bump functions used above, one could also rescale bump functions by some non-isotropic linear transformation (thus creating various "squashed" or "stretched" bumps adapted to disks, tubes, rectangles, or other sets), or modulate bumps by various frequencies, or translate them around in space. One can also try to superimpose several such transformed bump functions together to amplify the counterexample. The art of selecting good counterexamples can be somewhat difficult, although with enough trial and error one gets a sense of what kind of arrangement of bump functions are needed to make the right-hand side small and the left-hand side large in the estimate under study. $\diamond$

Example 4

(Scale-invariance in nonlinear PDE) The model equations and systems studied in nonlinear PDE often enjoy various symmetries, notably scale-invariance symmetry, that can then be used to calibrate various identities and estimates regarding solutions to those equations. For sake of discussion, let us work with the nonlinear Schrödinger equation (NLS)

$\displaystyle i u_t + \Delta u = |u|^{p-1} u$ (4)

where ${\Bbb R} \times {\Bbb R}^n \to {\Bbb C}$ is the unknown field, $\Delta$ is the spatial Laplacian, and $p > 1$ is a fixed exponent. (One can also place in some other constants in (4), such as Planck's constant $\hbar$ , but we have normalised this constant to equal $1$ here, although it is sometimes useful to reinstate this constant for calibration purposes.) If $u$ is one solution to (4), then we can form a rescaled family $u^{(\lambda)}$ of such solutions by the formula

$= \frac{1}{\lambda^a} u( \frac{t}{\lambda^b}, \frac{x}{\lambda} )$ (5)

for some specific exponents $a$ , $b$ ; these play the role of the rescaled bump functions in Example 2. The exponents $a$ , $b$ can be worked out by testing (4) using (5), and we leave this as an exercise to the reader, but let us instead use the shorthand of dimensional analysis to work these exponents out. Let's give $u$ the units of amplitude $A$ , space the units of length $L$ , and time the units of duration $T$ . Then the three terms in (4) have units $A/T$ , $A/L^2$ , and $A^p$ respectively; equating these dimensions gives $T=L^2$ and $A=L^{-2/(p-1)}$ . (In particular, time has "twice the dimension" of space; this is a feature of many non-relativistic equations such as Schrödinger, heat, or viscosity equations. For relativistic equations, of course, time and space have the same dimension with respect to scaling.) On the other hand, the scaling (5) multiplies $A$ , $T$ , and $L$ by $\lambda^{-a}$ , $\lambda^b$ , and $\lambda$ respectively; to maintain consistency with the relations $T=L^2$ and $A=L^{-2/(p-1)}$ we must thus have $a=2/(p-1)$ and $b=2$ .

Exercise

Solutions to (4) (with suitable smoothness and decay properties) enjoy a conserved Hamiltonian $H(u)$ , of the form

$\displaystyle H(u) = \int_{{\Bbb R}^n} \frac{1}{2} |\nabla u|^2 + \alpha |u|^q\ dx$

for some constants $\alpha, q$ . Use dimensional analysis (or the rescaled solutions (5) as test cases) to compute $q$ . (The constant $\alpha$ , unfortunately, cannot be recovered from dimensional analysis, and other model test cases, such as solitons or other solutions obtained via separation of variables, also turn out unfortunately to not be sensitive enough to $\alpha$ to calibrate this parameter.) $\diamond$

Remark

The scaling symmetry (5) is not the only symmetry that can be deployed to calibrate identities and estimates for solutions to NLS. For instance, we have a simple phase rotation symmetry $u \mapsto e^{i\theta} u$ for such solutions, where $\theta \in {\Bbb R}$ is an arbitrary phase. This symmetry suggests that in any identity involving $u$ and its complex conjugate $\bar{u}$ , the net number of factors of $u$ , minus the factors of $\bar{u}$ , in each term of the identity should be the same. (Factors without phase, such as $|u|$ , should be ignored for this analysis.) Other important symmetries of NLS, which can also be used for calibration, include space translation symmetry, time translation symmetry, and Galilean invariance. (While these symmetries can of course be joined together, to create a large-dimensional family of transformed solutions arising from a single base solution $u$ , for the purposes of calibration it is usually best to just use each of the generating symmetries separately.) For gauge field equations, gauge invariance is of course a crucial symmetry, though one can make the calibration procedure with respect to this symmetry automatic by working exclusively with gauge-invariant notation (see also my earlier post on gauge theory). Another important test case for Schrödinger equations is the high-frequency limit $|\xi| \to \infty$ , closely related to the semi-classical limit $\hbar \to 0$ , that allows one to use classical mechanics to calibrate various identities and estimates in quantum mechanics. $\diamond$

Exercise

Solutions to (4) (again assuming suitable smoothness and decay) also enjoy a virial identity of the form

$\displaystyle \partial_{tt} \int_{{\Bbb R}^n} x^2 |u(t,x)|^2\ dx = \int_{{\Bbb R}^n} ???\ dx$

where the right-hand side only involves $u$ and its spatial derivatives $\nabla u$ , and does not explicitly involve the spatial variable $x$ . Using the various symmetries, predict the type of terms that should go on the right-hand side. (Again, the coefficients of these terms are unable to be calibrated using these methods, but the exponents should be accessible.) $\diamond$

Remark

Einstein used this sort of calibration technique (using the symmetry of spacetime diffeomorphisms, better known as the general principle of relativity, as well as the non-relativistic limit of Newtonian gravity as another test case) to derive the Einstein equations of gravity, although the one constant that he was unable to calibrate in this fashion was the cosmological constant. $\diamond$

Example 5

(Fourier-analytic identities in additive combinatorics). Fourier analysis is a useful tool in additive combinatorics for counting various configurations in sets, such as arithmetic progressions $n, n+r, n+2r$ of length three. (It turns out that classical Fourier analysis is not able to handle progressions of any longer length, but that is a story for another time - see e.g. this paper of Gowers for some discussion.) A typical situation arises when working in a finite group such as ${\Bbb Z}/N{\Bbb Z}$ , and one has to compute an expression such as

$\displaystyle \sum_{n, r \in {\Bbb Z}/N{\Bbb Z}} f(n) g(n+r) h(n+2r)$ (6)

for some functions ${\Bbb Z}/N{\Bbb Z} \to {\Bbb C}$ (for instance, these functions could all be the indicator function of a single set $A \subset {\Bbb Z}/N{\Bbb Z}$ ). The quantity (6) can be expressed neatly in terms of the Fourier transforms ${\Bbb Z}/N{\Bbb Z} \to {\Bbb C}$ , which we normalise as $= \frac{1}{N} \sum_{x \in {\Bbb Z}/N{\Bbb Z}} f(x) e^{-2\pi i x \xi/N}$ . It is not too difficult to compute this expression by means of the Fourier inversion formula and some routine calculation, but suppose one was in a hurry and only had a vague recollection of what the Fourier-analytic expression of (6) was - something like

$\displaystyle N^p \sum_{\xi \in {\Bbb Z}/N{\Bbb Z}}\hat f( a \xi ) \hat g( b \xi ) \hat h( c \xi )$ (7)

for some coefficients $p$ , $a$ , $b$ , $c$ , but the precise values of which have been forgotten. (In view of some other Fourier-analytic formulae, one might think that some of the Fourier transforms $\hat f, \hat g, \hat h$ might need to be complex conjugated for (7), but this should not happen here, because (6) is linear in $f,g,h$ rather than anti-linear; cf. the discussion in Example 3 about factors of $u$ and $\bar{u}$ .) How can one quickly calibrate the values of $p,a,b,c$ without doing the full calculation?

To isolate the exponent $p$ , we can consider the basic case $f \equiv g \equiv h \equiv 1$ , in which case the Fourier transforms are just the Kronecker delta function (e.g. $\hat f(\xi)$ equals 1 for $\xi=0$ and vanishes otherwise). The expression (6) is just $N^2$ , while the expression (7) is $N^p$ (because only one of the summands is non-trivial); thus $p$ must equal $2$ . (Exercise: reinterpret the above analysis as a dimensional analysis.)

Next, to calibrate $a,b,c$ , we modify the above basic test case slightly, modulating the $f,g,h$ so that a different element of the sum in (7) is non-zero. Let us take $= e^{2\pi i a x \xi/N}$ , $= e^{2\pi i b x \xi/N}$ , $= e^{2\pi i c x \xi/N}$ for some fixed frequency $\xi$ ; then (4) is again equal to $N^p=N^2$ , while (6) is equal to

$\displaystyle \sum_{n,r \in {\Bbb Z}/N{\Bbb Z}} e^{2\pi i [ a n + b (n+r) + c(n+2r)] \xi / N}.$

In order for this to equal $N^2$ for any $\xi$ , we need the linear form $an+b(n+r)+c(n+2r)$ to vanish identically, which forces $a=c$ and $b=-2a$ . We can normalise $a=1$ (by using the change of variables $\xi \mapsto a \xi$ ), thus leading us to the correct expression for (7), namely

$\displaystyle N^2 \sum_{\xi \in {\Bbb Z}/N{\Bbb Z}}\hat f( \xi ) \hat g( -2 \xi ) \hat h( \xi )$ .

Once one actually has this formula, of course, it is a routine matter to check that it actually is the right answer.

Remark

One can also calibrate $a,b,c$ in (7) by observing the identity $n - 2(n+r) + (n+2r)=0$ (which reflects the fact that the second derivative of a linear function is necessarily zero), which gives a modulation symmetry $f(x) \mapsto f(x) e^{2\pi i \alpha x}$ , $g(x) \mapsto g(x) e^{-4\pi i \alpha x}$ , $h(x) \mapsto h(x) e^{2\pi i \alpha x}$ to (6). Inserting this symmetry into (7) reveals that $a=c$ and $b=-2a$ as before. $\diamond$

Remark

By choosing appropriately normalised conventions, one can avoid some calibration duties altogether. For instance, when using Fourier analysis on a finite group such as ${\Bbb Z}/N{\Bbb Z}$ , if one expects to be analysing functions that are close to constant (or subsets of the group of positive density), then it is natural to endow physical space with normalised counting measure (and thus, by Pontryagin duality, frequency space should be given non-normalised counting measure). [Conversely, if one is analysing functions concentrated on only a bounded number of points, then it may be more convenient to give physical space counting measure and frequency space normalised counting measure.] In practical terms, this means that any physical space sum, such as $\sum_{x \in {\Bbb Z}/N{\Bbb Z}} f(x)$ , should instead be replaced with a physical space average ${\Bbb E}_{x \in {\Bbb Z}/N{\Bbb Z}} f(x) = \frac{1}{N} \sum_{x \in {\Bbb Z}/N{\Bbb Z}} f(x)$ , while keeping sums over frequency space variables unchanged; when one does so, all powers of $N$ "miraculously" disappear, and there is no longer any need to calibrate using the constant function $1$ as was done above. Of course, this does not eliminate the need to perform other calibrations, such as that of the coefficients $a,b,c$ above.