1
$\begingroup$

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.

1 Answers 1

1

Nice question.

Observations:

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

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

  3. For $r=2$, these functions are $\pm(-1)^{}$ 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.

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