Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent

Question

Consider the hash function mapping $w$-bit keys to hash values in $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x_1,...,x_c)$ of $c$ $r$-bit keys.

Consider the hash family:

$$H = \{h_{T_1,...,T_c}:T_i \in \{0,...,m-1\}^{2^r}\}$$

where

$$h_{T_1,...,T_c}(x) = \sum\limits_{1\le i \le c}T_i[x_i]\mod m$$

Prove that $H$ is $3$-wise independent, but not $4$-wise independent.

$H$ is $k$-wise independent if for inputs $x_1,...,x_k$ and output $v_1,...,v_k$, $\Pr[h(x_1) = v_1 \wedge ... \wedge h(x_k)=v_k] = \frac{1}{m^k}$

So I can certainly see why $H$ is $1$-wise and $2$-wise independent if we're choosing inputs to the hash function that must be different from each other. However, I'm having a lot of trouble seeing why the family is not $4$-wise independent, which I think lends greatly to my difficulty in proving that the family is $3$-wise independent.

So for the family to not be $4$-wise independent, if we have inputs $x_1,...,x_4$ and outputs $v_1,...,v_4$, $\Pr[h(x_1)=v_1\wedge...\wedge h(x_4)=v_4]\not = \frac{1}{m^4}$. I am trying to think of a counterexample where this will not be the case, but it seems like we need, for example, $x_4$ to be constructed in such a way that $v_4$ can be attained by some combination of $v_1,v_2,v_3$. However, all of $x_1,...,x_4$ are $w$-bit keys, so even if $x_4$ had bits taken from each of $x_1,x_2,x_3$, the output $v_4$ would still be some random sum corresponding to the $c$ $r$-bit blocks accessing each $T_i$.

Is there something I'm missing here? Perhaps it's not possible for $v_4$ to be some combination of $v_1,...,v_3$, but how else would we show that $H$ is not $4$-wise independent?

Answer 1

Hint for refuting 4-wise independence: Suppose for simplicity that $c = 2$, pick some $\alpha \neq \beta$ of length $r$, and consider the four inputs $(\alpha,\alpha),(\alpha,\beta),(\beta,\alpha),(\beta,\beta)$.

Hint for proving 3-wise independence: Let the three inputs be $x,y,z$. If there is some coordinate $i$ such that $x_i,y_i,z_i$ are all different then we are done. Otherwise, without loss of generality there are coordinates $i,j$ such that $x_i = y_i \neq z_i$ and $x_j = z_j \neq y_j$, and we are again done.