Skip to main content
2 of 4
added 428 characters in body
Will Sawin
  • 148.8k
  • 9
  • 324
  • 563

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} { \log q -\log 2}$$

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} { \log q \lfloor \frac{q}{2} \rfloor}$$

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

Will Sawin
  • 148.8k
  • 9
  • 324
  • 563