CS Paper Radar

Twisted Equations and Palindrome Length

Volker Diekert, Anna E. Frid, Silas Natterer, Alexander Thumm

cs.FL math.GR ·submitted 2026-10-10 03:47 UTC · v1

Abstract

Twisted equations in free groups are equations in which a finite group of symmetries acts on the free group by automorphisms and anti-automorphisms, such as inversion and reversal; moreover, the variables may be subject to rational constraints. Algorithms from the theory of equations in virtually free groups solve such equations in PSPACE, but they are intricate. Our main result is an elementary algorithm for quadratic twisted equations, which extends the algorithm of Comerford and Edmunds (1981) for quadratic equations in free groups to the twisted setting and to rational constraints. Besides deciding solvability in PSPACE and yielding EDT0L descriptions of solution sets, our algorithm computes, for every quadratic expression, finitely many parametric forms describing its values as freely reduced words. As an application, we study the palindrome length of elements of free groups, that is, the least number of palindromes whose product they are. Guided by the parametric forms that our algorithm computes for products of palindromes, we found, and then proved directly, a characterization of the freely reduced words of palindrome length at most $n$ in terms of patterns describing how palindromes are nested by twisted conjugations, thereby confirming a Catalan structure conjectured by the second author. Consequently, these words form a context-free language, and palindrome length is computable in cubic time as well as in LOGCFL, answering a question of Bardakov, Shpilrain, and Tolstykh (2005).

Closest papers

Nearest neighbours by meaning across the whole index.

Conjugacy languages in free inverse monoids

cs.FL math.GR ·2026-08-11 ·André Carvalho, Ana-Catarina C. Monteiro
similarity 0.59
Abstract · preliminary version, 24 pages

We initiate the study of conjugacy languages in free inverse monoids. Motivated by the notion of conjugacy languages in groups and the study of conjugacy in semigroups, we introduce the language of shortest representatives of conjugacy classes and study it for free inverse monoids of rank at least $2$ under the natural notion of conjugacy. We show that, contrary to the free group case, where this language is regular, in a free inverse monoid it is neither context-free nor co-context-free. In the monogenic case, this language is context-free. We show that this non-context-freeness comes from elements with nontrivial conjugacy classes. We define an equivalence relation as follows: all elements with a nontrivial conjugacy class are related and elements with trivial conjugacy class are only related to themselves. We call this relation $\mathrm{UConj}$. We show that the language consisting of geodesics representing elements whose conjugacy class is trivial is context-free by providing an explicit context-free grammar generating it. For groups, we show that the language of minimal representatives of $\mathrm{UConj}$ classes is regular if the group is hyperbolic and for right-angled Artin groups with the standard generating set, it is piecewise testable. For virtually abelian groups, we show that there is a generating set for which this language is piecewise excluding and exhibit an example of a virtually abelian group admitting a generating set for which this language is not regular.

0.10

Code Equivalence and Automorphism Problems for Codes

cs.CC ·2026-09-21 ·Jean-Francois Biasse, Alexandra V. Hostetler, Anuvrat Jaindungarwal
similarity 0.57
Abstract

We study the complexity of the Code Equivalence problem and show that it is polynomially equivalent to several computational automorphism problems for codes. These problems ask for the cardinality (ACOUNT), an orbit partition (APART), and a generating set (AGEN) for the permutation automorphism group of a code. We present deterministic, polynomial-time reductions between Permutation Code Equivalence (PCE) and each of these problems, including a one-shot reduction from search-PCE to AGEN that makes a single oracle call. We present similar reductions between Linear Code Equivalence (LCE) and analogous problems for the monomial automorphism group of a code. All of our reductions work for any linear codes.

0.38

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.55
Abstract

In the binary diameter problem, the input consists of explicitly given permutations generating a finite group $G$ and a binary-encoded number $k$, and the question is whether every element of $G$ is a product of at most $k$ of the given generators. In the binary length problem, the input additionally contains a permutation $g \in G$, and the question is whether $g$ is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is $Π_2^{\mathrm{P}}$-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where $k$ is encoded in unary, is $Π_2^{\mathrm{P}}$-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.

0.28

Constructive Arithmetic Regularity for Abelian Groups

cs.DS ·2026-10-19 ·Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manmatha Roy
similarity 0.54
Abstract

The arithmetic regularity lemma of Green is a fundamental tool in additive combinatorics, providing a decomposition of arbitrary subsets of finite Abelian groups into pseudorandom pieces with respect to Fourier analysis. Over the years, it has found numerous applications in combinatorics, property testing, and theoretical computer science. However, Green's proof is existential, and many algorithmic applications require an efficient procedure for constructing the underlying regular decomposition. De, Nadimpalli, and Servedio (SODA 2022) developed a query-efficient constructive regularity framework over $\mathbb{F}_2^n$ and explicitly raised the problem of extending their dimension-independent sumset-estimation algorithm to other finite Abelian groups. In this work, we resolve this question for finite Abelian groups of constant torsion. We develop the first constructive version of Green's {\em Arithmetic Regularity Lemma} in this general setting. Given oracle access to a subset of the group, our algorithm computes an implicit description of a regular decomposition together with an oracle representation of a structured subset satisfying the guarantees of Green's lemma. The algorithm runs in time and query complexity polynomial in the regularity parameters and the tower bound, while remaining independent of the size of the ambient group. As applications, we obtain efficient algorithms for removing linear configurations and approximately counting linear images, including weighted sumsets and suitable matrix systems of Cauchy--Schwarz complexity one, over finite Abelian groups of constant torsion. Our results provide a unified algorithmic framework extending dimension-independent constructive arithmetic regularity and its applications beyond $\mathbb{F}_2^n$.

0.27

Algebraic Decomposition Theory for Transformer Length Generalization

cs.FL cs.AI ·2026-08-13 ·Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs +3 more
similarity 0.54
Abstract · 54 pages, 12 figures

Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit length generalization. It is not even known which regular languages transformers length-generalize on -- and this is a foundational class of languages. Our contributions are to establish the first complete characterization of which regular languages transformers length-generalize on and provide a decision algorithm running in polynomial time in the size of the language's syntactic monoid. These results rely on an effective characterization of the regular languages in C-RASP, a recently-established formalism that expresses which languages transformers length-generalize on. This characterization is challenging because classical tools like Krohn-Rhodes decomposition theory for finite semigroups are insufficient for C-RASP. Firstly, the basic building blocks of Krohn-Rhodes theory -- flip-flop and simple groups -- are not expressible in C-RASP. Secondly, the basic building block of C-RASP (unbounded counting) is not expressible by the finite semigroups of Krohn-Rhodes theory. Thus, length generalization on regular languages is controlled by an algebraic property that is invisible to classical finite decomposition theory. We generalize classical decomposition theory from finite semigroups to the infinite additive group on the integers, allowing us to characterize C-RASP in terms of iterated wreath products of the integers and derive a provable polynomial-time decision algorithm for regular language membership. Experiments across a broad test suite of regular languages confirm that our theory captures transformers' length-generalization behavior more accurately than existing classifications.

0.43

Algorithms for Finite Group Epimorphism Testing

cs.DS cs.CCmath.GR ·2026-09-07 ·Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
top venue similarity 0.51
Abstract · 19 pages, A preliminary version of this article appeared in the proceedings of the 53rd EATCS International Colloquium on Automata, Language…

The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.

0.62

Affine Symmetries of Polynomial Roots with Multiplicities and Applications to Constacyclic Codes

cs.IT math.NT ·2026-09-22 ·Li Zhu, Hongfeng Wu
similarity 0.51
Abstract

Let $f(X)$ be a polynomial over a finite field, and let its defining function record the multiplicities of its roots. In this paper, we introduce the affine stabilizer group and the affine stabilizer group scheme of the defining function of $f(X)$. These objects characterize the affine symmetries of the roots of $f(X)$ together with their multiplicities. We establish structural descriptions of these affine stabilizers and relate them to the coefficient structure of $f(X)$. In particular, the affine stabilizer group determines quotient structures of the defining function, which yield canonical descriptions of the corresponding semi-invariant polynomial spaces. The resulting coefficient constraints provide explicit restrictions on the possible supports of polynomials with prescribed affine symmetries. The affine stabilizer group scheme further captures infinitesimal symmetries arising from multiple roots and gives refined coefficient constraints beyond those obtained from ordinary affine transformations. We apply this framework to generator polynomials of constacyclic codes over finite fields. The affine stabilizer structure of a generator polynomial induces subcodes defined by semi-invariant conditions and provides constraints on their dimensions and Hamming distances. In the special case of multiplicative symmetries, the construction specializes to the support-primitive decomposition of constacyclic codes.

0.33

Further Remarks on Separating Words

cs.FL ·2026-08-31 ·John Nicol
theory similarity 0.51
Abstract · 7 pages, 2 figures

We revisit questions on separating words raised by Demaine, Eisenstat, Shallit, and Wilson, together with Ebrahimnejad's follow-up to their reversal problem. For length-$n$ pairs whose difference word has $d$ runs, we prove an $O(d\log n)$ bound, extending the Hamming-distance theorem of Demaine et al. For conjugate words, we give bounds controlled by the arithmetic of the shift. We resolve Demaine et al.'s Open Problem 2 by showing that the order of two words can change nondeterministic separation by an unbounded factor. Our reversal construction addresses Ebrahimnejad's follow-up to Open Problem 1: forward and reversed deterministic separation can differ by an unbounded factor. Since nondeterministic separation is invariant under reversal, the same construction also improves the lower bound in Open Problem 3.

0.18