MOD functions spanning the vector space $\mathbb{R}^{\{0,1\}^n}$ Let $MOD_{a,c}^r:\{0,1\}^n\to\{-1,1\}$ denote the function 
$$MOD_{a,c}^r(x)=\cases{-1 \ a\cdot x+c\equiv0\ (\text{mod r}) \\ 1 \ \text{else }}$$
Here $\cdot$ is the usual dot product.
I want to prove that for every given $r\ge 2$, the set of all $MOD_{a,c}^r$ functions on ${\{0,1\}^n}$ where $a\in\mathbb{Z}_r^n, c\in\mathbb{Z}_r$ spans the vector space $\mathbb{R}^{\{0,1\}^n}$.
Usually I'd try to find a "nice" set of characteristic functions (e.g. functions that are 1 for every value in ${\{0,1\}^n}$ except one, for which the function return -1) but I can't seem to do it here.
 A: Nice question. 
Observations: 


*

*The set of functions $MOD_{a,c}^{r}$ contains $MOD_{a,c}^{d}$ for $d|r$. To see this, take the coordinates of $a$ and $c$ to be divisible by $\frac{r}{d}$.

*Thus it is enough to prove this for $r$ prime. 

*For $r=2$, these functions are $\pm(-1)^{<x,v>}$ where $v\in \{0,1\}^{n}$. These are the characters of $\mathbb{Z}_{2}^{n}$, and it is well-known that they span the set of functions.

*Odd $r$ requires different insight.


Induction:
The key to the solution is induction. I'll add the additional superscript "$n$": $MOD_{a,c}^{r,n}$. I won't assume anything about $r$ other than $r\ge 2$.
n=1: You can choose $c=0$ to get the functions $(-1,-1),(-1,1)$ ($a=0,1$), which span $\mathbb{R}^{\{0,1\}}$. 
Induction step: Now we'll use induction on $n$. Suppose the claim is valid for $n$, and I'll prove it for $n+1$. 
Lifting a function: By choosing $a_i=0$, we get a function $MOD_{a,c}^{r,n+1}$ that doesn't "care" about the $i$'th coordinate. We can regard it as a function in $\mathbb{R}^{\{0,1\}^{n-1}}$, extended naturally to $\mathbb{R}^{\{0,1\}^{n}}$. 
This idea can be generalized - we can lift any combination of $MOD_{a,c}^{r,n}$ to a combination of $MOD_{a',c}^{r,n+1}$ (where $a'=(a_1,\cdots,a_{k-1},0,a_{k},\cdots,a_{n})$), and this can be done in $n+1$ different ways (for each value of $k$ up to $n+1$). 
Since  $MOD_{a,c}^{r,n}$ span $\mathbb{R}^{\{0,1\}^{n}}$ by induction, in particular it spans $e_{i}$, $i \in \{0,1\}^{n}$. Identifying $\{ 0,1\}^{n}$ with integers between $0$ and $2^n-1$, those basis function lift to $f_{j,j'} = e_{j} + e_{j'}$, where $j\text{ xor }j'$ is a power of 2 and $f$ lives in $\mathbb{R}^{\{0,1\}^{n+1}}$.
Constructing almost everything: We can construct $(e_{0}+e_{2^i})-(e_{2^i}+e_{2^i+2^j})+(e_{2^{i}+2^{j}}+e_{2^i+2^j+2k})\mp \cdots$, i.e. $e_{0}-(-1)^{Hammming(i)}e_{i}$. Taking combinations of those shows that we can construct
$$\sum_{i\neq 0} c_i e_i - (\sum_{i \neq 0} (-1)^{Hamming(i)}c_i)e_0$$
or equivalently,
$$\sum_{i \ge 0} c_i e_i , \sum_{i} (-1)^{Hamming(i)}c_i = 0$$
which has co-dimension 1. So we've reduced the problem to constructing some function $\sum_{i \ge 0} c_i e_i$ with $\sum_{i} (-1)^{Hamming(i)}c_i \neq 0$.
Case 1: $2|r$. Take the function attained by $c=r/2,a_1=\cdots=a_{n+1}=r/2$, which is $f=\sum_{i} (-1)^{Hamming(i)}e_{i}$.
Case 2: $2 \nmid r$. Let $p$ be a prime factor of $r$. Take the function attained by $c=\frac{r}{p}c',a_1=\cdots=a_{n+1}=r/p$, where $c'$ will be determined later. This function is $f=\sum_{i} (-1)^{Hamming(i) \equiv c' \mod p}e_{i}$. For it to satisfy the inequality $\sum_{i} (-1)^{Hamming(i)}c_i \neq 0$, we need
$$g_{n+1}(c')=\sum_{i \equiv c' \mod p}\binom{n+1}{i} (-1)^{i} \neq 0$$
(I skipped some calculations) By using the generating function $(1-x)^{n+1}$, one finds that $g_{n+1}(c')=\frac{1}{p} \sum_{i=0}^{p-1} (1-\omega_{p}^{i})^{n+1}\omega_{p}^{-ic'}$, where$\omega_p = e^{\frac{2\pi i}{p}}$. $g$ can't vanish for $c'=0,1,\cdots ,p-1$ simultaneously, since the vector $(g(0),\cdots,g(p-1))^T$ is a product of a Vandermonde matrix (which is non-singular) by the vector $v_i = \frac{1}{p}(1-\omega_p^i)^{n+1}$ which is non-zero. Choose $c'$ such that $g(c')\neq 0$.
The induction is complete. $\blacksquare$
Remark: My solution shows that you don't need all your $r^{n+1}$ MOD functions, you can use those with $a_i \in \{0, \frac{r}{p} \}$ where $p$ is a fixed prime divisor of $r$ (say, the smallest), and $c$ a multiple of $\frac{r}{p}$. Those are $2^n \cdot p$ functions. I believe this can be lowered by a closer examination of the proof.
EDIT: Note that $g_n(i)=(-1)^{n}g(n-i)$, $g(i+p)=g(i)$. Using Lucas' Theorem, which basically states $\binom{ap+b}{cp+d} = \binom{a}{c} \binom{b}{d} \mod p$ where $0 \le b,d < p$, one can show that $p|g(i)$ for any $i$, which is cool (I checked this only for odd $p$).
It can be seen, by the symmetry $\binom{n}{i}=\binom{n}{n-i}$, that $g_{pk+2a}(a) = 0$ for odd $k$, so sadly there's no $a$ such that $g_{n}(a) \neq 0$ for all $n$...
But I do suspect that the only solutions to $g_{n}(a)=0$ are of the form $n-2a=p(2k+1)$! This will show that for any $n$, either $a=0$ or $a=1$ will give $g_{n}(a) \neq 0$.
In other words-
Conjecture: The functions $\{ MOD_{a,c}^{r} | c \in \{ 0, 1 \}, a_i \in \{ 0,1 \} \}$ span $\mathbb{R}^{\{0,1\}^n}$.
A formulation using algebraic number theory, is the following:
$$\sum_{i=1}^{p-1} (1-\omega_p^i)^{n} = \operatorname{Tr}((1-\omega_p)^n) \neq 0$$
when $n-2a$ is not an odd multiple of $p$. (The trace is over the Cyclotomic extension $\mathbb{Q}(\omega_p)/\mathbb{Q}$.)
