For a positive integer $n$, denote with $b(n)$ the smallest positive integer $k$, such that there exist integers $a_1, a_2, \ldots, a_k$, satisfying $n=a_1^{33}+a_2^{33}+\ldots+a_k^{33}$. Determine whether the set of positive integers $n$ is finite or infinite, which satisfy: a) $b(n)=12;$ b) $b(n)=12^{12^{12}}.$
Problem
Source: Bulgarian Spring Tournament 2024 12.3
Tags: number theory
Tintarn
01.04.2024 13:50
The set of such $n$ is infinite. In fact, note that modulo $67$, the possible residues of $33$-rd powers are just $0$, $1$ and $-1$ by Fermat. Thus, to express a number in the congruence class $12 \pmod{67}$ as a sum of $33$-rd powers we need at least $12$ summands.
On the other hand, of course infinitely many numbers in this congruence class can indeed be expressed as sums of twelve $33$-rd powers, e.g. $(67k+1)^{33}+11$ for any $k$.
The set of such $n$ is finite, in fact empty. Indeed, let us show that any $n$ has $b(n) \le 12^{65}$ (which could be much strengthened, but completely suffices for us).
The main point is taking finite differences to reduce to a linear polynomial. E.g. with $(x+1)^{33}-x^{33}=33x^{32}+\dots$ we get a degree-$32$-polynomial by taking a suitable sum of two $33$-rd powers.
Iterating, we find that $\Delta^{32}(x^{33})$ is a linear polynomial $33!x+c$ and can be described as a sum of $2^{32}$ terms of the form $(x+k)^{33}$.
Thus, we can obtain any number in a fixed congruence class modulo $33!$ with at most $2^{32}$ terms, and then of course we can just add some ones to reach each number with at most $2^{32}+33! <12^{64}+12^{64}<12^{65}$ summands.