6
$\begingroup$

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

$\endgroup$
5
  • $\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$ Nov 2, 2018 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, 2018 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$ Nov 2, 2018 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, 2018 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, 2018 at 13:55

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Nov 5, 2018 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, 2018 at 16:03
1
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2018 at 22:33
  • $\begingroup$ You're right that's overkill. $\endgroup$
    – kodlu
    Nov 2, 2018 at 22:38
  • $\begingroup$ Thanks. I just got the paper and trying to make my mind on it. $\endgroup$
    – Michele
    Nov 3, 2018 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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