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

Question

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}\quad\mbox{and}\quad \tilde \nu_{n,p}=\frac1{2^{2^n}}\sum_{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 $\tilde \nu_{n,1}$ and $\nu_{n,1}$ are much smaller than $2^{3n/2}$ (the values of $\tilde\nu_{n,1}$ are calculated using the formula $$\tilde\nu_{n,1}=\frac1{2^{2^n}}\Big(\sum_{i=0}^{2^n}{2^n\choose i}i+2(2^n-1)\sum_{0\le i<j\le 2^n}{2^n\choose i}{2^n\choose j}(j-i)\Big)$$ of Alex Ravsky suggested in his comment): $$ \begin{array}{c|c|c|c|c|c|c} n&2^n&\tilde \nu_{n,1}&\nu_{n,1}&\lfloor 2^{3n/2}\rfloor&\tilde\nu_{n,1}/2^{3n/2}\\ \hline 0&1&1&1&1&1\\ 1&2&1.5&2&2&0.53...\\ 2&4&4.25&6&8&0.53...\\ 3&8&11.65...&14&22&0.51...\\ 4&16&31.56...&40&64&0.49...\\ 5&32&85.41...&\ge 96&181&0.47...\\ 6&64&232.28..&??&512&0.45...\\ 7&128&636.09...&??&1448&0.43...\\ 8&256&1754.09...&??&4096&0.42...\\ 9&512&4866.56...&??&11585&0.42...\\ \end{array} $$

Problem 1. Is $\nu_{n,1}\ge\frac12 2^{3n/2}$? Is $\tilde\nu_{n,1}\ge \varepsilon 2^{3n/2}$ for some $\varepsilon>0$?

Problem 2. Is $\tilde\nu_{n,1}=o(2^{3n/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$?

Answer 1

$\newcommand{\tnu}{\tilde\nu}$Continuing Alex Ravsky's comment, we have \begin{equation*} 2^{2^n}\tnu_{n,1}=\sum_{j=0}^{2^n-1}S_j=S_0+(2^n-1)S_1, \tag{1} \end{equation*} where \begin{equation*} S_j:=\sum_{F\subseteq[2^n]}\Big|\sum_{i\in F}a_{i,j}\Big|, \end{equation*} and for each $j\ne0$ \begin{equation*} S_j=S_1=\sum_{k,l=0}^M\binom Mk \binom Ml |k-l|, \end{equation*} where \begin{equation*} M=M_n:=2^{n-1}. \tag{2} \end{equation*}

So, \begin{equation*} S_1=2^{2M} E|K-K'|, \tag{3} \end{equation*} where, for each natural $n$, $K=K_n$ and $K'=K'_n$ are independent random variables (r.v.'s) each with the binomial distribution with parameters $M,1/2$. By the central limit theorem, the distribution of $(K-M/2)/\sqrt{M/4}$ converges weakly to the standard normal distribution (as $n\to\infty$), and hence $V_n:=(K-K')/\sqrt{M/4}$ converges in distribution to $Z-Z'$, where $Z$ and $Z'$ are independent standard normal r.v.'s.

Also, $EV_n^2=2<\infty$ for all $n$ and hence, by the de la Vallée-Poussin theorem, the $V_n$'s are uniformly integrable.

Therefore (see e.g. Theorem 3.5, p. 31), $E|V_n|\to E|Z-Z'|$ and hence, by (3), \begin{equation*} S_1\sim 2^{2M} \sqrt{\frac M4}\;E|Z-Z'|=2^{2M} \sqrt{\frac M4}\;\frac2{\sqrt\pi}. \tag{4} \end{equation*}

Also, \begin{equation*} S_0=\sum_{F\subseteq[2^n]}\sum_{i\in F}1=\sum_{k=0}^{2M}\binom{2M}k k=2^{2M}M. \tag{5} \end{equation*} Collecting the pieces (1), (5), (4), and (2), we finally get \begin{equation*} \tnu_{n,1}\sim\frac1{\sqrt{2\pi}}\,2^{3n/2}. \end{equation*}