Upper bounds for the constants of Bennett's inequality and the Gale--Berlekamp switching game

Abstract

In $1977$, G. Bennett proved, by means of non-deterministic methods, an inequality which plays a fundamental role in a series of optimization problems. More precisely, Bennett's inequality shows that, for $p_1,p_2\in [1,\infty ]$ and all positive integers $n_1,n_2$, there exists a bilinear form $A_{n_1,n_2}:\left({\mathbb{R}}^{n_1},{\Vert \cdot \Vert }_{p_1}\right)\times \left({\mathbb{R}}^{n_2},{\Vert \cdot \Vert }_{p_2}\right)⟶\mathbb{R}$ with coefficients $\pm 1$ satisfying \[ \left\Vert A_{n_{1},n_{2}}\right\Vert \leq C_{p_{1},p_{2}}\max\left\{ n_{1}^{1-\frac{1}{p_{1}}}n_{2}^{\max\left\{ \frac{1}{2}-\frac{1}{p_{2} },0\right\} },n_{2}^{1-\frac{1}{p_{2}}}n_{1}^{\max\left\{ \frac{1}{2} -\frac{1}{p_{1}},0\right\} }\right\} \] for a certain constant $C_{p_1,p_2}$ depending just on $p_1,p_2$; moreover, the exponents of $n_1,n_2$ cannot be improved. In this paper, using a constructive approach, we prove that $C_{p_1,p_2}\le \sqrt{8/5}$ whenever $p_1,p_2\in \left[2,\infty \right]$ or $p_1=p_2=p\in \left[1,\infty \right]$. Our techniques are applied to provide new upper bounds for the constants of a combinatorial game, known as Gale--Berlekamp switching game or unbalancing lights problem. As a consequence, we improve estimates obtained by Brown and Spencer in $1971$ and by Carlson and Stolarski in $2004$.

arXiv commentarXiv admin note: text overlap with arXiv:2006.12892