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:

$f$ is

*injective*;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).

for eachset $S$ (I changedfor anytofor eachto make this more explicit). $\endgroup$ – Michele Nov 2 '18 at 21:57