Skip to main content
4 of 11
added 55 characters in body
Taras Banakh
  • 41.8k
  • 3
  • 74
  • 183

The largest $\ell_p$-norm of a sum of rows of a Sylvester-Hadamard-Walsh matrix

Given any $n\in\mathbb N$, consider the the Sylvester-Hadamard-Walsh matrix $M=(a_{i,j})_{i,j\in 2^n}$ of size $2^n\times 2^n$ and for a number $p\in[1,\infty)$, let $$\nu_{n,p}=\max_{F\subseteq 2^n}\Big(\sum_{j\in 2^n}\big|\sum_{i\in F}a_{i,j}\big|^p\Big)^{1/p}.$$ For $p=2$, the Pithagoras Theorem and the orthogonality of the rows of the matrix $M$ imply that $\nu_{n,2}=2^n$. Using this equality, it is easy to show that $\nu_{n,p}=2^n$ for all $p\in[2,\infty)$.

If $p\in[1,2]$, then by the Holder inequality, we obtain $$2^n\le\nu_{n,p}\le 2^{n(\frac1p+\frac12)}.$$ In particular, $2^n\le\nu_{n,1}\le 2^{3n/2}$. On the other hand, computer calculations show that $\nu_{n,1}$ is much smaller than $2^{3n/2}$: $$ \begin{array}{c|c|c|c} n&2^n&\nu_{n,1}&\lfloor 2^{3n/2}\rfloor\\ \hline 0&1&1&1\\ 1&2&2&2\\ 2&4&6&8\\ 3&8&14&22\\ 4&16&40&64\\ 5&32&\ge 96&181\\ 6&64&??&512 \end{array} $$

Problem 1. Is $\nu_{n,1}\ge\frac12 2^{3n/2}$?

Problem 2. Is $\nu_{n,1}=o(2^{3n/2})$?

Problem 3. Find nontrivial lower and upper bounds on the number $$\lambda_1=\limsup_{n\to\infty}\frac1n\log_2(\nu_{n,1}).$$ Is $1<\lambda_1<\frac32$?

Taras Banakh
  • 41.8k
  • 3
  • 74
  • 183