Categories

## Poisson Summation Formula and Basel Problem

This note is based on Professor Noam Elkies’ talk at Carnegie Mellon University on December 2, 2014.

A classical mathematical analysis problem, also known as the Basel problem, first posed by Pietro Mengoli in 1644 and solved by Leonhard Euler in 1735, asks the precise sum in closed form of the infinite series $$\sum_{n=1}^\infty \frac{1}{n^2} = \lim_{n\to\infty}\left(\frac{1}{1^2}+\frac{1}{2^2}+\ldots+\frac{1}{n^2}\right).$$

Here we present an attack to the Basel problem using the Poisson summation formula.

#### Poisson Summation Formula

The Poisson summation formula states that $$\sum_{n\in\mathbb{Z}}f(n) = \sum_{k\in\mathbb{Z}}\hat{f}(k),$$ where $f: \mathbb{R}\to\mathbb{R}$ is a “nice” function and $\hat{f}(\omega):=\int_\mathbb{R}f(x)e^{-2\pi i\omega x}dx$ is the Fourier transformation of $f$.

For the sake of completeness, we are going to prove the Poisson summation formula and specify how “nice” the function should be for the formula to work.

Proof. Let $R:\mathbb{R}\to\mathbb{R}$ be defined by $R(t) = \sum_{n\in\mathbb{Z}}f(n+t)$. Because $R(t+m) = R(t)$ for all $m\in\mathbb{Z}$, and so $R$ is a periodic function, we can expand $R(t)$ in the Fourier series $$R(t) = \sum_{k\in\mathbb{Z}}a_ke^{2\pi i kt},$$ where \begin{aligned}a_k & = \int_0^1R(t)e^{-2\pi ikt}dt \\ & = \int_0^1\sum_{n\in\mathbb{Z}}f(n+t)e^{-2\pi ikt}dt \\ & = \sum_{n\in\mathbb{Z}}\int_0^1f(n+t)e^{-2\pi ikt}dt \\ & = \sum_{n\in\mathbb{Z}}\int_n^{n+1}f(t)e^{-2\pi ikt}dt \\ & = \int_\mathbb{R}f(t)e^{-2\pi ikt}dt.\end{aligned} which equals the value at $-k$ of the Fourier transform $\hat{f}$ of $f$. We conclude that $$\sum_{n\in\mathbb{Z}}f(n) = R(0)=\sum_{k\in\mathbb{Z}}a_k = \sum_{k\in\mathbb{Z}}\hat{f}(k).$$

Remark. In order to use Fourier series for $R$, we need $R\in C^1$ to ensure that its Fourier series expansion $\sum_{n\in\mathbb{Z}}a_ke^{2\pi ikt}$ converges to $R(t)$ pointwise (and uniformly in fact). This allows us to evaluate $R$ at $0$ and equate it with $\sum_{k\in\mathbb{Z}} a_k$. On the other hand, we switched the integration and the infinite summation $$\int_0^1\sum_{n\in\mathbb{Z}}f(n+t)e^{-2\pi ikt}dt = \sum_{n\in\mathbb{Z}}\int_0^1f(n+t)e^{-2\pi ikt}dt,$$ in the computation. The Fubini–Tonelli theorem says that this is legit if $$\int_0^1\sum_{n\in\mathbb{Z}}\left|f(n+t)e^{-2\pi ikt}\right|dt = \int_0^1\sum_{n\in\mathbb{Z}}\left|f(n+t)\right|dt < \infty$$ or $$\sum_{n\in\mathbb{Z}}\int_0^1\left|f(n+t)e^{-2\pi ikt}\right|dt = \sum_{n\in\mathbb{Z}}\int_n^{n+1}|f(x)|dx = \int_\mathbb{R}|f(x)|dx < \infty.$$

#### Application to Basel Problem

Take $f(x) = \frac{1}{x^2+c^2}$, where $c > 0$ is a constant. For such $f$, $R(t) = \sum_{n\in\mathbb{Z}}f(n+t)$ defined above converges uniformly. As each $f(n+t)$ is continuous, so is $R$. As $\sum_{n\in\mathbb{Z}}f'(n+t) = \sum_{n\in\mathbb{Z}}\frac{-2(t+n)}{((t+n)+c^2)^2}$ converges uniformly, we have that $R'(t) = \sum_{n\in\mathbb{Z}}f'(n+t)$, and moreover, as $f'(n+t)$ is continuous, so is $R'$. Now $R$ is continuously differentiable, and so we can use Fourier series for $R$. On the other hand, since $f$ is absolutely integrable, we can switch integral with summation. Therefore we can apply the Poisson summation formula.

Its Fourier transform is, by Cauchy’s integral formula, $$\hat{f}(\omega) = \int_\mathbb{R}\frac{1}{x^2+c^2}e^{-2\pi i\omega x}dx = \frac{\pi}{c}e^{-2\pi c|\omega|}.$$ By the Poisson summation formula, we obtain $$\sum_{n\in\mathbb{Z}}\frac{1}{n^2+c^2} = \sum_{k\in\mathbb{Z}}\frac{\pi}{c}e^{-2\pi c|k|} = \frac{\pi}{c}\frac{e^{2\pi c}+1}{e^{2\pi c}-1},$$ and so $$\sum_{n=1}^\infty \frac{1}{n^2+c^2} = \frac{1}{2}\left(\frac{\pi}{c}\frac{e^{2\pi c}+1}{e^{2\pi c}-1}-\frac{1}{c^2}\right).$$

Sending $c$ to $0^+$, the left hand side converges to $\sum_{n=1}^\infty\frac{1}{n^2}$ and the right hand side is equal to

\begin{aligned} & \frac{1}{2}\left(\frac{\pi}{c}\frac{2+2\pi c+2\pi^2 c^2 + \ldots}{2\pi c + 2\pi^2 c^2 + 4\pi^3c^3/3 + \ldots}-\frac{1}{c^2}\right) \\ = & \frac{1}{2}\left(\frac{(2 + 2\pi c+2\pi^2c^2 + \ldots) - (2 + 2\pi c + 4\pi^2c^2/3 + \ldots)}{2c^2 + 2\pi c^3 + 4\pi^2c^4/3 + \ldots}\right) \\ = & \frac{1}{2} \frac{2\pi^2c^2 - 4\pi^2c^2/3 + \ldots}{2c^2 + \ldots} \end{aligned}

and converges to $\frac{\pi^2}{6}$ as $c\to 0^+$.

Categories

## A Note on Thue's Method

This note is based on my talk Introduction to Diophantine Approximation at Carnegie Mellon University on November 4, 2014. Due to limit of time, details of Thue’s method were not fully presented in the talk. The note is supposed to serve as a complement to that talk.

### Diophantine Approximation

Diophantine approximation deals with the approximation of real numbers by rational numbers. In other words, given a real number $\alpha$, we are interested in finding a rational approximation $p/q$ such that the error $|\alpha - p/q|$ is “small”. The smaller the error, the better the approximation. Since the set of rationals is dense, there is no best rational approximation of an irrational number (apparently, the best rational approximation of a rational number is itself). However, if we compare the error with the complexity of the rational, i.e., the denominator of the rational, it is natural to expect that the more complicated the rational approximation, the smaller the error. In particular, we can make sense of this in the following way.

Theorem (Dirichlet). Given an irrational $\alpha$, we have $|\alpha - p/q| < 1/q^2$ for infinitely many rationals $p/q$.

Proof. Think of $C = \mathbb{R}/\mathbb{Z}$ as a circle with circumference 1. Fix a natural number $N$ and mark $nq$ on $C$ for $n=1,\ldots,N$. By the pigeonhole principle, there are $1\leq n_1 \leq n_2\leq N$ such that $n_1\alpha$ and $n_2\alpha$ is $\leq 1/N$ apart from each other on $C$. Let $q = n_2 - n_1 < N$. Then there is $p$ such that $|q\alpha - p| \leq 1/N$, and so $|\alpha - p/q| \leq 1/(Nq) < 1/q^2$. Taking $N$ large enough yields better approximation $p/q$ with the desired property.

By means of continued fraction, one can push the result a bit further by a constant factor.

Theorem (Hurwitz 1891). Given an irrational $\alpha$, we have $|\alpha - p/q| < 1/\sqrt{5}q^2$ for infinitely many rationals $p/q$. Moreover, the constant $\sqrt{5}$ is the best possible for $\alpha = (1+\sqrt{5})/2$.

These show us how “well” we can approximate reals by rationals. On the other hand, we would also like to say that we cannot approximate “too well”, i.e., given a real number $\alpha$, we have $|\alpha - p/q| > 1/q^n$ for all but finite rationals $p/q$, where $n$ may depend on $\alpha$. Unfortunately, this is not so because of the existence of Liouville numbers.

Definition. A Liouville number is an irrational number $\alpha$ with the property that, for every natural number $n$, there exists a rational $p/q$ and such that $|\alpha - p/q| < q^{-n}$.

For example, $\alpha = \sum_{k=1}^\infty 2^{-k!}$ is a Liouville number.

However, we indeed can say something along those lines for algebraic numbers.

### Diophantine Approximation for Algebraic Numbers

Definition. An algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients (or equivalently integer coefficients). Given an algebraic number, there is a monic polynomial (with rational coefficients) of least degree that has the number as a root. This polynomial is called its minimal polynomial. If its minimal polynomial has degree $d$, then the algebraic number is said to be of degree $d$.

Theorem (Liouville 1844). Given an algebraic irrational number $\alpha$ of degree $d$, there exists $A>0$ such that for all rationals $p/q$, $|\alpha - p/q|>Aq^{-d}$.

A immediate consequence of the theorem is that Liouville numbers are not algebraic.

Proof. Let $f(x)$ be a polynomial with integer coefficients of degree $d$ that has $\alpha$ as a root. Note that $f'(\alpha)\neq 0$ otherwise $f'(x)$ is a polynomial of degree $ that has $\alpha$ as a root. As $f'(x)$ is continuous, there is $r>0$ such that $|f'(x)| < 1 / A$ for all $|x-\alpha|. Without loss of generality, we may assume $p/q$ is pretty close, i.e., within distance $r$, to $\alpha$ by taking $A < r$. Note that also $f(p/q)\neq 0$ otherwise $f(x) / (x-p/q)$ is a polynomial of degree $ that has $\alpha$ as a root. Since $q^df(p/q)$ is an integer, $|f(p/q)| \geq q^{-d}$. On the other hand, by mean value theorem, there is $c$ between $p/q$ and $\alpha$ such that $|f(\alpha)-f(p/q)| = |f'(c)||\alpha - p/q|$. Therefore $|\alpha - p/q| = |f(p/q)|/f'(c) > Aq^{-n}$ since $|c-\alpha| < r$.

Liouville’s theorem (on Diophantine approximation) can be phrased in an alternative way.

Corollary. Given an irrational algebraic number $\alpha$ of degree $d$. If the equation $|\alpha - p/q| < 1/q^n$ has infinitely many rational solutions $p/q$, then $n\leq d$.

The continuing working was established by Axel Thue (1909), Carl Ludwig Siegle (1921), Freeman Dyson (1947), and culminated at Klaus Roth’s result (1955):

Theorem (Roth 1955). Given an irrational algebraic number $\alpha$. If the equation $|\alpha-p/q|<1/q^n$ has infinitely many rational solutions $p/q$, then $n\leq 2$.

The constant $2$ cannot be improved due to Dirichlet’s theorem. Another way to interpret Roth’s theorem is as follows.

Corollary. Any irrational algebraic number $\alpha$ has approximation exponent equal to 2, i.e., for any $\epsilon>0$, the inequality $|\alpha-p/q|<1/q^{2+\epsilon}$ can only have finitely many solutions $p/q$.

This amounts to say that we cannot approximate irrational algebraic numbers “too well” in the sense that if we slightly restrict the error from $q^{-2}$ to $q^{-(2+\epsilon)}$, the number of “good” approximation changes from infinite to finite.

### Thue’s Method

Although Roth’s proof has merit in itself, part of his idea dates back to Thue’s work. Indeed, Thue used a method, now known as the polynomial method, in a special way to prove the following theorem.

Theorem (Thue 1909). Given an irrational algebraic number $\alpha$. If the equation $|\alpha-p/q|<1/q^n$ has infinitely many rational solutions $p/q$, then $n\leq d/2+1$, where $d$ is the degree of $\alpha$.

Proof. Suppose that the irrational algebraic number $\alpha$ has two “good” rational approximations $r_1 = p_1/q_1, r_2 = p_2/q_2$, i.e., $|\alpha - p_i/q_i| < q_i^{-n}$ for $i = 1,2$. Since there are infinitely many “good” rational approximations, we get to choose later how large we want $q_i$ to be.

The rest of the proof can be broken into three parts. Let $m\in\mathbb{N}$ and $0 < \epsilon \ll 1$ be two constants to be determined. The constant $\epsilon$ is fixed before we send it to $0$.

We are going to use $C_0, \ldots, C_6$ to indicate positive constants that may depend on $\epsilon, d$ and $c$, a constant determined by $\alpha$ (defined later). We may always assume $\alpha, d, c, C_0,\ldots, C_6 \ll m$.

Part I. Find a non-zero polynomial $f(x,y) = P(x) + Q(x)y$ with integer coefficients that satisfies the following properties:

1. it vanishes at $(\alpha, \alpha)$ to order $(m, 1)$, i.e., $\partial_x^k f(\alpha, \alpha) = 0$ for all $k;
2. its degree in $x$ is $\leq D := \frac{1}{2}(1+\epsilon)dm$.
3. its size, i.e., the maximum of all its coefficients’ absolute values, denoted by $|f|$, is $\leq C_1^m$ for some constant $C_1$.

Proof of Part I. The proof is a classical “parameter counting” argument. Consider a polynomial $f(x,y)=P(x)+Q(x)y = \sum_{i with degree $\leq D$ in $x$ and think of its $2D$ coefficients as undetermined. We can interpret the first property as a homogeneous system of $m$ linear equations with coefficients in $\mathbb{Z}[\alpha]$ because $$\frac{1}{k!}\partial_x^k f(\alpha, \alpha) = 0 \text{ if and only if } \sum_{i < D}{i\choose k}\alpha^{i-k}a_i + \sum_{i < D}{i\choose k}\alpha^{i-k+1}b_i = 0.$$

Fix a (non-zero) polynomial $c_dx^d + \ldots + c_0$ with integer coefficients that has $\alpha$ as a root and $c$ the size of this polynomial. Notice that $c_d\alpha^d = -(c_{d-1}\alpha^{d-1} + \ldots + c_0)$. For each of the linear equation above of the form $$L_0 + L_1\alpha + \ldots + L_t\alpha^t = 0,$$ for some $t \geq d$ where $L_k$ are linear combination of $a_i, b_i$ with integer coefficients, we can replace it by $$c_d(L_0 + L_1\alpha + \ldots + L_{t-1}\alpha^{t-1}) - L_t(c_0\alpha^{t-d} + \ldots + c_{d-1}\alpha^{t-1}) = 0,$$ i.e., $$L'_0 + L_1'\alpha + \ldots + L_{t-1}\alpha^{t-1} = 0$$ with $$L'_k = \begin{cases} c_dL_k & 0\leq k < t-d \\ c_dL_k - c_{k-t+d}L_t & t-d \leq k < t\end{cases}$$ and we can repeat this until its degree in $\alpha$ becomes smaller than $d$. Let $|L_k|_1$ be the sum of the absolute values of all coefficients in $L_k$. Note that each replacement increases the $\max |L_k|_1$ to $\max |L_k'|_1 \leq 2c \max|L_k|$. Note that the initially $\max |L_k| < 2^D$. After at most $D$ replacements, the equation satisfies $\max |L_k| < 2^D(2c)^D = C_0^m$ for some constant $C_0$.

Finally, for each of the linear equation, after the replacements, of the form $L_0 + L_1\alpha + \ldots + L_{d-1}\alpha^{d-1} = 0$, it is equivalent to have $L_0 = L_1 = \ldots = L_{d-1}$ because $1, \alpha, \ldots, \alpha^{d-1}$ are linearly independent over $\mathbb{Q}$. Therefore each linear equation with coefficient in $\mathbb{Z}[\alpha]$ corresponding to $\partial_x^k f(\alpha, \alpha) = 0$ is equivalent to $d$ linear equations whose $|\cdot|_1$ are all bounded by $C_0^m$. In total, we have $dm$ linear equations with $2D$ undetermined.

One can view this homogeneous system of linear equations as a linear transformation $L = (L_1, \ldots, L_{dm}): \mathbb{Z}^{2D} \to \mathbb{Z}^{dm}$. Consider all integral points in $[-M, M]^{2D}$ and their image under $L$. Because $|L_k|_1 \leq C_0^m$, their image is contained in $[-C_0^mM, C_0^mM]^{dm}$. By the pigeonhole principle, as long as $$(2M+1)^{2D} > (2C_0^mM+1)^{dm},$$ there are two integral points $v', v''$ in $[-M,M]^{2D}$ such that $Lv'=Lv''$, hence there is an integral point $v=v'-v''\in [-2M, 2M]^{2D}$ such that $Lv=0$ and $v\neq 0$, hence a non-zero solution to the linear system. To guarantee the above inequality involving $M$, it is enough to have $2M > C_0^{m/\epsilon}$, and so $2M = C_1^m$, for some constant $C_1$, works.

Part II. Find $l < L := \epsilon m$ such that $g(x,y) = \frac{1}{l!}\partial_x^l f(x,y)$ satisfies the following properties:

1. it vanishes at $(\alpha, \alpha)$ to order $(m-L, 1)$;
2. its degree in $x$ is $\leq D$ ($=\frac{1}{2}(1+\epsilon)dm$);
3. its size is $|g| \leq {D\choose l}C_1^m < C_2^m$ for some constant $C_2$;
4. and $g(r_1, r_2)\neq 0$.

Proof of Part II. The first three properties follow immediately from the properties of $f$. Henceforth, we only have to show there exists $l < L$ such that the last property holds. For the sake of contradiction, assume that $\partial_x^l f(r_1, r_2) = 0$ for all $l < L$. Define $$D(x) := \begin{vmatrix}P(x) & Q(x) \\ P'(x) & Q'(x)\end{vmatrix} = P(x)Q'(x) - P'(x)Q(x).$$ Because $f(x,y)$ vanishes at $(r_1, r_2)$ to order $(L,1)$, by Leibniz rule, $D(x)$ vanishes at $r_1$ to order $L-1$. Note that $D(x)$ is in $\mathbb{Z}[x]$. By Gauss’ lemma, $(q_1x-p_1)^{L-1}$ divides $D(x)$. Therefore either (1) $|D(x)| \geq q_1^{L-1}$; or (2) $D(x) = 0$ as a polynomial.

If it is the first case, because $|D(x)| = |P(x)Q'(x) - P'(x)Q(x)| < 2D|f|^2$, we have $2D|f|^2 > q_1^{L-1}$. Because $|f| < C_1^m$, we get a contradiction as long as $$q_1 > C_3,$$ for some constant $C_3$.

If it is the second case, $P(x)$ and $Q(x)$ are linearly dependent over $\mathbb{Q}$. Therefore either (1) $P(x) = -r_2'Q(x)$ and $Q(x)$ vanishes at $r_1$ to order $< L$ or (2) $Q(x)$ vanishes at $r_1$ to order $L$. If it is the first case, because $f(x,y) = (y-r_2')Q(x)$ vanishes at $(r_1, r_2)$ to order $(L, 1)$ and $Q(x)$ vanish at $r_1$ to order $, we know that $r_2' = r_2$, hence by Gauss’ lemma, $f(x,y)$ is a multiple of $q_2x - p_2$, and so $|f| \geq q_2$. If it is the second case, because $Q$ vanishes at $r_1$ to order $L$, by Gauss’ lemma, $Q(x)$ is a multiple of $(q_1x - p_1)^L$, and so $|f| \geq |Q| \geq q_1^L$. To get a contradiction in both cases, we need $$q_1 > C_4\text{ and }q_2 > C_1^m.$$
Therefore, it is enough to have $$q_1 > C_5\text{ and }q_2 > q_1^m$$ for some constant $C_5$.

Part III. We claim that $|g(r_1, r_2)| < C_6^m\left(q_1^{-(1-\epsilon)m}+q_2^{-1}\right)$.

Proof of Part III. We know that $$|g(r_1, r_2)-g(r_1, \alpha)| = |Q(r_1)||\alpha - r_2| \leq D|g|(|\alpha|+1)^D|\alpha-r_2|.$$ Because $g$ vanishes at $(\alpha_1, \alpha_1)$ to order $(m-L, 1)$, using Taylor expansion, we have
\begin{aligned}|g(r_1, \alpha) - g(\alpha, \alpha)| & \leq \sup_{|x| < |\alpha|+1}\frac{1}{(m-L)!}\partial_x^{m-L}g(x,\alpha) |\alpha_1-r_1|^{m-L} \\ & < D2^D|g|(|\alpha|+1)^D||\alpha_1-r_1|^{m-L}.\end{aligned}

As $r_1, r_2$ are two “good” approximations of $\alpha$, we obtain \begin{aligned}|g(r_1, r_2)| & \leq D|g|(|\alpha|+1)^D|\alpha-r_2| + D2^D|g|(|\alpha|+1)^D||\alpha_1-r_1|^{m-L} \\ & < C_6^m\left(q_2^{-n} + q_1^{(-m+L)n}\right),\end{aligned} for some constant $C_6$

From Part II, we know that $g(r_1, r_2)\neq 0$, and so $|g(r_1, r_2)| \geq q_1^{-D}q_2^{-1}$. From Part III, we know that $|g(r_1, r_2)| < C_6^m(q_1^{(-m+L)n}+q_2^{-n})$. Therefore, we obtain $$q_1^{-D}q_2^{-1} < C_6^m\left(q_1^{(-m+L)n}+q_2^{-n}\right).$$ Set $m$ to be the biggest integer less than $\log{q_2} / \log{q_1}$, and so $q_1^m < q_2 \leq q_1^{m+1}$. To ensure Part II to work, we only need to take $q_1 > C_5$. In addition, we require $q_1^\epsilon > C_6$ and so $C_6^m < q_1^{\epsilon m} < q_2^\epsilon$. The choice of $m$ implies that
$$q_2^{-\frac{1}{2}(1+\epsilon)d - 1} = q_2^{-D/m}q_2^{-1} < q_2^\epsilon\left(q_2^{-\frac{m-L}{m+1}n}+q_2^{-n}\right) < 2q_2^{-(1-2\epsilon)n+\epsilon}.$$
In order to have this inequality hold for arbitrarily large $q_2$, we need $\frac{1}{2}(1+\epsilon)d + 1 > (1-2\epsilon)n-\epsilon$. Let $\epsilon$ go to $0$ and obtain $n\leq \frac{1}{2}d + 1$.

### Acknowledgement

The proof largely relies on Larry Guth‘s notes on polynomial method.

Categories

## How I wrote my first independent paper

This is what happened behind the scene.

In the first draft, I was very pedantic. The resulted draft is notation-heavy and has no introductory section. It was then totally discarded. However, the structure of the proof was reused in the later drafts. My advisor suggested a useful dictionary by Trzeciak for mathematicians like me who write in English as a second language.

The second draft was finished after 3 months. This time, I started with the history of the problem. The entire process of tracking down the history is like this.

The picture is exaggerated. The reality is that for the first time I was handling 10+ references at the same time and that I had to figure out how and in what order I should introduce them in my article. The introductory took 1/3 of the time. Another 1/3 of the time, I was struggling how I could turn the notation-heavy proof in my first draft into English words and sentences which are more friendly to readers. The rest 1/3 of the time, I was drawing pictures and figures. I had never used Tikz (a standard LaTeX graphics package) before. After I learnt how to draw points, lines, how to fill in shape with color and how to put labels, I started my ambitious project to draw a 3D triangulation of a sphere. The result was a super slow Ruby script that outputs Tikz code, which was later complied to generate pictures.

The hope was to have the top notch graphics in my paper to compensate the weak mathematics result I got.

Advisor was pretty happy with the second draft and provided several suggestions. Takeaways:

• In LaTex, : is a binary operator. The correct unary operator is \colon. Use \smallskip, \midskip or \bigskip to manually adjust spacing.
• Citation information on MathSciNet is generally better than Google Scholar in terms of accuracy of information.
• Starting with the introduction section might be a better way to start a paper. By looking at others’ writings, one can familiarize himself/herself with the language and writing style of the field.

Advisor also drew me the following picture on my second draft.

The third draft was a revision of the second draft with two new figures. One of the major pictures is enhance by the Phong shading algorithm. A more refined fourth draft followed with more than 70 places of modifications.

The outcome of this creative process can be found on arXiv:1405.2503.

Categories

## Fun with Hex (Cont.)

In the previous post Fun with Hex, I asserted without proof that the Hex Game will never result a draw. In Jiri Matousek’s An Invitation to Discrete Mathematics, I found an elegant proof for the assertion, which requires only a little bit of elementary graph theory. The idea of the proof can also prove Sperner’s Lemma. Moreover, I will present later how to extrapolate this idea to discover something new. The only bit of elementary graph theory we are going to use is the Handshaking lemma.

Lemma (handshaking). Every finite undirected graph has an even number of vertices with odd degree.

To prove the lemma, simply observe that the sum of the degrees of all vertices is equal to twice the number of the edges, which should be even.

Now let us review the Hex Game. Recall two versions of the Hex Game.

The original version of the game is to color the hexagons of the game board (illustrated in black) and each player tries to link the opposite sides of the board with a connected series of hexagons with the same color.

Alternatively, one can play with the Voronoi dual of the hexagon game board (illustrated in red). This time, two players color the vertices and compete to link the opposite sides with a path of vertices of their own color. For instance, player one would try to form a red path from the northwest side to the southeast side, while player two would strive to build a blue one from the northeast side to the southwest side.

We can tilt and rescale the dual graph without changing the game as follows.

In this new graph, the first player wants to build a red path from the west to the east and the second player wants to build a blue path from the north to the south. Furthermore, for purpose of the proof, we add four auxiliary vertices on each side and color them according to which player it belongs to.

As are shown in the above graph, the vertices on the west and the east are red and the ones on the north and the south are blue. Our goal is to prove that no matter how you color the remaining vertices with red and blue, there is always a monochromatic path connecting two of the four auxiliary points. For the coloring below, there is a red path from W to E.

Proof.Assume, for the sake of contradiction, that some coloring does not form any red path from W to E or blue path from N to S. First, for every red vertex unreachable by any red path starting from W, we change it to green. Similarly, for every blue vertex unreachable by any blue path starting from N, we change it to green, too.

Under the assumption that there is no red path from W to E and no blue path from N to S, the vertices E and S are both changed to green. Now we have a triangulated planar graph whose four vertices on the external face, W, N, E, S are colored by red, blue, green, green respectively.

Lemma. Given a 3-coloring on a triangulated planar graph whose four vertices on the external face, say W, N, E, S, are colored by red, blue, green, green respectively. There is an internal triangular face whose vertices are of different color.

By this lemma, we can conclude that there exists an internal triangular face, say ABC, such that A is red, B blue and C green. This implies that there are a red path from W to A and a blue path from N to B. If the vertex C is originally red, then it should still be red because there is an edge between A and C. By the same reason, if it is originally blue, then it should still be blue. This gives a contradiction! To finish the proof for the Hex Game, we only need to prove the lemma.

Proof of Lemma. For each face of the triangulated planar graph, we put a vertex in it. Two vertices are adjacent if and only if their corresponding faces share a common edge whose endpoints are colored red and blue.

Note that the degree of the vertex in the external face is 1. By the handshaking lemma, there is a vertex, say $v$ in the internal face, say $F$, whose degree is odd. It is easy to see the only possible coloring of the vertices of $F$ to get an odd degree of $v$ is to color them by 3 different colors.

Now I am going to show something new. The idea to consider another game board which looks like:

The idea is to get a symmetric board. To build such a game board, one can start with a hexagon in the center and then add several layers of hexagons around it. In the picture above, the hexagon labeled by 1 is the one we start with. We call it the 1st layer. Then we can add 6 hexagons labeled by 2 around it to form the 2nd layer and another 12 hexagons labeled by 3 around the 2nd layer. In general, to build a symmetric Hex of size $n$, one only needs to repeat the process $n$ times.

For this symmetric Hex game board, we have three pairs of opposite sides. One reasonable goal, which is analogous to the goal of the Hex Game, is to build a monochromatic path that links two opposite sides. However two players can cooperate to tie the game in this case.

Therefore, for the symmetric Hex, the goal is to build a monochromatic connected component that touches two opposite sides or three nonadjacent sides. For simplicity, we can such a monochromatic connected component a winning component. In other words, if we label six sides by 1 through 6, both players want to use their own colors to connect side 1 and 4, or side 2 and 5, or side 3 and 6, or side 1, 3 and 5, or side 2, 4 and 6. Again, we will only consider its dual variant in the sense that each player colors the vertex of the following graph.

Proposition. The Symmetric Hex Game can never end in a tie.

Proof. Assume, for the sake of contradiction, that there is a 2-coloring of the symmetric Hex that contains no winning component. Consider the graph with 4 extra vertices W, E, N, S which connect to the vertices of the original graph as follows.

To be specific, W connects to all the vertices on side 5, E the vertices on side 2, N the vertices on side 1 and 6, S the vertices on side 3 and 4.

By the same argument we used in the proof of the Hex Game, there is either a red path from W to E or a blue path from N to S. In other words, we should have one of the following schematic pictures.

By our assumption, it must look like the pictures on the second row. Without loss of generality, assume that we have the first picture on the second row and the blue path connects vertices $a$ and $b$.

Now we change the way the extra 4 vertices connect to the vertices on the boundary as follows.

Again, there is either a blue path from W to E or a red path from N to S. If there is a blue path from W to E, then this path combined with the blue path from $a$ to $b$ gives us a connected component that touches two opposite sides or 3 nonadjacent sides. Therefore it has to be the case that a red path connects N to S.

To summarize, whenever we have a blue path $P_1$ that connects side 4 and 6, there is be a red path $P_2$ connecting the same sides on its right side. By symmetry, there is a blue path $P_3$ connecting side 4 and 6 on $P_2$‘s right side. We can keep going and get an infinite sequence of paths connecting side 4 and 6 with alternating colors, which is impossible!

Corollary. For any 2-coloring of the symmetric Hex board of size $n$, there is a monochromatic connected component of size at least $2n+1$.

Proof. By the symmetric Hex theorem, there is a monochromatic connected component that touches 2 opposite sides or 3 nonadjacent sides. In either case, the size of the component is at least $2n+1$.

Categories

## Communicating Information through Randomness

This week Staren sent me a puzzle on WeChat. After we discovered a solution for the puzzle, I tried to backtrack the source of it. I found it appeared in the blog post Yet another prisoner puzzle by Oliver Nash. The author seemed to work at a quantitative trading company SIG at that time. Given that Staren is working at JP Morgan, I guess this is one of many brain-teasers that was circulating among the traders around year 2010. Anyway, here is a version of the puzzle that was used in that blog post.

A room contains a normal 8 by 8 chessboard together with 64 identical coins, each with one “heads” side and one “tails” side. Two prisoners are at the mercy of a typically eccentric jailer who has decided to play a game with them for their freedom. The rules are the game are as follows.

The jailer will take one of the prisoners (let us call him the “first” prisoner) with him into the aforementioned room, leaving the second prisoner outside. Inside the room the jailer will place exactly one coin on each square of the chess board, choosing to show heads or tails as he sees fit (e.g. randomly). Having done this he will then choose one square of the chess board and declare to the first prisoner that this is the “magic” square. The first prisoner must then turn over exactly one of the coins and exit the room. After the first prisoner has left the room, the second prisoner is admitted. The jailer will ask him to identify the magic square. If he is able to do this, both prisoners will be granted their freedom.

These rules are explained to both prisoners before the game begins and they are allowed some time together to discuss their strategy. Of course the question is: what strategy should the prisoners adopt?

There is an extremely simple and clever solution that uses the XOR operation. However we will detour into the realm of linear algebra and information theory and come back to the elegant one-line solution at the end of the post.

In this puzzle, it doesn’t matter that we have a 8 by 8 chessboard to place the coins. All it matters is that we have $n=64$ places to put the coins in. Also it doesn’t matter that the jailer declare a magic square. All it matters is that he pick a magic number from $0, 1, \ldots, n-1$, which corresponds to the position of the magic square, and tell the first prisoner the number.

Henceforth, we can consider the following puzzle.

The jailer chooses an $n$-bit binary and pick a magic number from $1, 2, \ldots, n$. The first prisoner flips exactly at most one bit of the binary (not necessarily the magic bit) and shows the second prisoner the altered binary. What strategy should the prisoners adopt so that the second prisoner can tell the magic number?

I have changed the puzzle a little bit. In the original puzzle, the first prisoner must flip a bit. Now we allow him to do nothing if he wants to. We shall solve this weaker version of the puzzle first and come back to the original one.

If we think of the set of all the $n$-bit binaries as a metric space under the Hamming distance. I claim such strategy exists if and only if one can partition all the $n$-bit binaries into $n$ groups denoted as $A_1, \ldots, A_n$ such that for all $k$, the 1-neighborhood of $A_k$ covers all the $n$-bit binaries, i.e. any $n$-bit binary is at most 1-bit away from some binary in $A_k$.

The reason is as follows. Given such partition $A_1, \ldots, A_n$. If the jailer chooses the initial binary $x$ and the magic number $k$, because there is some binary, say $y$, in $A_k$ such that $x$ and $y$ are at most 1 bit off, the first prisoner can turn the initial binary into $y$ by flipping at most 1 bit in $x$. The second prisoner then can take this binary $y$, look up the partition $A_1, \ldots, A_n$ and find the index of the group which contains $y$. Conversely, one can argue it is necessary to have such a partition of all the binaries if one has the strategy.

For some reason we will see later, we call a subset $A$ of $n$-bit binaries a covering code provided its 1-neighborhood covers all $n$-bit binaries. In terms of covering codes, our goal is to find $n$ disjoint covering codes. By the way, in information theory, people call a subset of binaries a code.

Notice that if we can find $n+1$ disjoint covering codes, we can find a strategy that works even if we allow the jailer to pick the magic number from $1, 2, \ldots, n+1$. However we can not hope for more than $n+1$ disjoint covering codes. Here is why. Suppose we have $N$ disjoint covering codes. By pigeonhole principle, there is a covering code, say $A$, whose size is no more than $2^n/N$. Note that the 1-neighborhood of a binary contains exactly $n+1$ binaries. Hence the 1-neighborhood of $A$ contains at most $2^n\times\frac{n+1}{N}$. In order to have the 1-neighborhood of $A$ to cover all the binaries, we must have $N\leq n+1$. Moreover, if $N=n+1$, all codes should have the same size $2^n/(n+1)$.

Let us start with small $n$.

• For $n=1$, we can find 2 disjoint covering codes $A_1=\{0\}, A_2=\{1\}$.
• For $n=2$, we can find 2 disjoint covering codes $A_1=\{00, 11\}$, $A_2=\{01, 10\}$ or $A_1=\{00, 01\}$, $A_2=\{10, 11\}$.
• For $n=3$, we can find 4 disjoint covering codes $A_1=\{000,111\}$, $A_2=\{001,110\}$, $A_3=\{010,101\}$, $A_4=\{100, 011\}$.
• For $n=4$, we can take 4 disjoint covering codes by appending 0,1 to the covering codes for $n=3$. These covering codes are $A_1=\{*000,*111\}$, $A_2=\{*001,*110\}$, $A_3=\{*010,*101\}$, $A_4=\{*100, *011\}$, where $*$ is a wild card that can be either 0 or 1.
• For $n=5$, it is impossible to find 5 disjoint covering codes because by pigeonhole principle one of the 5 disjoint covering codes would contain no more than $2^5/5\sim 6$ binaries and the 1-neighborhood of any 6-element subset will always have 2 binaries not covered. This can be checked by a computer program.

It is interesting to see that for some $n$ we can find $n$ or $n+1$ disjoint covering codes and for some $n$, for instance 5, there are no $n$ disjoint covering codes. The situation is quite complicated here.

Therefore we had better focus on the extremal cases in which we can find $n+1$ disjoint covering codes. If it is the case that $n+1$ disjoint covering codes exist, all the covering codes should be of the same size $2^n/(n+1)$ and for each covering code $A$, the 1-neighborhoods of two distinct point in $A$ do not overlap. This implies that $n=2^m-1$ for some $m$. Since we are interested in the extremal case, henceforth we always assume $n=2^m-1$.

Even finding one covering code is hard besides that our goal is to find $n+1$ many of them. However, Richard Hamming in 1950 invented the first error correction code, the Hamming code $H$, which has the properties:

1. it is a linear code, i.e., $H$ is a $(n-m)$-dimensional linear subspace of $\mathbb{Z}_2^n$, the liner space of all the $n$-bit binaries over the finite field $\mathbb{Z}_2$;
2. the minimum Hamming distance between two distinct elements in $H$ is exactly three.

For an introduction to Hamming code, I recommend Thirty-three Miniatures by Jiri Matousek. The 5th miniature, Error-Correcting Codes, includes detailed construction of the Hamming code.

Because of the 1st property, $H$ has $2^{n-m}$ elements. The 2nd property says that the 1-neighborhoods of any two distinct elements in $H$ are disjoint since $1+1<3$. Hence the 1-neighborhood of $H$ contains $2^{n-m}(n+1)=2^{n-m}2^m=2^n$ many elements. In other words, the Hamming code is a linear covering code!

Good! We have found a linear covering code $H$. By translating the Hamming code $H$ by $\mathbf{e_1}=100\ldots 00$, $\mathbf{e_2}=010\ldots 00$, $\ldots$, $\mathbf{e_n}=000\ldots 01$ respectively, we have $n+1$ covering codes in total (including $H$ itself) since a translate of a covering code is still a covering code. Moreover, they are disjoint from each other because of the 2nd property of Hamming code.

Great! We have found $n+1=2^m$ disjoint covering codes for $n$-bit binaries. We can take this construction and use the wild card trick to get $n+1$ disjoint covering codes for $n+1$-bit binaries. In fact, for any $n+1$ disjoint covering codes for $n$-bit binaries, say $A_0, \ldots, A_n$, define $A_k^* = \{0,1\}\times A_k$. For each $k$, $A_k^*$ is a covering code for $n$-bit binaries, and what’s more, they are disjoint.

Hence the weaker version of the puzzle in which the first prisoner can opt to not flip the coin is totally settled since $8\times 8=2^6$. The same strategy works for the stronger version of the puzzle, because if unfortunately the initial binary is an element of $A_k^* = \{0,1\}\times A_k$ and the magic number is also $k$, the first prisoner can flip the leftmost bit so that the outcome stays in $A_k^*$.

Practically, in order to achieve such strategy, the first prisoner needs to memorize the Hamming code. However there is an easy way to get the Hamming code as it can be characterized as follows.
The Hamming code is the solution set of the linear system $R\mathbf{x}=\mathbf{0}$, where the matrix $R=[\mathbf{c_1}, \mathbf{c_2}, \ldots, \mathbf{c_n}]$ is an $m \times n$ matrix whose $k$th column $\mathbf{c_k}$ is the binary expansion of $k$ for $k=1,2,\ldots, n$.

For instance, when $m=3, n=2^m-1=7$, the matrix $$R=\begin{bmatrix}0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1\end{bmatrix}.$$

Similarly, we can characterize $\{0,1\}\times H$ as the solution set of $$\begin{bmatrix}\mathbf{0} & R\end{bmatrix}\mathbf{x}=\mathbf{0}.$$ We denote $R^*=[\mathbf{c_0}, \mathbf{c_1}, \ldots, \mathbf{c_n}]$ as the matrix $R$ prepended by a zero column.

Suppose $x_0x_1\ldots x_n$ is in $\{0,1\}\times H$. This means $$\sum_{x_k\neq 0}\mathbf{c_k}=\sum_{k=0}^nx_k\mathbf{c_k}=\mathbf{0},$$ where all summations take place in $\mathbb{Z}_2^n$. The left hand side of the equation above can be thought as the following procedure: we take all indices of the non-zero bit in the binary, $\{k: x_k\neq 0\}$, write out the binary expansions of them, $\{\mathbf{c_k}: x_k\neq 0\}$ and then add them up bitwise. Recall that adding binaries bitwise is equivalent to the XOR operation of numbers. The number corresponding to the left hand side is $\mathrm{XOR}_{x_k\neq 0}k$. We call this number the XOR-signature of the binary $x_0x_1\ldots x_n$. Therefore the XOR-signature $$\mathrm{XOR}_{x_k\neq 0}k=0$$ is another characterization of the set $\{0,1\}\times H$. Similarly, a binary $x_0x_1\ldots x_n$ is in $\{0,1\}\times (H+\mathbf{e_k})$ if and only if its XOR-signature is equal to $k$.

All right. Now we have a convenient way to tell which covering code a binary belongs to according to its XOR-signature. How will this help the first prisoner to figure out which coin to flip? Given the initial binary $x_0x_1\ldots x_n$, the first prisoner can compute its XOR-signature denoted by $s$. He wants to flip the $k$th bit of the binary so as to change its XOR-signature from $s$ to $s'$ which is the magic number that the jailer has picked from $0,1,\ldots, n(=2^m-1)$. Note that when he flips the $k$th bit of the binary, he will change the XOR-signature from $s$ to $s \mathrm{XOR} k$. So $k$ must satisfy $s \mathrm{XOR} k=s'$. One can solve this equation by XOR both sides by $s$ and get $k=s \mathrm{XOR} s \mathrm{XOR} k = s \mathrm{XOR} s'$.

In other words, the first prisoner only needs to compute the XOR-signature of the initial binary, say $s$ and flip the $(s\mathrm{XOR}s')$th bit of the binary, which will change the XOR-signature of the binary from $s$ to $s'$. Then the second prisoner comes in and compute the XOR-signature of the new binary which gives the magic number.

Pretty neat, isn’t it?

Categories

## Crazy Telescoping

In mathematics, a telescoping series is a series whose partial sums eventually only have a fixed number of terms after cancellation. I learnt this technique when I was doing maths olympiad. However until last year I learnt this buzz word ‘telescoping’ since I received my education in China and we call it ‘the method of differences’.

Anyway, yesterday, I was helping Po-Shen Loh to proctor this Annual Virginia Regional Mathematics Contest at CMU. Unfortunately, I did not take my breakfast. All I could digest are the seven problems. And even worse, I got stuck by the last problem which is the following.

Find $$\sum_{n=1}^\infty\frac{n}{(2^n+2^{-n})^2}+\frac{(-1)^nn}{(2^n-2^{-n})^2}.$$

It turns out that the punch line is, as you might have expected, telescoping. But it is just a bit crazy.

There is Pleasure sure, In being Mad, which none but Madmen know!

John Dryden’s “The Spanish Friar”

First consider the first term, $$\frac{1}{(2^1+2^{-1})^2}+\frac{-1}{(2^1-2^{-1})^2}=\frac{-2\times 2}{(2^2-2^{-2})^2}.$$ Then take look at the second term, $$\frac{2}{(2^2+2^{-2})^2}+\frac{2}{(2^2-2^{-2})^2}.$$ Aha, the sum of the first two terms becomes $$\frac{2}{(2^2+2^{-2})^2}+\frac{-2}{(2^2-2^{-2})^2}=\frac{-4\times 2}{(2^4-2^{-4})^2}$$ which again will interact nicely with the 4th term (not the 3rd term). After all, the sum of the 1st, 2nd, 4th, 8th, …, $n=(2^m)$th  terms is $$\frac{-4n}{(2^{2n}-2^{-2n})^2}.$$ Note that this goes to zero.

But this only handles the terms indexed by 2’s power. Naturally, the next thing to look at is the sum of the 3rd, 6th, 12th, 24th, …, $n=(3\times 2^m)$th terms, which amazingly turns out have the telescoping phenomena again and is equal to $$\frac{-4n}{(2^{2n}-2^{-2n})^2}.$$ Again, the this goes to zero.

We claim that starting with an odd index, say $(2l+1)$, the partial sum of the $(2l+1), 2(2l+1), \ldots, 2^m(2l+1), \ldots$‘th terms goes to zero.

For people who is willing to suffer a bit more for rigorousness, the argument for the previous claim can be easily formalized by the method of differences. The key fact we have been exploiting above is the following identity.

$$\frac{2n}{(2^{2n}+2^{-2n})^2}+\frac{2n}{(2^{2n}-2^{-2n})^2} = \frac{4n}{(2^{2n}-2^{-2n})^2}-\frac{8n}{(2^{4n}-2^{-4n})^2}.$$

The last bit of the ingredient is the absolute summability of the original sequence which implies that changing the order of summation does not affect the result. Hence the sum in total is $0$.

Categories

## On Hardy–Littlewood maximal function of singular measure

In this exposition, we explore the behavior of the Hardy–Littlewood maximal function of measures that are singular with respect to Lebesgue measure.

We are going to prove that for every positive Borel measure $s$ that is singular with respect to Lebesgue measure $m$,
$$m(\{x\in\mathbb{T}:M_s(x))>h\})>\frac{1}{2h}s(\mathbb{T}),$$ for all $h>s(\mathbb{T})$, where $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ is a torus and $M_s$ is the Hardy–Littilewood maximal function of the measure $s$ defined by
$$M_s(x)=\sup_{x\in B\subset\mathbb{T}}\frac{s(B)}{m(B)} \text{ for all }x\in\mathbb{T},$$ where the supreme is over all the balls containing the point $x$ in the torus.

Yue Pu told me this problem a couple of days ago. Though I don’t feel confident solving analysis problems, I wanted to see how much I have learnt from Giovanni Leoni. Finally, after staring at the problem for about 6 hours, Yue and I came up with an answer. The proof is modified from Yue’s write-up.

For experts among the readers, our first step is to exploit Calderón–Zygmund covering lemma. We will explain this in detail.

Since two measures $m$ and $s$ are mutually singular, there exist two disjoint sets $M$ and $S$ whose union is $\mathbb{T}$ such that $s(M)=m(S)=0$. In other words, $m$ lives in $M$ and $s$ lives in $S$.

Let $A$ be the set of all atoms of $s$, i.e., $A=\{x: s(x)>0\}\subset\mathbb{T}$. Define $E(x):=\{x+\frac{m}{2^n}: m,n\in\mathbb{N}\}\subset\mathbb{T}$ for all $x\in\mathbb{T}$, where the addition is under mod $1$. Note that $A$ and $E(x)$ are both countable, so there exists $e\in\mathbb{T}$ such that $A\cap E(e)=\emptyset$. Without loss of generality, we may assume $e=0$ because we may choose a suitable point on the torus as $0$. We abbreviate $E(0)$ by $E$ which is going to be the set of the endpoints of some intervals.

Fix $h>s(\mathbb{T})$. Now we are ready to apply the Calderón-Zygmund decomposition according to the height $h$.

We can chop the torus into two disjoint intervals $(0, 1/2)$ and $(1/2, 1)$ both of length $1/2$. Notice that at most one of them, denoted as $I_1$ if any, whose average, namely $s(I_1)/m(I_1)$, is greater than or equal to $h$. Since $s(\mathbb{T}), we get an upper bound for the average of $I_1$, $h\leq s(I_1)/m(I_1) ds < 2h$.

We can keep chopping those intervals whose average is less than $h$ into half and pick out sub-intervals whose average is no less than $h$. Inductively, we can generate an enumerable sequence of mutually disjoint open intervals $\{I_n\}$, each satisfying $h \leq s(I_n)/m(I_n) < 2h$, which implies $s(I_n)<2hm(I_n)$.

Let $I=\bigcup_n{I_n}$. We claim that $s(I)=s(\mathbb{T})$. If this is the case, then \begin{aligned}m(\{x\in\mathbb{T}:M_s(x)>h\}) & \geq\sum_nm(I_n)>\frac{1}{2h}\sum_ns(I_n) \\ & =\frac{1}{2h}s(I)=\frac{1}{2h}s(\mathbb{T}).\end{aligned}

Left to prove the claim. To prove $s(I)=s(\mathbb{T})$, we only need to show $s(S-I)=0$ as $s$ lives in $S$. Note that $s(E)=0$ since $A$, the set of the atoms of $s$, is disjoint from $E$ and $E$ is countable. It suffices to show $s(S-I-E)=0$.

Let $K$ be a compact set contained in $S-I-E$. Since for a positive Borel measure, one can always approximate a Borel set from inside by compact sets, it is enough to show $s(K)=0$.

For any $\epsilon>0$, as $m(S)=0$, we may choose an open set $U$ such that $S\subset U$ and $m(U)<\epsilon$. We want to show for all $x$ in $K\subset S-I-E$, we can always find two intervals $J_x$ and $J_x^+$ both containing $x$ such that $4m(J_x)=m(J_x^+)$, $s(J_x^+) and $3J_x\subset J_x^+\subset U$, where $3J$ denotes the open interval that has the same center as $J$ but three times the radius.

According to the decomposition process, we can find an infinite sequence of descending open intervals $\{J_n\}_{n=1}^\infty$ containing $x$ such that $J_{n+1}$ is the left or right half of $J_n$ and $s(J_n) for all $n$. This is possible because $x\notin I\cup E$. Note that $x$ cannot always lie in the left half of $J_n$ for all sufficiently large $n$ and similarly $x$ cannot always lies in the right half of $J_n$ for all sufficiently large $n$. In other words, for infinitely many times, $J_{n+2}$ is the right half of $J_{n+1}$ which is the left half of $J_{n}$.

Therefore we can always find sufficiently large $n$ such that $J_n\subset U$. Now for every $x\in K\subset U$, there exist $J_x$ which is $J_{n+2}$ above, and $J_x^+$ which is $J_n$ above such that $x\in J_x$, $3J_x\subset J_x^+\subset U$, $m(J_x^+)=4m(J_x)$, and $s(J_x^+). Hence $\{J_x\}_{x\in K}$ is an open cover of the compact set $K$. We can choose a finite sub-cover, pass it to Vitali covering lemma and spit out a sub-collection $\{J_{x_n}\}_{n=1}^N$ which are disjoint balls such that $K\subset\bigcup_{n=1}^N 3J_{x_n}$. Now we have

\begin{aligned}s(K) & \leq s\left(\bigcup_{n=1}^N 3J_{x_n}\right)\leq s\left(\bigcup_{n=1}^N J_{x_n}^+\right)\leq\sum_{n=1}^N s(J_{x_n}^+)

As $\epsilon>0$ is chosen arbitrarily, we have $s(K)=0$, which yields the claim.

Remark. The fact that $s(\mathbb{T})<\infty$ which is implicitly required in the problem is used to prove the countability of $A$, the set of all atoms of $s$.

Remark. I have no idea whether the result is sharp in terms of the constant multiplier on the right hand side of the inequality.

Categories

## Alternating Fourier Coefficients

Suppose $f\in L^2$ is a periodic function from $\mathbb{R}$ to $\mathbb{C}$ with period $1$. Let $a(n)$ be its Fourier coefficients, namely $a(n)=\int_0^1{f(x)e^{-i2\pi nx}dx}$ for all $n\in\mathbb{Z}$. Prove for all $p\geq 2$ it is almost surely that function $g(\omega)(x)=\sum_{n\in \mathbb{Z}}\omega(n)a(n)e^{i2\pi nx}$ is in $L^p$ where $\omega$ is an infinite sequence of independent and identical random variables indexed by $\mathbb{Z}$ with $\omega(n)$ equals either $-1$ or $1$ with probability $1/2$.

I heard this problem from Yue Pu who heard it from Gautam Iyer. Roughly speaking, given a periodic $L^2$ function, by alternating the signs of its Fourier coefficients, one almost surely gets an $L^p$ function for all $p\geq 2$.

Here is the proof Yue and I worked out this afternoon which I think is pretty neat. However, all convergence arguments are omitted.

We shall prove that for all $p\in\mathbb{N}$, the expectation of $\int_0^1 |g(\omega)(x)|^{2p}dx$ is less than or equal to $C_p\left(\int_0^1|f(x)|^2dx\right)^p$, where $C_p$ is a constant that only depends on $p$.

This is sufficient to prove the original problem. For all $p\in\mathbb{N}$, we let $A=\{\omega: g(\omega)\notin L^{2p}\}$. If $\mathbb{P}(A)>0$, then for all $\omega\in A$, $\int_0^1{|g(\omega)(x)|^{2p}dx}=\infty$. Consequently $$\infty\leq\mathbb{E}\left[\int_0^1 |g(\omega)(x)|^{2p}dx\right]\leq C_n\left(\int_0^1|f(x)|^2dx\right)^p<\infty,$$ which is impossible. For a general $p\geq 2$, pick any $p'\in\mathbb{N}$ such that $p\leq 2p'$. We know $g(\omega)$ is almost surely in $L^{2p'}$, hence almost surely in $L^{p}$.

For brevity, we denote $e(n)(x)=e^{i2\pi nx}$. We will repeatedly use the facts that $e(m)(x)e(n)(x)=e(m+n)(x)$, $\overline{e(m)(x)}=e(-m)(x)$ and $\int_0^1e(n)(x)=0$ except for $n=0$ it equals $1$. We will also use Parseval’s identity which says $\int_0^1|f(x)|^2dx=\sum_{n\in\mathbb{Z}}|a(n)|^2$.

For all $p\in\mathbb{N}$, we have \begin{aligned}|g(\omega)(x)|^2&=g(\omega)(x)\overline{g(\omega)(x)}\\&=\sum_{m,n}\omega(m)\omega(n)a(m)\overline{a(n)}e(m)(x)e(-n)(x).\end{aligned} This gives us $$|g(\omega)(x)|^{2p}=\sum_{m_1,\ldots,m_p,n_1,\ldots,n_p}\prod_{i=1}^p\omega(m_i)a(m_i)e(m_i)(x)\omega(n_i)\overline{a(n_i)}e(-n_i)(x).$$ Integrate above formula from $0$ to $1$, we have
$$\int_0^1{|g(\omega)(x)|^{2p}}dx=\sum_{m_1+\ldots+m_p=n_1+\ldots+n_p}\prod_{i=1}^p\omega(m_i)\omega(n_i)a(m_i)\overline{a(n_i)}.$$

Notice that for fixed $m_1, \ldots, m_p, n_1, \ldots, n_p$, the expectation of the summand is always $0$ except when there is a perfect matching among $m_1,\ldots, m_p, n_1, \ldots, n_p$. By a perfect matching, we mean that one can pair the numbers such that the two numbers in each pair are the same. Hence the expectation of above is equal to
$$\sum_{m_1+\ldots+m_p=n_1+\ldots+n_p}^*\prod_{i=1}^pa(m_i)\overline{a(n_i)},$$
where $\sum^*$ is the summation over every sequence that admits a perfect matching.

The above is less than or equal to
$$\sum_{m_1,\ldots, m_p, n_1,\ldots, n_p}^*\prod_{i=1}^p|a(m_i)||a(n_i)|.$$

By over counting, the expectation is less than or equal to
$$\frac{(2p)!}{p!2^p}\sum_{l_1, \ldots, l_p}\prod_{i=1}^p|a(l_i)|^2=\frac{(2p)!}{p!2^p}\left(\int_0^1|f(x)|^2dx\right)^p,$$
where $\frac{(2p)!}{p!2^p}$ is the number of perfect matching can possibly be formed among $2p$ numbers.

Remark. The proof is not constructive. Indeed, it doesn’t provide a way for one to alternate the Fourier coefficients so that the outcome is an $L^p$ function, though it is almost sure that the outcome is in $L^p$.

Categories

## Number of non-isomorphic graphs

This expository essay is to test my understanding of the techniques used in More Bricks – More Walls?, Thirty-three Miniatures by Jiří Matoušek’s.

We shall prove the sequence $g_n(0),\ldots, g_n({n\choose 2})$ is unimodal, i.e., it is first nondecreasing and then, from some point on, non-increasing, where $g_n(k)$ is the number of non-isomorphic graphs with $n$ vertices and $k$ edges. In particular, we shall prove $$\begin{gathered}g_n(0)\leq g_n(1)\leq\ldots\leq g_n(\lfloor m/2\rfloor) \\ =g_n(\lceil m/2\rceil)\geq\ldots\geq g_n(m-1)\geq g_n(m),\end{gathered}$$ where $m={n\choose 2}$.

Throughout the article, the number of vertices, which is denoted as $n$, is always fixed. And $m$ always stands for the maximal number of edges between $n$ vertices.

Notice that taking the complement of graphs establishes a bijection between graphs with $k$ edges and graphs with $m-k$ edges. Moreover, two graphs are isomorphic if and only if their complement graphs are isomorphic. Thus we have $g_n(k)=g_n(m-k)$. Hence it is enough to show that $g_n(k)\leq g_n(l)$ for all $k\leq l\leq m/2$.

Denote $U, V$ be the sets of all graphs with $k, l$ edges on the fixed vertex set $[n]$ respectively. Let $r, s$ denote the number of non-isomorphic graphs in $U, V$. By our notation above, $r=g_n(k), s=g_n(l)$. We shall show $r\leq s$. The graph $G$ is the bipartite graph between $U$ and $V$ with $u\sim v$ if and only if $u$ is a subgraph of $v$.

Let $B=(b_{uv})_{u\in U, v\in V}$ be the bipartite adjacent matrix of $G$, where $b_{uv}=1$ if $u$ and $v$ are adjacent in $G$, otherwise $0$.

We claim the matrix $B$ is of full rank. As it is easy to see the size of $U$ is no greater than the size of $V$, we shall prove an equivalent statement that the matrix $B$ is of full row rank, that is the rows of $B$ are linearly independent.

Suppose not. There is a non-zero row vector $y$ in $\mathbb{R}^{U}$ such that $yB=0$. Notice the coordinates of $y$ are indexed by the elements in $U$. Let $K^*\in U$ such that $y_{K^*}\neq 0$.

Now we partition $U, V$ into $k+1$ according to the number of edges in the intersection of the graph with $K^*$: $K_i$ is the set of graphs in $U$ who share $i$ common edges with $K^*$ and $L_j$ is the set of graphs in $V$ who share $j$ common edges with $K^*$ for all $i, j=0,\ldots, k$. Remember the number of edges in $K^*$ is $k$ and $K_k$ contains only one element $K^*$. Also all $K_i$ and $L_j$ defined above are non-empty because of the assumption $k.

Note that for any $i, j\in \{0,\ldots, k\}$, all vertices in $K_i$ have the same degree to $L_j$ in the bipartite graph $G$. This is because the ways to extend a graph with $k$ edges and $i$ edges in common with $K^*$ to graphs with $l$ edges and $j$ edges in common with  doesn’t specifically depend the graph we start with. Denote this number as $d_{ij}$ and let $D=(d_{ij})$ be the matrix. Apparently, $D$ is an upper triangular matrix with $d_{ii}\neq 0$. Thus $D$ is non-singular. On the other hand, as $k_i\cdot d_{ij}=\sum_{K\in K_i, L\in L_j}B_{KL}$ where $k_i$ is the size of $K_i$, $D=\mathrm{diag}(k_0^{-1},\ldots, k_k^{-1})FBG$ where $F=(f_{i, u})_{i\in\{0,\ldots, k\}, u\in U}$ and $G=(g_{v, j})_{v\in V, j\in\{0,\ldots, k\}}$ are matrices with $f_{i, u}=1$ if and only if $u\in K_i$ and $g_{v, j}=1$ if and only if $v\in L_j$ otherwise $0$.

Let $x$ be a $k+1$ dimensional row vector such that $x=yE$, where $E=(e_{ui})_{u\in U, i\in\{0,\ldots, k\}}$ is matrix with $e_{ui}=1$ if $u\in K_i$ otherwise $0$. In fact, $x_i=\sum_{u\in U}y_ue_{ui}=\sum_{K\in K_i}y_K$. Hence $x_k=y_{K^*}\neq 0$ as $K_k$ contains only one element $K^*$.

Now we have $xD=yE\mathrm{diag}(k_0^{-1},\ldots, k_k^{-1})FBG$. However it is easy to check $EF=\mathrm{diag}(k_0,\ldots, k_k)$ and $yB=0$. So $xD=yBG=0$ contradicting to the non-singularity of $D$ as $x\neq 0$. According to the graph isomorphism the graphs in $U, V$ are classified into equivalent classes, denoted as $U_1,\ldots, U_r, V_1, \ldots, V_s$.

Similarly, we observe that all vertices in $V_j$ have the same degree to $U_i$ since the number of ways to restrict two isomorphic graphs to a certain class of isomorphic graphs is the same. Denote this degree as $d_{ij}$ as well. And again we claim the matrix $D$(different from the one we define before) is of full row rank where $D=(d_{ij})_{r\times s}$. This will finish the proof since an $r\times s$ matrix of full row rank implies $r\leq s$.

Suppose not. We have a non-zero $r$ dimensional row vector $y$ such that $yD=0$. Let $x\in\mathbb{R}^U$ be the row vector indexed by $U$ such that $x_u=y_i$ for all $u\in U_i$. Thus for all $u\in V_j$ we have \begin{aligned}(xB)_v &=\sum_{u\in U}x_uB_{uv}=\sum_{i\in[r]}\sum_{u\in U_i}x_uB_{uv} \\ &=\sum_{i\in[r]}y_i\sum_{u\in U_i}B_{uv}=\sum_{i\in[r]}y_id_{ij}=(yD)_j=0.\end{aligned} Notice $x\neq 0$ but $xB=0$ which contradicts with the non-sigularity of $B$.

Remark. This proof appears to me as an intricate idea similar to finding an injection. To prove one set is smaller than the other, one would just hope to find an injection from one set to the other. But this is hard in this problem because those two sets we are considering are sets of equivalent classes. On the other hand, in this problem, the inclusion mapping works just fine on the level of graphs though it breaks down on the level of equivalent classes. Thus we should come up with a delicate analysis on the bipartite graph induced by the inclusion mapping. And I think this is the motivation behind the proof.

Categories

## Fun with Hex

According to the folklore,

The Hex game was invented by the Danish mathematician Piet Hein, who introduced it in 1942 at the Niels Bohr Institute. It was independently re-invented in 1947 by the mathematician John Nash at Princeton University. The rules are really simple. Each player has an allocated color, Red and Blue being conventional. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal is to form a connected path of your stones linking the opposing sides of the board marked by your colors, before your opponent connects his or her sides in a similar fashion. The first player to complete his or her connection wins the game. The four corner hexagons each belong to both adjacent sides… The game can never end in a tie, a fact proved by John Nash: the only way to prevent your opponent from forming a connecting path is to form a path yourself. In other words, Hex is a determined game.
– Hex (board game), Wikipedia

For instance, in the following 2 by 2 board, player 1 should intend to build a connected path linking $x_1=0, x_1=2$, while player 2 should intend to build a connected path linking $x_2=0, x_2=2$.

Now, we would like to play Hex game in higher dimensions. The first question is: how can we set up the game board in the $n$ dimensional space? The answer all depends on your point of view. If we visualize the game board in 2 dimension as follows, we can view each cell as a cube in 3 dimensional space.

Here is a rework of the 2 dimensional board which can be easily generalized to higher dimension. Consider all unit cubes in $\mathbb{R}^3$ who are translation of the canonical unit cube (whose vertices are $(0,0,0), (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1),(1,1,1)$) along the vector $(x,y,z)$, where $(x,y,z)\in[n]\times[n]\times\mathbb{Z}$ ($[n]=\{1,2,\ldots, n\}$) and $x+y+z=0$. Basically, those unit cubes are the ones illustrated above. Now project all those cubes to the 2-dimensional plane $x+y+z=0$. This gives us the hexagon board.

For higher dimension, say $d$ dimension, just project all unit cubes in $\mathbb{R}^{d+1}$ who are translation of the $d+1$-dimensional canonical unit cube along the vector $(x_0, \ldots, x_n)$, where where $(x_0,\ldots, x_d)\in\mathbb{Z}^{d+1}$ and $x_0+\ldots+x_d=0$, to the $d$-dimensional hyperplane given by the equation $x_0+\ldots+x_d=0$.
With the help of Mathematica, each cell of 3D Hex board looks like the following.

Source code is attached here for those who want to play with it a little bit in Mathematica.

v = Orthogonalize[{{1, -1, 0, 0}, {0, 1, -1, 0}, {0, 0, 1, -1}}];
data = Flatten[Table[{{x, y, z, t}.v[[1]], {x, y, z, t}.v[[2]], {x, y, z, t}.v[[3]]}, {x, 0, 1}, {y, 0, 1}, {z, 0, 1}, {t, 0, 1}], 3];
`
I forgot to mention, in the $d$-dimensional Hex game, we have at most $d$ players. Again, the game will never tie. For those who are interested beyond this mere fact, please refer to David Gale’s great exposition on this topic [DG] ((David Gale, The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly, vol. 86, 1979, pp. 818-827)).
Indeed, mathematically speaking, this is the dual diagram of the original board. Its generalization in higher dimension is easy to imagine. Define a graph whose vertex set $V=[n]^d$. Two distinct vertices $u, v\in V$ are adjacent if $u_i-v_i\in\{0,1\}$ for all $i\in[d]$ or the other way around $v_i-u_i\in\{0,1\}$ for all $i\in[d]$.