53 votes
Accepted

Minimal polynomial of cos(π/n)

The minimal polynomial of $\cos(2\pi/n)$ (by William Watkins and Joel Zeitlin, The American Mathematical Monthly Vol. 100, No. 5 (May, 1993), pp. 471-474) has full clarity on this matter (just take ...
user avatar
39 votes
Accepted

How does Mathematica do symbolic integration?

An overview by one of the developers of Mathematica, focusing on definite integrals, is at Symbolic definite integration: methods and open issues. Mathematica knows all the entries in Gradshteyn-...
user avatar
32 votes
Accepted

Does there exist a complete implementation of the Risch algorithm?

No computer algebra system implements a complete decision process for the integration of mixed transcendental and algebraic functions. The integral from the excellent paper of Schultz may be solved by ...
user avatar
  • 436
29 votes
Accepted

What is currently feasible in invariant theory for binary forms?

Let $F$ be a binary form of degree $d$, namely, a homogeneous polynomial of the form $$ F(\mathbb{x})=\sum_{i=0}^{d}\left(\begin{array}{c}d\\ i \end{array}\right)f_i\ x_1^{d-i}x_2^i $$ where $\mathbb{...
user avatar
25 votes

How does Mathematica do symbolic integration?

Maple uses the Risch algorithm; see Keith Geddes and George Lebahn, Symbolic and numeric integration in Maple
user avatar
  • 23.4k
25 votes
Accepted

How can you find an integer coefficient polynomial knowing its values only at a few points (but requiring the coefficients be small)?

You can certainly do better than brute force by considering modular constraints. If the solution is $p(x) = \sum_i a_i x^i$ then $p(x) - \sum_{j=0}^{n-1} a_j x^j$ is divisible by $x^n$ and $$\frac{p(x)...
user avatar
  • 4,582
23 votes

Algebraic dependency over $\mathbb{F}_{2}$

Not for $n=2$. I'm afraid this answer uses a lot more algebraic geometry than the question; I spent some time trying to remove it and failed. Suppose, for the sake of contradiction, that $f_1$ and $...
user avatar
21 votes
Accepted

two's and three's survive in gcd of Lagrange

The claim is certainly true for $n$ sufficiently large, and "sufficiently large" could be specified explicitly with more care. We follow the suggestion of Fedor Petrov, and rely on the results of ...
user avatar
  • 86.4k
20 votes

Web interface for GAP (or other computer algebra system dealing with finite groups)?

You can get at GAP through http://sagemath.org, which has a perfectly fine web notebook interface.
user avatar
  • 93.9k
18 votes

What is the minimum size of a partial order containing all partial orders of size 5?

(Edited several times from earlier partial answer, which gave $f(5) \ge 11$.) We have exact results $f(5) = 11$ and $f(6)=16$, and bounds $16 \le f(7) \le 25$. 1. Proving $f(5)=11$ A short proof shows ...
user avatar
17 votes

How does Mathematica do symbolic integration?

People usually mention the Risch algorithm first, as other answers have. Another approach, which is surprisingly successful, is to do what you or I would when solving integrals: look for patterns for ...
user avatar
16 votes

Minimal polynomial of cos(π/n)

I guess you mean a polynomial $p(x)$ with rational coefficients. Then, once $\cos {\pi/n}$ is a root of $p(x)$, $\deg p=d$, $e^{ip/n}$ is a root of a polynomial $t^dp((t+1/t)/2)$. But $e^{i\pi/n}$ is ...
user avatar
  • 89.4k
16 votes
Accepted

Representing field elements in a computer

You are looking at a computable field (if your focus is on the field), or a computable presentation of a field (if your focus is on the details of how elements and operations are coded). These objects ...
user avatar
  • 3,391
16 votes

Does there exist a complete implementation of the Risch algorithm?

Fricas, an open-source clone of Axiom, implements a considerable chunk of Risch, see http://fricas-wiki.math.uni.wroc.pl/RischImplementationStatus Fricas is also available as a optional package of ...
user avatar
16 votes

How can you find an integer coefficient polynomial knowing its values only at a few points (but requiring the coefficients be small)?

Perhaps not the best possible polynomial but a very good polynomial can generally be computed by the LLL algorithm: Let $I$ be an integral polynomial taking the given values at the given points and ...
user avatar
15 votes

Fast computation of a Groebner basis. What is possible?

Note that the Groebner basis engine in Maple has been Faugère's (and colleagues)'s for a few versions now. So that is as state-of-the-art as it goes. The sizes you mention should be well in-scope of ...
user avatar
15 votes

From polynomial ideal over $\mathbb{Q}$ to polynomial ideal over $\mathbb{Z}$

Let J be a finitely generated ideal in $A = \mathbf{Z}[x_1,\dotsc,x_n]$. (Take your ideal $I$ and scale its generators to clear denominators.) The ideal you want is then $$ J' = \{f\in A: \exists n\in\...
user avatar
  • 151
14 votes
Accepted

How to compute with the Stark conjectures?

The main reference here is the very useful User's Guide, C. Batut, K. Belabas, D. Bernardi, H. Cohen, M. Olivier, "User's Guide to PARI / GP" (2003) Particularly the sections about bnrstark (pp. 108)...
user avatar
  • 17.1k
14 votes

Computation of a minimal polynomial

In Sage you can do something like: ...
user avatar
13 votes
Accepted

An efficient isomorphism between finite fields

Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (...
user avatar
13 votes

Is computer algebra or symbolic computation an active area of research?

[This is certainly a biased view, but too long for a comment, and hopefully these are some helpful starting points. ] I'd say it's active but in the US not huge (more elsewhere in the world). A few ...
12 votes

Is there a way of canonically labelling permutation groups?

A quick way to obtain canonical conjugates of permutation groups would of course be nice, but hoping for that may be a bit too optimistic. Rather than trying to go that route, in your situation I ...
user avatar
  • 18.2k
12 votes
Accepted

A question on a Macaulay2 computation

Commutative algebra is NOT the same as algebraic geometry, especially projective algebraic geometry. The variety in $\mathbb{P}^9$ defined by $I$ and the variety in $\mathbb{P}^9$ defined by $I_0$ are ...
user avatar
11 votes
Accepted

A centralised website for computational attempts in graph theory and metric geometry?

There are a few websites with lists and/or databases of graphs, maps and polytopes. House of graphs has a searchable database of interesting graphs and aims to serve as a repository for lists of ...
user avatar
11 votes
Accepted

Verify that a group is hyperbolic via computer algebra

The KBMAG package can be used to verify hyperbolicity of a group defined by a finite presentation. It does it by verifying that geodesic bigons in the Cayley graph are uniformly thin. Then a result of ...
user avatar
  • 34.1k
11 votes
Accepted

Web interface for GAP (or other computer algebra system dealing with finite groups)?

There is the Magma calculator which can be used to do calculations in finite groups. One problem is that you have to type in all of your input before executing it, but with practice you can do quite ...
user avatar
  • 34.1k
11 votes
Accepted

Greatest common divisor in $\mathbb{F}_p[T]$ with powers of linear polynomials

This is false. Let $p$ be an odd prime, let $\ell$ be another prime, and let $m$ be a small prime divisor of $p^{\ell}-1$, that doesn't divide $p-1$. Let $n= 1 + \frac{ p^{\ell}-1}{m}$. Then $n-1$ ...
user avatar
  • 117k
11 votes

How does Mathematica do symbolic integration?

One approach to symbolic integration is using representations as Holonomic functions (https://en.wikipedia.org/wiki/Holonomic_function): solutions to differential equations of the form: $$p_r f^{(r)} +...
user avatar
  • 239
10 votes
Accepted

From polynomial ideal over $\mathbb{Q}$ to polynomial ideal over $\mathbb{Z}$

I am aware that I am replying to an old question that has been satisfactorily answered, but I think it might be worth while pointing out, for the completeness of MathOverflow, that the question is ...
user avatar
  • 22.4k
10 votes

Algebraization of Bayesian networks?

A bayesian network corresponds to an independence (algebraic) variety and hence to a polynomial ring over $\mathbb{R}$. You can start from Garcia, Luis David, Michael Stillman, and Bernd Sturmfels. ...
user avatar
  • 7,523

Only top scored, non community-wiki answers of a minimum length are eligible