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.

Prerequisites

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.