Dissociated sets avoiding geometric progressions

In a recent preprint, I dealt with sets with distinct subset sums. A set $\mathcal S\subset \mathbb N$ is said to be a subset-sum-distinct or dissociated (when studied in other contexts) if all of its finite subsets have different sums. Alternately, an equivalent classification is if any equality of the form

$$\sum_{s\in \mathcal S} \varepsilon_s \cdot s =0$$

where $\varepsilon_s \in \{-1,0,+1\}$ implies that all the $\varepsilon_s$'s are $0$.

Some two and a half years ago, I was playing around with the greedy algorithm on these sets, and noticed something strange. This starts with two given integers $a>0$ and $b>a$. It sets $\gamma_1=a$, $\gamma_2=b$ and in the $r$-th step it chooses $\gamma_r$ to be the smallest integer greater than $\gamma_{r-1}$ such that the sequence $\{\gamma_k\}_{k=1}^r$ is dissociated. For any given $a,b$, let $\Gamma:=\Gamma_{a,b}=\{\gamma_1=a, \gamma_2=b, \gamma_3, \dots \}$ be the dissociated sequence that the greedy algorithm produces. From purely numerical experiments, I noticed that there is always an $n_0=n_0(a,b)$ such that

$$\gamma_n = 2\cdot \gamma_{n-1}$$

for all $n\ge n_0$. I had to wait all this time to finally be able to prove this. One can see the proof in the preprint.

From this result (and some other observations I made in and outside the preprint), I thought that a large dissociated set must contain a lot of geometric progressions. In the preprint, I answered this in the negative by constructing a large collection of dissociated sets which also do not contain any three $a,b,c$ with $b^2=ac$. In this post, I will give an explicit nice construction of such a set.

First of all, note that for a dissociated set $\mathcal S$, we have

$$\left\vert\mathcal S(n)\right\vert \le \log_2 n + \mathcal{O}( \log_2\log_2 n)$$

where $\mathcal S(n) := \mathcal S \cap [1,n]$. This is because the map $f : \mathcal P\left(\mathcal S(n)\right) \to \mathbb N$ that takes a subset of $\mathcal S(n)$ to the sum of its elements is injective, hence giving $2^{\left\vert\mathcal S(n)\right\vert} \leq n\cdot \left\vert\mathcal S(n)\right\vert +1$, hence completing the proof.

So, we will now construct a dissociated set of size $\sim \log_2 n$ that does not contain any GP.

Theorem : The sequence $\{\psi_n\}_{n=1}^\infty$ defined as

$$\psi_n = \frac{2^{n+2}}{7} + \frac{1}{7\sqrt 3}\cdot\sin \left(\frac{2\pi n}{3}\right) + \frac 37 \cdot \cos \left(\frac{2\pi n}{3}\right)$$

is dissociated and does not contain any three term geometric progression.

The proof of this follows from a series of simple and straightforward observations that we will list as Lemmas. We should of course begin with the obvious

Lemma 1 : The values of $\{\psi_n\}_{n=1}^\infty$ are given by

\begin{align*}&\psi_{3k} = \frac{4\cdot 8^k}{7} + \frac 37\\&\psi_{3k+1} = \frac{8^{k+1}}{7} - \frac 17\\&\psi_{3k+2} = \frac{2\cdot 8^{k+1}}{7} - \frac 27\end{align*}

for all $k$. So, $\psi_n$ is a positive integer, and can be expressed as

$$\psi_n = \left\lVert \frac{2^{n+2}}{7} \right\rVert$$

where $\lVert \cdot \rVert$ represents rounding to the nearest integer.

Proof : The expressions for $\psi_{3k+i}$, $i=0,1,2$ are a matter of straightforward computation. The fact that they are all integers follows from the simple observation that

$$8^k = \left(7+1\right)^k \equiv 1 \pmod 7$$

for all $k$. $\square$

Lemma 2 : The sequence $\{\psi_n\}_{n=1}^\infty$ is strictly increasing. In fact, we have

\begin{align*}&\psi_{3k} = 2\cdot \psi_{3k-1} + 1\\&\psi_{3k+1} = 2\cdot \psi_{3k} - 1\\&\psi_{3k+2} = 2\cdot \psi_{3k+1}\end{align*}

for all $k\in \mathbb N$. So,

$$\psi_n = \psi_{n-1}+\psi_{n-2}+2\cdot \psi_{n-3}$$

which admits

$$\frac 1{1 - x - x^2 - 2x^3} = \frac 1 {(1-2x)(1+x+x^2)}$$

as the generating function.

Proof : The expressions for $\psi_{3k+i}$, $i=0,1,2$ follow immediately from Lemma 1. This, used in an Induction argument, proves the recursion. The generating function is a simple consequence of it. $\square$

Lemma 3 : The sequence admits a nice modularity property. In particular

\begin{align*}&\psi_{3k} \equiv 5 \pmod 8\\&\psi_{3k+1} \equiv 1 \pmod 8\\&\psi_{3k+2} \equiv 2 \pmod 8\end{align*}

for all $k\in \mathbb N$.

Proof : We begin by calculating that $\psi_1=1$, $\psi_2=2$ and $\psi_3=5$. The rest of the proof is immediate from Lemma 2. $\square$

Lemma 4 : We have

$$\sum_{i=1}^m \psi_i < \psi_{m+1}$$

for all $m\in \mathbb N$, $m\ge 2$.

Proof :  Notice that the lemma is trivial to check for $m=2,3,4$.

Now, let us assume

$$\sum_{i=1}^k \psi_i < \psi_{k+1}$$

for some $k$. This gives

$$\sum_{i=1}^{k+1} \psi_i < 2\cdot\psi_{k+1}$$

and hence

$$\sum_{i=1}^{k+3} \psi_i < \psi_{k+4}$$

using the recursion discussed in Lemma 2.

So, an induction argument completes the proof. $\square$

Equipped with these lemmas, it is now possible to give a proof of the Theorem.

Proof : We will first show that the set is dissociated. To do so, let us assume that it's not. If possible, let there be indexing sets $\{i_k\}_{k=1}^n$ and $\{j_k\}_{k=1}^m$ such that

$$\psi_{i_1}+\dots \psi_{i_n} = \psi_{j_1}+\dots \psi_{j_m}$$

where all the $\psi_i$'s are distinct.

Without loss of generality, let $\psi_{i_1}$ be the largest of these $\psi_k$'s. By Lemma 4, this implies

$$\psi_{i_1} > \psi_{j_1}+\dots \psi_{j_m}$$

and hence

$$\psi_{i_1}+\dots \psi_{i_n} > \psi_{j_1}+\dots \psi_{j_m}$$

which is a contradiction.

Now, we wish to show that there are no three term geometric progressions in the sequence. On the contrary, let us assume

$$\psi_i^2 = \psi_j\cdot \psi_k$$

for some $\psi_i$, $\psi_j$, $\psi_k$ in our sequence. We begin by noticing that Lemma 3 implies that either

$$i,j,k \equiv 0,1,1 \pmod 3$$

or $i\equiv j\equiv k\pmod 3$.

For the first case, let us assume that there are integers $j,k,\ell\ge 2$ (the other cases can be checked by hand) such that

$$\psi_{3k}^2 = \psi_{3j+1} \cdot \psi_{3\ell +1}$$

which implies

$$\left(4\cdot 8^k + 3\right)^2 = \left(8^j-1\right)\cdot \left(8^\ell-1\right)$$

by Lemma 1. This is a contradiction since the LHS and the RHS are $9$ and $1$ modulo $64$ respectively.

Now, let us consider the case $i\equiv j\equiv k \equiv 0\pmod 3$. Again as before, we assume

$$\psi_{3k}^2 = \psi_{3j} \cdot \psi_{3\ell}$$

where without loss of generality, it may be assumed that $\ell<k<j$. By Lemma 1, we have

$$8^{2k+1}-8^{\ell+j+1} = 12\cdot \left(8^j + 8^\ell -8^k\right)$$

and hence

$$8^{2k+1-\ell} - 8^{j+1} = 12\times \left(8^{j-\ell} - 8^{k-\ell} + 1\right)$$

which is a contradiction since the LHS and RHS do not match modulo $8$.

The cases $i\equiv j\equiv k \equiv 1\pmod 3$ or $i\equiv j\equiv k \equiv 2\pmod 3$ are to be dealt similarly as the previous case. $\square$

Some Expressions of $\pi$

The idea is to derive some expressions for describing $\pi$ starting from the basic definition. The steps will be outlined and the reader will need to fill most of the details up. Of course, convergence questions will be ignored since checking them is routine. Take this as a late pi-day post if you wish to.

Start with the circle described by

$$\left(x=\frac{1-t^2}{1+t^2}, y=\frac{2t}{1+t^2}\right)$$

to get

$$\frac{\pi}{4} = \int_0^1\frac{dt}{1+t^2} = \frac12\int_0^1\frac{s^{-1/2}}{1+s}\,ds$$

using elementary calculus.

Now define

$$G(z)\;:=\;\frac12\int_0^1\frac{s^{-1/2}}{1+z s}\,ds =\frac12\sum_{n\ge0}(-z)^n\int_0^1 s^{n-1/2}\,ds =\sum_{n\ge0}\frac{(-z)^n}{2n+1}$$

and note that using $z=1$ gives

$$\boxed{\frac{\pi}4=\sum_{n\ge0}\frac{(-1)^n}{2n+1}}$$

which is the famous Madhava-Gregory-Leibnitz-(enter your favourite mathematician) series for $\pi$. Squaring both sides of this "carefully", one gets

$$\boxed{\frac{\pi^2}{6}=\sum_{n\ge 1} \frac 1{n^2}}$$

which is a famous result of Euler. This "careful squaring" is an exercise in Borwein & Borwein’s Pi and the AGM (Wiley, 1987).

Now, consider the character $\chi$ mod $4$ and define

$$F(s) := \frac{1}{1 - 2^{-s}} \cdot \prod_{p\in \mathcal P} \frac{1}{1 + \frac{\chi(p)}{p^s}}$$

where $\mathcal P$ is the set of odd primes.

A little algebra shows

$$F(s) = \frac{\zeta(2s)(1 + 2^{-s})}{L(s, \chi)}$$

where

$$\zeta(s) := \sum_{n\ge 1} \frac{1}{n^s}, \qquad L(s, \chi) := \sum_{n\ge 1} \frac{\chi(n)}{n^s} = \prod_{p} \frac{1}{1 - \frac{\chi(p)}{p^s}}$$

for our chosen character.

Taking $s\to 1^+$ proves

$$\boxed{\pi = \sum_{m=1}^{\infty}\frac{(-1)^{s(m)}}{m}}$$

where $s(m)$ counts the number of appearances of primes of the form $4k+1$ in the prime decomposition of $m$.

We return back to $G$ and note that $G$ can also be expressed as the Stieltjes integral

$$G(z)=\int_0^1\frac{d\mu(s)}{1+zs}$$

for the positive measure $\mu$ on $[0,1]$ with density $d\mu(s)=\tfrac12 s^{-1/2}ds$. Now, show that any function of this type admits an expression of the form

$$G(z)=\cfrac{1}{\,1+\cfrac{\beta_1 z}{3+\cfrac{\beta_2 z}{5+\cfrac{\beta_3 z}{7+\ddots}}}\,}$$

by looking at the Taylor series and uniquely determining the finite continued fraction convergents successively so that the $k$-th convergent matches the Taylor series up to $z^k$.

The crucial part is to show $\beta_n = n^2$. If we can prove this, then we get

$$\boxed{\frac{\pi}{4} = \cfrac{1}{\,1+\cfrac{1^2}{3+\cfrac{2^2}{5+\cfrac{3^2}{7+\ddots}}}\,}}$$

from which one also gets

$$\boxed{\frac{\pi}{4}=1+ \cfrac{1}{3- \cfrac{3\cdot 4}{1- \cfrac{2 \cdot 3}{3- \cfrac{5 \cdot 6}{1-\cfrac{4 \cdot 5}{\ddots}}}}}}$$

after some simple algebra.

Indeed, start with the first form and write

$$\begin{align*}\frac 4{\pi} -1 &= \frac{1}{3+\dfrac{4}{5+\dfrac{9}{7+\cdots}}} = \frac{1}{3+\dfrac{4}{\,\dfrac{\left(5+\dfrac{9}{7+\cdots}\right)}{1}\,}} = \frac{1}{\,3+\dfrac{4}{\dfrac{5+\dfrac{9}{7+\cdots}}{1}\,}}\\&= \frac{1}{\,3+\dfrac{4}{5+\dfrac{9}{7+\cdots}}\,} = \frac{1}{\,3-\dfrac{12}{\,1-\dfrac{6}{3-\dfrac{20}{1-\cdots}}\,}\,}\end{align*}$$

and continue in this manner at each step to get the second form.

Finally, to show $\beta_n=n^2$, we define

$$m_k=\int_0^1 s^k\frac{1}{2}s^{-1/2}ds=\int_0^1 u^{2k}\,du=\frac{1}{2k+1}$$

and let

$$\Delta_n=\det\bigl(m_{i+j}\bigr)_{0\le i,j\le n}$$

with the convention $\Delta_{-1}:=1$ and $\Delta_0=m_0$. By writing the orthogonality linear systems for the polynomial coefficients and solving them by Cramer’s rule, one gets

$$\beta_n=\frac{\Delta_n\Delta_{n-2}}{\Delta_{n-1}^2}$$

for $n\ge 1$. On the other hand, it is also possible to show (using Induction or otherwise) that

$$\Delta_n =\frac{2^{\,n(n+1)}\left(\prod_{m=1}^n m!\right)^{2}}{\prod_{k=0}^{2n}(2k+1)^{\min(k+1,2n-k+1)}}$$

for $n\ge 1$. Plugging this into the equation of $\beta_n$ now completes the proof.

A special case of Problem #355

In the online database of Erdős Problems, the following is listed as problem #355. A sequence of natural numbers $A\subset \mathbb N$ is called a lacunary sequence if $a_1<a_2<\dots$ and there is a $\lambda_A>1$ so that

$$\frac{a_{n+1}}{a_n} \ge \lambda_A$$

for all $n\ge 1$. Consider the set

$$\mathcal S_A := \left\{ \sum_{a\in A'}\frac{1}{a} : A'\subseteq A\textrm{ finite}\right\}$$

for such a sequence. The question is whether there exists a lacunary sequence $A$ for which $\mathcal S_A$ contains all rationals in some open interval.

While this question is quite a difficult one to answer, a special case is pretty elementary. I recently came to know that the results discussed in this post are pretty well known and are often attributed to Kakeya from more than a hundred years ago. I would like to thank Prof. Vjekoslav Kovač for this information.

Theorem 1 : Let $A = \{a_1 < a_2 < \cdots\} \subset \mathbb{N}$ be a lacunary sequence with $\lambda:=\lambda_A>2$. Then $\mathcal S_A$ does not contain all rationals in an open interval.

Proof : Set $u_n:=1/a_n$ and $r=1/\lambda<1/2$. By lacunarity, there is a constant $C=u_1/r$ such that

$$u_n\le Cr^n$$

for all $n\ge 1$. Note that every $s\in \mathcal S_A$ is of the form

$$s=\sum_{n\ge 1} \varepsilon_n u_n$$

for $\varepsilon_n\in \{0,1\}$ and $\varepsilon_n\ne 0$ for finitely many $n$.

    

Now, fix an $N\in \mathbb N$ and for each $\mathbf \varepsilon = (\varepsilon_1,\varepsilon_2,\dots , \varepsilon_N) \in \{0,1\}^N$, define

$$s_{\mathbf{\varepsilon}} := \sum_{n=1}^N \varepsilon_n u_n, \qquad R_N := \sum_{n>N} u_n$$

to be the first $N$ digits and the tail after that. But for each sequence $\{\varepsilon_n\}_{n\ge 1}$, we have

$$\sum_{n\ge 1} \varepsilon_n u_n \in \left[s_{\mathbf\varepsilon}, s_{\mathbf{\varepsilon}}+R_N\right]$$

for all $N\in \mathbb N$. So, define

$$\mathcal U_N := \bigcup_{\mathbf{\varepsilon}\in \{0,1\}^N} \left[s_{\mathbf\varepsilon}, s_{\mathbf{\varepsilon}}+R_N\right]$$

and note that $\mathcal S_A\subset \mathcal U_N$.

Now, $\mathcal U_N$ being a finite union of closed sets is closed. Also, it is clear that

$$\overline{\mathcal S_A}\subset \bigcap_{n\ge 1} \mathcal U_N$$

where $\overline{\mathcal S_A}$ is the closure of $\mathcal S_A$.

But by definition, we have

$$R_N \le \sum_{n\le N} Cr^n \le C' r^N$$

for a suitable constant $C'$. Now, $\mathcal U_N$ is the union of at most $2^N$ intervals. This implies

$$\left\lvert \mathcal U_N\right\rvert \le 2^N R_N \le C' (2r)^N \xrightarrow{N\to \infty} 0$$

since $\lambda>2$. This means that the Lebesgue measure

$$\mu\left(\bigcap_{n\ge 1} \mathcal U_N\right) = 0$$

and hence

$$\mu\left(\overline{\mathcal S_A}\right) = 0$$

implying $\overline{\mathcal S_A}$ has empty interior.

So, if there was an open interval $I$ such that $I\cap \mathbb Q \subset \mathcal S_A$, then this would imply

$$I = \overline{I\cap \mathbb Q} \subset \overline{\mathcal S_A}$$

which is a contradiction.

In fact, we can prove a stronger statement.

Theorem 2 : For a lacunary sequence $A$, we have

$$\dim_H\left(\overline{\mathcal S_A}\right) \le \frac{\log 2}{\log \lambda}$$

where $\dim_H(X)$ is the Hausdorff dimension of a set $X$.

Proof : With notations as in the previous proof, the $s$ dimensional Hausdorff content at scale $R_N$ satisfies

$$\mathcal H^s_{R_N} \left(\overline{\mathcal S_A}\right) \le 2^N (2R_N)^s$$

for $s>\frac{\log 2}{\log \lambda}$.

Using the bound for $R_N$, we have

$$\mathcal H^s_{R_N} \left(\overline{\mathcal S_A}\right) \le \left(\frac{2C r^{\,}}{1-r}\right)^s\cdot \left(2 r^s\right)^N$$

and hence

$$\lim_{N\to \infty} \mathcal H^s_{R_N} \left(\overline{\mathcal S_A}\right) = 0$$

since $2r^s=2\lambda^{-s}<1$.

Hence, $\dim_H\left(\overline{\mathcal S_A}\right) \le s$. Letting $s\downarrow \frac{\log2}{\log\lambda}$ completes the proof.

Remark : If we also impose $\lambda>2$ in Theorem 2, then $\dim_H\left(\overline{\mathcal S_A}\right)<1$ and hence $\overline{\mathcal S_A}$ has empty interior, hence proving Theorem 1.

On the Neighbour Sum Problem

As a kid, I remember being utterly fascinated by this deceptively simple Olympiad problem.

The 64 squares of an 8 × 8 chessboard are filled with positive integers in such a way that each integer is the average of the integers on the neighboring squares. (Two squares are neighbors if they share a common edge or a common vertex. Thus a square can have 8, 5 or 3 neighbors depending on its position). Show that all the 64 integer entries are in fact equal.

Brief Solution : Any given entry must lie in between the smallest and largest entries of its neighbors. Thus, the largest entry on the board must be surrounded by identical entries. This forces all entries to be equal.

Couple of years ago, I got a little cheeky and decided to ask myself what might happen if we take sums instead of averages. Fortunately, I was able to rope in a few equally deranged friends who were as interested as I was in useless problems, and we got a very precise answer to it.

Question : An $n \times n$ chessboard for $n \geq 3$, with each square bearing an integer, is said to be a solution to the neighbor sum problem if each number is the sum of the numbers on the neighboring squares. Two squares are neighbors if they share a common edge or a common vertex. A chessboard with all squares bearing the number zero is said to be a trivial solution. How many such non-trivial solutions exist for a chessboard of given size $n\times n$?

The idea we used to tackle this problem is to imagine a chessboard full of integers and consider the linear transform

$$x \mapsto - x + \sum_{x\sim y} y$$

where $a\sim b$ represents the relation that $a$ is a neighbour of $b$. The kernel of this linear map is precisely the answer to our question.

It turned out that we were lucky and the matrix representing this linear map can be easily studied using theorems that others have proved before (in other words, we let smarter people from the past do the heavy lifting). Using these theorems, it soon became clear to us that an $n\times n$ chessboard admits a non-trivial solution to the neighbour sum problem if and only if there exist $p, q \in \mathbb{N}$ such that

$$\left(1 + 2\cos\left(\frac{p\pi}{n + 1}\right)\right) \left(1 + 2\cos\left(\frac{q\pi}{n + 1}\right)\right) = 2$$

and $1 \leq p, q \leq n$.

Solving this diophantine requires tools from Algebraic Number Theory (which I will not go into in this post) but it turns out that it has a solution if and only if $6\mid (n+1)$. One solution for a $5\times 5$ board is

$$\begin{array}{|c|c|c|c|c|}\hline 1 & 0 & -1 & 0 & 1 \\\hline 1 & 0 & -1 & 0 & 1 \\\hline \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} \\\hline -1 & 0 & 1 & 0 & -1 \\\hline -1 & 0 & 1 & 0 & -1 \\\hline \end{array}$$

and another is its transpose.

Soon, we realised that these techniques can also be extended to other kinds of more general boards. For example, we proved that non-trivial $m\times n$ chessboards satisfying the neighbor-sum property exist if and only if $2 \mid (m+1)$ and $3 \mid (n+1)$ and that non-trivial $m\times n$ toroidal chessboards satisfying the neighbor-sum property exist if and only if $4 \mid m$ and $6 \mid n$. Of course, the next question to ask is about the dimension of the solution space and that turned out to be more difficult than the first problem. To know more, one can consult our original paper (that has now been accepted in American Mathematical Monthly).

As some of you have already figured out, the more general question to ask is whether it is possible to play the same game on a general graph. This is the question we asked in the first paper and tried to partially answer in a recent preprint where we studied the problem on trees.

Among other things, what we found was an algorithm to test whether a given finite tree satisfies the neighbour sum property. Very briefly, for a given tree and for a fixed (root) vertex $v_0$, we set up the following indexing scheme.

For notational clarity we will use $\bar{r}_l$ to denote a general indexing $r_1,\: r_2,\: \ldots,\:r_l$.

Finally, for a finite tree with a root vertex $v_0$ such that the longest path starting at $v_0$ is of length $k$, we also define

$$S_{1,k}= S_{1,k}(v_0) := \sum_{r_1}\left(1-\sum_{r_{2}}\left(1-\ldots\sum_{r_{k-1}}\left(1-\sum_{r_k} 1\right)^{-1}\ldots\right)^{-1}\right)^{-1}$$

and generally

$$S_{j,k}(\bar{r}_{j-1}) = S_{j,k}(\bar{r}_{j-1}, v_0) := \sum_{r_j}\left(1-\sum_{r_{j+1}}\left(1-\ldots\sum_{r_{k-1}}\left(1-\sum_{r_k} 1\right)^{-1}\ldots\right)^{-1}\right)^{-1}$$

for $1<j\leq k$.

One of our main theorems is that for a finite tree $\mathcal{T}=(\mathcal{V},\:\mathcal{E})$, there exists a pair $(\mathcal{T}, f)$ satisfying the neighbour sum property if and only if there is at least one vertex $v_0\in \mathcal{V}$ such that $S_{1k}(v_0)=1$.

Using this algorithm, we then wrote a code giving us the number of trees on $n$ vertices that satisfies the neighbour sum property and the output was as follows

$$0,1,0,0,1,2,2,6,14,29,63,166,405,977,2481,6530,16757,43534, 115700,308527, 820856, 2205628, 5971743$$

which we have not been able to explain fully. However, we were able to prove that the set of unlabelled trees on $n$ vertices has a positive density subset all of whose elements satisfy the neighbour sum property.

Finally, we also tackled this problem on infinite trees and found a couple of nice results. To know more, the interested reader is suggested to take a look into the two mentioned papers.

Infinitely many Proofs of Pythagoras' Theorem

This post is inspired by an MSE question and the brilliant answers that it received. However, it can be understood independently. Everything here is joint work with Satvik Saha.

Consider the following diagram made of 16 right triangles of sides $a\le b<c$ and four squares of side $b-a$. This being a tiling of the outer square (of side length $2c$), we have

$$(2c)^2 = 4(b-a)^2 + 16\times \frac 12 ab$$

hence implying

$$c^2 = a^2 + b^2$$

thus proving the Pythagoras' Theorem.

Outer square of side $2c$

This is similar to previously known proofs (eg. see proof #3 and #116 here), but it is hard to say whether this exact tiling appears anywhere before.

Now, consider the following diagram made up of right triangles of sides $a\le b<c$, (pink) sqaures of side $a$, (yellow) squares of side $b$, and (green) squares of side $(b-a)$. The reader is welcome to check that this also gives a completely valid proof of the Pythagoras' Theorem.

Outer square of side $3c$

Some of the readers might have started asking the right question. And the answer is yes, it can be generalised! With the outer sqaure of side $nc$, we get $4(n-2)$ of the red and yellow squares, $n^2-4n+8$ of the green squares, and $4(n^2-4n+8)$ of the triangles. This gives

$$n^2 c^2 = 4(n-2) (a^2 + b^2) + (n^2-4n+8) (a-b)^2 + 2(n^2-4n+8) ab$$

hence proving the Pythagoras' Theorem. For your viewing pleasure, here's the $16\times 16$ big square. Feel free to print it out and put it on your wall.

Outer square of side $16c$

Of course, the keen ones among you would ask whether this is truly a tiling for any values of $a$ and $b$ or is it a coincindence of the value chosen in the diagrams. To clear this doubt, here's an animated version of the diagrams. Notice that the animation also shows that it doesn't matter whether you call the larger side of the triangle $a$ or $b$.

Outer square of side $6c$

The keener ones would of course ask for a proof that this is indeed a tiling. For that, one only needs to note that the diagram is made of four spiky triangles (made of a layer of blue triangles followed by a layer of yellow and a layer of pink squares followed by a number of layers of blue triangles) - this is almost a triangle except two spikes on two sides. All one needs to convince oneself is that these spiky triangles fit with each other properly and leave a space in the middle which can be nicely filled by the green squares.

Feel free to play with the animation here (p5js code here). Also, feel free to check out my answer in the aforementioned MSE post.

Worst Way to Calculate Area of a Triangle

A useful technique from Complex Analysis helps us to identify whether a real number $u$ is positive or negative by checking a discontinuous integral. We have

$$\frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} e^{su}\;\frac{\text{d}s}{s} = \begin{cases}0 &\text{ if } u<0\\ \frac 12 &\text{ if } u=0\\ 1 &\text{ if } u>0\end{cases}$$

for $c>0$.

We will apply this to calculate the area of the triangle

$$T(N) := \left\{(x,y)\in \mathbb R_{\ge 0} : ax+by\le N\right\}$$

with $(a,b)=1$. This area is given by

\begin{align*}&\int_{x,y\ge 0} \mathbf{1}_{N-ax-by\ge 0} \;\text{d}x\;\text{d}y\\=&\int_{x,y\ge 0} \frac 1{2\pi i} \int_{s=c-i\infty}^{c+i\infty} e^{s(N-ax-by)}\;\frac{\text{d}s}s \;\text{d}x\;\text{d}y\\=&\frac 1{2\pi i} \int_{s=c-i\infty}^{c+i\infty} \left(\int_{x\ge 0} e^{-asx}\;\text{d}x\right) \left(\int_{y\ge 0} e^{-bsy}\;\text{d}y\right) \frac{e^{sN}}{s}\;\text{d}s\\=&\frac{1}{ab}\cdot \frac{1}{2\pi i} \int_{s=c-i\infty}^{c+i\infty} \frac{e^{sN}}{s^3}\;\text{d}s\end{align*}

by the above mentioned trick. Notice that the integral with $N-ax-by=0$ is zero, and hence was ignored.

Now, moving the contour far to the left we pick up the residue from the pole of order $3$ at $s=0$ and hence the area comes out to be

$$\frac{1}{ab}\cdot \frac{N^2}{2} = \frac{N^2}{2ab}$$

which matches with the area calculated by other known methods!

Acknowledgement : I learnt this from lectures by Prof. Andrew Granville for the course Distribution of Prime Numbers.

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 := \underbrace{A+\dots A}_{k \text{ times}}$$

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

for $A,B\subseteq Z$.

Theorem 1 : We have

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

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{align*} &f:(A-C)\times B \to (A-B)\times (B-C)\\ &(d,b)\mapsto (a_d-b, b-c_d) \end{align*}

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

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

although this definition of $\Delta$ is not really a distance as $\Delta(A,A)\neq 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{align*} &\left\vert A-A\right\vert \le \frac{\left\vert A-B\right\vert^2}{\left\vert B\right\vert}\\ &\left\vert A-A\right\vert \le \frac{\left\vert A+A\right\vert^2}{\left\vert A\right\vert} \end{align*}

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

$$\left\vert A+B\right\vert =c\left\vert A\right\vert \qquad \text{and}\qquad \left\vert A^\prime +B\right\vert \ge c\left\vert A^\prime\right\vert\;\;\;\forall A^\prime \subset A,$$

then, we have

$$\left\vert A+B+C\right\vert \le c\left\vert A+C\right\vert$$

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

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

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

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

$$\left\vert A+C^\prime\right\vert =\left\vert A+C\right\vert +\left\vert A\right\vert -\left\vert A^\prime\right\vert$$

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 \implies 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 \left [(A+B+x)\setminus (A^\prime +B+x)\right ]$$

and

$$\left\vert A+B+C^\prime\right\vert \le \left\vert A+B+C\right\vert + \left\vert A+B\right\vert - \left\vert A^\prime +B\right\vert$$

and hence, using the Induction Hypothesis, we have

$$\left\vert A+B+C^\prime\right\vert \le c\left\vert A+C\right\vert +c\left\vert A\right\vert -c\left\vert A^\prime\right\vert =c\left\vert A+C^\prime\right\vert$$

hence completing the proof.

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

Theorem 4 : We have

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

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

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

$$\left\vert U+A+C\right\vert \le c\left\vert U+C\right\vert$$

using the previous lemma.

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

Corollary 5 : We have

\begin{align*} &\left\vert A+A\right\vert \le \frac{\left\vert A+B\right\vert^2}{\left\vert B\right\vert}\\ &\left\vert A+A\right\vert \le \frac{\left\vert A-A\right\vert^2}{\left\vert A\right\vert} \end{align*}

for all $A, B$.

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

Corollary 6 : We have

\begin{align*} &\left\vert A-B\right\vert \le \frac{\left\vert A+B\right\vert^3}{\left\vert A\right\vert \left\vert B\right\vert}\\ &\left\vert A+B\right\vert \le \frac{\left\vert A-B\right\vert^3}{\left\vert A\right\vert \left\vert B\right\vert} \end{align*}

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

$$\left\vert A+B\right\vert =c\left\vert A\right\vert \qquad \text{and}\qquad \left\vert A^\prime +B\right\vert \ge c\left\vert A^\prime\right\vert\;\;\;\forall A^\prime\subset A$$

for some $c>0$, then

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

for all positive integers $h$.

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

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

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

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{\left\vert A+B\right\vert}{\left\vert A\right\vert}$ so that $\left\vert A+B\right\vert =c^\prime \left\vert A\right\vert$. Obviously $c^\prime\le c$. Also, $\left\vert A^\prime +B\right\vert \le c^\prime \left\vert A^\prime\right\vert$ for all $A^\prime \subset A$ and hence the conditions of Corollary 7 are satisfied. This gives

$$\left\vert hB\right\vert \le \left\vert A+hB\right\vert \le (c^\prime)^h \left\vert A\right\vert \le c^h\left\vert B\right\vert$$

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

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

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

hence completing the proof.