Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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)^{<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.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.