How many boolean functions $\{-1,1\}^n \to \{-1,1\}$ with Fourier degree at most $d$?
By Fourier degree I mean the maximal cardinality of $S$ such that the Fourier coefficient $\hat{f}(S)$ is not zero.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ You can get a decent bound by combining Emil's comment to your previous question (which I suspect is reasonably tight) with the fact that decision tree complexity is at most $O(d^3)$ for a degree-$d$ Boolean function. $\endgroup$– Jason GaitondeCommented Aug 21, 2023 at 19:46
-
$\begingroup$ @JasonGaitonde I want some non-trivial estimate for, say $d = 0.9 n$... if d just less then $n$ it is possible to calculate by using a binomial coefficient. Maybe it is possible to generalized... $\endgroup$– Alexey MilovanovCommented Aug 21, 2023 at 22:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I wrote a Mathematica code snippet to count for cases of small $n$ and $d$.
n = 2;
inputWords = Tuples[{-1, 1}, n];
outputResults = Tuples[{-1, 1}, 2^n];
expr = {Product[1/2 (1 + Subscript[a, i] Subscript[x, i]), {i, n}]}~
Join~Array[{Subscript[a, #], {-1, 1}} &, n];
allIndicatorFunctions = Flatten[Table @@ expr];
allBooleanFunctions = Table[Expand[fa . allIndicatorFunctions], {fa, outputResults}];
allBooleanFunctions // TableForm
polynomialDegree[expr_] := Max[0, Max[Total@*First /@ CoefficientRules[expr]]];
(polynomialDegree /@ allBooleanFunctions) // Tally
The number of boolean functions $\{ -1, 1\}^{n} \rightarrow \{-1, 1 \}$ whose Fourier degree equals to $d$:
$$ \begin{array}{c|ccccccccccc} n\backslash d & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 1 & 2 & 2 & - & - & - & - & - & - & - \\ 2 & 2 & 4 & 10 & - & - & - & - & - & - \\ 3 & 2 & 6 & 62 & 186 & - & - & - & - & - \\ 4 & 2 & 8 & 212 & 12648 & 52666 & - & - & - & - \\ \cdots & - & - & - & - & - & - & - & - & - \end{array} $$
The diagonal elements in the array are A037267.
$\begingroup$
$\endgroup$
I believe this is unknown in general, though we have the basic relationships $$ \sum_{S} |\hat{f}(S)|^2=2^{2n} $$ and $$ \sum_{S} \hat{f}(S)\hat{f}(S\Delta S')=0,\qquad\forall S \neq \emptyset $$
for the unnormalized coefficients of a valid Fourier transform. In the second equation (Titsworth formula) we have the symmetric difference of two sets $S,S'$ which looks kind of ugly, it would just be a modulo 2 sum of the characteristic functions of the two sets in the coding theory as opposed to TCS notation for Boolean functions.
