Rademacher functions

1 Binary expansions

Define $S:{\{0,1\}}^{\mathbb{N}}\to [0,1]$ by

$$S(\sigma )=\sum _{k=1}^{\mathrm{\infty }}\frac{{\sigma }_k}{2^k},\sigma \in {\{0,1\}}^{\mathbb{N}}.$$

For example, for ${\sigma }_1=0$ and ${\sigma }_2=1,{\sigma }_3=1,\mathrm{\dots }$,

$$S(\sigma )=\frac{0}{2}+\frac{1}{4}+\frac{1}{8}+\mathrm{\cdots }=\frac{1}{2};$$

for ${\sigma }_1=1$ and ${\sigma }_2=0$, ${\sigma }_3=0,\mathrm{\dots }$,

$$S(\sigma )=\frac{1}{2}+\frac{0}{4}+\frac{0}{8}+\mathrm{\cdots }=\frac{1}{2}.$$

Let $\sigma \in {\{0,1\}}^{\mathbb{N}}$. If there is some $n\in \mathbb{N}$ such that ${\sigma }_n=0$ and ${\sigma }_k=1$ for all $k\ge n+1$, then defining

we have

$$S(\sigma )=\sum _{k=1}^{n-1}\frac{{\sigma }_k}{2^k}+\sum _{k=n+1}^{\mathrm{\infty }}\frac{1}{2^k}=\sum _{k=1}^{n-1}\frac{{\sigma }_k}{2^k}+\frac{1}{2^n}=S(\tau ).$$

One proves that if either (i) there is some $n\in \mathbb{N}$ such that ${\sigma }_n=0$ and ${\sigma }_k=1$ for all $k\ge n+1$ or (ii) there is some $n\in \mathbb{N}$ such that ${\sigma }_n=1$ and ${\sigma }_k=0$ for all $k\ge n+1$, then $S^{-1}(S(\sigma ))$ contains exactly two elements, and that otherwise $S^{-1}(S(\sigma ))$ contains exactly one element.

In words, except for the sequence whose terms are only 0 or the sequence whose terms are only 1, $S^{-1}(S(\sigma ))$ contains exactly two elements when $\sigma$ is eventually $0$ or eventually $1$, and $S^{-1}(S(\sigma ))$ contains exactly one element otherwise.

We define $ϵ:[0,1]\to {\{0,1\}}^{\mathbb{N}}$ by taking $ϵ(t)$ to be the unique element of $S^{-1}(t)$ if $S^{-1}(t)$ contains exactly one element, and to be the element of $S^{-1}(t)$ that is eventually $0$ if $S^{-1}(t)$ contains exactly two elements. For $k\in \mathbb{N}$ we define ${ϵ}_k:[0,1]\to \{0,1\}$ by

$${ϵ}_k(t)=ϵ{(t)}_k,t\in [0,1].$$

Then, for all $t\in [0,1]$,

$$t=S(ϵ(t))=\sum _{k=1}^{\mathrm{\infty }}\frac{{ϵ}_k(t)}{2^k},$$ (1)

which we call the binary expansion of $t$.

2 Rademacher functions

For $k\in \mathbb{N}$, the $k$th Rademacher function $r_k:[0,1]\to \{-1,+1\}$ is defined by

$$r_k(t)=1-2{ϵ}_k(t),t\in [0,1].$$

We can rewrite the binary expansion of $t\in [0,1]$ in (1) as

$$\sum _{k=1}^{\mathrm{\infty }}\frac{r_k(t)}{2^k}=\sum _{k=1}^{\mathrm{\infty }}\left(\frac{1}{2^k}-2\cdot \frac{{ϵ}_k(t)}{2^k}\right)=1-2\sum _{k=1}^{\mathrm{\infty }}\frac{{ϵ}_k(t)}{2^k}=1-2t.$$ (2)

Define $r:ℝ\to \{-1,+1\}$ by

$$r(x)={(-1)}^{[x]},$$

where $[x]$ denotes the greatest integer $\le x$. Thus, for we have $r(x)=1$, for we have $r(x)=-1$, and $r$ has period $2$.

Lemma 1.

For any $n\mathrm{\in }\mathrm{N}$,

$$r_n(t)={(-1)}^{[2^{n}t]}=r(2^{n}t),t\in [0,1]$$

In the following theorem we use the Rademacher functions to prove an identity for trigonometric functions.

Theorem 2.

For any nonzero real $x$,

$$\prod _{k=1}^{\mathrm{\infty }}\cos \frac{x}{2^k}=\frac{\sin x}{x}.$$

Proof.

Let $n\in \mathbb{N}$ and let $c_1,\mathrm{\dots },c_n\in ℝ$. The function

$$\sum _{k=1}^n{c}_k{r}_k$$

is constant on each of the intervals

$$[\frac{s}{2^n},\frac{s+1}{2^n}),0\le s\le 2^n-1.$$ (3)

There is a bijection between ${\mathrm{\Delta }}_n={\{-1,+1\}}^n$ and the collection of intervals (3). Without explicitly describing this bijection, we have

${\displaystyle {\int }_0^1}\exp \left(i{\displaystyle \sum _{k=1}^n}{c}_k{r}_k(t)\right)𝑑t$ $=$ ${\displaystyle \sum _{s=0}^{2^n-1}}{\displaystyle {\int }_{s\cdot 2^{-n}}^{(s+1)\cdot 2^{-n}}}\exp \left(i{\displaystyle \sum _{k=1}^n}{c}_k{r}_k(t)\right)𝑑t$

$=$ ${\displaystyle \sum _{\delta \in {\mathrm{\Delta }}_n}}{\displaystyle \frac{1}{2^n}}\exp \left(i{\displaystyle \sum _{k=1}^n}{\delta }_k{c}_k\right)$

$=$ ${\displaystyle \sum _{\delta \in {\mathrm{\Delta }}_n}}{\displaystyle \prod _{k=1}^n}{\displaystyle \frac{e^{i{\delta }_k{c}_k}}{2}}$

$=$ ${\displaystyle \prod _{k=1}^n}{\displaystyle \frac{e^{i{c}_k}+e^{-i{c}_k}}{2}},$

giving

$${\int }_0^1\exp \left(i\sum _{k=1}^n{c}_k{r}_k(t)\right)𝑑t=\prod _{k=1}^n\cos c_k.$$ (4)

We have

$${\int }_0^1{e}^{ix(1-2t)}𝑑t={e^{ix}\frac{e^{-2ixt}}{-2ix}|}_0^1=e^{ix}\left(\frac{e^{-2ix}}{-2ix}+\frac{1}{2ix}\right)=\frac{\sin x}{x}.$$ (5)

Using (2) we check that the sequence of functions ${\sum }_{k=1}^n\frac{r_k(t)}{2^k}$ converges uniformly on $[0,1]$ to $1-2t$, and hence using (5) we get

$${\int }_0^1\exp \left(ix\sum _{k=1}^n\frac{r_k(t)}{2^k}\right)dt\to {\int }_0^1{e}^{ix(1-2t})dt=\frac{\sin x}{x}$$

as $n\to \mathrm{\infty }$. Combining this with (4), which we apply with $c_k=\frac{x}{2^k}$, we get

$$\prod _{k=1}^n\cos \frac{x}{2^k}\to \frac{\sin x}{x}$$

as $n\to \mathrm{\infty }$, proving the claim. ∎

We now give an explicit formula for the measure of those $t$ for which exactly $l$ of $r_1(t),\mathrm{\dots },r_n(t)$ are equal to $1$. We denote by $\mu$ Lebesgue measure on $ℝ$. We can interpret the following formula as stating the probability that out of $n$ tosses of a coin, exactly $l$ of the outcomes are heads.

Theorem 3.

For $n\mathrm{\in }\mathrm{N}$ and $\mathrm{0}\mathrm{\le }l\mathrm{\le }n$,

$$\mu \{t\in [0,1]:r_1(t)+\mathrm{\cdots }+r_n(t)=2l-n\}=\frac{1}{2^n}\left(\genfrac{}{}{0pt}{}{n}{l}\right).$$

Proof.

Define $\varphi :[0,1]\to ℝ$ by

$$\varphi (t)=\frac{1}{2\pi }{\int }_0^{2\pi }{e}^{ix\left(-(2l-n)+{\sum }_{k=1}^n{r}_k(t)\right)}𝑑x$$

But for $m\in \mathbb{Z}$,

(6)

hence

Therefore

$\mu \{t\in [0,1]:{\displaystyle \sum _{k=1}^n}{r}_k(t)=2l-n\}$ $=$ ${\displaystyle {\int }_0^1}\varphi (t)𝑑t$

$=$ ${\displaystyle {\int }_0^1}{\displaystyle \frac{1}{2\pi }}{\displaystyle {\int }_0^{2\pi }}{e}^{ix\left(-(2l-n)+{\sum }_{k=1}^n{r}_k(t)\right)}𝑑x𝑑t$

$=$ ${\displaystyle \frac{1}{2\pi }}{\displaystyle {\int }_0^{2\pi }}{e}^{-ix(2l-n)}{\displaystyle {\int }_0^1}{e}^{ix{\sum }_{k=1}^n{r}_k(t)}𝑑t𝑑x$

$=$ ${\displaystyle \frac{1}{2\pi }}{\displaystyle {\int }_0^{2\pi }}{e}^{-ix(2l-n)}{\cos }^{n}xdx;$

the last equality uses (4) with $c_1=x,\mathrm{\dots },c_n=x$. Furthermore, writing

$${\cos }^{n}x=2^{-n}(e^{ix}+e^{-ix})=2^{-n}\sum _{k=0}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)e^{ix(2k-n)},$$

we calculate using (6) that

${\displaystyle \frac{1}{2\pi }}{\displaystyle {\int }_0^{2\pi }}{e}^{-ix(2l-n)}{\cos }^{n}xdx$ $=$ $2^{-n}{\displaystyle \sum _{k=0}^n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){\displaystyle \frac{1}{2\pi }}{\displaystyle {\int }_0^1}{e}^{-ix(2l-n)}{e}^{ix(2k-n)}𝑑x$

$=$ $2^{-n}{\displaystyle \sum _{k=0}^n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){\displaystyle \frac{1}{2\pi }}{\displaystyle {\int }_0^1}{e}^{ix(2k-2l)}𝑑x$

$=$ $2^{-n}{\displaystyle \sum _{k=0}^n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){\delta }_{2k-2l,0}$

$=$ $2^{-n}{\displaystyle \sum _{k=0}^n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){\delta }_{k,l}$

$=$ $2^{-n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{l}}\right),$

proving the claim. ∎

We now prove that the expected value of a product of distinct Rademacher functions is equal to the product of their expected values.

Theorem 4.

If $k_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{k}_n$ are positive integers and , then

$${\int }_0^1{r}_{k_1}(t)\mathrm{\cdots }{r}_{k_n}(t)𝑑t=0.$$

Proof.

Write $J={\int }_0^1{r}_{k_1}(t)\mathrm{\cdots }{r}_{k_n}(t)𝑑t$ and define

$$\varphi (x)=\prod _{s=2}^{n}r(2^{k_s-k_1}x),x\in ℝ,$$

which satisfies

$$\varphi (x+1)=\prod _{s=2}^{n}r(2^{k_s-k_1}x+2^{k_s-k_1})=\prod _{s=2}^{n}r(2^{k_s-k_1}x)=\varphi (x).$$

Hence, as $\varphi$ has period $1$ and $r$ has period $2$,

$J$ $=$ ${\displaystyle {\int }_0^1}{r}_{k_1}(t)\varphi (2^{k_1}t)𝑑t$

$=$ ${\displaystyle {\int }_0^1}r(2^{k_1}t)\varphi (2^{k_1}t)𝑑t$

$=$ ${\displaystyle \frac{1}{2^{k_1}}}{\displaystyle {\int }_0^{2^{k_1}}}r(x)\varphi (x)𝑑x$

$=$ ${\displaystyle \frac{1}{2^{k_1}}}{\displaystyle \sum _{j=0}^{2^{k_1-1}-1}}{\displaystyle {\int }_{2j}^{2j+2}}r(x)\varphi (x)𝑑x$

$=$ ${\displaystyle \frac{1}{2^{k_1}}}{\displaystyle \sum _{j=0}^{2^{k_1-1}-1}}{\displaystyle {\int }_0^2}r(x)\varphi (x)𝑑x$

$=$ ${\displaystyle \frac{1}{2}}{\displaystyle {\int }_0^2}r(x)\varphi (x)𝑑x.$

But, as $\varphi$ has period $1$,

$${\int }_0^{2}r(x)\varphi (x)𝑑x={\int }_0^1\varphi (x)𝑑x-{\int }_1^2\varphi (x)𝑑x={\int }_0^1\varphi (x)𝑑x-{\int }_0^1\varphi (x)𝑑x=0,$$

hence $J=0$, proving the claim. ∎

For each $n\in \mathbb{N}$, if $f$ is a function defined on the integers we define

$$I_n(f)={\int }_0^{1}f\left(\sum _{k=1}^n{r}_k(t)\right)𝑑t.$$

Lemma 5.

For any $n\mathrm{\in }\mathrm{N}$,

$$I_n(x^2)=n,I_n(x^4)=3n^2-2n.$$

Proof.

Using Theorem 4 we get

$I_n(x^2)$ $=$ ${\displaystyle {\int }_0^1}{\left({\displaystyle \sum _{k=1}^n}{r}_k(t)\right)}^2𝑑t$

$=$ ${\displaystyle {\int }_0^1}{\displaystyle \sum _{k=1}^n}{r}_k{(t)}^2+{\displaystyle \sum _{j\ne k}}{r}_j(t)r_k(t)dt$

$=$ ${\displaystyle {\int }_0^1}{\displaystyle \sum _{k=1}^n}{r}_k{(t)}^{2}dt$

$=$ $n.$

Using Theorem 4 we get, since $r_j{(t)}^4=r_j{(t)}^2=1$ and $r_j{(t)}^3=r_j(t)$,

$I_n(x^4)$ $=$ ${\displaystyle {\int }_0^1}{\left({\displaystyle \sum _{k=1}^n}{r}_k(t)\right)}^4𝑑t$

$=$ ${\displaystyle {\int }_0^1}{\displaystyle \sum _{k=1}^n}{r}_k{(t)}^4+\left({\displaystyle \genfrac{}{}{0pt}{}{4}{3}}\right){\displaystyle \sum _{j=1}^n}{\displaystyle \sum _{k\ne j}}{r}_j{(t)}^3{r}_k(t)+\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right){\displaystyle \sum _{j=1}^n}{\displaystyle \sum _{k\ne j}}{r}_j{(t)}^2{r}_k{(t)}^2$

$+\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right){\displaystyle \sum _{j=1}^n}{\displaystyle \sum _{j,k,l\text{ all distinct}}}{r}_j{(t)}^2{r}_k(t)r_l(t)$

$+{\displaystyle \sum _{j,k,l,m\text{ all distinct}}}{r}_j(t)r_k(t)r_l(t)r_m(t)dt$

$=$ $n+\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right)n(n-1).$

∎

Our proof of the next identity follows Hata.

Lemma 6.

For any $n\mathrm{\in }\mathrm{N}$,

$$I_n(|x|)=\frac{2}{\pi }{\int }_0^{\mathrm{\infty }}\frac{1-{\cos }^{n}x}{x^2}𝑑x.$$

Proof.

For $n\in \mathbb{N}$ and $c_1,\mathrm{\dots },c_n\in ℝ$,

$${\int }_0^1\exp \left(i\sum _{k=1}^n{c}_k{r}_k(t)\right)𝑑t={\int }_0^1\cos \left(\sum _{k=1}^n{c}_k{r}_k(t)\right)𝑑t+i{\int }_0^1\sin \left(\sum _{k=1}^n{c}_k{r}_k(t)\right)𝑑t,$$

and since (4) tells us that the left-hand side of the above is real, it follows that we can write (4) as

$${\int }_0^1\cos \left(\sum _{k=1}^n{c}_k{r}_k(t)\right)𝑑t=\prod _{k=1}^n\cos c_k.$$ (7)

Suppose that $\xi$ is a positive real number. Using $t=x\xi$ and doing integration by parts,

${\displaystyle {\int }_0^{\mathrm{\infty }}}{\displaystyle \frac{1-\cos x\xi }{x^2}}𝑑x$ $=$ $\xi {\displaystyle {\int }_0^{\mathrm{\infty }}}{\displaystyle \frac{1-\cos t}{t^2}}𝑑t$

$=$ ${\xi {\displaystyle \frac{1-\cos t}{-t}}|}_0^{\mathrm{\infty }}+\xi {\displaystyle {\int }_0^{\mathrm{\infty }}}{\displaystyle \frac{\sin t}{t}}𝑑t$

$=$ $\xi {\displaystyle {\int }_0^{\mathrm{\infty }}}{\displaystyle \frac{\sin t}{t}}𝑑t$

$=$ $\xi {\displaystyle \frac{\pi }{2}}.$

It is thus apparent that for any real $\xi$,

$${\int }_0^{\mathrm{\infty }}\frac{1-\cos x\xi }{x^2}𝑑x=|\xi |\frac{\pi }{2}.$$

For any $n\in \mathbb{N}$, applying the above with $\xi ={\sum }_{k=1}^n{r}_k(t)$ we get

$I_n(|x|)$ $=$ ${\displaystyle \frac{2}{\pi }}{\displaystyle {\int }_0^1}\left|{\displaystyle \sum _{k=1}^n}{r}_k(t)\right|{\displaystyle \frac{\pi }{2}}𝑑t$

$=$ ${\displaystyle \frac{2}{\pi }}{\displaystyle {\int }_0^1}{\displaystyle {\int }_0^{\mathrm{\infty }}}{\displaystyle \frac{1-\cos \left(x{\sum }_{k=1}^n{r}_k(t)\right)}{x^2}}𝑑x𝑑t$

$=$ ${\displaystyle \frac{2}{\pi }}{\displaystyle {\int }_0^{\mathrm{\infty }}}{\displaystyle \frac{1}{x^2}}{\displaystyle {\int }_0^1}1-\cos \left(x{\displaystyle \sum _{k=1}^n}{r}_k(t)\right)dtdx$

$=$ ${\displaystyle \frac{2}{\pi }}{\displaystyle {\int }_0^{\mathrm{\infty }}}{\displaystyle \frac{1}{x^2}}(1-I_n(\cos x\cdot ))dx.$

Applying (7) with $c_k=x$ for each $k$, this is equal to

$$\frac{2}{\pi }{\int }_0^{\mathrm{\infty }}\frac{1}{x^2}\left(1-\prod _{k=1}^n\cos x\right)𝑑x=\frac{2}{\pi }{\int }_0^{\mathrm{\infty }}\frac{1-{\cos }^{n}x}{x^2}𝑑x,$$

completing the proof. ∎

We use the above formula for $I_n(|x|)$ to obtain an asymptotic formula for $I_n(|x|)$.

Theorem 7.

$$I_n(|x|)\sim \sqrt{\frac{2}{\pi }}\sqrt{n}.$$

Proof.

By Lemma 6,

$$I_n(|x|)=\frac{2}{\pi }{\int }_0^{\mathrm{\infty }}\frac{1-{\cos }^{n}x}{x^2}𝑑x.$$

For , define ${\varphi }_{ϵ}:[0,\frac{\pi }{2})\to ℝ$ by

$${\varphi }_{ϵ}(x)=\frac{x^2}{2(1-ϵ)}+\log \cos x.$$

We also define

$${\alpha }_{ϵ}=\arccos \sqrt{1-ϵ},{\beta }_{ϵ}={\int }_{{\alpha }_{ϵ}}^{\mathrm{\infty }}\frac{1-{\cos }^{n}x}{x^2}𝑑x,$$

and for $\sigma >0$,

$$K_{ϵ,\sigma }={\int }_0^{{\alpha }_{ϵ}}\frac{1-\exp \left(-\frac{n{x}^2}{\sigma }\right)}{x^2}𝑑x.$$

Let . Until the end of the proof, at which point we take $ϵ\to 0$, we shall keep $ϵ$ fixed. For we have, using $\arccos \sqrt{1-ϵ}\le \sqrt{ϵ}$,

hence

On the other hand,

$${\varphi }_{ϵ}^{\prime }(x)=\frac{x}{1-ϵ}-\tan x,{\varphi }_{ϵ}^{\prime \prime }(x)=\frac{1}{1-ϵ}-{\sec }^{2}x,$$

so ${\varphi }_{ϵ}(0)={\varphi }_{ϵ}^{\prime }(0)=0$ and ${\varphi }_{ϵ}^{\prime \prime }(t)>0$ for all , giving

$${\varphi }_{ϵ}(x)>0,$$

and hence

Collecting what we have established so far, for we have

This shows that

$$K_{ϵ,2(1-ϵ)}={\int }_0^{{\alpha }_{ϵ}}\frac{1-\exp \left(-\frac{n{x}^2}{2(1-ϵ)}\right)}{x^2}𝑑x\ge {\int }_0^{{\alpha }_{ϵ}}\frac{1-{\cos }^{n}x}{x^2}𝑑x,$$

and therefore

$$K_{ϵ,2(1-ϵ)}+{\beta }_{ϵ}\ge \frac{\pi }{2}{I}_n(|x|).$$

On the other hand,

$$K_{ϵ,2}={\int }_0^{{\alpha }_{ϵ}}\frac{1-\exp \left(-\frac{n{x}^2}{2}\right)}{x^2}𝑑x\le {\int }_0^{{\alpha }_{ϵ}}\frac{1-{\cos }^{n}x}{x^2}𝑑x,$$

so

$$K_{ϵ,2}+{\beta }_{ϵ}\le \frac{\pi }{2}{I}_n(|x|).$$

Now summarizing what we have obtained, we have

$$K_{ϵ,2}+{\beta }_{ϵ}\le \frac{\pi }{2}{I}_n(|x|)\le K_{ϵ,2(1-ϵ)}+{\beta }_{ϵ}.$$ (8)

For $\sigma >0$, doing the change of variable $t=\sqrt{\frac{n}{\sigma }}x$,

$$K_{ϵ,\sigma }={\int }_0^{{\alpha }_{ϵ}}\frac{1-\exp \left(-\frac{n{x}^2}{\sigma }\right)}{x^2}𝑑x=\sqrt{\frac{n}{\sigma }}{\int }_0^{\sqrt{\frac{n}{\sigma }}{\alpha }_{ϵ}}\frac{1-e^{-t^2}}{t^2}𝑑t.$$

As $n\to \mathrm{\infty }$, the right-hand side of this is asymptotic to

$$\sqrt{\frac{n}{\sigma }}{\int }_0^{\mathrm{\infty }}\frac{1-e^{-t^2}}{t^2}𝑑t=\sqrt{\frac{n}{\sigma }}\sqrt{\pi }.$$

Dividing (8) by $\sqrt{n}$ and taking the limsup then gives

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{\pi }{2}\frac{I_n(|x|)}{\sqrt{n}}\le \sqrt{\frac{\pi }{2(1-ϵ)}},$$

or

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{I_n(|x|)}{\sqrt{n}}\le \sqrt{\frac{2}{\pi (1-ϵ)}};$$

indeed ${\beta }_{ϵ}$ depends on $n$, but , which does not depend on $n$. Taking $ϵ\to 0$ yields

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{I_n(|x|)}{\sqrt{n}}\le \sqrt{\frac{2}{\pi }}.$$

On the other hand, taking the liminf of (8) divided by $\sqrt{n}$ gives

$$\underset{n\to \mathrm{\infty }}{lim\; inf}\frac{\pi }{2}\frac{I_n(|x|)}{\sqrt{n}}\ge \sqrt{\frac{\pi }{2}},$$

or

$$\underset{n\to \mathrm{\infty }}{lim\; inf}\frac{I_n(|x|)}{\sqrt{n}}\ge \sqrt{\frac{2}{\pi }}.$$

Combining the limsup and the liminf inequalities proves the claim. ∎

Lemma 8.

For any $\xi \mathrm{\in }\mathrm{R}$ and $n\mathrm{\in }\mathrm{N}$,

We will use the following theorem to establish an estimate similar to but weaker than the law of the iterated logarithm.

Theorem 9.

For any $ϵ\mathrm{>}\mathrm{0}$, for almost all $t\mathrm{\in }\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{]}$,

Proof.

Define $f_n:[0,1]\to (0,\mathrm{\infty })$ by

$$f_n(t)=\frac{1}{n^{2+ϵ}}\exp \left(\sqrt{\frac{2\log n}{n}}\left|\sum _{k=1}^n{r}_k(t)\right|\right).$$

Applying Lemma 8 with $\xi =\sqrt{\frac{2\log n}{n}}$,

$${\int }_0^1{f}_n(t)𝑑t\le \frac{1}{n^{2+ϵ}}\cdot 2\cdot {\left(\cosh \sqrt{\frac{2\log n}{n}}\right)}^n.$$

It is not obvious, but we take as given the asymptotic expansion

$${\left(\cosh \sqrt{\frac{2\log n}{n}}\right)}^n=n-\frac{1}{3}{(\log n)}^2+\frac{\frac{8}{45}{(\log n)}^3+\frac{1}{18}{(\log n)}^4}{n}+O(n^{-3/2}),$$

and using this,

$$\frac{1}{n^{2+ϵ}}\cdot 2\cdot {\left(\cosh \sqrt{\frac{2\log n}{n}}\right)}^n=\frac{2}{n^{1+ϵ}}+O\left(\frac{{(\log n)}^2}{n^{2+ϵ}}\right)=\frac{2}{n^{1+ϵ}}+O(n^{-2}).$$

Thus

Because each $f_n$ is nonnegative, using this with the monotone convergence theorem gives the claim. ∎

Theorem 10.

For almost all $t\mathrm{\in }\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{]}$,

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{\left|{\sum }_{k=1}^n{r}_k(t)\right|}{\sqrt{n\log n}}\le \sqrt{2}.$$

Proof.

Let $ϵ>0$. By Theorem 9, for almost all $t\in [0,1]$ there is some $n_t$ such that $n\ge n_t$ implies that , where we are talking about the functions $f_n$ defined in the proof of that theorem; certainly the terms of a convergent series are eventually less than $1$. That is, for almost all $t\in [0,1]$ there is some $n_t$ such that $n\ge n_t$ implies that (taking logarithms),

and rearranging,

For each $s\in \mathbb{N}$, let $E_s$ be those $t\in [0,1]$ such that

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{\left|{\sum }_{k=1}^n{r}_k(t)\right|}{\sqrt{n\log n}}>\sqrt{2}+\frac{1}{s}.$$

For each $s$, taking we get that almost all $t\in [0,1]$ do not belong to $E_s$. That is, for each $s$, the set $E_s$ has measure $0$. Therefore

$$E=\bigcup _{s=1}^{\mathrm{\infty }}{E}_s$$

has measure $0$. That is, for almost all $t\in [0,1]$, for all $s\in \mathbb{N}$ we have $t\notin E_s$, i.e.

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{\left|{\sum }_{k=1}^n{r}_k(t)\right|}{\sqrt{n\log n}}\le \sqrt{2}+\frac{1}{s},$$

and this holding for all $s\in \mathbb{N}$ yields

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{\left|{\sum }_{k=1}^n{r}_k(t)\right|}{\sqrt{n\log n}}\le \sqrt{2},$$

completing the proof. ∎

3 Hypercubes

Let $m_n$ be Lebesgue measure on ${ℝ}^n$, and let $Q_n={[0,1]}^n$.

Theorem 11.

If $f\mathrm{\in }C\mathit{}\mathrm{(}\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{]}\mathrm{)}$, then

$$\underset{n\to \mathrm{\infty }}{lim}{\int }_{Q_n}f\left(\frac{x_1+\mathrm{\cdots }+x_n}{n}\right)𝑑m_n(x)=f\left(\frac{1}{2}\right).$$

Proof.

Define $X_n:Q_n\to ℝ$ by

$$X_n=\frac{x_1+\mathrm{\cdots }+x_n}{n},x\in Q_n.$$

We have

$${\int }_{Q_n}{X}_n𝑑m_n(x)=\frac{1}{n}\sum _{k=1}^n{\int }_0^1{x}_k\cdot 1𝑑x_k=\frac{1}{n}\sum _{k=1}^n\frac{1}{2}=\frac{1}{2},$$

and we define

$V_n$ $=$ ${\displaystyle {\int }_{Q_n}}{\left(X_n-{\displaystyle \frac{1}{2}}\right)}^2𝑑m_n(x)$

$=$ ${\displaystyle {\int }_{Q_n}}{\displaystyle \sum _{k=1}^n}{\displaystyle \frac{x_k^2}{n^2}}+{\displaystyle \sum _{j\ne k}}{\displaystyle \frac{x_j{x}_k}{n^2}}-X_n+{\displaystyle \frac{1}{4}}d{m}_n(x)$

$=$ ${\displaystyle \frac{1}{n^2}}{\displaystyle \sum _{k=1}^n}{\displaystyle {\int }_0^1}{x}_k^2𝑑x_k+{\displaystyle \frac{1}{n^2}}{\displaystyle \sum _{j=1}^n}{\displaystyle \sum _{k\ne j}}{\displaystyle {\int }_0^1}{x}_j𝑑x_j{\displaystyle {\int }_0^1}{x}_k𝑑x_k-{\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{4}}$

$=$ ${\displaystyle \frac{1}{n^2}}{\displaystyle \sum _{k=1}^n}{\displaystyle \frac{1}{3}}+{\displaystyle \frac{1}{n^2}}{\displaystyle \sum _{j=1}^n}{\displaystyle \sum _{k\ne j}}{\displaystyle \frac{1}{4}}-{\displaystyle \frac{1}{4}}$

$=$ ${\displaystyle \frac{1}{3n}}+{\displaystyle \frac{n-1}{4n}}-{\displaystyle \frac{1}{4}}$

$=$ ${\displaystyle \frac{n^{-1}}{12}}.$

Suppose that $c_n$ is a sequence of positive real numbers tending to $0$, and define $J_n=J_n(c)$ to be those $x\in Q_n$ such that

$$\left|X_n(x)-\frac{1}{2}\right|\ge c_n.$$

Then

$V_n$ $=$ ${\displaystyle {\int }_{Q_n}}{\left(X_n-{\displaystyle \frac{1}{2}}\right)}^2𝑑m_n(x)$

$\ge$ ${\displaystyle {\int }_{J_n}}{\left(X_n-{\displaystyle \frac{1}{2}}\right)}^2𝑑m_n(x)$

$\ge$ ${\displaystyle {\int }_{J_n}}{c}_n^2𝑑m_n(x)$

$=$ $c_n^2{m}_n(J_n),$

so

$$m_n(J_n)\le \frac{V_n}{c_n^2}=\frac{n^{-1}}{12c_n^2}.$$

Take $c_n=n^{-1/3}$, giving

$$m_n(J_n)\le \frac{n^{-1/3}}{12}.$$

Let $ϵ>0$. Because $f$ is continuous, there is some $\delta >0$ such that implies that ; furthermore, we take $\delta$ such that

Set $N>{\delta }^{-3}$. For $n\ge N$ and $x\in Q_n\setminus J_n$,

and so

This gives us

$\left|{\displaystyle {\int }_{Q_n}}f(X_n(x))𝑑m_n(x)-f\left({\displaystyle \frac{1}{2}}\right)\right|$ $=$ $\left|{\displaystyle {\int }_{Q_n}}f(X_n(x))-f\left({\displaystyle \frac{1}{2}}\right)d{m}_n(x)\right|$

$\le$ ${\displaystyle {\int }_{J_n}}\left|f(X_n(x))-f\left({\displaystyle \frac{1}{2}}\right)\right|𝑑m_n(x)$

$+{\displaystyle {\int }_{Q_n\setminus J_n}}\left|f(X_n(x))-f\left({\displaystyle \frac{1}{2}}\right)\right|𝑑m_n(x)$

$\le$ ${\displaystyle {\int }_{J_n}}2{\parallel f\parallel }_{\mathrm{\infty }}𝑑m_n(x)+{\displaystyle {\int }_{Q_n\setminus J_n}}ϵ𝑑m_n(x)$

$\le$ $2{\parallel f\parallel }_{\mathrm{\infty }}{m}_n(J_n)+ϵ$

$\le$ $2{\parallel f\parallel }_{\mathrm{\infty }}{\displaystyle \frac{n^{-1/3}}{12}}+ϵ$

${\displaystyle \frac{{\parallel f\parallel }_{\mathrm{\infty }}\delta }{6}}+ϵ$

$2ϵ,$

which proves the claim. ∎