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
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 ...
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?
...
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(...
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 ...
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 ...
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 ...
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. ...
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 ...
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)=...
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$:
...
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 ...
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 ...
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 ...
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 ...
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 ...
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....
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 ...
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: (...
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 ...
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 ...
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\...
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 ...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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}}...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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(...
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}$ ...
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 ...
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<...
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 ...
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 ...
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 ...
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 ...
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$...
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,...
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 ...
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 ...
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?
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 ...
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 ...