# Questions tagged [computational-algebra]

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].

267 questions
Filter by
Sorted by
Tagged with
91 views

### Schönert & Seress Algorithm - Computing all block systems - blocks of imprimitivity

Atkinson as well as Schönert and Seress describe methods to compute the minimal block system; in particular in Permutation Group Algorithms by Ákos Seress, we find Theorem 5.5.1 Suppose that a set S ...
• 71
1 vote
105 views

### Find the conjugate/similar transformation matrices connecting two unitary irreducible representations corresponding to the same character.

According to the GAP manual, the following description is given for the command IrreducibleRepresentationsDixon: If the option ...
57 views

### Does a number n raised to itself (n^n) will have digits depending on the original number n? [closed]

Consider, 7^7 = 823543, the digit 3 in 823543 is repeated two times, is it possible that a number raised to itself can have a higher repetitions of any other digit or is it random. Now consider, 93^93 ...
20 views

### Prove asymptotic bound for a conditional function

I am a little bit confused when it comes to finding the asymtotic bound for a conditional function like this My approach is that I consider 2 seperate cases when n is odd and when n is even and treat ...
55 views

### Create a block diagonal matrix with different sizes of blocks in GAP

I don't know if this question has been asked before, or if this is the right site to ask it. If not, let me know about a site where can I ask, please. Problem: I want to create a block diagonal matrix ...
• 1,780
45 views

### How do i show that transitivity is required for a monomial order?

On Eisenbud - Commutative Algebra with a view Toward Algebraic geometry page 324 There is an example given why we must assume transitivity of a monomial order relation. this example, to me, seems ...
82 views

### Termination of Buchberger's algorithm for path algebras

I'm reading the paper Noncommutative Gröbner Bases, and Projective Resolutions by Edward L. Green, which presents a version of Buchberger's algorithm for path algebras. I'm trying to show that the ...
• 518
1 vote
35 views

### Understanding Graver basis, Grobner basis, and Lawrence lifting

I'm trying to understand the relationship between Graver and Grobner basis, in particular how Graver basis can be computed via Grobner basis via Lawrence lifting. The key result appear to be Theorem 7....
• 2,392
1 vote
37 views

• 13
165 views

1 vote
27 views

### Minimal polynomial of powers of primitive element in a finite field.

Let $F=\mathbb{F}_2$ be finite field of order $2$, $f(x)$ be a minimal polynomial of degree $n$ over $F$. Let $K=F(\alpha)$, where $\alpha$ is a root of $f(x)$. My question is how to deduce the ...
• 3,826
35 views

### Reshaping a vector into a matrix - represent this as a linear map

We know that in final dimensional space every linear map can be represented by a matrix. Let $x\in\mathbb{R}^{np \times 1}$ be an $np$-dimensional vector. Then the reshape operation that transforms ...
49 views

### What is the PDA for this language with three 0's per one 1?

I am trying to find a PDA for $L = \{0^{3i} 1^i \mid i \geq 0\}$ but I am struggling. I was trying to find a DFA and then convert it to PDA but now know that DFA's can't keep count. Any ideas?
1 vote
45 views

### More convenient GAP code to verify Additional property of d-maximal groups

Let $G$ be a finite $p$-group and $d(G)$ be its minimal number of generators. We say that $G$ is $d$-maximal if $d(H) < d(G)$ for all $H < G$. The following code determines weather $G$ is $d$-...
• 89
57 views

### Irreducible real representations of $D_{2k}$ and $(C_{i}\times C_{j})\rtimes D_{2k}$

I am considering finite groups of types $D_{2k}$ or $(C_{i}\times C_{j})\rtimes D_{2k}$. I would like to find the irreps of these groups over $\mathbb{R}$ on vector spaces of dimensions $N \lesssim 20$...
• 51
69 views

### Determining the defining polynomial of a parametrized variety

This was a question I came up with when working on twisted cubic curve. The twisted cubic curve in $\mathbb{A}^3$ is given by $Y=\{(t,t^2,t^3)|,t\in k\}$, we can immediately tell the defining ...
• 715
78 views

### What is an algorithm to test whether a number field element has a square root in that number field?

Let $K$ be a number field, such as $\mathbb{Q}(\sqrt{d})$ for $d$ a square-free integer. I am looking for an algorithm that outputs whether some $\alpha \in K$ has a square root in $K$, i.e. when ...
• 3,691
1 vote
30 views

### Computational complexity of the word & conjugacy problems for a (classical) reversible circuit

By word problem I mean the decision problem of whether a given reversible circuit is functionally equivalent to the empty one. It is in co-NP. The broader conjugacy problem asks whether, given $f$ ...
• 89
1 vote
50 views

### How to explain these ideal factorization results from gp?

Here are the two different factorization results of $\mathfrak{p} = 5$ in two different number fields $F = \mathbb{Q}[x]/(x^3 + 10x - 12)$ and $G = \mathbb{Q}[x]/(x^3 - 6x + 41)$. ...
• 23.6k
148 views

### Solving a Solvable Polynomial by Radicals (Effectively)

I'm trying to actually write some code (in sage) to take a polynomial $f$ with solvable galois group and compute its roots as nested radicals. Right now I'm just trying to get cyclic extensions to ...
• 25.7k
1 vote
190 views

### GAP on Jupyter Notebook

I wanted to learn GAP as it is certain that it will be helpful in the future for my research. I wanted to try GAP in Jupyter notebook in GitHub. I have tried following the step i.e. launch binder and ...
1 vote
48 views

### How do I proof Groebner basis existence in $R[x_1, \dots, x_n]$?

In An Introduction To Groebner Bases from Loustaunau, it says that: We further note that the Noetherian property of the ring R, and hence of the ring $R[x_1, \dots, x_n]$, yields to the following ...
• 11
5 views

### Least number of digits of the quotient of a base-B integer division

Let a and b be two integers (b is non-zero) of k and l base B digits, respectively. What is the least number of digits the quotient of the division of a and b can have? I am pretty sure the answer is ...
• 312
1 vote
77 views

### Polynomials which are invariant to the cyclic permutation of variables

I'm trying to solve the following problem from this book. I can find the Gröbner basis of $J$ using Buchberger’s algorithm, and so I don't have any problem with the first part of this problem. But my ...
• 393
1 vote
88 views

### Algorithm for expressing Gröbner basis in terms of ideal generators

Given a polynomial ring and an ideal $$A \supset I = (f_1, ..., f_m)$$ there are plenty of implementations of an algorithm (e.g. Buchberger's) that produces a Gröbner basis $$G = (g_1, ..., g_n)$$ and ...
95 views

### Existence of reduced Groebner basis [closed]

In my class notes there is a Theorem saying: Every non zero ideal of the ring $F[x_1,\dots,x_n]$ has a reduced Groebner Basis. Unfortunately there is no proof. Can someone give the proof or refer to ...
• 57
74 views

### Learn Algebra with computational applications [Book Recommendation] [closed]

I am studying Linear and abstract algebra and find it a bit too, again "abstract", could someone recommend me a good book so I can learn it through computational applications? I think it ...
• 113
266 views

### How to find minimal generating sets efficiently?

Let $G$ be a group. A minimal generating set of $G$ is a subset of $R$ of $G$ that generates $G$ such that no proper subset of $R$ also generates $G$. For arbitrary groups is its not true (unlike ...
• 103
66 views

### What is the minimal set of comparisons that determines a monomial order?

A monomial order in $k[x_1, x_2, \ldots, x_n]$ for a field $k$ is a relation $\prec$ on the monomials such that: $\prec$ is a total order; if $m_1 \prec m_2$ then $m_3m_1 \prec m_3m_2$ for any three ...
• 21
114 views

### Using a lemma to calculate syzygy.

I want to find the syzygies of the following monomial ideal $I = (x_1^4, x_1^3x_2, x_1^2x_2^2, x_1x_2^3, x_2^4)$ in $S = k[x_1, x_2]$. To do this I will use Lemma 15.1 on pg. 322 in Eisenbud "...
159 views

### Normal form and remainder - Groebner Basis

I'm quite confused about the concept of normal form of a polynomial $f$ relative to the ideal $I$. It should be the remainder of the division of $f$ with a Groebner Basis of $I$. But does that mean ...
• 121
1 vote
142 views

### Is there any function in GAP finding all maximal elementary abelian subgroup of a $p$-group $P$?

I know how to obtain all subgroups of a group in GAP. Is there any function in GAP (or algorithm that I could implemnt myself) for obtaining all maximal elementary abelian subgroups of a $p$-group $P$?...
• 14.2k
31 views

Let $K$ a field and $A$ subalgebra of $S=K[x_{1}, \ldots, x_{n}]$. If $<$ is a monomial order in $S$, we say that $in_{<}(A)$ is the $K$-subálgebra of $S$ generated over $K$ by all monomials $... 1 vote 1 answer 67 views ### Permutation acting on subsets of the domain Suppose a group$G \subseteq S_n$, where$S_n$is the permutation group on$X = \{1, ... ,n\}$. Consider two subsets$Y,Z \subseteq X$with$|Y| = |Z| \leq n$. Problem: Is there a permutation$g \in G$... • 13 1 vote 1 answer 98 views ### Finding seven harmonic cubics I am given an exercise of my thesis which is about "Computational Algeberaic Geometry", but I dont have enough knowldege to do it or even think about it. The exercixe is: A ternary cubic ... • 401 2 votes 2 answers 117 views ### Is there any software which does Ring Computations? Are there any software that is able to compute the following problems: Verifying if or not a subset of a ring is an ideal. Generating all ideals of a given finite ring. Finding maximal multiplicative ... • 1,273 -2 votes 2 answers 87 views ### Proof of two ideals are equal How can we prove that the ideals$\,I=(x_1+x_2, x_2^2)\,$and$\,J=(x_1+x_2, x_1^2)$are equal? I was thinking of looking at$ {\rm Mon}(I) = {\rm Mon}(J)\,$. Thank you. • 35 0 votes 1 answer 133 views ### How can I get maximal ideal containing an ideal using Macaulay2? In Macaulay2, I have written the following codes to find the maximal ideal in the ring$Q[x,y,z]$containing the ideal generated by$x^2y+z$and$xz-y$. R=QQ[x,y,z] I=ideal(x^2y+z,xz-y) M=getMaxIdeal ... • 9,587 1 vote 0 answers 46 views ### Let$P$be prime and$Q\subset P$. How feasible is the computation of a Gröbner basis of a min prime over$Q$compared to the computation for$P$? Context: I am computing the reduced Gröbner bases with respect to degRevLex for the following two ideals:$P$is a homogeneous prime ideal with$36$generators$\{g_1,\dots,g_{36}\}$with homogeneous ... • 2,268 0 votes 1 answer 50 views ### Finding smallest integer to make the expression A+Bx divisible by another number K I've come across this problem working on a special coordinate system that uses xy pairs belonging to$x = x_0+Cw$and$y = y_0+Ch$I sometimes perform checks to see if points are colinear and arrive ... • 133 1 vote 1 answer 43 views ### Checking if a matrix algebra is local algorithmically Since this question is strongly connected to the decomposition of modules over algebras, I expect there is some solution. Rather, I am looking for a solution that does not involve all the machinery ... • 1,734 1 vote 1 answer 21 views ### Relation between a particular codeword and primitive roots of the unit in a cyclic code I've got an exercise that asks Is it true that (1,1,1,1,1,1,1) is codeword for any binary cyclic code of length 7? My first answer was No. I can decompose$$c(x)=... • 626 0 votes 1 answer 82 views ### Proof of non-computability of subset of a countably infinite set In my statistical programming work, I have run into a computational problem that I am unfamiliar with. Although my problem is a bit more detailed, it can be boiled down to the following. Suppose we ... • 3,858 1 vote 1 answer 118 views ### GAP routine for computing orbits of cosets. Let$G=N{.}Q$be an extension with N nonabelian. I act$N$on the coset$Ng$, g is a lifting for a class representative$q \in Q$, to get say$l$orbits. Now I act the centralizer$C_Q(q)$on the set ... • 57 3 votes 1 answer 56 views ### Practical algorithm to calculate power subgroup of a polycyclic group I am looking for a practical algorithm to calculate the power subgroup$G^n := \langle g^n \mid g \in G \rangle$of a (possibly infinite) polycyclic group$G$. A theoretical algorithm is given in [1], ... • 6,108 1 vote 1 answer 89 views ### Using GAP to find coset representatives [closed] Given a finitely generated group$G$and a normal subgroup of finite index$K$, how can I use GAP to find a list of coset representatives, and also show that two coset representatives are equal? • 119 2 votes 0 answers 78 views ### Solving a system of polynomial equation - can I trust numerical results? To finish a proof, I need to solve a system of two polynomials with integer coefficients in two variables,$\{F_1(x,y)=0,\,F_2(x,y)=0\}$, and then show that no solutions satisfy$0<x<1$and$y&...
• 21
I have a set of multivariate polynomials over $\mathbb{Q}$, and I want to compute whether they cut out a homogeneous variety. My first idea is to compute the radical of the ideal $I$ that they ...