Bounding the sum of squares of some positive real numbers given their sum and an upper bound on them

Question

Let's say we have $k$ real numbers $a_1, a_2, \dots, a_k$ and a positive real number $n$ that satisfy the following constraints:

• $\sum\limits_{i=1}^{k}a_i=n$,
• $\forall_{i\in\{1,2,\dots,k\}} \quad 0 \leq a_i \leq \sqrt{n}$.

Can we prove that the sum of squares of these numbers it not greater than $n\sqrt{n}$? Formally, we want to prove that \begin{equation*} \sum\limits_{i=1}^{k}a_i^2\leq n\sqrt{n}. \end{equation*}

---

What I can prove is that this sum is less than $4n(\sqrt{n}+1)$. The proof goes as follows:

• First we split our numbers into $d$ groups such that each of the numbers belongs to exactly one group and the sum of numbers in each of the groups is within $\Big[\sqrt{n}, \,\, 2\sqrt{n}\Big)$ except for one. We can do this by creating an empty group and inserting there numbers that don't belong to a group yet as long as the sum of the numbers in the group is less than $\sqrt{n}$. Then we create a next empty group and repeat the process as long as there are numbers that don't belong to any group. Because the numbers are not greater than $\sqrt{n}$, the sum of any group will always be less than $2\sqrt{n}$. A small subtlety here is that the sum of the numbers in the last group may be less than $\sqrt{n}$, but all the other groups will have their sum within $\Big[\sqrt{n}, \,\, 2\sqrt{n}\Big)$.
• Next we notice that $d$, the number of groups, is not greater than $\sqrt{n} + 1$. Why? The sum of numbers in each of the groups except for one is at least $\sqrt{n}$ and the sum of $a_1+a_2+\dots+a_k$ is $n$, which means that there is no more than $\sqrt{n}$ groups, excluding the one that may not follow our condition of the sum of its numbers being within $\Big[\sqrt{n}, \,\, 2\sqrt{n}\Big)$. If we include this remaining group we get that the number of our groups is indeed not greater than $\sqrt{n}+1$.
• Now we will use the fact the fact that for any sequence of positive real numbers the sum of squares of its elements is less or equal than the square of the sum of the elements. Then we have \begin{equation*} \quad \quad \quad \sum\limits_{i=1}^{k}a_i^2=\sum\limits_{i=1}^{d}\sum\limits_{x\in X_i}x^2\leq\sum\limits_{i=1}^{d}\Big(\sum\limits_{x\in X_i}x\Big)^2<d(2\sqrt{n})^2\leq(\sqrt{n}+1)4n, \end{equation*} where $X_i$ denotes the set of numbers that belong to the $i$-th group and the second inequality comes from the fact that the sum of numbers in each of the groups is less than $2\sqrt{n}$.

For me, intuitively it seems that this bound could be lowered to $n\sqrt{n}$, but unfortunately I can't prove it. Maybe someone will be able to help. I'd appreciate that a lot. Thanks in advance.

Answer 1

Hints towards a solution. If you're stuck, explain what you've tried.

1. Show that if $ a_i \geq a_j$ and $\epsilon > 0$, we have $(a_i + \epsilon)^2 + (a_j - \epsilon)^2 > a_i ^2 + a_j^2$.

2. At the maximum (independent of $\sum a_i$) , we must have

   • At most one value that is strictly between 0 and $\sqrt{n}$. If we had multiple values, we could increase the sum per point 1.

   • Several (possibly 0) values that equal to the maximum, which is $\sqrt{n}$.

   • Several (possibly 0) values that equal to the minimum, which is 0.

3. Since $\sum a_i = n$, thus at the maximum, we have

   • $\lfloor \sqrt{n} \rfloor$ values equal to $ \sqrt{n}$
   • 1 value equal to $ n - \lfloor \sqrt{n} \rfloor \sqrt{n}$
   • $ n - \lfloor \sqrt{n} \rfloor - 1$ values equal to $0$.

4. Finally, show that at the maximum, $\sum a_i^2 \leq n \sqrt{n}$, with equality when $n$ is a perfect square.

   • It might be helpful to set $ k = \lfloor \sqrt{n} \rfloor, $ so $ k^2 \leq n < (k+1)^2$,

$ (n - k \sqrt{n} ) ^2 + kn \leq n\sqrt{n} \Leftrightarrow (n- k \sqrt{n} ) ^2 \leq n ( \sqrt{n} - k ) \Leftrightarrow n(\sqrt{n} - k )(\sqrt{n} - k - 1 ) \leq 0 $.

Notes

• If desired, you can find the maximum when $n$ is not a perfect square.
• Generalize this to arbitrary bound $ a_{\min} \leq a_i \leq a_{\max}$, and arbitrary sum $ S = \sum a_i $ (with the obvious bound of $ n a_{\min} \leq S \leq n a_{\max}$).

Answer 2

We may have a simpler approach. We have $$a_i(a_i-\sqrt{n})\le 0 \hspace{1cm} \text{for all } i =1,...,k$$ Then $$\sum_{i=1}^k a_i(a_i-\sqrt{n})\le 0 $$ or $$\sum_{i=1}^k a_i^2 \le \sqrt{n}\sum_{i=1}^k a_i = n\sqrt{n}$$ The equality occurs if and only if $a_i = 0$ or $a_i =\sqrt{n}$ for all $i$. That mean, if there exists an $m\in \mathbb{N}$ such that $$m\sqrt{n} = n \iff n=m^2$$ In that case (where $n$ is a square number), the equality exists with, for example, $a_1=...=a_m=\sqrt{n}$ and $a_{m+1}=..=a_n =0$.

Otherwise, when $n$ is not a square number, there is no equality.

Q.E.D