Minimizing $\frac{x_1+x_2}{1+x_1x_2}+\frac{x_2+x_3}{1+x_2x_3}+\dots+\frac{x_n+x_1}{1+x_nx_1}$ for non-negative $x_i$ satisfying $x_1+x_2+\dots+x_n=1$

Question

An "Olympiad type" inequality:

Let $x_1,x_2,\dots,x_n$ real numbers in $[0;+\infty)$ with $x_1+\dots+x_n=1$ and $$f(x_1,\dots,x_n)=\frac{x_1+x_2}{1+x_1x_2}+\frac{x_2+x_3}{1+x_2x_3}+\dots+\frac{x_n+x_1}{1+x_nx_1}$$ Find the minimum of $f$ under the given constraint.

It seems rather delicate to prove that $\frac95$ is the minimum for $n \geq 3$ apparently.

The problem comes from here, and as French member of the forum linked, I hope this problem will find a greater audience here, since it remains unsolved so far despite all unsuccessful attempts. Please do not submit any reasoning already rejected in the previous linked topic.

Thanks for your support.

Answer 1

Here is a complete solution proposal for the case $n\geq 4$. Sorry for the bad english.

The set of $(x_1,...,x_n)$ with non negative coefficients and sum $1$ is compact and the function $f$ considered is continuous, so we can fix $(a_1,...,a_n)$ a point where $f$ reaches its minimum.

Among all these points, we can consider one that has a maximal number of zeros in the list $(a_1,...,a_n)$.

Let us reason by contradiction and assume that this maximal number is less than or equal to $n-3$ and let $(a_1,...,a_n)$ be a associated point (which thus has at least three positive coefficients).

By circular permutation, we can assume without loss of generality that $a_1>0$ and $a_j>0$ for some $j\in [3,n-1]$.

We set $S = a_1+a_j$ and $g$ the function defined on $[0,S]$ by $g(x) = f(x,a_2,...,a_{j-1},S-x,a_{j+1},....,a_n)$.

There exists a constant $C$ independent of $x$ such that $g(x) = \dfrac{x+a_2}{1+a_2 x}+\dfrac{x+a_n}{1+a_n x} + \dfrac{a_{j-1}+S-x}{1+a_{j-1}(S-x)} + \dfrac{a_{j+1}+S-x}{1+a_{j+1}(S-x)}+C.$

Note that $j\in [3,n-1]$ allows $x$ and $S-x$ not to mix in the fractions.

For any $a\in [0,1]$, we set $h_a(x) = \dfrac{a+x}{1+ax}$ and we have $h_a''(x) = -\dfrac{2a(1-a^2)}{(1+ax)^3}\leq 0$, so each function $h_a$ is concave on $[0,S]$.

By symmetry, each function $x\mapsto h_a(S-x)$ is also concave on $[0,S]$.

By summing concave and continuous functions, the function $g$ is concave and continuous and therefore, $\min g_{[0,S]} = \min (g(0),g(S))$.

Thus, we have $\min f = f(a_1,...,a_n) = g(a_1) \geq \min (g(0),g(S)) = \min (f(0,a_2,...,a_{j-1},a_1+a_j,...,a_n), f(a_1+a_j,a_2,...,a_{j-1},0,....,a_n))$, so $f$ has a minimum at $(0,a_2,...,a_{j-1},a_1+a_j,...,a_n)$ or $(a_1+a_j,a_2,...,a_{j-1},0,....,a_n)$, which contradicts the assumed maximality of the number of zeros in $(a_1,...,a_n)$ (one of the two strictly positive terms $a_1$ or $a_j$ could have been replaced by 0 while maintaining the minimality property).

After this proof by contradiction, we know that $f$ has a minimum at some point $(a_1,...,a_n)$ with at least $n-2$ zeros.

We have $f(1,0,...,0)=2$ and $f(1/2,1/2,0,....,0) = \dfrac{9}{5}<2$, so we can affirm that the maximum number of zeros that we were interested in from the beginning is $n-2$.

Therefore, there exists a point $(a_1,...,a_n)$ such that $a_1>0$, $a_j>0$ for some $j\in [2,n]$, and $a_i=0$ for all $i\neq 1,j$ that satisfies $\min f = f(a_1,...,a_n)$.

If $j\in [3,n-1]$, by a completely similar reasoning (using the concavity argument), we have $\min f \geq \min f(a_1+a_j,a_2,..,0,a_{j+1},...,a_n) , f(0,...,a_1+a_j,...,a_n) )=f(1,0,...,0,0,...,0)=2$

which is absurd.

Therefore, by circular permutation, we can find a point $(a_1,a_2,0,...,0)$ such that $\min f = f(a_1,a_2,0,...,0)$. To conclude, we only need to minimize $x\mapsto f(x,1-x,0,...,0)$, which is achieved at $x=1/2$, showing that $\min f\geq f(1/2,1/2,0,...,0)=\dfrac{9}{5}$.

Answer 2

Some tought for $n\geq 4$:

Define for $x,a\in[0,1/2]$ :

$$f\left(x\right)=\frac{\left(x+a\right)}{1+xa}-\frac{\frac{9}{5}\left(x+a\right)}{2}-\left(\frac{x\left(1-x\right)}{1+x}-\frac{a\left(1-a\right)}{1+a}\right)+\frac{\left(x-1\right)}{x+1}-\frac{\left(a-1\right)}{a+1}+x-a$$

Then we have :

$$f\left(x\right)-\frac{\left(f\left(0\right)-f\left(\frac{1}{2}\right)\right)}{0-\frac{1}{2}}x-f\left(0\right)\geq 0$$

Some remarks :

It preserves the equality case and seems to be accurate enought .

Remains to show that :

$$\sum_{cyc}^{}2\left(\frac{19}{10}a_1+\frac{\left(-58a_1^{2}-65a_1+42\right)}{20a_1+40}\right)a_2-\frac{19}{10}a_1\geq 9/5$$

But :

$$h(x)=\frac{\left(-58x^{2}-65x+42\right)}{20x+40}+\frac{19}{10}x$$

Is decreasing on $[0,1/2]$ and concave so it's easy to see we have :

$$h(x)\geq r(x)=\frac{\left(h\left(0\right)-h\left(\frac{1}{2}\right)\right)}{0-\frac{1}{2}}x+h\left(0\right)$$

So it's not hard to see for :

$$h(x,y)=2\left(r(x)\right)y$$

Then the minimum is reached for $$\left(h\left(\frac{1}{2},\frac{1}{2}\right)+h\left(0,\frac{1}{2}\right)\right)-\frac{19}{10}=0$$

So the inequality is proved for $x_i\in[0,0.5]$

---

---

Second version with details

Sketch for $n\geq 4$:

Define for $x,a\in[0,1/2]$ :

$$f\left(x,a\right)=f_1(x,a)+f_2(x,a)$$

$$f_1(x,a)=\frac{\left(x+a\right)}{1+xa}-\frac{\frac{9}{5}\left(x+a\right)}{2}$$

$$f_2(x,a)=-\left(\frac{x\left(1-x\right)}{1+x}-\frac{a\left(1-a\right)}{1+a}\right)+\frac{\left(x-1\right)}{x+1}-\frac{\left(a-1\right)}{a+1}+x-a$$

Lemma 1.

Then we have for $x,a\in[0,1/2]$:

$$g(x)=f\left(x,a\right)-\frac{\left(f\left(0,a\right)-f\left(\frac{1}{2},a\right)\right)}{0-\frac{1}{2}}x-f\left(0,a\right)\geq 0$$

Proof :

$$g(x)=\frac{11x^{2}a-29xa^{2}+21x-19a}{10xa+10}$$

Then differentiating twice with respect to $x$:

$$g''(x)=\frac{2a\left(a^{2}-1\right)}{(ax+1)^{3}}$$

So the function is concave so the chord is less greater than the function.

Some remarks :

It preserves the equality case and it's accurate enought .Also we don't need concavity and calculus since we have as difference :

$$g(x)=\frac{a\left(a-1\right)\left(a+1\right)x\left(2x-1\right)}{\left(a+2\right)\left(xa+1\right)}\geq 0$$

Next :

Remains to show using lemma 1 :

$$\sum_{cyc}^{}-f_2(a_1,a_2)=\sum_{cyc}^{}2\left(\frac{19}{10}a_1+\frac{\left(-58a_1^{2}-65a_1+42\right)}{20a_1+40}\right)a_2-\frac{19}{10}a_1\geq 0$$

But a lemma 2 :

Lemma 2.

Define for $x\in[0,1/2]$

$$h(x)=\frac{\left(-58x^{2}-65x+42\right)}{20x+40}+\frac{19}{10}x$$

Then the function $h(x)$ is decreasing on $[0,1/2]$ and concave so it's easy to see we have :

$$h(x)\geq r(x)=\frac{\left(h\left(0\right)-h\left(\frac{1}{2}\right)\right)}{0-\frac{1}{2}}x+h\left(0\right)$$

As lemma 1 and again we don't need calculus also.

Recalling the sum of $a_i$ must be one we have to show for $a_i\in[0,0.5]$:

$$2\frac{\left(h\left(0\right)-h\left(\frac{1}{2}\right)\right)}{0-\frac{1}{2}}\left(\sum_{i=1}^{n}a_{i}a_{i+1}\right)+2h\left(0\right)-\frac{19}{10}\leq \frac{2\frac{\left(h\left(0\right)-h\left(\frac{1}{2}\right)\right)}{0-\frac{1}{2}}\left(\sum_{i=1}^{n}a_{i}\right)^{2}}{4}+2h\left(0\right)-\frac{19}{10}=0$$

Wich is true using Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$ for $n\geq 4$ (user richrow make a mistake at the end it's $n>3$)

To conclude :

We have proved :

$$\sum_{cyc}^{}f_1(a_1,a_2)\geq 0$$

But again the sum of $a_i$ is one so it's greater than $9/5$ in summing the inequalities .

So the inequality is proved for $a_i\in[0,0.5]$

Answer 3

This is a simplified version of the proof of @JLapin.

Since $f(1/2,1/2,0,....,0)=9/5$ for $n≥3$ it is sufficient to prove that $f(x_1,…,x_n)≥9/5$ for $n≥3$.

The case $n=3$ has already been proved so proceed by induction on $n$ and suppose $n>3$.

Each term of $f(x_1,…,x_n)$ either involves neither $x_1$ nor $x_3$ or involves just one of them and is a concave function of that variable.

If $x_1+x_3$ is kept constant, the second derivative of $f(x_1,…,x_n)$ w.r.t. $x_1$ is therefore negative and so $f(x_1,…,x_n)$ is a concave function of $x_1$ . Hence its minimum is attained at a point where either $x_1=0$ or $x_3=0$.

W.l.g. suppose the minimum is attained at a point where $x_1=0$. Then $$f(x_1,…,x_n)=x_2+x_n-(x_2+x_n)/(1+x_2x_n)+f(x_2,…,x_n)≥f(x_2,…,x_n).$$This is then at least $9/5$ by the inductive hypothesis and the proof is complete.

Answer 4

If we have only one non-zero argument $x_i$ then $x_i=1$ so minimal (and the only) possible value of $f$ is $2$.

If we have two non-zero arguments then there are two options. If two nonzero components are non-adjacent then $f=x_i + x_j= 1$. Otherwise we have to maximize $x_i(1-x_i)$ so $x_i=x_i=1$ and $f=\frac12+\frac12+(\frac12+\frac12) * \frac45=\frac95$. Now we will assume that we have at least three non-zero arguments.

Let $g(t)=\frac{1}{1+t}, I=(0,1)$. Note that $g$ is convex and decreasing on $I$. Then $$f_n(x_1, x_2, \dots, x_n)=2 \cdot (\frac{x_1+x_2}2 g(x_1x_2) + \frac{x_2+x_3}2 g(x_2x_3) + \dots + \frac{x_n+x_1}2 g(x_nx_1))$$

Note that $g$ is convex and all the coefficient sum to $1$. Let $$h(x_1, x_2, \dots, x_n)=x_1^2x_2+x_2^2x_1+x_2^2x_3+x_3^2x_2+ \dots + x_n^2x_1+x_1^2x_n$$ Then

$$f(x_1, x_2, \dots, x_n) \ge 2g(\frac12 \cdot h(x_1, x_2, \dots, x_n))$$ Since $g$ is decreasing we need to maximize $h$ when $\sum x_i = 1$. Using rearrangement inequality we conclude that $h(x_1, x_2, \dots, x_n) \le h'(x_1, x_2, \dots, x_n) = 2 \sum x_i^3$. So we need to minimize sum of cubes. Power Means inequality says that if $x_i >0$ then $(\frac1n \sum x_i^3)^{\frac13} \le \frac1n \sum x_i= \frac1n$, so $\sum x_i^3 \ge \frac1{n^2}$. Since we can have $k$ non-zero elements, $3 \le k \le n$ we will use the inequality $n-3+1$ times and then take the largest estimate with $k=3$. So, $h \le \frac19$ and $$f(x_1, x_2, \dots, x_n) \ge 2g(\frac12 \cdot \frac29) \ge \frac2{1+\frac1{9}}=\frac95$$

Since this we value is achieved e.g. at $(\frac12, \frac12, 0,\dots,0)$ we found a global minimum and the problem is solved. $\Box$

Note that if we ask about the minimum when all $x_i > 0$ then slight modification of this proof will us lower estimate of $\frac2{1+\frac1{n^2}}$ that is indeed achieved at $(\frac1n, \frac1n, \frac1n, \dots, \frac1n)$