Timeline for The largest $\ell_p$-norm of a sum of rows of a Sylvester-Hadamard-Walsh matrix
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 30, 2021 at 16:00 | vote | accept | Taras Banakh | ||
| Nov 30, 2021 at 14:18 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body
|
| Nov 30, 2021 at 14:12 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body
|
| Nov 30, 2021 at 14:11 | answer | added | Iosif Pinelis | timeline score: 3 | |
| Nov 30, 2021 at 13:59 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added info from Ravsky's comment
|
| Nov 30, 2021 at 13:49 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added info from Ravsky's comment
|
| Nov 30, 2021 at 13:38 | comment | added | Taras Banakh | @AlexRavsky Python was able to calclulate $\tilde\nu_{n,1}$ only for $n<10$. For $n=10$ it had Overflow Error (without Math). | |
| Nov 30, 2021 at 13:36 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added info from Ravsky's comment
|
| Nov 30, 2021 at 13:18 | comment | added | Alex Ravsky | I installed MathCad and I shall try to guess the asymptotics of $\tilde \nu_{n,1}$ via the formula. | |
| Nov 30, 2021 at 13:14 | comment | added | Taras Banakh | @AlexRavsky Sasha, thank you for your comment. Everything works and computer calculations using your formula agree with known values of $\tilde \nu_{n,1}$ for $n\le 4$. | |
| Nov 30, 2021 at 12:06 | comment | added | Taras Banakh | @fedja Probably yes, modulo some calculations of probabilities. In any case, I stopped to believe that Problem 2 has affirmative answer. | |
| Nov 30, 2021 at 11:48 | comment | added | fedja | @TarasBanakh But what I said immediately implies the negative answer to problem 2, doesn't it? | |
| Nov 30, 2021 at 11:26 | history | edited | Alex Ravsky |
Added a tag motivated by my comment.
|
|
| Nov 30, 2021 at 11:22 | comment | added | Alex Ravsky | It seems the following. We have that $$2^{2^n}\tilde \nu_{n,1}=\sum_{F\subseteq 2^n}\sum_{j\in 2^n}\big|\sum_{i\in F}a_{i,j}\big|=\sum_{j\in 2^n} S_j$$ where $S_j=\sum_{F\subseteq 2^n}\big|\sum_{i\in F}a_{i,j}\big|$. Let $j\in 2^n$ and $j\ne 0$. Since there is exactly $2^{n-1}$ elements $i\in 2^n$ such that $a_{i,j}=1$, $$S_j=\sum_{k=0}^{2^{n-1}} \sum_{\ell=0}^{2^{n-1}} {2^{n-1}\choose k}{2^{n-1}\choose \ell}|k-\ell|.$$ | |
| Nov 30, 2021 at 6:50 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added $\tilde\nu_{n,p}$.
|
| Nov 30, 2021 at 6:30 | comment | added | Taras Banakh | @fedja In fact, for my purposes it would be nice to have affirmative answer to Problem 2. Could you prove that there exists $\varepsilon>0$ such that for a sufficiently large $n$ and randomly chosen $F$ the probablity to have $\sum_{j\in 2^n}|\sum_{i\in F}a_{i,j}|>\varepsilon 2^{3n/2}$ is positive? | |
| Nov 30, 2021 at 1:56 | comment | added | Padraig Ó Catháin | Maximising the function $\nu_{n, 1}$ is equivalent to maximising $\sum_{H} |X| - 2|X \cap H|$ where $X \subseteq \mathbb{F}_{2}^{n}$, and the sum is over hyperplanes of $\mathbb{F}_{2}^{n}$. So the function is large when $X$ is 'unbalanced' with respect to many hyperplanes. Perhaps there is a construction for such objects in the finite geometry literature? | |
| Nov 29, 2021 at 23:50 | comment | added | fedja | Erm... If you just choose $F$ randomly, then the typical size of the sum over $F$ is $2^{n/2}$ for each $j$, so you get $\nu_{n,p}$ comparable to the trivial Holder bound. Whether the comparability constant is above $1/2$ or not for $p=1$ may be harder to determine, but do you really care? | |
| Nov 29, 2021 at 23:20 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 55 characters in body
|
| Nov 29, 2021 at 21:08 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 12 characters in body
|
| Nov 29, 2021 at 20:59 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited title; added 9 characters in body; edited title
|
| Nov 29, 2021 at 20:41 | history | asked | Taras Banakh | CC BY-SA 4.0 |