# Is this version of Lagrange's four-square theorem true?

Lagrange's four-square theorem states that any natural number $n$ can be represented as the sum of four integer squares.i.e. $n = a_1\times a_1 + a_2\times a_2 + a_3\times a_3 + a_4\times a_4$

Question: Is there any natural number $k$ such that: $$\forall n\geq1~~\exists a_1,...,a_k\geq 0~;~~~~n=a_1^{a_1}+\cdots+a_k^{a_k}$$

In order to avoid triviality about small numbers we define $0^0$ to be $0$ so in the case of $k>2$ we may represent $2$ as $1^1+1^1+0^0+...+0^0$.

Remark: I think the answer should be negative because of the fast growth speed of exponentiation function which makes the building blocks ($a^a$ s) so rare and this fact makes the necessary number $k$ larger and larger.

• It is easy to see that $k=2$ doesn't work. But then we cannot represent $n=2$. – André Nicolas Nov 22 '14 at 6:29
• @AndréNicolas Can't we write $2=1^1+1^1$? – user180918 Nov 22 '14 at 6:39
• @AliSadeghDaghighi Those are two separate sentences. $k=2$ doesn't work, but $k>2$ fails to represent $n=2$ due to the unnatural requirements in the OP. – Erick Wong Nov 22 '14 at 6:43
• @ErickWong Thanks for reminding me the typo on the conditions over $a$. I edited the question. – user180918 Nov 22 '14 at 6:45

As a simple proof, fix $k$ and consider the numbers from $1$ to $(2k)^{2k}$. Any $a_i$ in the representation of a number in this range must be at most $2k$. Therefore, there are at most $(2k+1)^{k}$ numbers $n$ in this range which can be represented as a sum $n=a_1^{a_1}+\cdots+a_k^{a_k}$. But as for $k>1$, $4k^2>2k+1$, it follows that $(2k)^{2k} > (2k+1)^k$, and there exists a number with no such representation.
• +1. A generalization of this argument shows that in order for $k$ to work, the sequence $a_n$ must grow at most as fast as $O(n^k)$. A simple greedy argument would probably suffice to show that finite $k$ is impossible if $a_{n+1} > 2a_n$. – Erick Wong Nov 22 '14 at 8:08