Timeline for The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$

4 events

when toggle format	what		by	license	comment
Jun 27, 2017 at 18:38	comment	added	fedja		Of course, not! The sum of squares has the minimum $n^2/d$ more often than not (any time you can write $nI=\sum_i v_i\otimes v_i$ with unit length vectors $v_i$). What I mean is that the difference between the sum and the sum of squares can be at most $d/4$, so the Gram matrix may have only $O(d/\varepsilon)$ elements with absolute values between $\varepsilon$ and $1-\varepsilon$. From there it is easy to see that the minimizing configuration must consist of $d$ bunches of nearly coinciding vectors and different bunches are nearly orthogonal. After that the local analysis is not hard at all.
Jun 27, 2017 at 18:22	comment	added	Fedor Petrov		@fedja You mean that for large $n$ even the sum of squares has the same minimizer?
Jun 27, 2017 at 16:42	comment	added	fedja		Actually, combined with the argument from my post, this idea allows one to prove the sharp bound for the case $n\ge N_0(d)$ (I'm too lazy to estimate $N_0(d)$ now but it is surely at most polynomial in $d$). Also it is easy to do the case $d<n\le 2d$ by simple induction. This makes the conjecture in question extremely plausible (though I'm somewhat short of the full proof yet).
Jun 26, 2017 at 5:38	history	answered	Fedor Petrov	CC BY-SA 3.0