I have a set of $n$ variables $(x_1,\ldots, x_n)$ satisfying $x_i < n$ and $\sum x_i < n^{3/2}$. I want to maximize: $$\sum\limits_{i,j, i \neq j} \sqrt{x_i^{1/3} x_j^{1/3} (x_i^{1/3} + x_j^{1/3})^2 (x_i^{5/3} + x_j^{5/3})}$$

Is there a systematic way to approach these kinds of problems? I am fine with having an asymptotic answer.

My best upper bound is $O(n^3)$ which we can get by seeing that the expression is $< \sum\limits_{i,j, i \neq j} max(x_i, x_j)^{3/2} < n(\sum_i x_i^{3/2}) < n(n^2) = n^3$

My current best way to maximize is to set $\sqrt{n}$ $x_i$'s to $n/2$ and the other $n-\sqrt{n}$ $x_i$'s to $\sqrt{n}/2$. This gives $O(n^{35/12})$. Is there a way to prove this is optimal upto constant/polylogarithmic factors?


The idea is that there are $2$ parts of the expression, one which maximizes at $x_i = x_j$ and one which maximizes at some $x_i = n$(max value) and other $x_i = 0$. This is why we need to set $\sqrt{n}$ $x_i$'s to $n/2$ and the other $n-\sqrt{n}$ $x_i$'s to $\sqrt{n}/2$ which gives $O(n^{35/12})$.

To prove this we will separate the expression into 2 parts and maximize them independently. Let $m_{i, j} = max(x_i, x_j)$. Then,

$\sum\limits_{i,j, i \neq j} \sqrt{x_i^{1/3} x_j^{1/3} (x_i^{1/3} + x_j^{1/3})^2 (x_i^{5/3} + x_j^{5/3})} = O(\sum\limits_{i,j, i \neq j} \sqrt{x_i^{1/3} x_j^{1/3} (m_{i, j}^{1/3})^2 (m_{i, j}^{5/3})}) = O(\sum\limits_{i,j, i \neq j} \sqrt{x_i^{8/3} x_j^{1/3}}) = O(\sum\limits_{i,j, i \neq j} x_i^{4/3} x_j^{1/6}) = O((\sum x_i^{4/3})(\sum x_i^{1/6})) = O((\sqrt{n}n^{4/3})(n\sqrt{n}^{1/12})) = O(n^{35/12})$.

$\sum x_i^{4/3}$ and $\sum x_i^{1/6}$ are the expressions we maximized independently.


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.