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?

Improve this question
$\endgroup$
3
  • $\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 '12 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 '12 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$ – Quinn Culver Feb 5 '12 at 16:50
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm having considerable trouble figuring out what the question is here. $\endgroup$ – Robert Israel Feb 2 '12 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 '12 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.