Mutually independent vectors with small, integer coefficients Consider a family $\cal V$ of $n$ vectors $v_1,\ldots,v_n$ in ${\mathbb N}^3$ (here ${\mathbb N}$ denotes the set of positive integers, excluding $0$). Say that $\cal V$ is strongly independent if any three vectors $v_i,v_j,v_k$ in $\cal V$ with $i<j<k$ are linearly independent. Also, define the size of $\cal V$ to be $\max_{v\in {\cal V}} ||v||_{\infty}$, where $||(x,y,z)||_{\infty}=\max(|x|,|y|,|z|)$.
Using a "Van der Monde" construction with $v_k=(1,k,k^2)$, one achieves a strongly independent family with size $n^2$.
Question. For every $n\geq 3$, is there a strongly independent family with size at most $n$ ?
The answer is yes for $n\leq 9$, by considering the family $v_k=(1,k,a_k)$
where $a_k$ is the $k$-th element in $1, 2, 1, 2, 4, 3, 4, 3, 8$.
 A: This is a partial answer that provides a strongly independent family with size at most $n$ when $n$ is a prime number.

Suppose $n$ is a prime number.
Let $v_k=(1, k,(k^2-1){\%}n+1)$ for $1\le k\le n$, where $\%$ is the residue operator, i.e. $x\%n$ is the unique interger between $0$ and $n-1$ that is $x$ modulo $n$. Note that each coordinate of $v_k$ is between $1$ and $n$ and the last coordinate is $k^2\bmod n$.
When $1\le i,j,k\le n$ are distinct, since $$\begin{vmatrix}v_i\\v_j\\v_k\end{vmatrix}
\equiv_n\begin{vmatrix}
  1 & i & i^2\\
  1 & j & j^2\\
  1 & k & k^2 \end{vmatrix}
= (j-i)(k-i)(k-j)\not\equiv_n0,$$ we see that $v_i, v_j,v_k$ are linearly independent.
A: A modification of Apass.Jack's method works for all $n\ge 4$:
Let $p$ be a prime number such that $\frac n 2 + 1 \le p < n$. This exists for all $n\ge 4$ by Bertrand's postulate. Let $f_p(i)$ be the integer in $\{1,\dots,p\}$ such that $i^2\equiv f_p(i)$ mod $p$. Then, for $i\in \{1,\dots,p-1\}$, define \begin{eqnarray}
v_i(t) = (1+tp,i,f_p(i))
\end{eqnarray}
The set ${\cal V} = \{v_i(t)\mid i\in\{1..p-1\} \text{ and } t\in\{0,1\}\}$ has $2(p-1) \ge n$ elements, and the maximum entry is $p+1\le n$. We claim that $\cal V$ is strongly independent.
We select $3$ vectors from $\cal V$. Either they all have distinct subscripts, or two of them have the same subscript. If all subscripts are distinct, we have a Vandermonde matrix mod $p$, i.e. $$
\det\begin{bmatrix}v_i(t_1)\\v_j(t_2)\\v_k(t_3)\end{bmatrix}\equiv\det\begin{bmatrix}1&i&i^2\\1&j&j^2\\1&k&k^2\end{bmatrix}=(j-i)(k-j)(k-i)\not\equiv 0 \mod p
$$
On the other hand, if two have the same subscript, then the three vectors must be $v_i(0),v_i(1)$ and $v_j(t)$ for some $i\ne j$ and $t=0,1$. Observe: $$
\det\begin{bmatrix}v_i(0)\\v_i(1)\\v_j(t)\end{bmatrix} = \det\begin{bmatrix}1&i&f_p(i)\\1+p&i&f_p(i)\\1+tp & j & f_p(j)\end{bmatrix} = if_p(j)-jf_p(i) - (1+p)(if_p(j) - jf_p(i)) = -p (if_p(j)-jf_p(i))
$$
This is nonzero because $p\ne0$ and, mod $p$, the other factor is $$if_p(j)-jf_p(i)\equiv ij^2-ji^2 \equiv ij(j-i)\not\equiv 0\mod p$$ because $i,j<p$ and $p$ is prime.
A: There exists a strongly independent family with size $\ge n$, and asymptotically with size $\frac 3 2 n$.
We use vectors $(n, i, j)$ with $i,j$ integers in $[1,n]$. If each of these vectors is represented by a pair of points $(O,A_k)$, points $A_k$ are all on the same face of the $n$-sided cube.
Then, $3$ of these vectors are linearly dependent iff the $3$ points $A_k$ are aligned: the line to which the $3$ points belong is the intersection of the plane that includes the $3$ vectors, and the face of the cube where the $A_k$ are placed.
So the problem can be solved by finding sets of points in an integer square grid $[1, n] \times [1,n]$, with no $3$ points aligned. This is the no-three-in-line problem.
The best lower bound currently known comes from an article by Hall, R. R.; Jackson, T. H.; Sudbery, A.; Wild, K. (1975): "Some advances in the no-three-in-line problem", which can be (freely) read here. The articles proves that on a $n \times n$ grid, one can place at least $n$ points with no three-in-line, and $\forall \varepsilon > 0, \exists N, \forall n>N$ one can place $(\frac 3 2 - \varepsilon)n$ points.
Note that this is rather suboptimal: we use only one face of the cube, where we could use the $3$ faces facing the origin; and of course we could use interior points of the cube, too.
