# An extremal 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]$

• Are there specific regions in "parameter space" that are of greatest interest to you? For instance, do you primarily care about the case when $q$ is small and $r$ is large? – Michael Zieve Aug 7 '13 at 20:19
• Actually for every finite $q$ and $r$, I am interested. – T.... Aug 7 '13 at 20:44
• One more particular toy example I am interested is $q=7$ and $r=8$, $r=16$, $r=24$ and $r=85$. If you get $N$ for $r=8$, do you get $2N$ and $3N$ for $r=16$ and $r=24$? And what happens at $r=85$? – T.... Aug 7 '13 at 21:35
• I guess thinking again, I am interested in $q$ relatively small (but not that small) compared to $r$. – T.... Aug 7 '13 at 21:45
• For $q$ fixed as $r$ varies, we have a lower bound that is linear in $r$ (my answer), and an upper bound that is linear in $r$ (concatenation). So the growth is at least asymptotically linear. – Will Sawin Aug 8 '13 at 19:44

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.

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.

• Where does $2^r$ come from? $|S| = 3^r-1$. Also is the $\log$ here base $2$? – T.... Aug 8 '13 at 19:47
• Is your bound tight? Can you give an example with $r >q$ that meets your bound? – T.... Aug 8 '13 at 19:50
• I'm not using $S$, but rather the set of $0$-$1$ vectors. The key fact is that the difference of any two distinct $0$-$1$ vectors is in $S$. My bound is tight for $N=1$, as Michael Zieve showed. I think by concatenating Michael's example, we can give an upper bound that differs by at most a constant. – Will Sawin Aug 8 '13 at 19:55
• It seems highly plausible that $r=8, q=6, N=6$ exists, which would be a tight example. – Will Sawin Aug 8 '13 at 19:56
• I see. If possible please provide the upper bound as well? I am highly interested in your result. It looks like what I need. But need to see upper bound as well and the constant particularly you are talking off. So far this has been very enlightening to me. – T.... Aug 8 '13 at 19:59