Fourier Transforms of Boolean Functions • 1

Posted on May 30, 2013 by Jon Awbrey

Re: R.J. Lipton and K.W. Regan • Twin Primes Are Useful

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 KLMMV • On the Fourier Spectrum of Symmetric Boolean Functions)

{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)}

Additional Formulas

{\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 …

Notes

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.

1 Response to Fourier Transforms of Boolean Functions • 1

  1. Pingback: Fourier Transforms of Boolean Functions : 2 | Inquiry Into Inquiry

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.