Let $[q]:=\{1,2,3, \ldots,q\}$, where $q$ is a positive integer. Consider a vector $\underline{\alpha}=(\alpha_A)_{A\subseteq [q], A\neq \emptyset}$, where each $\alpha_A \in \mathbb{R}$. Note that such a vector $\underline{\alpha}$ has $2^q-1$ entries.
Given such an $\underline{\alpha}$, we define the following:
$$ F(\underline{\alpha}):=\sum_{A\neq \emptyset} \alpha_A \log(|A|), \quad v(\underline{\alpha})=\sum_{A\neq \emptyset} \alpha_A, \quad E(\underline{\alpha})=\sum_{\{ \{A,B\}: A,B \subseteq [q], A\cap B=\emptyset \}} \alpha_A \alpha_B, $$
where the sum in the definition of $E(\underline{\alpha})$ is taken over all unordered pairs of disjoint subsets of $[3]$.
Define $T(1/4)=\{\underline{\alpha}: \alpha_A \geq 0 \text{ for all nonempty A },\, v(\underline{\alpha})=1, \, E(\underline{\alpha})\geq 1/4 \}$.
I believe that the following is true: $$ \max_{\underline{\alpha} \in T(1/4) } F(\underline{\alpha})=\frac{\log(\lfloor q/2 \rfloor \cdot \lceil q/2 \rceil)}{2}. $$
I know that it is true when $q$ is even (it was proven), but I want to show that it also holds for odd $q$. I have verified that this is true for $q=3,5,7,9$ using SageMath, but would like to prove it by hand for general odd $q$.
I think that this problem can be solved using the language of probability. It is natural to do so given that the sum $v(\underline{\alpha})=\sum \alpha_A=1$ in the set $T(1/4)$.
Consider a random variable $X$ on $2^{q}\setminus \{\emptyset\}$ (the power set of $[q]$, excluding the empty set) such that $\mathbb{P}[X=A]=\alpha_A$, where $A \subseteq [q]$.
Note that $2\cdot E(\underline{\alpha})$ can be interpreted as the probability that from the sets in $2^{[q]}\setminus \{\emptyset\}$ one selects two disjoint sets $A$ and $B$. Since by definition of $T(1/4)$, $2\cdot E(\underline{\alpha}) \geq 1/2$, we see that we are more likely to select two disjoint sets rather than two sets which have a nonempty intersection.
One can verify that the set $T(1/4)$ is compact, so there exists some $\underline{\alpha}^*\in T(1/4)$ for which $F(\underline{\alpha}^*)=\max_{\underline{\alpha} \in T(1/4) } F(\underline{\alpha})$. I conjecture that this vector $\underline{\alpha}^*$ has exactly 2 nonzero entries $\alpha^*_{A_1}=1/2$ and $\alpha^*_{A_2}=1/2$, where $|A_1|=\lfloor q/2 \rfloor$, $|A_2|=\lceil q/2 \rceil$, $A_1\cap A_2 =\emptyset$, and $A_1\cup A_2=[q]$. That is, the sets $A_1$ and $A_2$ form a partition of the first $q$ positive integers and their sizes are as equal as possible.
If it is difficult to prove this for general odd $q$, how would I prove it for, say, $q=5$? I would like to avoid using Lagrange multipliers with so many variables.
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment