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).


1 Answer 1


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


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.