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

0
votes
0answers
9 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 ...
6
votes
0answers
121 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 ...
18
votes
2answers
453 views

Most wanted reproducible results in computational algebra

I am interested in suggestions for major computational results obtained with the help of mathematical software but not easily verifiable using computers. "Most wanted" could refer, for example, to ...
0
votes
1answer
17 views

what is inductive class of algebras?

When I was studying the following lemma from an article , I faced to some notations I was not familiar with them, I would appreciate your help to find out them: Lemma:Let $X$ be an inductive ...
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
26 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 ...
3
votes
1answer
98 views

Equation over free group

Let us consider free group $F(a,b)$ of rank two. I need to find a solution (or to prove that there is no one) over this group of the following equation: $$x^2[x^{2k},y]=a^2b^2,$$ where $[x,y]=xyx^{-...
1
vote
2answers
35 views

Could we find an element on finite field? [closed]

Let $F$ be a finite field. Given an element $a^x$ in $F\setminus\{0\}$, could we find $a$?? I know that finding an integer $x$ is very hard problem (Discrete Logarithm Problem). However, I don't know ...
3
votes
0answers
51 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 ...
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
1answer
96 views

About subsets of finite groups with $A^{-1}A=G$ or $AA^{-1}=G$?

Regarding to the problems Does $A^{-1}A=G$ imply that $AA^{-1}=G$? and Is it true that if $|A|>\frac{|G|}{2}$ then $A^{-1}A=AA^{-1}=G$?, we are looking for some subsets $A$ of $G$ with $\lfloor \...
0
votes
1answer
25 views

An algorithm to find a subgroup generated by a subset of a finite group

I'm currently writing a library on python, and now I'm a little bit stuck on how to find a subgroup generated by a subset $S$ of the group $G$. In the case $S = \{a\}\subseteq G$ the problem's easy: ...
2
votes
1answer
43 views

Algebraic description of $\frac1{x+y}$ in terms of $\frac1x$ and $\frac1y$ over finite field.

Given an $a = \frac1x$ and $b = \frac1y$, is there some algebraic way to get the value $c = \frac1{x+y}$ using $a$ and $b$ without the use of inversions. I can't seem to figure it out and it might be ...
2
votes
0answers
48 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$ ...
5
votes
1answer
112 views

Can someone explain how the Schreier-Sims Algorithms works on a permutation group with a simple example?

Can someone explain how the Schreier-Sims Algorithms works on a permutation group with a simple example? All the books I read have a dense notation that hard to comprehend but a simple and concrete ...
2
votes
0answers
60 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
105 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 ...
1
vote
1answer
30 views

Is there always a non-cyclic abelian subgroup of S2n with order n^2?

Let $ n \in N$. Does there always exist a non-cyclic abelian subgroup of $S_{2n}$, the symmetric group on 2n letters, with $n^2$ elements? How could a computer give an example of such subgroup in? ...
3
votes
1answer
197 views

Permutation calculator

I am studying the Mathieu group $M_{11}$ on the twelve letters $\infty,7,6,8,X,2,0,3,4,1,9,5$ (in this specific order) in the form that it is generated by the permutations $(0123456789X)$, $(13954)(...
3
votes
1answer
75 views

Given the generators, find the entire group

my question is quite simple. If you are given the generators of a group, is there any systematic way to generate all of the elements of the group? For example, suppose that you have the Hadamard ...
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 ...
3
votes
0answers
27 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 ...
1
vote
1answer
25 views

Expected number of rows of the full rank matrix

Let A be a m by n random matrix over finite fields F_q. Suppose the rank of A is n. How much does expected number of m? I think m maybe qlogq by bins and balls property But I do not know exactly why....
7
votes
3answers
151 views

How do Gap generate the elements in permutation groups?

I understand that permutationgroups in Gap are represented by generators, which seems to be far more efficient than groups represented by all it's elements, but how could then for example ...
6
votes
2answers
307 views

Number of Irreducible Factors of $x^{63} - 1$

I have to find the number of irreducible factors of $x^{63}-1$ over $\mathbb F_2$ using the $2$-cyclotomic cosets modulo $63$. Is there a way to see how many the cyclotomic cosets are and what is ...
1
vote
1answer
46 views

Isomorphic subgroups of finite groups

Which is the smallest number $n$ such that $S_n$ has non-isomorphic subgroups of the same order with the same number of cyclic subgroups of the same order? Example: $S_4$ has subgroups of order $...
2
votes
1answer
71 views

Algorithm for isomorphic groups?

As I understand There can't be a general algorithm to decide if two finite groups are isomorphic, Wikipedia. But are there efficient algorithms for all subgroups of $S_n$ for say $n=10$ or so? ...
5
votes
1answer
689 views

Is there any efficient algorithm for finding subgroups of a given finite group?

I am implementing an algorithm which finds every subgroup of given group. Here's my algorithm. Let $G$ be a group of order $n$ with elements $g_1,\cdots,g_n$. Then I consider each $\langle g_i\...
2
votes
2answers
60 views

Janko Group and subgroups.

I want to work with the Janko simple group $J_2$ using the computer, and if it is possible, the Janko simple group $J_4$ too. In specific, I want to take certain subgroups of it and compute their ...
0
votes
1answer
42 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 ...
0
votes
0answers
45 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
1answer
69 views

About Gröbner Bases

Recently I have come across a book of Gröbner Bases written by Adams & Loustaunau. The book is excellent and I have become interested in Gröbner bases after reading the book. I want to read more ...
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 ...
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 ...
4
votes
4answers
141 views

Group conjecture

Conjecture: Given a finite group $G$ and a subset $A\subset G$. Then $\{A,A^2,A^3,\dots\}$ is a group iff $\forall n\in \mathbb N: |A^n|=|A^{n+1}|$. Given that the composition between the ...
2
votes
1answer
38 views

Quasi canonical isomorphisms between finite groups and subgroups of the symmetric group?

I'm implementing finite groups in Forth for my blog and since any group is a subgroup of a permutation group it make sense to let the standard elements be permutation schemas: ...
1
vote
0answers
56 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 ...
4
votes
1answer
71 views

GAP Most efficient way to check multiple properties of a group in the small group library

In GAP I would like to search the small groups library looking for groups with specific properties (I suppose this is the most common usage). If I have a list of properties I want to test, what is ...
1
vote
1answer
78 views

Minimizing computations for evaluating two polynomial simultaneously

I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700. I ...
2
votes
1answer
76 views

The Command “TzGoGo” in GAP

I am learning GAP and would like to ask one question about a command called "TzGoGo": If $P$ is a finite presentation of a group $G$, then will the eventual result of the command "TzGoGo(P)" be ...
8
votes
2answers
299 views

Is it “often known” how to compute a list of groups?

From the introduction of the article Construction of Finite Groups written by Hans Ulrich Besche and Bettina Eick: When attempting to determine up to isomorphism the groups of a given order it is ...
2
votes
1answer
58 views

The equation $|A^{-1}A|=|A|^2-|A|+1$ for finite subsets of a group

Let $A$ be a finite subset of a group $G$. It is clear that $|A^{-1}A|\leq|A|^2-|A|+1$. If $A$ is singleton or $A=\{1,a\}$ with $O(a)\neq 2$ then the equality holds. Now, can somebody characterize all ...
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\...
3
votes
2answers
106 views

Is there an easy way to find the (number of) subgroups of a given group?

Is there an easy way to find all subgroups of a given group? For example, say you had the dihedral group $D_{4}$ - is there a way to work out how many subgroups this has, or what they are, or can it ...
3
votes
1answer
33 views

Algorithmic way to check if a power-conjugate presentation is consistent?

Is there an algorithmic way to check if a power-conjugate presentation (for a finite polycyclic group) is consistent? Background: A finite solvable group $G$ has a subnormal series $$ G=G_0 \...
0
votes
1answer
47 views

Prove that $\mu ((X,Y)^n (X+1, Y+1)^m)=(n+1)(m+1)$

Let $k$ be a field (if it helps, we can think $k$ algebraically closed and/or of characteristic $0$), and consider the polynomial ring $k[X,Y]$. For an ideal $I$ of $k[X,Y]$ I denote by $$\mu(I) = \...
1
vote
1answer
31 views

Computing Extensions of an Ideal in Singular or Macaulay2

Does Macaulay2 or Singular compute extensions of ideals under ring homomorphisms? Specifically, if $\phi:R\rightarrow S$ is a ring homomorphism (say polynomial rings over $\mathbb{Q}$ which can be ...
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 ...
1
vote
2answers
132 views

Compute Automorphism Group using Computer Software

Is there a computer software that can compute Automorphism Groups. For instance $Aut(\mathbb{Z}_4\times\mathbb{Z}_2)$. I tried Sage, but could not get it to work. Output: ...
3
votes
1answer
106 views

Do circular tapes exist in Turing Machines?

I've been looking for information about this topic without success. Have someone described Turing Machines over circular tapes instead lineal and infinite? Like the tape could be described with ...