# Maximum of $(1-q_1)(1-q_2)\ldots(1-q_n)$

I'm trying to find the maximum of $(1-q_1)(1-q_2)\ldots(1-q_n)$ where $n\ge 2$, on a the set $\{(q_1,\ldots , q_n) :q_1^2+q_2^2+\ldots+q_n^2=1 \ q_i\ge 0 \}$ (With the condition $q_i\ge0$ this is just the upper half of the sphere). This appeared to be a simple Lagrange multipliers question but calculating the derivative is becoming a problem. How is this done?

I was thinking of trying the fact that the product is the volume of a box having $(1,1\ldots 1)$ and $(q_1,\ldots ,q_n)$ at its diagonal but I can't figure out how to continue.(I'm guessing this reduces the problem to something geometrical)

Updates: Empirical evidence suggests that the maximum is when the $q_i$ are equal as pointed out by @Sabyasachi , I let WolframAlpha solve the Laplace multiplier equations for $n=2,3,4$ and got the same result(that they are equal). One solution which does not turn up in WA's solutions is that $q_3=0$ and $q_1=q_2=\frac {1} {\sqrt{2}}$ which is on the sphere and returns a larger value.

• Taking $q_1=q_2=\ldots=q_n$, we get maximum $\left(\frac{\sqrt{n}-1}{\sqrt{n}}\right)^n$. Try to justify the equality via symmetry.
– Guy
Mar 22, 2014 at 12:55
• @Sabyasachi Can you elaborate? Mar 22, 2014 at 13:31
• You can always prove that the symmetry point has to be an extremal point (imagine even functions at x=0). However, there could technically be other extrema. In this case, it seems that everything is monotonous enough to prevent this, but I wouldn't know how to prove it. Mar 22, 2014 at 13:39
• @Sabyasachi The maximum is $\frac12 \left(3-2 \sqrt2\right)$, obtained when all but two of the $q_i$ are $0$. Will work on a proof shortly if no one else does it by then... Mar 22, 2014 at 14:49
• @Sabyasachi The formula you give seems to be working(Here is for n=3) , I'm failing in proving it. Every time I increase the dimension the cases which appear in the equations increase exponentially. Mar 22, 2014 at 19:57

Here is a complete answer. The computations are rather long but every step is natural. Perhaps someone else can simplify the computational part of the proof.

We will show that the maximum is $M=\frac{3}{2}-\sqrt{2}$ independently of $n$, just as claimed in Macavity's comments. Let $\phi(x)=1-\sqrt{x}$ for $x\in [0,1]$. The inequality to be shown can then be restated as :

$$\phi(x_1)\phi(x_2)\ldots \phi(x_n)\leq M, \ \text{whenever} \ x_i\geq 0, \ x_1+x_2+x_3+\ldots +x_n=1. \tag{1}$$

To show such an inequality, one of the first ideas that comes to mind is to try to show that $\phi$ satisfies properties like $\phi(x)\phi(y) \leq \phi(x+y)$ or $\phi(x+y)\leq (\phi(\frac{x+y}{2}))^2$. Unfortunately, both those are false (take $x=\frac{1}{6},y=\frac{1}{3}$). We must use a slightly corrected version of $\phi$ : let

$$\psi(t)=\left\lbrace\begin{array}{lcl} \phi(t), & \rm{if} & t\leq \alpha, \\ \phi\big(\frac{t}{2}\big)^2, & \rm{if} & t\geq \alpha, \\ \end{array}\right.\tag{2}$$

where $\alpha=4(3-2\sqrt{2})$ is the unique solution of $\phi(t)=\phi(\frac{t}{2})^2$ in $(0,1)$.

Lemma 1. $\phi \leq \psi$ on $[0,1]$.

Lemma 2. $\psi$ satisfies $\psi(x)\psi(y) \leq \psi(x+y)$, for any $x,y\in [0,1]$ with $x+y \leq 1$.

Lemmas 1 and 2 yield $$\phi(x_1)\phi(x_2)\ldots \phi(x_n) \leq \psi(x_1)\psi(x_2)\ldots \psi(x_n) \leq \psi(x_1+x_2+x_3+\ldots +x_n) =\psi(1)=M \tag{3}$$

as wished. It will therefore suffice to show those two lemmas. This we do below.

Proof of lemma 1. We must show $\phi(t) \leq \psi(t)$ for $t\in [0,1]$. Clearly, we may assume that $t\geq\alpha$. But then

$$\psi(t)-\phi(t)=\frac{\sqrt{t}}{2}(\sqrt{t}-\sqrt{\alpha}) \geq 0.$$

Proof of lemma 2. We must show $\psi(x)\psi(y) \leq \psi(x+y)$ for $x,y\in [0,1]$.

First case : $x+y\leq \alpha$.

We then have to show that $$(1-\sqrt{x})(1-\sqrt{y})\leq 1-\sqrt{x+y} \tag{4}$$

Putting $a=\sqrt{x},b=\sqrt{y}$, this is equivalent to

$$\begin{array}{cl} & (1-a)(1-b)\leq 1-\sqrt{a^2+b^2} \\ \Leftrightarrow & ab+\sqrt{a^2+b^2} \leq a+b \\ \Leftrightarrow & a^2b^2+a^2+b^2+2ab\sqrt{a^2+b^2} \leq a^2+b^2+2ab \\ \Leftrightarrow & a^2b^2+2ab\sqrt{a^2+b^2} \leq 2ab \\ \Leftrightarrow & ab+2\sqrt{a^2+b^2} \leq 2 \\ \end{array}$$

Now, from the hypotheses we have $a^2+b^2 \leq \alpha$, so

$$ab+2\sqrt{a^2+b^2} \leq \frac{a^2+b^2}{2}+2\sqrt{a^2+b^2} \leq \frac{\alpha}{2}+2\sqrt{\alpha}=6-4\sqrt{2}+4\sqrt{2}-4=2 \tag{5}$$

Second case : $x\leq \alpha, y\leq \alpha, x+y > \alpha$.

We then have to show that $$(1-\sqrt{x})(1-\sqrt{y})\leq \bigg(1-\sqrt{\frac{x+y}{2}}\bigg)^2 \tag{6}$$

Putting $a=\sqrt{x},b=\sqrt{y}$, this is equivalent to

$$\begin{array}{cl} & (1-a)(1-b)\leq \bigg(1-\frac{\sqrt{a^2+b^2}}{2}\bigg)^2 \\ \Leftrightarrow & \sqrt{2(a^2+b^2)} \leq a+b+\frac{a^2+b^2}{2}-ab \\ & \\ \Leftrightarrow & 2(a^2+b^2) \leq \frac{a^4+b^4}{4}-(a^3b+ab^3)-(a^2b+ab^2)+(a^3+b^3)+ \frac{3a^2b^2}{2} +a^2+b^2-2ab \\ & \\ \Leftrightarrow & 0 \leq \frac{a^4+b^4}{4}-(a^3b+ab^3)-(a^2b+ab^2)+(a^3+b^3)+ \frac{3a^2b^2}{2} -a^2-b^2-2ab \\ \Leftrightarrow & 0 \leq \frac{(b-a)^2}{4}(a^2+b^2+4(a+b)-2ab-4) \\ \Leftrightarrow & 0 \leq a^2+b^2+4(a+b)-2ab-4 \\ \Leftarrow & 0 \leq \alpha+4(a+b)-2ab-4 \\ \Leftrightarrow & 0 \leq 4(a+b)-2ab-4\sqrt{\alpha} \ ({\rm since} \ \alpha-4=-4\sqrt{\alpha})\\ \Leftrightarrow & 2(\sqrt{\alpha}-a) \leq b(2-a) \\ \Leftrightarrow & 4(\sqrt{\alpha}-a)^2 \leq b^2(2-a)^2 \\ \Leftarrow & 4(\sqrt{\alpha}-a)^2 \leq (\alpha-a^2)(2-a)^2 \\ \Leftrightarrow & 4(\sqrt{\alpha}-a) \leq (\sqrt{\alpha}+a)(2-a)^2 \\ \end{array}$$

The last inequality is true because

$$(\sqrt{\alpha}+a)(2-a)^2-4(\sqrt{\alpha}-a)=a(16(1-\sqrt{\alpha})+(\sqrt{\alpha}-a)(\alpha+2\sqrt{\alpha}-a)) \tag{7}$$

\newpage

Third case : One of $x,y$ is smaller than $\alpha$, the other is larger.

We can assume $x \leq \alpha \leq y \leq 1-x$. Notice that $x\leq 1-\alpha$. We then have to show that $$(1-\sqrt{x})\bigg(1-\sqrt{\frac{y}{2}}\bigg)^2\leq \bigg(1-\sqrt{\frac{x+y}{2}}\bigg)^2 \tag{8}$$

To this end, let us put $F_1(y)=\frac{1-\sqrt{\frac{x+y}{2}}}{1-\sqrt{\frac{y}{2}}}$ for $y\in [\alpha,1-x]$. A little computation shows that

$${F'}_1(y)=\frac{F_2(y)}{\sqrt{y(x+y)}\bigg(1-\sqrt{\frac{y}{2}}\bigg)^2}, \ F_2(y)=\sqrt{x+y}-\sqrt{y}-\frac{x}{\sqrt{2}} \tag{9}$$

Note that ${F'}_2(y)=\frac{1}{2\sqrt{x+y}}-\frac{1}{2\sqrt{y}} \leq 0$ so $F_2$ is decreasing, and hence $F_2(y)\leq F_2(\alpha)=F_3(x)$ where $F_3(x)=\sqrt{x+\alpha}-\frac{x}{\sqrt{2}}-\sqrt{\alpha}$. Note that ${F'}_3(y)=\frac{1}{2\sqrt{x+\alpha}}-\frac{1}{\sqrt{2}} \leq 0$ and $2\sqrt{x+\alpha} \geq 2\sqrt{\alpha} > 1.5 > \sqrt{2}$, so $F_3$ is decreasing, and hence $F_3(x) \leq F_3(0)=0$. We see now that $F_2(y) \leq 0$, so $F_1$ is decreasing, and hence $F_1(y)\geq F_1(1-x)$. So in the proof of (8), we can assume that $y=1-x$ : all we need to show is

$$(1-\sqrt{x})\bigg(1-\sqrt{\frac{1-x}{2}}\bigg)^2\leq \bigg(1-\sqrt{\frac{1}{2}}\bigg)^2 \tag{10}$$

Putting $a=\sqrt{x}$, this is equivalent to

$$\begin{array}{cl} & (1-a)\bigg(1-\sqrt{\frac{1-a^2}{2}}\bigg)^2\leq \frac{3}{2}-\sqrt{2} \\ \Leftrightarrow &(1-a)\bigg(1-\sqrt{2(1-a^2)}+\frac{1-a^2}{2}\bigg)\leq \frac{3}{2}-\sqrt{2} \\ & \\ \Leftrightarrow & (1-a)\bigg(1+\frac{1-a^2}{2}\bigg)-(\frac{3}{2}-\sqrt{2})\leq (1-a)\sqrt{2(1-a^2)} \\ \Leftrightarrow & \frac{a^3-a^2-3a}{2}+\sqrt{2}\leq (1-a)\sqrt{2(1-a^2)} \\ \Leftarrow & \bigg(\frac{a^3-a^2-3a}{2}-\sqrt{2}\bigg)^2\leq (1-a)^22(1-a^2) \\ \end{array}$$

The last inequality is true because $a\leq\sqrt{1-\alpha} \leq 0.6=\frac{3}{5}$ and

$$\begin{array}{cl} & 2(1-a)^2(1-a^2)-\bigg(\frac{a^3-a^2-3a}{2}-\sqrt{2}\bigg)^2 \\ =& \frac{a}{4}(-a^5+2a^4 - 3a^3 + (10-4\sqrt{2})a^2 + (4\sqrt{2} - 9)a + (12\sqrt{2}- 16)) \\ \geq& \frac{a}{4}(-a^5+2a^4 - 3a^3 +\frac{108}{25}a^2 + -\frac{84}{25}a + \frac{24}{25} \end{array} \tag{11}$$

Fourth case : Both $x$ and $y$ are larger than $\alpha$.

We then have to show that $$\bigg(1-\sqrt{\frac{x}{2}}\bigg)^2\bigg(1-\sqrt{\frac{y}{2}}\bigg)^2\leq \bigg(1-\sqrt{\frac{x+y}{2}}\bigg)^2 \tag{12}$$

But this is simply inequality (4) of the first case, used with $(\frac{x}{2},\frac{y}{2})$ in place of $(x,y)$. And this is all OK since $\frac{x}{2}$ and $\frac{y}{2}$ are both $\leq \frac{1}{2} \leq \alpha$, so we only need to reuse our already treated first case. This concludes the proof.

• I was able to follow the argument I just didn't get why the inequality becomes $\phi(x_1)\phi(x_2)\ldots \phi(x_n)\leq M$. Btw: Amazing answer!!! Mar 23, 2014 at 18:14
• @user63697 Put $x_i=q_i^2$ Mar 23, 2014 at 18:16
• Well that was dumb of me, I will try to work on refining the calculations. Thank you. Mar 23, 2014 at 18:19

${\bf 1\ }$ We begin with the following two-dimensional problem: Maximize $$f(q_1,q_2):=(1-q_1)(1-q_2)$$ under the constraints $$q_1^2+q_2^2=r^2, \quad q_1\geq0, \ q_2\geq0\ .$$ Here $r$ is a parameter, $0<r\leq1$. Analyzing the graphs of the functions $$g_r(t):=(1-r\cos t)(1-r\sin t)\qquad(0\leq t\leq{\pi\over2})$$ we find the following (see the figure):

(a) When $r<\rho:=2(\sqrt{2}-1)$ then $$q_1q_2>0\quad\Rightarrow\quad f(q_1,q_2)<f(r,0)\ .$$ (b) When $r>\rho$ then $$q_1\ne q_2\quad\Rightarrow\quad f(q_1,q_2)<f\left({r\over\sqrt{2}},{r\over\sqrt{2}}\right)\ .$$ ${\bf 2\ }$ Now let $n\geq2$ be arbitrary and assume that $q=(q_1,q_2,\ldots,q_n)$ is an admissible point where $f$ assumes its maximum. Put $$\tau:={1\over2}\rho^2\doteq0.343>{1\over3}\ .$$ In the light of ${\bf 1}$ there can be at most one $i$ with $0<q_i^2<\tau$, and as $\tau>{1\over3}$ there can be at most two $i$ with $q_i^2\geq\tau$. All other $q_i$ have to be zero.

${\bf 3\ }$ When $0<q_1^2<\tau\leq q_2^2\leq q_3^2$ then $$q_1^2+q_2^2=1-q_3^2\leq 1-\tau<2\tau=\rho^2\ .$$ From ${\bf 1}$(a) we then conclude that $q$ cannot be a maximum point.

${\bf 4\ }$ When only $q_1^2$ and $q_2^2$ are $>0$ then ${\bf 1}$(b) with $r=1$ tells us that we have $q_1=q_2={1\over\sqrt{2}}$, and this leads to the maximal value $$\max f=\left(1-{1\over\sqrt{2}}\right)^2={1\over2}(3-2\sqrt{2})\doteq0.0858\ .$$

Addendum: I've included the full set of solutions Mathematica finds for the case $n=3$ at the end of this answer.

The comments and answers so far don't show how Lagrange multipliers can solve the problem (because of the non-negativity condition). Here's how that technique can be used.

To maximize a function $f(q_1,\dots, q_n)$ with the requirement that $q_i\ge0$ and an additional constraint $c(q_1,\dots, q_n)=0$, it suffices to maximize the function $f(s_1^2,\dots, s_n^2)$ subject to the constraint $c(s_1^2,\dots, s_n^2)=0$, then choose those solutions with all $s_i$ real that give the largest value of $f$. For these, $(s_1^2,\dots, s_n^2)$ is a non-negative solution to the original constrained maximization question.

For this particular question, then, maximize $\prod(1-s_i^2)$ subject to $\sum s_i^4=1$.

Here’s the three-variable case, where we need to maximize $(1-a)(1-b)(1-c)$ for $a,b,c\ge0$, subject to $a^2+b^2+c^2=1$.

Maximize $(1-x^2)(1-y^2)(1-z^2)$ subject to $x^4+y^4+z^4=1$. Using Lagrange multipliers, let $g(x,y,z,\lambda)=(1-x^2)(1-y^2)(1-z^2)-\lambda(x^4+y^4+z^4-1)$, and solve the following system of equations over the real numbers:

\begin{align} 0 = \frac{\partial f}{\partial x} = & -2x(1-y^2)(1-z^2)+4x^3\lambda\\ 0 = \frac{\partial f}{\partial y} = & -2y(1-x^2)(1-z^2)+4y^3\lambda\\ 0 = \frac{\partial f}{\partial z} = & -2z(1-x^2)(1-y^2)+4z^3\lambda\\ 0 = \frac{\partial f}{\partial \lambda} = & x^4+y^4+z^4-1\\ \end{align}

When a solution $(x,y,z,\lambda)$ of this system gives a maximum among all real solutions, $(x^2,y^2, z^2)$ is a solution to the original question.

The system is no fun to solve, and I didn't try to generalize to see if it gives a nice answer the original question in general. In theory it will, but whether it's any simpler than the other answers, I don't know.

Here are all of Mathematica’s real solutions to the system above, written in terms of $a=x^2,b=y^2,c=z^2$.

$\begin{array}{llll} (a,b,c) & (1-a)(1-b)(1-c)\\ \hline\\ \left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0\right) & \left(1-\frac{1}{\sqrt{2}}\right)^2 \\ \left(\frac{1}{\sqrt{2}} , 0 , \frac{1}{\sqrt{2}}\right) & \left(1-\frac{1}{\sqrt{2}}\right)^2 \\ \left(0 , \frac{1}{\sqrt{2}} , \frac{1}{\sqrt{2}} \right)& \left(1-\frac{1}{\sqrt{2}}\right)^2 \\ \left(\frac{1}{\sqrt{3}} , \frac{1}{\sqrt{3}} , \frac{1}{\sqrt{3}} \right)& \left(1-\frac{1}{\sqrt{3}}\right) ^3 \\ \left(\frac{2}{3}, \frac{2}{3} , \frac{1}{3} \right)& \frac{2}{27} \\ \left(\frac{2}{3} , \frac{1}{3} , \frac{2}{3} \right)& \frac{2}{27} \\ \left(\frac{1}{3} , \frac{2}{3} , \frac{2}{3} \right)& \frac{2}{27} \\ (1 , 0 , 0) & 0 \\ (0 , 1 , 0) & 0 \\ (0 , 0 , 1) & 0 \\ \end{array}$

• I appreciate your effort, but I wish you went through the comments. We had WolframAlpha solve these systems for n=3 and obtained that they must be equal, however asking wolfram to maximize the function gave another answer. I'm sorry but your answer doesn't put anything new on the table. And the last equation needs a $-1$ Mar 23, 2014 at 14:14
• I did go through the comments, and I also ran my equations through Mathematica. They definitely give the correct solution (two non-zero values). Of course Mathematica also gives the all-equal solutions, because the are among the relative extrema, but they aren’t where the maxima are. I've included a screenshot of the Mathematica output showing $\{a,b,c,\mbox{objective}\}$ for all real solutions of the Lagrange multiplier equations in descending order of the value of the objective. Note that the objective is maximized when two of $a,b,c$ are non-zero, as expected. i.imgur.com/ggc0pUs.png Mar 23, 2014 at 15:39
• That is rather interesting, how the case appears for these equations. What is left however is proving this works in general. Mar 23, 2014 at 15:44
• Now that you see this does add something to the table, please consider upvoting the answer. It will definitely “work” in general - the correct solution will always appear - since Lagrange multipliers is a valid technique when all the constraints are incorporated. Whether the solution for all $k$ can be deduced in a simple way from the system of equations, that I don't know. But this is definitely a general and valid way to solve the problem. Mar 23, 2014 at 15:55

If any of the $q_i$ are 1, then the product is zero.
Otherwise, take the logarithm, and try to maximize
$\log(1-q_1)+\log(1-q_2)+\ldots+\log(1-q_n)$

• I don't see how this can lead to any progress, and I believe that the last sign is wrong. Mar 23, 2014 at 2:20
• Yes, thanks for spotting the error. The derivative is simpler, you get $2\lambda q_i-1/(1-q_i)=0$ for every $i$ Mar 23, 2014 at 7:04
• This does give a simpler system, but still not a solvable one. Mar 23, 2014 at 9:29