François G. Dorais

Research in Logic and Foundations of Mathematics


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:

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:

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


CC0 Originally posted on by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.


Comments