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

Filter by
Sorted by
Tagged with
4
votes
0answers
58 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 ...
1
vote
1answer
74 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
0answers
41 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 ...
0
votes
0answers
2 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 ...
1
vote
1answer
61 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 ...
1
vote
1answer
51 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 ...
0
votes
1answer
69 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 ...
2
votes
1answer
59 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 ...
0
votes
0answers
21 views

Relations between Pseudoprimes

good to everyone. I need your help. Does anyone know the relationships between the pseudoprimes ​​of Catalan, Euler-Jacobi, Frobenius, Lucas, Somer-Lucas and Perrin? and with other pseudoprimes? A ...
4
votes
2answers
171 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 ...
2
votes
0answers
63 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 ...
-1
votes
1answer
96 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 "...
2
votes
1answer
62 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 ...
1
vote
1answer
91 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$?...
0
votes
1answer
30 views

Example $A$ algebra finitely generated but the initial algebra not.

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
1answer
55 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$...
1
vote
1answer
90 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 ...
2
votes
2answers
107 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 ...
0
votes
0answers
21 views

Converting Macaulay2 syntax to Bertini syntax

I am running Bertini 1.6 using the interface provided by Macaulay2. Macaulay2 has a nice indexing syntax where you can input an expression CC[x_(1,1)..x_(2,3)] and ...
-2
votes
2answers
78 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.
0
votes
1answer
66 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 ...
1
vote
0answers
34 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 ...
0
votes
1answer
39 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 ...
1
vote
1answer
35 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
vote
1answer
19 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)=...
0
votes
1answer
62 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 ...
1
vote
1answer
94 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 ...
3
votes
1answer
48 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], ...
1
vote
1answer
69 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?
2
votes
0answers
72 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&...
0
votes
0answers
57 views

Computing whether a set of polynomials cuts out a homogeneous variety

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 ...
3
votes
0answers
54 views

Why is it so computationally hard to determine group isomorphism?

Finding an isomorphism requires to show that for 2 groups $G$ and $H$, there exists a bijective map $\phi : G\to H$ such that $$\phi(ab)=\phi(a)\phi(b)$$ For all $a,b \in G$. This is (probably naively)...
2
votes
0answers
25 views

How can I easily find character table of Sergeev group (finite)?

I am looking for the character table of the Sergeev group S_d for small d (say, 'd' up to 10 or up to whatever is possible). The Sergeev group $S_d$ is defined as follows: Let $\mathfrak{S}_d$ be ...
1
vote
2answers
23 views

Help with recursive function

I need some help understanting how the following conclusion was made: We have the recursive function: $ε_n=-n \cdot ε_{n-1}$ How do we come to the conclusion that $ε_n=(-1)^{n-1}\cdot n!\cdot ε_1$
5
votes
1answer
183 views

Is all group theory permutation group theory?

By Cayley's theorem every abstract group is isomorphic to some permutation group. Since the permutation group viewpoint has the advantage of considering the actions of the group on different sets, and ...
0
votes
1answer
31 views

Extending a map to a homomorphism — can this algorithm produce a false positive?

Consider the following computational problem: Let $G,G'$ be groups so that $G$ is finite and generated by $X=\left\{g_1,\ldots,g_n\right\}$. Let $f:X \to G'$ be a map. Decide whether $f$ extends to a ...
0
votes
1answer
41 views

Solving a linear system of equations with constraints

Q) I have a finite state space $S$ of size $n$ and $f:S\to \mathbb{R}$. $A,B\subset S$. $L$ is a $n\times n$ matrix such that all row sums = $0$. Also $f(A)=0$ and $f(B)=1$. I am trying to find a $...
2
votes
0answers
214 views

Finding Coefficients efficiently for an Elliptic Curve such that $P=[m]R$

EDITED QUESTION: To avoid X-Y problem I am going to write my problem down in detail, so plz bear with me. The elliptic curve over $Q$ given by a Weierstrass equation is - $E := y^2 +a_1 xy +a_3 y = x^...
0
votes
0answers
42 views

Are there established algorithms for working with towers of low-degree algebraic extensions?

I'm interested in doing 'computational ruler-and-compass' construction simulations along the lines of Euclidea and similar tools. Because the constructions can get rather involved, I'd like to be able ...
1
vote
1answer
118 views

Decide if certain polynomial is in an Ideal

Let $I$ be the ideal $ I = (x^3y-x^2y^2,x^3z+z^2yx,x^2-xz) \subset \mathbb{Q}[x,y,z]$. I have to decide if $x$ is part of $I$ or $\sqrt I$. My first take was computing the Groebnerbasis $G$ of $I$ by ...
3
votes
2answers
130 views

Q: how to describe these results by a descendants tree in gap

I wrote an implement to find the "fullyInvariantGroups" in GAP and the results appeared as below: ...
0
votes
0answers
38 views

Factoring matrices over $\mathbb{Z}_k$ for $k$ composite?

Say you have some matrix $C\in\mathbb{Z}_k^{n\times m}$, where $k$ is composite, and say the rank of $C$ is $r$. Moreover, say that you have some prior knowledge that $C$ can be written as $C = AB$, ...
1
vote
1answer
51 views

How does GAP calculate 2-closure?

GAP software has a method for calculating the two closure of a (permutation) group? how does it do that calculation?
0
votes
1answer
63 views

How generate a algebraicaly independent set over rational number field?

Algebraic independence. In abstract algebra, a subset ${\displaystyle S}$ of a field ${\displaystyle }$L is algebraically independent over a subfield ${\displaystyle }$K if the elements of ${\...
1
vote
1answer
52 views

normal form property of grobner basis

I am not clear on how why this proof works. I understand that for any $p$ this algorithm gives us back a $\overline{p}$ such that: $p$ and $\overline{p}$ are congruent mod $I$, and only standard ...
1
vote
1answer
37 views

Is there any software that I can use to determine whether matrix group cosets are equal?

Is there any software that I can use to determine whether matrix group cosets are equal? For instance, if I'm working with the group $SL_{2}( \mathbb{F}_{p} [[t]])$ and I want to know if $a SL_{2}( \...
11
votes
1answer
388 views

Sum of determinants of block submatrices

I have a $2n \times 2n$ matrix, $M$. I view it a block matrix, of $n^2$ blocks, each of shape $2\times 2$. Computing the determinant of $M$ is easy by conventional methods. I could also look at ...
2
votes
2answers
533 views

Macaulay2: How to compute the remainder when dividing a polynomial by a set of polynomials (in some order)?

I'm writing Buchberger's Criterion in a program in Macaulay2 to check whether or not the set of polynomials I have form a Grobner basis for the ideal it generates. However, I have not been able to ...
7
votes
2answers
203 views

Program to find intersection of subgroups of free groups

As the title says, I am working on examples for a research project I'm doing, and I need a way to efficiently calculate the intersection of subgroups of a free group (say, of rank 2). Are there any ...
6
votes
1answer
351 views

Discriminant of homogeneous polynomials

Let $f$ be a homogeneous polynomial in variables $x,y,z$. Suppose that the sum of coefficients of $\frac{\partial^i f}{\partial x^i}$ is $0$ for each $0 \leq i \leq r$. I believe that, in this ...

1
2 3 4 5