# Lower bound for $\sum{a_ib_i}$

Assume that $\sum_{i=1}^na_i=1$ and $\sum_{i=1}^nb_i=1$, and $0 \le a_i, b_i \le 1$ for $i=1,\ldots,n$. Can we prove the following lower bound:

$$\frac{1}{n} \le \sum_{i=1}^n{a_ib_i} \,.$$

PS: If $b_i$s do not depend on $a_i$s, then we can easily take derivatives of the right-hand side with respect to $a_i$s, and solve the system to get:

$$b_1=\cdots=b_n = \frac{1}{n} \,.$$

From there, we see that the minimum value of $\sum_{i=1}^n{a_ib_i}$ is $\frac{1}{n}$.

• A counterexample: $b_1 = b_2 = \cdots = b_{n-1} = 0$, $b_n = 1$ and $a_1 = 1$, $a_2 = a_3 = \cdots = a_n = 0$. – PSPACEhard Apr 2 '17 at 15:51
• Or for strictly positive values: $a_1=a_2=\ldots=a_{n-1}=b_2=b_3=\ldots=b_n=\epsilon>0$, $a_n=b_1=1-(n-1)\epsilon$. Then $\sum_i a_i = \sum_i b_i = 1$ and $\sum_i a_i b_i = 2\epsilon - n\epsilon^2$, which can be made arbitrary small. – celtschk Apr 2 '17 at 15:59

We can easily reach $0$ by settings $a_1 := 1,\ a_i := 0\ \forall i > 1$ and $b_1 := 0, \ b_2 = 1,\ \ b_i := 0\ \forall i > 2$. Since all terms must be non-negative, this is an actual lower bound.
Also using Cauchy-Schwarz and the fact that $0 \leq a_i, b_i \leq 1$ : $$\sum_{i=1}^n a_ib_i \leq \left(\sum_{i=1}^n a_i^2\right)^{1/2}\left(\sum_{i=1}^n b_i^2\right)^{1/2} \leq \left(\sum_{i=1}^n a_i\right)^{1/2}\left(\sum_{i=1}^n b_i\right)^{1/2} = 1$$ Where the bound can be reached with $a_1 = b_1 = 1, \ a_i = b_i = 0\ \forall i>1$. Overall we have $$0 \leq \sum_{i=1}^n a_ib_i \leq 1$$
You solution is a saddle stationary point, rather than either a minimum or a maximum. You can easily see this by the simply example of $n=2$. That is the very pitfall of using only the first order condition. If you want to use the Lagrangian equation, you have to check the solution is indeed a minimum or maximum by, say, checking the convexity or concavity of the function under the constraint.