Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-016 | 10th June 2018 13:45

On $\ell_4$ : $\ell_2$ ratio of functions with restricted Fourier support

RSS-Feed




Revision #1
Authors: Naomi Kirshner, Alex Samorodnitsky
Accepted on: 10th June 2018 13:45
Downloads: 58
Keywords: 


Abstract:

Given a subset $A\subseteq \{0,1\}^n$, let $\mu(A)$ be the maximal ratio between $\ell_4$ and $\ell_2$ norms of a function whose Fourier support is a subset of $A$. We make some simple observations about the connections between $\mu(A)$ and the additive properties of $A$ on one hand, and between $\mu(A)$ and the uncertainty principle for $A$ on the other hand. One application obtained by combining these observations with results in additive number theory is a stability result for the uncertainty principle on the discrete cube.

Our more technical contribution is determining $\mu(A)$ rather precisely, when $A$ is a Hamming sphere $S(n,k)$ for all $0\leq k\leq n$.



Changes to previous version:

In this revision, we simplify the proof of Proposition 4.5, add a reference to a paper of Polyanskiy, fix a typo in the first author's name, replace a wrong argument on page 13, fifth line from the bottom, and add acknowledgements.


Paper:

TR18-016 | 25th January 2018 18:23

On $\ell_4$ : $\ell_2$ ratio of functions with restricted Fourier support





TR18-016
Authors: Naomi Kirshner, Alex Samorodnitsky
Publication: 26th January 2018 16:00
Downloads: 260
Keywords: 


Abstract:

Given a subset $A\subseteq \{0,1\}^n$, let $\mu(A)$ be the maximal ratio between $\ell_4$ and $\ell_2$ norms of a function whose Fourier support is a subset of $A$. We make some simple observations about the connections between $\mu(A)$ and the additive properties of $A$ on one hand, and between $\mu(A)$ and the uncertainty principle for $A$ on the other hand. One application obtained by combining these observations with results in additive number theory is a stability result for the uncertainty principle on the discrete cube.

Our more technical contribution is determining $\mu(A)$ rather precisely, when $A$ is a Hamming sphere $S(n,k)$ for all $0\leq k\leq n$.



ISSN 1433-8092 | Imprint