0
$\begingroup$

Consider $\mathbb{Z}_q \equiv \mathbb{Z}/q\mathbb{Z}$, where $q \geqslant 2$. A set of vectors in $\mathbb{Z}_q^n$ is said to be linearly independent if no nontrivial linear combination of them produces the zero vector. When $q$ is a prime (and hence $\mathbb{Z}_q$ is a field), the following is true: Given any $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, we are guaranteed to find $\lceil\log_qk\rceil$ linearly independent vectors among them. This does not seem to be true when $q$ is not a prime; for example, even just one vector $(3,3)$ is not linearly independent in $\mathbb{Z}_6^2$. My question is then the following: is there an obvious lower bound, perhaps not too different from the above, on the number of linearly independent vectors that we are guaranteed to find among any given $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, but such that it holds for arbitrary $q$?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Generalizing your $(3,3)$ example, if $p$ is any prime divisor of $q$, then $p\mathbb Z_q^n$ is a set of $(q/p)^n$ vectors that does not contain a single linearly independent vector, according to your interpretation of the definition. Does that not answer the questin negatively? $\endgroup$
    – Emil Jeřábek
    Commented Jun 13 at 18:19
  • 4
    $\begingroup$ For $n=1$, there are $\varphi(q)$ elements of $\mathbb{Z}/q\mathbb{Z}$ that are (each, separately) “linearly independent”, so to find a single vector you need $q-\varphi(q)+1$ vectors. This does not bode well for your question. $\endgroup$
    – Gro-Tsen
    Commented Jun 13 at 18:20

0

Reset to default

You must log in to answer this question.