Suppose we know that $t = \sum_{i = 1}^n x_i$ and $M = \sum_{i = 1}^n x_i^2$, where $x_i \in \mathbb{N}^+$.
It's not hard to give $t \leq M$ by eyeballing or if you expand out the square of t and use inequality of arithmetic and geometric means. However, the upper bound on t is very loose. I am wondering if someone can give me a more compact upper bound of t with respect to M (e.g. $O(M^{\frac{3}{4}})$)?
Alternatively, can someone show that the lower bound of t is also $O(n)$ so that it is not possible to give a more compact upper bound?
The upper bound can be some constants multiply by M, but it cannot include $n$.
Thanks!