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

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.

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications