On Prielipp's problem on signed sums of \(k\)th powers (Q1907850)

Starting with a question of R. W. Prielipp (concerning the special case \(k=2\) of the author's main result), the author proves by elementary (number-theoretical and combinatorial) methods: For every positive integer \(n\) and any integer \(k\geq 0\), there is an integer \(m\) and a vector \(\{\varepsilon_0, \dots, \varepsilon_m\}\), where every \(\varepsilon_i\) is from the set \(\{+1, -1\}\), such that \((**)\) \(n= \sum^m_{i=0} \varepsilon_i \cdot i^k\). For the ``length'' \(L(n)\) of this representation the author gives a lower and an upper bound, which -- for fixed \(k\) -- implies for the minimal \(m\) in \((**)\) the asymptotic relation, as \(n\to \infty\): \[ L(n)\sim [( k+1)\cdot n]^{1\over {k+1}}. \] Similarly, for fixed \(n\), a lower bound \(\ell(k)\geq k+2\), as \(k\to \infty\), is given. Finally, some problems and conjectures are mentioned.