Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908380616982528 |
|---|---|
| author | Anokhin, Mikhail |
| author_facet | Anokhin, Mikhail |
| contents | Let $Ω$ be a finite set of finitary operation symbols. An $Ω$-expanded group is a group (written additively and called the additive group of the $Ω$-expanded group) with an $Ω$-algebra structure. We use the black-box model of computation in $Ω$-expanded groups. In this model, elements of a finite $Ω$-expanded group $H$ are represented (not necessarily uniquely) by bit strings of the same length, say, $n$. Given representations of elements of $H$, equality testing and the fundamental operations of $H$ are performed by an oracle.
Assume that $H$ is distributive, i.e., all its fundamental operations associated with nonnullary operation symbols in $Ω$ are distributive over addition. Suppose $s=(s_1,\dots,s_m)$ is a generating system of $H$. In this paper, we present probabilistic polynomial-time black-box $Ω$-expanded group algorithms for the following problems: (i) given $(1^n,s)$, construct a generating system of the additive group of $H$, (ii) given $(1^n,s,(t_1,\dots,t_k))$ with $t_1,\dots,t_k\in H$, find a generating system of the additive group of the ideal in $H$ generated by $\{t_1,\dots,t_k\}$, and (iii) given $(1^n,s)$, decide whether $H\in\mathfrak V$, where $\mathfrak V$ is an arbitrary finitely based variety of distributive $Ω$-expanded groups with nilpotent additive groups. The error probability of these algorithms is exponentially small in $n$. In particular, this can be applied to groups, rings, $R$-modules, and $R$-algebras, where $R$ is a fixed finitely generated commutative associative ring with $1$. Rings and $R$-algebras may be here with or without $1$, where $1$ is considered as a nullary fundamental operation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_20497 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups Anokhin, Mikhail Rings and Algebras Computational Complexity Symbolic Computation 68W30 (primary), 68Q09, 08A62 (secondary) Let $Ω$ be a finite set of finitary operation symbols. An $Ω$-expanded group is a group (written additively and called the additive group of the $Ω$-expanded group) with an $Ω$-algebra structure. We use the black-box model of computation in $Ω$-expanded groups. In this model, elements of a finite $Ω$-expanded group $H$ are represented (not necessarily uniquely) by bit strings of the same length, say, $n$. Given representations of elements of $H$, equality testing and the fundamental operations of $H$ are performed by an oracle. Assume that $H$ is distributive, i.e., all its fundamental operations associated with nonnullary operation symbols in $Ω$ are distributive over addition. Suppose $s=(s_1,\dots,s_m)$ is a generating system of $H$. In this paper, we present probabilistic polynomial-time black-box $Ω$-expanded group algorithms for the following problems: (i) given $(1^n,s)$, construct a generating system of the additive group of $H$, (ii) given $(1^n,s,(t_1,\dots,t_k))$ with $t_1,\dots,t_k\in H$, find a generating system of the additive group of the ideal in $H$ generated by $\{t_1,\dots,t_k\}$, and (iii) given $(1^n,s)$, decide whether $H\in\mathfrak V$, where $\mathfrak V$ is an arbitrary finitely based variety of distributive $Ω$-expanded groups with nilpotent additive groups. The error probability of these algorithms is exponentially small in $n$. In particular, this can be applied to groups, rings, $R$-modules, and $R$-algebras, where $R$ is a fixed finitely generated commutative associative ring with $1$. Rings and $R$-algebras may be here with or without $1$, where $1$ is considered as a nullary fundamental operation. |
| title | Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups |
| topic | Rings and Algebras Computational Complexity Symbolic Computation 68W30 (primary), 68Q09, 08A62 (secondary) |
| url | https://arxiv.org/abs/2505.20497 |