MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Notation: identify an element of $\{-1,1\}^n$ with the set $S \subseteq \{1, \ldots, n\}$ on which it takes the value $-1$.

The following is an asymptotic question. "Close to one" means "more than $r_n$" and "away from $\frac{n}{2}$" means "outside the interval $[\frac{n}{2} - k_n\sqrt{n}, \frac{n}{2} + k_n\sqrt{n}]$", for some $r_n$ and $k_n$ which respectively increase to one and infinity as $n \to \infty$.

Conjecture: for any subset of $\{-1,1\}^n$ there is a complex valued function with $l^2$ norm equal to 1, supported either on that subset or on its complement, whose Fourier transform has $l^2$ norm close to one on $\{S: |S|$ is away from $\frac{n}{2}\}$.

A positive answer would have very interesting consequences. It would mean that a single subspace of $l^2(\{-1,1\}^n)$ whose dimension is small compared to the whole space is close to every subspace spanned by standard basis vectors or its complement.

I'm not familiar with the literature on Fourier analysis on the discrete cube. Is there anything there that would help settle this question?

Edit: I would have edited this earlier, but I assumed it had disappeared from view. Since the Kadison-Singer problem has a positive solution, the answer to the conjecture is no. Posting details in an answer.

share|cite|improve this question
Nice question, Nik. Do you know what happen for a random subset of {-1,1}^n? – Gil Kalai Jan 1 '13 at 12:12
@Gil: I don't know. Does a random subset approximately contain a face of dimension greater than $n/2$? I think the characteristic function of such a face has transform supported on small $S$ ... – Nik Weaver Jan 1 '13 at 18:56
In a separate thread ( Anthony Quas informs me that typical subsets do not contain faces that big. So that idea doesn't work. – Nik Weaver Jan 3 '13 at 1:10
Glad to see this answer. (I fixed a typo: missing ")" before each $I$ in the display.) Questions with this many votes and no answer don't "disappear from view"; yours is on the first screen at . – Noam D. Elkies Jun 29 '14 at 4:59
@Noam: I see, thanks. So should I submit the edit as an answer to get off the "unanswered" list? – Nik Weaver Jun 29 '14 at 5:29
up vote 4 down vote accepted

In the language of Marcus-Spielman-Srivastava, Corollary 1.5, identify $l^2(S)$ with ${\mathbb C}^d$ where $d = |S|$ and let the vectors $u_i \in {\mathbb C}^d$ be the orthogonal projections into $l^2(S)$ of the Fourier transforms of the standard basis vectors of $l^2(\{-1,1\}^n)$. By Corollary 1.5 with $r = 2$, we can find a subset $T$ of $\{-1,1\}^n$ such that $$(.5 - O(\sqrt{\delta}))I \leq \sum_{i \in T} u_iu_i^* \leq (.5 + O(\sqrt{\delta}))I$$ where $\delta = \frac{d}{2^n}$. This means that the Fourier transform of any vector in $l^2(T)$ with $l^2$ norm equal to 1 will split into a component supported on $S$ and a component supported off of $S$, each of which has square norm in the interval $[.5 - O(\sqrt{\delta}), .5 + O(\sqrt{\delta})]$.

The conjecture fails dramatically: not only is $l^2(S)$ not close to $l^2(T)$ or $l^2(T)^\perp$, but every unit vector in either $l^2(T)$ or $l^2(T)^\perp$ is approximately $45^\circ$ from $l^2(S)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.