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!
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\}$.