5
$\begingroup$

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 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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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) $\endgroup$
    – boumol
    Commented Sep 6, 2015 at 10:38
  • $\begingroup$ 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$. $\endgroup$
    – Shaull
    Commented Sep 6, 2015 at 11:56
  • 2
    $\begingroup$ 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? $\endgroup$
    – Nikhil
    Commented Sep 7, 2015 at 15:04
  • $\begingroup$ @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) $\endgroup$
    – Shaull
    Commented Sep 7, 2015 at 15:12
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Holden Lee
    Commented Sep 7, 2015 at 22:41

1 Answer 1

Reset to default
4
$\begingroup$

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. So, if $a$'s are algebraic (as in the current version of the question), then the answer to your question is "yes".

Improve this answer
$\endgroup$
7
  • $\begingroup$ Right. The interesting case is when they are non algebraic, which is exactly the point of the question. $\endgroup$
    – Shaull
    Commented Sep 8, 2015 at 17:26
  • $\begingroup$ @Shaull What class of numbers you allow for the input then? You cannot allow all reals because there are uncountably many of them. $\endgroup$
    – Boris Bukh
    Commented Sep 8, 2015 at 17:48
  • $\begingroup$ 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. $\endgroup$
    – Shaull
    Commented Sep 8, 2015 at 18:13
  • 2
    $\begingroup$ @Shaull Sorry, but these details do matter, and are non-trivial. You really should explain yourself. It is impossible to answer an imprecise question. $\endgroup$
    – Boris Bukh
    Commented Sep 8, 2015 at 18:14
  • $\begingroup$ 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. $\endgroup$
    – Shaull
    Commented Sep 8, 2015 at 18:20

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.