# Singmaster’s conjecture in the interior of Pascal’s triangle

Kaisa Matomki, Maksym Radziwill, Xuancheng Shao, Joni Tervinen, and myself have just uploaded to the arXiv our preprint “Singmaster’s conjecture in the interior of Pascal’s triangle“. This paper leverages the theory of exponential sums over primes to make progress on a well known conjecture of Singmaster which asserts that any natural number larger than $latex {1}&fg=000000$ appears at most a bounded number of times in Pascal’s triangle. That is to say, for any integer $latex {t geq 2}&fg=000000$, there are at most $latex {O(1)}&fg=000000$ solutions to the equation

$latex displaystyle binom{n}{m} = t (1)&fg=000000$

with $latex {1 leq m < n}&fg=000000$. Currently, the largest number of solutions that is known to be attainable is eight, with $latex {t}&fg=000000$ equal to

$latex displaystyle 3003 = binom{3003}{1} = binom{78}{2} = binom{15}{5} = binom{14}{6} = binom{14}{8} = binom{15}{10} &fg=000000$

$latex displaystyle = binom{78}{76} = binom{3003}{3002}.&fg=000000$

Because of…

View original post 1,408 more words

# Uniform convergence of Fourier series for continuous periodic functions with absolutely summable Fourier coefficients

In a previous blogpost we proved the $L^2$ convergence of the Fourier series of a Riemann integrable 1-periodic function $f$ to $f$. However $L^2$ convergence doesn’t tell us anything about pointwise convergence.

Exercise 1:

(i.) Find an example of a sequence $(f_n)_{n \in \mathbf{N}}$ of functions which converge in $L^2$ norm to a function $f$ but does not converge pointwise to $f.$

(ii.) Find an example of a sequence $(g_n)_{n \in \mathbf{N}}$ of functions which converges pointwise to a function $g$ but does not converge in $L^2$ norm to $g.$

(iii.) Let $(h_n)_{n \in \mathbf{N}}$ be a sequence of functions which converge pointwise to a function $H_1$ and in $L^2$ norm to a function $H_2.$ Is it possible to have $H_1 \ne H_2 ?$

Under some conditions however one can ensure pointwise convergence of the Fourier series of a function; in fact in what follows we discuss one important condition under which we can guarantee uniform convergence of the Fourier series of a function (which in particular would imply its pointwise convergence).

Proof: Notice that if $\sum_{k= - \infty}^{\infty} |c_k| < \infty$ then $\sum_{k=-\infty}^{\infty} c_k e_k(x)$ converges uniformly. Let $g$ denote this limit (i.e., $g(x) = \sum_{k=-\infty}^{\infty} c_k e_k(x)$).

Then notice that $g$ being the uniform limit of a sequence of continuous functions must be a continuous function itself.

However we know that the Fourier series of $f$ must converge to $f$ in $L^2$ norm.

Thus, one must have $||f-g||_2 = 0.$ However since both $f,g$ are continuous functions so

$||f - g||_2 = 0 \implies f=g.$

This proves the claim. $\square$

Exercise 3:

If $f$ is continuous, periodic and piecewise continuously differentiable, then prove that the Fourier series of $f$ converges uniformly to $f.$

# Second binomial moments of hitting times for a simple random walk on a finite tree are integers

In a previous blogpost I proved that the first moments of hitting times for a simple random walk on a finite tree are integers. That answered a part of a more general problem which I was asked by professor Yuval Peres, and in this blogpost I address another part of his question by proving the following:

Interestingly, in this case too one can reduce proving Proposition 1 to proving it for the special case when $x,y$ are neighbouring vertices, and in particular when $y$ is a leaf of $T.$ The verification of this reduction is left as an exercise for the readers.

Thus we would only need to prove the following corollary of Proposition 1:

Exercise 3:

Prove that Proposition 1 and Corollary 2 are logically equivalent.

We can do further reduction. Taking help of our conclusions drawn here and the observation that

$\displaystyle \mathbf{E} \left [ \binom{\tau(x,y)}{2} \right ] = \frac{1}{2} \left ( \mathbf{E}[\tau(x,y)^2] - \mathbf{E}[\tau(x,y)] \right ),$

it suffices to show that $\mathbf{E}[\tau(x,y)^2]$ is an integer having the same parity as that of $\mathbf{E}[\tau(x,y)].$

Thus, it suffices to show the following claim:

Proof of Lemma 4: We induce on the number $n$ of vertices of $T,$ with the base case being $n=2$ (since $n=1$ is a vacuous case). For $n=2$ the tree $T$ just comprises of two vertices joined by an edge and thus $\textsf{Var}(\tau(x,y)) = 0$ (which is an even integer) in this case.

Next we make some observations.

Let $k = \textsf{ deg } (x)$ be the number of vertices which are adjacent to the vertex $x$ in the tree $T$ and let the neighbours of $x$ in the tree $T$ be $x_1 , x_2 , ........... , x_k$ with $x_1 = y$ being the concerned target (leaf) node.

We think of the Markov chain evolving in the following way: when the particle performing the simple random is at the node $x$ it rolls a fair $k$ sided dice, and if the outcome is $j$ then it moves to $x_j$ and then performs a symmetric simple random walk on $T$ starting at the $x_j$ as usual until it reaches $x$ upon which we again roll the dice and continue so on and so forth unless the particle hits the state $x_1 = y$ upon which we stop; it is easy to notice that the collection $(Z_n )_{ n =1 } ^{\infty}$ obtained in this way is indeed a symmetric simple random walk on the tree $T.$ Thus let $R_1 , R_2, ............$ denote the sequence of outcomes on respective independent rolls of the $k$ sided dice and let $G := \inf \{ n \ge 1 : R_n = 1 \}$ denote the first time the dice shows up $1$ as the outcome. Clearly $G$ has the geometric distribution with success probability $1/k$ and thus $\mathbf{E} [ G ] = k.$

Now this allows us to write

$\tau ( x , y ) = n+ \tau (x _{R_1} , x ) + \tau ( x_{R_2} , x ) + .......... + \tau ( x_{R_G} , x ) ~~~~~~~ (1),$

where $R_j$ s denote the respective outcome of the tosses and $n$ is some integer, thus one can write

$\tau (x,y ) = m + A_1 + A_2 + .......... + A_G ~~~~~~~ (2),$

for some integer $m$ and where $A_j = \tau ( x_{R_j} , x )$; these $A_j$ s basically correspond to the time difference between two consecutive respective visits to the vertex $x$ of $T$, thus $A_1 , ............ , A_G$ are independent and identically distributed and $A_1 , A_2 , ........ , G$ are also independent.

So, by Wald’s identity for variances one has:

$\displaystyle \textsf{Var}(\tau (x,y)) = \mathbf{E}[A]^2 \textsf{Var}(G) + \textsf{Var}(A) \mathbf{E}[G] ~~~~~~~ (3),$

where $A$ is a random variable with the same probability distribution as that of $A_1.$

Now, by our induction hypothesis it follows that $\textsf{Var}(A)$ is an even integer, and in this scenario we have

$\displaystyle G \sim$geometric $( 1/ \textsf{deg}(x)) ~~~~~~~ (4),$

and hence $\textsf{Var}(G) = \textsf{deg}(x) \cdot ( \textsf{deg}(x) -1 )$ and thus $\textsf{Var}(G)$ is an even number, so that $\textsf{Var}(\tau(x,y))$ is a sum of two even numbers and hence also it is an even number, thus proving the claim. $\square$

# Béla Bollobás’s proof of Napoleon’s triangle theorem

Recently I came across a super cute proof of Napoleon’s triangle theorem using complex numbers in Béla Bollobás’s book “The Art of Mathematics: Coffee time in Memphis”. Realizing the fact that I never knew it till now, and the fact that it is neither discussed in the standard textbooks on Euclidean geometry I read till day nor any online reading source (for instance Wikipedia doesn’t discuss this proof, however the Cut the Knot page on Napolean’s triangle discusses this proof), I think that despite being so beautiful this proof is not very popular (especially among math Olympians and other mathematics enthusiasts at the undergraduate level), and thus I decided to dedicate this blogpost for discussing the proof.

Here is an illustration of how the setup of Napoleon’s triangle theorem looks like.

Here $A'BC, B'CA, C'AB$ are equilateral triangles erected outwards on the sides $BC, CA, AB$ of $\Delta ABC,$ and $A”, B”, C”$ are the centroids of $\Delta A’BC, B’CA, C’AB$ respectively; we wish to show that the dotted triangle (i.e., the triangle with its edges marked by dotted lines

Proof: We notice that a triangle $\Delta PQR$ is equilateral if and only if the angle between the sides $PQ$ and $PR$ is $60^{\circ}$ and $|PQ| = |PR|;$ in other words $\Delta PQR$ is equilateral if and only if rotating the side $PQ$ by an angle of $60^{\circ}$ gives the side $PR$ of this triangle.

So, it suffices to show that rotation of side $A''B''$ of triangle $\Delta A''B''C''$ gives the side $A''C''$ of this triangle; in terms of complex numbers a rotation by an angle of $60^{\circ}$ basically corresponds to multiplication by the complex number $e^{i \pi / 3}.$

The idea is to write each side of triangle $\Delta A''B''C''$ in terms of complex numbers and then verify the fact that multiplication by $e^{i \pi / 3}$ rotates the side $A''B''$ to yield $A''C''.$

Let $\alpha = CA'', \beta = AB'', \gamma = BC'',$ and $\tau = e^{i \pi / 3}.$ Then one has $\tau ^3 = -1,$ and $\tau = 1+\tau^2.$ Also one obtains $A''B = \tau \alpha, B''C = \tau \beta,$ and $C''A = \tau \gamma.$ Thus we immediately get

$\displaystyle (1+\tau)(\alpha + \beta + \gamma) = \alpha + \tau \alpha + \beta + \tau \beta + \gamma + \tau \gamma = 0 ~~~~~ (1).$

whence $\alpha + \beta + \gamma = 0$ (since $1+ \tau \ne 0$ and the product of two non-zero complex numbers must necessarily be non-zero).

Now, notice that $\tau A''C'' = \tau (A''B + BC'') = \tau (\tau \alpha + \gamma).$
Hence, $\tau A''C'' - A''B'' = \tau(\tau \alpha + \gamma) + (\tau \beta + \alpha) = (\tau^2 +1) \alpha + \tau \beta + \tau \gamma = 0$ thus proving the claim. $\square$

EDIT: (Last updated on 7 June, 2021)

# a raised to the power x is never lesser than 1+x if and only if a = e

Here I prove the following interesting result in a very slick way (this is a proof is beleived to be originally due to Paul Erdős, although I discovered on my own long ago (approximately in 2016-17), and since then it has remained one of my favourite deductions).

Proof: One part of the claim is fairly straightforward

$\displaystyle e^x = \lim_{n\to\infty} \left ( 1+ \frac{x}{n} \right)^n \ge 1 + x ~~~~~~~ (1)$ by Bernoulli’s inequality.

For proving the converse we use the following important property of Euler’s number $e.$

Exercise 2:

Show that $e^{1/e} \ge x^{1/x}$ for all positive real numbers $x,$ with equality if and only if $x=e.$

(Hint: Consider the function $y \mapsto y^{1/y}$ defined for $y >0;$ this is a differentiable function; differentiate it (for this step you may require to consider differentiating $\ln ( y^{1/y})$) and find where the derivative changes sign, where it is positive and where it is negative to conclude the result.)

Conversely suppose $a^x \ge 1+x$ holds for every real number $x.$ Let $t$ be an arbitrary positive real number. Then putting $x = \frac{1}{ta} - 1$ one has

$\displaystyle a^{\frac{1}{ta} -1} \ge \frac{1}{ta} ~~~~~~~ (2)$

$\displaystyle \implies a^{1/ta} \ge \frac{1}{t} ~~~~~~~ (\text{ by multiplying both sides of (2) by } a)~~~~~~~ (3)$

$\displaystyle \implies a^{1/a} \ge \left ( \frac{1}{t} \right ) ^{t} ~~~~~~~ (\text{ by raising both sides of (3) to the power of } t)$

$\implies a=e$ (thanks to Exercise 2). $\square$

Exercise 3:

Let $a>0$ be a positive real number satisfying $a^z \ge 1+z$ for all real numbers $z \in (-1, \infty).$ Show that $a = e$ (the Euler’s number).

(Hint: The same proof as that of Proposition 1 works once we notice that if $t>0, a>0$ then $\frac{1}{ta} - 1 > - 1.$)