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