Given a positive integer $u$, how many $k$-dimensional vectors whose coordinates are all in $\lbrace 1, 2, 3, ..., u\rbrace$ can you choose so that any $k$ of them are linearly independent? Equivalently, what is the size of the largest subset of $\lbrace 1, 2, 3, ... u \rbrace^k$ so that each hyperplane through the origin contains at most $k-1$ of them?

If $k=2$, two vectors are linearly dependent iff they have the same slope, so the maximum number of pairwise independent vectors is the number of distinct slopes $y/x$ with $1\le x,y \le u$,

$$ -1 + 2\sum_{n=1}^u \phi(n),$$

since the number of slopes up to $1$ with reduced denominator $n$ is $\phi(n)$, and slopes other than $1$ come in reciprocal pairs.

  • $\begingroup$ Hei, this site is for research-level questions, so this question is not appropriate here. See mathoverflow.net/faq#whatnot for some places where your question will be more likely to get an answer. $\endgroup$
    – MTS
    Jun 8 '12 at 4:23
  • 1
    $\begingroup$ I rewrote the main question so that it does sound research level, at least at the moment, at least to my ears. (Is it easy and I don't see it, MTS?) I couldn't make sense of the "sub problem" so I deleted that part for now. $\endgroup$ Jun 8 '12 at 4:57
  • $\begingroup$ David, thank you. Before I submitted the question, I read through mathoverflow.net/howtoask. I just wanted to make this question very clear, specific and precise. Actually, my original question is an optimization problem as you stated with many constraints. $\endgroup$
    – Xiali Hei
    Jun 8 '12 at 5:16
  • 1
    $\begingroup$ Which asymptotic region are you interested in? $\endgroup$ Jun 8 '12 at 8:41
  • 2
    $\begingroup$ I think I misunderstood the question. Withdrawing my vote to close. $\endgroup$
    – MTS
    Jun 8 '12 at 16:09

Tony already mentioned that the maximum size of a set of vectors that are $k$-wise linearly independent over a finite field $\mathbb F_q$ grows linearly with $q$.

In our situation, however, this is no longer true, and the right order of asymptotics is $O(u^{k/(k-1)})$. That is, if you keep $k$ fixed, the maximum number of $k$-wise linearly independent vectors from $\lbrace 1,2,\dots, u\rbrace ^k$ is $\sim u^{k/(k-1)}$. One has the same order of magnitude for the minimal number of linear subspaces needed to cover the points $\lbrace 1,2,\dots, u\rbrace ^k$. These statements are proved in

I. Barany, G. Harcos, J. Pach and G. Tardos, "Covering Lattice Points by Subspaces", Per. Math. Hung. 43, 2001, 93-103.

Here is the arxiv link. I think that the right order of magnitude for the maximum number of such $k$-dimensional vectors so that any $r$ are linearly independent is not known for $r < k$. See this artcle for references on such generalizations.

  • $\begingroup$ I am traveling. Thank everyone here. After my traveling, I will update my ideas and goals. $\endgroup$
    – Xiali Hei
    Jun 11 '12 at 3:58

Not an answer, but you may also be interested in the 'finite field' analogue of your question. Namely, given a finite field $\mathbb{F}_q$, what is the maximum size of a subset of vectors $S \subset \mathbb{F}_q^k$ so that every subset of $S$ of size $k$ is linearly independent.

An old conjecture of Segre asserts that the maximum size of such a set is at most $q+1$, (except for some exceptional cases). This paper of Ball proves the conjecture for $q$ prime (and some other cases). He also proves that the largest examples are all essentially equivalent to the following example:

$$S:=\{(1,t, t^2, \dots, t^{k-1}) : t \in \mathbb{F}_q \} \cup \{(0, \dots, 0, 1)\}$$


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.