Difference between revisions of "User:Jon Awbrey/WORDPRESS"

MyWikiBiz, Author Your Legacy — Wednesday May 15, 2024
Jump to navigationJump to search
Line 835: Line 835:
 
===Fourier Transforms of Boolean Functions===
 
===Fourier Transforms of Boolean Functions===
  
<pre>
+
Re: [http://rjlipton.wordpress.com/2013/05/21/twin-primes-are-useful/ Another Problem]
Re: <a href="http://rjlipton.wordpress.com/2013/05/21/twin-primes-are-useful/" target="_blank">Another Problem</a>
 
 
 
<div style="margin-left:30px;">
 
  
 +
<blockquote>
 
<p>The problem is concretely about Boolean functions $latex {f}$ of $latex {k}$ variables, and seems not to involve prime numbers at all.  For any subset $latex {S}$ of the coordinates, the corresponding Fourier coefficient is given by:</p>
 
<p>The problem is concretely about Boolean functions $latex {f}$ of $latex {k}$ variables, and seems not to involve prime numbers at all.  For any subset $latex {S}$ of the coordinates, the corresponding Fourier coefficient is given by:</p>
  
 
<p align="center">
 
<p align="center">
$latex \displaystyle \hat{f}(S) = \frac{1}{2^k} \sum_{x \in \mathbb{Z}_2^k} f(x)\chi_S(x)$</p>
+
<math>\displaystyle \hat{f}(S) = \frac{1}{2^k} \sum_{x \in \mathbb{Z}_2^k} f(x)\chi_S(x)\!</math>
 
+
</p>
<p>where $latex {\chi_S(x)}$ is $latex {-1}$ if $latex {\sum_{i \in S} x_i}$ is odd, and $latex {+1}$ otherwise.</p>
 
 
 
</div>
 
 
 
<b>Note to Self.</b>  I need to play around with this concept a while.
 
  
Begin with a survey of concrete examples, perhaps in tabular form.
+
<p>where <math>\chi_S(x)\!</math> is <math>-1\!</math> if <math>\sum_{i \in S} x_i\!</math> is odd, and <math>+1\!</math> otherwise.</p>
 +
</blockquote>
  
$latex {k = 1}$
+
<math>k = 1\!</math>
  
 
&hellip;
 
&hellip;
  
$latex {k = 2}$
+
<math>k = 2\!</math>
  
For ease of reading formulas, let $latex {x = (x_1, x_2) = (u, v)}.$
+
For ease of reading formulas, let <math>x = (x_1, x_2) = (u, v).\!</math>
  
 +
<pre>
 
<p align="center">
 
<p align="center">
 
$latex
 
$latex
Line 881: Line 876:
 
&amp;fg=000000$
 
&amp;fg=000000$
 
</p>
 
</p>
 +
</pre>
  
 +
<pre>
 
<p align="center">
 
<p align="center">
 
$latex
 
$latex
Line 1,050: Line 1,047:
 
\end{tabular}&amp;fg=000000$
 
\end{tabular}&amp;fg=000000$
 
</p>
 
</p>
 
<i>To be continued &hellip;</i>
 
 
<h3>Notes</h3>
 
 
<ul><li><a href="http://inquiryintoinquiry.com/2013/05/31/special-classes-of-propositions/" target="_blank">Special Classes of Propositions</a></li></ul>
 
 
<h3>References</h3>
 
 
<table border="0" style="border-width:0;">
 
 
<tr>
 
<td style="border-top:1px solid white;">21 May 2013</td>
 
<td style="border-top:1px solid white;"><a href="http://rjlipton.wordpress.com/2013/05/21/twin-primes-are-useful/" target="_blank">Twin Primes Are Useful</a></td></tr>
 
 
<tr>
 
<td style="border-top:1px solid white;">08 Nov 2012</td>
 
<td style="border-top:1px solid white;"><a href="http://rjlipton.wordpress.com/2012/11/08/the-power-of-guessing/" target="_blank">The Power Of Guessing</a></td></tr>
 
 
<tr>
 
<td style="border-top:1px solid white;">05 Jan 2011</td>
 
<td style="border-top:1px solid white;"><a href="http://rjlipton.wordpress.com/2011/01/05/fourier-complexity-of-cirtemmys-boolean-functions/" target="_blank">Fourier Complexity Of Symmetric Boolean Functions</a></td></tr>
 
 
<tr>
 
<td style="border-top:1px solid white;">19 Nov 2010</td>
 
<td style="border-top:1px solid white;"><a href="http://rjlipton.wordpress.com/2010/11/19/is-complexity-theory-on-the-brink/" target="_blank">Is Complexity Theory On The Brink?</a></td></tr>
 
 
<tr>
 
<td style="border-top:1px solid white;">18 Sep 2009</td>
 
<td style="border-top:1px solid white;"><a href="http://rjlipton.wordpress.com/2009/09/18/why-believe-that-pnp-is-impossible/" target="_blank">Why Believe That P=NP Is Impossible?</a></td></tr>
 
 
<tr>
 
<td style="border-top:1px solid white;">04 Jun 2009</td>
 
<td style="border-top:1px solid white;"><a href="http://rjlipton.wordpress.com/2009/06/04/the-junta-problem/" target="_blank">The Junta Problem</a></td></tr>
 
 
</table>
 
 
</pre>
 
</pre>
  

Revision as of 03:48, 4 June 2013

WordPress versions of HTML and LaTeX markup

Tables

Boolean Functions and Propositional Calculus

Table A1. Propositional Forms on Two Variables

$latex
\begin{tabular}{|*{7}{c|}}
\multicolumn{7}{c}{Table A1. Propositional Forms on Two Variables} \\
\hline
\(L_1\)&\(L_2\)&&\(L_3\)&\(L_4\)&\(L_5\)&\(L_6\) \\
\hline
&&\(x=\)&1 1 0 0&&& \\
&&\(y=\)&1 0 1 0&&& \\
\hline
\(f_{0}\)&
\(f_{0000}\)&&
0 0 0 0&
\((~)\)&
false&
\(0\)
\\
\(f_{1}\)&
\(f_{0001}\)&&
0 0 0 1&
\((x)(y)\)&
neither \(x\) nor \(y\)&
\(\lnot x \land \lnot y\)
\\
\(f_{2}\)&
\(f_{0010}\)&&
0 0 1 0&
\((x)~y~\)&
\(y\) without \(x\)&
\(\lnot x \land y\)
\\
\(f_{3}\)&
\(f_{0011}\)&&
0 0 1 1&
\((x)\)&
not \(x\)&
\(\lnot x\)
\\
\(f_{4}\)&
\(f_{0100}\)&&
0 1 0 0&
\(~x~(y)\)&
\(x\) without \(y\)&
\(x \land \lnot y\)
\\
\(f_{5}\)&
\(f_{0101}\)&&
0 1 0 1&
\((y)\)&
not \(y\)&
\(\lnot y\)
\\
\(f_{6}\)&
\(f_{0110}\)&&
0 1 1 0&
\((x,~y)\)&
\(x\) not equal to \(y\)&
\(x \ne y\)
\\
\(f_{7}\)&
\(f_{0111}\)&&
0 1 1 1&
\((x~~y)\)&
not both \(x\) and \(y\)&
\(\lnot x \lor \lnot y\)
\\
\hline
\(f_{8}\)&
\(f_{1000}\)&&
1 0 0 0&
\(~x~~y~\)&
\(x\) and \(y\)&
\(x \land y\)
\\
\(f_{9}\)&
\(f_{1001}\)&&
1 0 0 1&
\(((x,~y))\)&
\(x\) equal to \(y\)&
\(x = y\)
\\
\(f_{10}\)&
\(f_{1010}\)&&
1 0 1 0&
\(y\)&
\(y\)&
\(y\)
\\
\(f_{11}\)&
\(f_{1011}\)&&
1 0 1 1&
\((~x~(y))\)&
not \(x\) without \(y\)&
\(x \Rightarrow y\)
\\
\(f_{12}\)&
\(f_{1100}\)&&
1 1 0 0&
\(x\)&
\(x\)&
\(x\)
\\
\(f_{13}\)&
\(f_{1101}\)&&
1 1 0 1&
\(((x)~y~)\)&
not \(y\) without \(x\)&
\(x \Leftarrow y\)
\\
\(f_{14}\)&
\(f_{1110}\)&&
1 1 1 0&
\(((x)(y))\)&
\(x\) or \(y\)&
\(x \lor y\)
\\
\(f_{15}\)&
\(f_{1111}\)&&
1 1 1 1&
\(((~))\)&
true&
\(1\)
\\
\hline
\end{tabular}&fg=000000$

Table A2. Propositional Forms on Two Variables

$latex
\begin{tabular}{|*{7}{c|}}
\multicolumn{7}{c}{Table A2. Propositional Forms on Two Variables} \\
\hline
\(L_1\)&\(L_2\)&&\(L_3\)&\(L_4\)&\(L_5\)&\(L_6\) \\
\hline
&&\(x =\)&1 1 0 0&&& \\
&&\(y =\)&1 0 1 0&&& \\
\hline
\(f_{0}\)&
\(f_{0000}\)&&
0 0 0 0&
\((~)\)&
false&
\(0\)
\\
\hline
\(f_{1}\)&
\(f_{0001}\)&&
0 0 0 1&
\((x)(y)\)&
neither \(x\) nor \(y\)&
\(\lnot x \land \lnot y\)
\\
\(f_{2}\)&
\(f_{0010}\)&&
0 0 1 0&
\((x)~y~\)&
\(y\) without \(x\)&
\(\lnot x \land y\)
\\
\(f_{4}\)&
\(f_{0100}\)&&
0 1 0 0&
\(~x~(y)\)&
\(x\) without \(y\)&
\(x \land \lnot y\)
\\
\(f_{8}\)&
\(f_{1000}\)&&
1 0 0 0&
\(~x~~y~\)&
\(x\) and \(y\)&
\(x \land y\)
\\
\hline
\(f_{3}\)&
\(f_{0011}\)&&
0 0 1 1&
\((x)\)&
not \(x\)&
\(\lnot x\)
\\
\(f_{12}\)&
\(f_{1100}\)&&
1 1 0 0&
\(x\)&
\(x\)&
\(x\)
\\
\hline
\(f_{6}\)&
\(f_{0110}\)&&
0 1 1 0&
\((x,~y)\)&
\(x\) not equal to \(y\)&
\(x \ne y\)
\\
\(f_{9}\)&
\(f_{1001}\)&&
1 0 0 1&
\(((x,~y))\)&
\(x\) equal to \(y\)&
\(x = y\)
\\
\hline
\(f_{5}\)&
\(f_{0101}\)&&
0 1 0 1&
\((y)\)&
not \(y\)&
\(\lnot y\)
\\
\(f_{10}\)&
\(f_{1010}\)&&
1 0 1 0&
\(y\)&
\(y\)&
\(y\)
\\
\hline
\(f_{7}\)&
\(f_{0111}\)&&
0 1 1 1&
\((~x~~y~)\)&
not both \(x\) and \(y\)&
\(\lnot x \lor \lnot y\)
\\
\(f_{11}\)&
\(f_{1011}\)&&
1 0 1 1&
\((~x~(y))\)&
not \(x\) without \(y\)&
\(x \Rightarrow y\)
\\
\(f_{13}\)&
\(f_{1101}\)&&
1 1 0 1&
\(((x)~y~)\)&
not \(y\) without \(x\)&
\(x \Leftarrow y\)
\\
\(f_{14}\)&
\(f_{1110}\)&&
1 1 1 0&
\(((x)(y))\)&
\(x\) or \(y\)&
\(x \lor y\)
\\
\hline
\(f_{15}\)&
\(f_{1111}\)&&
1 1 1 1&
\(((~))\)&
true&
\(1\)
\\
\hline
\end{tabular}&fg=000000$

Table A3. Ef Expanded Over Differential Features {dx, dy}

$latex
\begin{tabular}{|c|c||c|c|c|c|}
\multicolumn{6}{c}{Table A3. \(\mathrm{E}f\) Expanded Over Differential Features \(\{\mathrm{d}x, \mathrm{d}y\}\)} \\
\hline
&
\(~~~~~~~~ f ~~~~~~~~\)&
\(~~~~\mathrm{T}_{11}f~~~~\)&
\(~~~~\mathrm{T}_{10}f~~~~\)&
\(~~~~\mathrm{T}_{01}f~~~~\)&
\(~~~~\mathrm{T}_{00}f~~~~\)
\\
&&
\(\mathrm{E}f|_{~\mathrm{d}x ~\mathrm{d}y~}~\)&
\(\mathrm{E}f|_{~\mathrm{d}x~(\mathrm{d}y)}~\)&
\(\mathrm{E}f|_{(\mathrm{d}x)~\mathrm{d}y~}~\)&
\(\mathrm{E}f|_{(\mathrm{d}x)(\mathrm{d}y)}~\)
\\
\hline\hline
\(f_{0}\)&
\(0\)&
\(0\)&
\(0\)&
\(0\)&
\(0\)
\\
\hline
\(f_{1}\)&
\((x)(y)\)&
\(~x~~y~\)&
\(~x~(y)\)&
\((x)~y~\)&
\((x)(y)\)
\\
\(f_{2}\)&
\((x)~y~\)&
\(~x~(y)\)&
\(~x~~y~\)&
\((x)(y)\)&
\((x)~y~\)
\\
\(f_{4}\)&
\(~x~(y)\)&
\((x)~y~\)&
\((x)(y)\)&
\(~x~~y~\)&
\(~x~(y)\)
\\
\(f_{8}\)&
\(~x~~y~\)&
\((x)(y)\)&
\((x)~y~\)&
\(~x~(y)\)&
\(~x~~y~\)
\\
\hline
\(f_{3}\)&
\((x)\)&
\( x \)&
\( x \)&
\((x)\)&
\((x)\)
\\
\(f_{12}\)&
\( x \)&
\((x)\)&
\((x)\)&
\( x \)&
\( x \)
\\
\hline
\(f_{6}\)&
\( (x,y) \)&
\( (x,y) \)&
\(((x,y))\)&
\(((x,y))\)&
\( (x,y) \)
\\
\(f_{9}\)&
\(((x,y))\)&
\(((x,y))\)&
\( (x,y) \)&
\( (x,y) \)&
\(((x,y))\)
\\
\hline
\(f_{5}\)&
\((y)\)&
\( y \)&
\((y)\)&
\( y \)&
\((y)\)
\\
\(f_{10}\)&
\( y \)&
\((y)\)&
\( y \)&
\((y)\)&
\( y \)
\\
\hline
\(f_{7}\)&
\((~x~~y~)\)&
\(((x)(y))\)&
\(((x)~y~)\)&
\((~x~(y))\)&
\((~x~~y~)\)
\\
\(f_{11}\)&
\((~x~(y))\)&
\(((x)~y~)\)&
\(((x)(y))\)&
\((~x~~y~)\)&
\((~x~(y))\)
\\
\(f_{13}\)&
\(((x)~y~)\)&
\((~x~(y))\)&
\((~x~~y~)\)&
\(((x)(y))\)&
\(((x)~y~)\)
\\
\(f_{14}\)&
\(((x)(y))\)&
\((~x~~y~)\)&
\((~x~(y))\)&
\(((x)~y~)\)&
\(((x)(y))\)
\\
\hline
\(f_{15}\)&
\(1\)&
\(1\)&
\(1\)&
\(1\)&
\(1\)
\\
\hline\hline
\multicolumn{2}{|c||}{Fixed Point Total}&
4&
4&
4&
16
\\
\hline
\end{tabular}&fg=000000$

Table A4. Df Expanded Over Differential Features {dx, dy}

$latex
\begin{tabular}{|c|c||c|c|c|c|}
\multicolumn{6}{c}{Table A4. \(\mathrm{D}f\) Expanded Over Differential Features \(\{\mathrm{d}x, \mathrm{d}y\}\)} \\
\hline
&
\(~~~~~~~~ f ~~~~~~~~\)&
\(\mathrm{D}f|_{~\mathrm{d}x\;\mathrm{d}y~}~\)&
\(\mathrm{D}f|_{~\mathrm{d}x~(\mathrm{d}y)}~\)&
\(\mathrm{D}f|_{(\mathrm{d}x)~\mathrm{d}y~}~\)&
\(\mathrm{D}f|_{(\mathrm{d}x)(\mathrm{d}y)}~\)
\\
\hline\hline
\( f_{0} \)&
\( 0 \)&
\( 0 \)&
\( 0 \)&
\( 0 \)&
\( 0 \)
\\
\hline
\( f_{1} \)&
\( (x)(y) \)&
\( ((x,y)) \)&
\( (y) \)&
\( (x) \)&
\( 0 \)
\\
\( f_{2} \)&
\( (x)~y~ \)&
\( (x,y) \)&
\( y \)&
\( (x) \)&
\( 0 \)
\\
\( f_{4} \)&
\( ~x~(y) \)&
\( (x,y) \)&
\( (y) \)&
\( x \)&
\( 0 \)
\\
\( f_{8} \)&
\( ~x~~y~ \)&
\( ((x,y)) \)&
\( y \)&
\( x \)&
\( 0 \)
\\
\hline
\( f_{3} \)&
\( (x) \)&
\( 1 \)&
\( 1 \)&
\( 0 \)&
\( 0 \)
\\
\( f_{12} \)&
\( x \)&
\( 1 \)&
\( 1 \)&
\( 0 \)&
\( 0 \)
\\
\hline
\( f_{6} \)&
\( (x,y) \)&
\( 0 \)&
\( 1 \)&
\( 1 \)&
\( 0 \)
\\
\( f_{9} \)&
\( ((x,y)) \)&
\( 0 \)&
\( 1 \)&
\( 1 \)&
\( 0 \)
\\
\hline
\( f_{5} \)&
\( (y) \)&
\( 1 \)&
\( 0 \)&
\( 1 \)&
\( 0 \)
\\
\( f_{10} \)&
\( y  \)&
\( 1 \)&
\( 0 \)&
\( 1 \)&
\( 0 \)
\\
\hline
\( f_{7} \)&
\( (~x~~y~) \)&
\( ((x,y)) \)&
\( y \)&
\( x \)&
\( 0 \)
\\
\( f_{11}\) &
\( (~x~(y)) \)&
\( (x,y) \)&
\( (y) \)&
\( x \)&
\( 0 \)
\\
\( f_{13}\) &
\( ((x)~y~) \)&
\( (x,y) \)&
\( y \)&
\( (x) \)&
\( 0 \)
\\
\( f_{14} \)&
\( ((x)(y)) \)&
\( ((x,y)) \)&
\( (y) \)&
\( (x) \)&
\( 0 \)
\\
\hline
\(f_{15}\)&
\( 1 \)&
\( 0 \)&
\( 0 \)&
\( 0 \)&
\( 0 \)
\\
\hline
\end{tabular}&fg=000000$

Table A5. Ef Expanded Over Ordinary Features {x, y}

$latex
\begin{tabular}{|c|c||c|c|c|c|}
\multicolumn{6}{c}{Table A5. \(\mathrm{E}f\) Expanded Over Ordinary Features \(\{x, y\}\)} \\
\hline
&
\(~~~~~~~~ f ~~~~~~~~\)&
\(~~\mathrm{E}f|_{ x\;y }~~~\)&
\(~~\mathrm{E}f|_{ x~(y)}\,~~\)&
\(~~\mathrm{E}f|_{(x)~y }\,~~\)&
\(~~\mathrm{E}f|_{(x)(y)}\;~\)
\\
\hline\hline
\(f_{0}\)&
0&
0&
0&
0&
0
\\
\hline
\(f_{1}\)&
\((x)(y)\)&
~d\(x\)~~d\(y~\)&
~d\(x\)~(d\(y\))&
(d\(x\))~d\(y~\)&
(d\(x\))(d\(y\))
\\
\(f_{2}\)&
\((x)~y~\)&
~d\(x\)~(d\(y\))&
~d\(x\)~~d\(y~\)&
(d\(x\))(d\(y\))&
(d\(x\))~d\(y~\)
\\
\(f_{4}\)&
\(~x~(y)\)&
(d\(x\))~d\(y~\)&
(d\(x\))(d\(y\))&
~d\(x\)~~d\(y~\)&
~d\(x\)~(d\(y\))
\\
\(f_{8}\)&
\(~x~~y~\)&
(d\(x\))(d\(y\))&
(d\(x\))~d\(y~\)&
~d\(x\)~(d\(y\))&
~d\(x\)~~d\(y~\)
\\
\hline
\(f_{3}\)&
\((x)\)&
 d\(x\) &
 d\(x\) &
(d\(x\))&
(d\(x\))
\\
\(f_{12}\)&
\( x \)&
(d\(x\))&
(d\(x\))&
 d\(x\) &
 d\(x\) 
\\
\hline
\(f_{6}\)&
\( (x,y) \)&
 (d\(x\), d\(y\)) &
((d\(x\), d\(y\)))&
((d\(x\), d\(y\)))&
 (d\(x\), d\(y\)) 
\\
\(f_{9}\)&
\(((x,y))\)&
((d\(x\), d\(y\)))&
 (d\(x\), d\(y\)) &
 (d\(x\), d\(y\)) &
((d\(x\), d\(y\)))
\\
\hline
\(f_{5}\)&
\((y)\)&
 d\(y\) &
(d\(y\))&
 d\(y\) &
(d\(y\))
\\
\(f_{10}\)&
\( y \)&
(d\(y\))&
 d\(y\) &
(d\(y\))&
 d\(y\) 
\\
\hline
\(f_{7}\)&
\((~x~~y~)\)&
((d\(x\))(d\(y\)))&
((d\(x\))~d\(y\)~)&
(~d\(x\)~(d\(y\)))&
(~d\(x\)~~d\(y\)~)
\\
\(f_{11}\)&
\((~x~(y))\)&
((d\(x\))~d\(y\)~)&
((d\(x\))(d\(y\)))&
(~d\(x\)~~d\(y\)~)&
(~d\(x\)~(d\(y\)))
\\
\(f_{13}\)&
\(((x)~y~)\)&
(~d\(x\)~(d\(y\)))&
(~d\(x\)~~d\(y\)~)&
((d\(x\))(d\(y\)))&
((d\(x\))~d\(y\)~)
\\
\(f_{14}\)&
\(((x)(y))\)&
(~d\(x\)~~d\(y\)~)&
(~d\(x\)~(d\(y\)))&
((d\(x\))~d\(y\)~)&
((d\(x\))(d\(y\)))
\\
\hline
\(f_{15}\)&
1&
1&
1&
1&
1
\\
\hline
\end{tabular}&fg=000000$

Table A6. Df Expanded Over Ordinary Features {x, y}

$latex
\begin{tabular}{|c|c||c|c|c|c|}
\multicolumn{6}{c}{Table A6. \(\mathrm{D}f\) Expanded Over Ordinary Features \(\{x, y\}\)} \\
\hline
&
\(~~~~~~~~ f ~~~~~~~~\)&
\(~~\mathrm{D}f|_{ x\;y }~~~\)&
\(~~\mathrm{D}f|_{ x~(y)}\,~~\)&
\(~~\mathrm{D}f|_{(x)~y }\,~~\)&
\(~~\mathrm{D}f|_{(x)(y)}\,~\)
\\
\hline\hline
\(f_{0}\)&
0&
0&
0&
0&
0
\\
\hline
\(f_{1}\)&
\((x)(y)\)&
~~d\(x\)~~d\(y~~\)&
\;d\(x\)~(d\(y\))~&
~(d\(x\))~d\(y~~\)&
((d\(x\))(d\(y\)))
\\
\(f_{2}\)&
\((x)~y~\)&
\;d\(x\)~(d\(y\))~&
~~d\(x\)~~d\(y~~\)&
((d\(x\))(d\(y\)))&
~(d\(x\))~d\(y~~\)
\\
\(f_{4}\)&
\(~x~(y)\)&
~(d\(x\))~d\(y~~\)&
((d\(x\))(d\(y\)))&
~~d\(x\)~~d\(y~~\)&
~~d\(x\)~(d\(y\))~
\\
\(f_{8}\)&
\(~x~~y~\)&
((d\(x\))(d\(y\)))&
~(d\(x\))~d\(y~~\)&
\;d\(x\)~(d\(y\))~&
~~d\(x\)~~d\(y~~\)
\\
\hline
\(f_{3}\)&
\((x)\)&
d\(x\)&
d\(x\)&
d\(x\)&
d\(x\)
\\
\(f_{12}\)&
\( x \)&
d\(x\)&
d\(x\)&
d\(x\)&
d\(x\)
\\
\hline
\(f_{6}\)&
\( (x,y) \)&
(d\(x\), d\(y\))&
(d\(x\), d\(y\))&
(d\(x\), d\(y\))&
(d\(x\), d\(y\))
\\
\(f_{9}\)&
\(((x,y))\)&
(d\(x\), d\(y\))&
(d\(x\), d\(y\))&
(d\(x\), d\(y\))&
(d\(x\), d\(y\))
\\
\hline
\(f_{5}\)&
\((y)\)&
d\(y\)&
d\(y\)&
d\(y\)&
d\(y\)
\\
\(f_{10}\)&
\( y \)&
d\(y\)&
d\(y\)&
d\(y\)&
d\(y\)
\\
\hline
\(f_{7}\)&
\((~x~~y~)\)&
((d\(x\))(d\(y\)))&
~(d\(x\))~d\(y~~\)&
\;d\(x\)~(d\(y\))~&
~~d\(x\)~~d\(y~~\)
\\
\(f_{11}\)&
\((~x~(y))\)&
~(d\(x\))~d\(y~~\)&
((d\(x\))(d\(y\)))&
~~d\(x\)~~d\(y~~\)&
~~d\(x\)~(d\(y\))~
\\
\(f_{13}\)&
\(((x)~y~)\)&
\;d\(x\)~(d\(y\))~&
~~d\(x\)~~d\(y~~\)&
((d\(x\))(d\(y\)))&
~(d\(x\))~d\(y~~\)
\\
\(f_{14}\)&
\(((x)(y))\)&
~~d\(x\)~~d\(y~~\)&
\;d\(x\)~(d\(y\))~&
~(d\(x\))~d\(y~~\)&
((d\(x\))(d\(y\)))
\\
\hline
\(f_{15}\)&
1&
0&
0&
0&
0
\\
\hline
\end{tabular}&fg=000000$

Fourier Transforms of Boolean Functions

Re: Another Problem

The problem is concretely about Boolean functions $latex {f}$ of $latex {k}$ variables, and seems not to involve prime numbers at all. For any subset $latex {S}$ of the coordinates, 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.

\(k = 1\!\)

\(k = 2\!\)

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

<p align="center">
$latex
\begin{tabular}{|c||*{4}{c}|}
\multicolumn{5}{c}{Table 2.1. Values of \( \chi_S(x) \) for \( f : \mathbb{B}^2 \to \mathbb{B} \)} \\[4pt]
\hline
\( S \backslash (u, v)  \) &
\( (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{tabular}
&fg=000000$
</p>
<p align="center">
$latex
\begin{tabular}{|*{5}{c|}*{4}{r|}}
\multicolumn{9}{c}{Table 2.2. Fourier Coefficients of Boolean Functions on Two Variables} \\[4pt]
\hline
~&~&~&~&~&~&~&~&~\\
\( 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{tabular}&fg=000000$
</p>

Work 2

Array Test

$latex
|x| = \left\{
\begin{array}{ll}
x  & \text{if \( x \geq 0 \)};
\\
-x & \text{if \( x < 0 \)}.
\end{array}
\right.
&fg=000000$
$latex
|x| = \left\{
\begin{array}{ll}
x  & \text{if}~ x \geq 0;
\\
-x & \text{if}~ x < 0.
\end{array}
\right.
&fg=000000$
$latex
\begin{array}{*{9}{l}}
Alpha & Bravo & Charlie & Delta & Echo & Foxtrot & Golf & Hotel & India
\\
Juliet & Kilo & Lima & Mike & November & Oscar & Papa & Quebec & Romeo
\\
Sierra & Tango & Uniform & Victor & Whiskey & X\text{-}ray & Yankee & Zulu & \varnothing
\end{array}&fg=000000$

Matrix Test

$latex
\begin{matrix}
Alpha & Bravo & Charlie & Delta & Echo & Foxtrot & Golf & Hotel & India
\\
Juliet & Kilo & Lima & Mike & November & Oscar & Papa & Quebec & Romeo
\\
Sierra & Tango & Uniform & Victor & Whiskey & X\text{-}ray & Yankee & Zulu & \varnothing
\end{matrix}&fg=000000$

Tabular Test 1

$latex
\begin{tabular}{lll}
Chicago & U.S.A. & 1893
\\
Z\"{u}rich & Switzerland & 1897
\\
Paris & France & 1900
\\
Heidelberg & Germany & 1904
\\
Rome & Italy & 1908
\end{tabular}&fg=000000$

Tabular Test 2

$latex
\begin{tabular}{|r|r|}
\hline
\( n \) & \( n! \) \\
\hline
1 & 1 \\
2 & 2 \\
3 & 6 \\
4 & 24 \\
5 & 120 \\
6 & 720 \\
7 & 5040 \\
8 & 40320 \\
9 & 362880 \\
10 & 3628800 \\
\hline
\end{tabular}&fg=000000$

Tabular Test 3

$latex
\begin{tabular}{|c|c|*{16}{c}|}
\multicolumn{18}{c}{Table 1. Higher Order Propositions \( (n = 1) \)} \\[4pt]
\hline
\( f \) & \( f \) &
\( m_{0}  \)  & \( m_{1}  \) & \( m_{2}  \) & \( m_{3}  \) &
\( m_{4}  \)  & \( m_{5}  \) & \( m_{6}  \) & \( m_{7}  \) &
\( m_{8}  \)  & \( m_{9}  \) & \( m_{10} \) & \( m_{11} \) &
\( m_{12} \)  & \( m_{13} \) & \( m_{14} \) & \( m_{15} \) \\[4pt]
\hline
\( f_0 \) & \texttt{()} &
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\[4pt]
\( f_1 \) & \texttt{(}\( x \)\texttt{)} &
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\[4pt]
\( f_2 \) & \( x \) &
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\[4pt]
\( f_3 \) & \texttt{(())} &
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\[4pt]
\hline
\end{tabular}&fg=000000$

Tabular Test 4

$latex
\begin{tabular}{|*{7}{c|}}
\multicolumn{7}{c}{\textbf{Table A1. Propositional Forms on Two Variables}} \\
\hline
\( L_1 \) &
\( L_2 \) &&
\( L_3 \) &
\( L_4 \) &
\( L_5 \) &
\( L_6 \) \\
\hline
& & \( x = \) & 1 1 0 0 & & & \\
& & \( y = \) & 1 0 1 0 & & & \\
\hline
\( f_{0} \) &
\( f_{0000} \) &&
0 0 0 0 &
\( (~) \) &
false &
\( 0 \)
\\
\( f_{1} \) &
\( f_{0001} \) &&
0 0 0 1 &
\( (x)(y) \) &
neither \( x \) nor \( y \) &
\( \lnot x \land \lnot y \)
\\
\( f_{2} \) &
\( f_{0010} \) &&
0 0 1 0 &
\( (x)\ y \) &
\( y \) without \( x \) &
\( \lnot x \land y \)
\\
\( f_{3} \) &
\( f_{0011} \) &&
0 0 1 1 &
\( (x) \) &
not \( x \) &
\( \lnot x \)
\\
\( f_{4} \) &
\( f_{0100} \) &&
0 1 0 0 &
\( x\ (y) \) &
\( x \) without \( y \) &
\( x \land \lnot y \)
\\
\( f_{5} \) &
\( f_{0101} \) &&
0 1 0 1 &
\( (y) \) &
not \( y \) &
\( \lnot y \)
\\
\( f_{6} \) &
\( f_{0110} \) &&
0 1 1 0 &
\( (x,\ y) \) &
\( x \) not equal to \( y \) &
\( x \ne y \)
\\
\( f_{7} \) &
\( f_{0111} \) &&
0 1 1 1 &
\( (x\ y) \) &
not both \( x \) and \( y \) &
\( \lnot x \lor \lnot y \)
\\
\hline
\( f_{8} \) &
\( f_{1000} \) &&
1 0 0 0 &
\( x\ y \) &
\( x \) and \( y \) &
\( x \land y \)
\\
\( f_{9} \) &
\( f_{1001} \)  &&
1 0 0 1 &
\( ((x,\ y)) \) &
\( x \) equal to \( y \) &
\( x = y \)
\\
\( f_{10} \) &
\( f_{1010} \) &&
1 0 1 0 &
\( y \) &
\( y \) &
\( y \)
\\
\( f_{11} \) &
\( f_{1011} \) &&
1 0 1 1 &
\( (x\ (y)) \) &
not \( x \) without \( y \) &
\( x \Rightarrow y \)
\\
\( f_{12} \) &
\( f_{1100} \) &&
1 1 0 0 &
\( x \) &
\( x \) &
\( x \)
\\
\( f_{13} \) &
\( f_{1101} \) &&
1 1 0 1 &
\( ((x)\ y) \) &
not \( y \) without \( x \) &
\( x \Leftarrow y \)
\\
\( f_{14} \) &
\( f_{1110} \) &&
1 1 1 0 &
\( ((x)(y)) \) &
\( x \) or \( y \) &
\( x \lor y \)
\\
\( f_{15} \) &
\( f_{1111} \) &&
1 1 1 1 &
\( ((~)) \) &
true &
\( 1 \)
\\
\hline
\end{tabular}&fg=000000$

Table Test 1

<table border="0" style="border-width:0;width:100%;">

<tr>
<td style="border-top:1px solid white;width:35%;"></td>

<td style="border-top:1px solid white;width:65%;">
Can we ever become what we weren’t in eternity?
Can we ever learn what we weren’t born knowing?
Can we ever share what we never had in common?</td>
</tr>

</table>

Table Test 2

<table align="left" border="0" style="border-width:0;">

<tr>
<td style="border-top:1px solid white;">
<p>Everything considered, a determined soul will always manage.</p></td>

<td style="border-top:1px solid white;">(41)</td>
</tr>

<tr>
<td style="border-top:1px solid white;">
<p>To a man devoid of blinders, there is no finer sight than that of the intelligence at grips with a reality that transcends it.</p></td>

<td style="border-top:1px solid white;">(55)</td>
</tr>

</table>

Table Test 3

<table align="center" border="0">

<tr>
<td>
<br>
<p>Everything considered, a determined soul will always manage.</p></td>

<td><p>(41)</p></td>
</tr>

<tr>
<td>
<br>
<p>To a man devoid of blinders, there is no finer sight than that
of the intelligence at grips with a reality that transcends it.</p></td>

<td><p>(55)</p></td>
</tr>

</table>

Table Test 4

<table align="center" border="0" style="border-width:0;text-align:center;">

<tr>
<td style="border-top:1px solid white;">
<a href="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure1visibleframe1.jpg" title="Logical Graph Figure 1">
<img src="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure1visibleframe1.jpg" alt="()()=()" width="500" height="168" border="0"></a></td>

<td style="border-top:1px solid white;">(1)</td>
</tr>

<tr> 
<td style="border-top:1px solid white;">
<a href="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure2visibleframe1.jpg" title="Logical Graph Figure 2">
<img src="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure2visibleframe1.jpg" alt="(())= " width="500" height="168" border="0"></a></td>

<td style="border-top:1px solid white;">(2)</td>
</tr>

</table>

Table Test 5

<table align="center" border="0" style="text-align:center;">

<tr>
<td style="padding:10px;">
<a href="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure1visibleframe1.jpg" title="Logical Graph Figure 1">
<img src="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure1visibleframe1.jpg" alt="()()=()" align="center" width="500" height="168" /></a></td>

<td style="padding:80px 10px;">(1)</td>
</tr>

<tr>
<td style="padding:10px;">
<a href="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure2visibleframe1.jpg" title="Logical Graph Figure 2">
<img src="http://inquiryintoinquiry.files.wordpress.com/2008/09/logicalgraphfigure2visibleframe1.jpg" alt="(())= " align="center" width="500" height="168" /></a></td>

<td style="padding:80px 10px;">(2)</td>
</tr>

</table>

Table Test 6

<table align="center" border="0" style="text-align:center;">

<caption><font size="+2">$latex \text{Table 1.} ~~ \text{Higher Order Propositions} ~ (n = 1) $</font></caption>

<tr>
<td style="border-bottom:2px solid black;">$latex m_{0} $</td>
<td style="border-bottom:2px solid black;">$latex m_{1} $</td>
<td style="border-bottom:2px solid black;">$latex m_{2} $</td>
<td style="border-bottom:2px solid black;">$latex m_{3} $</td>
<td style="border-bottom:2px solid black;">$latex m_{4} $</td>
<td style="border-bottom:2px solid black;">$latex m_{5} $</td>
<td style="border-bottom:2px solid black;">$latex m_{6} $</td>
<td style="border-bottom:2px solid black;">$latex m_{7} $</td>
</tr>

<tr>
<td style="background:white;color:black;">0</td>
<td style="background:black;color:white;">1</td>
<td style="background:white;color:black;">0</td>
<td style="background:black;color:white;">1</td>
<td style="background:white;color:black;">0</td>
<td style="background:black;color:white;">1</td>
<td style="background:white;color:black;">0</td>
<td style="background:black;color:white;">1</td>
</tr>

<tr>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:black;color:white;">1</td>
<td style="background:black;color:white;">1</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:black;color:white;">1</td>
<td style="background:black;color:white;">1</td>
</tr>

<tr>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:black;color:white;">1</td>
<td style="background:black;color:white;">1</td>
<td style="background:black;color:white;">1</td>
<td style="background:black;color:white;">1</td>
</tr>

<tr>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
<td style="background:white;color:black;">0</td>
</tr>

</table>