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
7 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
-2 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 518
1 vote
0 answers
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....
user avatar
  • 2,392
1 vote
0 answers
37 views

Efficient way of simplify sum of product of multiple polynomials

Let $A \in \mathbb{R}^{n\times m}, B \in \mathbb{R}^m$. I'm trying to compute the coefficients of $n$ polynomials $C_i = (c_0^i, c_1^i, \cdots, c_{n-1}^i)$. where $\displaystyle \sum_{j=0}^{n-1} c_j^i ...
user avatar
  • 1,111
0 votes
0 answers
16 views

Any exemple of a semi-regular sequence to compute a Gröbner basis?

According to the definition of a semi-regular sequence in this paper Hybrid approach for solving multivariate systems over finite fields page 5: Let {$p_{1},...,p_{m}$} $\subset \mathbb{K}[x_{1},...,...
user avatar
  • 13
3 votes
0 answers
165 views

Do the invariants & covariants completely characterize a projective variety up to projective equivalence?

Let $V \subseteq \mathbb{CP}^n$ be a projective variety embedded in complex projective n-space. By the nullstellensatz it is the zero-set of a finite number of homogeneous polynomials, $p_1(x_1,...x_{...
user avatar
  • 354
0 votes
0 answers
49 views

Equivalence of multivariate polynomial matrices

Let $R = k[x_1,\dots,x_n]$ and $k$ be a field. $F,G$ are $l \times m$ matrices with elements from $R$. $Columnspace(F)$ denotes the submodule of $R^l$ generated by the columns of $F$. If $R^l / ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 3,826
0 votes
0 answers
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 ...
user avatar
0 votes
2 answers
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?
user avatar
1 vote
1 answer
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$-...
user avatar
0 votes
1 answer
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$...
user avatar
  • 51
0 votes
1 answer
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 ...
user avatar
  • 715
2 votes
2 answers
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 ...
user avatar
  • 3,691
1 vote
0 answers
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$ ...
user avatar
  • 89
1 vote
0 answers
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)$. ...
user avatar
  • 23.6k
7 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 312
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 57
0 votes
1 answer
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 ...
user avatar
  • 113
4 votes
2 answers
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 ...
user avatar
  • 103
2 votes
0 answers
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 ...
user avatar
-1 votes
1 answer
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 "...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 121
1 vote
1 answer
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$?...
user avatar
  • 14.2k
0 votes
1 answer
31 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 $...
user avatar
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$...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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)=...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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], ...
user avatar
  • 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?
user avatar
  • 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&...
user avatar
  • 21
0 votes
0 answers
67 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 ...
user avatar
  • 433

1
2 3 4 5 6