<p>A model of computation allowing real numbers is the Real-RAM model. In this model, it is impossible to even decide if a number is rational. Indeed, the time-T halting sets are semialgebraic. If any one of them has a non-empty interior, then the time-T yes-set and time-T no-sets are semialgebraic subsets with no-empty interior, which is a contradiction. If none of the time-T halting sets is semialgebraic, then their union cannot be $\mathbb{R}$.</p>

<p><strong>Answer to the previous version of the question:</strong></p>

<p>If $a_1,\dotsc,a_k$ are algebraic numbers that are linearly independent over $\mathbb{Q}$, then $e^{a_1},\dotsc,e^{a_k}$ are algebraically independent over $\mathbb{Q}$. This is the <a href="https://en.wikipedia.org/wiki/Lindemann%E2%80%93Weierstrass_theorem" rel="nofollow">Lindemann–Weierstrass theorem</a>. So, if $a$'s are algebraic (as in the current version of the question), then the answer to your question is "yes". </p>

CC BY-SA 3.0
2015-09-08T17:26:11.150Z
Right. The interesting case is when they are non algebraic, which is exactly the point of the question.
Shaull
CC BY-SA 3.0
2015-09-08T17:48:35.303Z
@Shaull What class of numbers you allow for the input then? You cannot allow all reals because there are uncountably many of them.
Boris Bukh
CC BY-SA 3.0
2015-09-08T18:13:29.747Z
We could consider a model that allows real numbers, or indeed - choose some other representation of a subset of the reals. As I wrote - I'm trying to figure out if resolving Schanuel's conjecture would lead to a constructive solution.
Shaull
CC BY-SA 3.0
2015-09-08T18:14:11.123Z
@Shaull Sorry, but these details *do matter*, and are *non-trivial*. You really should explain yourself. It is impossible to answer an imprecise question.
Boris Bukh
CC BY-SA 3.0
2015-09-08T18:20:38.077Z
I do not claim for a second that these details don't matter. Clearly they do. I don't have a suggestion for an encoding which would suggest that the problem is decidable or non-decidable, so I prefer to leave this open. I'll edit the question to clarify that.
Shaull
CC BY-SA 3.0
2015-09-09T14:36:35.510Z
@Shaull I updated my answer in response to your edit. Does it now answer your question?
Boris Bukh
CC BY-SA 3.0
2015-09-09T15:36:14.443Z
Your answer is indeed correct, but it somehow circumvents the issue. I agree that the fault may be in the formulation of the question, but the main idea is: if there was a proof of Schanuel's conjecture, without knowing whether it's constructive or not, would you be able to turn it into a constructive argument? It seems that your answer suggests the answer is "no", but it's not entirely clear yet, since we would have to assume that the numbers are given as an input for a TM. Anyway, I upvoted, and if no other answers come up, I'll accept. Thanks.
Shaull
CC BY-SA 3.0
2015-09-08T15:11:14.950Z
2015-09-08T18:37:24.810Z
2015-09-08T18:37:24.810Z
Boris Bukh
<p>A set of numbers $S=\{x_1,...,x_n\}$ is said to be <em>algebraically dependent</em> if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a subset thereof).</p>

<blockquote>
  <p>Given numbers $S=\{x_1,...,x_n\}$, is it decidable whether they are algebraically dependent?</p>
</blockquote>

<p>Now, there is obviously an encoding issue here, since the numbers need to be transcendental, so describing them is problematic. Any solution would do, but specifically, I am interested in the case where all the numbers are of the form $e^{a_i}$, where the $a_i$'s are linearly independent over $\mathbb Q$.</p>

<p>The motivation for this question is understanding whether a (positive) solution to <a href="https://en.wikipedia.org/wiki/Schanuel%27s_conjecture" rel="nofollow">Schanuel's conjecture</a> would automatically lead to a constructive solution.</p>

<p>UPDATE (based on the comments): the encoding of the numbers is an issue. I'll accept any answer which suggests either a reasonable encoding for a subset of the reals for which the problem is non-trivial, or a solution that uses a computational model that allows real numbers.</p>

CC BY-SA 3.0
2015-09-06T10:38:44.157Z
What do you mean with "numbers"? In other words, how do you specify the input numbers? You have to realize the the set of input numbers must be a countable set (so for sure it cannot be all real numbers)
boumol
CC BY-SA 3.0
2015-09-06T11:56:37.877Z
As I wrote, I'm open for interpretations here, but the most relevant numbers would be $e^{a_i}$, where $a_i$ are rational. Such a number can be described by the respective rational $a_i$.
Shaull
CC BY-SA 3.0
2015-09-07T15:04:58.630Z
I think that very much depends on the quantitative bounds in the proof (if and when there is one) of Schanuel's conjecture. For example, Baker's theorem currently gives a bound that is a function of Height, degree of the algebraic numbers involved. This immediately translates to the precision to which the numbers have to be evaluated. So AFAIK, essentially this is a question of whether the bounds are effective. Does that make sense?
Nikhil
CC BY-SA 3.0
2015-09-07T15:12:28.443Z
@Nikhil - I agree that if and when there is a proof, it is likely to go through such bounds, and then would probably yield an effective solution. However, what if the proof involves a non-constructive argument? (e.g. probabilistic method)
Shaull
CC BY-SA 3.0
2015-09-07T22:41:47.853Z
If the $a_i$ are rational, aren't their exponentials trivially algebraically dependent? $e^{p/q},e^{r/s}$ are roots to $x^{qr}-y^{ps}=0$.
Holden Lee
CC BY-SA 3.0
2015-09-08T04:59:16.263Z
@HoldenLee Right, sorry, I somehow confused "rational" with "linearly independent over $\mathbb Q$". I edited the question. So regarding representation - anything goes.
Shaull
<algebra><decidability>
Is algebraic dependency decidable?
Shaull
# Is algebraic dependency decidable?

(Asked by: username_0 on 2015-09-05)

A set of numbers $S=\{x\_1,...,x\_n\}$ is said to be *algebraically dependent* if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x\_1,...,x\_n$ (or a subset thereof).

> Given numbers $S=\{x\_1,...,x\_n\}$, is it decidable whether they are algebraically dependent?

Now, there is obviously an encoding issue here, since the numbers need to be transcendental, so describing them is problematic. Any solution would do, but specifically, I am interested in the case where all the numbers are of the form $e^{a\_i}$, where the $a\_i$'s are linearly independent over $\mathbb Q$.

The motivation for this question is understanding whether a (positive) solution to [Schanuel's conjecture](https://en.wikipedia.org/wiki/Schanuel%27s_conjecture) would automatically lead to a constructive solution.

UPDATE (based on the comments): the encoding of the numbers is an issue. I'll accept any answer which suggests either a reasonable encoding for a subset of the reals for which the problem is non-trivial, or a solution that uses a computational model that allows real numbers.

**Tags:** algebra, decidability

> **Comments:**
> **username_1**: What do you mean with "numbers"? In other words, how do you specify the input numbers? You have to realize the the set of input numbers must be a countable set (so for sure it cannot be all real numbers)  
> **username_0**: As I wrote, I'm open for interpretations here, but the most relevant numbers would be $e^{a_i}$, where $a_i$ are rational. Such a number can be described by the respective rational $a_i$.  
> **username_2**: I think that very much depends on the quantitative bounds in the proof (if and when there is one) of Schanuel's conjecture. For example, Baker's theorem currently gives a bound that is a function of Height, degree of the algebraic numbers involved. This immediately translates to the precision to which the numbers have to be evaluated. So AFAIK, essentially this is a question of whether the bounds are effective. Does that make sense?  
> **username_0**: @username_2 - I agree that if and when there is a proof, it is likely to go through such bounds, and then would probably yield an effective solution. However, what if the proof involves a non-constructive argument? (e.g. probabilistic method)  
> **username_3**: If the $a_i$ are rational, aren't their exponentials trivially algebraically dependent? $e^{p/q},e^{r/s}$ are roots to $x^{qr}-y^{ps}=0$.  
> **username_0**: @HoldenLee Right, sorry, I somehow confused "rational" with "linearly independent over $\mathbb Q$". I edited the question. So regarding representation - anything goes.  

---

## 1 answers

### Answer by username_4 on 2015-09-08. Score: 4

A model of computation allowing real numbers is the Real-RAM model. In this model, it is impossible to even decide if a number is rational. Indeed, the time-T halting sets are semialgebraic. If any one of them has a non-empty interior, then the time-T yes-set and time-T no-sets are semialgebraic subsets with no-empty interior, which is a contradiction. If none of the time-T halting sets is semialgebraic, then their union cannot be $\mathbb{R}$.

**Answer to the previous version of the question:**

If $a\_1,\dotsc,a\_k$ are algebraic numbers that are linearly independent over $\mathbb{Q}$, then $e^{a\_1},\dotsc,e^{a\_k}$ are algebraically independent over $\mathbb{Q}$. This is the [Lindemann–Weierstrass theorem](https://en.wikipedia.org/wiki/Lindemann%E2%80%93Weierstrass_theorem). So, if $a$'s are algebraic (as in the current version of the question), then the answer to your question is "yes".

> **Comments:**
> **username_0**: Right. The interesting case is when they are non algebraic, which is exactly the point of the question.  
> **username_4**: @username_0 What class of numbers you allow for the input then? You cannot allow all reals because there are uncountably many of them.  
> **username_0**: We could consider a model that allows real numbers, or indeed - choose some other representation of a subset of the reals. As I wrote - I'm trying to figure out if resolving Schanuel's conjecture would lead to a constructive solution.  
> **username_4**: @username_0 Sorry, but these details *do matter*, and are *non-trivial*. You really should explain yourself. It is impossible to answer an imprecise question.  
> **username_0**: I do not claim for a second that these details don't matter. Clearly they do. I don't have a suggestion for an encoding which would suggest that the problem is decidable or non-decidable, so I prefer to leave this open. I'll edit the question to clarify that.  
> **username_4**: @username_0 I updated my answer in response to your edit. Does it now answer your question?  
> **username_0**: Your answer is indeed correct, but it somehow circumvents the issue. I agree that the fault may be in the formulation of the question, but the main idea is: if there was a proof of Schanuel's conjecture, without knowing whether it's constructive or not, would you be able to turn it into a constructive argument? It seems that your answer suggests the answer is "no", but it's not entirely clear yet, since we would have to assume that the numbers are given as an input for a TM. Anyway, I upvoted, and if no other answers come up, I'll accept. Thanks.  

---

