In ''[The Probabilistic Method](http://books.google.com/books?id=V8YgNioxF6AC&printsec=frontcover&dq=probabilistic+method&hl=en&src=bmrr&ei=55eLTZ6YNM-WhQeE94yyDg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CDAQ6AEwAA#v=onepage&q&f=false)'' 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](http://qjmath.oxfordjournals.org/content/os-1/1/164.extract) 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](http://www.jstor.org/pss/1968255). 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](http://books.google.com/books?id=QC_KALDZw5wC&printsec=frontcover&dq=analysis+blei&hl=en&ei=vJOLTZzXJMLAhAeyqZ2nDg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCgQ6AEwAA#v=onepage&q&f=false) by Ron C. Blei. However, I could not find any information about whether the bounds can be improved.



Unbalancing lights in higher dimensions
Belatedly answering my own question: Pellegrino and Seoane-Sepulveda have [shown](http://arxiv.org/pdf/1010.0461.pdf) 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.


