$O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products

Question

Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game:

1. Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. Each of these is assigned to a pair of entries $i,j\in[n], i\neq j$ in some pre-determined way (e.g., placed in a strictly triangular matrix).
2. Given this $\epsilon$, choose any sequence of $n$ points $\{v_i\}_{i=1}^n$ (duplicates allowed) on the unit hypersphere $\mathcal{S}^{d-1}$.
3. The value of the game is equal to the sum of the products of each $\epsilon_{i,j}$ with the corresponding inner product $v_i^\top v_j$.

You can think of this as choosing a set of $n$ points and then assigning a weight of $\pm 1$ to each pair's inner product, except that we get to see all the $\pm 1$ values before choosing the points. For example, suppose $d=2,n=3$ and $\epsilon = (+1, +1, +1)$, then choosing $v_1 = v_2 = v_3$ will have value 3, since each inner product is 1. However, if $\epsilon = (-1, -1, -1)$, it's less clear (I imagine spacing them out evenly giving a value of $-3cos(\frac{2\pi}{3})$).

Since $\epsilon$ is drawn uniformly, the minimum expected value of this game is the negation of the maximum, so either will do. I've been trying to bound it for specific patterns of $\epsilon$ even, without regard to the distribution, but have had no luck so far. I've also tried writing it as an optimization problem but it is difficult to work with except for very benign $\epsilon$ (such as those that make it convex/concave).

A trivial upper bound is $O(n^2)$, but in general I would expect this to grow slower than that, and I have little intuition for how it should grow with $d$. Honestly, even something slightly smaller such as $O(n^{(2-\epsilon)}\cdot\text{poly}(d))$ would be a useful result for my purposes (overloading $\epsilon$ here to mean a very small positive value).

Answer 1

Let $\lambda$ be the largest eigenvalue of the symmetric matrix $M_{ij}$ with diagonal entries $0$ and off-diagonal entries $\epsilon_{ij}$.

Then

$$\sum_{1\leq i<j\leq n} \epsilon_{ij} v_i v_j^T =\sum_{1\leq i<j\leq n} \epsilon_{ij} \sum_{k=1}^d v_{i,k } v_{j,k} = \sum_{k=1}^d \sum_{1\leq i<j\leq n} \epsilon_{ij} v_{i,k } v_{j,k} \leq \sum_{k=1}^d \frac{\lambda}{2} \sum_{i=1}^n v_{i,k}^2 = \frac{\lambda}{2} \sum_{i=1}^n \sum_{k=1}^d v_{i,k}^2 = \frac{\lambda}{2} \sum_{i=1}^n |v_i|^2 = \frac{n \lambda}{2}. $$

Here the only non-formal calculation is the inequality $w^T M w \leq \lambda |w|^2$ for a symmetric matrix $M$ with largest eigenvalue $\lambda$.

By random matrix theory, the expected value of the largest eigenvalue of such a random matrix is going to be, I think, $O(n^{1/2})$, so your game has expectation at most $O(n^{3/2})$.

Answer 2

This is correct.

Consider a random symmetric matrix $A=(a_{ij})$, $a_{ij}=a_{ji}=\epsilon_{ij}/2$, $a_{ii}=0$.

Let $u_1,\ldots,u_n$ be your $n$ points on the sphere $\mathcal{S}^{d-1}$. Denote $u_i=(u_{i1},u_{i2},\ldots,u_{id})$, $\sum_s u_{is}^2=1$. Consider $d$ vectors in $\mathbb{R}^n$: $f_s=(u_{1s},\ldots,u_{ns})^t$ for $s=1,\ldots,d$ (an uppercase $t$ denotes the transposition). Then your sum equals $$ \sum_{i,j} a_{ij}\langle u_i,u_j \rangle=\sum_{s=1}^d \sum_{i,j}a_{ij} u_{is}u_{js}=\sum_{s=1}^d \langle Af_s, f_s\rangle \leqslant C\sum_{s=1}^d \|f_s\|^2=Cn, $$ where $C$ is the maximal absolute value of the (random) matrix $A$. So, we want to prove that $C$ is small enough, like $O(n^{1-\delta})$ (sorry, I do not like your $\epsilon$ here, because you previously used $\epsilon$ in other context.)

This may be done, for example, by considering the sum $\Phi$ of fourth powers of eigenvalues: it equals $\sum a_{ij}a_{jk}a_{kl}a_{li}$, and the expectation of each such guy for which all $i,j,k,l$ are distinct equals 0. We are remained with expressions like $a_{ij}^2a_{ki}^2$, thus the expected value of $\Phi$ is, say, at most $n^3$. Therefore the expected value of $C$ is at most $n^{3/4}$, and the probability that $C>n^{3/4+1/100}$ is already small for large $n$.

This may be improved (and a lot is known about eigenvalues of such random matrices), but as I understand for your goals that's enough.