Fourier Transforms of Boolean Functions : 1

The problem is concretely about Boolean functions ${f}$ of ${k}$ variables, and seems not to involve prime numbers at all. For any subset ${S}$ of the coordinate [indices], the corresponding Fourier coefficient is given by:

$\displaystyle \hat{f}(S) = \frac{1}{2^k} \sum_{x \in \mathbb{Z}_2^k} f(x) \chi_S(x)$

where ${\chi_S(x)}$ is ${-1}$ if ${\sum_{i \in S} x_i}$ is odd, and ${+1}$ otherwise.

Note to Self. I need to play around with this concept a while.

Notation (from KLMMVjunta)

${f : \{0,1\}^k \to \{0,1\}}$

${S \subseteq [k] = \{1, \ldots, k\}}$

${\chi_S(x) = (-1)^{\sum_{i \in S} x_i}}$

The order of a Fourier coefficient ${\hat{f}(S)}$ is ${|S|}.$

The Fourier expansion of ${f}$ is:

${\displaystyle f(x) = \sum_{S \subseteq [k]} \hat{f}(S) \chi_S(x)}$

Added Notation (for shifting between coordinate indices and actual coordinates)

${\mathcal{X} = \{x_1, \ldots, x_k\}}$

${\mathcal{S} = \mathcal{X}_S = \{x_i : i \in S\}}$

${\boldsymbol{\chi}_\mathcal{S}(x) = \chi_S(x)}$

${\hat{f}(\mathcal{S}) = \hat{f}(S)}$

${\displaystyle \boldsymbol{\chi}_\mathcal{S}(x) = \prod_{x_i \in \mathcal{S}} (-1)^{x_i}}$

Begin with a survey of concrete examples, perhaps in tabular form.

${k = 1}$

${k = 2}$

For ease of reading formulas, let ${x = (x_1, x_2) = (u, v)}.$

Tables

$\begin{array}{|c||*{4}{c}|} \multicolumn{5}{c}{\text{Table 2.1. Values of}~ \boldsymbol{\chi}_\mathcal{S}(x)} \\[4pt] \hline \mathcal{S} & (1, 1) & (1, 0) & (0, 1) & (0, 0) \\ \hline\hline \varnothing & +1 & +1 & +1 & +1 \\ \{ u \} & -1 & -1 & +1 & +1 \\ \{ v \} & -1 & +1 & -1 & +1 \\ \{ u, v \} & +1 & -1 & -1 & +1 \\ \hline \end{array}$

$\begin{array}{|*{5}{c|}*{4}{r|}} \multicolumn{9}{c}{\text{Table 2.2. Fourier Coefficients of Boolean Functions on Two Variables}}\\[4pt] \hline \text{~~~~~~~~} & \text{~~~~~~~~} & & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} \\ L_1 & L_2 && L_3 & L_4 & \hat{f}(\varnothing) & \hat{f}(\{u\}) & \hat{f}(\{v\}) & \hat{f}(\{u,v\}) \\ ~&~&~&~&~&~&~&~&~\\ \hline && u = & 1~1~0~0 &&&&& \\ && v = & 1~0~1~0 &&&&& \\ \hline f_{0} & f_{0000} && 0~0~0~0 & (~) & 0 & 0 & 0 & 0 \\ f_{1} & f_{0001} && 0~0~0~1 & (u)(v) & 1/4 & 1/4 & 1/4 & 1/4 \\ f_{2} & f_{0010} && 0~0~1~0 & (u)~v~ & 1/4 & 1/4 &-1/4 &-1/4 \\ f_{3} & f_{0011} && 0~0~1~1 & (u) & 1/2 & 1/2 & 0 & 0 \\ f_{4} & f_{0100} && 0~1~0~0 & ~u~(v) & 1/4 &-1/4 & 1/4 &-1/4 \\ f_{5} & f_{0101} && 0~1~0~1 & (v) & 1/2 & 0 & 1/2 & 0 \\ f_{6} & f_{0110} && 0~1~1~0 & (u,~v) & 1/2 & 0 & 0 &-1/2 \\ f_{7} & f_{0111} && 0~1~1~1 & (u~~v) & 3/4 & 1/4 & 1/4 &-1/4 \\ \hline f_{8} & f_{1000} && 1~0~0~0 & ~u~~v~ & 1/4 &-1/4 &-1/4 & 1/4 \\ f_{9} & f_{1001} && 1~0~0~1 &((u,~v))& 1/2 & 0 & 0 & 1/2 \\ f_{10}& f_{1010} && 1~0~1~0 & v & 1/2 & 0 &-1/2 & 0 \\ f_{11}& f_{1011} && 1~0~1~1 &(~u~(v))& 3/4 & 1/4 &-1/4 & 1/4 \\ f_{12}& f_{1100} && 1~1~0~0 & u & 1/2 &-1/2 & 0 & 0 \\ f_{13}& f_{1101} && 1~1~0~1 &((u)~v~)& 3/4 &-1/4 & 1/4 & 1/4 \\ f_{14}& f_{1110} && 1~1~1~0 &((u)(v))& 3/4 &-1/4 &-1/4 &-1/4 \\ f_{15}& f_{1111} && 1~1~1~1 & ((~)) & 1 & 0 & 0 & 0 \\ \hline \end{array}$

$\begin{array}{|*{5}{c|}*{4}{r|}} \multicolumn{9}{c}{\text{Table 2.3. Fourier Coefficients of Boolean Functions on Two Variables}}\\[4pt] \hline \text{~~~~~~~~} & \text{~~~~~~~~} & & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} \\ L_1 & L_2 && L_3 & L_4 & \hat{f}(\varnothing) & \hat{f}(\{u\}) & \hat{f}(\{v\}) & \hat{f}(\{u,v\}) \\ ~&~&~&~&~&~&~&~&~\\ \hline && u = & 1~1~0~0 &&&&& \\ && v = & 1~0~1~0 &&&&& \\ \hline f_{0} & f_{0000} && 0~0~0~0 & (~) & 0 & 0 & 0 & 0 \\ \hline f_{1} & f_{0001} && 0~0~0~1 & (u)(v) & 1/4 & 1/4 & 1/4 & 1/4 \\ f_{2} & f_{0010} && 0~0~1~0 & (u)~v~ & 1/4 & 1/4 &-1/4 &-1/4 \\ f_{4} & f_{0100} && 0~1~0~0 & ~u~(v) & 1/4 &-1/4 & 1/4 &-1/4 \\ f_{8} & f_{1000} && 1~0~0~0 & ~u~~v~ & 1/4 &-1/4 &-1/4 & 1/4 \\ \hline f_{3} & f_{0011} && 0~0~1~1 & (u) & 1/2 & 1/2 & 0 & 0 \\ f_{12}& f_{1100} && 1~1~0~0 & u & 1/2 &-1/2 & 0 & 0 \\ \hline f_{6} & f_{0110} && 0~1~1~0 & (u,~v) & 1/2 & 0 & 0 &-1/2 \\ f_{9} & f_{1001} && 1~0~0~1 &((u,~v))& 1/2 & 0 & 0 & 1/2 \\ \hline f_{5} & f_{0101} && 0~1~0~1 & (v) & 1/2 & 0 & 1/2 & 0 \\ f_{10}& f_{1010} && 1~0~1~0 & v & 1/2 & 0 &-1/2 & 0 \\ \hline f_{7} & f_{0111} && 0~1~1~1 & (u~~v) & 3/4 & 1/4 & 1/4 &-1/4 \\ f_{11}& f_{1011} && 1~0~1~1 &(~u~(v))& 3/4 & 1/4 &-1/4 & 1/4 \\ f_{13}& f_{1101} && 1~1~0~1 &((u)~v~)& 3/4 &-1/4 & 1/4 & 1/4 \\ f_{14}& f_{1110} && 1~1~1~0 &((u)(v))& 3/4 &-1/4 &-1/4 &-1/4 \\ \hline f_{15}& f_{1111} && 1~1~1~1 & ((~)) & 1 & 0 & 0 & 0 \\ \hline \end{array}$

To be continued …

References

 21 May 2013 Twin Primes Are Useful 08 Nov 2012 The Power Of Guessing 05 Jan 2011 Fourier Complexity Of Symmetric Boolean Functions 19 Nov 2010 Is Complexity Theory On The Brink? 18 Sep 2009 Why Believe That P=NP Is Impossible? 04 Jun 2009 The Junta Problem
This entry was posted in Boolean Functions, Computational Complexity, Fourier Transforms, Harmonic Analysis, Logic, Mathematics, Propositional Calculus and tagged , , , , , , . Bookmark the permalink.