MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Hei, this site is for research-level questions, so this question is not appropriate here. See for some places where your question will be more likely to get an answer. – MTS Jun 8 '12 at 4:23
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. – David Feldman Jun 8 '12 at 4:57
David, thank you. Before I submitted the question, I read through 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. – Xiali Hei Jun 8 '12 at 5:16
Which asymptotic region are you interested in? – Gjergji Zaimi Jun 8 '12 at 8:41
I think I misunderstood the question. Withdrawing my vote to close. – MTS Jun 8 '12 at 16:09
up vote 4 down vote accepted

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.

share|cite|improve this answer
I am traveling. Thank everyone here. After my traveling, I will update my ideas and goals. – 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)\}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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