3
$\begingroup$

Assume that we have $m$ real numbers $x_1,x_2,...,x_m\in[0,1/4]$ satisfying the following equations: $$ \sum_{i=1}^m x_i=a_1, \sum_{i=1}^mx_i^2=a_2,\sum_{i=1}^mx_i^3\geq a_3,$$ where $a_1,a_2,a_3$ are all positive. The aim is to obtain restrictions on $a_1,a_2,a_3$. We can consider the polynomial $$f_b(x)=(x-1/4)(x+b)^2=x^3+(2b-1/4)x^2+(b^2-b/2)x-(1/4)b^2$$ where $b\in\mathbb{R}$. Then $$0\geq \sum_{i=1}^m f_b(x_i)\geq a_3+(2b-1/4)a_2+(b^2-b/2)a_1-(1/4)b^2m,$$ where the right hand side can be seen as a quadratic polynomial in variable $b$ and it is always less than or equal to 0. This will give us a restriction on $a_1,a_2,a_3$. I wonder whether there are other restrictions on $a_1,a_2,a_3$?

$\endgroup$
  • $\begingroup$ Do you mean $\sum_{i=1}^m x_i^3\ge a_3$ instead of $\sum_{i=3}^m x_i^3\ge a_3$? If yes, do you mean $\sum_{i=1}^m x_i^3 = a_3$ instead of $\sum_{i13}^m x_i^3 \ge a_3$? $\endgroup$ – Markus Schweighofer May 27 '18 at 22:04
  • $\begingroup$ Thank you for pointing that out. It should be $\sum_{i=1}^m x_i^3\geq a_3$. $\endgroup$ – Sihuang Hu May 28 '18 at 12:17
  • $\begingroup$ Then $a_3$ may be equal to 0, and we do not have $a_2^2\le a_1a_3$. $\endgroup$ – Fedor Petrov May 28 '18 at 12:26
  • $\begingroup$ @FedorPetrov you are right. The argument $a_2^2\leq a_1a_3$ is a stupid mistake. Why $a_3$ may be equal to $0$? $\endgroup$ – Sihuang Hu May 28 '18 at 12:33
  • $\begingroup$ @SihuangHu why not? $a_3=0$ always satisfies your restriction. $\endgroup$ – Fedor Petrov May 28 '18 at 12:37
1
$\begingroup$

This is a partial answer. If it is correct, I can proceed.

Let $m \ge 3$ be a fixed positive integer. Let $\lfloor x\rfloor$ be the greatest integer less than or equal to $x$.

First, let us prove the following lemma.

Lemma 1: There exists $x_1, x_2, \cdots, x_m \in [0, \frac{1}{4}]$, not all zero, such that $x_1 + x_2 + \cdots + x_m = a_1, \ x_1^2 + x_2^2 + \cdots + x_m^2 = a_2$ and $x_1^3+x_2^3 + \cdots + x_m^3 \ge a_3$,

if and only if, \begin{equation} 0 < a_1 \le \frac{m}{4}, \qquad\qquad\qquad\qquad\qquad\qquad\qquad (1) \end{equation} \begin{equation} \frac{a_1^2}{m} \le a_2 \le \frac{1}{16}\lfloor 4a_1\rfloor + \left(a_1 - \frac{1}{4}\lfloor 4a_1\rfloor\right)^2, \qquad (2) \end{equation} and \begin{align} a_3 \le F(a_1, a_2),\qquad\qquad\qquad\qquad\qquad\qquad\quad (3) \end{align} where \begin{align} F(a_1, a_2) = &\max_{x_1, x_2, \cdots, x_m} \ x_1^3 + x_2^3 + \cdots + x_m^3\qquad\qquad\qquad\qquad\quad (4)\\ &\mathrm{s.t.}\quad x_i\in [0, \frac{1}{4}], \forall i; \ x_1 + x_2 + \cdots + x_m = a_1, \ x_1^2 + x_2^2 + \cdots + x_m^2 = a_2.\nonumber \end{align}

Proof of Lemma 1: WLOG, assume that $x_1 \ge x_2\ge \cdots \ge x_m$.

(the "only if" part):

i) Clearly, $0 < a_1 \le \frac{m}{4}$.

ii) Given $0 < a_1 \le \frac{m}{4}$, the range of $a_2$ is $[g(a_1), f(a_1)]$ where \begin{align*} f(a_1) = &\max_{x_1, x_2, \cdots, x_m} \ x_1^2 + x_2^2 + \cdots + x_m^2\\ &\mathrm{s.t.}\quad x_i\in [0, \frac{1}{4}], \forall i; \ x_1 + x_2 + \cdots + x_m = a_1 \end{align*} and \begin{align*} g(a_1) = &\min_{x_1, x_2, \cdots, x_m} \ x_1^2 + x_2^2 + \cdots + x_m^2\\ &\mathrm{s.t.}\quad x_i\in [0, \frac{1}{4}], \forall i; \ x_1 + x_2 + \cdots + x_m = a_1. \end{align*} It is easy to obtain $g(a_1) = \frac{a_1^2}{m}$ (the minimum is attained always when $x_1=x_2 = \cdots = x_m = \frac{a_1}{m}\in [0, \frac{1}{4}]$).

We have $f(a_1) = \frac{1}{16}\lfloor 4a_1\rfloor + \left(a_1 - \frac{1}{4}\lfloor 4a_1\rfloor\right)^2$ since $h(x) = x_1^2 + x_2^2 + \cdots + x_n^2$ is convex, and (denote $K = \lfloor 4a_1\rfloor$)

$\big(\underbrace{\frac{1}{4}, \frac{1}{4}, \cdots, \frac{1}{4}}_{K}, a_1 - \frac{1}{4}K, 0, 0, \cdots, 0\big)$ majorizes $(x_1, x_2, \cdots, x_m)$ with $x_i\in [0, \frac{1}{4}], \forall i; \ x_1 + x_2 + \cdots + x_m = a_1$.

iii) Clearly, (3) is true.

(the "if" part): It is clear according to the (the "only if" part). This completes the proof of Lemma 1.

Let us proceed. We want to find the explicit expression of $F(a_1, a_2)$.

Let $(x_1, \ x_2, \cdots, x_m)$ be the global maximizer of the optimization problem given in (4). We claim that $|\{x_1, \ x_2, \cdots, x_m\}|\le 4$ where $|\cdot|$ is the cardinality of a set.

Proof of the claim: Assume, for the sake of contradiction, that $|\{x_1, \ x_2, \cdots, x_m\}| > 4$. WLOG, assume that $0 < x_1 < x_2 < x_3 < \frac{1}{4}.$ Denote $D = 16(x_1^2+x_2^2+x_3^2) - 32(x_1x_2 + x_1x_3 + x_2x_3) + 8(x_1+x_2+x_3) -3.$

Remark: The proof of the inequalities in this part is simple and thus omitted.

1) If $D\le 0$, let $$a = \frac{x_1+x_2+x_3}{3}-\frac{1}{3}\sqrt{x_1^2+x_2^2+x_3^2-x_1x_2-x_1x_3-x_2x_3}\, ,$$ $$b = \frac{x_1+x_2+x_3}{3}+\frac{2}{3}\sqrt{x_1^2+x_2^2+x_3^2-x_1x_2-x_1x_3-x_2x_3}\, .$$ We have $x_1+x_2+x_3 = a + a + b, \ x_1^2+x_2^2+x_3^2 = a^2 + a^2 + b^2$ and $0 \le a \le b\le \frac{1}{4}$. Thus, $(a, a, b, x_4, x_5, \cdots, x_m)$ is a feasible point of the optimization problem given in (4). We also have $a^3 + a^3 + b^3 > (x_1^3 + x_2^3 + x_3^2) \Longleftarrow (x_2-x_3)^2(x_1-x_3)^2(x_1-x_2)^2 > 0.$ Thus, we have $a^3 + a^3 + b^3 + x_4^3 + x_5^3 + \cdots + x_m^3 > x_1^3 + x_2^3 + x_3^3 + x_4^3 + x_5^3 + \cdots + x_m^3.$ Thus, $(a, a, b, x_4, x_5, \cdots, x_m)$ is strictly better than $(x_1, \ x_2, \cdots, x_m)$. This contradicts the optimality of $(x_1, \ x_2, \cdots, x_m)$.

2) If $D > 0$, let $$u = \frac{x_1+x_2+x_3}{2} - \frac{1}{8} + \frac{1}{8}\sqrt{D}\,,$$ $$v = \frac{x_1+x_2+x_3}{2} - \frac{1}{8} - \frac{1}{8}\sqrt{D}\,.$$ We have $x_1 + x_2 + x_3 = \frac{1}{4} + u + v, \ x_1^2+x_2^2+x_3^2 = (\frac{1}{4})^2 + u^2 + v^2.$ It follows from $D>0$ and $0 < x_1 < x_2 < x_3 < \frac{1}{4}$ that $$x_1+x_2+x_3\ge \frac{1}{4},$$ $$x_1^2+x_2^2+x_3^2 \ge \frac{1}{16},$$ $$16(x_1x_2+x_1x_3+x_2x_3) - 4(x_1+x_2+x_3) + 1\ge 0,$$ $$16(x_1x_2 + x_1x_3 + x_2x_3) - 8(x_1+x_2+x_3) + 3 > 0,$$ $$-192x_1x_2x_3 + 48(x_1x_2+x_1x_3+x_2x_3) - 12(x_1+x_2+x_3) + 3 > 0.$$ With these facts, we have $0 \le v \le u \le \frac{1}{4}$ and $(\frac{1}{4})^3 + u^3 + v^3 > x_1^3 + x_2^3 + x_3^3.$ Thus, $(\frac{1}{4}, u, v, x_4, x_5, \cdots, x_m)$ is a feasible point of the optimization problem given in (4) and is strictly better than $(x_1, \ x_2, \cdots, x_m)$. This contradicts the optimality of $(x_1, \ x_2, \cdots, x_m)$. This completes the proof of the claim.

$\endgroup$
  • $\begingroup$ I agree with Lemma 1. Could you please explain how do you apply the KKT condition and get the conclusion that $|\{x_1, x_2, \cdots, x_m\}|\le 4$? $\endgroup$ – Sihuang Hu Jun 14 '19 at 8:29
  • $\begingroup$ I updated my answer. I proved it without the KKT conditions. $\endgroup$ – River Li Jun 15 '19 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.