The sum of the squares of the parts of a partition, and some related questions (Q1262895)

The result that given positive integers m,n with \(n\leq m\leq n^ 2/5\) and \(m\equiv n (mod 2)\), there exist positive integers \(x_ i\) such that \(\sum \left( \begin{matrix} x_ i\\ 2\end{matrix} \right)=(m-n)/2\) arises in graph theory [\textit{P. Winkler}, Mean distance in a tree, Discr. Appl. Math. (to appear)]. The upper bound for m is shown to be \(n^ 2- 2^{3/2}n^{3/2}+O(n^{5/4})\). More general results, which extend those of Erdős, Hensley and Purdy, are obtained for a class of polynomials p(t) (which includes \(\left( \begin{matrix} t\\ k\end{matrix} \right)\), \(k\geq 2)\). It is pointed out that Waring's problem corresponds to finding the minimum of the cardinality of the set \(\{x_ i\}\) such that \(m=\sum x_ i^ k\).