# Function which detects rotation of bit string

Consider a function $F: \mathbb{F}_2^d \to \mathbb{Z}^n = (f_1,\ldots,f_n)$ with the property that if $y \in \mathbb{F}_2^d$ is a rotation of $x \in \mathbb{F}_2^d$, i.e. $y$ is $x$ permuted by an element of the cyclic group generated by $(1 \ 2 \ldots d)$, then F(x)=F(y), and the additional constraint that $f_i$ is of the form

$f_i(x) = \sum\limits_{j=1}^d \alpha_jx_j$.

There are obvious examples of such functions, for instance $F(x) = \sum\limits_{1}^d x_i$. For any $x \in \mathbb{F}_2^d$ and $\pi \in S_d$, $F(x)=F(\pi x)$. We say that such a function is fixed under $S_d$. However, as you might expect from my initial explanation, I am interested in such a function which is fixed strictly under rotations, that is for any permutation $\pi$ which is not a rotation, then $F(x) \neq F(\pi x)$, or at least fixed under rotations and not fixed under all of $S_d$.

Do such functions exist? I am having difficulty finding any example which is not the one I gave above.

• No, they don't exist. Let $e_i$ be the bitvector with bit $i$ set and others reset. Under your conditions, $F(e_i)=F(e_j)$ implies $\alpha_i=\alpha_j$ for all $i$ and $j$. Jul 18, 2017 at 4:48
• What does it mean to permute an element of $\mathbb{F}_2^d$ by an element of the cyclic group with $n$ elements? Should the $n$ be $d$?
– D.W.
Jul 18, 2017 at 16:47

This is an old but interesting question.

Edit: As suggested by Emil Jerabek, $$d\geq 6$$ is also needed.

I will interpret it by assuming $$n$$ should be $$d$$ and demonstrate that it can be solved by using a function that is slightly more general than what the OP asked for and works in detecting cyclic shifts.

Let $$(x_0,\ldots,x_{d-1}) \in \mathbb{F}_2^d$$ but interpret it as being in the set $$\{0,1\}^d.$$ Define the function $$f(x_0,\ldots,x_{d-1})=\max \{ \sum_{j=0}^{d-1} x_j 2^{(j+\tau)\pmod d} : \tau \in \{0,1,\ldots,d-1\}\}.$$

If $$x$$ is the integer represented by the string, denoted $$x\leftrightarrow (x_0,\ldots,x_{d-1})$$ this function is clearly invariant under cyclic shifts of the string. Note that the maximum can be achieved by more than one $$\tau$$ if the sequence is subperiodic but this does not matter.

The question is, will it also yield different values between $$f(x_0,\ldots,x_{d-1})$$ and $$f(y_0,\ldots,y_{d-1})$$ when $$y\leftrightarrow (y_0,\ldots,y_{n-1})$$ is a more general permutation of $$x.$$

For this specific case the function $$f$$ works and obeys the desired property above. Actually, it also distinguishes between strings with different Hamming weights, but those strings are not permutations of each other.

This follows from the definition of a cyclotomic coset modulo $$q$$ used in coding theory.

Definition: Consider a binary relation on the integers in $$\{0,1,\ldots,n-1\}$$. Given two integers $$a,b$$ in $$\{0,1,\ldots,n-1\}$$ we say that $$a$$ is related to $$b$$ if $$b=a q^i \pmod n.$$ This is a reflexive and transitive relation. When $$q$$ and $$n$$ are relatively prime, this relation is also symmetric, and hence is an equivalence relation. Given positive integers $$q$$ and $$n$$ that are relatively prime, the $$q-$$ary cyclotomic cosets are the equivalence classes defined by this binary relation and acyclotomic coset in general has the form $$\{a,aq,aq^2,\ldots\}$$ for some nonnegative integer $$a.$$

Since we have $$n=2^d-1$$ for our case $$n$$ and we take $$q=2$$, $$n$$ and $$q$$ are relatively prime and the function works.

In general, given $$n$$ one can take the smallest $$q$$ which is relatively prime to $$n$$ and apply this distinguishing algorithm, but the interpretation of cyclic shifts is lost if $$n\neq q^d-1,$$ for some natural number $$d.$$

• I think you mean $2^{(j+\tau)\bmod d}$ rather than $2^{j+\tau}$ in the definition of $f$, otherwise it is not invariant under cyclic shifts (or any nontrivial permutation, for that matter). In other words, $f$ is taking a canonical representative from the orbit of $x$ under the action of the cyclic shift group. But then it actually works only for $d\ge6$: if $d\le5$, then the permutations that map every $x\in\{0,1\}^d$ to a cyclic shift of $x$ are not just the cyclic shifts themselves, but also “reversed” cyclic shifts. To see this, note that you only need to care about $x$ of weight $2$. Jun 11 at 13:01
• That is, if $d=3,4,5$, then no function $F\colon\mathbb F_2^d\to X$ whatsoever is fixed only by cyclic shifts. Jun 11 at 13:17