# Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?

Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that $$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$ Where two strings $s_1,s_2$ have length $2^n$ and $\forall i\in\{1,\cdots,n^c\}, \; f_i(s_j)\leq n^d, \; j\in \{1,2\}$?

It seems a little similar to hash functions but since we don't have any restrictions (e.g. having uniform distribution or being oneway) our hands are open to define whatever we like.

I think it's not possible. Because we have $2^{2^n}$ strings of size $2^n$ and transformring them into polynomial size strings means we have put many strings in a single string. But when I make an example this comes to my mind that maybe by defining a good design for each function we can recognize the difference by probability one.

One example can be:

For $c=3$ and $d=1$,

$f_1$: it takes string of length $2^n$ and transforms it to $mod\, n$.

$f_2$: it takes string of length $2^n$. (suppose we have divided $2^{2^n}$ strings into $\frac{2^{2^n}}{n}$ collections) If the input belongs to $i$th collection, $f_2$ transforms it to $i$.

$f_3$: it takes string of length $2^n$ and transforms it to the number which shows its $1$s number.

The probability that for two strings $s_1$ and $s_2$, these three maps $f_1, f_2,f_3$ be the same would be $$\frac{1}{n}\times \frac{1}{n} \times \frac{1}{2^{2n}}$$ That is negligible.

So my question is that can we ever understand the difference of two long strings with probability $1$ using polynomial size strings?

## 1 Answer

There is no sequence of functions $f_1,...,f_{n^c}:\{0,1\}^{2^n}\rightarrow\{0,1\}^{n^d}$, such that for all $s_1\neq s_2\in\{0,1\}^{2^n}$ $\exists i\in\{1,...,n^c\} : f_1(s_1)\neq f_i(s_2)$.

Examine the function $F:\{0,1\}^{2^n}\rightarrow \prod\limits_{i=1}^{n^c}\{0,1\}^{n^d}$ defined by $F(s)=\left(f_1(s),f_2(s),...,f_{n^c}(s)\right)$.

The domain of $F$ is of cardinality $2^{2^n}$, while its range is of cardinality $\left(2^{n^d}\right)^{n^c}=2^{n^{c+d}}$. Since for large enough $n$ it holds that $2^{2^n}>2^{n^{c+d}}$, $F$ is not one to one, and thus the condition is not satisfied.