# How close is a Boolean function from being a linear boolean function?

I want to prove that for every boolean function $$f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$$ the (normalized) Hamming distance from a certain linear boolean function (i.e. a boolean function $$f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$$ that satisfies $$\forall$$ $$x, y$$ $$\in$$ $$\{0,1\}^n: f(x+y)=f(x)+f(y)$$) is at most $$\frac{1}{2}$$. In other words, I want to show that in order to make an arbitrary boolean function $$f$$ linear (that is to turn it to some linear boolean $$g:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$$ function), we need to change the value of at most half its inputs.

I am aware that there is an answer to this using Fourier analysis of boolean functions, here is book about the topic : https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf but since I don't know much about this topic, I was wondering if there is a simpler method to solve this question. Any kind of help is welcomed (even help with the Fourier analysis maybe from the perspective of linear algebra or some resources about the topic).

• What is $+$ in your question, disjunction or XOR? Also, if $f$ is an $n$-ary linear function, isn't the Hamming distance between $f$ and the bitwise negation of $f$ maximal, i.e. $2^n$? Commented Jul 5 at 21:00
• Commented Jul 5 at 21:04
• – D.W.
Commented Jul 6 at 6:54

Let's choose a random $$r$$ and look at the distance from $$g(x) = \langle r, x \rangle$$. Because for any $$x \ne 0$$, $$g(x)$$ is uniformly distributed, by linearity of expectation the expected number of places where $$g$$ and $$f$$ agree is at least $$\frac{2^n - 1}2$$. Therefore, for some $$r$$, they agree in at least $$\lceil \frac{2^n - 1}2 \rceil = 2^{n-1}$$ locations, so the hamming distance is at most $$2^{n-1}$$.