The Question
Let $p\in\mathbb{R}^d_{\geq 0}$ with $\sum\limits_{i=1}^d p_i = 1$ be a probability vector. Define the matrices $a=(a_{ij})_{i,j}$, $g=(g_{ij})_{ij}\in\mathbb{R}^{d\times d}$ via \begin{align*} a_{ij} = \frac{p_i + p_j}{2},\quad g_{ij}=\sqrt{p_i p_j}. \end{align*} Denote by $a_k^\downarrow$ and $g_k^\downarrow$ the $k^{\textrm{th}}$ largest entry of $a$ and $g$, respectively. Define, for a function $h:\mathbb{N}\to\mathbb{N}$ to be determined, \begin{align*} A = \sum\limits_{k=1}^{h(d)} a_k^\downarrow,\quad G = \sum\limits_{k=1}^{h(d)} g_k^\downarrow. \end{align*}
What is the largest integer $h(d)$ s.t. $A+G\leq d$ holds for any probability vector $p$ with $d$ entries?
The Attempts
We can prove the following:
- The claim is true for $h(d)=\lfloor 2d-2\sqrt{2d}+1\rfloor$. This can be seen by upper-bounding $G$ via the Cauchy-Schwarz inequality and $A$ by $\frac{h(d)+1}{2}$.
- If we were dealing only with $A$, the sum of largest arithmetic means, the optimal choice for $h(d)$ would be $2d-2$. (The "worst-case" probability vector in this case is a standard unit vector.)
- If we were dealing only with $G$, the sum of largest geometric means, the optimal choice for $h(d)$ would be $d^2$. (The "worst-case" probability vector in this case is the one describing a uniform distribution.)
- The optimal choice for $h(d)$ has to satisfy $h(d)\leq 2d-2$. (By explicitly constructing a counterexample, we see that nothing better can be achieved. If you're interested, you can find more details in Examples $4.12$ and $4.17$ in our paper linked below.)
After doing some (admittedly not too sophisticated) numerics, we believe that the optimal choice for $h(d)$ should be $2d-5$.
The Background
My friend and colleague Benedikt and I came across this problem in our work on "Necessary Criteria for Markovian Divisibility of Linear Maps" (https://arxiv.org/abs/2009.06666). There, our argument relies on bounding, for every $\mathcal{L}\in\mathbb{C}^{d\times d}$, $$\left\lVert\overline{\mathcal{L}} \otimes \mathcal{L} + \overline{\mathcal{L}^\dagger} \otimes \mathcal{L}^\dagger - \operatorname{Id}_d \otimes \mathcal{L}^\dagger \mathcal{L} - \overline{\mathcal{L}^\dagger \mathcal{L} } \otimes \operatorname{Id}_d\right\rVert_{1,k}\leq 2d \lVert\mathcal{L}\rVert_F^2.$$ Here, $\operatorname{Id}_d$ denotes the $d\times d$ identity matrix, $\lVert\cdot\rVert_F$ is the Frobenius norm and $\lVert A\rVert_{1,k}:=\sum\limits_{\ell=1}^k s_\ell^\downarrow(A)$ is the $k^{\textrm{th}}$ Ky Fan norm of $A$.
After a triangle inequality, writing out the singular values and w.l.o.g. normalizing the Frobenius norm of $\mathcal{L}$ to be $1$, this becomes exactly the question that this post is about. In our paper, we have written it down as Conjecture $4.19$.
This is my first question on stackexchange, so if you have suggestions for how I can improve the question itself, please let me know. Otherwise, I would of course be even happier about suggestions for how to solve the question ;)