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.

  • 6
    $\begingroup$ 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$. $\endgroup$ – Radu GRIGore Jul 18 '17 at 4:48
  • $\begingroup$ 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$? $\endgroup$ – D.W. Jul 18 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.