12,089
edits
Changes
MyWikiBiz, Author Your Legacy — Wednesday September 10, 2025
Jump to navigationJump to search→Fourier Transforms of Boolean Functions
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
&fg=000000$
</pre>
</pre>
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
&fg=000000$
</pre>
</pre>
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
&fg=000000$
</pre>
</pre>
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
&fg=000000$
</pre>
</pre>
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
&fg=000000$
</pre>
</pre>
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
&fg=000000$
</pre>
</pre>
<blockquote>
<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 <math>f\!</math> of <math>k\!</math> variables, and seems not to involve prime numbers at all. For any subset <math>S\!</math> of the coordinates, the corresponding Fourier coefficient is given by:</p>
<p align="center">
<p align="center"><math>\hat{f}(S) = \frac{1}{2^k} \sum_{x \in \mathbb{Z}_2^k} f(x)\chi_S(x)\!</math></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 <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>
<p>where <math>\chi_S(x)\!</math> is <math>-1\!</math> if <math>\textstyle \sum_{i \in S} x_i\!</math> is odd, and <math>+1\!</math> otherwise.</p>
</blockquote>
</blockquote>
For ease of reading formulas, let <math>x = (x_1, x_2) = (u, v).\!</math>
For ease of reading formulas, let <math>x = (x_1, x_2) = (u, v).\!</math>
====Table 2.1. Values of χ<sub>S</sub>(x)====
<pre>
<pre>
$latex
$latex
\begin{tabular}{|c||*{4}{c}|}
\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]
\multicolumn{5}{c}{Table 2.1. Values of \( \boldsymbol{\chi}_\mathcal{S}(x) \) for \( f : \mathbb{B}^2 \to \mathbb{B} \)} \\[4pt]
\hline
\hline
\( S \backslash (u, v) \) &
\( \mathcal{S} \backslash (u, v) \) &
\( (1, 1) \) &
\( (1, 1) \) &
\( (1, 0) \) &
\( (1, 0) \) &
\end{tabular}
\end{tabular}
&fg=000000$
&fg=000000$
</pre>
</pre>
====Table 2.2. Fourier Coefficients of Boolean Functions on Two Variables====
<pre>
<pre>
$latex
$latex
\begin{tabular}{|*{5}{c|}*{4}{r|}}
\begin{tabular}{|*{5}{c|}*{4}{r|}}
\hline
\hline
~&~&~&~&~&~&~&~&~\\
~&~&~&~&~&~&~&~&~\\
\( L_1 \)&
\(L_1\)&\(L_2\)&&\(L_3\)&\(L_4\)&
\( L_2 \)&&
\(\hat{f}(\varnothing)\)&\(\hat{f}(\{u\})\)&\(\hat{f}(\{v\})\)&\(\hat{f}(\{u,v\})\) \\
\( L_3 \)&
\( L_4 \)&
\( \hat{f}(\varnothing) \)&
\( \hat{f}(\{u\}) \)&
\( \hat{f}(\{v\}) \)&
\( \hat{f}(\{u,v\}) \)
\\
~&~&~&~&~&~&~&~&~\\
~&~&~&~&~&~&~&~&~\\
\hline
\hline
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
</p>
&fg=000000$
</pre>
====Table 2.3. Fourier Coefficients of Boolean Functions on Two Variables====
<pre>
$latex
\begin{tabular}{|*{5}{c|}*{4}{r|}}
\multicolumn{9}{c}{Table 2.3. 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\)
\\
\hline
\(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_{4}\)&
\(f_{0100}\)&&
0 1 0 0&
\(~u~(v)\)&
\( 1/4\)&
\(-1/4\)&
\( 1/4\)&
\(-1/4\)
\\
\(f_{8}\)&
\(f_{1000}\)&&
1 0 0 0&
\(~u~~v~\)&
\( 1/4\)&
\(-1/4\)&
\(-1/4\)&
\( 1/4\)
\\
\hline
\(f_{3}\)&
\(f_{0011}\)&&
0 0 1 1&
\((u)\)&
\(1/2\)&
\(1/2\)&
\( 0 \)&
\( 0 \)
\\
\(f_{12}\)&
\(f_{1100}\)&&
1 1 0 0&
\(u\)&
\( 1/2\)&
\(-1/2\)&
\( 0 \)&
\( 0 \)
\\
\hline
\(f_{6}\)&
\(f_{0110}\)&&
0 1 1 0&
\((u,~v)\)&
\( 1/2\)&
\( 0 \)&
\( 0 \)&
\(-1/2\)
\\
\(f_{9}\)&
\(f_{1001}\)&&
1 0 0 1&
\(((u,~v))\)&
\(1/2\)&
\( 0 \)&
\( 0 \)&
\(1/2\)
\\
\hline
\(f_{5}\)&
\(f_{0101}\)&&
0 1 0 1&
\((v)\)&
\(1/2\)&
\( 0 \)&
\(1/2\)&
\( 0 \)
\\
\(f_{10}\)&
\(f_{1010}\)&&
1 0 1 0&
\(v\)&
\( 1/2\)&
\( 0 \)&
\(-1/2\)&
\( 0 \)
\\
\hline
\(f_{7}\)&
\(f_{0111}\)&&
0 1 1 1&
\((u~~v)\)&
\( 3/4\)&
\( 1/4\)&
\( 1/4\)&
\(-1/4\)
\\
\hline
\(f_{11}\)&
\(f_{1011}\)&&
1 0 1 1&
\((~u~(v))\)&
\( 3/4\)&
\( 1/4\)&
\(-1/4\)&
\( 1/4\)
\\
\(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\)
\\
\hline
\(f_{15}\)&
\(f_{1111}\)&&
1 1 1 1&
\(((~))\)&
\(1\)&
\(0\)&
\(0\)&
\(0\)
\\
\hline
\end{tabular}
&fg=000000$
</pre>
</pre>
