Function which detects rotation of bit string

Question

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.

Answer 1

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