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?

  • $\begingroup$ Neither is a polynomial; polynomials must have finite degree. I'd say it's a formal power series, except that the coefficients don't even converge... $\endgroup$
    – Charles
    Jan 31, 2012 at 15:38
  • $\begingroup$ @Charles, what if we we let $Q_n$ be a subset of $\mathbf{Q}$ containing the first $n$ terms and take the limit of $n$ in $P(Q_n)$? This would work for the rationals, but I don't think we can order the reals in the same way. $\endgroup$
    – Hooked
    Jan 31, 2012 at 15:49
  • $\begingroup$ 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. $\endgroup$ Feb 5, 2012 at 16:50

1 Answer 1


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.

  • $\begingroup$ I'm having considerable trouble figuring out what the question is here. $\endgroup$ Feb 2, 2012 at 19:29
  • $\begingroup$ @RobertIsrael: Indeed, that seems to be the main difficulty: finding some way to formalize the question. I took a stab at it... $\endgroup$
    – Charles
    Feb 2, 2012 at 20:46

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.