## Fourier Transforms of Boolean Functions • 2

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}$ $\hat{f}(g) = \sum_{x \in \mathbb{B}^2} f(x) \cdot g(x)$

Fourier expansion of ${f}$ $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}$

### 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.

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