1
$\begingroup$

Consider a polynomial defined by its roots:

\begin{equation} P(z; \mathbf{S}) = \Pi_{\theta_j \in \mathbf{S}} (z - \exp({2 \pi i \theta_j}) ) \end{equation}

where $\mathbf{S}$ is a set of numbers. The roots to this polynomial are locations on the unit circle. Let's consider two sets: the set of all rationals $\mathbf{Q}$ and the set of all real numbers $\mathbf{R}$, each between zero and one. While $\mathbf{Q}$ is infinite but countable, $\mathbf{R}$ is not countable, so I'm not sure that this is even a valid polynomial. Nonetheless I was wondering about the following question:

Assume you had a computer program $C(n)$ that could converge to the nth root of this polynomial, but you're not sure if it is $P(\mathbf{Q})$ or $P(\mathbf{R})$. My guess is that you could perform a countably infinite number of computations to rule out or confirm $P(\mathbf{Q})$. Is there any finite computation that you could do to determine what the underlying set is?

  • 0
    This question is difficult to understand. I think you should clean it up. For example, how could a "program $C(n)$...converge to the $n$th root of this polynomial" if $\mathbf{S}=\mathbf{R}$? Since there would be uncountably many roots of this "polynomial" (which isn't really a polynomial, as @Charles pointed out), no program could recognize them all.2012-02-05

1 Answers 1

2

In response to a comment:

OK, so take two sequences of $n$ real numbers $Q_n$ and $R_n$ on the unit circle, the former containing only rationals and the latter containing at least one irrational. You can't take the limits of the two (what would that even mean?) but you could try to distinguish the two.

But that's easy to do in finite (but gigantic) time: list the rationals in some standard order, then take the first n = 1, 2, ... of them, then take all subsets of k = 1, 2, ..., n of them and see if either polynomial is equal to the appropriate product. Of course this assumes you can test equality, but if you can't then you can't even tell whether x - 1 has a rational root or not.

I guess the problem is going to have a lot to do with the particulars of what operations you allow and how the polynomials are presented.

  • 0
    @RobertIsrael: Indeed, that seems to be the ma$i$n difficulty: finding some w$a$y to formalize the question. I took a sta$b$ at it...2012-02-02