# Unbalancing lights in higher dimensions

In ''The Probabilistic Method'' by Alon and Spencer, the following unbalancing lights problem is discussed. Given an $n \times n$ matrix $A = (a_{ij})$, where $a_{ij} = \pm 1$, we want to maximise the quantity

$x^T A y = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i y_j$

over all $n$-dimensional vectors $x$, $y$ such that $x_i,y_j = \pm 1$. The name of the problem comes from interpreting $A$ as a grid of lights that are on or off, and $x$ and $y$ as sets of light switches, each associated with a row or column (respectively); flipping a switch flips all lights in that row or column, and the goal is to maximise the number of lights switched on.

Let $m(A)$ be the maximum of $x^T A y$ over $x$ and $y$ such that $x_i,y_j = \pm 1$. As Alon and Spencer discuss, for any $A$ it is possible to show that $m(A) \ge C n^{3/2}$ for some constant $0<C<1$. On the other hand, there is an explicit family of matrices $A$ such that $m(A) = n^{3/2}$.

It is natural to generalise this problem to $n \times n \times \dots \times n$ arrays $A$ containing $\pm 1$ entries, writing

$A(x^1,\dots,x^d) := \sum_{i_1,\dots,i_d=1}^n a_{i_1\dots i_d} x^1_{i_1} x^2_{i_2} \dots x^d_{i_d}$

and defining $m(A)$ as the maximum of $A(x^1,\dots,x^d)$ over $x^1,\dots,x^d$, each of which is again an $n$-dimensional vector of $\pm 1$'s. Now it is known (and fun to prove!) that for this "$d$-dimensional" variant, one can always achieve $m(A) \ge C^d n^{(d+1)/2}$ for some universal constant $C$ between 0 and 1, and on the other hand there exists a family of $A$'s with $m(A) = n^{(d+1)/2}$.

My question is: can the lower bound be improved to $m(A) \ge C n^{(d+1)/2}$ for some universal constant $C>0$? Or even just improved so that the dependence on $d$ is subexponential? Conversely, can the upper bound be reduced?

Background

Finding a lower bound on $m(A)$ in the more general case where $A$ is an arbitrary bilinear form was considered by Littlewood back in 1930. The bound above for the $d$-dimensional case is a special case of a bound for general $d$-linear forms which was proven later by Bohnenblust and Hille. In the functional analysis literature, the quantity $m(A)$ is known as the injective tensor norm of $A$; this norm, and the above results, are discussed extensively in the book Analysis in Integer and Fractional Dimensions by Ron C. Blei. However, I could not find any information about whether the bounds can be improved.

-

Belatedly answering my own question: Pellegrino and Seoane-Sepulveda have shown the lower bound that $m(A) \ge n^{(d+1)/2}/\text{poly}(d)$. As far as I know, it is still open whether the $\text{poly}(d)$ term can be replaced with a universal constant.