Computational algebra is an area of algebra that seeks efficient algorithms to answer fundamental problems concerning basic algebraic objects (groups, rings, fields, etc.). For questions about generic computer algebra systems, use [tag:computer-algebra-systems].

learn more… | top users | synonyms

2
votes
1answer
77 views

A field of Radical Sums

I am dealing with a computation that yields numbers that are sums of radicals of the following form: $N=\sum_{i=0}^{m}{a_i\sqrt{b_i}}$ Where $a_i,b_i \in \mathbb{Q}$ (rationals). The context is ...
0
votes
1answer
12 views

Gauss-Seidel Convergence Criterion

The convergence criterion is $\| y^{k+1} - y^{k} \| < \varepsilon$ where $k$ is iteration number. Question 1. Is it possible to use simpler criterion $$ \max_j \left(\left | y_j^{k+1} - y_j^k \...
0
votes
1answer
30 views

Groebner basis over rings

Let $I$ be an ideal in $A[x_1, \ldots, x_n]$, where $A$ is a Noetherian commutative ring, such that w.r.t some monomial order it has a Groebner basis $G = \{g_1, \ldots, g_t\}$ with all the leading ...
0
votes
1answer
43 views

Efficient way to compute the symmetric reduction of special polynomials (specially for resolvents)

By the Fundamental Theory of Symmetric Polynomials every symmetric polynomial in $K[x_1, \dots, x_n]$ can be written uniquely in the elementary symmetric functions $s_1, \dots, s_n$. I know there are ...
6
votes
0answers
142 views

Is the group $G_{n,\phi} = \langle x_1 , \dots, x_n \mid x_i^2, (x_i x_j)^4, x_i x_{\phi(i)} x_{i+1} x_{\phi(i)} \rangle$ abelian?

I am working on a family of finitely presented groups and I asking me the following question. Let $\phi$ be an application from $\left\{1,\dots,n\right\}$ to $\left\{1,\dots,n\right\}$ (not necessary ...
3
votes
0answers
49 views

How to find the smallest set of generating elements in a group?

Is there a systematic procedure for finding the smallest set of generating elements of a finite group?
3
votes
0answers
52 views

Software for computing generators of the invariant rings of the symmetric groups

(Please skip to the last paragraph if you are interested in just the question) I wish to compute the generators of the ring of invariants for a symmetric group acting on a polynomial ring using a ...
3
votes
0answers
32 views

Algorithmic computing kernel of a graded homomorpism

For computing kernel of a module homomorphism we can use module-Grobner basis such as described in notes talking about computing SyZyGies. How can we compute kernel of a homomorphism between a graded ...
3
votes
0answers
90 views

Software for Braid Groups

I am looking for software/online tool that works on Braid Groups. I am aware that there are resources that allows you to draw braids by imputing generators or detect whether two braids are equivalent ...
3
votes
0answers
26 views

Has there been work on computational group theory applications to computing colimits of crosses n-cubes of groups?

I'm trying to compute homotopy groups of a few spaces using crossed n-cubes of groups. I'm able to describe a few colimits in terms of quotients of induced crossed modules and nonabelian tensor ...
3
votes
0answers
158 views

Simplifying Relations in a Group

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that any simple commutator with repeated generator is trivial; for example, $[[x_2,[x_1,x_3]],x_3]=1$. As I have asked ...
2
votes
0answers
35 views

Write an element of a group as product of generators

Say we have a finite group $G$ generated by $g_1,\cdots,g_n$. Are there any algorithms or techniques to write any element $g$ as a product of these generators? Ofcourse we could just try all ...
2
votes
0answers
61 views

Order of a group given its generating set

Let $n,k \in \mathbb{N}$ and $x_1, \dots, x_k \in S_n$, symmetric group. Is there an efficient algorithm to determine the $$ \text{order of }\langle x_1, \dots, x_k\rangle\text{?} $$ If necessary, ...
2
votes
0answers
49 views

How to find a base of a permutation group?

How to find a base of the permutation group G=⟨x,y⟩≤S4 x=(1,2,3), y=(1,2,4)? I hear that base for G is a sequence B = [$b_1, ..., b_m$] ⊂ Ω such that the only element of G which stabilizes each $b_i$ ...
2
votes
0answers
50 views

A recursive problem with GAP concerning lists and an iterator loop

I have the following question concerning a list algorithm in GAP: Let $L_1$ be a non-empty list with certain objects as entries. I wrote a program and called it helping_program_1. The Input for ...
2
votes
0answers
34 views

What is Relator Matrix

At the third section of a paper "Computing second cohomology of finite groups with trivial coefficients" by G. Ellis et al., the authors write Suppose that $<\underline{x}\mid \underline{r}>=&...
2
votes
0answers
108 views

How to compute/ find cancellation for the second group cohomology $H^2(G,A)$?

My problem is the following, suppose you have a discrete group $G$ (finite type) and a $G$-module $M$, $M$ is a $\mathbb{Q}$-vectorial space. I would like to know if there are "ways" to compute $H^2(...
2
votes
0answers
70 views

An algorithm for generating a finite group with a finite set of generators

Let $A$ be a finite set of permutations on $\Bbb N$ with finite support. Is there a good efficient algorithm to obtain the subgroup $\left<A\right>$ of the symmetric group $\operatorname{Sym}(\...
2
votes
0answers
108 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
2
votes
0answers
213 views

Using GAP to compute the abelianization of a subgroup

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that each generator commutes with all its conjugates. (An equivalent relation is, any simple commutator with repeated ...
2
votes
0answers
83 views

First order logic in polynomial equations

Have you ever wondered which points on a conic are the intersections of tangent lines of another surface through the origin? More generally, which points on a shape hold some specified relation to all ...
2
votes
0answers
98 views

How to tell if an ideal is absolutely prime

Consider the ideal $I=(ag-ec-1,ah+bg-cf-de)$ of $R=K[a,b,c,d,e,f,g,h]$. Is $I$ prime when $K=\overline{\mathbb{F}}_2$ is the algebraic closure of a field of 2 elements? Can computers answer this ...
1
vote
0answers
17 views

Relative error in perturbed linear system

The linear system $A\vec{x}=\vec{b}$, where $$A_{(n\times n)}=\begin{bmatrix} 1 &-1 &\dots &\dots &-1 \\ 0& 1 &-1 &... &-1 \\ \vdots & \ddots &\ddots &...
1
vote
0answers
25 views

Different Representation Matrices from same Generating Set

Motivation: This post. $K \subset S_n, \langle K \rangle =G \leq S_n$. We can create a Representation Matrix $M$ from $K$ that represnts $G$ (Furst. Hopcroft, Luks). Question: Is $M$ unique for a ...
1
vote
0answers
25 views

Ordering of elements in the base of a group

In section 4.6.7 of HANDBOOK OF COMPUTATIONAL GROUP THEORY, the authors use an ordering $\prec$ for the elements in a coset. That ordering, $\prec$, was defined in section 4.6 as follows. Throughout ...
1
vote
0answers
19 views

Minimize the rank of a matrix with some entries known

Let $m,n$ be two positive integers, with $m\geq n$. Suppose we have $m$ sets $A_1,\ldots, A_m\subseteq [n]$, with $|A_i|=d_i$. Let $\mathbb F$ be a finite field of size $q$. Let $D$ be the set ...
1
vote
0answers
57 views

A rather special monoid

While implementing an embryo of computational algebra on my blog I ran into a rather special monoid and I wonder if it's studied before. After implementing a very simple concept of dynamic sets I ...
1
vote
0answers
71 views

A GAP code for maximum and minimum cardinals of some classes of subsets of a finite group

Let $G$ be a finite group with a fixed subset $A$. Put $$ S_r(A)=\{B\subseteq G : |AB|=|A||B|\; \& \; B \; \mbox{is inclusion-maximal with respect to this property}\} $$ $$ M_r(A)=\max\{|B| : B\...
1
vote
0answers
45 views

Proposition 4.7 of Handbook of Computational Group Theory

I have been studying Derek Holt's Handbook of Computational Group Theory. I am looking at Proposition 4.7, and I can't figure out what I'm doing wrong. Proposition 4.7(i) states that, given $K$, a ...
1
vote
0answers
98 views

Does this proof that the resultant provides an upper bound for intersection multiplicity look correct?

Let $f,g \in \mathbb{C}[x,y]$ such that $f(0,0)=g(0,0)=0$ and the varieties $V(f)$ and $V(g)$ are both smooth at $(0,0)$ such that the tangent line of $V(f)$ and $V(g)$ is not the $y$ axis. Let Res$(f,...
1
vote
0answers
159 views

Necessary and sufficient conditions for Hensel lifting in the multidimensional case

in Multidimensional Hensel lifting, @Hurkyl gave a neat sufficient condition for the existence of $p$-adic liftings in the multidimensional case. I have finally gotten around (but please also see p-...
1
vote
0answers
355 views

An Algorithm to Find the Generators of the Radical of a Monomial Ideal

Working over $R=\mathbb{C}[x_1,...,x_n]$, I'm given a ring homomorphism with $i\in{1,...,n}$ and $t\in \mathbb{C}$. $\phi_{i,t}(x_j)=x_j$ for $j\neq i$ to themselves. From this I've proven that an ...
0
votes
0answers
14 views

Is calculating the order ideal easier than calculating a Groebner basis?

Given an ideal $I = \langle f_1,\cdots,f_k \rangle \subset K[x_1,\cdots,x_n]$ and a monomial order I am interested in calculating the order ideal of $I$ with respect to that monomial order. This is ...
0
votes
0answers
10 views

How to find the schreier transversal by Todd-Coxeter algorithm?

I was reading the book "Presentation of groups by johnson" and I could not understand the first three lines of page 103. Here they are finding the schreier transversal from the definition column of ...
0
votes
0answers
50 views

“Out of memory” in MAGMA

I'm trying to find some information about Sporadic simple groups of the large order using MMAGM and ATLAS of Brauer. While I am sure that the memory of the cpu is enough, after while, MAGMA says that ...
0
votes
0answers
12 views

Indirect Left recursion.

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
0
votes
0answers
52 views

Computational cost of solving $Ax_i = b_i$ for $i=1,…,m$

$A$ is an invertible matrix square $n$ matrix. The exercise is about 3 different ways you can solve this and I have to determine its efficiency. It's always the same matrix $A$ but a different right ...
0
votes
0answers
77 views

number of symmetries of an arbitrary graph

Given an (undirected) graph G, is there way to (approximately) estimate the order of Aut(G)-- i.e., the number of permutations ...
0
votes
0answers
93 views

Boosting of Coset diagrams

If we have the diagram that represents a transitive permutation representation of $(p,q,r_o)$ for some $p, q$ and $r_o$, we often use this diagram to get diagrams for any $r>r_o$. We can do this ...
0
votes
0answers
65 views

minmax of hamming weight in a basis for a vector space

Consider the vector space $V=\mathbb{Z}_2^n$ and take some linear subspace $U\subseteq V$ (we can assume we are given some basis for $U$). Now, for every basis $B$ of U, define $f(B)=\max_{b\in B}\{w(...