16
$\begingroup$

Is it true that: $$ f_n(x_1,\ldots,x_n)=\frac{x_1-x_2}{x_n+x_1} + \frac{x_2-x_3}{x_1+x_2}+\cdots+ \frac{x_n-x_1}{x_{n-1} +x_n}\le 0 $$ for $x_1,\ldots,x_n>0$, such that $x_1+\cdots+x_n=1$?

It is a cyclic inequality that I came up with while proving similar ones, although it may well be already solved/proposed somewhere else. Equality is attained at $x_1=\cdots=x_n=1/n$.

The first approach I’ve tried is to represent the inequality equivalently as $$ n\le \frac{x_1 +x_3}{x_1+x_2} + \frac{x_2+x_4}{x_2+x_3}+\cdots+\frac{x_n+x_2}{x_n+x_1}, $$ which is trivially true for $n=3$ by AM-GM, but not so for $n>3$, since the terms don’t cancel.

I’ve also tried the following approach: let $x_1$ be the largest wlog, then we can examine the function $$ g(t)=f_n(x_1-t, x_2 +t,\ldots,x_n) = \frac{x_1-x_2-2t}{x_n+x_1-t} + \frac{x_2+t-x_3}{x_1+x_2}+ \frac{x_3-x_4}{x_2+t+x_3} +\cdots+ \frac{x_n-x_1+t}{x_{n-1} +x_n} $$ and see if it is increasing for small enough $t$. Then we can proceed by generating sequences that approach the average while increasing the value of $f$. For example $$ g(t)-g(0)=\frac{t}{x_1+x_2}+\frac{t}{x_n+x_{n-1}}-t\frac{x_1+x_2+2x_n}{(x_1+x_n-t)(x_1+x_n)}-t\frac{x_3-x_4}{(x_2+x_3+t)(x_2+x_3)}, $$ but not sure if this is nonnegative.

EDIT: I've made some progress towards the $n=5$ case.

Let us assume wlog that $x_1$ is the largest throughout the proof. We also know that the $n=4$ case is true (see comments). Thus $$ f_5(x_1,\ldots,x_5)=f_4(x_2,\ldots,x_5)+\frac{x_2-x_1}{x_4+x_5}+\frac{x_1-x_2}{x_5+x_1}+\frac{x_2-x_3}{x_1+x_2}-\frac{x_2-x_3}{x_5+x_1}\leq\\\leq \frac{x_2-x_1}{x_4+x_5}+\frac{x_1-x_2}{x_5+x_1}+\frac{x_2-x_3}{x_1+x_2}-\frac{x_2-x_3}{x_5+x_1}=\\=\frac{(x_1-x_2)(x_4-x_1)}{(x_1+x_5)(x_4+x_5)}+\frac{(x_2-x_3)(x_5-x_1)}{(x_1+x_2)(x_2+x_5)}.\tag{1}\label{ineq:1} $$ By successively cyclically permuting the sequence we also derive the inequalities: \begin{align} f_5(x_1,\ldots,x_5) &\leq \frac{(x_2-x_3)(x_5-x_2)}{(x_2+x_1)(x_5+x_1)}+\frac{(x_3-x_4)(x_1-x_2)}{(x_2+x_3)(x_3+x_1)}\label{ineq:2}\tag{2}, \\ f_5(x_1,\ldots,x_5) &\leq \frac{(x_3-x_4)(x_1-x_3)}{(x_3+x_2)(x_1+x_2)}+\frac{(x_4-x_5)(x_2-x_3)}{(x_3+x_4)(x_4+x_2)}\label{ineq:3}\tag{3}, \\ f_5(x_1,\ldots,x_5) &\leq \frac{(x_4-x_5)(x_2-x_4)}{(x_4+x_3)(x_2+x_3)}+\frac{(x_5-x_1)(x_3-x_4)}{(x_4+x_5)(x_5+x_3)}\label{ineq:4}\tag{4}, \\ f_5(x_1,\ldots,x_5) &\leq \frac{(x_5-x_1)(x_3-x_5)}{(x_5+x_4)(x_3+x_4)}+\frac{(x_1-x_2)(x_4-x_5)}{(x_5+x_1)(x_1+x_4)}\label{ineq:5}\tag{5}. \end{align}

Now we consider several cases.

Case 1: If $x_2\geq x_3$ then $\eqref{ineq:1}$ is $\leq 0$.

Case 3: If $x_2 < x_3 \leq x_4 \leq x_5$ then $\eqref{ineq:2}$ is $\leq 0$.

Case 2: If $x_2 < x_3 \leq x_4$ and $x_4 > x_5$ then $\eqref{ineq:3}$ is $\leq 0$.

Case 4: If $x_2 < x_3$, $x_3 > x_4, x_4 \leq x_5$ and $x_3 \geq x_5$ then $\eqref{ineq:5}$ is $\leq 0$.

Case 5: If $x_2 < x_3$, $x_3 > x_4, x_4 \leq x_5$ and $x_2 \geq x_4$ then $\eqref{ineq:4}$ is $\leq 0$.

Case 6: If $x_2 < x_3$, $x_3 > x_4, x_4 > x_5$ and $x_2 \leq x_4$ then $\eqref{ineq:4}$ is $\leq 0$.

There are two more cases to consider.

Case 7: If $x_3>x_2>x_4 > x_5$ then it seems to be the case that $$ f_5(x_1,\ldots,x_5) \leq f_5(x_1,x_2,x_4,x_3,x_5). $$ via simulation. If proven true, then we just need to apply case 1 to it and we're done.

Case 8: Since case 4 and 5 are true independently, we need consider only $x_5>x_3>x_4>x_2$ as a subcase. However I haven't the slightest clue how to approach this.

EDIT 2 According to WolframAlpha, it seems that the individual fractions are concave functions of $\mathbf{x}=(x_1,\ldots,x_n)$. Does that mean that $f$ is also concave, therefore we can bound by $$ f_n(\mathbf{x}) \leq f_n(\mathbf{1}/n) + \nabla f_n(\mathbf{1}/n)^T(\mathbf{x} - \mathbf{1}/n) = 0? $$

$\endgroup$
21
  • 1
    $\begingroup$ @Accelerator they are similar yes, but not quite. $\endgroup$
    – V.S.e.H.
    Commented Apr 26, 2023 at 22:02
  • 2
    $\begingroup$ as of some years ago, the $n = 5$ case remains a conjecture - see page 60 of old and new inequalities $\endgroup$
    – dezdichado
    Commented Apr 26, 2023 at 22:21
  • 5
    $\begingroup$ Since this question is bountied, I am gonna ask people to not upvote answers unless they make a significant progress on the problem. $n=4$ is very easy by AM-GM and any progress on $n>4$ should be very solid. This is because I have seen time and time again once a hard question is bountied, some people write answers with little progress and get the bounty if someone just happens to vote up. $\endgroup$
    – dezdichado
    Commented Apr 30, 2023 at 16:00
  • 1
    $\begingroup$ $n=6$, $(x_1,x_2,x_3,x_4,x_5,x_6)=(\frac1{86}, \frac{13}{43}, \frac{1}{43}, \frac{13}{43}, \frac{3}{86}, \frac{14}{43})$ or $(1,26,2,26,3,28)$, $f_n(x_1,\ldots,x_n)= \frac1{226548}>0.$ $\endgroup$
    – Apass.Jack
    Commented May 1, 2023 at 13:18
  • 3
    $\begingroup$ I've executed a genetic algorithm to find counterexamples and both $n=6$ and $n=13$ are found quickly, but none of $n=7,9,11$ is, so that hints towards affirmative for these cases. $\endgroup$
    – Sil
    Commented May 2, 2023 at 11:32

7 Answers 7

11
$\begingroup$

The inequality is false for $n = 6$ (and any even $n > 6$ also). I drop the requirement that the sum be equal to $1$, since one can always scale any counter-example if desired.

As an example, one has $$ f(0.01,~1,~0.05,~1,~0.10,~1.10) \approx 0.00033 > 0. $$ This is inspired by counter-examples to Shapiro's inequality, which look for $x$ under the form $$ x(\varepsilon) := (\varepsilon a_1 ,~1 + \varepsilon a_2,~\varepsilon a_3 ,~1 + \varepsilon a_4,~\varepsilon a_5,~1 + \varepsilon a_6), $$ for well-chosen coefficients $a_i$ and $\varepsilon$ small enough. I use $a = (1, 0, 5, 0, 10, 10)$ for which $$ f(x(\varepsilon)) = 19 \varepsilon^2 + O(\varepsilon^3) $$ by Taylor expansion, which is indeed positive (with $x_i > 0$) for $\varepsilon > 0$ small enough.


Edit: For any even $n \geq 6$, one can use $x = (0.10,~1.10,~0,~1.05,~0,~1,\dotsc,~0,~1)$ which is of the form $x(\varepsilon) = (2\varepsilon,~1+2\varepsilon,~0,~1+\varepsilon,~0,~1, ~\dotsc,~0,~1)$, where $\varepsilon = 0.05$. The last $(0,1)$ are repeated as much as necessary. Taylor expansion proves that $f(x(\varepsilon)) = \varepsilon^2 + O(\varepsilon^3)$. If desired, the zero components can be replaced by $\varepsilon^3$ to ensure $x_i > 0$.

$\endgroup$
5
  • 3
    $\begingroup$ Nice find! Just to save others the scaling, a counterexample to the original problem is $(1/326, 50/163, 5/326, 50/163, 5/163, 55/163)$, $\endgroup$
    – Sil
    Commented Apr 30, 2023 at 22:34
  • $\begingroup$ Very nice indeed, and this puts lots of rest on my mind! However, I'd refrain from up-voting your answer until some more progress towards the $n=5$ case is made. $\endgroup$
    – V.S.e.H.
    Commented Apr 30, 2023 at 22:56
  • $\begingroup$ @cs89.- Besides, a permutation of a suitable $(x_1,x_2,x_3,.......,x_n)$ can give distinct result for $f(x_1,....,x_n)$ so if $f(x_1,....,x_n)\le0$ does not implies a change of the order of indices is also $\le0$. For example $f(x_1,....,x_5)=f(1/3,1/10, 7/30,1/7,4/21)$ we get $f(1/3,...,4/21)=-0.145962$ and $f(1/10,1/3,7/30,4/21,1/7)=-0.413453$. If the inequality were always true, then a proof for $(x_1,....,x_n)$ is not a proof for all the permutations of the $x_i$. (Sorry for bad English) $\endgroup$
    – Piquito
    Commented May 1, 2023 at 1:22
  • 2
    $\begingroup$ @piquito The conjecture was "for all $x$, $f(x) \leq 0$". To prove it, you have to consider all permutations. To disprove it, finding a single counter-example is sufficient. $\endgroup$
    – cs89
    Commented May 1, 2023 at 6:17
  • 1
    $\begingroup$ @cs89 Nice counterexamples. (+1) $\endgroup$
    – River Li
    Commented May 1, 2023 at 7:18
9
+150
$\begingroup$

Remarks: The inequality is not true for even $n\ge 6$, or odd $n\ge 13$. The inequality is true for $n = 3, 4, 5$. The remaining cases are $n = 7, 9, 11$.

Some results for even $n\ge 6$ or odd $n\ge 13$ etc.

Since the inequality is homogeneous, we drop the condition $x_1 + x_2 + \cdots + x_n = 1$ for convenience. In other words, we consider the following problem.

Problem. Let $n\ge 3$. Let $x_1, x_2, \cdots, x_n \ge 0$ with $(x_1+x_2)(x_2 + x_3)\cdots (x_n + x_1) \ne 0$. Prove or disprove $$\sum_{\mathrm{cyc}} \frac{x_2 - x_3}{x_1 + x_2} \le 0. \tag{1}$$

Denote LHS by $f_n(x_1, x_2, \cdots, x_n)$. We have the relation: $$f_{n+2}(x_1, x_2, \cdots, x_n, x_1, x_n) = f_n(x_1, x_2, \cdots, x_n). \tag{2}$$ Note: This is actually Wenlan Yan (a Chinese Scholar)'s idea for a related problem (see my another answer). The proof is easy. Indeed, we have \begin{align*} &f_{n+2}(x_1, x_2, \cdots, x_n, x_1, x_n)\\ ={}& \frac{x_2 - x_3}{x_1 + x_2} + \cdots + \frac{x_n - x_1}{x_{n-1} + x_n} + \frac{x_1 - x_n}{x_n + x_1} + \frac{x_n - x_1}{x_1 + x_n} + \frac{x_1 - x_2}{x_n + x_1}\\ ={}& \frac{x_2 - x_3}{x_1 + x_2} + \cdots + \frac{x_n - x_1}{x_{n-1} + x_n} + \frac{x_1 - x_2}{x_n + x_1}\\ ={}& f_n(x_1, x_2, \cdots, x_n). \end{align*}

From (2), we know that if (1) is true for $n + 2$, then (1) is also true for $n$. In other words, if (1) is not true for $n$, then (1) is not true for $n + 2$. Using this fact, we obtain some results as follows.

  1. The inequality is not true for even $n\ge 6$.

We have $$f_6(40,3,40,5,45,0) ) = \frac{11}{15480} > 0.$$ Thus, (1) is not true for $n = 6$.

So, (1) is not true for even $n\ge 6$.

  1. The inequality is not true for odd $n\ge 13$.

We have $$f_{13}(4,4,6,4,8,0,6,0,4,1,4,2,4) = \frac{1}{60} > 0.$$ Thus, (1) is not true for $n = 13$.

Thus, (1) is not true for odd $n\ge 13$.

$\endgroup$
7
$\begingroup$

Remarks: Here is a proof for $n = 5$ case. The identity is verified by Maple. The Maple expression of $f(a,b,c,d,e)$ is given at the end if someone wants to verify it by CAS (Computer Algebra Systems).

Problem. Let $a, b, c, d, e \ge 0$ with $(a+b)(b+c)(c+d)(d+e)(e+a) \ne 0$. Prove that $$\frac{a - b}{e + a} + \frac{b - c}{a + b} + \frac{c - d}{b + c} + \frac{d - e}{c + d} + \frac{e - a}{d + e} \le 0.$$

Proof.

We have \begin{align*} &-\frac{a - b}{e + a} - \frac{b - c}{a + b} - \frac{c - d}{b + c} - \frac{d - e}{c + d} - \frac{e - a}{d + e}\\[6pt] ={}& \frac{f(a,b,c,d,e) + f(b,c,d,e,a) + f(c,d,e,a,b) + f(d,e,a,b,c) + f(e,a,b,c,d)}{(a+b)(b+c)(c+d)(d+e)(e+a)} \end{align*} where \begin{align*} f(a, b, c, d, e) &:= {\frac {1}{540}}\,cab \left( 23\,a-15\,d-8\,e \right) ^{2}+{\frac {11} {540}}\,cab \left( a-d \right) ^{2}\\[6pt] &\qquad + {\frac {1}{945}}\,abd \left( 30\,a-30\,d+7\,c-7\,e \right) ^{2} + {\frac {2213}{108000}}\,{a}^{2}c \left( b-e \right) ^{2}\\[6pt] &\qquad +{ \frac {1}{2025}}\,c \left( 36\,ab+4\,ad-31\,ae+6\,bd-30\,be+15\,ce \right) ^{2}\\[6pt] &\qquad +{\frac {1}{16200}}\,c \left( 31\,ab+24\,ad+59\,ae-114\,b d+120\,be-120\,ce \right) ^{2}\\[6pt] &\qquad +{\frac {1}{16200}}\,c \left( 3\,ab+4\,a d-13\,ae+6\,bd \right) ^{2} +\frac{1}{21}\,abd \left( a-d \right) ^{2}\\[6pt] &\qquad +{\frac {1}{324000}}\,c \left( 301\,ab+240 \,ad-301\,ae-240\,bd \right) ^{2}. \end{align*}

We are done.


Maple expression of $f(a,b,c,d,e)$:

(1/540)*c*a*b*(23*a-15*d-8*e)^2+(11/540)*c*a*b*(a-d)^2+(1/21)*a*b*d*(a-d)^2+(1/945)*a*b*d*(30*a-30*d+7*c-7*e)^2+(1/2025)*c*(36*a*b+4*a*d-31*a*e+6*b*d-30*b*e+15*c*e)^2+(1/16200)*c*(31*a*b+24*a*d+59*a*e-114*b*d+120*b*e-120*c*e)^2+(1/16200)*c*(3*a*b+4*a*d-13*a*e+6*b*d)^2+(1/324000)*c*(301*a*b+240*a*d-301*a*e-240*b*d)^2+(2213/108000)*a^2*c*(b-e)^2
$\endgroup$
6
  • $\begingroup$ this is one of the more obnoxious SOS I have seen yet. The equality case seems to only leave $a = b=c=d=e$ just from the four linear terms. Was hoping to see some weird equality cases like some of Vasc's inequalities. $\endgroup$
    – dezdichado
    Commented May 1, 2023 at 15:07
  • $\begingroup$ @dezdichado The form is not very complicated due to cyclic sum. I seldom saw inequalities with simple forms and weird equality cases. $\endgroup$
    – River Li
    Commented May 1, 2023 at 15:24
  • 1
    $\begingroup$ I have verified the equality using PARI/GP. ? f(a,b,c,d,e) + f(b,c,d,e,a) + f(c,d,e,a,b) + f(d,e,a,b,c) + f(e,a,b,c,d) - ((b-a)*(a+b)*(b+c)*(c+d)*(d+e) + (c-b)*(b+c)*(c+d)*(d+e)*(e+a) + (d-c)*(a+b)*(c+d)*(d+e)*(e+a) + (e-d)*(a+b)*(b+c)*(d+e)*(e+a) + (a-e)*(a+b)*(b+c)*(c+d)*(e+a)) %2 = 0 $\endgroup$
    – Apass.Jack
    Commented May 3, 2023 at 22:04
  • 1
    $\begingroup$ It looks this proof is the one that makes real progress on this question if I have to select only one among all answers so far. The proof for $n=5$ presented here is not immediate to verify. $\endgroup$
    – Apass.Jack
    Commented May 3, 2023 at 22:07
  • $\begingroup$ @Apass.Jack Thanks! SOS (Sum of Squares) is easily verified by computer (simply expanding both sides), though it takes hours to verify it by hand. $\endgroup$
    – River Li
    Commented May 4, 2023 at 0:19
5
$\begingroup$

Related inequalities:

Remarks: Here I introduce the No. 13 of Xuezhi Yang's 22 conjectures. I think we can find some similar results, and the strategy for it is helpful. More details are given in https://artofproblemsolving.com/community/c6h2718098


At the Symposium in Elementary Mathematics (in 2009, China), Mr. Xuezhi Yang proposed 22 conjectures in inequalities. No. 13 is the following:

Conjecture 13 (Xuezhi Yang): Let $x_1, x_2, \cdots, x_n \ge 0$. For $n = 5, 6, \cdots, 13$ and $ n = 15, 17, 19, 21, 23$, prove or (disprove) $$\sum_{\mathrm{cyc}} \frac{x_1 - x_2}{x_2 + x_3}\ge 0.$$

According to Mr. Xuezhi Yang's book (written in Chinese, 2009), the case $n = 3, 4$ was proposed in 1990.

According to the results of some Chinese scholars, the inequality is not true for $n = 6, 8, 10, 12$ and $n = 13, 15, 17, 19, 21, 23$; and the inequality is true for $n = 5$. The remaining cases are $n = 7, 9, 11$.

For general $n$: According to the results of Wenlan Yan (a Chinese scholar), $f_{n + 2} \ge 0$ implies $f_n \ge 0$ where $f_n$ denotes the LHS of the inequality. Thus, the inequality is not true for $n\ge 6$ and even, or $n\ge 13$ and odd.

$\endgroup$
5
  • $\begingroup$ Can you post a corrected and translated version of Wenlan Yan's proof for $n=5$? $\endgroup$
    – V.S.e.H.
    Commented Apr 30, 2023 at 23:18
  • $\begingroup$ @V.S.e.H. Perhaps in some days. $\endgroup$
    – River Li
    Commented Apr 30, 2023 at 23:39
  • $\begingroup$ @V.S.e.H. I gave a proof for $n=5$ case. So I will not consider Wenlan Yan's proof. $\endgroup$
    – River Li
    Commented May 1, 2023 at 7:13
  • $\begingroup$ @Sil Yes, I guess the results are similar. $\endgroup$
    – River Li
    Commented May 1, 2023 at 15:15
  • $\begingroup$ @Sil Ah yes, there was a small mistake... $\endgroup$
    – V.S.e.H.
    Commented May 1, 2023 at 16:22
4
$\begingroup$

This is too long for a comment and since it was requested, here is a Python script to search for counterexamples using a genetic algorithm. It uses first library I found for genetic algorithms with basic settings, in this case PyGAD. I am sure things like crossover & mutation can be tuned as well as the code optimized, but it already finds (counter)examples quickly enough. Also it searches without the $x_1+\dots +x_n=1$ restriction, so scale the solutions if needed.

Note: In current implementation the genes (individual $x_i$s) can be negative so I am working with absolute values.

import pygad


def check(n):

    def fitness_func(ga_instance, solution, solution_idx):
        X = [abs(x) for x in solution]
        S = 0
        for i in range(n):
            if X[(i - 1)] + X[i] == 0:
                return -1
            S += (X[i] - X[(i + 1) % n]) / (X[(i - 1) % n] + X[i])

        return S

    fitness_function = fitness_func

    num_generations = 100
    num_parents_mating = 4

    sol_per_pop = 50
    num_genes = n

    init_range_low = 0
    init_range_high = 1

    parent_selection_type = "sss"
    keep_parents = 1

    crossover_type = "single_point"

    mutation_type = "random"
    mutation_percent_genes = "default"
    mutation_num_genes = 1

    for attempt in range(200):
        gene_type = [float] * n

        ga_instance = pygad.GA(num_generations=num_generations,
                               num_parents_mating=num_parents_mating,
                               fitness_func=fitness_function,
                               sol_per_pop=sol_per_pop,
                               num_genes=num_genes,
                               init_range_low=init_range_low,
                               init_range_high=init_range_high,
                               parent_selection_type=parent_selection_type,
                               keep_parents=keep_parents,
                               crossover_type=crossover_type,
                               mutation_type=mutation_type,
                               mutation_percent_genes=mutation_percent_genes,
                               mutation_num_genes=mutation_num_genes,
                               gene_type=gene_type)

        ga_instance.run()

        solution, solution_fitness, solution_idx = ga_instance.best_solution()

        if solution_fitness > 0:
            return [abs(x) for x in solution], solution_fitness

    return None, None


for n in range(3, 20):
    sol, fitness = check(n)
    if sol is None:
        print(f"{n}: counterexample not found")
    else:
        print(f"{n}: counterexample found: {sol}, {fitness}")

Here is an example output when searching in range $n=3,4,\dots,19$:

3: counterexample not found
4: counterexample not found
5: counterexample not found
6: counterexample found: [0.1127451443655707, 0.984047056559817, 0.0006891812689751031, 0.8747821381098065, 0.07973695836666417, 0.8923772229596213], 0.0008424173573100546
7: counterexample not found
8: counterexample found: [0.7555196233906635, 0.002284834826341453, 0.6066683059689687, 0.035242433747941115, 0.5500023844379328, 0.13912705899813071, 0.6227234634922209, 0.17019419483944864], 0.008692855805153221
9: counterexample not found
10: counterexample found: [0.2865983261600199, 1.0494435537886102, 7.556348092685461e-06, 0.8026083255492057, 0.002541750372603957, 0.6226469717045814, 0.14437176959682485, 0.6626180639943181, 0.28551562949546505, 0.8593656766544738], 0.0333552418370901
11: counterexample not found
12: counterexample found: [0.4598963440624112, 1.0406403276703875, 0.3690044176216819, 1.2251453839093667, 0.00272450987067574, 0.882985035974145, 0.0007653966593861306, 0.6372299973803794, 0.1551872312511604, 0.6231971103898529, 0.33989248661093063, 0.7628276059879917], 0.05556447423696165
13: counterexample found: [0.5038459363748282, 1.3133558069280669, 0.008177075932440991, 0.8967924375504703, 0.022380104007717172, 0.6467699203174091, 0.1584673377078757, 0.5933052961735467, 0.38879601764418403, 0.6066572584225334, 0.6466163377832892, 0.642257389205082, 1.003618621480073], 0.02230627298168064
14: counterexample found: [0.2936805194030777, 1.101167116014886, 0.003222280282728973, 0.7995927516297595, 0.007168899301610132, 0.6585845937517883, 0.11700998100189608, 0.6323059856367423, 0.24031085433340538, 0.6772291101836613, 0.36253497690141756, 0.8111908100214541, 0.3547934092222419, 0.9573210731042766], 0.06106131972134221
15: counterexample found: [0.5477099288485329, 0.14730657809570247, 0.5376848427524631, 0.380555167689996, 0.637009671846778, 0.6422098324140793, 0.7022963361696113, 1.0057284457810964, 0.6616176612213105, 1.561049295175914, 0.005156204220376437, 1.0907727535676819, 0.004646387587251555, 0.7780822896796564, 0.0028204349956135744], 0.08453066977596169
16: counterexample found: [0.6397938698339589, 0.28234049273033257, 0.6904935018333977, 0.3804797750754091, 0.7725996710450245, 0.4933655531224208, 0.9628793435340853, 0.5205017242374805, 1.2076892091095182, 0.3036581190825709, 1.2630253424373237, 0.003934738509556834, 0.883203765847461, 0.005181489305189579, 0.6380104290746482, 0.1365655586542045], 0.08747753124842539
17: counterexample found: [0.8089562532936915, 0.7671223686995414, 1.3097405784811802, 0.6274276398114672, 1.6859621526863962, 0.0008962964378883553, 1.1708809051169948, 0.005156967931749024, 0.842201107879035, 0.00443971922676234, 0.5871581225772036, 0.08072680836604595, 0.475399915499073, 0.24305503363159742, 0.5164480153919089, 0.49097915717416885, 0.6500685676958009], 0.12352471651055946
18: counterexample found: [0.4941360812428496, 0.9855792458054153, 0.39214096423944556, 1.2175256082754318, 0.013009837737754881, 0.9115555653063624, 0.0038629864364830846, 0.6531094666853975, 0.007590820745124405, 0.4599560432187483, 0.06023746725062318, 0.4142086539545594, 0.18738989383376248, 0.41555600252250013, 0.2969341489356452, 0.4925680529149822, 0.4268911172788926, 0.6498808193467815], 0.14161415469210945
19: counterexample found: [0.43397023970898874, 0.2762568644315543, 0.48850362912513257, 0.4224351109668695, 0.5431450504814156, 0.6011817391126395, 0.5937733459216573, 0.853280211198245, 0.5916627588456863, 1.1142048188624363, 0.3181712042000304, 1.1479101992709562, 0.010300281098192143, 0.8080262936090858, 0.024535790039653227, 0.6318421262424485, 0.006276206316145894, 0.4577509718418442, 0.12785211607940616], 0.12041951610009682

This is consistent with findings in other answers, and for remaining unsolved cases $7,9,11$ it finds no counterexample (even if we try to search for much longer, I've had it running for couple hours and no luck). This of course proves nothing but at least gives some numeric evidence that the inequality might hold in these three cases.

I would also like to point out a similarity to Shapiro inequality which was already touched on in another answer. Shapiro has first even counterexample for $n=14$, while first odd for $n=25$, and our computations suggest that this inequality has also odd counterexample higher than the even one. So I believe that studying Shapiro's and related proofs might help with the cases $n=7,9,11$.

$\endgroup$
6
  • 2
    $\begingroup$ Thanks for sharing. (+1) By the way, No. 3/4/13 of Xuezhi Yang's 22 conjectures in inequalities are similar (the inequalities are not true for $n> N$ for small $N$). $\endgroup$
    – River Li
    Commented May 4, 2023 at 12:07
  • $\begingroup$ @RiverLi, is there an English transcription of this 22 conjectures or a paper written somewhere? This is like the 3rd time I am encountering it. $\endgroup$
    – dezdichado
    Commented May 4, 2023 at 17:20
  • $\begingroup$ @dezdichado No. $\endgroup$
    – River Li
    Commented May 4, 2023 at 22:37
  • $\begingroup$ No. 4 is in: math.stackexchange.com/questions/4190740/…. The remaining cases are $n=6,7,8$. Can your code find counterexamples for them? $\endgroup$
    – River Li
    Commented May 6, 2023 at 10:30
  • $\begingroup$ @RiverLi We only need to modify the fitness function, I've tried it and it did not find anything for $n\leq 8$, but found quickly for $n\geq 9$. $\endgroup$
    – Sil
    Commented May 6, 2023 at 11:02
4
$\begingroup$

Using your notation for $f_n(x_1,\ldots,x_n)$, notice if we reverse the variables and change the sign, as well as the order of first $n-1$ terms, we get the equivalent

$$ -f_n(x_n,\ldots,x_1)=\sum_{cyc}\frac{x_i-x_{i+1}}{x_{i+1}+x_{i+2}}=\frac{x_1-x_2}{x_2 +x_3}+\frac{x_2-x_3}{x_3 +x_4}+\dots+\frac{x_n-x_1}{x_1 +x_2}\geq 0.\tag{*} $$

This happens to be the related inequality as posted by River Li in their answer (No. 13 of Xuezhi Yang's 22 conjecture) - so not only they are related but they are equivalent. Furthermore I have checked a literature and found this has been apparently proven for $n=3,4,5,7$, namely in Automated Inequality Proving and Discovering by Bican Xia and Lu Yang (2016) we find:

Page 290, Example 10.15 (Problem 7.14 of [Cirtoaje et al. (2009)]):

$$ \frac{a-b}{b+c}+\frac{b-c}{c+d}+\frac{c-d}{d+e}+\frac{d-e}{e+a}+\frac{e-a}{a+b}\geq 0 $$

Page 291, Example 10.19 (Vasc's Conjecture with 6 variables):

$$ \frac{a_1-a_2}{a_2 +a_3}+\frac{a_2-a_3}{a_3 +a_4}+\frac{a_3-a_4}{a_4 +a_5}+\frac{a_4-a_5}{a_5 +a_6}+\frac{a_5-a_6}{a_6 +a_1}+\frac{a_6-a_1}{a_1 +a_2}\geq 0 $$ where $a_i>0$, ($i=1,\dots,6$). It is easy to see that Example 10.15 is a special case of Vasc's Conjecture when the number of variables is $5$.

The inequality does not hold. An output counterexample is $$a_1=84,a_2=7,a_3=79,a_4=5,a_5=76,a_6=1.$$ Let $n$ be the number of variables in Vasc's Conjecture. By SDS method, we have proven that the inequality holds for $n=3,4,5,7$.

Page 291, Example 10.20 (Vasc's Conjecture with 7 variables):

$$ \frac{a_1-a_2}{a_2 +a_3}+\frac{a_2-a_3}{a_3 +a_4}+\frac{a_3-a_4}{a_4 +a_5}+\frac{a_4-a_5}{a_5 +a_6}+\frac{a_5-a_6}{a_6 +a_7}+\frac{a_6-a_7}{a_7 +a_1}+\frac{a_7-a_1}{a_1 +a_2}\geq 0 $$ where $a_i>0$ for $i=1,\dots,7$.

Chen (2008) made use of the Parallel Successive Difference Substitution to verify this inequality. It runs on 18 nodes of a set of HP Proliant DL360 Intel xeon 2.8Ghz, 2GB memory, Windows 2003 Server, with Maple 10, and proved that the inequality holds in CPU time 9128.92 seconds.

So we are given a counterexample to $n=6$ to our original problem, as well as we know the cases $n=3,4,5,7$ have been verified by the successive difference substitution (SDS) method described earlier in the book. Unfortunately, we are not given any analytical proof, the method relies on heavy computations (large number of polynomials are generated in the process). Still it might be worth reproducing the result and trying the algorithm on the last two cases $n=9,11$.

As for reproducing the result, I've implemented a version of the algorithm in Maple and verified the cases $n=3,4,5,7$. I will show how the method works for $n=5$ and then just summarize the case $n=7$.

Consider $n=5$. We want to have inequality with polynomial on one side, so we first multiply by (positive) $\prod_{cyc}(x_2+x_3)$. Then since the inequality is cyclic, we can WLOG assume $x_1$ is the maximal of the $x_i$ values. Now we consider $4!=24$ orderings of the remaining variables, for example for $x_1\geq x_2 \geq \dots \geq x_5$ we let \begin{alignat*}{5} x_1&=t_1+&t_2+&t_3+&t_4+&t_5\\ x_2&= &t_2+&t_3+&t_4+&t_5\\ x_3&= & &t_3+&t_4+&t_5\\ x_4&=& & &t_4+&t_5\\ x_5&=& & & &t_5. \end{alignat*} It can be verified that all $x_i>0$ if and only if all $t_i > 0$. Substituting to the original polynomial we get a polynomial in $t_1,t_2,t_3,t_4,t_5$ with only non-negative coefficients, and so it is positive for positive $t_i$'s. Checking the remaining $23$ orderings and applying corresponding substitutions (largest number, i.e. $x_1$ being $t_1+t_2+\dots+t_5$, second largest $t_2+\dots +t_5$ and so on), we find there are only three polynomials that have a negative coefficient. For example one of them being:

$$ t_1^3t_2^2 + 3t_1^3t_2t_3 + 3t_1^3t_2t_4 + 4t_1^3t_2t_5 + 2t_1^3t_3^2 + 4t_1^3t_3t_4 + 6t_1^3t_3t_5 + 2t_1^3t_4^2 + 6t_1^3t_4t_5 + 4t_1^3t_5^2 + 3t_1^2t_2^3 + 10t_1^2t_2^2t_3 + 8t_1^2t_2^2t_4 + 12t_1^2t_2^2t_5 + 9t_1^2t_2t_3^2 + 13t_1^2t_2t_3t_4 + 24t_1^2t_2t_3t_5 + 5t_1^2t_2t_4^2 + 20t_1^2t_2t_4t_5 + 16t_1^2t_2t_5^2 + 3t_1^2t_3^3 + 7t_1^2t_3^2t_4 + 12t_1^2t_3^2t_5 + 6t_1^2t_3t_4^2 + 20t_1^2t_3t_4t_5 + 16t_1^2t_3t_5^2 + 2t_1^2t_4^3 + 10t_1^2t_4^2t_5 + 16t_1^2t_4t_5^2 + 8t_1^2t_5^3 + 3t_1t_2^4 + 12t_1t_2^3t_3 + 9t_1t_2^3t_4 + 14t_1t_2^3t_5 + 15t_1t_2^2t_3^2 + 19t_1t_2^2t_3t_4 + 36t_1t_2^2t_3t_5 + 4t_1t_2^2t_4^2 + 22t_1t_2^2t_4t_5 + 20t_1t_2^2t_5^2 + 8t_1t_2t_3^3 + 12t_1t_2t_3^2t_4 + 26t_1t_2t_3^2t_5 \color{red}{-} t_1t_2t_3t_4^2 + 18t_1t_2t_3t_4t_5 + 24t_1t_2t_3t_5^2 \color{red}{-} 4t_1t_2t_4^3 \color{red}{-} 4t_1t_2t_4^2t_5 + 8t_1t_2t_4t_5^2 + 8t_1t_2t_5^3 + 2t_1t_3^4 + 5t_1t_3^3t_4 + 8t_1t_3^3t_5 + 3t_1t_3^2t_4^2 + 10t_1t_3^2t_4t_5 + 8t_1t_3^2t_5^2 + t_2^5 + 5t_2^4t_3 + 4t_2^4t_4 + 6t_2^4t_5 + 9t_2^3t_3^2 + 14t_2^3t_3t_4 + 22t_2^3t_3t_5 + 5t_2^3t_4^2 + 16t_2^3t_4t_5 + 12t_2^3t_5^2 + 8t_2^2t_3^3 + 19t_2^2t_3^2t_4 + 28t_2^2t_3^2t_5 + 14t_2^2t_3t_4^2 + 38t_2^2t_3t_4t_5 + 28t_2^2t_3t_5^2 + 4t_2^2t_4^3 + 12t_2^2t_4^2t_5 + 16t_2^2t_4t_5^2 + 8t_2^2t_5^3 + 4t_2t_3^4 + 15t_2t_3^3t_4 + 18t_2t_3^3t_5 + 22t_2t_3^2t_4^2 + 42t_2t_3^2t_4t_5 + 24t_2t_3^2t_5^2 + 17t_2t_3t_4^3 + 34t_2t_3t_4^2t_5 + 24t_2t_3t_4t_5^2 + 8t_2t_3t_5^3 + 6t_2t_4^4 + 14t_2t_4^3t_5 + 8t_2t_4^2t_5^2 + t_3^5 + 6t_3^4t_4 + 6t_3^4t_5 + 15t_3^3t_4^2 + 26t_3^3t_4t_5 + 12t_3^3t_5^2 + 20t_3^2t_4^3 + 46t_3^2t_4^2t_5 + 32t_3^2t_4t_5^2 + 8t_3^2t_5^3 + 14t_3t_4^4 + 42t_3t_4^3t_5 + 36t_3t_4^2t_5^2 + 8t_3t_4t_5^3 + 4t_4^5 + 16t_4^4t_5 + 20t_4^3t_5^2 + 8t_4^2t_5^3. $$

For these three polynomials the process above is repeated (the successive part of the algorithm) for all orderings, this is because the new polynomials are no longer cyclic and we have to consider all permutations. Next iteration results only in non-negative coefficients, hence proving the case $n=5$.

For $n=7$, similarly as above we first check $6!=720$ orderings to find $72$ polynomials with a negative coefficient. Repeating the process on these the next iteration yields only polynomials with non-negative coefficients, proving the case $n=7$.

I've briefly tried $n=9$ but each iteration took too long and generated too many new polynomials to check in next iteration, so it does not seem to be efficient in the current form (not to mention $n=11$).

$\endgroup$
3
  • 1
    $\begingroup$ Very nice. So, the OP is equivalent to No. 13 of Xuezhi Yang's 22 conjecture. So my proof for $n=5$ also works for No. 13 conjecture. $\endgroup$
    – River Li
    Commented May 6, 2023 at 6:10
  • $\begingroup$ good source. did you buy a copy of the book ? $\endgroup$
    – dezdichado
    Commented May 8, 2023 at 18:54
  • 1
    $\begingroup$ @dezdichado I found a copy here $\endgroup$
    – Sil
    Commented May 9, 2023 at 13:20
-3
$\begingroup$

Just some remark :

We have the following theorem :

Define :

$$f\left(x\right)=\frac{x+b}{x+c},g\left(x\right)=f\left(1-x\right)+f\left(x\right)-f\left(1-x\right)f\left(x\right)$$

Let $b,c\in(0,1),x\in(0,1)$ such that then we have :

$$g''(x)\leq 0,g(x)-g(0)\geq 0$$

Now if :

$$h\left(x\right)=f\left(1-x\right)f\left(x\right)$$

Then for $b\leq c$ we have :

$$h(x)\geq h(0),f(1-x)$$

And if $c\leq b$ we have :

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

On the other hand we can squeeze $f(1-x)$ as we have for $c\in(0,1),b\in[0,0.2],x\in[0,1/2]$ then :

$$t\left(x\right)=\frac{\left(1-x^{2}+b\right)}{1-x^{2}+c}-\frac{5}{3}\left(x^{2}+b+c\right),\frac{\left(t\left(0\right)-t\left(\frac{1}{\sqrt{2}}\right)\right)}{0-\frac{1}{\sqrt{2}}}\sqrt{x}+t\left(0\right)\leq t\left(\sqrt{x}\right)$$





A totally different way using integral :

Consider the integral :

$$f\left(x\right)=\frac{x+b}{x+c},\int_{0}^{x}f\left(t\right)dt=h(x)-h(0),h(x)=\left(b-c\right)\ln\left(c+x\right)+x$$

Then plugging $x_i-x_{i+1}=a_ia_j$ so the sum is zero we can use A conditional negative definite quadratic form involving $\ln$ function

We start in setting $x=1$ so we have :

$$\int_{0}^{1}f\left(t\right)dt=\left(b-c\right)\ln\left(c+1\right)+1-\left(b-c\right)\ln\left(c\right)$$

using the link above in the case $n=9$ we have that the sum of difference of log is positive so we have :

$$\sum_{cyc}^{}\int_{0}^{1}f\left(t\right)dt\geq n$$

then integrating with the tangent lemma and if the sum to show is convex and the function to integrate is finite for all $x\in(\varepsilon,1]$ then we can conclude as OP did.

We have someting like :

$$g\left(x\right)=\frac{x+b}{x+c}+\frac{\left(x+a\right)}{x+d}+...+\frac{x+u}{x+v}$$

Then for $t,x\in[0,1]$ :

$$\int_{0}^{t}\left(\frac{x+b}{x+c}+\frac{\left(x+a\right)}{x+d}+...+\frac{x+u}{x+v}\right)dx-g\left(x\right)\left(t-x\right)-\int_{0}^{x}\left(\frac{y+b}{y+c}+\frac{\left(y+a\right)}{y+d}+...+\frac{y+u}{y+v}\right)dy\leq 0$$

$\endgroup$
5
  • $\begingroup$ At the end it remains to have $$b/c+(1+b)/(1+c),(1+2b)/(1+c)$$ there is one general case where it is easy to conclude . $\endgroup$ Commented May 1, 2023 at 9:37
  • $\begingroup$ @S.V.e.H Can you give me your feedback ? $\endgroup$ Commented May 2, 2023 at 11:58
  • $\begingroup$ I don't understand how you get $x_i - x_{i+1} = a_ia_j$. I also don't understand how you apply the inequality in the linked question to our problem here. $\endgroup$
    – V.S.e.H.
    Commented May 2, 2023 at 17:00
  • $\begingroup$ @S.V.e.H We have $$\sum_{i,j=1}^{n}a_{i}a_{j}=\left(\sum_{i=1}^{n}a_{i}\right)^{2}=0=\sum_{cyc}^{ }x_{i}-x_{i+1}$$. On the other hand $$\int_{0}^{1}f\left(u\right)du<f\left(x\right)$$ for $b,c,x\in[0.05,0.2]$ such that $b\leq c$ If we improve it in the case where the variable are decreasing we have one case for $n=9$ . $\endgroup$ Commented May 2, 2023 at 18:39
  • $\begingroup$ @S.V.e.H I found a condition to have the inequality in the general case .If the sum $g(x)$ is convex so we have : $$\frac{\left(\int_{0}^{1}g\left(x\right)dx-\int_{0}^{x}g\left(y\right)dy\right)}{1-x}\leq g(x)$$ but with the linked question we have $$\left(\int_{0}^{1}g\left(x\right)dx-\int_{0}^{x}g\left(y\right)dy\right)-n\left(1-x\right)\geq 0$$ which makes the inequality true .Can you give me your feedback again ? . $\endgroup$ Commented May 4, 2023 at 8:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .