An extremal combinatorics problem over Finite Rings

Question

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]$

Answer 1

If $q>2^{r+1}$ then you can take $T$ to consist of the single vector $(2,4,8,...,2^r)$, just as in Jyrkhi Lahtonen's example.

Answer 2

Let $N=|T|$, then there are $q^N$ possible functions from $T$ to $\mathbb Z/q$. Each of the $2^r$ vectors whose entries are all $0$ or $1$ gives such a function, by dotting it with these elements of $T$, and the map must be injective - otherwise the difference of two distinct $0$-$1$ vectors, an element of $S$, provides a counterexample. In fact, no two entries can get sent to functions whose entries differ by at most $1$. So the image is a subset of the function space of size $q^N$ of density at most $2^N$, so

$$2^r \leq (q/2)^N$$

$$ N \geq \frac{ r } { \log_2 q -1}$$

which shows that Michael Zieve's exampe gives the only case when $|T|=1$.

EDIT: The estimate $2^r \leq (q/2)^N$ comes from the fact that we can only fit that many $2 \times 2 \times \dots \times 2$ cubes in $\mathbb Z/q^N$. I think that for $q$ odd we can in fact fit only $\lfloor \frac{q}{2} \rfloor$ such cubes, in which case the bound improves to

$$ N \geq \frac{ r } { \log_2 \lfloor \frac{q}{2} \rfloor}$$

which in the case $q=7$, $r=8$, is $5.05>5$, giving a lower bound of $6$.

EDIT 2: For a matching upper bound, round $q$ down to the nearest power of $2$, $q'$ then round $r$ up to the nearest multiple of $\log_2 q'-1$, $r'$. Then this bound is tight, because we can take $r'/(\log_2 q'-1)$ copies of Michael Zieve's vector, each padded with $0$s. Since $\log_2 q'> \log_2 q - 1$, we have:

$$ N \leq \lceil\frac{ r } {\lfloor\log_2 q \rfloor -1} \rceil $$

showing the bound is fairly tight.