-2
votes
1answer
218 views

Polygon Problem [closed]

There are $N$ regions which are numbered from $1$ to $N$. Each region is represented by a single simple polygon on the 2D plane. Simple polygon means the boundary of the polygon does not cross itself. ...
7
votes
3answers
659 views

smooth manifolds as real algebraic set (continued)

There are several ways of producing manifolds,say: 1.orbits space of group action 2.connected sum of manifolds 3.underlying topological space of nonsingular algebraic set .... here,i am ...
1
vote
1answer
271 views

calculate function from its divizor

There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$. There is algebraic function f on C. We have div(f). How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + ...
7
votes
1answer
355 views

Constructive proof of “Projective implies proper”

For every ring $A$, the structural morphism of schemes $\pi_A : {\bf P}^n_{A} \to {\rm Spec}{A}$ is a closed map. The usual proof of this fact is not constructive : given equations of a closed subset ...
9
votes
2answers
644 views

How to compute the Picard rank of a K3 surface?

I'm curious about the following question: Given a K3 surface, how does one proceed to compute its rank? Of course the answer may depend on the form of the input, i.e. how the K3 is "given". So ...
10
votes
3answers
453 views

Algorithms in Invariant Theory

Let $V$ be a polynomial representation of the general linear group $\Gamma:=\DeclareMathOperator{\Gl}{Gl}\Gl_n(\newcommand{\C}{\mathbb C}\C)$. In chapter 4.6 of his book "Algorithms in Invariant ...
1
vote
0answers
136 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 ...
3
votes
2answers
164 views

Determination of rationality and computing a rational parametrization

Suppose I have a hypersurface in $\mathbb{C}P^n$ given by some $f(z_1, \dots, z_{n+1}) = 0.$ Is there an algorithm which returns a rational parametrization if there is one, and "not rational" ...
9
votes
1answer
922 views

Groebner basis for Sudoku

I'm trying to write a program that solves sudoku's using a Groebner basis. I introduced 81 variables $x_1$ to $x_{81}$, this is a linearisation of the sudoku board. The space of valid sudokus is ...
2
votes
1answer
202 views

Nearest trio of neighbours for non-intersecting ellipses

Hi, I'm working on a problem which is to find the closest trio of neighbours for a set of arbitrarily placed non-intersecting ellipses. As a new user I'm not allowed to include image tags but I've ...
6
votes
2answers
375 views

Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The ...
3
votes
1answer
317 views

Mathematical Programming with other Algebras than Linear

Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization. What analogies are there for ...
3
votes
0answers
131 views

A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello, What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain $E = \{1,...,n\}$ and a partial function $f: E^3 \to \{-1, 0, 1\}$ ...
3
votes
1answer
455 views

Quick algorithm for finding real solutions for a system polynomial equations

Would you please recommend a computer program that could give quick answer Yes/No for the question: does there exist a real solution of a given system of polynomial equations with integer ...
13
votes
3answers
1k views

When are (finite) simplicial complexes (smooth) manifolds?

Hi, is there an algorithm that determines if a given simplicial complex is a.) a manifold b.) a smooth manifold c.) homotopy equivalent to a manifold d.) a real algebraic variety ?
7
votes
2answers
605 views

An effective way to tell if the saturation of a homogeneous ideal is the irrelevant ideal

Let $\Bbbk$ be an algebraically closed field, let $R$ denote the graded ring $\Bbbk[x_0, \dotsc, x_N]$, and let $f_1, \dotsc, f_n \in R_m$ be nonconstant homogeneous polynomials. Then the common ...
13
votes
2answers
896 views

Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...
16
votes
6answers
3k views

Algorithms for finding rational points on an elliptic curve?

I am looking for algorithms on how to find rational points on an elliptic curve $$y^2 = x^3 + a x + b$$ where $a$ and $b$ are integers. Any sort of ideas on how to proceed are welcome. For example, ...
0
votes
1answer
415 views

How to formulate such problem mathematicaly? (line continuation search) [closed]

I have an array of "lines" each defined by 2 points. I am working with only the line segments lying between those points. I need to search lines that could continue one another (relative to some ...
8
votes
6answers
657 views

Variety defined by a recursively enumerable set of polynomials

Suppose we have a recursively enumerable set of polynomials $\mathcal{P}=\{ p_1({\bf x}), p_2({\bf x}), \ldots\}, p_i \in \mathbb{Z}[{\bf x}], {\bf x} = (x_1, \ldots, x_n)$. Let $V(\mathcal{P})$ ...
44
votes
4answers
2k views

What algorithm in algebraic geometry should I work on implementing?

This summer my wife and one of my friends (who are both programmers and undergraduate math majors, but have not learned any algebraic geometry) want to learn some algebraic geometry from me, and I ...
25
votes
2answers
914 views

Groebner basis with group action

At one point my advisor, Mark Haiman, mentioned that it would be nice if there was a way to compute Groebner bases that takes into account a group action. Does anyone know of any work done along ...
23
votes
4answers
2k views

Can Gröbner bases be used to compute solutions to large, real-world problems?

In particular, suppose I have an affine algebraic variety over $\mathbb{R}^n$ described by generators of a radical ideal $I$ and I want to find (perhaps not all of the) points in the variety. Several ...
6
votes
3answers
841 views

Polynomials that are sums of squares

Is any algorithm known for determining whether or not a multivariate polynomial with integer coefficients can be written as a sum of squares of such polynomials? By way of background, if we one ...