Conjecture on maximum of symmetric combinatoric function

Question

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture).

(The question was first asked at math.SE, where (even after 2.5months and 2 rounds of bounty) there is only one special-case-solution and one additional insight on concavity. So I'm hoping to get some more insights here).

The problem

There are $n$ different objects $A_1,...,A_n$, and there are sets containing $m$ different $A_i$s: $C_i=(A_{i_1}, A_{i_2}, ..., A_{i_m})$. There are $i_{max}=\binom{n}{m}$ different combinations $C_i$. Each combination $C_i$ has a probability $p_i$ (with $\sum_{i=1}^{i_{max}} p_i=1$).

Defining the function

For a given pair of objects $A_k$ and $A_l$:

• $f_1(k,l)$ contains all probabilities $p_i$ of the sets $C_i$, which contains both objects $A_k$ and $A_l$.
• $f_2(k,l)$ contains all probabilities $p_i$ of the sets $C_i$, which contains either object $A_k$ or $A_l$ (if it contains both elements, we add $p_i$ twice).
• $F(k,l)=\frac{f_1(k,l)}{f_2(k,l)}$

With that, we get the main-function $$D^{(n,m)}=\sum_{k=1}^{n-1} \sum_{l=k+1}^{n} F(k,l)$$

What is the maximum of $D^{(n,m)}$, given that the sum of all probabilities $p_i$ is 1?

Alternative notation

As pointed out by Wolfgang in a comment, the function $D^{(n,m)}$ can be written in a more intuitive way by the form: $$D^{(n,m)}=\sum_{i<j}\frac{\sum \{p_I|I \ni x,y \}}{\sum \{p_I|I \ni x\} + \sum \{p_I|I \ni y \}}$$ where $I$ denotes any m-subset of [n].

Special cases

n=2, m=2

This is a trivial case. We have two objects $A_1$ and $A_2$, and only one set of combinations $C_1=(A_1,A_2)$ with $p_1$.

Thus $f_1(1,2)=p_1$, $f_2(1,2)=p_1+p_1$. This leads to $D^{(2,2)}=F(1,2)=\frac{1}{2}$.

Every other case with $n=m$ can be solved easily by $D^{(n,m)}=\frac{1}{n}$

---

n=3, m=2

This case is simple (but not trivial) and I found a solution:

We have n=3 objects $A_1$, $A_2$ and $A_3$, and combinations $C_i$ of m=2 objects $C_1$=($A_1$, $A_2$), $C_2$=($A_1$, $A_3$), $C_3$=($A_2$, $A_3$), with $p_1$, $p_2$, $p_3$ respectivly.

For k=1, l=2 we have $f_1(1,2)=p_1$ (because only $C_1$ contains both $A_1$ and $A_2$), and $f_2(1,2)=2p_1+p_2+p_3$ (because $A_1$ is contained in $C_1$ and $C_2$ and $A_2$ is in $C_1$ and $C_3$).

So we get $$D^{(3,2)}=F(1,2) + F(1,3) + F(2,3) = \frac{p_1}{2p_1+p_2+p_3} + \frac{p_2}{p_1+2p_2+p_3} + \frac{p_3}{p_1+p_2+2p_3}$$ A maximum can be found easily (due to normalisation of $p_1+p_2+p_3=1$): $$D^{(3,2)} = \frac{p_1}{1+p_1} + \frac{p_2}{1+p_2} + \frac{p_3}{1+p_3}$$ so each term can be maximized individually, which gives $D^{(3,2)}=\frac{3}{4}$ for $p_1=p_2=p_3$.

---

n=4, m=2

We have four objects $A_1$, $A_2$, $A_3$, $A_4$, and six combinations $C_1=(A_1,A_2)$, $C_2=(A_1,A_3)$, ..., $C_6=(A_3, A_4)$.

Therefore we get: $$D^{(4,2)} = \frac{p_1}{2p_1+p_2+p_3+p_4+p_5} + \frac{p_2}{p_1+2p_2+p_3+p_4+p_6} + \frac{p_3}{p_1+p_2+3p_3+p_5+p_6} + \frac{p_4}{p_1+p_2+2p_4+p_5+p_6} + \frac{p_5}{p_1+p_3+p_4+2p_5+p_6} + \frac{p_6}{p_2+p_3+p_4+p_5+2p_6}$$

I was not able to find a method for proving a global maximum.

---

n=4, m=3

We have $C_1=(A_1,A_2,A_3)$, $C_2=(A_1,A_2,A_4)$, $C_3=(A_1,A_3,A_4)$, $C_4=(A_2,A_3,A_4)$, which gives

$$D^{(4,3)}=\frac{p_1+p_2}{2p_1+2p_2+p_3+p_4}+\frac{p_1+p_3}{2p_1+p_2+2p_3+p_4}+\frac{p_1+p_4}{2p_1+p_2+p_3+2p_4}+\frac{p_2+p_3}{p_1+2p_2+2p_3+p_4}+\frac{p_2+p_4}{p_1+2p_2+p_3+2p_4}+\frac{p_3+p_4}{p_1+p_2+2p_3+2p_4}$$

This case can be simplified aswell, similar to $n=3,m=2$ case to $$D^{(4,3)}=\frac{p_1+p_2}{1+p_1+p_2}+\frac{p_1+p_3}{1+p_1+p_3}+\frac{p_1+p_4}{1+p_1+p_4}+\frac{p_2+p_3}{1+p_2+p_3}+\frac{p_2+p_4}{1+p_2+p_4}+\frac{p_3+p_4}{1+p_3+p_4}$$

but I'm not able to find any further method to calculate the maximum.

Conjecture

The two cases I solved had a maximum at equal $p_i=\frac{1}{\binom{n}{m}}$. Furthermore, the function $D^{(n,m)}$ is very symmetric, so I expect that the maximum is always at $p_1=p_2=...=p_i$. Numerical search up to n=7 confirms my expectation (but I'm not 100% sure about my Mathematica-based numerical maximization).

Questions

1. How can you prove (or disprove) that the maximum for $D^{(n,m)}$ for arbitrary $n$ and $m$ is always at $p_1=p_2=...=p_i$?
2. Is there literature on similar problems or is this function even known? Has the similarity to the Shapiro inequality some significance or is it just a coincidence?
3. Is there a better (maybe geometrical) interpretation of this function?
4. Can you find solutions for any other special case than $n=m$ (always trivial) and $n=3,m=2$? (See solution for $m=n-1$ and $m=2, n=4$ at math.SE)

Answer 1

Indeed, I have just made things overly complicated in my approach. Thanks to JiK, I now see it fairly clearly.

Let $(\{S\},P_S)$ be our probability space and let $X_k$ be the event $S\ni k$. Let $u_k=EX_k$. Note that at each $S$ there are exactly $m$ values $X_k=1$ and the rest are $0$. What we need to control is just $\sum_{k,j}E\frac{X_kX_j}{u_k+u_j}$ (adding a few $\frac 12$'s corresponding to $k=j$ does not hurt). Now write it as $$ E\int_0^{\infty}\left[\sum_k X_ke^{-u_kt}\right]^2\,dt\le mE\int_0^\infty \sum_kX_ke^{-2u_kt}\,dt=\frac {mn}2\,, $$ and when all $u_k$ are equal $m/n$, we have an identity.

Edit As NicoDean requested, here is exactly the same proof without the word "probability" (or anything like that).

1.Setup: We have the set $U$ of all $m$-subsets of $\{1,\dots,n\}$ and with each such subset $S$, a positive number $p_S$ is associated, so that the sum of all numbers is $1$.

2.Functions $X_k$: For $k=1,\dots,n$, define the function $X_k:U\to\mathbb R$ by $X_k(S)=1$ if $k\in S$ and $X_k(S)=0$ if $k\notin S$.

3.The numerator and the denominator: $$ N(k,j)=\sum_{S:k,j\in S}p_S=\sum_{S\in U}p_SX_k(S)X_j(S) $$ This is exactly what stands in the numerator if $k\ne j$. If $k=j$, then $X_k(S)^2=X_k(S)$, so $$ N(k,k)=\sum_{S:k\in S}p_S=\sum_{S\in U}p_SX_k(S)\,, $$ which is "one half" of the denominator (another half is $N(j,j)$). We shall also denote $N(k,k)$ by $u_k$ to make our notation here agree with that in the "probabilistic" version of the argument.

4.The sum of fractions: The sum we want to maximize is $\sigma=\sum_{k<j}\frac{N(k,j)}{N(k,k)+N(j,j)}$. Note that $\frac{N(k,k)}{N(k,k)+N(k,k)}=\frac 12$ and that the sum over $k>j$ is the same as the sum over $k<j$, so $$ \Sigma=\frac n2+2\sigma=\sum_{k,j}\frac{N(k,j)}{N(k,k)+N(j,j)}\,. $$ At last, to maximize $\Sigma$ is the same as to maximize $\sigma$.

5.The weighted sum representation: We now replace $N(k,j)$ with its sum representation from Part 3 but treat $N(k,k)=u_k$ and $N(j,j)=u_j$ as positive numbers. Swapping the order of summation, we get $$ \Sigma=\sum_{S\in U}p_S\sum_{k,j}\frac{X_k(S)X_j(S)}{u_k+u_j}\,. $$

6.The square formula: If we had no denominator in the summands, we could write the inner sum $\sum_{k,j}X_k(S)X_j(S)$ as $\left[\sum_{k}X_k(S)\right]^2$. We could also use this trick if we had $v_kv_j$ instead of $\frac{1}{u_k+u_j}$, in which case the representation would be $\left[\sum_{k}X_k(S)v_k\right]^2$. Unfortunately, our actual factor (inverse sum) does not look like a product, or does it?

7.The Cauchy-Gram trick: While many expressions like the one we have cannot be written as usual products of numbers, one of which depends on $k$ only and one of which depends on $j$ only, they can often be written as a mixture of such products, i.e., as integrals $\int_a^b v_k(t)v_j(t)\,dt$ for some appropriate choice of the functions $v_k$ and the interval of integration. Note, by the way, that such representation, if it exists, is never unique: you can always make any change of variable in the integral and get a new one. In this case, the representation we'll get will be $\int_a^b\left[\sum_{k}X_k(S)v_k(t)\right]^2\,dt$, which often is just as good as a single square.

8.The exponential functions: The fact that we need to replace the sum by the product suggests that there will be some exponentiation (or raising to the power, or logarithm) somewhere. To put the parameter to the denominator, the formula $\frac 1u=\int_0^\infty v(ut)\,dt$ valid for any integrable function $v:[0,+\infty)\to\mathbb R$ with total integral $1$ is often used. Since, as I said, we need to turn the sum into the product, $v(x)=e^{-x}$ becomes a natural choice here. So, putting $v_k(t)=e^{-u_kt}$, we get just the representation $$ \sum_{k,j}\frac{X_k(S)X_j(S)}{u_k+u_j}=\int_0^\infty\left[\sum_k X_k(S)e^{-u_kt}\right]^2\,dt $$ we need.

9.The Cauchy (Arithmetic mean-Quadratic mean) inequality: It is $\left[\sum_{i\in I}w_i\right]^2\le |I|\sum_{i\in I}w_i^2$ where $|I|$ is the number of terms in the sum. The equality holds when all terms are equal. Note that we can improve the right hand side a bit if instead of all terms, we count just the non-zero ones. Then the inequality becomes an equality if all non-zero terms are equal.

10. The final count: Applying the Cauchy inequality to our innermost sum and taking into account that for each $S\in U$, we have exactly $m$ values of $k$ for which $X_k(S)\ne 0$ (namely, $k\in S$, when $X_k(S)=X_k(S)^2=1$), we get $$ \left[\sum_k X_k(S)e^{-u_kt}\right]^2\le m\sum_k X_k(S)^2e^{-2u_kt}\,. $$ Plugging this estimate into the integral, we estimate the integral for each fixed $S$ by $$ m\sum_k X_k(S)^2\int_0^\infty e^{-2u_kt}\,dt=m\sum_k \frac{X_k(S)}{2u_k}\,. $$ (The square or any other positive power on $X_k(S)$ can be just ignored because it is always $0$ or $1$). Finally, summing these estimates with the coefficients $p_S$ and swapping the order of summation, we get $$ \Sigma\le m\sum_k\frac 1{2u_k}\sum_{S\in U}p_SX_k(S)=m\sum_k\frac 1{2u_k}N(k,k)= m\sum_k \frac 12=\frac{mn}{2}\,. $$

Answer 2

If the conjecture is true for $m=2$, it is true in the general case.

Denoting $p_{x,y} = \sum \{p_I|I\ni x,y\} $ and $p_x = \sum \{p_I|I\ni x\} $, we get necessary conditions $ (m-1) p_x = \sum_{y\neq x} p_{x,y}$ and $\sum_{x< y} p_{x,y} = \binom{m}{2}$. The target function has the value $$ D^{(n,m)} = \sum_{x<y} \frac{p_{x,y}}{\frac{1}{m-1}\sum_{z\neq x} p_{x,z} + \frac{1}{m-1}\sum_{z\neq y} p_{y,z} }. $$

Defining $q_{x,y} = p_{x,y}/\binom{m}{2}$ gives $$ D^{(n,m)} = (m-1) \sum_{x<y} \frac{q_{x,y}}{\sum_{z\neq x} q_{x,z} + \sum_{z\neq y} q_{y,z} } $$ with $\sum_{x<y} q_{x,y} = 1$. We may interpret $q_{x,y}$ as the probabilities of $2$-sets in the case $m=2$, and thus we get the relation $$ \max D^{(n,m)} \leq \max (m-1) D^{(n,2)}. $$ This is not an equality because it is not clear if the optimal choice of the values $q_{x,y}$ can be achieved in the general case.

If the original conjecture is true for $m=2$, the maximum of $D^{(n,2)}$ is obtained when $q_{x,y}$ are equal. In particular, the maximum of $D^{(n,m)}$ is achieved when $p_I$ are equal (and possibly at some other points, too, but uniqueness was not required in the conjecture).