Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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... –  Charles Jan 31 '12 at 15:38
    
@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. –  Hooked Jan 31 '12 at 15:49
    
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. –  Quinn Culver Feb 5 '12 at 16:50
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
I'm having considerable trouble figuring out what the question is here. –  Robert Israel Feb 2 '12 at 19:29
    
@RobertIsrael: Indeed, that seems to be the main difficulty: finding some way to formalize the question. I took a stab at it... –  Charles Feb 2 '12 at 20:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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