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).

  • $\begingroup$ The structure of $\mathbf{F}_2^n$ is not important, is it? As it is written now, we could talk about a subset of $\mathbf{F}_2^m$ or size $2^n$ instead of $\mathrm{Im} f$ just the same. $\endgroup$ – Mikhail Tikhomirov Nov 2 '18 at 19:35
  • $\begingroup$ @Mikhail. The structure of $F_2^n$ might come into play when spelling out the conditions on $f$ and $m$ (e.g. $m-n$ might be required to be large enough etc.). $\endgroup$ – Michele Nov 2 '18 at 19:56
  • $\begingroup$ Indeed, if you fix n-1 members of the set, you have fewer than 2^{m-n+1} choices for the remaining assignment. Gerhard "Wonders About Shape Of Image" Paseman, 2018.11.02. $\endgroup$ – Gerhard Paseman Nov 2 '18 at 21:34
  • $\begingroup$ I do not fix n-1 members, as I require that the property holds for each set $S$ (I changed for any to for each to make this more explicit). $\endgroup$ – Michele Nov 2 '18 at 21:57
  • $\begingroup$ @JyrkiLahtonen. Yees... This seems to work, and is way simpler than the GRS construction pointed to by Kodlu (whom I thank, anyway). Can you write this as an answer? Also if you have any suggestion on ways to make it more efficient, I would greatly appreciate it. $\endgroup$ – Michele Nov 5 '18 at 13:55

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.

  • $\begingroup$ I won't quantify that "likely". There may be semi-obvious obstructions. I haven't really thought about how large $m$ absolutely has to be for the required mapping to exist. $\endgroup$ – Jyrki Lahtonen Nov 5 '18 at 14:46
  • $\begingroup$ Many thanks. As for improvements, I think the result on Vandermonde matrices here may help. What do you think? $\endgroup$ – Michele Nov 5 '18 at 16:03

Simon McNicol et al, in Traitor tracing against powerful attacks, IEEE ISIT Proceedings 2005 (sorry can't find a free link yet) have defined $\delta-$nonlinear codes, as a code where for any collection of $\leq \delta$ codewords, the sum is not a codeword.

They take generalized Reed Solomon codes and use a concatenated construction together with a permutation of the codewords of the GRS.

The GRS code has alphabet $\mathbb{F}_{2^n}$ a permutation polynomial in $\mathbb{F}_{2^n}[x]$ is specified, and if the following conditions hold, there exists a code with the property you want. This code is over $\mathbb{F}_{2^n}$ so you'd need to represent codewords as $n-$ vectors which will multiply codeword length by $n$.

Theorem: If $2^n>r(s+1)-1,$ and $$N>\binom{\delta+1}{2} s,$$ then a $\delta-$nonlinear code derived from a GRS code exists. Here $r$ is the degree of the permutation polynomial used in the construction.

Conversion to binary means that the blocklength (your $m$) of the code is actually $nN.$

It would be interesting to look at randomized constructions which wouldn't have the structure in their construction (they wanted the distance distribution of the GRS code to be preserved) which would probably be more efficient.

I will give more details later when I have more time.

  • $\begingroup$ Hello, trying to understand your answer: why are you requiring $M\geq F$? It's not that we want to map each subset to a different sub-space.. $\endgroup$ – Michele Nov 2 '18 at 22:33
  • $\begingroup$ You're right that's overkill. $\endgroup$ – kodlu Nov 2 '18 at 22:38
  • $\begingroup$ Thanks. I just got the paper and trying to make my mind on it. $\endgroup$ – Michele Nov 3 '18 at 10:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.