Tamaño máximo de $k$ -conjunto linealmente independiente dentro de $\lbrace 1, 2, 3, ..., u \rbrace^k$

Question

Dado un número entero positivo $u$ cuántos $k$ -vectores dimensionales cuyas coordenadas están todas en $\lbrace 1, 2, 3, ..., u\rbrace$ puede elegir para que cualquier $k$ son linealmente independientes? Equivalentemente, ¿cuál es el tamaño del mayor subconjunto de $\lbrace 1, 2, 3, ... u \rbrace^k$ de modo que cada hiperplano que pasa por el origen contenga como máximo $k-1$ de ellos?

Si $k=2$ dos vectores son linealmente dependientes si tienen la misma pendiente, por lo que el número máximo de vectores independientes entre sí es el número de pendientes distintas $y/x$ con $1\le x,y \le u$ ,

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

ya que el número de pendientes hasta $1$ con denominador reducido $n$ es $\phi(n)$ y pendientes distintas de $1$ vienen en pares recíprocos.

Answer 1

Tony ya mencionó que el tamaño máximo de un conjunto de vectores que se $k$ -linealmente independientes sobre un campo finito $\mathbb F_q$ crece linealmente con $q$ .

En nuestra situación, sin embargo, esto ya no es cierto, y el orden correcto de la asíntota es $O(u^{k/(k-1)})$ . Es decir, si mantienes $k$ fijo, el número máximo de $k$ -vectores linealmente independientes de $\lbrace 1,2,\dots, u\rbrace ^k$ es $\sim u^{k/(k-1)}$ . Se tiene el mismo orden de magnitud para el número mínimo de subespacios lineales necesarios para cubrir los puntos $\lbrace 1,2,\dots, u\rbrace ^k$ . Estas afirmaciones se demuestran en

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

Aquí es el enlace arxiv. Creo que el orden de magnitud correcto para el número máximo de tales $k$ -de modo que cualquier $r$ son linealmente independientes no se conoce para $r < k$ . Véase este artículo para obtener referencias sobre tales generalizaciones.

Answer 2

No es una respuesta, pero puede que también te interese el análogo "campo finito" de tu pregunta. Es decir, dado un campo finito $\mathbb{F}_q$ ¿cuál es el tamaño máximo de un subconjunto de vectores $S \subset \mathbb{F}_q^k$ de modo que cada subconjunto de $S$ de tamaño $k$ es linealmente independiente.

Una antigua conjetura de Segre afirma que el tamaño máximo de dicho conjunto es como máximo $q+1$ (salvo en algunos casos excepcionales). Este papel de Ball demuestra la conjetura para $q$ prime (y algunos otros casos). También demuestra que los ejemplos más grandes son todos esencialmente equivalentes al siguiente ejemplo:

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