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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.