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
21 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
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 &...
2
votes
1answer
75 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 ...
6
votes
0answers
140 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 ...
0
votes
0answers
13 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 ...
2
votes
3answers
89 views

Subgroup of Order $n^2-1$ in Symmetric Group $S_n$ when $n=5, 11, 71$

$G$ is a symmetric subgroup of symmetric group $S_n$ acting on $n$ objects where $n=5, 11, 71$ and order of $G$ is $n^2-1$. Question: Does $G$ (as defined above for $n=5, 11, 71$) exist? How can I ...
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?
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 ...
18
votes
2answers
482 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
19 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
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 ...
3
votes
1answer
100 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
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 ...
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
97 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
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$ ...
6
votes
1answer
123 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
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
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 ...
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
206 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
77 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
31 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
26 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
157 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
308 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
48 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
72 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
707 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
63 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
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 ...
0
votes
0answers
49 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
71 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
143 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
73 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
300 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 ...