Rationals are repeating $p$-adics

I've been amusing myself with $p$-adic arithmetic lately: I've never really got to know it until now.

We are all familiar with the fact that every $q\in\mathbf{Q}$ gets represented in $\mathbf{R}$ as a repeating decimal, or whatever your favourite base is. (Here I count terminating decimals as decimals which eventually repeat $000...$.) The converse is of course true as well: repeating decimals are rationals.

Is this true in $\mathbf{Q}_p$ as well? That is, are the rationals precisely those $p$-adics which are eventually repeating (in the other direction, of course)? One direction, that repeating $p$-adics are rational, is pretty obvious: if $a\in p^{-t}\mathbf{Z}$ and $b\in\mathbf{Z}$ then
\[
a + b p^r + b p^{r+s} + b p^{r+2s} + \cdots = a + b \frac{p^r}{1 - p^s}
\]
is rational. What about the converse?

The converse seems trickier. How again did we do it in $\mathbf{R}$? I don't even remember: it's one of those things that we know so fundamentally (until very recently, $\mathbf{Q}$ was almost defined in my brain as the reals which eventually repeat) that we forget how to prove it.

Who cares how to prove it? It is true, and it says, in base $p$, that if $q\in\mathbf{Q}$ then there exists $a\in p^{-t}\mathbf{Z}$ and $b\in\mathbf{Z}$ such that
\[
q = a + b p^r + b p^{r-s} + b p^{r-2s} + \cdots = a + b \frac{p^r}{1 - p^{-s}}.
\]
But hey, this implies that
\[
q = a - b \frac{p^{r+s}}{1 - p^s},
\]
which we already know is a repeating $p$-adic.

Inducing a Haar measure from a quotient

Suppose that $G$ is a locally compact group and that $H$ is a closed subgroup with an $H$-left-invariant regular Borel measure $\mu_H$ such that $G/H$ possesses a $G$-left-invariant regular Borel measure $\mu_{G/H}$. For instance, $G = \mathbf{R}$, $H=\mathbf{Z}$, and $G/H= S^1$. The following is how you then induce a Haar measure on $G$. (Technically, it's easier to construct Haar measure on compact groups, so this extends that construction slightly.)

For $f\in C_c(G)$, define $T_H(f) : G\to \mathbf{C}$ by
\[
T_H(f)(x) = \int_H f(xh) d\mu_H.
\]
Let $K=\text{supp}f$. Then $f(xh)$, as a function of $h$ is supported on $x^{-1} K$, so the above integral is finite. Moreover, if $x,y\in U$ and $U$ is compact, then
\[
|T_H(f)(x)  - T_H(f)(y)| = \left| \int_H (f(xh)-f(yh))d\mu_H\right| \leq \mu_H(H\cap U^{-1} K) \sup_h |f(xh)-f(yh)|.
\]
Because a continuous function on a compact set is uniformly continuous (in the sense that there exists a neighbourhood $V$ of $e$ such that $gh^{-1} \in V$ implies $|f(g)-f(h)| <\epsilon$), $T_H(f)$ is continous. Since $T_H(f)$ is $H$-right-invariant, $T_H(f)$ descends to a continuous function $\hat{T}_H(f)$ defined on $G/H$. Moreover, if $q$ is the quotient map $G\to G/H$, then $\hat{T}_H(f)$ is supported on $q(K)$, so $\hat{T}_H:C_c(G)\to C_c(G/H)$. Finally, define $\lambda: C_c(G)\to \mathbf{C}$ by
\[
\lambda(f) = \int_{G/H} \hat{T}_H(f) d\mu_{G/H}.
\]
This linear functional $\lambda$ is positive (in the sense that $f\geq0$ implies $\lambda(f)\geq0$), so the Riesz representation theorem guarantees the existence of a regular Borel measure $\mu_G$ on $G$ such that
\[
\lambda(f) = \int_G f d\mu_G
\]
for all $f\in C_c(G)$. It is now a simple matter to check that $\mu_G$ is $G$-left-invariant.

Deriving the normal distribution

When I was in high school, I asked several a person, "Why the normal distribution?" After all, the function $e^{-x^2/2}/\sqrt{2\pi}$ looks like a pretty bizarre function to guess, when there are other functions like $1/(1+x^2)$ which produce perfectly fine bell-shaped curves. One answer I received was that the normal distribution is in some sense the limit of the binomial distribution. While this answer seems fair enough, I tried my hand at the mathematics and did not succeed, so I was still confounded. None the less I believed the answer, and it satisfied me for the time.

The real answer that I was looking for but did not appreciate until university was the central limit theorem. For me, the central limit theorem is the explanation of the normal distribution. In any case, the calculation that I attempted was basically a verification of the central limit theorem in a simple case, and it is a testement to the force of the central limit theorem that that simple case is difficult to work out by hand.

In this post, I rectify that calculation that I should have accomplished in high school (with the benefit of hind-sight being the correct factor of $\sqrt{n}$ rather than $n$). On the way, I will also check both laws of large numbers in this simple case.

Consider a "random walk" on $\bf Z$. Specifically, let $X$ be a random variable taking the values $1$ and $-1$ each with probability $1/2$, and let
\[
S_n = X_1+X_2+\ldots+X_n,
\]
where each $X_i$ is an independent copy of $X$. Note that $(X+1)/2$ is Bernoulli, so $S_n/2 + n/2$ is binomial, so
\[
{\bf P}(S_n = k) = {\bf P}(S_n/2 + n/2 = k/2 + n/2) = \left(\begin{array}{c}n\\ k/2+n/2\end{array}\right) 2^{-n},
\]
where we make the convention that the binomial coefficient is zero when it doesn't make sense. Hence, if $x>0$,
\[
{\bf P}(S_n/n \geq x) = \sum_{k\geq x} {\bf P}(S_n/n = k) \leq \frac{n}{2} \left(\begin{array}{c} n\\\lceil (1+x)n/2\rceil \end{array}\right) 2^{-n}.
\]
By Stirling's formula, $m! \sim \sqrt{2\pi m} (m/e)^m$, so
\[
\left(\begin{array}{c}m\\k\end{array}\right) \sim \sqrt{\frac{m}{2\pi k(m-k)}} \frac{m^m}{k^k (m-k)^{m-k}}
\]
as $m,k\rightarrow\infty$. Hence, for constant $x>0$,
\[
{\bf P}(S_n/n \geq x) \leq \frac{n}{2} \left(\begin{array}{c} n\\\lceil (1+x)n/2\rceil \end{array}\right) 2^{-n} \sim \frac{\sqrt{n}}{\sqrt{2\pi(1-x^2)}} \left((1+x)^{1+x} (1-x)^{1-x}\right)^{-n/2}.

\]

Let $f(x) = (1+x)^{1+x} (1-x)^{1-x}$. Note that $f(x)>0$ for $0<x<1$, that $f(0)=1$, and that
\[
\frac{f^\prime(x)}{f(x)} = (\log f(x))^\prime = \log(1+x) + 1 - \log(1-x) - 1 = \log\left(\frac{1+x}{1-x}\right) > 0,
\]
so $f(x)>1$ for all $0<x<1$. Hence
\[
{\bf P}(S_n/n\geq x) \rightarrow 0,
\]
and by symmetry,
\[
{\bf P}(S_n/n\leq -x) \rightarrow 0,
\]
as $n\rightarrow\infty$. Thus we have verified the weak law.

In fact, because the convergence above is geometric,
\[
\sum_{n=1}^\infty {\bf P}(S_n/n\geq x) < \infty,
\]
whence
\[
{\bf P}(S_n/n\geq x\text{ infinitely often}) = \lim_{m\rightarrow\infty} {\bf P}(S_n/n\geq x\text{ for some }n\geq m)  \leq \lim_{m\rightarrow\infty} \sum_{n=m}^\infty {\bf P}(S_n/n\geq x) =0.
\]
(This is the Borel-Cantelli lemma.) Thus $S_n/n\rightarrow 0$ almost surely. Thus we have verified the strong law.

It remains to check the central limit theorem, i.e., to investigate the limiting distribution of $S_n/\sqrt{n}$. Now, for constant $x<y$,
\[
{\bf P}(x\leq S_n/\sqrt{n} \leq y) = \int_x^y\frac{\sqrt{n}}{2} \left(\begin{array}{c} n\\ (1+t/\sqrt{n})n/2\end{array}\right) 2^{-n} \,d\mu_n(t),
\]
where $\mu_n$ is the atomic measure assigning a mass $2/\sqrt{n}$ to each point of $(n+2{\bf Z})/\sqrt{n}$. Now Stirling's formula strikes again, giving
\[
\frac{\sqrt{n}}{2}\left(\begin{array}{c} n\\ (1+t/\sqrt{n})n/2\end{array}\right) 2^{-n} \sim \frac{1}{\sqrt{2\pi(1-t^2/n)}} \left((1+t/\sqrt{n})^{1+ t/\sqrt{n}} (1- t/\sqrt{n})^{1- t/\sqrt{n}}\right)^{-n/2} \longrightarrow \frac{1}{\sqrt{2\pi}} e^{-t^2/2},
\]
as
\[
\lim_{m\rightarrow\infty} \left((1+t/m)^{1+t/m} (1-t/m)^{1-t/m}\right)^{m^2/t^2} = \lim_{z\rightarrow\pm\infty} (1-1/z^2)^{z^2} (1+1/z)^z (1-1/z)^{-z} = e.
\]
Hence
\[
{\bf P}(x\leq S_n/\sqrt{n} \leq y) = \frac{1}{\sqrt{2\pi}} \int_x^y e^{-t^2/2}\,d\mu_n(t) + \int_x^y R_n(t)\,d\mu_n(t),
\]
where $R_n(t)\rightarrow 0$ as $n\rightarrow\infty$. Moreover this convergence is uniform in $t\in[x,y]$, so
\[
\left|\int_x^y R_n(t)\,d\mu_n(t)\right| \leq \mu_n([x,y]) \max_{x\leq t\leq y} |R_n(t)| \leq (y-x + 2/\sqrt{n})\max_{x\leq t\leq y} |R_n(t)| \rightarrow 0.
\]
Hence
\[
{\bf P}(x\leq S_n/\sqrt{n}\leq y) \rightarrow \frac{1}{\sqrt{2\pi}} \lim_{n\rightarrow\infty}\int_x^y e^{-t^2/2}\,d\mu_n(t) = \frac{1}{\sqrt{2\pi}}\int_x^y e^{-t^2/2}\,dt,
\]
where the last equality follows from the theorem that continuous functions are Riemann integrable. Thus we have verified the central limit theorem.