On the Subgroup Distance Problem in Cyclic Permutation Groups

2025/04/09 by Andreas Rosowski, Rosowski, Andreas
Biochemistry, Genetics and Molecular Biology · Engineering · Mathematics · #FOS: Mathematics #Genome Rearrangement Algorithms #Group Theory (math.GR) #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2504.06844

openalex publication_date 2025/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the Subgroup distance problem regarding the Hamming distance, the Cayley distance and the l_∞ distance is NP-complete when the input group is cyclic. When we restrict the l_∞ distance to fixed values we show that it is NP-complete to decide whether there are numbers z₁,z₂ ∈ ℕ such that l_∞(β, α₁^z₁α₂^z₂) ≤ 1 for permutation α₁,α₂,β∈ S_n where α₁ and α₂ commute. However on the positive side we can show that it can be decided in NL whether there is a number z ∈ ℕ such that l_∞(β, α^z) ≤ 1 for permutations α,β∈ S_n. For the former we provide a tool, namely for all numbers t₁,t₂,t ∈ ℕ where t is required to be odd, 0 ≤ t₁ < t₂ < t and t₁ \not≡ t₂ \bmod q for all primes q | t we give a constructive proof for the existence of permutations α,β∈ S_t with l_∞(β, α^t₁) ≤ 1 and l_∞(β, α^t₂) ≤ 1.

Related

• The distance of a permutation from a subgroup of S_n
• Permutation-Based Distances for Groups and Group-Valued Time Series
• Explicit Good Codes Approaching Distance 1 in Ulam Metric
• On the minimum weight problem of permutation codes under Chebyshev\n distance
• Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall τ-Metric