a repository of mathematical know-how

Use self-similarity to get a limit from an inferior or superior limit.

Quick description

In some situations the existence of a limit can be derived by using inferior or superior limit and suitably dividing a domain to use self-similarity.


Basic real analysis.

Example 1: Maximal density of a packing

Fix a compact domain D in Euclidean space \mathbb{R}^n (for example, a ball). A packing P is then a union of domains congruents to D, with disjoint interiors. The density of a packing is defined as

\delta(P)=\lim_{r\to \infty} \frac{V(P\cap B(r))}{V(B(r))}

where V is the volume and B(r) is the square [-r,r]^n, when the limit exists.

The present trick shows that if P_r is a packing contained in B(r) of maximal volume, then \lim_{r\to \infty} \delta(P_r) exists.

First, since \delta(P_r)\in [0,1], the superior limit \ell=\limsup_{r\to \infty} \delta(P_r) exists. We want to prove that the inferior limit equals the superior one. Given any \varepsilon>0, there is an r_0 such that \delta(P_{r_0})>\ell-\varepsilon. Now for any integer k the square B(k r_0) can be divided into k^n translates of B(r_0). Each of these contains a packing of density greater than \ell-\varepsilon, so that \delta(P_{kr_0})>\ell-\varepsilon for all k. This rewrites as V(P_{k r_0}) > (2kr_0)^n(\ell-\varepsilon). By maximality, V(P_r) is non-decreasing in r; for all r>r_0 one can introduce k=\lfloor r/r_0\rfloor and gets V(P_r)>(2kr_0)^n(\ell-\varepsilon). It follows that

\delta(P_r)>\left(1-\frac{r_0}{r}\right)^n (\ell-\varepsilon)

so that as soon as r is large enough, \delta(P_r)>\ell-2\varepsilon. As a consequence, \liminf_r \delta(P_r)\geq \limsup_r \delta(P_r) and we are done.

Example 2: Weyl's inequality and polynomial equidistribution

This example is taken from a mathoverflow question and answer.

Let f(n)=\theta n^d+a_{d-1}n^{d-1}+\dots+a_1n+a_0 be a polynomial with real coefficients, and \theta irrational. Let

 S_N=\sum_{n=1}^N e^{2i\pi f(n)}

Weyl's Equidistribution theorem for polynomials is equivalent to the claim that S_N/N \to 0 as N\to\infty. Though it is not the most easy way to prove this, let us deduce this theorem from the following Weyl's inequality.

Let p/q be a rational number in lowest terms with |\theta - p/q|\leq 1/q^2 . Weyl's Inequality is the bound:

 \frac{S_N}{N}\leq 100 (\log N)^{d/2^d} \left(\frac1q+\frac1N+\frac{q}{N^d}\right)^{1/(2^d-1)}

If q and N are both large enough, and of the same order of magnitude, then the right-hand side gets small. The point is that the conditions on p/q prevent one to apply this to arbitrary q. However, Dirichlet's theorem tells us that arbitrary high q satisfy the needed condition, so that Weyl's inequality implies \liminf S_N/N = 0.

Now the trick comes into play: the right-hand side in Weyl's inequality does not depend on f, but only on d. It therefore gives a uniform bound simultaneously for the sum S_N and the sums S_N^t computed using f(\cdot+t) instead of f.

For all \varepsilon, there is therefore a N_0 such that for all t, S_{N_0}^t<\varepsilon N_0. Then given any K, one has

 S_{KN_0}=\sum_{k=1}^K S_{N_0}^{kN_0} <K\varepsilon N_0

Then, for all N, letting K=\lfloor N/N_0 \rfloor we get that S_N<K\varepsilon N_0+N_0 \leq \varepsilon N+N_0. It follows that \limsup S_N/N=0.

General discussion

The principle of the trick is the following: dividing the domain (either geometric in optimization setting, of the domain of sumation or integration) can allow you to take an estimate on your sequence that holds at a point, and propagate it to all its multiples. Then, for all other terms you usually get a bounded additional error term, which is hopefully negligible. This can especially be applied when a compactness argument provides you with an inferior or superior limit.