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

CC BY-SA 4.0
2024-07-06T02:56:27.137Z
2024-07-07T00:34:42.490Z
2024-07-07T00:34:42.490Z
Command Master
<p>I want to prove that for every boolean function <span class="math-container">$f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$</span> the (normalized) Hamming distance from a certain linear boolean function (i.e. a boolean function <span class="math-container">$f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$</span> that satisfies <span class="math-container">$\forall$</span> <span class="math-container">$x, y$</span> <span class="math-container">$\in$</span>  <span class="math-container">$\{0,1\}^n: f(x+y)=f(x)+f(y)$</span>) is at most <span class="math-container">$\frac{1}{2}$</span>.
In other words, I want to show that in order to make an arbitrary boolean function <span class="math-container">$f$</span> linear (that is to turn it to some linear boolean <span class="math-container">$g:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$</span> function), we need to change the value of at most half its inputs.</p>
<p>I am aware that there is an answer to this using Fourier analysis of boolean functions, here is book about the topic : <a href="https://www.cs.tau.ac.il/%7Eamnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf" rel="nofollow noreferrer">https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf</a> 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).</p>

CC BY-SA 4.0
2024-07-05T21:00:33.193Z
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$?
Martin Berger
CC BY-SA 4.0
2024-07-05T21:04:48.197Z
Also asked on https://cs.stackexchange.com/questions/168901/showing-that-every-boolean-function-is-1-2-close-to-being-a-linear-boolean-fun and https://math.stackexchange.com/questions/4942036/all-boolean-functions-are-not-too-far-in-hamming-distance-from-some-linear-funct
Martin Berger
CC BY-SA 4.0
2024-07-06T06:54:28.780Z
Cross-posted: https://cstheory.stackexchange.com/q/54463/5038, https://math.stackexchange.com/q/4942036/14578, https://cs.stackexchange.com/q/168901/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<boolean-functions><fourier-analysis>
How close is a Boolean function from being a linear boolean function?
usul
# How close is a Boolean function from being a linear boolean function?

(Asked by: username_0 on 2024-07-05)

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](https://www.cs.tau.ac.il/%7Eamnon/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).

**Tags:** boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: 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$?  
> **username_1**: Also asked on https://cs.stackexchange.com/questions/168901/showing-that-every-boolean-function-is-1-2-close-to-being-a-linear-boolean-fun and https://math.stackexchange.com/questions/4942036/all-boolean-functions-are-not-too-far-in-hamming-distance-from-some-linear-funct  
> **username_2**: Cross-posted: https://cstheory.stackexchange.com/q/54463/5038, https://math.stackexchange.com/q/4942036/14578, https://cs.stackexchange.com/q/168901/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_3 on 2024-07-06. Score: 4 | Accepted answer

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


---

