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.

Advertisements

Leave a comment

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<q'<q 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<q<N 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<q<N, as required. \square

Leave a comment

Filed under Combinatorics, Number theory