MyWikiBiz

Changes

User:Jon Awbrey/WORDPRESS (view source)

Revision as of 03:14, 4 June 2013

5,831 bytes added ,  03:14, 4 June 2013
→‎Fourier Transforms of Boolean Functions: + text
Line 834: Line 834:     
===Fourier Transforms of Boolean Functions===
 
===Fourier Transforms of Boolean Functions===
 +
 +
<pre>
 +
Re: <a href="http://rjlipton.wordpress.com/2013/05/21/twin-primes-are-useful/" target="_blank">Another Problem</a>
 +
 +
<div style="margin-left:30px;">
 +
 +
<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">
 +
$latex \displaystyle \hat{f}(S) = \frac{1}{2^k} \sum_{x \in \mathbb{Z}_2^k} f(x)\chi_S(x)$</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.
 +
 +
$latex {k = 1}$
 +
 +
&hellip;
 +
 +
$latex {k = 2}$
 +
 +
For ease of reading formulas, let $latex {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)  \) &amp;
 +
\( (1, 1) \) &amp;
 +
\( (1, 0) \) &amp;
 +
\( (0, 1) \) &amp;
 +
\( (0, 0) \)
 +
\\
 +
\hline\hline
 +
\( \varnothing \) &amp; \( +1 \) &amp; \( +1 \) &amp; \( +1 \) &amp; \( +1 \) \\
 +
\( \{ u \} \)    &amp; \( -1 \) &amp; \( -1 \) &amp; \( +1 \) &amp; \( +1 \) \\
 +
\( \{ v \} \)    &amp; \( -1 \) &amp; \( +1 \) &amp; \( -1 \) &amp; \( +1 \) \\
 +
\( \{ u, v \} \)  &amp; \( +1 \) &amp; \( -1 \) &amp; \( -1 \) &amp; \( +1 \) \\
 +
\hline
 +
\end{tabular}
 +
&amp;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
 +
~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~\\
 +
\( L_1 \)&amp;
 +
\( L_2 \)&amp;&amp;
 +
\( L_3 \)&amp;
 +
\( L_4 \)&amp;
 +
\( \hat{f}(\varnothing) \)&amp;
 +
\( \hat{f}(\{u\})    \)&amp;
 +
\( \hat{f}(\{v\})    \)&amp;
 +
\( \hat{f}(\{u,v\}) \)
 +
\\
 +
~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~\\
 +
\hline
 +
&amp;&amp; \(u =\)&amp; 1 1 0 0&amp;&amp;&amp;&amp;&amp; \\
 +
&amp;&amp; \(v =\)&amp; 1 0 1 0&amp;&amp;&amp;&amp;&amp; \\
 +
\hline
 +
\(f_{0}\)&amp;
 +
\(f_{0000}\)&amp;&amp;
 +
0 0 0 0&amp;
 +
\((~)\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)
 +
\\
 +
\(f_{1}\)&amp;
 +
\(f_{0001}\)&amp;&amp;
 +
0 0 0 1&amp;
 +
\((u)(v)\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)
 +
\\
 +
\(f_{2}\)&amp;
 +
\(f_{0010}\)&amp;&amp;
 +
0 0 1 0&amp;
 +
\((u)~v~\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{3}\)&amp;
 +
\(f_{0011}\)&amp;&amp;
 +
0 0 1 1&amp;
 +
\((u)\)&amp;
 +
\(1/2\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{4}\)&amp;
 +
\(f_{0100}\)&amp;&amp;
 +
0 1 0 0&amp;
 +
\(~u~(v)\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{5}\)&amp;
 +
\(f_{0101}\)&amp;&amp;
 +
0 1 0 1&amp;
 +
\((v)\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{6}\)&amp;
 +
\(f_{0110}\)&amp;&amp;
 +
0 1 1 0&amp;
 +
\((u,~v)\)&amp;
 +
\( 1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)&amp;
 +
\(-1/2\)
 +
\\
 +
\(f_{7}\)&amp;
 +
\(f_{0111}\)&amp;&amp;
 +
0 1 1 1&amp;
 +
\((u~~v)\)&amp;
 +
\( 3/4\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\hline
 +
\(f_{8}\)&amp;
 +
\(f_{1000}\)&amp;&amp;
 +
1 0 0 0&amp;
 +
\(~u~~v~\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{9}\)&amp;
 +
\(f_{1001}\)&amp;&amp;
 +
1 0 0 1&amp;
 +
\(((u,~v))\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)&amp;
 +
\(1/2\)
 +
\\
 +
\(f_{10}\)&amp;
 +
\(f_{1010}\)&amp;&amp;
 +
1 0 1 0&amp;
 +
\(v\)&amp;
 +
\( 1/2\)&amp;
 +
\( 0 \)&amp;
 +
\(-1/2\)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{11}\)&amp;
 +
\(f_{1011}\)&amp;&amp;
 +
1 0 1 1&amp;
 +
\((~u~(v))\)&amp;
 +
\( 3/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{12}\)&amp;
 +
\(f_{1100}\)&amp;&amp;
 +
1 1 0 0&amp;
 +
\(u\)&amp;
 +
\( 1/2\)&amp;
 +
\(-1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{13}\)&amp;
 +
\(f_{1101}\)&amp;&amp;
 +
1 1 0 1&amp;
 +
\(((u)~v~)\)&amp;
 +
\( 3/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{14}\)&amp;
 +
\(f_{1110}\)&amp;&amp;
 +
1 1 1 0&amp;
 +
\(((u)(v))\)&amp;
 +
\( 3/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{15}\)&amp;
 +
\(f_{1111}\)&amp;&amp;
 +
1 1 1 1&amp;
 +
\(((~))\)&amp;
 +
\(1\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)
 +
\\
 +
\hline
 +
\end{tabular}&amp;fg=000000$
 +
</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>
    
==Work 2==
 
==Work 2==
Jon Awbrey
12,080

edits

Retrieved from "https://mywikibiz.com/Special:MobileDiff/181666"