 Page 1 of 1 [ 2 posts ]
 Print view Previous topic | Next topic
Exercise [16.04]
Author Message

Joined: 12 Jul 2010, 07:44
Posts: 154
This is actually really easy provided we prove a little lemma first.

Lemma:

What we want to show is that if a and b are unequal mod r, then so are xa and xb, where x is any number relatively prime to r (i.e. having no prime factors in common with r).

Simply set c = a-b (mod r). So c is one of 1,2,...,(r-1).

Then

xa = xb (mod r) <=> xc = kr for some k

Now consider the prime factorization of xc. Since c<r, it cannot contain all the prime factors of r (including multiplicities of the same factor in the count). But x is relatively prime to r, so it can't make up the difference: The LHS xc therefore does not contain the full set of factors of r, and so the LHS is not equal to the RHS. (except when c=k=0, i.e. when a=b (mod r)).

QED

How does this help us?

Well, note that "multiplying angular distance" is actually multiplication modulo r, where r = 1+q+q^2
(i.e. modulo one revolution around the disk).

In the text, a magic disk is defined by the intervals a0, a1, ..., aq. However, the problem calls for multiplication of angular distances from a fixed, marked point. So we need to re-express the marks on the magic disk in these terms. Define:

b0 = 0
b1 = a0
b2 = a0 + a1
b3 = a0 + a1 + a2
.
.
.
bq = a0 + ... + aq-1

Note that it doesn't matter which of the a's is chosen as a0, so long as cyclical order is preserved.

Then the cyclically successive sums of the a's are equal to, and map one-to-one onto the set:

{bi - bj (mod r): i, j in 0, ..., q & i not equal to j}.

This is just the set of angular distances between pairs of marks on the magic disk, clockwise from the ith to the jth.

Note that the "mod r" is there because if i<j (so bi<bj) we need to measure "the other way" around the circle, to get a value of r-(bj-bi).

This set excludes the empty sum (zero) and the complete sum (a0+a1+...+aq = r). However it should be obvious that whatever marks we make on a disk, we can always get these two values!

Now the defining characteristic of a magic disk is that this set equals {1, 2, ..., (r-1)}:
Every number from 1 to r-1 is a sum of some set of cyclically successive a's, or of some ordered pair of b's.

Suppose we pick any number x relatively prime to r.
Then if we multiply each of the b's by x, we also multiply each of the (bi-bj)'s by x (mod r).
But if we multiply each member of the set {1, 2, ..., (r-1)} by x (mod r), then by our lemma, no two multiplied elements can be equal, nor can they equal zero (since 0x = 0 (mod r))...
...and so the result must also be the set {1, 2, ..., (r-1)}, just with the elements rearranged.

Thus, angular multiplication of the b's of any magic disk of circumference r by any number x relatively prime to r will produce the b's of a new magic disk! (Or of course possibly the same one with the b's rotated).

Note that in the two cases Penrose asks us to do (q = 3,5), we have r = 13, 31: Both prime numbers. So in these cases "relatively prime" just degenerates to "not a multiple of r". Also, although we can pick the number x as large as we like, it's modulo arithmetic we're using here, so we may as well pick x < r; for higher values the results will just repeat themselves. And picking an x that is a multiple of r is the same as picking x=0, which is just stupid; that's probably why Penrose just says to pick "some fixed integer", leaving us to figure out that it oughtn't be a multiple of r.

19 Mar 2011, 08:51 Joined: 12 Jul 2010, 07:44
Posts: 154
Note that Laura has written up an explanation of magic disks to complement the rather inadequate explanation provided in the text.

Find it here:

http://camoo.freeshell.org/magic.circle.pdf

Also, there's a general discussion topic about them:  