9
$\begingroup$

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})$ denote the affine variety in $\mathbb{C}^n$ defined by $\mathcal{P}$. Is there an algorithm to compute $V(\mathcal{P})$? By the Nullstellensatz, we know that we need only use finitely many of the polynomials $p_i$ to cut out $V(\mathcal{P})$. We can recursively compute varieties cut out by $\{p_1, \ldots, p_k\}$, for example by computing a Grobner basis for the radical ideal of $(p_1,\ldots,p_k)$. But is there a way to compute $k$ such that $V(\mathcal{P})=V(p_1,\ldots,p_k)$?

Please let me know if this question needs clarification or if I'm not using the correct notation.

Addendum: This problem was motivated by this MO question. It would follow from:

If one has a finitely generated group $G$ with solvable word problem, for any $n$ can one compute the representation variety $G\to SL_n(\mathbb{C})$?

I view $G$ as being given as the homomorphic image of a free group $\\langle g_1,\ldots,g_k\\rangle$. Moreover, there is a Turing machine which takes as input any element $h\in \\langle g_1,\ldots,g_k\\rangle$ and tells if $h$ is trivial in $G$. The space of representations $\rho:G\to SL_n(\mathbb{C})$ is an affine variety, with $kn^2$ variables given by the entries of the matrices of $\rho(g_i)$. One can recursively generate polynomials which are the entries of the matrices $\rho(h)-I$ which cut out the representation variety (together with $det(\rho(g_i))-1$). So the algorithm should depend on how these polynomials are generated, if one wants to be able to compute the representation variety for each $n$. I suspect that the answer is no, although I'm not sure how to generalize Borcherds or Groves' answers to this context.

If one could compute the representation variety, then one could determine if $G$ has a homomorphism to a finite group.

$\endgroup$
5
  • $\begingroup$ I am not sure how terms like recursively enumerable apply when complex numbers are around. $\endgroup$ Jul 20, 2010 at 1:49
  • $\begingroup$ In view of Borcherd's reply maybe you ask the question with the first line changed. For example, the set of polynomials is a rational language, that is, is recognised by a finite state automaton. $\endgroup$ Jul 20, 2010 at 1:52
  • $\begingroup$ I like your suggestion Bruce, but I don't think it's relevant to the question I'm interested in. $\endgroup$
    – Ian Agol
    Jul 20, 2010 at 3:21
  • $\begingroup$ I think the formulation of the problem is ambiguous in that it is not clear if the algorithm is allowed to depend on $\mathcal P$ or not. If it is then of course there is an algorithm, just let it print out a set of generators of the ideal. If it isn't then you need to specify what the algorithm is allowed to see of $\mathcal P$. If it may only see the output, then Daniel's answer is correct but if it is allowed to see a primitive recursive function generating $\mathcal P$ then borcherds' answer is correct as we know that there is no algorithm to decide whether the function just outputs $0$'s. $\endgroup$ Jul 20, 2010 at 8:18
  • $\begingroup$ Yes, Torsten, I meant that the algorithm should depend on $\mathcal{P}$, or rather the algorithm that generates $\mathcal{P}$. $\endgroup$
    – Ian Agol
    Jul 20, 2010 at 16:36

6 Answers 6

6
$\begingroup$

There is no such algorithm, even if n is zero. Take p_i to be 0 unless you can find a counterexample of length i to your favorite unsolved math problem (such as "is 2i+4 the sum of 2 primes?"), in which case p_i is 1.

$\endgroup$
6
  • $\begingroup$ Ok, that was too easy! $\endgroup$
    – Ian Agol
    Jul 20, 2010 at 3:18
  • 1
    $\begingroup$ Clever, but this doesn't quite work, since it only provides a single P. So either the algorithm which always answers yes', or the algorithm which always answers no' will do the trick. (We just don't know which one...). $\endgroup$ Jul 20, 2010 at 3:19
  • $\begingroup$ Sorry, I mean the algorithm which always answers p_1' or else the algorithm which always answer p_j' where j is the smallest counterexample to the Goldbach conjecture. (Just because we don't know what the answer to the Goldbach Conjecture is doesn't invalidate the existence of this Turing Machine). $\endgroup$ Jul 20, 2010 at 3:22
  • $\begingroup$ The point is that any algorithm that can solve Agol's problem can also solve any open problem equivalent to the problem of determining if a recursively enumerable set is empty, which is in turn equivalent to the (unsolvable) halting problem for Turing machines. $\endgroup$ Jul 20, 2010 at 14:51
  • $\begingroup$ Yes, but the Goldbach conjecture encoded the way you describe is not `equivalent to the problem of determing if a recursively enumerable set is empty'. The Goldbach Conjecture is either true or false, and your set is either all 1's or it isn't. In either case, there's a Turing machine which does the trick (I just don't know which Turing machine to pick). $\endgroup$ Jul 20, 2010 at 16:49
8
$\begingroup$

There cannot be such an algorithm. Suppose that there were and call the algorithm $A$. Let $\mathcal P$ be a sequence which has a nonempty set $V(\mathcal P)$, and suppose that $V(\mathcal P) = V(\{p_1, \ldots , p_k\})$. Feed $\mathcal P$ to $A$ and look at what happens. $A$ decides that $k$ suffices on the basis of reading a finite number of polynomials, say up to $p_j$. Now, $j$ may be much bigger than $k$, and I'll assume that $j \ge k$. Now make a sequence $\mathcal P'$, which is the same as $\mathcal P$ except that $p_{j+1} = 1$. Then $V(\mathcal P') = \emptyset$, but $A$ won't discover this and will output that for $\mathcal P'$ the number $k$ suffices. But it doesn't, since for $\mathcal P'$ we need to go to $j+1$ to find that $V(\mathcal P') = \emptyset$. So there's no such $A$.

$\endgroup$
2
  • $\begingroup$ @Daniel-I'm not sure this answers the question. There is perhaps a question of what the "input" is. Your argument shows that there is no algorithm which when given a sequence of polynomials can determine the variety they define (though one would have pick a formalizm where this kind of algorithm makes sense) It doesn't rule out the possibility that such an algorithm might exist so that if the input is a code for a Turing machine producing the sequence. Perhaps the algorithm could somehow take advantage of the code. I argue below that it can't. $\endgroup$ Jul 20, 2010 at 17:42
  • $\begingroup$ @Dave. Yes that is a fair point. I was thinking of being given the polynomials... Your answer is better in any case. $\endgroup$ Jul 20, 2010 at 21:29
4
$\begingroup$

Answering the same question twice with opposite answers seems a little indecisive, but anyway:

Hilbert ran into essentially this problem in his work on invariant theory. More precisely he showed that certain ideals were finitely generated without at first giving an algorithm for finding a finite basis. It was this that provoked Gordan's famous comment about Hilbert's work being theology not mathematics (which was a joke, not a criticism of Hilbert: Gordan had a humorous streak and thought very highly of Hilbert's work). However Hilbert was later able to make his work on invariant theory constructive, and show that it was possible to find finite generating sets in `the cases that actually came up in invariant theory.

The point of this is that although the problem as stated has no solution for arbitrary recursively enumerable sequences of polynomials, it is quite likely that there is an algorithm `that covers all the recursively enumerable sequences you are interested in.

$\endgroup$
1
  • $\begingroup$ That's what I was trying to say too. $\endgroup$ Jul 20, 2010 at 13:05
4
$\begingroup$

I think the answer is no, but let me first give a precise version of the question (which I think Daniel's argument doesn't quite address).

Fix some reasonable listing $P_0,P_1,\dots$ of recursively enumerable sets of polynomials. [See below for a ``reasonable" coding.]

I claim that there is no algorithm to determine if $V(P_e)=\emptyset$.

Let $K$ be the diagonal halting set. Namely, $K=$ {$e$: the $ e^{\rm th}$ Turing machine halts on input $e$}.

For each $e$ let $P_e=\{p_0,p_1,\dots\}$ be the recursively enumerable sequence of polynomials where $p_i=0$ if the $e^{\rm th}$ Turing machine has not halted by stage $i$ and $p_i=1$ if has. Then $V(P_e)=\emptyset \Leftrightarrow e\in K$. Since $K$ is undecidable there is no algorithm to decide if $V(P_e)$ is empty.

One way to code sequences of polynomials would be to let $q_0,q_1,\dots$ list all polynomials, and let $P_e$ be {$q_i:$ the $e^{\rm th}$ Turing machine halts on input $i$}. To get to Ian's setting we could view $P_e$ as the sequence $p_0,p_1,\dots$ where $p_{(i,j)\}$ is 0 unless the $e^{\rm th}$ Turing machine halts on input i at stage $j$ in which case it is $q_i$ and $(i,j)$ is some computable pairing function.

$\endgroup$
1
  • $\begingroup$ Your claim also follows immediately from Rice’s theorem. $\endgroup$ Nov 1, 2011 at 14:43
2
$\begingroup$

Agol's other question (If one has a finitely generated group G with solvable word problem, for any n can one compute the representation variety G -> SLn(C)) also has a negative answer. In fact one cannot even compute the number of homomorphisms to the group of order 2 when G is generated by one element g. Take the relations to be g^(2k+1)=1 if some given Turing machine halts for the first time after k steps. A little thought shows that this group has an effectively solvable word problem and an effectively recursive set of relations, but one cannot decide if it has a homomorphism to the group of order 2 without solving the halting problem for the given Turing machine.

$\endgroup$
5
  • $\begingroup$ I'm not sure this works--as far as I can tell you haven't actually produced a group, but instead a function $f$ from "Turing machines" to "groups". The composition of this function with the function $g$ from "groups" to "number of homomorphism to $\mathbb{Z}/2\mathbb{Z}$" is not computable, but only because $f$ is not computable. $\endgroup$ Jul 20, 2010 at 19:11
  • $\begingroup$ The function from Turing machines to groups with effectively solvable words problem is computable. Given a Turing machine and an integer k, one can effectively compute if g^k=1. $\endgroup$ Jul 20, 2010 at 19:51
  • $\begingroup$ This doesn't answer the 2nd question as stated - one is given a generating set, plus a Turing machine which answers the word problem. You're interpreting the question as given a recursively presented presentation, which is different. $\endgroup$
    – Ian Agol
    Jul 27, 2010 at 16:20
  • $\begingroup$ You are correct that in general a recursively generated presentation does not have a solvable word problem. However the particular example of a recursive presentation I gave does have a solvable word problem. $\endgroup$ Jul 27, 2010 at 17:59
  • $\begingroup$ Ok, I see, I misunderstood your answer. I guess I shouldn't ask the question with the particular solution to the word problem given, since your example shows that you can choose a particularly nasty one. $\endgroup$
    – Ian Agol
    Jul 28, 2010 at 20:23
1
$\begingroup$

If you make some further assumptions about how that recursively generated set is actually generated, then yes you can [other answers show that, without these, you can't]. The most natural one is some degree condition -- i.e. that the total degree of your polynomial grows. That's actually not enough. What you really need is a condition which will imply that the Newton Polygon of your set of polynomials will no longer change once $k$ is large enough.

In other words, for your problem to switch from 'undecidable' to 'solvable', you need stronger invariants than what you get simply by saying 'recursively enumerable over $\mathbb{Z}[\mathbf{x}]$'. And, frequently, you do have such invariants right in your generation procedure for the $p_i$'s; whenever the $p_i$'s do not encode some kind of (undecidable) arithmetic statement, there's a chance. In other words, in your case, do you actually have more structure than you gave in your question?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.