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
Boolean function on 
Boolean coordinate projections
where 
Minimal negation operator 
For ease of reading formulas, let
Identify 
Try some other bases, but with addition as in
Observation. The propositions 
Let 
Definitions
Fourier coefficient of 
Fourier expansion of
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}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7B%7Cc%7C%7C%2A%7B4%7D%7Bc%7D%7C%7D++%5Cmulticolumn%7B5%7D%7Bc%7D%7B%5Ctext%7BTable+2.1.+Values+of%7D%7E+g%28x%29%7D+%5C%5C%5B4pt%5D++%5Chline++g+%26+f_%7B8%7D+%26+f_%7B4%7D+%26+f_%7B2%7D+%26+f_%7B1%7D+%5C%5C++%26++%5Ctexttt%7B+%7D+u+%5Ctexttt%7B++%7D+v+%5Ctexttt%7B+%7D+%26++%5Ctexttt%7B+%7D+u+%5Ctexttt%7B+%28%7D+v+%5Ctexttt%7B%29%7D+%26++%5Ctexttt%7B%28%7D+u+%5Ctexttt%7B%29+%7D+v+%5Ctexttt%7B+%7D+%26++%5Ctexttt%7B%28%7D+u+%5Ctexttt%7B%29%28%7D+v+%5Ctexttt%7B%29%7D+%5C%5C++%5Chline%5Chline++f_%7B7%7D++%26+0+%26+1+%26+1+%26+1+%5C%5C++f_%7B11%7D+%26+1+%26+0+%26+1+%26+1+%5C%5C++f_%7B13%7D+%26+1+%26+1+%26+0+%26+1+%5C%5C++f_%7B14%7D+%26+1+%26+1+%26+1+%26+0+%5C%5C++%5Chline++%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=1&c=20201002)
![\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}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7B%7C%2A%7B9%7D%7Bc%7C%7D%7D++%5Cmulticolumn%7B9%7D%7Bc%7D%7B%5Ctext%7BTable+2.2.+Fourier+Coefficients+of+Boolean+Functions+on+Two+Variables%7D%7D%5C%5C%5B4pt%5D++%5Chline++%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%26++%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26++%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7E%7D+%5C%5C++L_1+%26+L_2+%26%26+L_3+%26+L_4+%26++%5Chat%7Bf%7D%28f_%7B7%7D%29+%26+%5Chat%7Bf%7D%28f_%7B11%7D%29+%26+%5Chat%7Bf%7D%28f_%7B13%7D%29+%26+%5Chat%7Bf%7D%28f_%7B14%7D%29+%5C%5C++%7E%26%7E%26%7E%26%7E%26%7E%26%7E%26%7E%26%7E%26%7E%5C%5C++%5Chline++%26%26u+%3D+%26+1%7E1%7E0%7E0+%26%26%26%26%26+%5C%5C++%26%26v+%3D+%26+1%7E0%7E1%7E0+%26%26%26%26%26+%5C%5C++%5Chline++f_%7B0%7D+%26+f_%7B0000%7D+%26%26+0%7E0%7E0%7E0+%26+%28%7E%29++++%26+0+%26+0+%26+0+%26+0+%5C%5C++f_%7B1%7D+%26+f_%7B0001%7D+%26%26+0%7E0%7E0%7E1+%26+%28u%29%28v%29+%26+1+%26+1+%26+1+%26+0+%5C%5C++f_%7B2%7D+%26+f_%7B0010%7D+%26%26+0%7E0%7E1%7E0+%26+%28u%29%7Ev%7E+%26+1+%26+1+%26+0+%26+1+%5C%5C++f_%7B3%7D+%26+f_%7B0011%7D+%26%26+0%7E0%7E1%7E1+%26+%28u%29++++%26+0+%26+0+%26+1+%26+1+%5C%5C++f_%7B4%7D+%26+f_%7B0100%7D+%26%26+0%7E1%7E0%7E0+%26+%7Eu%7E%28v%29+%26+1+%26+0+%26+1+%26+1+%5C%5C++f_%7B5%7D+%26+f_%7B0101%7D+%26%26+0%7E1%7E0%7E1+%26+%28v%29++++%26+0+%26+1+%26+0+%26+1+%5C%5C++f_%7B6%7D+%26+f_%7B0110%7D+%26%26+0%7E1%7E1%7E0+%26+%28u%2C%7Ev%29+%26+0+%26+1+%26+1+%26+0+%5C%5C++f_%7B7%7D+%26+f_%7B0111%7D+%26%26+0%7E1%7E1%7E1+%26+%28u%7E%7Ev%29+%26+1+%26+0+%26+0+%26+0+%5C%5C++%5Chline++f_%7B8%7D+%26+f_%7B1000%7D+%26%26+1%7E0%7E0%7E0+%26+%7Eu%7E%7Ev%7E+%26+0+%26+1+%26+1+%26+1+%5C%5C++f_%7B9%7D+%26+f_%7B1001%7D+%26%26+1%7E0%7E0%7E1+%26%28%28u%2C%7Ev%29%29%26+1+%26+0+%26+0+%26+1+%5C%5C++f_%7B10%7D%26+f_%7B1010%7D+%26%26+1%7E0%7E1%7E0+%26++v+++++%26+1+%26+0+%26+1+%26+0+%5C%5C++f_%7B11%7D%26+f_%7B1011%7D+%26%26+1%7E0%7E1%7E1+%26%28%7Eu%7E%28v%29%29%26+0+%26+1+%26+0+%26+0+%5C%5C++f_%7B12%7D%26+f_%7B1100%7D+%26%26+1%7E1%7E0%7E0+%26++u+++++%26+1+%26+1+%26+0+%26+0+%5C%5C++f_%7B13%7D%26+f_%7B1101%7D+%26%26+1%7E1%7E0%7E1+%26%28%28u%29%7Ev%7E%29%26+0+%26+0+%26+1+%26+0+%5C%5C++f_%7B14%7D%26+f_%7B1110%7D+%26%26+1%7E1%7E1%7E0+%26%28%28u%29%28v%29%29%26+0+%26+0+%26+0+%26+1+%5C%5C++f_%7B15%7D%26+f_%7B1111%7D+%26%26+1%7E1%7E1%7E1+%26+%28%28%7E%29%29++%26+1+%26+1+%26+1+%26+1+%5C%5C++%5Chline++%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=1&c=20201002)
![\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}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7B%7C%2A%7B9%7D%7Bc%7C%7D%7D++%5Cmulticolumn%7B9%7D%7Bc%7D%7B%5Ctext%7BTable+2.3.+Fourier+Coefficients+of+Boolean+Functions+on+Two+Variables%7D%7D%5C%5C%5B4pt%5D++%5Chline++%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%26++%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26++%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7D+%26+%5Ctext%7B%7E%7E%7E%7E%7E%7E%7E%7E%7E%7D+%5C%5C++L_1+%26+L_2+%26%26+L_3+%26+L_4+%26++%5Chat%7Bf%7D%28f_%7B7%7D%29+%26+%5Chat%7Bf%7D%28f_%7B11%7D%29+%26+%5Chat%7Bf%7D%28f_%7B13%7D%29+%26+%5Chat%7Bf%7D%28f_%7B14%7D%29+%5C%5C++%7E%26%7E%26%7E%26%7E%26%7E%26%7E%26%7E%26%7E%26%7E%5C%5C++%5Chline++%26%26+u+%3D+%26+1%7E1%7E0%7E0+%26%26%26%26%26+%5C%5C++%26%26+v+%3D+%26+1%7E0%7E1%7E0+%26%26%26%26%26+%5C%5C++%5Chline++f_%7B0%7D+%26+f_%7B0000%7D+%26%26+0%7E0%7E0%7E0+%26+%28%7E%29++++%26+0+%26+0+%26+0+%26+0+%5C%5C++%5Chline++f_%7B1%7D+%26+f_%7B0001%7D+%26%26+0%7E0%7E0%7E1+%26+%28u%29%28v%29+%26+1+%26+1+%26+1+%26+0+%5C%5C++f_%7B2%7D+%26+f_%7B0010%7D+%26%26+0%7E0%7E1%7E0+%26+%28u%29%7Ev%7E+%26+1+%26+1+%26+0+%26+1+%5C%5C++f_%7B4%7D+%26+f_%7B0100%7D+%26%26+0%7E1%7E0%7E0+%26+%7Eu%7E%28v%29+%26+1+%26+0+%26+1+%26+1+%5C%5C++f_%7B8%7D+%26+f_%7B1000%7D+%26%26+1%7E0%7E0%7E0+%26+%7Eu%7E%7Ev%7E+%26+0+%26+1+%26+1+%26+1+%5C%5C++%5Chline++f_%7B3%7D+%26+f_%7B0011%7D+%26%26+0%7E0%7E1%7E1+%26+%28u%29++++%26+0+%26+0+%26+1+%26+1+%5C%5C++f_%7B12%7D%26+f_%7B1100%7D+%26%26+1%7E1%7E0%7E0+%26++u+++++%26+1+%26+1+%26+0+%26+0+%5C%5C++%5Chline++f_%7B6%7D+%26+f_%7B0110%7D+%26%26+0%7E1%7E1%7E0+%26+%28u%2C%7Ev%29+%26+0+%26+1+%26+1+%26+0+%5C%5C++f_%7B9%7D+%26+f_%7B1001%7D+%26%26+1%7E0%7E0%7E1+%26%28%28u%2C%7Ev%29%29%26+1+%26+0+%26+0+%26+1+%5C%5C++%5Chline++f_%7B5%7D+%26+f_%7B0101%7D+%26%26+0%7E1%7E0%7E1+%26+%28v%29++++%26+0+%26+1+%26+0+%26+1+%5C%5C++f_%7B10%7D%26+f_%7B1010%7D+%26%26+1%7E0%7E1%7E0+%26++v+++++%26+1+%26+0+%26+1+%26+0+%5C%5C++%5Chline++f_%7B7%7D+%26+f_%7B0111%7D+%26%26+0%7E1%7E1%7E1+%26+%28u%7E%7Ev%29+%26+1+%26+0+%26+0+%26+0+%5C%5C++f_%7B11%7D%26+f_%7B1011%7D+%26%26+1%7E0%7E1%7E1+%26%28%7Eu%7E%28v%29%29%26+0+%26+1+%26+0+%26+0+%5C%5C++f_%7B13%7D%26+f_%7B1101%7D+%26%26+1%7E1%7E0%7E1+%26%28%28u%29%7Ev%7E%29%26+0+%26+0+%26+1+%26+0+%5C%5C++f_%7B14%7D%26+f_%7B1110%7D+%26%26+1%7E1%7E1%7E0+%26%28%28u%29%28v%29%29%26+0+%26+0+%26+0+%26+1+%5C%5C++%5Chline++f_%7B15%7D%26+f_%7B1111%7D+%26%26+1%7E1%7E1%7E1+%26+%28%28%7E%29%29++%26+1+%26+1+%26+1+%26+1+%5C%5C++%5Chline++%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=1&c=20201002)
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 |
