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?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.