Efficient Algorithms for Finite $\mathbb{Z}$-Algebras
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910556468805632 |
|---|---|
| author | Kreuzer, Martin Walsh, Florian |
| author_facet | Kreuzer, Martin Walsh, Florian |
| contents | For a finite $\mathbb{Z}$-algebra $R$, i.e., for a $\mathbb{Z}$-algebra which is a finitely generated $\mathbb{Z}$-module, we assume that $R$ is explicitly given by a system of $\mathbb{Z}$-module generators $G$, its relation module ${\rm Syz}(G)$, and the structure constants of the multiplication in $R$. In this setting we develop and analyze efficient algorithms for computing essential information about $R$. First we provide polynomial time algorithms for solving linear systems of equations over $R$ and for basic ideal-theoretic operations in $R$. Then we develop ZPP (zero-error probabilitic polynomial time) algorithms to compute the nilradical and the maximal ideals of 0-dimensional affine algebras $K[x_1,\dots,x_n]/I$ with $K=\mathbb{Q}$ or $K=\mathbb{F}_p$. The task of finding the associated primes of a finite $\mathbb{Z}$-algebra $R$ is reduced to these cases and solved in ZPPIF (ZPP plus one integer factorization). With the same complexity, we calculate the connected components of the set of minimal associated primes ${\rm minPrimes}(R)$ and then the primitive idempotents of $R$. Finally, we prove that knowing an explicit representation of $R$ is polynomial time equivalent to knowing a strong Gröbner basis of an ideal $I$ such that $R = \mathbb{Z}[x_1,\dots,x_n]/I$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_02610 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient Algorithms for Finite $\mathbb{Z}$-Algebras Kreuzer, Martin Walsh, Florian Commutative Algebra Rings and Algebras 13P99 (Primary) 68W39, 13P10, 68Q15 (Secondary) For a finite $\mathbb{Z}$-algebra $R$, i.e., for a $\mathbb{Z}$-algebra which is a finitely generated $\mathbb{Z}$-module, we assume that $R$ is explicitly given by a system of $\mathbb{Z}$-module generators $G$, its relation module ${\rm Syz}(G)$, and the structure constants of the multiplication in $R$. In this setting we develop and analyze efficient algorithms for computing essential information about $R$. First we provide polynomial time algorithms for solving linear systems of equations over $R$ and for basic ideal-theoretic operations in $R$. Then we develop ZPP (zero-error probabilitic polynomial time) algorithms to compute the nilradical and the maximal ideals of 0-dimensional affine algebras $K[x_1,\dots,x_n]/I$ with $K=\mathbb{Q}$ or $K=\mathbb{F}_p$. The task of finding the associated primes of a finite $\mathbb{Z}$-algebra $R$ is reduced to these cases and solved in ZPPIF (ZPP plus one integer factorization). With the same complexity, we calculate the connected components of the set of minimal associated primes ${\rm minPrimes}(R)$ and then the primitive idempotents of $R$. Finally, we prove that knowing an explicit representation of $R$ is polynomial time equivalent to knowing a strong Gröbner basis of an ideal $I$ such that $R = \mathbb{Z}[x_1,\dots,x_n]/I$. |
| title | Efficient Algorithms for Finite $\mathbb{Z}$-Algebras |
| topic | Commutative Algebra Rings and Algebras 13P99 (Primary) 68W39, 13P10, 68Q15 (Secondary) |
| url | https://arxiv.org/abs/2308.02610 |