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
16 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
23 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
42 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 ...
1
vote
1answer
29 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
64 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 ...
3
votes
0answers
22 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
20 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 ...
6
votes
3answers
124 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 ...
2
votes
0answers
33 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
57 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, ...
1
vote
1answer
45 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 ...
2
votes
1answer
67 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? ...
2
votes
2answers
54 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 ...
2
votes
0answers
47 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
100 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 ...
0
votes
1answer
36 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
37 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
65 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
10 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 ...
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 ...
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: ...
14
votes
1answer
370 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 ...
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
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
66 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| : ...
3
votes
2answers
102 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 ...
4
votes
1answer
62 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 ...
3
votes
1answer
32 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
46 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
28 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 ...
2
votes
0answers
47 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
95 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
83 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 ...
2
votes
3answers
133 views

Is there any good software that solves equations of permutation group elements?

I need to solve equations of permutation group elements (elements of $S_n$) that may not may not have solutions. The number of equations generally exceeds the number of variables. Is there any good ...
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 ...
0
votes
1answer
50 views

Ring Structure for Non Commutative Groups: Is there a grander reason for Abelian requirements?

So I was considering the following idea. Let a generalized Ring $gR$ be a set equipped with two operations $$u_1, u_2$$ Such that $gR$ is a with the operation $u_1$ and the operation $u_2$ ...
3
votes
1answer
174 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)$, ...
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 ...
8
votes
1answer
91 views

(Un)distorted subgroups in $\mathbb{F}_2 \times \mathbb{F}_2$

We consider the product of free groups $$\mathbb{F}_2 \times \mathbb{F}_2 = \langle a,b,c,d \mid [a,b]=[b,c]=[c,d]=[d,a]=1 \rangle.$$ Given some elements $g_1,\ldots,g_n \in \mathbb{F}_2 \times ...
17
votes
2answers
283 views

Enumerating Bianchi circles

Background: Katherine Stange describes Schmidt arrangements in "Visualising the arithmetic of imaginary quadratic fields", arXiv:1410.0417. Given an imaginary quadratic field $K$, we study the Bianchi ...
5
votes
2answers
228 views

Algorithm design for enumerating pairs of noncommuting elements up to conjugacy

I am trying to write some Magma code that, given a group $G$, returns a list of pairs $(x,y)$ with $x,y\in G$ such that $[x,y]\neq 1$ and such that every pair $(z,w)$ in the group with $[z,w]\neq 1$ ...
2
votes
0answers
107 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 ...
0
votes
1answer
26 views

Ring module homomorphism properties

$\text{Hom}_{\mathbb Z} (\mathbb Z/3\mathbb Z , \mathbb Z/5\mathbb Z) = ?$ how many homomorphism are there from $\mathbb Z/3\mathbb Z$ to $\mathbb Z/5\mathbb Z = ?$ Where $\mathbb Z$ represents ...
2
votes
1answer
76 views

Algorithms for generating $A_n$ and $S_n$ from specific generators

Is there a simple algorithm to generate the elements of the alternating group $A_n$ in terms of some small set of generators? For example, when $n = 4$, I'm looking for an algorithm whose output is a ...
2
votes
1answer
99 views

do we have any special algorithms or software to find all 2-sylow subgroups of a group?

I am working on a project that involves 2-sylow subgroups of groups,one thing that I need to do is to find all 2-sylow subgroups of a group and check that it is cyclic or not, now my question is that ...
7
votes
6answers
773 views

How to efficiently represent and manipulate polynomials in software?

I've started to work on a package (written in matlab for now) that among other things must be able to represent and manipulate (compare, add, multiply, differentiate, etc) polynomials in several ...
0
votes
1answer
81 views

Fixed Spaces for Group Elements

what is the GAP code for finding the fixed space? A list of row vectors that form a base of the vector space $V$ such that $v M = v$ for all $v$ in $V$ and all matrices $M$ in the list $mats$.
3
votes
0answers
76 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 ...