2
$\begingroup$

Let $\chi_S: \mathbb{F}_2^n \to \{\pm 1\}, x \mapsto (-1)^{\sum_{i \in S}x_i}$ for every $S \subseteq [n]$ denote the parity functions from $\mathbb{F}_2^n$ to $\{\pm 1\}$. Then, of course, every $f: \mathbb{F}_2^n \to \{\pm 1\}$ can be written as a linear combination (over $\mathbb{R}$) of the parity functions. I have tried (without much ease or success), to produce the Fourier expansions of compositions of even simple Boolean functions, in particular of conjunctions of parity functions, like $\chi_S \wedge \chi_T$ (where under the encoding of $1_{\mathbb{F}_2^n} \mapsto -1,0_{\mathbb{F}_2^n} \mapsto +1$, $\wedge$ is just $\max_2$).

So, my questions are:

  1. Are there good techniques/tools in general for computing/estimating the Fourier expansion of $f \circ g$ when we know both of the expansions for both $f,g$?
  2. Is there something we can say about the particular case of conjunctions/disjunctions over parity functions?
$\endgroup$

1 Answer 1

1
$\begingroup$

If $f,g$ are two $\pm1$-valued functions and $f \lor g$ is their maximum (this is the standard notation for maximum; $\land$ stands for minimum), then $$ f \lor g = \frac{1 + f + g - fg}{2}. $$ Since $\chi_S \chi_T = \chi_{S \Delta T}$, this shows that $$ \chi_S \lor \chi_T = \frac{1}{2} + \frac{\chi_S}{2} + \frac{\chi_T}{2} - \frac{\chi_{S\Delta T}}{2}. $$ You can read the Fourier expansion from this (unless $S = T$, in which case $\chi_S \lor \chi_S = \chi_S$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.