Questions tagged [computer-algebra]

Using computer-aid approach to solve algebraic problems. Questions with this tag should typically include at least one other tag indicating what sort of algebraic problem is involved, such as ac.commutative-algebra or rt.representation-theory or ag.algebraic-geometry.

113 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
176 views

Enumeration of stable graphs of genus $g$

Let $G=(V,E)$ be a connected undirected finite graph, let us call $G$ stable if each vertex has degree at least $3$. Is there a computer algorithm to efficiently enumerate (repetition allowed) all ...
user avatar
3 votes
0 answers
147 views

For which $n$ is this ring an euclidean domain?

Let $f_n(x)=x^n-\sum\limits_{i=0}^{n-1}{x^i}$ and $A_n$ the number field corresponding to $f_n$. Question: Is $A_n$ for all $n$ an euclidean domain? Is there a good choice for an euclidean function? ...
Mare's user avatar
  • 25.8k
3 votes
0 answers
96 views

Deterministic procedure to find irreducible polynomials

In $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ is there a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(...
Turbo's user avatar
  • 13.7k
3 votes
0 answers
103 views

Can one do better than using general purpose determinant algorithms when using the Fisher-Kasteleyn-Temperley method for perfect matchings?

Questions. (numerical.generalPfaffian) Is it proved anywhere that in general it is not easier0 to calculate the determinant (over $\mathbb{Q}$) of the skew-symmetric signed adjacency matrix defined ...
Peter Heinig's user avatar
  • 6,001
3 votes
0 answers
163 views

Explicit roots in algebraic extention of Q with roots

Denis Bouhineau in "Solving Geometrical Constraint System Using CLP Based on Linear Constraint Solver" gave a method to find explicit square root in algebraic extention of Q with square roots. For ...
George Cherevichenko's user avatar
3 votes
0 answers
351 views

Using the Affine Maxima Package

The Maxima computer algebra system has a package called Affine for doing the calculations implicit in Bergman's diamond lemma for rings. It can be viewed as a kind of noncommutative analogue of ...
arsmath's user avatar
  • 6,720
3 votes
0 answers
338 views

Rank of Subgroup of Elliptic Curve

I'm currently looking at two rational points $ p, q $ on an elliptic curve $E$ over $ \mathbb{Q} $. SAGE tells me that $E$ has rank 5 and no torsion, and that $p$ and $q$ both have infinite order. ...
user4192's user avatar
  • 309
2 votes
0 answers
110 views

How to find a single-variable polynomial in a zero-dimensional ideal?

Given finitely many multivariate polynomials with algebraic coefficients that generate a zero-dimensional ideal, is there an easy way to find a nonzero single-variable polynomial in this ideal? If we ...
Dustin G. Mixon's user avatar
2 votes
0 answers
157 views

Help with Macaulay2 computation of invariant ring

Consider the algebraic group $G:=\operatorname{SL}_{2}\times\operatorname{SL}_{2}$ acting on $V:=\operatorname{Mat}_{2\times 2}\oplus\operatorname{Mat}_{2\times 2}$ via the action $(A,B)\,\cdot\,(X,Y)=...
It'sMe's user avatar
  • 767
2 votes
0 answers
75 views

Gröbner implicitization with relationships between the variables

I have the following parametric equations, where cost$=\cos t$, cos2t$=\cos 2t$, and $A^2+B^2=1$: ...
Stéphane Laurent's user avatar
2 votes
0 answers
243 views

Integer points on genus 1 curves using CAS

How can I practically find integer points on genus 1 curves with small coefficients using computer algebra systems (CAS), like Mathematica, Maple, SageMath, Magma, etc.? As a specific example, do ...
Bogdan Grechuk's user avatar
2 votes
0 answers
146 views

How to decide if an algebraic number is a root of a given polynomial?

Let $p$ be a polynomial with rational coefficients and $\alpha = \sqrt[n]{q}e^{i2k\pi/m}$ for some natural numbers $n,m,k$ and a rational number $q > 0$. Is there an effective algorithm for ...
Jára Cimrman's user avatar
2 votes
0 answers
43 views

Transforming a symmetric matrix into pentadiagonal form

Given a symmetric matrix $A$, which has complex values in the diagonal, but whose all other entries are real, I am interested in finding an orthonormal transformation $Q$ such that $Q^tAQ$ is a ...
Qwertuy's user avatar
  • 251
2 votes
0 answers
68 views

Checking for norm-Euclidean with a computer

Let $K$ be a finite Galois extension of $\mathbb{Q}$ and $O$ the ring of integers in $K$. Question: Is there an algorithm to test whether $O$ is norm-euclidean? In case the question has a positive ...
Mare's user avatar
  • 25.8k
2 votes
0 answers
105 views

Computer program which computes the automorphism group of Gram Matrix of lattice?

$\DeclareMathOperator\GL{GL}\DeclareMathOperator\Aut{Aut}$Fixed $n \geq 2$, given $K \in \GL(n,Z)$. One can view $K$ is a Gram matrix of Lattice. I also imposed that $K$ is symmetric i.e $K^{T}=K$. We ...
en kuo's user avatar
  • 145
2 votes
0 answers
113 views

Computing whether a set of polynomials cuts out a projective variety

I have a set of multivariate polynomials over $\mathbb{Q}$, and I want to compute whether they cut out a projective variety, i.e. whether the radical of the ideal $I$ that they generate is homogeneous....
Ben's user avatar
  • 1,010
2 votes
0 answers
78 views

Affine projection of polynomials for a given set of points

(Not sure this question fits here, I will remove it in case it doesn't) Let $F_{\mathrm{ML}}[x_1, \ldots,x_n]$ denote the set of multilinear polynomials over a finite field $F=\mathbb{F}_q$ (i.e. a ...
Ernie's user avatar
  • 53
2 votes
0 answers
71 views

CAS for finite-dimensional complex representations of $S_n$

Does there exist a computer algebra system that can work with finite-dimensional complex representations of the symmetric groups on finitely many letters? It should have the following functionality: (...
user avatar
2 votes
0 answers
63 views

Constructing stable equivalences for finite dimensional algebras

Given a finite dimensional (non-selfinjective) algebra $A$. Is there a method (for example using QPA) to construct algebras stable equivalent to $A$? Such a thing is easily possible for derived ...
Mare's user avatar
  • 25.8k
2 votes
0 answers
61 views

Efficient algorithm to prove that a polynomial ideal contains 1

I have the following problem: Suppose to have an ideal $I\triangleleft k[x_1,...,x_n]$ defined by generators. There exists an efficient algorithm (perhaps more efficient than calculating the Groebner ...
DDT's user avatar
  • 297
2 votes
0 answers
209 views

Combinatorial and computational problem related to Weyl groups and the coroot lattice

Let $W$ be a Weyl group with root system $R$ and with set of positive roots $R^+$. Let $\tilde{R}^+$ be the set of $B$-cosmall roots, i.e. positive roots $\alpha$ which satisfy $\ell(s_\alpha)=2\...
Christoph Mark's user avatar
2 votes
0 answers
120 views

Benchmark problems for computing rational points on varieties

Are there standard benchmark problem sets used for empirically evaluating algorithms designed for computing rational points on (various classes of) algebraic varieties? If so, could you please point ...
Grant Olney Passmore's user avatar
2 votes
0 answers
177 views

Randomized alternative to Buchberger's algorithm

Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra. Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...
user19172's user avatar
  • 529
2 votes
0 answers
254 views

Efficient computing critical points of algebraic function involved radical expression

I am interested in finding local optima of an algebraic function $f(X,Y)$. Suppose, that this expression involves radicals, for example $f(X,Y)= \frac{1}{2}(X+Y)-\sqrt{XY}$. The approach in which i am ...
Maciej Skorski's user avatar
1 vote
0 answers
28 views

Finite right-triple convex sets in planes

Let $\mathcal{S}$ be a set of points in $\mathbb{R}^2$. We say that $\mathcal{S}$ is right-angle convex, if for any two distinct points $P,Q\in \mathcal{S}$ there always exists another point $R\in \...
Joe Zhou's user avatar
  • 123
1 vote
1 answer
109 views

Factorial series $j(D)=\sum_{n=1}^\infty \frac{1}{(n^D)!}$ and hypergeometric functions

For positive integer $D$, define $j(D)=\sum_{n=1}^\infty \frac{1}{(n^D)!}$. For $D \le 6$, sage finds closed form in terms of hypergeometric functions at algrebraic arguments and fails to find closed ...
joro's user avatar
  • 24.2k
1 vote
0 answers
70 views

Hall-Littlewood polynomials with sage

I need to make some computations with Sage involving Hall-Littlewood polynomials. I couldn't find any satisfying information in the Sage manuals/tutorials that I found on the internet. What I found is ...
Paul Broussous's user avatar
1 vote
0 answers
208 views

Computer algebra programs that can solve polynomial systems on algebraically closed fields besides MAGMA

I was wondering which computer algebra programs out there can solve polynomial systems on the algebraic closure of $\mathbb{Q}$ analytically and efficiently. So far, I only found MAGMA with its ...
ArminJR's user avatar
  • 21
1 vote
0 answers
42 views

Is there a more efficient computer algebra system to solve the system of nonlinear equations in N-R method or other numerical methods?

Consider the system of infinite series \begin{align} &F=x+\frac{y^{3^2}}{3}+\frac{x^{3^5}}{3^2}+\frac{y^{3^7}}{3^3}+\frac{x^{3^{10}}}{3^4}+\frac{y^{3^{12}}}{3^5}+\cdots=0 \\ &G=y+\frac{x^{3^3}}...
MAS's user avatar
  • 872
1 vote
0 answers
41 views

Computer verification for hyperbolic trigonometry

I am currently writing a paper that requires some lengthy computations using basic hyperbolic trigonometry. So, several hyperbolic figures appear, and we apply the law of sines and so on in order to ...
user44172's user avatar
  • 541
1 vote
0 answers
129 views

Can PARI compute class numbers without factoring the discriminant?

When calculating properties of algebraic number fields, one of the hardest steps is factorizing the discriminant of a defining polynomial. This is necessary in the Pohst-Zassenhaus algorithm for ...
wandersam's user avatar
  • 125
1 vote
0 answers
133 views

Polynomial systems and algebraic functions

An algebraic function $y(x)$ is defined as the solution of a polynomial equation of the form $p(x,y)=0$, that is one making the identity $p(x,y(x))=0$ true --- in either analytical or formal power ...
Michele's user avatar
  • 313
1 vote
0 answers
214 views

How to solve special Diophantine equation systems (which one can solve by hand) with the computer?

I have a quadratic Diophantine equation system which is possibly not homogeneous and has some mixed and some linear terms. But I know that there are only finitely many solutions over the integers. One ...
Bernhard Boehmler's user avatar
1 vote
0 answers
177 views

Using Bertini software to determine whether or not a variety is empty

I have a system of polynomials $f_1,\dots, f_n \in \mathbb{C}[x_1,\dots, x_m]$, and I would like to determine whether the set of solutions to the system $f_1(x)=\dots=f_n(x)=0$ is empty or not. Since ...
Ben's user avatar
  • 1,010
1 vote
0 answers
78 views

Degree bounds on coordinates of points in a zero-dimensional variety

Let $S = \{f_1, \dots, f_s \in \mathbb{Q}[x_1, \dots, x_n]\}$ have a zero-dimensional nullset $V \subset \mathbb{C}^n$, and suppose that each $f_i$ has total degree at most $d$. Is there a shared ...
bean's user avatar
  • 479
1 vote
0 answers
175 views

Computing the class-preserving automorphism group of finite $p$-groups

Let $G$ be a finite non-abelian $p$-group, where $p$ is a prime. An automorphism $\alpha$ of $G$ is called a class-preserving if for each $x\in G$, there exists an element $g_x\in G$ such that $\alpha(...
Rohit's user avatar
  • 41
1 vote
0 answers
35 views

Grobner basis of the toric ideal $I_{A_P}$ with respect to $<_{rev}$ consists of those binomials $t_αt_β − t_{α\cap β} t_{α\cup β}$

I try to understand the proof of the Theorem. 10.1.3.(page 185) from ''Monomial Ideals'' by Herzog & Hibi. The reduced Grobner basis of the toric ideal $I_{A_P}$ with respect to $<_{rev}$ ...
Problemsolving's user avatar
1 vote
0 answers
109 views

generalized sieve implementations

Suppose I have a multiplicative function $f$ and I want to compute it for all integers from $1$ to $N$ (or maybe just for a long sequence of consecutive integers). It is clear that this is far faster ...
Igor Rivin's user avatar
  • 95.6k
1 vote
0 answers
174 views

Coefficient perturbations of polynomials with real roots only

Let \begin{align} P(x) &= x^n+a_{n-1} x^{n-1} +\ldots+a_0 = \prod_{i=1}^n (x-p_i)\\ Q(x) &= x^n + b_{n-1} x^{n-1} + \ldots +b_0 = \prod_{i=1}^n (x-q_i)\\ p_i, q_i& \in \mathbb{R},\ 0<...
vkonton's user avatar
  • 175
1 vote
0 answers
151 views

Efficient deterministic algorithms of factorizing

My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$. Are there such algorithms that use poly$(n, \log q)$ bit operations? I know ...
Alexey Milovanov's user avatar
1 vote
0 answers
107 views

Grobner basis for a general algebra

Let $R$ be a quotient of the polynomial ring $\mathbb{C}[x_1,\dots , x_n]$. We fix a $\mathbb{C}^*$ action on $R$ which preserve homogenous components and the multiplication. (The geometric analogue ...
Giulio's user avatar
  • 2,324
1 vote
0 answers
273 views

Algebraic independence criterion

Is there any criterion for checking algebraic independence of a set of polynomials in $n$ variables in terms of the leading monomials with respect to some monomial order ? The Jacobian criterion is ...
Jack's user avatar
  • 11
1 vote
1 answer
199 views

Finding generators of symmetric cones

I have a bunch of vectors $\mathbf v_i$ in $\mathbb R^n$. I would like to consider the cone $C$ spanned by these vectors, together with all the other vectors that can be obtained by permuting the ...
user avatar
1 vote
0 answers
215 views

How do I check if a sequence of R-modules is exact?

Let R be a ring. For example, take $R=k[x_1,\ldots,x_n]$ or, if possible, $R = \Bbb{Z}[x_1,\ldots,x_n]$. Consider a sequence of free R-modules $$R^a \stackrel{f}\to R^b \stackrel{g}\to R^c$$ where $f$...
Peter McNamara's user avatar
1 vote
0 answers
151 views

Calogero-Moser eigenfunction

The folllowing function \begin{equation} J(t_1,t_2,t_3,m,h)=[(1-e^{t_1-t_2})(1-e^{t_2-t_3})(1-e^{t_1-t_3})]^{-m/h} e^{-\frac{a_1t_1+a_2t_2+a_3t_3}{h}}\sum_{k_{1,1},k_{2,1},k_{2,2}\ge0}e^{(t_1-t_2)k_{1,...
Satoshi  Nawata's user avatar
1 vote
0 answers
545 views

Finding a generator of an ideal in an algebraic function field

I have an algebraic function field $\mathbb{Q}(x,y)$, where $y$ satisfies $$ (y^2-1)^2 = x^2(1+x^2), $$ and I need to find a rational function that has a first order root at $x=0,y=1$ a first order ...
Kirill's user avatar
  • 416
1 vote
0 answers
197 views

Testing functional equivalence

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
Denis Serbin's user avatar
1 vote
0 answers
205 views

Computer package to compute HOMFLY polynomial?

I apologize of already asked by someone else, but what (in your opinion) is the best package for computing HOMFLY polynomials?
minimax's user avatar
  • 1,137
1 vote
0 answers
122 views

What is the largest computed summatory liouville interval ?

I am interested to know the largest computed summatory liouville interval, an implementation of which is detailed in Section 4.1 of [1]. The wikipedia page [2] for the function charts summatory ...
Rob's user avatar
  • 11
1 vote
0 answers
238 views

How to ask Magma to compute the induced morphisim on divisor group

Suppose Magma has computed homomorphism $h$ between function fields $F1 \to F2$. Then we have an induced homomorphism $h$ on the divisor group. Now my question is that if there's a better way to ...
Syed's user avatar
  • 601