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

  • 1
    $\begingroup$ 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? $\endgroup$ – Michael Zieve Aug 7 '13 at 20:19
  • $\begingroup$ Actually for every finite $q$ and $r$, I am interested. $\endgroup$ – T.... Aug 7 '13 at 20:44
  • $\begingroup$ 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$? $\endgroup$ – T.... Aug 7 '13 at 21:35
  • $\begingroup$ I guess thinking again, I am interested in $q$ relatively small (but not that small) compared to $r$. $\endgroup$ – T.... Aug 7 '13 at 21:45
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Where does $2^r$ come from? $|S| = 3^r-1$. Also is the $\log$ here base $2$? $\endgroup$ – T.... Aug 8 '13 at 19:47
  • $\begingroup$ Is your bound tight? Can you give an example with $r >q$ that meets your bound? $\endgroup$ – T.... Aug 8 '13 at 19:50
  • $\begingroup$ 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. $\endgroup$ – Will Sawin Aug 8 '13 at 19:55
  • $\begingroup$ It seems highly plausible that $r=8, q=6, N=6$ exists, which would be a tight example. $\endgroup$ – Will Sawin Aug 8 '13 at 19:56
  • $\begingroup$ 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. $\endgroup$ – T.... Aug 8 '13 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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