2
$\begingroup$

Suppose I have a finite set $S$ of real numbers, and let $F(S)$ be the set of real numbers which can be obtained by applying additions and multiplications to elements of $S$ and their additive and multiplicative inverses.

If I am given a candidate real number $c$, is there an efficient way to decide whether $c \in F(S)$?

  • 0
    @Dilip: It wasn't initially clear how $F(S)$ was defined in the question. Originally it stated $F(S)$ was the field induced by adding $S$. As the question currently stands, I agree with you.2012-01-19

2 Answers 2

2

Generally, no, because to answer such questions would require answering difficult open problems in transcendental number theory. For example, take S to include well-known real transcendentals such as $\ e,\ \pi\ $ etc whose algebraic independence is unknown. While there are interesting conjectures (e.g. Schanuel's) on some classes of problems, most of these problems are intractable using current theory.

1

Even for $S=\{1\}$ it is hard because deciding whether $c \in F(S)$ is the same as deciding whether $c$ is rational. Try that for $c=\pi+e$ or $c=\zeta(5)$ or $c=\gamma$ or your favorite real number for which irrationality is open.

Moreover, deciding this depends what you mean by given a real number $c$. How is $c$ given?

  • 0
    @RobertIsrael, ah, so $F(S)=\mathbb Z[S\cup S^{-1}]$ ?2012-01-21