A Conjecture

Introduction

I wrote this post Exploring an Inequality last month, and I still don’t have a mathematical proof of the inequality. This shows that my maths ability is not strong 😢!

In this post, I will present a conjecture related to the inequality from the previous post. I have investigated the conjecture and I am confident that it holds true.

A conjecture

Let $n$ be an integer $\ge 2$. For a fixed $n$, randomly choose $n$ non-negative numbers,

$$ x_1,\ \ldots,\ x_n; $$

let $P$ denote a permutation of the $n$ numbers. For example, in the case $n=4$, when four non-negative numbers $x_1,\ x_2,\ x_3$ and $x_4$ are chosen, there are $24$ permutations for these four numbers. One permutation can be

$$ P = (x_3,\ x_1,\ x_4,\ x_2), $$

and in this case

$$ P[1] = x_3,\ P[2] = x_1,\ P[3] = x_4,\ \hbox{and}\ P[4] = x_2. $$

Define

$$ f(P) = \sum_{i=1}^n \frac{P[i]}{1 + x_i}. $$

Then $f(P)$ attains its minimum at $P=(x_1,\ x_2,\ \ldots, x_n)$.

When $n = 2$, it’s pretty easy to prove the statement in the above conjecture. When $n\ge 3$, at this point, I am not able to provide a mathematical proof of the statement. Sorting to the brute force, I have verified the conjecture with the following R code, and based on the numerical evidence, I believe the conjecture must hold true.

R code

library(combinat) # for permn

helper_func <- function(func_name, para = NULL, n)
{switch(func_name,
        "runif" = runif(n, min = para[['min']], max = para[['max']]),
        "rchisq" = rchisq(n, df = para[['df']]),
        "rexp" = rexp(n),
        "rnorm" = rnorm(n))
        
}

a_simu <- function(rand_nbr_func, para, n)
{the_nbrs <- helper_func(rand_nbr_func, para, n)
 a_list <- permn(the_nbrs)

 op <- function(x) {sum(x / (1 + the_nbrs))}

 re <- vapply(a_list, op, FUN.VALUE = numeric(1))
 return(min(re) == re[1])
}

set.seed(12345)
N <- 10000 


# testing the case n = 3 --------------------------------------------------
# test 1
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "runif", 
                                   para = list('min' = 0, 'max' = 1), 
                                   n = 3))
(sum(simu_re) == N)

## [1] TRUE

# test 2
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "runif", 
                                   para = list('min' = 0, 'max' = 100),
                                   n = 3))
(sum(simu_re) == N)

## [1] TRUE

# test 3
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "rexp", n = 3))
(sum(simu_re) == N)

## [1] TRUE

# test 4
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "rchisq", 
                                   para = list('df' = 10),
                                   n = 3))
(sum(simu_re) == N)

## [1] TRUE

# test 5: Can we remove the assumption of "non-negative"
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "rnorm", n = 3))
(sum(simu_re) == N)

## [1] FALSE

# testing the case n = 4 --------------------------------------------------
# test 1
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "runif", 
                                   para = list('min' = 0, 'max' = 1), 
                                   n = 4))
(sum(simu_re) == N)

## [1] TRUE

# test 2
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "runif", 
                                   para = list('min' = 0, 'max' = 100),
                                   n = 4))
(sum(simu_re) == N)

## [1] TRUE

# test 3
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "rexp", n = 4))
(sum(simu_re) == N)

## [1] TRUE

# test 4
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "rchisq", 
                                   para = list('df' = 10),
                                   n = 4))
(sum(simu_re) == N)

## [1] TRUE

# testing the case n = 5 --------------------------------------------------
# test 1
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "runif", 
                                   para = list('min' = 0, 'max' = 1), 
                                   n = 5))
(sum(simu_re) == N)

## [1] TRUE

# test 2
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "runif", 
                                   para = list('min' = 0, 'max' = 100),
                                   n = 5))
(sum(simu_re) == N)

## [1] TRUE

# test 3
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "rexp", n = 5))
(sum(simu_re) == N)

## [1] TRUE

# test 4
simu_re <- replicate(n = N, a_simu(rand_nbr_func = "rchisq", 
                                   para = list('df' = 10),
                                   n = 5))
(sum(simu_re) == N)

## [1] TRUE

Update on 28 October 2024

I sent the conjecture to Dr. Petros Hadjicostas. He quickly gave a proof as follows.

Let $y_i = 1 + x_i$. Then, the inequality is equivalent to

$$ \sum_{i=1}^n \frac{Q[i]}{y_i} \ge n, $$

where $Q$ is a permutation of $(y_1,\ \ldots, y_n)$ and $Q[i]$ is the $i$th component of $Q$. Using the well known result

$$ \hbox{arithmetic mean}\ge \hbox{gemometric mean}, $$

we can easily establish the above equivalent inequality.