Fourier Transforms of Boolean Functions • 2

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

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

Notes

Special Classes of Propositions

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

	Jon Awbrey on Scratchpad
	Tom on In the Way of Inquiry • Justif…
	Jon Awbrey on Scratchpad
	tgollier on In the Way of Inquiry • Initia…
	Survey of Semiotics,… on Zeroth Law Of Semiotics • Disc…
	Zeroth Law Of Semiot… on All Liar, No Paradox
	Zeroth Law Of Semiot… on Zeroth Law Of Semiotics
	Survey of Semiotics,… on Zeroth Law Of Semiotics • Disc…
	Zeroth Law Of Semiot… on Zeroth Law Of Semiotics
	Zeroth Law Of Semiot… on All Liar, No Paradox

M	T	W	T	F	S	S
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30