On computing complex square roots
What could possibly be interesting about complex square roots? That’s what I thought until very recently when I realized that complex square roots are significantly more difficult to compute than real square roots. Let me explain why by putting you in a context where you need to teach students how to compute complex square roots…
There is not much to computing complex square roots; it just takes a little practice to get used to it. So you just need to assign a few homework problems to make sure that students practice enough. How many problems should you assign: one, two, five, twelve, or seventeen? There is no upper bound on how many practice problems are enough, so perhaps you should assign infinitely many problems?
Now, you may find the very idea of an infinite problem set objectionable, but they are in fact very common. Here is one:
For every positive integer , find a square root of .
Some might find the following problem infinite too:
Find a square root of .
Here, is a finite description of a complex number, the complex number being described is actually an infinite object. Hopefully this is enough to convince you that infinite problem sets are not completely unreasonable. Of course, you do need to set some ground rules so that students can at least understand the what the problem set is asking and that they know what a solution entails. Here are the rules:
- Real numbers are represented by rapidly convergent sequences of rational numbers. That is, a real number is a function such that for all natural numbers .
- Complex numbers are pairs , where and are real numbers represented by rapidly convergent sequences of rational numbers. The real and imaginary parts of will also be denoted and when convenient.
- An infinite problem set is an uniformly computable sequence of complex numbers. That is, there is a Turing machine which, on input , will give me the rational numbers and , where as above.
- A solution to the infinite problem set is an uniformly computable sequence of complex numbers such that for each .
Grading such a problem set can be a daunting task, but let’s not worry about the aftermath. A more interesting question is:
Does every infinite problem set have a solution?
Indeed, it would be unreasonable to assign a problem set that students can’t possibly solve!
If the problem set were specifically asking for the principal square roots then you could easily devise an infinite problem set that has no solution. Recall that the principal square root of is where and is the nonnegative square root of the nonnegative real number . In other words, the principal branch agrees with the positive square root on the positive real axis, and it has a branch cut along the negative real axis.
Theorem D. Given any computably enumerable set , there is a uniformly computable sequence of nonzero complex numbers such that the corresponding sequence of principal square roots computes .
Proof. Let’s assume that is infinite and let be a computable enumeration of , without repetitions. Define the sequence by
To see that this is uniformly computable, recall that where and are two rapidly convergent sequences of rationals. The first sequence is constant with value , which is definitely computable. The second sequence can be defined by
Because we require , we only have finitely many possible to check in order to determine which case to use. So is computable too. Since this process is uniform in , the sequence is in fact uniformly computable.
Now suppose is the corresponding sequence of principal square roots. Then we must have when , and when . So we can use the sign of to determine whether or not is in the range of . More precisely, if then we can look at the terms of the rapidly convergent sequence until we find such that ; such an will eventually be found since we know that . Then the sign of will tell us whether or not. Therefore, is computable from . QED
Choosing to be the halting set will trick many students, but solutions to infinite problem sets do not require principal square roots. Some students might use a slightly different convention and define the principal square root of to be instead of . In that case, the above trick doesn’t work since such a student will give me a sequence of square roots where for every . However, it turns out that you can design an infinite problem set that will simultaneously deal with all such variations. Let us say that is a weakly principal square root of if is the principal square root, or is a negative real number in which case can be any of the two square roots.
Theorem C. For every pair , of disjoint computably enumerable sets, there is a uniformly computable sequence of nonzero complex numbers such that any corresponding sequence of weakly principal square roots computes a separating set for and .
Proof. Let and be computable enumerations of and , respectively. Similar to the proof of Theorem A, define
Suppose we have a corresponding sequence of weakly principal square roots. It must be that (in fact, ) when , and (in fact, ) when . We could have when , but we still know that . We can still use the sign of to separate and since
and the two supersets are complementary sets. QED
Choosing and to be an inseparable pair of computably enumerable sets, many of your students will be unable to solve this problem set. That is, you will trick all your students who don’t realize that the choice of branch cut for square roots is completely arbitrary. Any student that chooses the branch cut at an angle of instead of will have no trouble solving this infinite problem set.
It is not difficult to adapt the above to simultaneously deal with a bunch of plausible branch cuts However, you can’t deal with all possible branch cuts. While there are only countably many computable branch cuts that students could choose from, but there is no computable enumeration of all of these choices. In fact, a clever student can always pick a branch cut that you haven’t considered.
Theorem B. If is a uniformly computable sequence of nonzero complex numbers, then there is a corresponding uniformly computable sequence such that for every .
Proof. The trick is to select a branch cut angle that avoids all the numbers . This can be done by a trisection argument. Initially set and , say. Once have been chosen, set and compute to enough precision that you can determine that does not belong to one of the three sets
In the first case set ; in the second case set ; in the third case set .
This process defines two rapidly convergent sequences of rational numbers that represent the same real number . The branch angle so defined is computable and avoids all the numbers . So there is no problem computing the principal square roots of the numbers . The solution to the infinite problem set is then . QED
Now the fact that the complex numbers were nonzero was very important in this argument. A student using this strategy will stall at any stage where . However, some very clever students will anticipate this possibility and avoid this problem.
Theorem A. If is a uniformly computable sequence of complex numbers, then there is a corresponding uniformly computable sequence such that for every .
Proof. Although there may be no computable way to determine which are zero, the set is computably enumerable since is a statement. For simplicity, let’s assume that this set is infinite and let be a computable enumeration of this set (without repetitions). We can then use the method from Theorem B to compute a sequence of square roots for the subsequence . The desired sequence of square roots is then
To see that the sequence is uniformly computable, recall that where and are rapidly convergent sequences of rational numbers. So we can define where
These will be a rapidly convergent sequences of rationals provided that the computable function is suitably chosen.
To define we need to make sure that the first time where , we don’t have or . Should this happen, we necessarily have . So we can look at . Since , if then and we’re safe to define . Otherwise, we know that so that for some . Therefore, we can define when , and such that when . QED
So every infinite problem set does have a solution! Moreover, any student that reaches the solution of Theorem A clearly understands complex square roots (and basic computability theory!), so infinite problem sets might not be such a bad idea after all…
So what does this have to do with reverse mathematics? Well, the four theorems above can be used to show that:
- It is provable in that every infinite sequence of complex numbers has a corresponding sequence of complex square roots.
- It is not provable in that every infinite sequence of complex numbers has a corresponding sequence of principal square roots. In fact, this statement is equivalent to -comprehension (i.e. ).
- It is also not provable in that every infinite sequence of complex numbers has a corresponding sequence of weakly principal square roots. In fact, this statement is equivalent to -separation (i.e. ).
In fact, there is nothing very special about square roots. The same applies to the inverse of any nonlinear polynomial over . Therefore, you must be very careful when using the Fundamental Theorem of Algebra in …
Peter Krautzberger wrote
When I caught up on last week’s Booles’ Rings activity, I read this and wanted to write something – but couldn’t quite formulate, why I like this post. I didn’t want to just leave a spammish “Great post!” comment and just now realized what’s so great about your post: it’s a perfect example for the range of content I hoped for when Sam and I started to think about this project.
Thank you, François!
Thanks Peter! This is an unusual post because the results are kind of interesting but not enough to publish, so Booles’ Rings is just the right place!
(The result of Theorem A did get a mention in my paper Classical consequences of continuous choice principles from intuitionistic analysis.)