Return to Answer

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 \frac{ r } { \log_2 q -2} +1$$

showing the bound is fairly tight.

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.

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

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 \frac{ r } { \log_2 q -2} +1$$

showing the bound is fairly tight.

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

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