# 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$

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.

• This problem is Problem 2166 from Mathematics Magazine. While the MAA does not have explicit rules regarding the publication of these problems, they do ask that submitted solutions be original, and not published elsewhere. This thread seems to violate the spirit of the problem, if not the explicit rules. Apr 21, 2023 at 14:14
• @XanderHenderson does that mean that no more answers can be posted? Apr 21, 2023 at 15:54
• @V.S.e.H. I did not say that no more answers can be posted? Apr 21, 2023 at 15:57
• @XanderHenderson I had no idea about that when I was trying to solve the problem. Apr 21, 2023 at 16:34
• @XanderHenderson Can we have the comments back then ? They have all been deleted. Apr 21, 2023 at 17:46

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}$$.

• (+1) A lovely argument! I was tackling this problem by examining the effect of 'pair-modification' processes on the value of $f$, only to end up getting messy formulas. Now that I know a maximality argument beautifully resolves the problem, I can finally sleep tight and happy! 😊 Apr 21, 2023 at 17:52

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.

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)$$

• your solution has issues where you increase $h$ to the sum of cubes which you then decrease to $\dfrac{1}{n^2}$, so your proposed chain of inequality is broken. Instead, if you could prove: $$\sum_{i=1}^n x_ix_{i+1}(x_i + x_{i+1})\leq\dfrac{2}{n^2}\left(\sum_{i=1}^n x_i\right)^3,$$ which may or may not be true - I am not sure. Apr 27, 2023 at 19:16
• I do not decrease to $\frac1{n^2}$, I increase - I take maximum among all possible lower bounds. Apr 28, 2023 at 9:48

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]$$