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

  • 2
    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?2012-01-19
  • 0
    Dilip, yes thanks, I clarified the statement somewhat.2012-01-19
  • 0
    @Dilip: One definition for $F(S)$ is the smallest field containing $F$ and $S$, so it is automatically a field.2012-01-19
  • 1
    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$?2012-01-19
  • 0
    @BrandonCarter But that it is _not_ how $F(S)$ is defined in the question.2012-01-19
  • 0
    @Dilip, you are right, it is not a field... Modified the question again.2012-01-19
  • 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
    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.2012-01-19
  • 0
    @RobertIsrael, ah, so $F(S)=\mathbb Z[S\cup S^{-1}]$ ?2012-01-21