| 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> |
| | | | |
| | … | | … |
| | | | |
| − | $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: |
| | &fg=000000$ | | &fg=000000$ |
| | </p> | | </p> |
| | + | </pre> |
| | | | |
| | + | <pre> |
| | <p align="center"> | | <p align="center"> |
| | $latex | | $latex |
| Line 1,050: |
Line 1,047: |
| | \end{tabular}&fg=000000$ | | \end{tabular}&fg=000000$ |
| | </p> | | </p> |
| − |
| |
| − | <i>To be continued …</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> |
| | | | |
