AMM problem 12449

This is AMM problem 12449 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

Let $n$ be a positive integer with $n \geq 2$. The squares of an $(n^2 + n - 1)$-by-$(n^2 + n - 1)$ grid are colored with up to $n$ colors. Prove that there exist two rows and two columns whose four squares of intersection have the same color.

Solution -

Define a monochromatic $i$-pair as an unordered pair of row indices of squares in the same column with the same color $i$.

Note that if the same $i$-pair appears in two distinct columns, we have found a monochromatic rectangle. If not, each column must contribute distinct $i$-pairs, making the maximum number of possible $i$-pairs $\binom{n^2 + n - 1}{2}$, hence the maximum number of monochromatic pairs $n\cdot\binom{n^2 + n - 1}{2}$.

But if the $k$-th column contains $k_i$ squares of color $i$, then it contributes

$$\sum_{i = 1}^n \binom{k_i}{2}$$

monochromatic pairs, which is minimized when one $k_i$ is $n$ and the remaining $n - 1$ many $k_i$ are $n + 1$.

Thus, the $k$-th column contributes at least

$$\binom{n}{2} + (n - 1)\binom{n + 1}{2} = \frac{n\cdot (n^2 + n - 2)}{2}$$

monochromatic pairs, giving a total of at least

$$\frac{(n^2 + n - 1)\cdot n \cdot (n^2 + n - 2)}{2} = n \cdot \binom{n^2 + n - 1}{2}$$

monochromatic pairs.

Since we have equality, each color $i$ must contribute the same number (i.e. $\binom{n^2 + n - 1}{2}$) of $i$-pairs, while simultaneously all $k_i \in \{n, n + 1\}$. The latter means that each color $i$ must contribute a multiple of $n$ many $i$-pairs, whereas

$$n \nmid \binom{n^2 + n - 1}{2}$$

which is a contradiction. $\square$

The $\ell$-th element of a Sidon set in $\mathbb Z_m$

Before we begin, a Sidon set is a set $\mathcal S\subset \mathbb N$ with no non-trivial solutions to the equation $a+b=c+d$ (trivial solutions being those satisfying $\{a,b\}=\{c,d\}$). A Sidon subset $A\subset [n]:=\{1,2,\dots , n\}$ is called dense if $\left\lvert A\right\rvert = \max \left\lvert S\right\rvert$ where the maximum is taken over all Sidon subsets of $[n]$. For a brief introduction to some of the work done in the field, see the first two sections of our paper. That being said, for all practical purposes of this particular post, it is enough to think of Sidon sets as sets with a certain property.

Recently I co-authored Prof. R. Balasubramanian in a work on Sidon sets (which has now been accepted in Journal of Number Theory) where we proved that if $A = \{a_1< a_2< \dots <a_{\left\lvert A\right\rvert}\}\subset [n]$ be a dense Sidon set with $|A|=n^{1/2}-L^\prime$, then

$$a_m = m\cdot n^{1/2} + \mathcal O\left( n^{7/8}\right) + \mathcal O\left(L^{1/2}\cdot n^{3/4}\right)$$

where $L=\max\{0,L^\prime\}$. This helped us to provide easier derivations of results previously also achieved by Ding (see this and this).

The main ingredient in our proof is a theorem due to Cilleruelo. Very informally, the theorem says that if we have a dense Sidon set $\mathcal S \subset [n]$ and if we choose an interval $I\subset [n]$ of length $m$, then $I$ will contain about these many elements of $\mathcal S$. In our proof, we specifically put $I=[1,a_m]$ and this gave us an asymptotic estimate for $a_m$.

It was only much after the paper was uploaded that it came to my notice that an analogue of Cilleruelo's theorem also exists for Sidon sets in $\mathbb Z_m$, due to Tomasz Schoen. This means that our proof technique can also achieve an analogous result for Sidon sets in $\mathbb Z_m$. And (due to technical reasons), this time the calculations will be easier than before. This is what I will show here.

Theorem : Let $A\subset \mathbb Z_m$ be a dense Sidon set with $|A|=m^{1/2}+O(1)$. Then

$$a_\ell = \ell\cdot m^{1/2} + \mathcal O\left( m^{3/4} \ln m\right)$$

where $a_\ell$ is the $\ell$-th element of $A$ (in increasing order).

Proof : Take Theorem 1 from Schoen's paper and put

$$\mathscr I = \{1,2,\dots , a_\ell\}$$

so that (by definition) $\left\lvert \mathscr I\right\rvert = a_\ell$ and $\left\lvert A\cap \mathscr I\right\rvert = \ell$. So, by Schoen's theorem,

$$\left\lvert \ell - \left\lvert A\right\rvert \cdot \frac{a_\ell}{m}\right\rvert = \mathcal O \left(\left\lvert A\right\rvert^{1/2} \ln m\right)$$

and hence

$$\frac{a_\ell}{\sqrt{m}} = \ell + \mathcal O\left(m^{1/4}\ln m\right)$$

thus giving

$$a_\ell = \ell \sqrt m + \mathcal O\left(m^{3/4}\ln m\right)$$

hence completing the proof.

Finding asymptotic form for $\sum_{a\in \left\lvert A\right\rvert} a^k$ (as done in our original paper) is now only a matter of computaion and is left as an exercise for the reader. It should be noted (as was also done in the original paper) that this theorem is technically a valid formula for all $\ell$, but it's only useful as an asymptotic formula when $\ell$ is close to $\sqrt m$, more precisely when $\ell > m^{1/4}\ln m$.

AMM problem 12448

This is AMM problem 12448 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

Given real numbers $a_1, \dots, a_n$. Prove

$$S_1\sqrt{nS_2} \leq S_1^2 + \frac{1}{2}\left\lfloor\frac{n^2}{4}\right\rfloor\left(\max_i a_i - \min_i a_i\right)^2$$

where $S_1 = \sum_{i = 1}^n a_i$ and $S_2 = \sum_{i = 1}^n a_i^2$.

Solution -

Without loss of generality, let $a_1 \leq \dots \leq a_n$ and $S_1 > 0$.

Setting $\mu = S_1 / n$, we need to prove 

$$\mu \sqrt{\sigma^2 + \mu^2} \leq \mu^2 + \frac{1}{2}\left\lfloor\frac{n^2}{4}\right\rfloor \frac{(a_n - a_1)^2}{n^2}$$

where $\sigma^2 = \frac{1}{n}\sum_{i = 1}^n (a_i - \mu)^2 = \frac{S_2}{n} - \mu^2$.

Squaring both sides, this is equivalent to

$$\sigma^2 \leq \left\lfloor\frac{n^2}{4}\right\rfloor \frac{(a_n - a_1)^2}{n^2} + \frac{1}{4\mu^2}\left(\left\lfloor\frac{n^2}{4}\right\rfloor \frac{(a_n - a_1)^2}{n^2}\right)^2 \tag{$\star$}$$

since $\mu > 0$.

Let $\mu_{\mathbf{x}} = \frac{1}{n} \sum_{i} x_i$ and $\sigma^2_{\mathbf{x}} = \frac{1}{n}\sum_i (x_i - \mu_{\mathbf{x}})^2$ for real numbers $x_1, \dots, x_n$.

Since $\sigma^2_{\mathbf{x}}$ is a smooth convex function of $\mathbf{x}$, it attains its maximum on $[a, b]^n$ at an extreme point, i.e. when all $x_i \in \{a, b\}$.

If exactly $k$ many $x_i$ are equal to $a$ and $n - k$ many are equal to $b$, we have

$$\sigma^2_{\mathbf{x}} = \frac{k(n - k)}{n^2}(b - a)^2.$$

Now, $(n - 2k)^2 \geq 0$ gives $k(n - k) \leq n^2/4$, forcing $k(n - k) \leq \lfloor n^2/4\rfloor$.

Thus, 

$$\max_{\mathbf{x} \in [a, b]^n} \sigma^2_{\mathbf{x}} \leq \left\lfloor\frac{n^2}{4}\right\rfloor \frac{(b - a)^2}{n^2}$$

and $\sigma^2 \leq \lfloor n^2/4\rfloor (a_n - a_1)^2/n^2$, from which ($\star$) follows directly. $\square$

Another Needlessly Sophisticated Proof of a Simple Result

This post belongs solely to a genre that should be called "joke proofs". The only thing a joke proof provides (except an awfully sophisticated argument for a very simple result) is intellectual stimulation. Some very well known contributions to this field are a proof of irrationality of $2^{1/n}$ using Fermat's Last Theorem or a proof of infinitude of primes using irrationality of $\zeta(3)$ (although infinitude of primes have received some more suspicious entries as well).

The following theorem (if you can call it a theorem) follows directly from looking at the integers $\{(k+1)! +\ell\}_{\ell = 2}^{k+1}$. But our proof instead uses two other well known results, namely the fact that the sum of reciprocals of primes diverges (proof) and something slightly stronger than the fact that the sum of reciprocals of twin primes converges (proof). It is well known that an exact same proof technique runs through to show that if $\mathcal S_k = \{p\in \mathcal P : p+k \in \mathcal P\}$ where $\mathcal P$ is the set of primes, then $\sum_{s\in \mathcal S_k} \frac 1s$ converges. This is what we will use in the proof.

As far as my knowledge goes (which is not too far), this proof is completely original, although that's not something to be very proud of!

Theorem : For any given $k$, there exists $k$ consecutive composite numbers.

Proof : If possible, let

$$\sup_{p_1, p_2 \text{ are consecutive primes}} \left\vert p_1-p_2\right\vert = B$$

for some integer $B$.

Then

$$\sum_{i=1}^B \;\;\sum_{p, p+i\in \mathcal P} \frac 1p \ge \sum_{p\in \mathcal P} \frac 1p$$

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

The LHS converges by Brun sieve and the RHS diverges, hence giving a contradiction! $\square$

AMM problem 12435

This is AMM problem 12435 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

For a positive integer $n$, let $d(n)$ be the number of positive divisors of $n$, let $\phi(n)$ be Euler's totient function, and let $q(n) = d(\phi(n)) / d(n)$. Find $\inf_n q(n)$ and $\sup_n q(n)$.

Solution -

We claim that $\inf_n q(n) = 0$ and $\sup_n q(n) = \infty$.

To show that $\sup_n q(n) = \infty$, note that $q(p) = d(p - 1) / 2$ for primes $p$, which can be made arbitrarily large. Indeed, for any $\ell \in \mathbb{N}$, the arithmetic progression $\{\ell!\, k + 1\}_{k \in \mathbb{N}}$ must contain a prime $p'$ (due to Dirichlet) whence $p' - 1 = \ell!\,k'$ has at least $M$ divisors so that $d(p' - 1) \geq \ell$.

Next, we show that $\inf_n q(n) = 0$. To do so, we choose arbitrary $m \in \mathbb{N}$ and find $N$ such that $q(N) \leq 1/2^{m - 1}$. Pick a sequence $\mathcal{Q}_m$ of $m$ primes $q_1 \leq \dots \leq q_m$ such that $q_m < 2q_1$; we will show later that this is always possible via the Prime Number Theorem. Let $\mathcal{P} = \{p_1, \dots, p_n\}$  be all the primes less than $q_1$. Note that each $q_i - 1$ and each $p_j - 1$ can be factored solely in terms of the primes from $\mathcal{P}$.

For $k_1, \dots, k_n \in \mathbb{N}$, consider

$$N = N(k_1, \dots, k_n) = p_1^{k_1}\cdots p_n^{k_n} \times q_1\cdots q_m,$$

With this, we have 

$$d(N) = (k_1 + 1)\cdots (k_n + 1)\times 2^m$$

and

\begin{align}\phi(N) &= p_1^{k_1 - 1} \cdots p_n^{k_n - 1} \times (p_1 - 1)\cdots (p_n - 1)\times (q_1 - 1)\cdots (q_m - 1)\\ &= p_1^{k_1 + \alpha_1 - 1} \cdots p_n^{k_n + \alpha_n - 1}\end{align}

where the integers $\alpha_j \geq 0$ depend only on $\mathcal{Q}_m$. Thus,

$$d(\phi(N)) = (k_1 + \alpha_1)\cdots (k_n + \alpha_n)$$

and

$$q(N(k_1, \dots, k_n)) = \left(\frac{k_1 + \alpha_1}{k_1 + 1}\right)\cdots \left(\frac{k_n + \alpha_n}{k_n + 1}\right) \times \frac{1}{2^m}.$$

Taking $\min\{k_1, \dots, k_n\} \to \infty$, we can make $q(N(k_1, \dots, k_n))$ arbitrarily close to $1/2^m$, in particular less than $1/2^{m - 1}$.

To prove the existence of $\mathcal{Q}_m$ for each $m \in \mathbb{N}$, it is enough to show that there is $n \in \mathbb{N}$ such that $[n, 2n]$ contains at least $m$ primes. By the Prime Number Theorem, the number of primes in $[n, 2n]$ is of the order

$$\frac{2n}{\log(2n)} - \frac{n}{\log(n)} \sim \frac{n}{\log(n)}$$

which grows arbitrarily large as $n \to \infty$.

Note : Here's an easier proof of $\inf_n q(n) = 0$ assuming that there are infinitely many Fermat primes. Consider the sequence

$$N=2^k\cdot F_1\dots F_n$$

where $F_1,\dots ,F_n$ are the first $n$ Fermat primes. This gives

$$q(N)=\frac{k+\alpha_1+\dots +\alpha_n}{k+1}\times \frac 1{2^n}$$

where $F_i=2^{\alpha_i}+1$. Taking $k$ and $n$ to infinity, we complete the proof.

Thanks to this argument, if $\inf_n q(n) \neq 0$, then that implies that there are only finitely many Fermat primes, which resolves a long standing conjecture about Fermat primes. Since that is highly unlikely, the $\inf$ has to be $0$ - this is a classic case of proof by existence of proof!

AMM problem 12377

This is my first post (or second, depending on how you look at the world). For this, I decide to post the first AMM problem I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

We define a one-drop number as in problem 12377 from Problems and Solutions, The American Mathematical Monthly, Volume 130, 2023, Issue 3.

An integer is a one-drop number if its decimal digits \(d_1, \dots, d_n\) satisfy

$$1 \leq d_1 \leq d_2 \dots \leq d_i > d_{i + 1} \leq \dots \leq d_n$$

for some \(i\), with \(1 \leq i < n\).

For example, the numbers \(13802\) and \(49557\) are one-drop numbers, while the numbers \(12345\) and \(352712\) are not.

We answer the following question: for \(n \geq 2\), how many \(n\)-digit one-drop numbers are there?

Solution -

There are

$$\binom{n + 18}{18} - \binom{n + 9}{9} - n\cdot\binom{n + 8}{8}$$

one-drop numbers of length \(n \geq 2\).

The digits of every \(n\)-digit one-drop number \(d_1, \dots, d_n\) can be uniquely split into two zero-drop blocks \(A\) and \(B\), with digits \(1 \leq d_1 \leq \dots \leq d_i\) and \(0 \leq d_{i + 1} \leq \dots \leq d_n\). Here, is a zero-drop block consists of a sequence of non-decreasing decimal digits; we allow the leading digit to be \(0\).

Consider all \(19\)-tuples \( (a_1, \dots, a_9, b_0, b_1, \dots, b_9) \) of non-negative integers such that

$$a_1 + \dots + a_9 + b_0 + b_1 + \dots + b_9 = n.$$

Each tuple represents an \(n\)-digit number obtained by concatenating two zero-drop blocks \(A\) and \(B\), where \(a_d\) and \(b_d\) denote the number of occurrences of the digit \(d\) in the respective blocks. Clearly, there are \(\binom{n + 18}{18}\) such tuples. Note that each tuple of this kind represents either a zero-drop or a one-drop number, and each \(n\)-digit one-drop number is uniquely represented by such a tuple.

Discard all tuples where the block \(A\) is empty, with all \(a_d = 0\); the corresponding number is zero-drop. There are as many such tuples as there are non-negative integer solutions of 

$$b_0 + b_1 + \dots + b_9 = n,$$

that is, \(\binom{n + 9}{9}\). This leaves \(\binom{n + 18}{18} - \binom{n + 9}{9}\) tuples; call this set of tuples \(S\). Note that for any element in \(S\), the block \(A\) is non-empty. Thus, it represents a proper \(n\)-digit number since the leftmost digit is non-zero.

Suppose that a tuple \( (a_1, \dots, a_9, b_0, b_1, \dots, b_9) \in S\) represents a zero-drop number. Since some \(a_d > 0\), the digit \(0\) cannot appear in block \(B\), hence the number consists only of digits \(1\) through \(9\). There are \(\binom{n + 8}{8}\) such \(n\)-digit zero drop numbers, via counting the non-negative integer solutions of

$$c_1 + \dots + c_9 = n.$$

Each of these numbers has been represented by precisely \(n\) tuples from \(S\), because the first \(i\) digits of such a number can be placed in block \(A\) with the remaining digits in block \(B\) for all \(1 \leq i \leq n\).

For example, the \(5\)-digit zero-drop number \(11234\) can be broken into blocks \(A, B\) as \(1, 1234\) or \(11, 234\) or \(112, 34\) or \(1123, 4\) or \(11234, \emptyset\), each of which correspond to distinct tuples from \(S\).

Thus, precisely \(n\cdot\binom{n + 8}{8}\) tuples from \(S\) represent zero-drop numbers. The remaining $\binom{n + 18}{18} - \binom{n + 9}{9} - n\cdot\binom{n + 8}{8}$ tuples uniquely represent all \(n\)-digit one-drop numbers. $\square$

Hello World

Hey there!

I am Sayan Dutta, a student of mathematics interested in Number Theory and Combinatorics. I completed my BS-MS from IISER Kolkata and I will be joining a PhD program in 2025 in University of Montreal under Prof. Dimitris Koukoulopoulos. Before that, I completed my Masters' thesis under the supervision of Prof. Ramachandran Balasubramanian and Prof. Soumya Bhattacharya. My thesis was on Sidon sets and can be found in my website.

A far less boring description of me was given by my dear friend Sohom Gupta

Sayan Dutta is an undergraduate student of mathematics, interested in discrete mathematics and vibrant patterns hidden in the simplest of structures. His appreciation of beauty stems from his cinephile present, while his chess moves are just nuances of perfection. He aspires to paint the world in the language of mathematics and the blossoms of the silver screen.

Inspired by What's new, Joni's Math Notes and others, I decided to keep a blog of my own. As of now, I don't have any particular plans and will post anything I have in mind (only related to mathematics). We will see where this goes!