# Efficient method for testing membership

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)$?

-
How is $F(S)$ a field since it might not contain the additive identity or multiplicative identity (unless you say the empty sum and empty product are providing these) nor does it necessarily contain additive and multiplicative inverses? – Dilip Sarwate Jan 19 '12 at 13:30
Dilip, yes thanks, I clarified the statement somewhat. – mitchus Jan 19 '12 at 14:06
@Dilip: One definition for $F(S)$ is the smallest field containing $F$ and $S$, so it is automatically a field. – Brandon Carter Jan 19 '12 at 14:29
Suppose $S = \{1, 2\}$ and so $F(S)$ includes elements such as $1+2 = 3$,$2 \times 2 = 4$, $2^{-1} = \frac{1}{2}$, etc. that are not in $S$. What is the multiplicative inverse of $3 \in F(S)$, and how can it be obtained by applying additions and multiplications to elements of $\{1,2,-1,-2,\frac{1}{2}\}$ which is precisely the set $S$ together with additive and multiplicative inverses of elements of $S$? – Dilip Sarwate Jan 19 '12 at 14:43
@BrandonCarter But that it is not how $F(S)$ is defined in the question. – Dilip Sarwate Jan 19 '12 at 14:46

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.
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?
In the current state of the question, for $S = \{1\}$, $F(S) = \mathbb Z$, not $\mathbb Q$. Deciding whether a real number $c$ is an integer may still be hard, depending on how $c$ is given. For example, let $c = \sum_{n=1}^\infty a_n 2^{-n}$ where $a_n = 0$ if $2n$ is the sum of two primes and $1$ otherwise. – Robert Israel Jan 19 '12 at 20:15
@RobertIsrael, ah, so $F(S)=\mathbb Z[S\cup S^{-1}]$ ? – lhf Jan 21 '12 at 12:58