MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\Gamma$ be a finitely generated subgroup of $C^*$. For a polynomial $P\in Z[x_1,...x_k]$, determine whether $P(x_1,...x_k)=0$ has a zero in $\Gamma$. Is this decidable?

Motivation is related to the question whether whether there are standard examples of stable theories that are undecidable: the theory of $(C,+,*, \Gamma)$ (that is, we add a predicate for the subgroup $\Gamma$) is superstable, and a positive answer is necessary (and perhaps sufficient) for this theory to be decidable. With a similar motivation (the superstable theory of generic powers where you add to an algebraically closed field multivalued functions $x^\alpha$ where $\alpha$ is sufficiently generic), one can ask similar but complicated number theoretic questions related to Faltings' and Ax's theorems. $\Gamma$.

share|cite|improve this question
How are you given $\Gamma$? – Qiaochu Yuan Nov 25 '11 at 17:17
@QiaochuYuan: in any way you prefer, say by giving the finitely many generators as complex numbers. – mmm Nov 26 '11 at 2:22
@mmm: okay, but how are you given the complex numbers? – Qiaochu Yuan Nov 26 '11 at 3:19
The question is equivalent to the following one. Given an ideal $I$ in the ring of polynomials $\mathbb{C}[x_1,...,x_n]$ and a polynomial $f(x_1,...,x_m)$ consider the set $F$ of all polynomials obtained from $f$ by substitutions $x_i\mapsto u_i$, $i=1,...,m$, where $u_i$ are monomials in $\mathbb{C}[x_1,...,x_n]$. Question: Is intersection $F\cap I$ empty? The set $F$ does not have a nice structure, so the answer is not clear. To be more precise and to be able to talk about algorithms, one probably need to replace $\mathbb{C}$ by the algebraic closure of $\mathbb{Q}$. But it is not necessary – Mark Sapir Nov 26 '11 at 3:53
Continued: one can always assume that all coefficients are in some finitely generated subfield of $\mathbb{C}$ which is a finite extension of a purely transcendental extension of $\mathbb{Q}$ (of finite transcendence degree). This gives a way to algorithmically represent the generators of $I$ and coefficients of $F$. – Mark Sapir Nov 26 '11 at 4:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.