2

Suppose I have a Boolean function $ f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2 $ which satisfies the following property:

$$d(f, \ell)\leq 2^{n-1}\quad\forall\; \text{linear functions}\; \ell .$$

where $d(.,.)$ is the Hamming distance between two functions. I want to prove that this implies that $f$ must then be linear itself. In other words, if a function differs at at most half the points in $\mathbb{F}_2^{n}$ from every linear function, then it itself must be linear.

Any help is much appreciated. Thanks!

JQX
  • 159

1 Answers1

2

Here is an approach based on Fourier analysis (cf., for instance, the excellent book and notes by Ryan O'Donnell).

For convenience, I'll consider $f$ as a Boolean function with the (equivalent) $\pm1$ view, i.e. $f\colon \{-1,+1\}^n \to \{-1,+1\}$; and denote by $\chi_S$ (for $S\subseteq[n]$) the $2^n$ linear functions (parities) that form the Fourier basis.

Then, the fact that $f$ is at distance at most $1/2$ in (normalized) Hamming distance to any $\chi_S$ means that the correlations, and therefore the Fourier coefficients $\widehat{f}(S)$, are all nonnegative: $$ \widehat{f}(S) = \langle f,\chi_S\rangle = \mathbb{E}_x[f(x)\chi_S(x)] = 1-2\mathbb{P}\{f(x)\neq \chi_S(x)\} \geq 0. $$

Since $\lVert f\rVert_2^2 = \mathbb{E}_x[f(x)^2] = 1$ (as $f(x)^2 = 1$ for all $x$), we have by Parseval's identity that $$ 1 = \sum_{S \subseteq[n]} \widehat{f}(S)^2 \leq \sum_{S \subseteq[n]} \lvert\widehat{f}(S)\rvert = \sum_{S \subseteq[n]} \widehat{f}(S) $$ the last equality following from the nonegativity. Moreover, the middle inequality is strict, unless there exists $S^\ast$ such that $\lvert\widehat{f}(S^\ast)\rvert=1$ (and all other $\widehat{f}(S)$'s are zero). Which is exactly saying that $f = \lvert\widehat{f}(S^\ast)\rvert\chi_{S^\ast} = \widehat{f}(S^\ast)\chi_{S^\ast}$, i.e. $f$ is a parity function: if it's the case, we are done.

If $f$ is not, then the inequality is strict. But then recall that we have $$ f(1^n) = \sum_{S \subseteq[n]} \widehat{f}(S)\underbrace{\chi_S(1^n)}_{=1} = \sum_{S \subseteq[n]} \widehat{f}(S) > 1 $$ which is a contradiction, as $f$ (a Boolean function) takes values in $\{-1,1\}$.

Clement C.
  • 67,323
  • 1
    Damn. I've been thinking about this for a while, decided to convert it to a harmonic analysis thing exactly as you did, saw the solution just now and I was just starting to type it up when you posted essentially the same thing. – David C. Ullrich Mar 31 '16 at 18:25
  • @DavidC.Ullrich To be honest, I've been confused for a while on how to use the Boolean range (the crucial step at the end). I started trying something general for functions with range $\mathbb{R}$ assuming only unit norm, but the conclusion does not hold under these weaker assumptions... – Clement C. Mar 31 '16 at 18:29
  • My last step was your first, realizing that "if not" then we need to show that there exists $\chi$ with $\hat f(\chi)<0$... – David C. Ullrich Mar 31 '16 at 18:31