Introduction to Sumsets II

This is a sequel to a previous post. However, one can technically read it without reading the previous post.

Given $A,B\subseteq Z$ for a commutative ring $Z$, we define

$$A+B:=\{a+b:a\in A,b\in B\}$$

to be the sumset of $A$ and $B$.

Similarly,

$$A-B:=\{a-b:a\in A,b\in B\}$$

$$kA:=\underset{k\text{ times}}{\underbrace{A+\dots A}}$$

$$b+A:=\{b\}+A$$

for $A,B\subseteq Z$.

Theorem 1 : We have

$$|A-C|\left|B\right|\le |A-B||B-C|$$

where $A$, $B$ and $C$ are finite subset of $\mathbb{R}$.

Proof : For all $d\in A-C$, we fix the representation $d=a_d-c_d$ where $a_d\in A$ and $c_d\in C$. Now, we define

$$\begin{array}{rl}& f:(A-C)\times B\to (A-B)\times (B-C)\\ & (d,b)\mapsto (a_d-b,b-c_d)\end{array}$$

Note that if $f(x,y)=(u,v)$, then we must have $x=u+v$ and $y$ is determined by the equations $y=a_x-u$ and $y=c_x+v$. So, an image determines its unique inverse, that is, $f$ is injective.

This completes the proof.

Remark : Theorem 1 can be interpreted as a triangle inequality under the norm

$$\mathrm{\Delta }(A,B)=\log \frac{|A-B|}{\sqrt{\left|A\right|\left|B\right|}}$$

although this definition of $\mathrm{\Delta }$ is not really a distance as $\mathrm{\Delta }(A,A)\ne 0$.

Putting $C=A$ and then $B=-A$ in Theorem 1 we have

Corollary 2 : For all $A,B\subset \mathbb{R}$, we have

$$\begin{array}{rl}& |A-A|\le \frac{{|A-B|}^2}{\left|B\right|}\\ & |A-A|\le \frac{{|A+A|}^2}{\left|A\right|}\end{array}$$

The last inequality basically says that if $A$ has small doubling, then $A-A$ is also small. Now, we want to show that $A-A$ being small also implies that $A+A$ is. For that, we proceed with

Lemma 3 : Let $A,B\subset \mathbb{R}$ be finite. If there is a $c>0$ so that

$$|A+B|=c\left|A\right|\text{and}|A^{\prime }+B|\ge c\left|A^{\prime }\right|\mathrm{\forall }{A}^{\prime }\subset A,$$

then, we have

$$|A+B+C|\le c|A+C|$$

for any finite $C\subset \mathbb{R}$.

Proof : We use induction on the size of $C$. For $\left|C\right|=1$, i.e., $C=\{x\}$, we have

$$|A+B+x|=|A+B|=c\left|A\right|=c|A+x|$$

and hence the statement is trivial.

Now, let us assume that the statement is true for a non-empty set $C$, and define $C^{\prime }:=C\cup \{x\}$ for some $x\notin C$. We define

$$A^{\prime }:=\{a\in A:a+x\in A+C\}=A\cap (A+C-x)\subset A$$

so that

$$|A+C^{\prime }|=|A+C|+\left|A\right|-\left|A^{\prime }\right|$$

since $A^{\prime }+x=(A+x)\cap (A+C)$ and $A+C^{\prime }=(A+C)\cup (A+x)$.

Now, $A^{\prime }+x\subset A+C⟹A^{\prime }+B+x\subset A+B+C$ so that

$$A+B+C^{\prime }=(A+B+C)\cup (A+B+x)=(A+B+C)\cup [(A+B+x)\setminus (A^{\prime }+B+x)]$$

and

$$|A+B+C^{\prime }|\le |A+B+C|+|A+B|-|A^{\prime }+B|$$

and hence, using the Induction Hypothesis, we have

$$|A+B+C^{\prime }|\le c|A+C|+c\left|A\right|-c\left|A^{\prime }\right|=c|A+C^{\prime }|$$

hence completing the proof.

This lemma will help us to prove the two following important consequences.

Theorem 4 : We have

$$|A+C|\left|B\right|\le |A+B||B+C|$$

for all $A,B,C\subset \mathbb{R}$.

Proof : Let $U\subset B$ be such that $\frac{|U+A|}{\left|U\right|}=c$ is minimal. This implies

$$|U+A+C|\le c|U+C|$$

using the previous lemma.

Again, since $B$ itself is considered when the minimum is selected, we have $|A+C|\le |U+A+C|$, $|U+C|\le |B+C|$ and $c\le \frac{|A+B|}{\left|B\right|}$. These four inequalities complete the proof.

Corollary 5 : We have

$$\begin{array}{rl}& |A+A|\le \frac{{|A+B|}^2}{\left|B\right|}\\ & |A+A|\le \frac{{|A-A|}^2}{\left|A\right|}\end{array}$$

for all $A,B$.

Proof : Put $C=A$ and then $B=-A$ in the previous theorem.

Corollary 6 : We have

$$\begin{array}{rl}& |A-B|\le \frac{{|A+B|}^3}{\left|A\right|\left|B\right|}\\ & |A+B|\le \frac{{|A-B|}^3}{\left|A\right|\left|B\right|}\end{array}$$

for all $A,B$.

Proof : Use the previous corollary in Theorem 1 and then set $-B$ to $B$.

Corollary 7 : Let $A,B\subset \mathbb{R}$ be finite. If we have

$$|A+B|=c\left|A\right|\text{and}|A^{\prime }+B|\ge c\left|A^{\prime }\right|\mathrm{\forall }{A}^{\prime }\subset A$$

for some $c>0$, then

$$|A+hB|\le c^h\left|A\right|$$

for all positive integers $h$.

Proof : Set $C=(h-1)B$ in Lemma 3 to get $|A+hB|\le c|A+(h-1)B|$ and use Induction.

Theorem 8 (Plünnecke-Ruzsa Inequality) : Let $B\subset \mathbb{R}$ be finite satisfying $|B+B|\le c\left|B\right|$ (or $|B-B|\le c\left|B\right|$). Then

$$|mB-nB|\le c^{m+n}\left|B\right|$$

for all $m,n\in \mathbb{N}$.

Proof : Let the non empty set $A\subset B$ (or $A\subset -B$) be one of the sets that minimizes $\frac{|A+B|}{\left|A\right|}$ so that $|A+B|=c^{\prime }\left|A\right|$. Obviously $c^{\prime }\le c$. Also, $|A^{\prime }+B|\le c^{\prime }\left|A^{\prime }\right|$ for all $A^{\prime }\subset A$ and hence the conditions of Corollary 7 are satisfied. This gives

$$\left|hB\right|\le |A+hB|\le (c^{\prime }{)}^h\left|A\right|\le c^h\left|B\right|$$

hence proving the statement for the case $m=0$ or $n=0$.

Now, if $m,n\ne 0$, we use Theorem 1 and set $A\mapsto mB$, $B\mapsto -A$ and $C\mapsto nB$ to get

$$|mB-nB|\left|A\right|\le |A+mB||A+nB|\le (c^{\prime }{)}^m\left|A\right|(c^{\prime }{)}^n\left|A\right|\le c^{m+n}\left|B\right|\left|A\right|$$

hence completing the proof.

Introduction to Sumsets

After finding a quetsion on Math Stack Exchange, I decided to take a large chunk out of my MS thesis and present it.

Given $A,B\subseteq Z$ for a commutative ring $Z$, we define

$$A+B:=\{a+b:a\in A,b\in B\}$$

to be the sumset of $A$ and $B$.

Similarly,

$$A-B:=\{a-b:a\in A,b\in B\}$$

$$kA:=\underset{k\text{ times}}{\underbrace{A+\dots A}}$$

$$b+A:=\{b\}+A$$

for $A,B\subseteq Z$.

Theorem 1 : If $A$ and $B$ are two finite subsets of $\mathbb{R}$, then

$$|A|+|B|-1\le |A+B|\le |A||B|$$

and the lower bound is sharp iff $A$ and $B$ are arithmetic progressions of same difference.

Proof : The upper bound is obvious as we can just choose $A$ and $B$ in such a manner that all the sums of the form $a+b$ are different. One example of such a set is

$$A=\{0,1,\dots ,r-1\},B=r\cdot \{0,1,\dots ,s-1\}$$

so that

$$A+B=\{0,1,\dots ,rs-1\}$$

hence completing the proof.

  

Denoting $A=\{a_1<a_2<\cdots <a_r\}$ and $B=\{b_1<b_2<\cdots <b_s\}$, and noting that the following chain of inequalities

$$a_1+b_1<a_1+b_2<a_1+b_3<\cdots <a_1+b_s<a_2+b_s<\cdots <a_r+b_s$$

contains $r+s-1$ different elements of $A+B$ immediately completes the proof of the lower bound.

  

Now, let us assume that the lower bound is tight. Then, the following chain of inequalities

$$a_1+b_1<a_2+b_1<a_2+b_2<a_2+b_3<\cdots <a_2+b_s<a_3+b_s<\cdots <a_r+b_s$$

and the previous one must be the same.

The first and the last $r-1$ terms are clearly equal, the other $s-1$ terms determine the equations

$$\begin{array}{rl}{a}_1+b_2& =a_2+b_1\\ a_1+b_3& =a_2+b_2\\ & .\\ & .\\ & .\\ a_1+b_s& =a_2+b_{s-1}\end{array}$$

which on rearranging gives

$$\begin{array}{rl}{b}_2-b_1& =a_2-a_1\\ b_3-b_2& =a_2-a_1\\ & .\\ & .\\ & .\\ b_s-b_{s-1}& =a_2-a_1\end{array}$$

and hence $B$ is an arithmetic progression with difference $a_2-a_1$. Since the roles of $A$ and $B$ are symmetric in the statement, then so must be $A$.

In fact, a more general statement is true.

Theorem 2 : If $A_1,A_2,\dots ,A_k$, $k\ge 2$ are finite subsets of $\mathbb{R}$, then

$$|A_1|+|A_2|+\dots |A_k|-k+1\le |A_1+A_2+\dots A_k|\le |A_1||A_2|\dots |A_k|$$

and the lower bound is sharp iff $A_1,A_2,\dots ,A_k$ are arithmetic progressions of same difference.

Proof : We proceed by Induction.

The case $k=2$ is precisely the last theorem.

Now, let us assume that the statement is true for $k-1$.

Let $A=A_1+A_2+\cdots +A_{k-1}$ and $B=A_k$ so that $A+B=A_1+A_2+\cdots +A_k$. Using the previous theorem and the Induction Hypothesis, we get

$$\begin{array}{rl}|A_1|+|A_2|+\dots |A_{k-1}|-k+2+|A_k|-1& \le |A|+|B|-1\\ & \le |A+B|\\ & \le |A||B|\\ & \le |A_1||A_2|\dots |A_k|\end{array}$$

and hence the proof follows.

  

Now, we just notice that the left inequality can be an equality only if

$$|A_1|+|A_2|+\dots |A_{k-1}|-k+2=|A_1+A_2+\cdots +A_{k-1}|=|A|$$

and

$$|A|+|B|-1=|A+B|.$$

The first relation implies that $A_1,\dots ,A_{k-1}$ and hence $A_1+\cdots +A_{k-1}=A$ are arithmetic progressions of same difference, and the second relation implies that $B$ is also an arithmetic progression of same difference. This completes the proof.

Corollary 3 : Let $A$ be a finite subset of $\mathbb{R}$. Then, for an integer $k\ge 2$, we have

$$k|A|-k+1\le |kA|\le |A{|}^k$$

and the lower bound is sharp iff $A$ is an arithmetic progression.

However, it should be noted that the upper bound in the last corollary is not sharp. The sharp upper bound is given by the following theorem.

Theorem 4 : Let $A$ be a finite subset of $\mathbb{R}$. Then,

$$|kA|\le (\genfrac{}{}{0ex}{}{|A|+k-1}{k})$$

for any integer $k\ge 1$.

Proof : The number of ways of choosing unordered $k$-tuples from a set of cardinality $|A|$ is the number of non-zero integer solutions of the equation

$$x_1+\cdots +x_{|A|}=k$$

which is $(\genfrac{}{}{0ex}{}{|A|+k-1}{k})$.

This upper bound is indeed sharp and the case $k=2$ of the sharp upper bound is called a Sidon set.

The moral of Corollary 3 is that if $A+A$ is smallest possible, then $A$ has a well defined structure, namely it is an arithmetic progression. We want to understand whether $A+A$ being small, say $\le C\left|A\right|$ still implies some structure in $A$. To do that, we investigate some examples now.

Clearly, if $A$ is a set of $r$ members of an arithmetic progression of length $2r$, then $A+A$ is part of an arithmetic progression of length $4r-1$ and hence $|A+A|\le 4r-1$.

Now, considering $A=\{0,1,\dots ,r-2,N\}$ for some $N>r-2$, we see that

$$A+A=\{0,1,\dots ,2r-4\}\cup \{N,N+1,\dots ,N+r-2\}\cup \{2N\}$$

and so, if $r-2<N\le 2r-4$, then $|A+A|=N+r\le 3r-4$, and if $N>2r-4$, then $|A+A|=3r-3$. The first one is an example of having $r$ members of an arithmetic progression of size $N+1$ ($\le 2r-3$) such that $|A+A|\le 3r-4$. And the second one is an example of the same where $|A+A|=3r-3$ but $A$ cannot be covered with any arithmetic progression of reasonable size.

And next, we consider

$$Q=\{a_0+a_1{n}_1+\cdots +a_d{n}_d:0\le n_j\le N_j,j=1,\dots ,d\}$$

where $a_0,a_1,\dots ,a_d$ are fixed, and $N_1,\dots ,N_d$ are integers $\ge 2$. This is a generalized arithmetic progression of dimension $\dim (Q)=d$ and volume $\mathrm{vol}(Q)=N_1\dots N_d$.

Obviously, $\left|Q\right|\le \mathrm{vol}(Q)$, and the equality holds only if all the elements are different in which case we call $Q$ to be proper.

It was Gregori Freiman in the 1960’s who recognized if $A+A$ is small, say $\le C\left|A\right|$, then $A$ still has a special structure, though not that strong. Freiman's theorem is one of the deepest results in the theory of sumsets and it is obligatory to state it in a discussion about Additive Combinatorics.

Theorem 5 (Freiman, Ruzsa) : If $A$ is a set of positive integers and $C\ge 2$ such that $|A+A|\le C\left|A\right|$, then there is a generalized AP, $Q$ with $A\subset Q$, $\mathrm{vol}(Q)\le F(C)\left|A\right|$ and $\dim (Q)\le d(C)$ for some functions $F(C)$ and $d(C)$.

A Surprising Proof of an Inequality

Problem : Prove that for real numbers $x_1,\dots ,x_n$,

$$\sum _{i=1}^n\sum _{j=1}^n{|x_i-x_j|}^r\le \sum _{i=1}^n\sum _{j=1}^n{|x_i+x_j|}^r$$

for any $r\in [0,2]$.

Solution : The cases $r=0,2$ can be checked by hand. So, we assume $r\in (0,2)$ and begin by noting that the integral

$$\mathcal{I}(\alpha )={\int }_0^{\mathrm{\infty }}\frac{1-\cos \left(\alpha x\right)}{x^{r+1}}\text{d}x$$

is positive and finite. Also, it is easy to prove using the substitution $y=|\alpha |x$ that $\mathcal{I}(\alpha )=\sqrt{|\alpha |}\cdot \mathcal{I}(1)$.

Now, using this, we have

$$\begin{array}{rl}|a+b{|}^r-|a-b{|}^r& =\frac{1}{\mathcal{I}(1)}{\int }_0^{\mathrm{\infty }}\frac{\cos ((a-b)x)-\cos ((a+b)x)}{x^{r+1}}\text{d}x\\ & =\frac{1}{\mathcal{I}(1)}{\int }_0^{\mathrm{\infty }}\frac{2\sin (ax)\sin (bx)}{x^{r+1}}\text{d}x\end{array}$$

and hence

$$\sum _{i=1}^n\sum _{j=1}^n{|x_i-x_j|}^r-\sum _{i=1}^n\sum _{j=1}^n{|x_i+x_j|}^r=\frac{2}{\mathcal{I}(1)}{\int }_0^{\mathrm{\infty }}\frac{{(\sum _{i=1}^n\sin (x_{i}x))}^2}{x^{r+1}}\text{d}x\ge 0$$

hence completing the proof.

Prokhorov’s Theorem

The aim is to give a proof of Prokhorov’s Theorem.

Theorem : Let $\{{\mu }_n:n\ge 1\}$ be a sequence of probability measures on $({\mathbb{R}}^d,\mathcal{B}\left({\mathbb{R}}^d\right))$. If $\{{\mu }_n:n\ge 1\}$ is tight, then every sequence has a further subsequence that converges weakly to some probability measure.

We will use the following (well known) fact in our proof.

Fact : Let $\{{\mu }_n:n\ge 1\}$ be a sequence of probability measures on $({\mathbb{R}}^d,\mathcal{B}\left({\mathbb{R}}^d\right))$. Then, weak convergence ${\mu }_n\stackrel{d}{\to }{\mu }_0$ is equivalent to $\int g\text{d}{\mu }_n\to \int g\text{d}{\mu }_0$ for all compactly supported continuous functions.

With this at hand, we give the proof of the theorem.

Proof of Theorem : Let $K^N=[-N,N{]}^d$. Then, ${\mu }_n$ induces a subprobability ${\nu }_n^N:={\mu }_n{|}_{K^N}$ on $K^N$. By weak${}^{\ast }$ compactness, we can find a subsequence ${\nu }_{n_k}^N$ such that ${\nu }_{n_k}^N\stackrel{w^{\ast }}{\to }{\nu }^N$ for a subprobability measure ${\nu }^N$ on $K^N$. Repeating the argument starting with this subsequence on $K^{N+1}$ gives a new limit ${\nu }^{N+1}$. Repeating this procedure countably many times (and noticing that ${\nu }^N={\nu }^{N+1}$ on $K^N$), we get

$$\mu (A):=\underset{N\to \mathrm{\infty }}{lim}{\nu }^N(A\cap K^N)$$

for $A\in \mathcal{B}\left({\mathbb{R}}^d\right)$.

Now, we will show that $\mu$ is a probability measure. From here, it follows using the mentioned fact that our subsequence converges weakly to $\mu$.

Clearly $\mu \left(\mathrm{\Omega }\right)\le 1$ as each ${\nu }^N$ is a subprobability. Given $\epsilon >0$, tightness yields $N_{\epsilon }$ such that ${\mu }_n\left(K^{N_{\epsilon }}\right)\ge 1-\epsilon$ for all $n\ge 1$. It follows that $\mu \left(\mathrm{\Omega }\right)\ge \mu \left(K^{N_{\epsilon }}\right)\ge 1-\epsilon$. This shows that $\mu \left(\mathrm{\Omega }\right)=1$. It remains to prove that $\mu$ is $\sigma$-additive. Clearly $\mu$ is monotone. Let first

$$A=\bigcup _{i=1}^I{A}_i$$

be a disjoint union of finitely many measurable sets. Then

$$|\mu \left(\bigcup _{i=1}^I{A}_i\right)-\sum _{i=1}^I\mu \left(A_i\right)|\le |\mu (\bigcup _{i=1}^I{A}_i\cap K^{N_{\epsilon }})-\sum _{i=1}^I\mu (A_i\cap K^{N_{\epsilon }})|+(I+1)\epsilon =(I+1)\epsilon$$

since the restriction of $\mu$ to $K^{N_{\epsilon }}$ (which is ${\nu }^{N_{\epsilon }}$) is $\sigma$-additive. Thus $\mu$ is finitely additive. It follows that $\mu$ is $\sigma$-superadditive as

$$\mu (A)\ge \mu \left(\bigcup _{i=1}^I{A}_i\right)=\sum _{i=1}^I\mu \left(A_i\right)\to \sum _{i=1}^{\mathrm{\infty }}\mu \left(A_i\right)$$

by letting $I\to \mathrm{\infty }$.

Conversely, using again that the restriction of $\mu$ to $K^{N_{\epsilon }}$ is $\sigma$-additive, we have

$$\begin{array}{rl}\mu (A)& =\mu (A\setminus K^{N_{\epsilon }})+\mu (\bigcup _{i=1}^{\mathrm{\infty }}{A}_i\cap K^{N_{\epsilon }})\\ & =\mu (A\setminus K^{N_{\epsilon }})+\sum _{i=1}^{\mathrm{\infty }}\mu (A_i\cap K^{N_{\epsilon }})\\ & \le \epsilon +\sum _{i=1}^{\mathrm{\infty }}\mu \left(A_i\right)\end{array}$$

thus completing the proof.

Kolmogorov’s Continuity Theorem

The aim is to give a proof of the Kolmogorov’s Continuity Theorem, also known as Kolmogorov-Chentsov Theorem. The main reference we are following is Probability Theory, An Analytic View by Daniel W. Stroock.

Theorem : Suppose a stochastic process $X=\{X(t):0\le t\le T\}$ takes values in a Banach space $B$ so that for some $p>1$, $C>0$, $r>0$,

$$\mathbb{E}{\left[{\Vert X(t)-X(s)\Vert }_B^p\right]}^{\frac{1}{p}}\le C|t-s{|}^{\frac{1}{p}+r}$$

for all $s,t\in [0,T]$. Then there exists a family $\{\tilde{X}(t):t\in [0,T]\}$ of random variables such that $X(t)=\tilde{X}(t)$ almost surely for all $t\in [0,T]$ and $t\in [0,T]\mapsto \tilde{X}(t,\omega )\in B$ is continuous for all $\omega \in \mathrm{\Omega }$. In fact, for each $\alpha \in (0,r)$, we have

$$\mathbb{E}{\left[\underset{0\le s<t\le T}{sup}{\left(\frac{{\Vert \tilde{X}(t)-\tilde{X}(s)\Vert }_B}{(t-s{)}^{\alpha }}\right)}^p\right]}^{\frac{1}{p}}\le K{T}^{\frac{1}{p}+r-\alpha }$$

for a suitable constant $K=K(\alpha ,r,C)$.

Proof : By rescaling time, we can assume without loss of generality, that $T=1$.

Now, for $n\ge 0$, we define

$$M_n:=\underset{1\le m\le 2^n}{max}{\Vert X\left(m{2}^{-n}\right)-X((m-1)2^{-n})\Vert }_B$$

and observe that

$$\mathbb{E}{\left[M_n^p\right]}^{\frac{1}{p}}\le \mathbb{E}\left[{\left(\sum _{m=1}^{2^n}{\Vert X\left(m{2}^{-n}\right)-X((m-1)2^{-n})\Vert }_B^p\right)}^{\frac{1}{p}}\right]$$

which is bounded by $C{2}^{-rn}$.

Next, consider the path $t⇝X(t)$ on each interval $[(m-1)2^{-n},m{2}^{-n}]$ and linearize it to $t⇝X_n(t)$. It is easy to see that

$$\underset{t\in [0,1]}{max}{\Vert X_{n+1}(t)-X_n(t)\Vert }_B=\underset{1\le m\le 2^n}{max}\Vert X((2m-1)2^{-n-1})-\frac{X((m-1)2^{-n})-X(m{2}^{-n})}{2}\Vert$$

which is bounded by $M_{n+1}$.

So,

$$\mathbb{E}{\left[\underset{t\in [0,1]}{sup}{\Vert X_{n+1}(t)-X_n(t)\Vert }_B^p\right]}^{\frac{1}{p}}\le C{2}^{-rn}$$

and so there exists a measurable $\tilde{X}:[0,1]\times \mathrm{\Omega }\to B$ satisfying

$$\mathbb{E}{\left[\underset{t\in [0,1]}{sup}{\Vert \tilde{X}(t)-X_n(t)\Vert }_B^p\right]}^{\frac{1}{p}}\le \frac{C{2}^{-rn}}{1-2^{-r}}$$

and $t⇝\tilde{X}(t,\omega )$ is continuous for all $\omega \in \mathrm{\Omega }$.

Next, notice that for all $t\in [0,1]$,

$${\Vert \tilde{X}(\tau )-X(t)\Vert }_B\underset{\tau \to t}{\overset{p}{\to }}0$$

and hence $\tilde{X}(\tau )=X(t)$ almost surely.

Finally, note that for $2^{-n-1}\le t-s\le 2^{-n}$, we have

$$\begin{array}{rl}{\Vert \tilde{X}(t)-\tilde{X}(s)\Vert }_B& \le {\Vert \tilde{X}(t)-X_n(t)\Vert }_B+{\Vert X_n(t)-X_n(s)\Vert }_B+{\Vert X_n(s)-\tilde{X}(s)\Vert }_B\\ & \le 2\underset{\tau \in [0,1]}{sup}{\Vert \tilde{X}(\tau )-X_n(\tau )\Vert }_B+2^n(t-s)M_n\end{array}$$

and hence

$$\frac{{\Vert \tilde{X}(t)-\tilde{X}(s)\Vert }_B}{(t-s{)}^{\alpha }}\le 2^{\alpha n+\alpha +1}\underset{\tau \in [0,1]}{sup}{\Vert \tilde{X}(\tau )-X_n(\tau )\Vert }_B+2^{n+\alpha n}{M}_n$$

which implies

$$\begin{array}{rl}\mathbb{E}{\left[\underset{0\le s<t\le 1}{sup}{\left(\frac{{\Vert \tilde{X}(t)-\tilde{X}(s)\Vert }_B}{(t-s{)}^{\alpha }}\right)}^p\right]}^{\frac{1}{p}}& \le C\sum _{n=0}^{\mathrm{\infty }}(\frac{2^{\alpha n+\alpha +1-rn}}{1-2^{-r}}+2^{\alpha n-rn})\\ & \le \frac{5C}{(1-2^{-r})(1-2^{\alpha -r})}\end{array}$$

hence completing the proof.

Tangent Space of SL2(R)

This was a project I did about three years ago when I was in third year - I thought that it would be a good fit for this blog. I didn't change much from the original (except the necessary ones to change an Overleaf document to a Blogger post).

Introduction

The group ${\text{SL}}_2(\mathbb{R})$ consists of $2\times 2$ real matrices of determinant $1$. So, it is the collection of all points $(a,b,c,d)$ satisfying $ad-bc=1$.

Of course, ${\text{SL}}_2(\mathbb{R})\subset {\text{M}}_2(\mathbb{R})$ as ${\text{M}}_2(\mathbb{R})$ consists of all the points of the form $(a,b,c,d)$. And since ${\text{M}}_2(\mathbb{R})\cong {\mathbb{R}}^4$, and ${\mathbb{R}}^4$ has the Euclidean metric on it, we can induce that metric to ${\text{SL}}_2(\mathbb{R})$ and consider it as a metric space.

Two properties of ${\text{SL}}_2(\mathbb{R})$ immediately stick out-

1. ${\text{SL}}_2(\mathbb{R})$ is closed in ${\text{M}}_2(\mathbb{R})$.

2. ${\text{SL}}_2(\mathbb{R})$ is unbounded.

Proof of 1 : Consider the function

$$\begin{array}{rl}& \mathtt{det}:{\text{M}}_2(\mathbb{R})\to \mathbb{R}\\ & (a,b,c,d)\mapsto ad-bc\end{array}$$

Clearly, ${\text{SL}}_2(\mathbb{R})=(\mathtt{det}{)}^{-1}(\{1\})$. And since the $\mathtt{det}$ map is continuous, the result immediately follows.

Proof of 2 : From definition, $(a,b,c,d)\in {\text{SL}}_2(\mathbb{R})⟺ad-bc=1$. So, fixing $b=b_0$ and $d=d_0$, we have

$$a=\frac{1+b_{0}c}{d_0}$$

which means that any arbitrarily large value of $a$ can be accounted for by using suitably large value of $c$.

Problem 1 :

Let $A\in {\text{SL}}_2(\mathbb{R})$. Show that $\mathrm{\exists }ϵ$ such that $B_{ϵ}(A)\cap {\text{SL}}_2(\mathbb{R})$ is homeomorphic to an open subset of ${\mathbb{R}}^3$.

Solution :

First let us only look at the points of the form $p=(a,b,c,\frac{1+bc}{a})$ with $a\ne 0$. So, consider the set 

$$U=\{\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in {\text{SL}}_2(\mathbb{R}):a\ne 0\}$$ 

Let us consider the map

$$\begin{array}{rl}\varphi :& U\to \varphi (U)\subset {\mathbb{R}}^{\ast }\times \mathbb{R}\times \mathbb{R}\\ & \left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\mapsto (a,b,c)\end{array}$$

where ${\mathbb{R}}^{\ast }=\mathbb{R}\setminus \{0\}$.

Clearly, $U$ is an open subset of ${\text{SL}}_2(\mathbb{R})$ as $a\ne 0$ is an open condition. Also, the map $\varphi$ is clearly continuous.

Now, the inverse of $\varphi$ is given by

$$\begin{array}{rl}{\varphi }^{-1}:& \varphi (U)\to U\\ & (a,b,c)\mapsto \left(\begin{array}{cc}a& b\\ c& \frac{1+bc}{a}\end{array}\right)\end{array}$$

which is continuous since the inverse of the open set $U_a\times U_b\times U_c\times U_{\frac{1+bc}{a}}$ is $U_a\times U_b\times U_c$ which is open.

So, $\varphi$ is a homeomorphism from $U$ to $\varphi (U)$.

Now, let $a=0$. But, since $ad-bc=1$, if $a=0$, then $b$ and $c$ must be non-zero. So, now let us consider the set

$$V=\{\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in {\text{SL}}_2(\mathbb{R}):b\ne 0\}$$

and the map

$$\begin{array}{rl}\psi :& V\to \psi (V)\subset {\mathbb{R}}^{\ast }\times \mathbb{R}\times \mathbb{R}\\ & \left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\mapsto (a,b,d)\end{array}$$

This map is a homeomorphism from $V$ to $\psi (V)$ due to the same arguments as the last one.

So, ${\text{SL}}_2(\mathbb{R})$ is a $3$-dimensional topological manifold with the atlas $\{(U,\varphi ),(V,\psi )\}$.

So, $\mathrm{\forall }A\in {\text{SL}}_2(\mathbb{R})$, $\mathrm{\exists }ϵ>0$ such that $B_{ϵ}(A)\cap {\text{SL}}_2(\mathbb{R})$ is homeomorphic to an open subset of ${\mathbb{R}}^3$.

Problem 2 :

Let $\gamma :(\alpha ,\beta )\to {\text{SL}}_2(\mathbb{R})$ be a continuous curve. We say $\gamma$ is smooth if $\gamma$ is a smooth curve in ${\mathbb{R}}^4$. Show that $B\cdot \gamma$ is a smooth curve for any $B\in {\text{SL}}_2(\mathbb{R})$.

Solution :

Let

$$B=\left(\begin{array}{cc}{a}_1& a_2\\ b_1& b_2\end{array}\right)$$

and

$$\gamma (t)=\left(\begin{array}{cc}{p}_1(t)& q_1(t)\\ p_2(t)& q_2(t)\end{array}\right)$$

Then,

$$B\cdot \gamma (t)=\left(\begin{array}{cc}\sum _{1=1}^2{a}_i{p}_i(t)& \sum _{1=1}^2{a}_i{q}_i(t)\\ \sum _{1=1}^2{b}_i{p}_i(t)& \sum _{1=1}^2{b}_i{q}_i(t)\end{array}\right)$$

Now, since $\gamma$ is a smooth curve, each of the $p_i$'s and $q_i$'s are smooth. So, clearly, $B\cdot \gamma$ is also smooth.

We discuss about this a little bit more in Appendix Notes 1.

Problem 3 :

Let $\gamma$, $\eta$ be smooth curves in ${\text{SL}}_2(\mathbb{R})$ passing through $I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$, i.e., $\gamma (0)=\eta (0)$. We say, $\gamma \sim \eta ⟺{\gamma }^{\prime }(0)={\eta }^{\prime }(0)$. Show that the set of equivalence classes of smooth curves passing through $I$ is a vector space, denoted by ${\mathfrak{sl}}_{\mathfrak{2}}$, of dimension 3.

Solution :

First, we will try to prove that ${\mathfrak{sl}}_{\mathfrak{2}}$ is the set of all traceless matrices. To do that, let us note that if 

$$x(t)=\left(\begin{array}{cc}{x}_1(t)& x_2(t)\\ x_3(t)& x_4(t)\end{array}\right)$$

is a parametrized curve in ${\text{SL}}_2(\mathbb{R})$ with

$$x(0)=\left(\begin{array}{cc}{x}_1(0)& x_2(0)\\ x_3(0)& x_4(0)\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$$

Now, if $x(t)\in {\text{SL}}_2(\mathbb{R})$, then,

$$\begin{array}{rl}& x_1(t)x_4(t)-x_2(t)x_3(t)=1\\ ⟹& x_1^{\prime }(t)x_4+x_1(t)x_4^{\prime }(t)-x_2^{\prime }(t)x_3-x_2(t)x_3^{\prime }(t)=0\\ ⟹& x_1^{\prime }(0)+x_4^{\prime }(0)=0\end{array}$$

This shows that any element in ${\mathfrak{sl}}_{\mathfrak{2}}$ is traceless.

Now, we want to show that if $A$ is a traceless matrix, then $A$ is in ${\mathfrak{sl}}_{\mathfrak{2}}$. This, we will prove in the answer of the next question. For now, we will assume that this is true.

So, the question boils down to proving that the set of traceless matrices has dimension three. To do so, let us prove that

$$\mathtt{span}\{\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right),\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right),\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)\}=T$$

where $T$ is the set of all traceless matrices.

But, this is clearly true as given $A=\left(\begin{array}{cc}a& b\\ c& -a\end{array}\right)$, we can write

$$A=a.\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)+b.\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)+c.\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$$

and since the linear independence of the given vectors is trivially true, this completes our proof.

Problem 4 :

Show that ${\mathfrak{sl}}_{\mathfrak{2}}$ can be identified, in a natural way, to traceless $2\times 2$ matrices. Moreover, the exponential map

$$\begin{array}{rl}\text{exp}:& \{A\in {\text{M}}_2(\mathbb{R}):\text{tr}(A)=0\}\to {\text{SL}}_2(\mathbb{R})\\ & A\mapsto e^A\end{array}$$

is well defined and produces a smooth curve

$$\begin{array}{rl}{\gamma }_A:& \mathbb{R}\to {\text{SL}}_2(\mathbb{R})\\ & {\gamma }_A(t)=\text{exp}(tA)\end{array}$$

passing through $I$ with ${\gamma }_A^{\prime }(0)=A$.

Solution :

This map is clearly well defined as the matrix exponential map is well defined. Some details about this can be found in Appendix Problem 1.

Now, we want to show that, for any complex matrix $A$,

$$det(\text{exp}(A))=e^{\text{tr}(A)}$$

To do that, let us recall that every complex matrix has a Jordan normal form and that the determinant of a triangular matrix is the product of the diagonal. So,

$$\exp (A)=\exp (S^{-1}JS)=S^{-1}\exp (J)S$$

and hence,

$$\begin{array}{rl}det(\exp (A))& =det(\exp (SJ{S}^{-1}))\\ & =det(S\exp (J)S^{-1})\\ & =det(S)det(\exp (J))det(S^{-1})\\ & =det(\exp (J))\\ & =\prod _{i=1}^n{e}^{j_{ii}}\\ & =e^{\sum _{i=1}^n{j}_{ii}}\\ & =e^{\text{tr}(J)}\\ & =e^{\text{tr}(A)}\end{array}$$

which completes the proof.

So, if trace of $A$ is zero, that immediately gives that the determinant of $\exp (A)$ will be $1$, which (combined with our proof in the last problem) proves that the traceless matrices can be naturally identified with ${\mathfrak{sl}}_{\mathfrak{2}}$.

Now, we have

$${\gamma }_A(t):=\text{exp}(tA)$$

This ${\gamma }_A$ is clearly smooth as

$$\text{exp}(tA)=\sum _{n=0}^{\mathrm{\infty }}\frac{t^n{A}^n}{n!}$$

which gives

$$\begin{array}{rl}{(\text{exp}(tA))}^{\prime }& ={\left(\sum _{n=0}^{\mathrm{\infty }}\frac{t^n{A}^n}{n!}\right)}^{\prime }\\ & =\sum _{n=0}^{\mathrm{\infty }}\frac{n{t}^{n-1}{A}^n}{n!}\\ & =\sum _{n=0}^{\mathrm{\infty }}\frac{t^{n-1}{A}^n}{(n-1)!}\\ & =A.\text{exp}(tA)\end{array}$$

which is clearly well defined. We add some rigour to this argument in Appendix Problem 2.

Now,

$${\gamma }_A(t)=\text{exp}(tA)$$

which gives

$${\gamma }_A(0)=\text{exp}(\mathbf{0})=I$$

and

$${\gamma }_A^{\prime }(t)=A.\text{exp}(tA)$$

which gives

$${\gamma }_A^{\prime }(0)=A.\text{exp}(\mathbf{0})=A$$

hence completing the proof.

Problem 5 :

What is the fundamental group of ${\text{SL}}_2(\mathbb{R})$?

Solution :

We claim that the fundamental group of ${\text{SL}}_2(\mathbb{R})$ is $\mathbb{Z}$.

To prove our claim, first we will prove that ${\text{SL}}_2(\mathbb{R})$ deformation retracts to ${\text{SO}}_2(\mathbb{R})$. To do that, let us define the retraction map,

$$\begin{array}{rl}\phi :& {\text{SL}}_2(\mathbb{R})\to {\text{SO}}_2(\mathbb{R})\\ & (v_1,v_2)\mapsto (\frac{v_1}{||v_1||},\frac{e_2}{||e_2||})\end{array}$$

where $e_2=v_2-(u_1.v_2)u_1$ where $u_1=\frac{v_1}{||v_1||}$.

To prove that this is indeed a deformation retract, let us note the homotopy

$$\begin{array}{rl}\text{H}:& {\text{SL}}_2(\mathbb{R})\times I\to {\text{SL}}_2(\mathbb{R})\\ & (A,t)\mapsto (1-t)A+t\phi (A)\end{array}$$

so that $\text{H}(A,0)=A$ and $\text{H}(A,1)=\phi (A)$ hence completing the proof.

Now, we want to show that ${\text{SO}}_2(\mathbb{R})$ is homeomorphic to $S^1$. To do this, let us note that the map

$$\begin{array}{rl}f:& {\text{SO}}_2(\mathbb{R})\to S^1\\ & \left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)\mapsto e^{i\theta }=(\cos \theta ,\sin \theta )\end{array}$$

is one-one, onto and continuous.

Proving that this map is an injection is trivial as $(\cos {\theta }_1,\sin {\theta }_1)=(\cos {\theta }_2,\sin {\theta }_2)$ implies ${\theta }_1={\theta }_2$.
Surjectivity is also trivial as any point in $S^1$ is of the form $(\cos \theta ,\sin \theta )$ which has the preimage $\left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)$.
To prove that the map is a homeomorphism, we simply need to note that it is component wise continuous, and the inverse

$$\begin{array}{rl}{f}^{-1}:& S^1\to {\text{SO}}_2(\mathbb{R})\\ & (\cos \theta ,\sin \theta )\mapsto \left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)\end{array}$$

is also component wise continuous. 

Now, we know that the fundamental group of $S^1$ is $\mathbb{Z}$. So, the fundamental group of ${\text{SO}}_2(\mathbb{R})$ and hence ${\text{SL}}_2(\mathbb{R})$ should also be $\mathbb{Z}$. This completes the proof.

Problem 6 :

What does ${\text{SL}}_2(\mathbb{R})$ look topologically?

Solution :

We claim that ${\text{SL}}_2(\mathbb{R})$ is homeomorphic to $S^1\times {\mathbb{R}}^2$.

Let us recall that any invertible matrix $M$ has a unique decomposition of the form $M=QR$ where $Q$ is orthogonal and $R$ is upper triangular. So, given $M\in {\text{SL}}_2(\mathbb{R})$, we have

$$M=\left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)R$$

where $R$ is upper triangular.

So,

$$detM=det\left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)detR$$

hence giving $detR=\pm 1$.

So,

$$M=\left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)\left(\begin{array}{cc}a& b\\ 0& 1/a\end{array}\right)$$

where $a>0$, $b\in \mathbb{R}$.

This proves our claim.

Alternately, we may also take a different and much more beautiful approach and note that the group ${\text{SL}}_2(\mathbb{R})$ acts transitively on ${\mathbb{R}}^2\setminus \{(0,0)\}$ which is clearly homeomorphic to $\mathbb{R}\times S^1$. The stabilizer of the vector 

$$\left(\begin{array}{c}1\\ 0\end{array}\right)$$

is the set of matrices of the form

$$\left(\begin{array}{cc}1& a\\ 0& 1\end{array}\right)$$

which is clearly homeomorphic to $\mathbb{R}$, hence completing the proof.

Appendix :

Appendix Problem 1 :

Prove that the matrix exponential is well defined.

Proof :

First, we will show that, if $X$ and $Y$ are two $n\times n$ matrices, then

$$||XY||\le ||X||.||Y||$$

where

$$||X||={\left(\sum _{i,j=1}^n{x}_{ij}^2\right)}^{\frac{1}{2}}$$

where $x_{ij}$ is the $ij$-th entry of $X$.

So, let $X=\left\{x_{ij}\right\}$ and $Y=\left\{y_{ij}\right\}$. Using Cauchy-Schwarz Inequality, we have

$$\begin{array}{rl}||XY|{|}^2& =\sum _{i,j}(xy{)}_{ij}^2\\ & \le \sum _{i,j}\left(\sum _k{x}_{ik}^2\right)\left(\sum _k{y}_{kj}^2\right)\\ & \le \left(\sum _{i,k}{x}_{ik}^2\right)\left(\sum _{j,k}{y}_{kj}^2\right)\\ & =||X|{|}^2||Y|{|}^2\end{array}$$

hence completing the proof.

Now, let us consider the sequence of partial sums

$$S_n=\sum _{k=0}^n\frac{X^k}{k!}$$

We will show that $\{S_n{\}}_{n=1}^{\mathrm{\infty }}$ is an uniformly Cauchy sequence. To do so, let us note that for $n>m$, we have

$$\begin{array}{rl}||S_n-S_m||& =\Vert \sum _{k=m+1}^n\frac{X^k}{k!}\Vert \\ & \le \sum _{k=m+1}^n\frac{||X^k||}{k!}\\ & \le \sum _{k=m+1}^n\frac{||X|{|}^k}{k!}\end{array}$$

which of course goes to 0, as the sequence of partial sums, $\sum _{k=1}^n\frac{x^k}{k!}$ uniformly converges (as a sequence of reals) to $e^x$. So, $\{S_n{\}}_{n=1}^{\mathrm{\infty }}$ is an uniformly Cauchy sequence.

Now, we know that $({\mathbb{R}}^{n\times n},||.|{|}_{{\mathbb{R}}^{n\times n}})$ is complete. So, $\{S_n{\}}_{n=1}^{\mathrm{\infty }}$ being an uniformly Cauchy sequence, must converge uniformly.

This completes the proof.

Appendix Problem 2 :

Prove that ${\gamma }_A$ as defined in Problem 3 is a smooth curve.

Proof :

Let us consider the partial sums of $\exp (tA)$ given by

$$\begin{array}{rl}{S}_n& =\sum _{k=0}^n\frac{(tA{)}^k}{k!}\\ & =\sum _{k=0}^n\frac{t^k{A}^k}{k!}\end{array}$$

So, we have

$$\begin{array}{rl}{S}_n^{\prime }& ={\left(\sum _{k=0}^n\frac{t^k{A}^k}{k!}\right)}^{\prime }\\ & =\sum _{k=0}^n\frac{k{t}^{k-1}{A}^k}{k!}\\ & =A.\sum _{k=0}^n\frac{t^k{A}^k}{k!}\end{array}$$

which (using the result of Appendix Problem 1) converges.

The result that we have used in the last argument is from Rudin's Principles of Mathematical Analysis, Theorem 7.17, given by
Suppose $\{f_n\}$ is a sequence of functions, differentiable on $[a,b]$ and such that $\{f_n(x_0)\}$ converges for some point $x_0$ on $[a,b]$. If $\{f_n^{\prime }\}$ converges uniformly on $[a,b]$, then $\{f_n\}$ converges uniformly on $[a,b]$, to a function $f$, and

$$f^{\prime }(x)=\underset{n\to \mathrm{\infty }}{lim}{f}_n^{\prime }(x),(a\le x\le b).$$

Arguing inductively, we can show that ${\gamma }_A$ is $C^{\mathrm{\infty }}$ and

$${\gamma }_A^{(n)}=A^{n-1}.{\gamma }_A$$

which completes the proof.

Alternately, we could have also noted that each entry of ${\gamma }_A$ being a power series in $t$, is $C^{\mathrm{\infty }}$ and hence ${\gamma }_A$ is also $C^{\mathrm{\infty }}$.

Appendix Problem 3 :

We want to understand what a smooth curve in ${\text{SL}}_2(\mathbb{R})$ actually means. This we will do in the next appendix notes. For now, we wish to set the stage and look at ${\text{SL}}_2(\mathbb{R})$ as a differentiable manifold.

Proof :

We know that, to obtain a ${\mathcal{C}}^1$-differentiable manifold from a topological manifold with atlas $\mathcal{A}$, we only need to check that every transition map between charts in $\mathcal{A}$ is differentiable in the usual sense.
In this case, we have the atlas $\mathcal{A}=\{(U,x),(V,y)\}$ (from solution of Problem 1). It is easy to see that

$$(y\circ x^{-1}).(a,b,c)=y.\left(\begin{array}{cc}a& b\\ c& \frac{1+bc}{a}\end{array}\right)=(a,b,\frac{1+bc}{a})$$

This gives us the transition map

$$\begin{array}{rl}y\circ x^{-1}:& x(U\cap V)\to y(U\cap V)\\ & (a,b,c)\mapsto (a,b,\frac{1+bc}{a})\end{array}$$

Similarly,

$$(x\circ y^{-1}).(a,b,d)=y.\left(\begin{array}{cc}a& b\\ \frac{ad-1}{b}& d\end{array}\right)=(a,b,\frac{ad-1}{b})$$

giving us

$$\begin{array}{rl}x\circ y^{-1}:& y(U\cap V)\to x(U\cap V)\\ & (a,b,d)\mapsto (a,b,\frac{ad-1}{b})\end{array}$$

Clearly, the transition maps are differentiable as $a\ne 0$ and $b\ne 0$.

This proves that $\mathcal{A}$ is a differentiable atlas. So, we see that ${\text{SL}}_2(\mathbb{R})$ is a differentiable manifold.

Appendix Note 1 :

Let us recall that a function $f:{\mathbb{R}}^n\to M$ on a manifold $M$ is called smooth if for all charts $(U,\varphi )$ the function

$$\varphi \circ f:{\mathbb{R}}^n\to \varphi (U)$$

is smooth (in the Euclidean sense).

In our case (in Problem 2), we were already given the definition that $\gamma$ is smooth if $\gamma$ is a smooth curve in ${\mathbb{R}}^4$. We want to unify the two definitions which will establish that ${\text{SL}}_2(\mathbb{R})$ is a good enough manifold. So, given the two charts $\{(U,\varphi ),(V,\psi )\}$, let us look at

$$\begin{array}{rl}& \varphi \circ \gamma :\mathbb{R}\to \gamma \cap U\to {\mathbb{R}}^3\\ & \varphi \circ \gamma (t)=\varphi \circ \left(\begin{array}{cc}{p}_1(t)& q_1(t)\\ p_2(t)& q_2(t)\end{array}\right)=(p_1(t),q_1(t),p_2(t))\end{array}$$

and

$$\begin{array}{rl}& \psi \circ \gamma :\mathbb{R}\to \gamma \cap V\to {\mathbb{R}}^3\\ & \psi \circ \gamma (t)=\psi \circ \left(\begin{array}{cc}{p}_1(t)& q_1(t)\\ p_2(t)& q_2(t)\end{array}\right)=(p_1(t),q_1(t),q_2(t))\end{array}$$

Now, these being maps from ${\mathbb{R}}^n$ to ${\mathbb{R}}^m$ are smooth in the Euclidean sense as the components are smooth.

Once this unification is done, we can now say that component-wise smoothness is enough to guarantee manifold-wise smoothness. This justifies the argument we used in Problem 2 to show that $B\cdot \gamma$ is smooth.

Appendix Problem 4 :

Prove that ${\text{SL}}_2(\mathbb{R})$ is a topological space.

Proof :

Let us recall that if $N$ is a subset of $M$, and $\mathcal{O}$ is a topology on $M$, then

$$\mathcal{O}{|}_N:=\{U\cap N:U\in \mathcal{O}\}$$

equips $N$ with the subset topology inherited from $M$.

So, let us take the standard topology on $\mathbb{R}$ given by

$$\begin{array}{rl}& B_r(x):=\{y\in \mathbb{R}:|x-y|<r\}\\ & U\in {\mathcal{O}}_{\mathbb{R}}⟺\mathrm{\forall }x\in U\mathrm{\exists }r>0:B_r(x)\subset U\end{array}$$

Now, we can equip ${\mathbb{R}}^4$ with the product topology so that we can finally define

$$\mathcal{O}:=\left({\mathcal{O}}_{\mathbb{R}}\right){|}_{{\text{SL}}_2(\mathbb{R})}$$

so that $({\text{SL}}_2(\mathbb{R}),\mathcal{O})$ is a topological space.

This added to Appendix Problem 3 and Problem 1 shows that ${\text{SL}}_2(\mathbb{R})$ is a differentiable topological manifold.

Appendix Problem 5 :

Prove that ${\text{SL}}_2(\mathbb{R})$ forms a group under the usual definition of multiplication.

Proof :

The usual definition of multiplication is of course given by

$$\begin{array}{rl}& \cdot :{\text{SL}}_2(\mathbb{R})\times {\text{SL}}_2(\mathbb{R})\to {\text{SL}}_2(\mathbb{R})\\ & (\left(\begin{array}{cc}a& b\\ c& d\end{array}\right),\left(\begin{array}{cc}e& f\\ g& h\end{array}\right))\mapsto \left(\begin{array}{cc}ae+bg& af+bh\\ ce+dg& cf+dh\end{array}\right)\end{array}$$

This operation is closed as real numbers are closed under addition and multiplication. It is also straightforward to check that

1. this operation is associative

2. has the identity element $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$, and

3. for each $\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$, admits the inverse $\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$.

This completes the proof that ${\text{SL}}_2(\mathbb{R})$ is a (non-commutative) group.

Appendix Problem 6 :

Prove that ${\text{SL}}_2(\mathbb{R})$ is connected.

Proof :

We will prove the more general case of ${\text{SL}}_n(\mathbb{R})$.

First, let us prove that the elementary matrices of first type generate ${\text{SL}}_n(\mathbb{R})$. This is Exercise 2.4.8(b) of Artin's Algebra.

If $E$ is an elementary matrix, then $X\mapsto EX$ can be described as follows: if $E$ is Type 1, with the off-diagonal entry $a$ at $(i,j)$, we do $r_i\mapsto r_i+a{r}_j$; if $E$ is Type 3, with the modified diagonal entry $c\ne 0$ at index $i$, then $r_i\mapsto c{r}_i$.

Note that Type 1 matrices have determinant $1$ and Type 3 matrices have determinant $c$.

In order to show$$M=E_1{E}_2\dots E_k$$for some (permitted) elementary matrices $E_i$, it suffices to show $$I_n=F_k{F}_{k-1}\dots F_{1}M$$for some elementary $F_i$, since then$$M=F_1^{-1}\dots F_k^{-1},$$as elementary matrices are invertible, and their inverses are elementary as well.

Now, we consider $M\in {\text{SL}}_n(\mathbb{R})$. Using the row operations corresponding to Type 1 elementary matrices, we turn column $i$ into $e_i$ ($1$ at position $i$, $0$ elsewhere) from left to right.

Take the leftmost column $i$ with $c_i\ne e_i$, if it exists (otherwise, we are done). Since $det(M)=1\ne 0$, we can not have $c_i$ written as a linear combination of$$c_1=e_1,\dots ,c_{i-1}=e_{i-1};$$hence one of entries $i,i+1,\dots ,n$ must be nonzero, say $j$.

Subtracting $r_j$ from the other rows as necessary, we first clear out all column $i$ (except for row $j$). Note that none of this affects columns $1$ through $i-1$. If $i=n$, we have a diagonal matrix with determinant $1$ and the first $n-1$ entries all $1$'s, so we are done. Otherwise, if $i<n$, pick an arbitrary row $k\ne j$ from $i$ to $n$, and add a suitable multiple of $r_j$ to $r_k$ so that the $(k,i)$ entry becomes $1$. Now subtract a suitable multiple of $r_k$ from $r_j$ so the $(j,i)$ entry becomes $0$. If $k=i$, we can proceed to column $i+1$; otherwise, add $r_k$ to $r_i$ and subtract $r_i$ from $r_k$, and then proceed to column $i+1$.

Now, Let $\sim$ be the binary operation corresponding to path-connectivity in ${\text{SL}}_n(\mathbb{R})$. Clearly, $\sim$ is an equivalence relation.

In order to show ${\text{SL}}_n(\mathbb{R})$ is path-connected, it suffices to show $A\sim I_n$ for all $A\in {\text{SL}}_n(\mathbb{R})$. But, we just proved that $A$ can be written as a (possibly empty) product of elementary matrices of the first type, so it in fact suffices to prove that

$$E_{uv}(a)M\sim M$$

for all $M\in {\text{SL}}_n(\mathbb{R})$ and Type 1 elementary matrices $E_{uv}(a)$ ($1\le u,v\le n$) of the form

$$I_n+[a[(i,j)=(u,v)]{]}_{i,j=1}^n$$

Yet

$$M\to E_{uv}(b)M$$

simply adds $b$ times row $j$ to row $i$, i.e. takes $r_i$ to $r_i+b{r}_j$. For fixed $u$, $v$, $M$, this map is continuous in $b$ (and preserves the determinant), so the continuous function

$$X(t)=E_{uv}(ta)M$$

over $[0,1]$ takes

$$X(0)=M\to X(1)=E_{uv}(a)M$$

while remaining inside ${\text{SL}}_n(\mathbb{R})$, as desired.

Alternately, we can also first prove that ${\text{GL}}_n^{+}(\mathbb{R}):=\{A\in M_n(\mathbb{R}):det(A)>0\}$ is connected, and then consider the continuous surjective map

$$\mathrm{\Psi }:{\text{GL}}_n^{+}(\mathbb{R})\ni A\mapsto \frac{A}{detA}\in {\text{SL}}_2(\mathbb{R})$$

and recall that continuous image of a connected set is connected.

Now, we can prove ${\text{GL}}_n^{+}(\mathbb{R})$ is connected by induction on $n$. Consider the map

$$p:{\text{M}}_n(\mathbb{R})={\mathbb{R}}^n\times {\text{M}}_{n(n-1)}(\mathbb{R})\to {\mathbb{R}}^n$$

given by $p(A)=A{e}_1$. That is $p$ sends $A\in {\text{M}}_n(\mathbb{R})$ to its first column. Note that $p$ is a projection map, hence open and continuous. 

Note that, ${\text{GL}}_1^{+}(\mathbb{R})=(0,\mathrm{\infty })$. Now, let $f:{\text{GL}}_n^{+}(\mathbb{R})\to {\mathbb{R}}^n-\{0\}$ be the restriction of $p$ to the ${\text{GL}}_n^{+}(\mathbb{R}){\subseteq }_{\text{open}}{\text{M}}_n(\mathbb{R})$. So, $f$ is also open continuous. 

Next, $f^{-1}(e_1)={\mathbb{R}}^{n-1}\times {\text{GL}}^{+}(n-1,\mathbb{R})$, which is a connected set by induction. For $y\in {\mathbb{R}}^n-\{0\}$ choose $B\in {\text{GL}}_n^{+}(\mathbb{R})$ with $f(B)=y$. Then, $f^{-1}(y)=\{B\cdot C:C\in f^{-1}(e_1)\}$. Hence each fibre of $f$ is connected. But, we know that if $Y$ be connected and $f:X\to Y$ is a surjective continuous map having connected fibers, and if $f$ is open, then $X$ is also connected. This, we can prove by contradiction-

If possible, write $X=U⨆V$ where $U,V$ are non-empty open subsets of $X$. Then, $f(U),f(V)$ are open subsets of $Y$ such that $f(U)\cup f(V)=Y$. Now, $Y$ is connected implies $f(U)\cap f(V)\ne \mathrm{\varnothing }.$ Take, $y\in f(U)\cap f(V)$, then $f^{-1}(y)\cap U\ne \mathrm{\varnothing }$ and $f^{-1}(y)\cap V\ne \mathrm{\varnothing }$, contradicts to the fact that fibers are connected sets.

This proves that ${\text{SL}}_2(\mathbb{R})$ in particular is path connected, and hence connected.

Appendix Problem 7 :

Prove that ${\text{SL}}_2(\mathbb{R})$ forms a Lie group.

Proof :

We have equipped ${\text{SL}}_2(\mathbb{R})$ with both a group and a manifold structure. In order to obtain a Lie group structure, we have to check that these two structures are compatible, i.e, we need to show that the two maps

$$\begin{array}{rl}\mu :& {\text{SL}}_2(\mathbb{R})\times {\text{SL}}_2(\mathbb{R})\to {\text{SL}}_2(\mathbb{R})\\ & (\left(\begin{array}{cc}a& b\\ c& d\end{array}\right),\left(\begin{array}{cc}e& f\\ g& h\end{array}\right))\mapsto \left(\begin{array}{cc}ae+bg& af+bh\\ ce+dg& cf+dh\end{array}\right)\end{array}$$

and

$$\begin{array}{rl}i:& {\text{SL}}_2(\mathbb{R})\to {\text{SL}}_2(\mathbb{R})\\ & \left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\to {\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)}^{-1}\end{array}$$

are differentiable with the differentiable structure on ${\text{SL}}_2(\mathbb{R})$. For instance, for the inverse map $i$, we have to show that the map $y\circ i\circ x^{-1}$ is differentiable in the usual sense for any pair of charts $(U,x),(V,y)\in \mathcal{A}$.

$$\begin{array}{c}U\subseteq {\text{SL}}_2(\mathbb{R})\stackrel{i}{\to }V\subseteq {\text{SL}}_2(\mathbb{R})\\ \downarrow x\downarrow y\\ x(U)\subseteq {\mathbb{R}}^3\stackrel{y\circ i\circ x^{-1}}{\to }y(V)\subseteq {\mathbb{R}}^3\end{array}$$

But, since ${\text{SL}}_2(\mathbb{R})$ is connected, the differentiability of the transition maps in $\mathcal{A}$ implies that if $y\circ i\circ x^{-1}$ is differentiable for any two given charts, then it is differentiable for all charts in $\mathcal{A}$. Hence, we can simply let $(U,x)$ and $(V,y)$ be the two charts on ${\text{SL}}_2(\mathbb{R})$ defined above. then we have

$$(y\circ i\circ x^{-1})(a,b,c)=(y\circ i)\left(\left(\begin{array}{cc}a& b\\ c& \frac{1+bc}{a}\end{array}\right)\right)=y\left(\left(\begin{array}{cc}\frac{1+bc}{a}& -b\\ -c& a\end{array}\right)\right)=(\frac{1+bc}{a},-b,a)$$

which is clearly differentiable as a map between open subsets of ${\mathbb{R}}^3$ as $a\ne 0$ on $x(U)$.

To prove that $\mu$ is differentiable, we can proceed almost similarly once we have a differentiable structure on the product manifold ${\text{SL}}_2(\mathbb{R})\times {\text{SL}}_2(\mathbb{R})$. Or, we may also argue that the matrix multiplication ${\text{M}}_2(\mathbb{R})\times {\text{M}}_2(\mathbb{R})\to {\text{M}}_2(\mathbb{R})$ is

given by smooth expressions in the entries (involving products and sums) and hence it is a smooth map, from which it follows that the restriction to ${\text{SL}}_2(\mathbb{R})\times {\text{SL}}_2(\mathbb{R})\to {\text{SL}}_2(\mathbb{R})$ is also smooth.

This completes the proof that ${\text{SL}}_2(\mathbb{R})$ is a 3-dimensional Lie group.

An Application of a Theorem I Just Learned

Question : Recall that a polygonal number is a number that counts dots arranged in the shape of a regular polygon. Prove that the $n$-th non $s$-gonal number is given by

$$\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+\frac{2n}{s-2}}\rfloor +n$$

where $\lfloor x\rfloor$ represents the least integer less than or equal to $x$.

Answer : It is well known that

$$(s-2)\frac{n(n-1)}{2}+n$$

is the $n$-th $s$-gonal number.

Now, we will use the Lambek-Moser Theorem to get

$$f(n)=(s-2)\frac{n(n-1)}{2}$$

and hence

$$f^{\ast }(n)=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+\frac{2n}{s-2}}\rfloor$$

and hence

$$F^{\ast }(n)=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+\frac{2n}{s-2}}\rfloor +n$$

hence completing the proof.

Remark : A careful induction on $n$ (keeping $s$ fixed) would probably have also done the job.

Acknowledgement : I learnt about the Lambek-Moser Theorem from the book The Irrationals: a Story of the Numbers You Can't Count On by Julian Havil (section Theoretical Matters of chapter Does Irrationality Matter?) which I also reviewed for zbMATH. 

The Law of Iterated Logarithm

1. Introduction

The goal is to give a complete proof of the Law of Iterated Logarithm. The setup we will work in is the following. Let $\{X_i{\}}_{i=1}^{\mathrm{\infty }}$ be a sequence of iid random variables with mean $0$ and variance $1$. Let

$$S_n:=\sum _{i=1}^n{X}_i\text{ and }{\overline{S}}_n:=\frac{S_n}{n}$$

for $n\in {\mathbb{Z}}^{+}$. From now on, we will use $X_n$ and $S_n$ as defined in our discussions.

We wish to prove the following theorem.

Theorem 1 (The Law of Iterated Logarithm) : Let

$${\mathrm{\Lambda }}_n:=\sqrt{2n\log \log n}$$

wherever it is defined. Then,

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{S_n}{{\mathrm{\Lambda }}_n}=1$$

almost surely. By replacing $X_j$ by $-X_j$, this also proves that

$$\underset{n\to \mathrm{\infty }}{lim inf}\frac{S_n}{{\mathrm{\Lambda }}_n}=-1$$

almost surely. In fact, for any $f\in C(\mathbb{R},\mathbb{R})$,

$$\underset{n\to \mathrm{\infty }}{lim sup}f\left(\frac{S_n}{{\mathrm{\Lambda }}_n}\right)=\underset{t\in [-1,1]}{sup}f(t)$$

almost surely. That is, the set of limit points of

$$\{\frac{S_n}{{\mathrm{\Lambda }}_n}:n\ge 1\}$$

coincides with the interval $[-1,1]$ almost surely.

In what follows, we will use the notation

$${\mathrm{\Lambda }}_{\beta }:={\mathrm{\Lambda }}_{\lfloor \beta \rfloor }\text{ and }{\tilde{S}}_{\beta }:=\frac{S_{\lfloor \beta \rfloor }}{{\mathrm{\Lambda }}_{\beta }}$$

where $\lfloor \beta \rfloor$ is greatest integer less than or equal to $\beta$.

The main reference we are following is Probability Theory, An Analytic View by Daniel W. Stroock.

2. Lemmas

To prove Theorem 1, we need three lemmas.

Lemma 1 : For $a\in (0,\mathrm{\infty })$ and $\beta \in (1,\mathrm{\infty })$, if

$$\sum _{m=1}^{\mathrm{\infty }}\mathbb{P}(\left|{\tilde{S}}_{{\beta }^m}\right|\ge \frac{a}{\sqrt{\beta }})<\mathrm{\infty }$$

then

$$\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\le a$$

almost surely.

Lemma 2 : For any sequence $\{X_n:n\ge 1\}$ of iid random variables with mean $0$ and variance ${\sigma }^2$, we have

$$\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\le 8\sigma$$

almost surely.

Lemma 3 : Let the sequence $\{X_n\}$ have a common distribution $\mu$. Further, let the moment-generating function

$$M_{\mu }(\xi ):={\int }_{\mathbb{R}}{e}^{\xi x}\mu (\text{d}x)<\mathrm{\infty }$$

for all $\xi \in \mathbb{R}$. Then, for all $R\in (0,\mathrm{\infty })$, there is an $N(R)\in {\mathbb{Z}}^{+}$ and a suitable constant $K$ such that

$$\mathbb{P}(\left|{\tilde{S}}_n\right|\ge R)\le 2\exp [-(1-K\sqrt{\frac{8R\log \log n}{n}})R^2\log \log n]$$

for all $n\ge N(R)$. Also, for each $\epsilon \in (0,1]$, there is an $N(\epsilon )\in {\mathbb{Z}}^{+}$ such that for all for all $n\ge N(\epsilon )$ and $\left|a\right|\le \frac{1}{\epsilon }$,

$$\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )\ge \frac{1}{2}\exp [-(a^2+4K\left|a\right|\epsilon )\log \log n]$$

for some suitable constant $K$.

3. Proof of Theorem

We will first give a proof assuming the three lemmas and then give a proof of the lemmas afterwards.

Proof of Theorem 1 : Observe first that for any $X_n$ and $\epsilon >0$, it is easy to find a $\psi \in C_{\text{b}}(\mathbb{R})$ so that $Y_n:=\psi \circ X_n$ has mean $0$ and variance $1$ while $Z_n:=X_n-Y_n$ has variance less than ${\epsilon }^2$ (what we want is to find a smooth truncation - one way to do this is by first considering $X_n\cdot {\mathbf{1}}_{\left|X_n\right|<n}$ and then appropriately smoothening the edges). Applying Lemma 2 to this $Z_n$, we have

$$\underset{n\to \mathrm{\infty }}{lim sup}|{\tilde{S}}_n(\omega )|\le 1+\underset{n\to \mathrm{\infty }}{lim sup}\left|\frac{\sum _{m=1}^n{Z}_m(\omega )}{{\mathrm{\Lambda }}_n}\right|\le 1+8\epsilon$$

and for $a\in [-1,1]$, we have

$$\underset{n\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_n(\omega )-a|\le \underset{n\to \mathrm{\infty }}{lim sup}\left|\frac{\sum _{m=1}^n{Z}_m(\omega )}{{\mathrm{\Lambda }}_n}\right|\le 8\epsilon$$

for almost every $\omega \in \mathrm{\Omega }$. So, it is enough to assume that the random variables are bounded, and that is what will be assumed in the rest of the proof.

Now, for a given $\beta >1$, we can use Lemma 3 to argue

$$\mathbb{P}(\left|{\tilde{S}}_{{\beta }^m}\right|\ge \sqrt{\beta })\le 2\exp [-\sqrt{\beta }\log \log \lfloor {\beta }^m\rfloor ]$$

for all sufficiently large $m\in {\mathbb{Z}}^{+}$. So, using Lemma 1 with $a=\beta$, we see that

$$\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\le \beta$$

almost surely for all $\beta \in (1,\mathrm{\infty })$.

So, to complete the proof, we need to show

$$\mathbb{P}(\underset{n\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_n-a|<\epsilon )=1$$

for all $a\in (-1,1)$ and all $\epsilon >0$. To do this, we wish to use the Borel-Cantelli Lemma. But for that, we need to make sure we are dealing with independent events. For this, we can use the previously proved result to argue that

$$\underset{n\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_n-a|\le \underset{k\ge 2}{inf}\underset{m\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_{k^m}-a|\le \underset{k\to \mathrm{\infty }}{lim inf}\underset{n\to \mathrm{\infty }}{lim inf}|\frac{S_{k^m}-S_{k^{m-1}}}{{\mathrm{\Lambda }}_{k^m}}-a|$$

almost surely for all integers $k\ge 2$.

Now, since the events

$$A_{k,m}:={\{|\frac{S_{k^m}-S_{k^{m-1}}}{{\mathrm{\Lambda }}_{k^m}}-a|<\epsilon \}}_{m\in {\mathbb{Z}}^{+}}$$

are mutually independent for each $k\ge 2$, it is enough to check that

$$\sum _{m=1}^{\mathrm{\infty }}\mathbb{P}\left(A_{k,m}\right)=\mathrm{\infty }$$

for sufficiently large $k$.

But, since

$$\underset{k\to \mathrm{\infty }}{lim}\underset{m\in {\mathbb{Z}}^{+}}{max}|\frac{{\mathrm{\Lambda }}_{k^m}}{{\mathrm{\Lambda }}_{k^m-k^{m-1}}}-1|=0$$

and

$$\mathbb{P}\left(A_{k,m}\right)=\mathbb{P}(|{\tilde{S}}_{k^m-k^{m-1}}-\frac{a{\mathrm{\Lambda }}_{k^m}}{{\mathrm{\Lambda }}_{k^m-k^{m-1}}}|<\frac{\epsilon {\mathrm{\Lambda }}_{k^m}}{{\mathrm{\Lambda }}_{k^m-k^{m-1}}})$$

for all $k\ge 2$, it is enough to show

$$\sum _{m=1}^{\mathrm{\infty }}\mathbb{P}(|{\tilde{S}}_{k^m-k^{m-1}}-a|<\epsilon )=\mathrm{\infty }$$

for every $k\ge 2$ and $a\in (-1,1)$ and $\epsilon >0$. This follows by using the second part of Lemma 3 and choosing $\tilde{\epsilon }>0$ so small that $\rho :=a^2+4K\tilde{\epsilon }|a|<1$ from which it is possible to conclude that when $0<\epsilon <\tilde{\epsilon }$, we have

$$\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )\ge \frac{1}{2}\exp [-\rho \log \log n]$$

for all sufficiently large $n$.

This completes the proof. $◻$

4. Proof of Lemma 1

We first introduce the idea of a median. Give a real valued random variable $Y$, we say $\alpha \in \mathbb{R}$ is a median of $Y$ if

$$\mathbb{P}(Y\le \alpha )\ge \frac{1}{2}\text{ and }\mathbb{P}(Y\ge \alpha )\ge \frac{1}{2}$$

and write as $\alpha \in \mathrm{med}(Y)$. It is easy to see that

$$\alpha :=inf\{t\in \mathbb{R}:\mathbb{P}(Y\le t)\ge \frac{1}{2}\}$$

is a median of $Y$. In other words, every $Y$ has a median. Additionally, it can be shown that if $Y\in L^2(\mathbb{R})$ and $m$ is the mean of $Y$, then

$$|\alpha -m|\le \sqrt{2\text{Var}(Y)}$$

for all $\alpha \in \text{med}(Y)$.

We also have the following theorem.

Theorem 2 (Lévy Reflection Principle) : For $k\le \ell$, choose ${\alpha }_{\ell ,k}\in \mathrm{med}(S_{\ell }-S_k)$. Then, for all $\epsilon >0$, we have

$$\mathbb{P}(\underset{1\le n\le N}{max}|S_n+{\alpha }_{n,m}|\ge \epsilon )\le 2\mathbb{P}(\left|S_N\right|\ge \epsilon )$$

for all $N\in {\mathbb{Z}}^{+}$.

With this at hand, we move to the proof.

Proof of Lemma 1 : Let $\beta \in (1,\mathrm{\infty })$ be given. For each $m\in \mathbb{N}$ and $1\le n\le {\beta }^m$, let ${\alpha }_{m,n}$ be a median of $S_{\lfloor {\beta }^m\rfloor }-S_n$. This gives $\left|{\alpha }_{m,n}\right|\le \sqrt{2{\beta }^m}$ so that

$$\begin{array}{rl}\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|& =\underset{m\to \mathrm{\infty }}{lim sup}\underset{{\beta }^{m-1}\le n\le {\beta }^m}{max}\left|{\tilde{S}}_n\right|\\ & \le \sqrt{\beta }\underset{m\to \mathrm{\infty }}{lim sup}\underset{n\le {\beta }^m}{max}\frac{\left|S_n\right|}{{\mathrm{\Lambda }}_{{\beta }^m}}\\ & \le \sqrt{\beta }\underset{m\to \mathrm{\infty }}{lim sup}\underset{n\le {\beta }^m}{max}\frac{|S_n+{\alpha }_{m,n}|}{{\mathrm{\Lambda }}_{{\beta }^m}}\end{array}$$

which gives

$$\mathbb{P}(\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\ge a)\le \mathbb{P}(\underset{m\to \mathrm{\infty }}{lim sup}\underset{n\le {\beta }^m}{max}\frac{|S_n+{\alpha }_{m,n}|}{{\mathrm{\Lambda }}_{{\beta }^m}}\ge \frac{a}{\sqrt{\beta }})$$

and hence on application of Theorem 2, we have

$$\mathbb{P}(\underset{n\le {\beta }^m}{max}\frac{|S_n+{\alpha }_{m,n}|}{{\mathrm{\Lambda }}_{{\beta }^m}}\ge \frac{a}{\sqrt{\beta }})\le 2\mathbb{P}(\left|{\tilde{S}}_{{\beta }^m}\right|\ge \frac{a}{\sqrt{\beta }})$$

from which the desired result follows using Borel-Cantelli Lemma. $◻$

5. Proof of Lemma 2

Again, we need to introduce a few objects before we can move to our proof.

We define the Rademacher functions $\{R_n{\}}_{n\in {\mathbb{Z}}^{+}}$ on $[0,1)$ as follows. Consider the function $R:\mathbb{R}\to \{-1,1\}$ given by

$$R(t):=\{\begin{array}{ll}-1& \text{if}t-\lfloor t\rfloor \in [0,\frac{1}{2})\\ 1& \text{if}t-\lfloor t\rfloor \in [\frac{1}{2},1)\end{array}$$

and define $R_n$ on $[0,1)$ by

$$R_n(\omega ):=R\left(2^{n-1}\omega \right)$$

for $n\in {\mathbb{Z}}^{+}$ and $\omega \in [0,1)$. It can be shown that the Rademacher functions are mutually independent.

We will use these functions in our proof.

Proof of Lemma 2 : Without loss of generality, it can be assumed that $\sigma =1$. We begin by considering the case where the $X_n$'s are symmetric, i.e., $X_n$ and $-X_n$ has the same distribution as $X_n$ itself. For this case, we will be able to prove the result with the constant $8$ replaced by $4$ once we can show

$$\sum _{m=0}^{\mathrm{\infty }}\mathbb{P}\left(|{\tilde{S}}_{2^m}\ge 2^{3/2}|\right)<\mathrm{\infty }$$

since we can then use Lemma 1.

Now, let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be the probability space on which the $X_n$'s are defined and let $\{R_n{\}}_{n\in {\mathbb{Z}}^{+}}$ be the sequence of Rademacher functions on $[0,1)$. Set $\mathbb{Q}:={\lambda }_{[0,1)}\times \mathbb{P}$ on $([0,1)\times \mathrm{\Omega },{\mathcal{B}}_{[0,1)}\times \mathcal{F})$ where ${\lambda }_{[0,1)}$ is the Lebesgue measure on $[0,1)$. It is easy to check that the symmetry of $X_n$ is equivalent to the statement that

$$\omega \in \mathrm{\Omega }\mapsto (X_1(\omega ),X_2(\omega ),\dots )\in {\mathbb{R}}^{{\mathbb{Z}}^{+}}$$

has the same distribution under $\mathbb{P}$ as

$$(t,\omega )\in [0,1)\times \mathrm{\Omega }\mapsto (R_1(t)X_1(\omega ),R_2(t)X_2(\omega ),\dots )\in {\mathbb{R}}^{{\mathbb{Z}}^{+}}$$

has under $\mathbb{Q}$.

Now, from Hoeffding's inequality, we know that for a given $\{{\sigma }_k{\}}_{k=1}^n\in \mathbb{R}$ and mutually independent random variables $\{X_i{\}}_{i=1}^n$ with common distribution $\mu$, the centered Bernoulli distribution given by $\mu (\{\pm 1\})=\frac{1}{2}$, if $\nu$ denotes the distribution $S:=\sum _1^n{\sigma }_k{X}_k$, then for all $a\in [0,\mathrm{\infty })$, we have

$$\mathbb{P}(|S|\ge a)\le 2\exp [-\frac{a^2}{2{\mathrm{\Sigma }}^2}]$$

where ${\mathrm{\Sigma }}^2:=\sum _1^n{\sigma }_k^2$. We use this with ${\sigma }_k=X_k(\omega )$ and note that

$${\lambda }_{[0,1)}\left(\{t\in [0,1):|\sum _{n=1}^{2^m}{R}_n(t)X_n(\omega )|\ge a\}\right)\le 2\exp [-\frac{a^2}{2\sum _1^{2^m}{X}_n(\omega {)}^2}]$$

for all $a\in [0,\mathrm{\infty })$ and $\omega \in \mathrm{\Omega }$.

So, if we define

$$A_m:=\{\omega \in \mathrm{\Omega }:\frac{1}{2^m}\sum _{n=1}^{2^m}{X}_m(\omega {)}^2\ge 2\}$$

and

$$F_m(\omega ):={\lambda }_{[0,1)}\left(\{t\in [0,1):|\sum _{n=1}^{2^m}{R}_n(t)X_n(\omega )|\ge 2^{3/2}{\mathrm{\Lambda }}_{2^m}\}\right)$$

then we have

$$\begin{array}{rl}\mathbb{P}\left(\{\omega \in \mathrm{\Omega }:|S_{2^m}(\omega )|\ge 2^{3/2}{\mathrm{\Lambda }}_{2^m}\}\right)& ={\int }_{\mathrm{\Omega }}{F}_m(\omega )\mathbb{P}\left(\text{d}\omega \right)\\ & \le 2{\int }_{\mathrm{\Omega }}\exp [-\frac{8{\mathrm{\Lambda }}_{2^m}^2}{2\sum _1^{2^m}{X}_n(\omega )}]\mathbb{P}\left(\text{d}\omega \right)\\ & \le 2\exp [-4\log \log 2^m]+2\mathbb{P}\left(A_m\right)\end{array}$$

due to Tonelli's Theorem.

So, it is enough to show $\sum _0^{\mathrm{\infty }}\mathbb{P}\left(A_m\right)<\mathrm{\infty }$. To do so, let us set

$$T_m:=\sum _{n=1}^{2^m}{X}_n^2{B}_m:=\{\frac{T_{m+1}-T_m}{2^m}\ge 2\}{\overline{T}}_m:=\frac{T_m}{2^m}$$

for $m\in {\mathbb{Z}}^{+}$. Clearly $\{B_m{\}}_{m\in {\mathbb{Z}}^{+}}$ are independent and $\mathbb{P}\left(A_m\right)=\mathbb{P}\left(B_m\right)$. So, it is enough to show

$$\mathbb{P}\left(\underset{m\to \mathrm{\infty }}{lim sup}{B}_m\right)=\mathbb{P}(\underset{m\to \mathrm{\infty }}{lim sup}\frac{T_{m+1}-T_m}{2^m}\ge 2)=0$$

and then use Borel-Cantelli Lemma.

But, by Strong Law of Large Numbers, we know ${\overline{T}}_m\to 1$ almost surely, and hence

$$\frac{T_{m+1}-T_m}{2^m}\to 1$$

almost surely. This completes the proof for the symmetric case replacing the constant $8$ by $4$.

To eliminate the symmetry assumption, let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be the space on which $X_n$'s are defined and define $\{Y_n\}$ on $({\mathrm{\Omega }}^2,{\mathcal{F}}^2,{\mathbb{P}}^2)$ as

$$Y_n({\omega }_1,{\omega }_2):=X_n({\omega }_1)-X_n({\omega }_2)$$

for $n\in {\mathbb{Z}}^{+}$. It is easy to check that the $Y_n$'s are symmetric. This gives

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{|S_n({\omega }_1)-S_n({\omega }_2)|}{{\mathrm{\Lambda }}_n}\le 2^{5/2}\le 8$$

for $\mathbb{Q}$ almost every $({\omega }_1,{\omega }_2)\in {\mathrm{\Omega }}^2$.

Now, we wish to proceed by contradiction. If possible, let

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{|S_n(\omega )|}{{\mathrm{\Lambda }}_n}>8$$

on a set of positive $\mathbb{P}$ measure so that by Kolmogorov's $0-1$ Law, there is an $\epsilon >0$ such that

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{|S_n(\omega )|}{{\mathrm{\Lambda }}_n}\ge 8+\epsilon$$

for $\mathbb{P}$ almost every $\omega \in \mathrm{\Omega }$. Using Fubini's Theorem, this gives that for ${\mathbb{P}}^2$ almost every $({\omega }_1,{\omega }_2)\in {\mathrm{\Omega }}^2$, there is a $\{n_m({\omega }_1):m\in {\mathbb{Z}}^{+}\}\subset {\mathbb{Z}}^{+}$ such that $n_m({\omega }_1)$ increases to $\mathrm{\infty }$ so that the limit

$$\underset{m\to \mathrm{\infty }}{lim}\frac{S_{n_m({\omega }_1)}({\omega }_1)}{{\mathrm{\Lambda }}_{n_m(\omega )}}\ge 8+\epsilon$$

exists and

$$\underset{m\to \mathrm{\infty }}{lim inf}\frac{|S_{n_m({\omega }_1)}({\omega }_2)|}{{\mathrm{\Lambda }}_{n_m({\omega }_1)}}\ge \underset{m\to \mathrm{\infty }}{lim}\frac{S_{n_m({\omega }_1)}({\omega }_1)}{{\mathrm{\Lambda }}_{n_m(\omega )}}-\underset{m\to \mathrm{\infty }}{lim sup}\frac{|S_{n_m(\omega )}({\omega }_1)-S_{n_m(\omega )}({\omega }_2)|}{{\mathrm{\Lambda }}_{n_m({\omega }_1)}}\ge \epsilon$$

so that by Fubini's Theorem, we have an $\{n_m:m\in {\mathbb{Z}}^{+}\}\subset {\mathbb{Z}}^{+}$ such that $n_m$ increases to $\mathrm{\infty }$ and

$$\underset{m\to \mathrm{\infty }}{lim inf}\frac{|S_{n_m}({\omega }_2)|}{{\mathrm{\Lambda }}_{n_m}}\ge \epsilon$$

for $\mathbb{P}$ almost every ${\omega }_2\in \mathrm{\Omega }$. This contradicts Markov's Inequality owing to

$$\mathbb{E}\left[{\left(\frac{S_n}{{\mathrm{\Lambda }}_n}\right)}^2\right]=\frac{1}{2\log \log n}\to 0$$

hence completing the proof. $◻$

Proof of Lemma 3

As usual, we need to discuss some new ideas before we can move to our proof. We define

$${\mathrm{\Lambda }}_{\mu }(\xi ):=\log (M_{\mu }(\xi ))$$

and define the Legendre transform of ${\mathrm{\Lambda }}_{\mu }$ as

$$I_{\mu }(x):=sup\{\xi x-{\mathrm{\Lambda }}_{\mu }(\xi ):\xi \in \mathbb{R}\}$$

for $x\in \mathbb{R}$. Also, let ${\mathrm{\Xi }}_{\mu }:={\left({\mathrm{\Lambda }}_{\mu }^{\prime }\right)}^{-1}$.

Lemma 4 : There exists a $\delta \in (0,1]$ and a $K\in (0,\mathrm{\infty })$ such that $[m-\delta ,m+\delta ]\subset (\alpha ,\beta )$ and

$$|{\mathrm{\Lambda }}_{\mu }^{\prime \prime }(\mathrm{\Xi }(x))|\le K|{\mathrm{\Xi }}_{\mu }(x)|\le K|x-m|$$

and

$$|I_{\mu }(x)-\frac{(x-m{)}^2}{2{\sigma }^2}|\le K{|x-m|}^3$$

for all $x\in [m-\delta ,m+\delta ]$. In particular, if $0<\epsilon <\delta$, then

$$\mathbb{P}(|{\overline{S}}_n-m|\ge \epsilon )\le 2\exp [-n(\frac{{\epsilon }^2}{2{\sigma }^2}-K{\epsilon }^3)]$$

and if $|a-m|<\delta$, then

$$\mathbb{P}(|{\overline{S}}_n-m|<\epsilon )\ge (1-\frac{K}{n{\epsilon }^2})\exp [-n(\frac{|a-m{|}^2}{2{\sigma }^2}+K|a-m|(\epsilon +|a-m{|}^2))]$$

for any $\epsilon >0$.

Proof : Recall that we started with the assumption that our random variables have mean $0$ and variance $1$. So, we have ${\mathrm{\Lambda }}_{\mu }(0)={\mathrm{\Lambda }}_{\mu }^{\prime }(0)=0$ and ${\mathrm{\Lambda }}_{\mu }^{\prime \prime }(0)=1$ and hence ${\mathrm{\Xi }}_{\mu }(0)=0$ and ${\mathrm{\Xi }}_{\mu }^{\prime }(0)=1$. So, we can find an $M\in (0,\mathrm{\infty })$ and a $\delta \in (0,1]$ with $\alpha <-\delta <\delta <\beta$ for which

$$|{\mathrm{\Xi }}_{\mu }(x)-x|\le M|x{|}^2$$

whenever $|x|\le \delta$ and

$$|{\mathrm{\Lambda }}_{\mu }(\xi )-\frac{{\xi }^2}{2}|\le M|\xi {|}^3$$

whenever $|\xi |\le (M+1)\delta$. This immediately proves

$$|{\mathrm{\Xi }}_{\mu }(x)|\le (M+1)|x|$$

for $|x|\le \delta$ and the estimate for $I_{\mu }$ follows since $I_{\mu }(x)=\mathrm{\Xi }(x)x-{\mathrm{\Lambda }}_{\mu }({\mathrm{\Xi }}_{\mu }(x))$. $◻$

This gives us enough room to discuss our proof.

Proof of Lemma 3 : Begin by setting

$${\lambda }_n:=\frac{{\mathrm{\Lambda }}_n}{n}=\sqrt{\frac{2\log \log n}{n}}$$

wherever it is defined.

To prove the first part, we apply the upper bound of $\mathbb{P}(|{\overline{S}}_n-m|\ge \epsilon )$ obtained in Lemma 4 to see that

$$\mathbb{P}(\left|{\tilde{S}}_n\right|\ge R)=\mathbb{P}(\left|{\overline{S}}_n\right|\ge R{\lambda }_n)\le 2\exp [-n(\frac{R^2{\lambda }_n^2}{2}-K{R}^3{\lambda }_n^3)]$$

for sufficiently large $n\in {\mathbb{Z}}^{+}$.

To prove the next part of the lemma, we note

$$\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )=\mathbb{P}(|{\overline{S}}_n-a_n|<{\epsilon }_n)$$

where $a_n=a{\lambda }_n$ and ${\epsilon }_n=\epsilon {\lambda }_n$.So, using the lower bound on $\mathbb{P}(|{\overline{S}}_n-m|<\epsilon )$ obtained in Lemma 4 to conclude

$$\begin{array}{rl}\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )& \ge (1-\frac{K}{n{\epsilon }_n^2})\exp [-n(\frac{a_n^2}{2}+K|a_n|({\epsilon }_n+a_n^2))]\\ & \ge (1-\frac{K}{2{\epsilon }^2\log \log n})\exp [-(a^2+2K|a|(\epsilon +a^2{\lambda }_n))\log \log n]\end{array}$$

for sufficiently large $n$. $◻$

Acknowledgement : I'd like to thank Satvik Saha, who has been my partner in reading this proof, patiently answering my barrage of inane questions and making clever observations that I've shamelessly passed off as my own in this write-up. I feel safe admitting it here because, let’s be real, no one’s reading this far anyway.