6
$\begingroup$

Let $\mathbb{F}^n_2$ denote the set of $n$-bit 0-1 strings. How to construct an efficiently computable function $f:\mathbb{F}^n_2\to \mathbb{F}^m_2 (m>n)$ satisfying that $\forall u\neq v$,$f(u)\neq f(v)$ and $f(u)$ is not a circular rotation of $f(v)$?

$m$ is expected to be as small as possible.

Thank you very much for your kindness.

$\endgroup$
  • $\begingroup$ I design a mapping where $m=3n$. Using Polya's theorem, the optimal case is that $m$ is about $n+\ln n$, but the mapping seems to be of extreme low efficiency. $\endgroup$ – Cech Cohomology May 24 '13 at 3:21
6
$\begingroup$

Here's a more efficient way of doing it. Let's map all the strings of length $n$ into strings of length $n+O(\sqrt{n} \log n)$ with no consecutive string of $0$'s of length more than $\sqrt{n}$. We then add a string $1 0^{a}1$ at the end, where $a \geq \sqrt{n} + 1$. Our mapping isn't always going to give us the same length string, so $a$ can vary.

How do we do this encoding? We need a way of encoding long string of 0's. Let's do that by taking a string of $0$'s of length at least $t$ and mapping it to a string of zeros of length $t$ followed by a number telling us how many zeros were in it.

$$ \begin{array}{lcl} 0^{\sqrt{n}} & \rightarrow & 0^{\sqrt{n}}10\ldots000 \\ 0^{\sqrt{n}+1} & \rightarrow & 0^{\sqrt{n}}10\ldots001 \\ 0^{\sqrt{n}+2} & \rightarrow & 0^{\sqrt{n}}10\ldots010 \\ 0^{\sqrt{n} +3} & \rightarrow & 0^{\sqrt{n}}10\ldots011 \\ 0^{\sqrt{n} +4} & \rightarrow & 0^{\sqrt{n}}10\ldots100 \\ \vdots &\rightarrow & \vdots \end{array} $$ Because we will never have a string of more than $n$ 0's, we can use the first $\lceil\log n \rceil$ bits after the string $0^{\sqrt{n}} 1$ to encode the length of the string of 0's. Thus, the most we can increase the length of our code by is a factor of $1 + \frac{\log n+2}{\sqrt{n}}$. After this expansion of the code, we need to add at least $\sqrt{n} + 1$ consecutive 0's. This lets us take $m = n + \sqrt{n}(\log n + 3)$.

I think you can probably get $m \approx n + \log n\,$ by using the ideas behind arithmetic codes, but I don't have time to work the details out right now. If somebody else wants to work them out and post an answer, please feel free to do so.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Here is a trivial solution. Take $m = 2n+3$, and map $u$ to $u10^{n+1}1$. Each $f(u)$ has only one rotation containing the substring $10^{n+1}1$, so $f(u)$ is a rotation of $f(v)$ iff $u=v$. You can probably make do with a much smaller $m$, but I leave that to you.

| cite | improve this answer | |
$\endgroup$

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.