Tag Archives: pigeonhole principle

Sums of Equal Powers

Let $k$ be a fixed positive integer. Let

$S_k(n):=1^k+\cdots+n^k$.

Let us consider expressions of the form

$\pm 1^k\pm\cdots\pm n^k=\displaystyle\sum_{j=1}^nj^ke_j=: S(e_1,\dots,e_n)$

where $e_j=\pm 1\,\forall j$.

Note that $S$ takes $2^n$ possible values in $[-S_k(n),S_k(n)]$ which are all congruent modulo $2$. Hence the number of distinct values that $S$ takes is at most

$\displaystyle\left\lceil\frac{2S_k(n)+1}{2}\right\rceil=S_k(n)+1$

Since this is $O(n^{k+1})$, it is eventually dominated by $2^n$. Thus for all sufficiently large $n$, we can find $e_j,e_j'\in\{\pm 1\}$ such that

$\displaystyle\sum_{j=1}^nj^ke_j=\sum_{j=1}^nj^ke_j'\Leftrightarrow\sum_{j=1}^n(e_j-e_j')j^k=0$

with $e_j\neq e_j'$ for some $j$.

Note that $e_j-e_j'\in\{0,\pm 2\}\,\forall j$. Let $A=\{j:e_j-e_j'=2\}$ and $B=\{j:e_j-e_j'=-2\}$. Then $A$ and $B$ are non-empty and disjoint, $A\cup B\subseteq\{1,\dots,n\}$, and

$\displaystyle\sum_{j\in A}j^k=\sum_{j\in B}j^k$.

Thus:

Proposition. Let $k$ be a fixed positive integer. Then one can find distinct positive integers $x_1,\dots, x_r,y_1,\dots,y_s$ such that

$x_1^k+\cdots+x_r^k=y_1^k+\cdots+y_s^k$.

In particular, one can choose $x_i,y_j\le\min\{n\in\mathbb N: 2^n>S_k(n)+1\}\,\forall i,j$.

Example. Let $k=4$. Note that $2^n>S_4(n)+1$ for all $n\ge 20$. So there exist distinct integers $1\le x_i,y_j\le 20$ such that $\sum_ix_i^4=\sum_jy_j^4$. In particular, one has

$1^4+2^4+9^4=3^4+7^4+8^4$

as well as

$7^4+8^4+10^4+13^4=3^4+9^4+14^4$.

Likewise, for fifth powers we can find such $x_i$‘s and $y_j$‘s in $[1,26]$.

This wikipedia article contains many results related to sums of powers.

Filed under Number Theory

What Dirichlet Had to Do with the Pigeonhole Principle

Suppose you have six pigeons. You want to put them into five holes. Then at least one of the holes must contain more than one pigeon.

This simple idea is a very important mathematical principle known as the pigeonhole principle, or sometimes Dirichlet principle, Dirichlet’s box principle etc. If you have come across this you have probably wondered (like me) why it is named after Dirichlet, or how exactly did he use it. Dirichlet was one of the most prominent mathematicians of all time, having many important things named after him. E.g.

1. Dirichlet’s theorem on arithmetic progressions that says any arithmetic progression $a, a+d, a+2d,\dots$, where $a$ and $d$ are integers sharing no common factor greater than $1$, must contain infinitely many prime numbers.
2. Dirichlet’s unit theorem, a result about the units in the ring of integers of an algebraic number field.
3. Dirichlet L-function, a generalisation of the Riemann Zeta function.
4. The Dirichlet conditions for a Fourier series.
5. And many, many more.

When I first came to know that the pigeonhole principle was credited to Dirichlet, I was curious as to what Dirichlet had to do with it. A number theory lecture from last term happened to shed some light on it. First we need to know some basic facts about rational approximations.

We know that any real number has arbitrarily good rational approximations: just take the decimal expansion and truncate it anywhere. The more digits, the better the approximation. However, there is a different notion of a ‘good rational approximation’ in number theory.

Let $\alpha$ be a real number. A way of measuring how good a rational number $p/q$ approximates $\alpha$ is to check how small $|q\alpha-p|$ is. We say that $p/q$ is a best approximation to $\alpha$ if for any integers $p'$ and $0 we have $|q'\alpha-p'|>|q\alpha-p|$.

Dirichlet proved the following theorem using his principle:

Theorem. (Dirichlet) Let $\alpha$ be a real number. Then for any integer $N>1$ there exist integers $p,q$ with $0 such that

$\displaystyle|q\alpha-p|<\frac 1N$.

Proof. By $\{x\}$ and $\lfloor x\rfloor$ we respectively denote the fractional part and integer part of the real number $x$. E.g.
$\{20/3\}=2/3$,
$\lfloor 20/3\rfloor=6$,
$\{\pi\}=\pi-3=0.1415926535\dots$,
$\lfloor \pi\rfloor=3$ etc.

Note that $x=\lfloor x\rfloor+\{x\}$.

Consider the numbers $0,1,\{\alpha\}, \{2\alpha\},\dots,\{(N-1)\alpha\}$. These are $N+1$ numbers all lying between $0$ and $1$ (inclusive). Divide the interval $[0,1]$ into the $N$ intervals $[0,1/N], [1/N, 2/N],\dots,[(N-1)/N, 1]$. Since we have $N$ intervals and $N+1$ numbers each lying in one of these, the pigeonhole principle says that there must be two numbers lying in the same interval. Then the difference of these two numbers must be less than $1/N$, the length of the interval.

If one of the two numbers is $1$, then $1/N>|\{m\alpha\}-1|=|m\alpha-(\lfloor m\alpha\rfloor+1)|$ for some $m$, so take $p=\lfloor m\alpha\rfloor+1$ and $q=m$. Otherwise, let the two numbers be $\{m\alpha\},\{n\alpha\}$ with $N-1\ge m>n\ge 0$. Then

$\displaystyle \quad |\{m\alpha\}-\{n\alpha\}|<\frac 1N$
$\displaystyle \Rightarrow |(m\alpha-\lfloor m\alpha\rfloor)-(n\alpha-\lfloor n\alpha\rfloor)|<\frac 1N$
$\displaystyle \Rightarrow |q\alpha-p|<\frac 1N$

where $p=\lfloor m\alpha\rfloor-\lfloor n\alpha\rfloor$ and $q=m-n$, with $0, as required. $\square$