Cross Posting from: https://math.stackexchange.com/questions/462016/a-combinatorics-problem-over-finite-rings

Consider the set $S$ of all non-zero vectors over $\Bbb Z_{q}$ of length $r$ whose coordinates are from $\{0,1,q-1\}$ with $q>4$ odd. $S$ has cardinality $3^{r}-1$.

How many vectors over $\Bbb Z_{q}$ of length $r$ does one exactly need in a new set $T$(vectors in $T$ have any possible coordinate from $\Bbb Z_{q}$) such that when we take inner product of members of $S$ with members of $T$, for every vector $s \in S$, $\exists t \in T$ such that the inner product $\langle s, t \rangle \notin \{0,1,q-1\}$?

If this problem is hard, is there at least a tight upper bound for $|T|$?

If upper bound is also hard, how about tight lower bound?

Note:$\{0,1,q-1\}$ is not same as $\{0,\dots,q-1\}$.

From Comment of Jyrki Lahtonen: "Consider the following example. Take $q=37$ and $r=4$. Unless I have misunderstood a set $T$ consisting of the single vector $(2,4,8,16)$ works, as we cannot write $\pm1$ as a signed knapsack sum of the components of this vector. With a large $q$ we have a lot of elbow room, but the combinatorial difficulties appear daunting to me. The general case may be very difficult."

For $q=7$, $r=8$, is $|T|=5$?

With these $5$ vectors as elements of $T$ I am able to force all but $8$ vectors of $S$ to the constraint (Since $|S| = 3^8-1=6560$, $8$ out of $6560$ is less than $0.12195122\%$):

$[2 4 3 5 0 0 0 0]$

$[0 0 0 0 2 4 3 5]$

$[6 6 3 2 0 0 0 0]$

$[0 0 0 0 6 6 3 2]$

$[0 0 0 3 0 0 0 1]$

Is there a different set of five vectors of $T$ which will force all of $S$ to be under the constraint?

The $8$ remaining vectors of $S$ are:

$[0 0 0 0 6 0 6 1]$

$[0 0 0 0 6 0 0 6]$

$[0 0 0 0 6 0 1 1]$

$[0 0 0 0 6 1 1 6]$

$[0 0 0 0 1 6 6 1]$

$[0 0 0 0 1 0 6 6]$

$[0 0 0 0 1 0 0 1]$

$[0 0 0 0 1 0 1 6]$