# $\ell_1$ norm of Fourier coefficients vector for the hypercube

Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$.

Given a function $f:[-1,1] \rightarrow[0,1]$, we can define for every $a \in \{0,1\}^d$ the Fourier coefficient $$\hat{h}_a = \sum_{r \in \{0,1\}^d}f\left(1-2\frac{|r|}{d}\right)(-1)^{\left<r,a\right>}$$ Now, let $v$ be the vector of size $2^d$ so that $v_i = \hat{h}_i$ for $i \in \{0,1\}^d$.

I am looking for an upper-bound on $\frac{1}{2^{d}}\|v\|_1$ in terms of $f$.

Thank you very much for your help.

• Is this question motivated by something? You could compose $f$ with any other symmetric function of $r$, what is so special about the eigenvalues of the hypercube? – Sasho Nikolov Jun 8 '14 at 12:13
• @SashoNikolov, thank you for your comment. It is motivated by the need to bound the induced infinity norm of $f(A)$, where $A$ is the normalized adjacency matrix of the Hypercube. $f$ itself is the normalized Féjer kernel. I thought the connection to the Fourier coefficients might simplify the problem. – Dean Jun 8 '14 at 12:21
• In case $f$ maps to $\{0,1\}$, then $h(x) = f(1-2|x|/d)$ is a symmetric boolean function and then, your question is answered by cs.mcgill.ca/~aada/papers/AFH2012.pdf. – arnab Jun 8 '14 at 12:35
• Thank you @arnab, but I discretization will not help here. However, this result does strengthen my intuition, that the upper bound is around $d$. – Dean Jun 8 '14 at 13:00

The question is about the spectral norm of the symmetric function $h: \{0,1\}^n \to [-1,+1]$ defined as $h(x) = f(1-2|x|/d)$. (I have assumed range $[-1,+1]$ instead of $[0,1]$ which is wlog by appropriate rescaling.)
Ada, Fawzi and H. Hatami show that for any boolean $g: \{0,1\}^n \to \{-1, +1\}$, $$\log \|\hat{g}\|_1 = \Theta\left(r(g) \log\left(\frac{n}{r(g)}\right)\right)$$ where $r(g) = \max(r_0(g), r_1(g))$ and $r_0(g)$ and $r_1(g)$ are minimum integers such that $g$ is either constant or perfectly correlated with parity or anti-parity for $x$ with $|x| \in [r_0(g), n-r_1(g)]$.
Now, look at the proof of Lemma 3.1 in the paper. Note that this straightforward argument also holds for functions $h$ mapping to $[-1,+1]$ instead of $\{-1,+1\}$. So, the same upperbound also holds for your case. This upperbound is tight at least for the boolean functions, but I don't know if there's a similar general lowerbound for non-boolean $h$.