5
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\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
    Commented Jun 8, 2012 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$
    – David Feldman
    Commented Jun 8, 2012 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
    Commented Jun 8, 2012 at 5:16
  • 1
    $\begingroup$ Which asymptotic region are you interested in? $\endgroup$
    – Gjergji Zaimi
    Commented Jun 8, 2012 at 8:41
  • 2
    $\begingroup$ I think I misunderstood the question. Withdrawing my vote to close. $\endgroup$
    – MTS
    Commented Jun 8, 2012 at 16:09

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am traveling. Thank everyone here. After my traveling, I will update my ideas and goals. $\endgroup$
    – Xiali Hei
    Commented Jun 11, 2012 at 3:58
3
$\begingroup$

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)\}$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .