<p>This is an old but interesting question.</p>
<p><em>Edit:</em> As suggested by Emil Jerabek, <span class="math-container">$d\geq  6$</span> is also needed.</p>
<p>I will interpret it by assuming <span class="math-container">$n$</span> should be <span class="math-container">$d$</span> 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.</p>
<p>Let <span class="math-container">$(x_0,\ldots,x_{d-1}) \in \mathbb{F}_2^d$</span> but interpret it as being in the set <span class="math-container">$\{0,1\}^d.$</span> Define the function
<span class="math-container">$$
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\}\}.$$</span></p>
<p>If <span class="math-container">$x$</span> is the integer represented by the string, denoted <span class="math-container">$x\leftrightarrow (x_0,\ldots,x_{d-1})$</span> this
function is clearly invariant under cyclic shifts of the string. Note that the maximum can be achieved by more than one <span class="math-container">$\tau$</span> if the sequence is subperiodic but this does not matter.</p>
<p>The question is, will it also yield different values between <span class="math-container">$f(x_0,\ldots,x_{d-1})$</span> and <span class="math-container">$f(y_0,\ldots,y_{d-1})$</span> when <span class="math-container">$y\leftrightarrow (y_0,\ldots,y_{n-1})$</span> is a more general permutation of <span class="math-container">$x.$</span></p>
<p>For this specific case the function <span class="math-container">$f$</span> 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.</p>
<p>This follows from the definition of a cyclotomic coset modulo <span class="math-container">$q$</span> used in coding theory.</p>
<p><strong>Definition:</strong> Consider a binary relation on the integers in <span class="math-container">$\{0,1,\ldots,n-1\}$</span>. Given two integers <span class="math-container">$a,b$</span> in <span class="math-container">$\{0,1,\ldots,n-1\}$</span> we say that
<span class="math-container">$a$</span> is related to <span class="math-container">$b$</span> if <span class="math-container">$b=a q^i \pmod n.$</span> This is a reflexive and transitive relation. When <span class="math-container">$q$</span> and <span class="math-container">$n$</span> are relatively prime, this relation is also symmetric, and hence is an equivalence relation. Given positive integers <span class="math-container">$q$</span> and <span class="math-container">$n$</span> that are relatively prime,  the
<span class="math-container">$q-$</span>ary cyclotomic cosets are the equivalence classes defined by this binary relation and acyclotomic coset in general has the form
<span class="math-container">$$
\{a,aq,aq^2,\ldots\}
$$</span>
for some nonnegative integer <span class="math-container">$a.$</span></p>
<p>Since we have <span class="math-container">$n=2^d-1$</span> for our case <span class="math-container">$n$</span> and we take <span class="math-container">$q=2$</span>, <span class="math-container">$n$</span> and <span class="math-container">$q$</span> are relatively prime and the function works.</p>
<p>In general, given <span class="math-container">$n$</span> one can take the smallest <span class="math-container">$q$</span> which is relatively prime to <span class="math-container">$n$</span> and apply this distinguishing algorithm, but the interpretation of cyclic shifts is lost if <span class="math-container">$n\neq q^d-1,$</span> for some natural number <span class="math-container">$d.$</span></p>

CC BY-SA 4.0
2022-06-11T13:01:32.117Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2022-06-11T13:17:24.280Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-06-10T21:21:36.967Z
2022-06-11T13:11:45.537Z
2022-06-11T13:11:45.537Z
kodlu
<p>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</p>

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

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

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

CC BY-SA 3.0
2017-07-18T04:48:01.073Z
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$.
Radu GRIGore
CC BY-SA 3.0
2017-07-18T16:47:51.120Z
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.
<coding-theory><permutations>
Function which detects rotation of bit string
Max Hopkins
# Function which detects rotation of bit string

(Asked by: username_0 on 2017-07-18)

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.

**Tags:** coding-theory, permutations

> **Comments:**
> **username_1**: 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$.  
> **username_2**: 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$?  

---

## 1 answers

### Answer by username_3 on 2022-06-10. Score: 1 | Accepted answer

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

> **Comments:**
> **username_4**: 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$.  
> **username_4**: 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.  

---

