This week we find out a little bit about Directed Graphs, like the one below:  Directed Graphs (or digraphs) can be generated by repeatedly applying a function ("iterating"). In this tutorial, we will consider iterations of taking the square of a number, modulo n. Squares in Modular ArithmeticIs 932774127023565476743263463407213412072 a square number? No. How do we know? Because its last digit is a "2", and square numbers never end in a 2, 3, 7, or 8.How can we see this? The last digit of X is the remainder of X when divided by 10 ( X % 10 in Python). The last digit of X2 only depends on the last digit of X (can you see why?). Starting with the digits 0 to 9, we can compute the last digits of their squares:0 -> 0 1 -> 1 2 -> 4 3 -> 9 4 -> 16, whose last digit is 6 5 -> 25 => 5 6 -> 36 => 6 7 -> 49 => 9 8 -> 64 => 4 9 -> 81 => 1 Notice that the digits 2, 3, 7, and 8 are absent on the right hand side, whereas the digits 1, 4, 6 and 9 appear twice over. We can ask Python to compute this for us: [i**2 % 10 for i in range(10)]Here's a mathematical way of expressing this idea, using modular (clock) arithmetic, first discussed in Tutorial #5. The equation x2 ≡ a (mod 10) has solutions for x when a = 0, 1, 4, 5, 6, or 9, but not when a = 2, 3, 7, or 8. We say that 0, 1, 4, 5, 6 and 9 are quadratic residues (modulo 10), and 2, 3, 7 and 8 are quadratic non-residues. We can find the residues and non-residues using Python: n = 10residues = set([i**2 % n for i in range(n)])nonresidues = set(range(n)).difference(residues)print residues, nonresiduesExercise: Experiment with changing the base, n, in the code above. Try setting n to a prime number, p > 2. Can you deduce how the number of residues and non-residues depends on the prime p? Let's try squaring the digits repeatedly, modulo 10. We may iterate the mapping above, so 0 -> 0, 1 -> 1, 4 -> 6, 5 -> 5, 6 -> 6 and 9 -> 1. Now let's iterate once more, so we are left with 0, 1, 5 and 6. We could iterate again, but now this will not reduce the set of digits any further. We are left with those digits which map to themselves when squared, modulo 10. In the language of discrete dynamics, these are fixed points under squaring modulo 10. Here is a diagram of the way which digits map onto each other under the operation of squaring, modulo 10:  This diagram is called a Directed Graph, or DiGraph. Note that I have omitted the self-referential arrows on the fixed points 0, 1, 5, and 6, for clarity. There is nothing special about the number 10. We are familiar with arithmetic in "base ten" because of biological/evolutionary happenstance: homo sapiens has 10 fingers (including thumbs!) and 10 toes, and these "digits" are very convenient for counting. If we had 12 fingers, then most likely we our arithmetic system would be in "base 12", and we would have invented new symbols to represent the digits "10" and "11". In fact, some people have argued that working in base 12 would be much easier for everyone, as 12 divides by 2, 3, 4, and 6. The case for a duodecimal system was put forth at length in F. Emerson Andrews' 1935 book New Numbers: How Acceptance of a Duodecimal Base Would Simplify Mathematics. Now let's repeat the exercise above, but this time from the point of view of an alien species with a prime number of fingers, let's say, 11. Exercise: With pen and paper, try drawing the digraph generated by iterations of f(x) = x^2 (mod 11). Now scroll down to check your diagrams .... Exercise: Find the squares modulo 11 with a Python code, e.g.
Here's the digraph:
The digraph is much more interesting this time! 0 and 1 are still fixed points. But hopefully you can see that 9, 4, 5, and 3 form a cycle with four elements. That is, 9 maps to 4, 4 maps to 5, 5 maps to 3, and 3 maps back to 9, under squaring modulo 11. CyclesStarting from any node, and following the arrows on the graph, eventually leads us to a cycle or fixed point. Cycles are the kind of things that interest mathematicians. Why? Because they are there -- but unlike Everest, they can be easily explored without getting out of your chair. Python codeFind cycles in digraphs sounds like a perfect task for Python. You may wish to write your own code for finding cycles in the digraph generated by squaring modulo n. Or you may wish to try the following code snippet: n = 29sq = [k**2 % n for k in range(n)]loops = []for j in range(n): k = j seq = [k] while not sq[k] in seq: k = sq[k] seq.append(k) loop = seq[seq.index(sq[k]):] l = len(loop) i = loop.index(min(loop)) loops.append(tuple([loop[k % l] for k in range(i, l+i)]))print set(loops)ExercisesTry changing n, the modulus. Draw up a table of n, and the lengths of the cycles. Do you notice any obvious patterns? Here are some observations which you may wish to investigate further:
Graphs with PythonFinding the cycles helped us to understand some features of these digraphs, but it does not give a full picture. To visualize the digraphs, I wasted many hours drawing these graphs by hand:  Fortunately, there are Python packages for drawing graphs. Popular choices are networkx, igraph and python-graph. I used networkx to generate some graphs. The package seems easy to use, and most of the coding effort went into laying our the digraphs neatly, so their symmetry could be appreciated. GalleryHere are a selection of digraphs generated by iterations of x2 (mod n). Alternatively, check out this beautiful implementation in Clojurescript by Richard Hull.  n = 17 is an example of a Fermat prime: n = 2^(2k) + 1 For all Fermat primes, 0 is an isolated fixed point, and 1 is a fixed point connected to a complete binary tree of depth 2k.  n = 23 = 2 x 11 + 1 11 is an example of a Sophie Germain prime (as both 11 and 23 are prime). The associated network has a "large loop" if 2 is a cyclic generator modulo the SG prime.  n = 59 Another example of a Sophie Germain prime and a large loop.  n = 97 = 3 x 25 + 1 A Proth prime with a small number of cycles. n = 64 = 26  n = 125 = 53  ExtensionsHere are some slightly more challenging exercises for the interested reader:
|
Tutorials >
