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

Improve this question
$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Dilip Sarwate Jan 19 '12 at 13:30
  • $\begingroup$ Dilip, yes thanks, I clarified the statement somewhat. $\endgroup$ – mitchus Jan 19 '12 at 14:06
  • $\begingroup$ @Dilip: One definition for $F(S)$ is the smallest field containing $F$ and $S$, so it is automatically a field. $\endgroup$ – Brandon Carter Jan 19 '12 at 14:29
  • 1
    $\begingroup$ 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$? $\endgroup$ – Dilip Sarwate Jan 19 '12 at 14:43
  • $\begingroup$ @BrandonCarter But that it is not how $F(S)$ is defined in the question. $\endgroup$ – Dilip Sarwate Jan 19 '12 at 14:46
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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?

Improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Jan 19 '12 at 20:15
  • $\begingroup$ @RobertIsrael, ah, so $F(S)=\mathbb Z[S\cup S^{-1}]$ ? $\endgroup$ – lhf Jan 21 '12 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.