# Relation beween approximate degree of a function and its Fourier coefficient.

Consider a Boolean function $$f:\{0,1\}^n\to\{0,1\}$$.

The degree of the function $$d$$ has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than $$d$$, i.e. $$\forall S\subseteq [1,n], \hat{f}(S) = 0$$ if $$|S| > d$$.

[edit:add] The approximate degree $$\tilde{d}$$ of a function $$f$$ is the lowest degree of a polynomial $$p$$ such that $$\max_{x\in\{0,1\}^n} |f(x) - p(x)| \leq 1/3$$. [/edit:add]

I was wondering if there is an interpretation of the approximate degree along those kind of lines. I have the intuition (maybe plain wrong) the Fourier coefficient of a function lower that its approximate degree should be small, but I cannot find any claim to sustain this intuition.

The only result I am aware of, is a paper by Sherstov, in STOC'08 (corollary 3.3.1):

Let $$f:\{0,1\}^n \to \mathbb{R}$$ with approximate degree $$\tilde{d}$$. Then there is a function $$\psi:\{0,1\}^n\to\mathbb{R}$$ such that

$$\hat{\psi}(S) = 0$$ if $$|S|<\tilde{d}$$

$$\sum_{x\in\{0,1\}^n}|\psi(x)| = 1$$

$$\sum_{x\in\{0,1\}^n} \psi(x) f(x) > 1/3$$

But the interpretation is very not clear to me since $$\psi$$ is bounded in the $$\ell_1$$ norm and not the $$\ell_2$$ norm as usually used in Fourier analysis. Also how can we have a constant overlap between $$\psi$$ and $$f$$ when $$f$$ is unbounded?

• Could you add a short definition of approximate degree of a function for those who aren't familiar with it? (There might even be different definitions in the literature based on which norm is used to quantify that two functions are close.) Jul 22, 2011 at 14:37
• Hi Robin, just did it. So basically it is the $\ell_\infty$ norm. This is also the reason why the $\ell_1$ norm pops-up, since they are dual of each other. Jul 22, 2011 at 15:43
• How about considering the sum of squares of the Fourier coefficients of f−p? This must be small by Parseval’s identity. Jul 23, 2011 at 21:53
• Yes, this tells us that the sum of the square of the weights of $f$ on Fourier coefficient is small. In this case 1/9. ($\sum_{S : |S| = \tilde{d}+1}^d \hat{f}(S)^2 \leq (\frac{1}{3})^2$) I am interested in the reverse property, ie that $\sum_{S:|S|=\tilde{d}} \hat{f}(S)^2$ is large. Jul 26, 2011 at 18:57
• Maybe I don't understand the question properly, but... isn't the Inner Product function (f(x,y) = (-1)^{<x,y>} where the inner product is taken over F_2) a function with very small fourier coefficients but approximate degree as large as possible? Aug 3, 2011 at 21:57