Fourier Transforms of Boolean Functions : 2

Re: Another Problem

Note. Just another sheet of scratch paper, exploring possible alternatives to the Fourier transforms in the previous post. As a rule, I like to keep Boolean problems in Boolean spaces, partly for aesthetic reasons and partly from a sense that it doesn’t reduce the computational complexity of Boolean problems to replace them with integer or real number problems. I’ll begin by copying the previous post as a template and gradually transform it as I proceed.

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

Notation

Boolean domain {\mathbb{B} = \{0, 1\}}.

Boolean function on {k} variables {f : \mathbb{B}^k \to \mathbb{B}}.

Boolean coordinate projections {\mathcal{X} = \{ x_1, \ldots, x_k \}},
where {x_j : \mathbb{B}^k \to \mathbb{B}} such that {x_j : (x_1, \ldots, x_j, \ldots, x_k) \mapsto x_j}.

Minimal negation operator {\nu_k : \mathbb{B}^k \to \mathbb{B}}. In contexts where the meaning is clear, {\nu_k (x_1, \ldots, x_k)} may be written as {\nu (x_1, \ldots, x_k)} or even, using a different style of parentheses, as \texttt{(} x_1 \texttt{,} \ldots \texttt{,} x_k \texttt{)}.

{k = 2}

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

Identify {x \in \mathbb{B}^2} with the corresponding singular proposition {x : \mathbb{B}^2 \to \mathbb{B}}.

Try some other bases, but with addition as in {\mathbb{F}_2 = \text{GF}(2)}.

Observation. The propositions {f_7, f_{11}, f_{13}, f_{14}} are pairwise orthogonal.

Let {\mathcal{G} = \{ f_7, f_{11}, f_{13}, f_{14} \}}. I’m thinking of calling these the cosingular or fenestral propositions. (I would have called them the lacunary or umbral propositions but those terms already have established meanings in mathematics.) On third thought, I think I’ll call them crenular propositions, a crenel being a notch at the top of a structure.

Definitions

Fourier coefficient of {f} on {g}

{\displaystyle \hat{f}(g) = \sum_{x \in \mathbb{B}^2} f(x) \cdot g(x)}

Fourier expansion of {f}

{\displaystyle f(x) = \sum_{g \in \mathcal{G}} \hat{f}(g) \cdot g(x)}

Tables

\begin{array}{|c||*{4}{c}|}  \multicolumn{5}{c}{\text{Table 2.1. Values of}~ g(x)} \\[4pt]  \hline  g & f_{8} & f_{4} & f_{2} & f_{1} \\  &  \texttt{ } u \texttt{  } v \texttt{ } &  \texttt{ } u \texttt{ (} v \texttt{)} &  \texttt{(} u \texttt{) } v \texttt{ } &  \texttt{(} u \texttt{)(} v \texttt{)} \\  \hline\hline  f_{7}  & 0 & 1 & 1 & 1 \\  f_{11} & 1 & 0 & 1 & 1 \\  f_{13} & 1 & 1 & 0 & 1 \\  f_{14} & 1 & 1 & 1 & 0 \\  \hline  \end{array}
 

\begin{array}{|*{9}{c|}}  \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}(f_{7}) & \hat{f}(f_{11}) & \hat{f}(f_{13}) & \hat{f}(f_{14}) \\  ~&~&~&~&~&~&~&~&~\\  \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 & 1 & 1 & 0 \\  f_{2} & f_{0010} && 0~0~1~0 & (u)~v~ & 1 & 1 & 0 & 1 \\  f_{3} & f_{0011} && 0~0~1~1 & (u)    & 0 & 0 & 1 & 1 \\  f_{4} & f_{0100} && 0~1~0~0 & ~u~(v) & 1 & 0 & 1 & 1 \\  f_{5} & f_{0101} && 0~1~0~1 & (v)    & 0 & 1 & 0 & 1 \\  f_{6} & f_{0110} && 0~1~1~0 & (u,~v) & 0 & 1 & 1 & 0 \\  f_{7} & f_{0111} && 0~1~1~1 & (u~~v) & 1 & 0 & 0 & 0 \\  \hline  f_{8} & f_{1000} && 1~0~0~0 & ~u~~v~ & 0 & 1 & 1 & 1 \\  f_{9} & f_{1001} && 1~0~0~1 &((u,~v))& 1 & 0 & 0 & 1 \\  f_{10}& f_{1010} && 1~0~1~0 &  v     & 1 & 0 & 1 & 0 \\  f_{11}& f_{1011} && 1~0~1~1 &(~u~(v))& 0 & 1 & 0 & 0 \\  f_{12}& f_{1100} && 1~1~0~0 &  u     & 1 & 1 & 0 & 0 \\  f_{13}& f_{1101} && 1~1~0~1 &((u)~v~)& 0 & 0 & 1 & 0 \\  f_{14}& f_{1110} && 1~1~1~0 &((u)(v))& 0 & 0 & 0 & 1 \\  f_{15}& f_{1111} && 1~1~1~1 & ((~))  & 1 & 1 & 1 & 1 \\  \hline  \end{array}
 

\begin{array}{|*{9}{c|}}  \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}(f_{7}) & \hat{f}(f_{11}) & \hat{f}(f_{13}) & \hat{f}(f_{14}) \\  ~&~&~&~&~&~&~&~&~\\  \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 & 1 & 1 & 0 \\  f_{2} & f_{0010} && 0~0~1~0 & (u)~v~ & 1 & 1 & 0 & 1 \\  f_{4} & f_{0100} && 0~1~0~0 & ~u~(v) & 1 & 0 & 1 & 1 \\  f_{8} & f_{1000} && 1~0~0~0 & ~u~~v~ & 0 & 1 & 1 & 1 \\  \hline  f_{3} & f_{0011} && 0~0~1~1 & (u)    & 0 & 0 & 1 & 1 \\  f_{12}& f_{1100} && 1~1~0~0 &  u     & 1 & 1 & 0 & 0 \\  \hline  f_{6} & f_{0110} && 0~1~1~0 & (u,~v) & 0 & 1 & 1 & 0 \\  f_{9} & f_{1001} && 1~0~0~1 &((u,~v))& 1 & 0 & 0 & 1 \\  \hline  f_{5} & f_{0101} && 0~1~0~1 & (v)    & 0 & 1 & 0 & 1 \\  f_{10}& f_{1010} && 1~0~1~0 &  v     & 1 & 0 & 1 & 0 \\  \hline  f_{7} & f_{0111} && 0~1~1~1 & (u~~v) & 1 & 0 & 0 & 0 \\  f_{11}& f_{1011} && 1~0~1~1 &(~u~(v))& 0 & 1 & 0 & 0 \\  f_{13}& f_{1101} && 1~1~0~1 &((u)~v~)& 0 & 0 & 1 & 0 \\  f_{14}& f_{1110} && 1~1~1~0 &((u)(v))& 0 & 0 & 0 & 1 \\  \hline  f_{15}& f_{1111} && 1~1~1~1 & ((~))  & 1 & 1 & 1 & 1 \\  \hline  \end{array}

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
Advertisements
This entry was posted in Boolean Functions, Computational Complexity, Fourier Transforms, Harmonic Analysis, Logic, Mathematics, Propositional Calculus and tagged , , , , , , . Bookmark the permalink.

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