4
$\begingroup$

Let $n<d$ be positive integers, and let $0< \epsilon\leq 1-\frac{n}{d}$ be a real number. I would like a succinct description of the following quantity:

$$ f_{\epsilon}(n,d):=\min_{\substack{x_1\geq \dots \geq x_d\geq 0\\ x_1+\dots+x_n =1-\epsilon\\ x_{n+1}+\dots+x_d=\epsilon}} \left(\sum_{1 \leq i_1 < \dots < i_{n+1} \leq d} x_{i_1}\cdots x_{i_{n+1}}\right). $$ In the absence of such a description, I would be interested in good lower/upper bounds on this quantity.

(I wasn't sure what tags to use.)

The assumption $\epsilon\leq 1-\frac{n}{d}$ ensures that the function is defined.

$\endgroup$
2
  • 2
    $\begingroup$ The function is defined only for $\frac{1-\epsilon}n\geq \frac{\epsilon}{d-n}$, that is, $\epsilon \leq 1-\frac{n}{d}$. $\endgroup$ Mar 28, 2022 at 14:33
  • $\begingroup$ @MaxAlekseyev Yes! Thanks (I should have noticed this). I have changed the range of $\epsilon$ in my question. $\endgroup$
    – Ben
    Mar 28, 2022 at 15:40

1 Answer 1

3
$\begingroup$

Here is a succinct description of $f_{\epsilon}(n,d)$ (I only have time to sketch the argument-- hopefully it is right).

Let $$ h(x_1,\dots, x_d)=\left(\sum_{1 \leq i_1 < \dots < i_{n+1} \leq d} x_{i_1}\cdots x_{i_{n+1}}\right), $$ and let $x \in \mathbb{R}^d$ be a feasible element of the minimization (i.e., $x_1\geq \dots \geq x_d\geq 0, x_1+\dots+x_n=1-\epsilon$, and $x_{n+1}+\dots+x_d=\epsilon$).

For any $i<j \in \{n+1,\dots, d\}$, let

$$g(t)=h(x_1,\dots, x_{i-1},x_i+t,x_{i+1},\dots,x_{j-1},x_j-t, x_{j+1},\dots, x_d).$$

It is straightforward to verify that $g(t)$ is a quadratic function with negative second derivative. So $g(t)$ is minimized at an extreme point. It follows that $h(x)$ is minimized when $x_{r+1},\dots, x_n$ are as ``unbalanced" as possible. This implies that the minimum is attained for some $x \in \mathbb{R}^d$ for which $$ (x_{n+1},\dots, x_d)=\left(\frac{1-\epsilon}{n},\dots, \frac{1-\epsilon}{n},\epsilon-\frac{k(1-\epsilon)}{n},0,\dots,0\right), $$ where $\frac{1-\epsilon}{n}$ is repeated $k$ times in the tuple, and $$ k=\lfloor \frac{\epsilon n}{1-\epsilon} \rfloor. $$ We can do the same trick for the first $n$ coordinates of $x$, and prove that the minimum is attained for $x \in \mathbb{R}^d$ that satisfies $$ (x_1,\dots, x_n)=\begin{cases} (\frac{1-\epsilon}{n},\dots,\frac{1-\epsilon}{n}) ,& \epsilon \geq \frac{1-\epsilon}{n}\\ (1-n\epsilon,\epsilon,\dots, \epsilon) ,& \epsilon\leq \frac{1-\epsilon}{n}. \end{cases} $$

It follows that $$ f_\epsilon(n,d)=\begin{cases} \binom{n+k}{n+1} \left(\frac{1-\epsilon}{n}\right)^{n+1}+\binom{n+k}{n} \left(\frac{1-\epsilon}{n}\right)^n \left[\epsilon-k\left(\frac{1-\epsilon}{n}\right)\right] ,& \epsilon \geq \frac{1-\epsilon}{n}\\ (1-n\epsilon)\epsilon^n,& \epsilon\leq \frac{1-\epsilon}{n}. \end{cases} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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