1
$\begingroup$

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?
$\endgroup$

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.