On the Subgroup Distance Problem in Cyclic Permutation Groups
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910026238525440 |
|---|---|
| author | Rosowski, Andreas |
| author_facet | Rosowski, Andreas |
| contents | We show that the Subgroup distance problem regarding the Hamming distance, the Cayley distance and the $l_\infty$ distance is NP-complete when the input group is cyclic. When we restrict the $l_\infty$ distance to fixed values we show that it is NP-complete to decide whether there are numbers $z_1,z_2 \in \mathbb{N}$ such that $l_\infty(β, α_1^{z_1}α_2^{z_2}) \leq 1$ for permutation $α_1,α_2,β\in S_n$ where $α_1$ and $α_2$ commute. However on the positive side we can show that it can be decided in NL whether there is a number $z \in \mathbb{N}$ such that $l_\infty(β, α^z) \leq 1$ for permutations $α,β\in S_n$. For the former we provide a tool, namely for all numbers $t_1,t_2,t \in \mathbb{N}$ where $t$ is required to be odd, $0 \leq t_1 < t_2 < t$ and $t_1 \not\equiv t_2 \bmod q$ for all primes $q \mid t$ we give a constructive proof for the existence of permutations $α,β\in S_t$ with $l_\infty(β, α^{t_1}) \leq 1$ and $l_\infty(β, α^{t_2}) \leq 1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06844 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Subgroup Distance Problem in Cyclic Permutation Groups Rosowski, Andreas Group Theory We show that the Subgroup distance problem regarding the Hamming distance, the Cayley distance and the $l_\infty$ distance is NP-complete when the input group is cyclic. When we restrict the $l_\infty$ distance to fixed values we show that it is NP-complete to decide whether there are numbers $z_1,z_2 \in \mathbb{N}$ such that $l_\infty(β, α_1^{z_1}α_2^{z_2}) \leq 1$ for permutation $α_1,α_2,β\in S_n$ where $α_1$ and $α_2$ commute. However on the positive side we can show that it can be decided in NL whether there is a number $z \in \mathbb{N}$ such that $l_\infty(β, α^z) \leq 1$ for permutations $α,β\in S_n$. For the former we provide a tool, namely for all numbers $t_1,t_2,t \in \mathbb{N}$ where $t$ is required to be odd, $0 \leq t_1 < t_2 < t$ and $t_1 \not\equiv t_2 \bmod q$ for all primes $q \mid t$ we give a constructive proof for the existence of permutations $α,β\in S_t$ with $l_\infty(β, α^{t_1}) \leq 1$ and $l_\infty(β, α^{t_2}) \leq 1$. |
| title | On the Subgroup Distance Problem in Cyclic Permutation Groups |
| topic | Group Theory |
| url | https://arxiv.org/abs/2504.06844 |