<p>Let $f:\mathbb{F}^n_2\rightarrow \{0,1\}$ be a function constant on an affine subspace $V$ of co-dimension $t$. Assume that that $V$ is a linear subspace, by replacing $f(x)$ with $f(x+v)$ for some $v \in V$. Let $W$ be the quotient subspace $\mathbb{F}^n_2/W$ so that $dim(W)=t$ and $\mathbb{F}^n_2=V+W$. Let $\pi_V:\mathbb{F}^n_2\rightarrow V$ and $\pi_W:\mathbb{F}^n_2 \rightarrow W$ be the projection maps to $V$ and $W$. Then:</p>

<p>$$f|_V(v)=\sum_{i=1}^r \hat{f}(\alpha_i)(-1)^{\langle v,\pi_V(\alpha_i)\rangle},$$</p>

<p>where $rank(f)=r$. In particular, as $f$ is constant on $V$, it must be the case that for every non-zero $\alpha_i$ there exists some $\alpha_j$ such that $\pi_V(\alpha_i)=\pi_V(\alpha_j)$, or equivalently $\alpha_i+\alpha_j\in W$.</p>

<p>I reported exactly the piece of the proof that I don't completely understand, could somebody explain me these two points:</p>

<ol>
<li>Why do we need to assume that $V$ is a linear subspace?</li>
<li>Why there must be $\alpha_i$ and $\alpha_j$ satisfying the property above?</li>
</ol>

CC BY-SA 3.0
2016-08-28T10:13:45.457Z
What is the result you are trying to prove?
Emil Jeřábek
CC BY-SA 3.0
2016-08-28T12:34:14.350Z
It's Lemma 3.6 from this paper http://eccc.hpi-web.de/report/2016/044/download
Marco
<linear-algebra><fourier-analysis>
Fourier expansion of boolean functions and affine subspaces
Marco
# Fourier expansion of boolean functions and affine subspaces

(Asked by: username_0 on 2016-08-27)

Let $f:\mathbb{F}^n\_2\rightarrow \{0,1\}$ be a function constant on an affine subspace $V$ of co-dimension $t$. Assume that that $V$ is a linear subspace, by replacing $f(x)$ with $f(x+v)$ for some $v \in V$. Let $W$ be the quotient subspace $\mathbb{F}^n\_2/W$ so that $dim(W)=t$ and $\mathbb{F}^n\_2=V+W$. Let $\pi\_V:\mathbb{F}^n\_2\rightarrow V$ and $\pi\_W:\mathbb{F}^n\_2 \rightarrow W$ be the projection maps to $V$ and $W$. Then:

$$f|\_V(v)=\sum\_{i=1}^r \hat{f}(\alpha\_i)(-1)^{\langle v,\pi\_V(\alpha\_i)\rangle},$$

where $rank(f)=r$. In particular, as $f$ is constant on $V$, it must be the case that for every non-zero $\alpha\_i$ there exists some $\alpha\_j$ such that $\pi\_V(\alpha\_i)=\pi\_V(\alpha\_j)$, or equivalently $\alpha\_i+\alpha\_j\in W$.

I reported exactly the piece of the proof that I don't completely understand, could somebody explain me these two points:

1. Why do we need to assume that $V$ is a linear subspace?
2. Why there must be $\alpha\_i$ and $\alpha\_j$ satisfying the property above?

**Tags:** linear-algebra, fourier-analysis
> **Comments:**
> **username_1**: What is the result you are trying to prove?  
> **username_0**: It's Lemma 3.6 from this paper http://eccc.hpi-web.de/report/2016/044/download  

---

## 0 answers

