Fourier Transforms of Boolean Functions : 1

Re: Another Problem

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

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.

One Response to Fourier Transforms of Boolean Functions : 1

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s