Boolean functions that are not too far from all linear functions. 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!
 A: 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\}$.
