Let $\mathbb{F}\_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n\_2\rightarrow \mathbb{F}\_2^m$ (for some $m\geq 1$) such that:


1. $f$ is *injective*;
2. for each $S\subseteq \mathbb{F}^n\_2$, with $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of *linearly independent* vectors in $\mathbb{F}\_2^m$ (seen as a vector space over $\mathbb{F}\_2$).


Both $m$ and the returned representation of $f$ should be "succinct", that is, of size polynomial in $n$.


The algorithm might also be probabilistic, in the sense that the two required properties might hold with "high probability" (possibly approaching 1 as $m-n$ grows).



Nonlinear boolean functions
A relatively obvious, but possibly inefficient construction would be to identify the space $\Bbb{F}\_2^n$ with the extension field $K=\Bbb{F}\_{2^n}$.
With $m=n^2$ we can then similarly identify $\Bbb{F}\_2^m$ with $K^n$.


The mapping
$$
f:K\to K^n, x\mapsto (1,x,x^2,\ldots,x^{n-1})
$$
will then work. The reason is that if $x\_1,x\_2,\ldots,x\_n$ are distinct elements of $K$ the matrix $\in M\_{n\times n}(K)$ with rows $f(x\_i),i=1,2,\ldots,n$, is a Vandermonde matrix known to have a non-vanishing determinant. That last piece implies that $\{f(x\_1),f(x\_2),\ldots,f(x\_n)\}$ will be linearly independent.


But, it will even be linearly independent over $K$ rather than just $\Bbb{F}\_2$. That's why there is likely to be room for improvement. Particularly when linear dependence with high probability suffices.


