Recent Updates

Aditya Guha Roy 1:12 am on June 16, 2021  

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

What's new

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

Aditya Guha Roy 2:11 pm on June 14, 2021
Tags: , ,   

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).

Theorem 2:
Let f be a continuous, 1-periodic function with Fourier coefficients c_k : = \langle f , e_k \rangle = \int_{0}^{1} f(x) e^{-2 \pi i k x} for each k \in \mathbf{Z}.
Suppose that \sum_{k=-\infty}^{\infty} |c_k| < \infty.
Then the Fourier series of f converges uniformly to f.
As a consequence, f(x) = \sum_{k=-\infty}^{\infty} c_k e_k (x) holds for all real numbers x.

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.

#fourier-analytic-methods, #fourier-series, #fourier-transform

Aditya Guha Roy 6:40 am on May 30, 2021
Tags: ,   

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:

Proposition 1:
If T is a finite tree, x,y are two vertices of T and \tau(x,y) denotes the number of steps taken by a simple random walk on T starting at x to reach vertex y then
\displaystyle \mathbf{E} \left [ \binom{\tau (x,y)}{2} \right ] is an integer.

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:

Corollary 2:
If T is a finite tree, x,y are two neighbouring vertices of T and y is a leaf of T and if \tau(x,y) denotes the number of steps taken by a simple random walk on T starting at x to reach vertex y then
\displaystyle \mathbf{E} \left [ \binom{\tau (x,y)}{2} \right ] is an integer.

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:

Lemma 4:9
For a simple random walk on a finite tree T and any two adjacent vertices x,y of T with y being a leaf of T the variance \textsf{Var}(\tau (x,y) ) is an even integer.

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

#markov-chains, #yuval-peres

Aditya Guha Roy 5:22 am on May 29, 2021
Tags: complex numbers, ,   

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.

Proposition 1 (Napoleon’s triangle theorem)
Given any triangle ABC, we construct equilateral triangles \Delta A'BC, \Delta B'CA, \Delta C'AB erected outwards (i.e., the points A',B',C' lie in the exterior of \Delta ABC) on the sides BC, CA, AB respectively. Let A'', B'', C'' be the centroids of triangles A'BC, B'CA, C'AB respectively. Then \Delta A''B''C'' must be an equilateral triangle.

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

Figure 1: Pictorial description of the setup of Napoleon’s triangle which says that the dotted triangle must be equilateral.

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)

Remark: Some sources believe that the proof discussed above was known much before Béla Bollobás’s discovery of the proof.

#complex-numbers, #easy-beautiful-proofs, #geometry

Aditya Guha Roy 1:07 pm on May 25, 2021
Tags: , Euler's number e   

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).

Proposition 1:
A real number a satisfies a^x \ge 1+x for all real numbers x if and only if a =e (where e denotes Euler’s number).

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.)

#easy-beautiful-proofs, #eulers-number-e