Much of the discussion in this part is covered in other sections. This page is an effort to consolidate those pieces into a more mathematically concise package rather than the rambling prose that I am more prone to. Much of the terminology is in standard use for bitwise operations or matrix math. When I introduce new terms of my own, I will try to emphasize them with sufficient definition.
In general, the variable m will be used only to designate the order of a magic figure and the variable n will be used to designate the number of dimensions of the figure. The value 2^{p} is equal to m but is used to emphasize that the only values of m being considered are powers of 2.
The discussion below can be generalized to powers of 3, etc., but it is easier to follow without that generalization. A brief discussion of that further generalization will be given at the end of this section. The definitions for terms are often written in broader scope than they are used in the subsequent discussion. The narrower scope provides a basis for some of the proofs. Statements based on the proofs may apply to some other members in the broader scope as well but without a solid proof.
Definition: A base line unit is a bit pattern of length 2^{q} where q>=1 and bits spaced 2^{q}/2 apart are inverses where inversion means 0 = 1 and 1 = 0.
a_{0} = 01 | b_{0} = 0011 | c_{0} = 00001111 |
a_{1} = 10 | b_{1} = 0110 | c_{1} = 00011110 |
b_{2} = 1001 | c_{2} = 00101101 | |
b_{3} = 1100 | c_{5} = 01011010 |
The base line unit can be represented with an alphanumeric code where the alpha part, in lower case, is related to its length (for a, q=1; b, q=2; etc.).
The numeric part is a number from 0 to (2^{(2(q-1))}-1). The first 2^{q}/2 bits (most significant bits) of the base line unit are the binary equivalent of the numeric part of the alphanumeric code, with leading 0's. The other 2^{q}/2 bits (least significant bits) of the base line unit are the inverses of the most significant bits. If numbers are moved from one end of the base line unit to the opposite end a new base line unit is created with the same properties as above but with a different numeric part of the code. In the examples the two a codes and four b codes are generated in this way. This is the basis for the wraparound property of pan-magic figures. There are two different types of c base line units in the examples. One type is represented by c_{0} and c_{1} and the other by c_{2} and c_{5}. The two types cannot be interchanged using the wraparound property. A total of 16 c base line units can be generated, 8 of each type.
Definition: A base line for a magic figure of order-2^{p} is composed of 2^{(p-q)} identical base line units where p ≥ q.
By convention an uppercase letter in the alphanumeric code will signify that it is a base line while lower case indicates a base line unit. They may be the same. For instance, the B_{0} base line for an order-4 square is the same as the b_{0} base line unit above whereas the B_{0} base line for an order-8 cube is 00110011.
Definition: A set of integers from 0 to s has uniform integral distribution if every integer from 0 to s appears an equal number of times within the set.
By the above definition, all base line units and base lines have uniform integral distribution because they all have equal numbers of 0's and 1's.
2^{1} x B_{0} | 0 | 0 | 2 | 2 | 0 | 0 | 2 | 2 |
2^{0} x B_{1} | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
sum | 0 | 1 | 3 | 2 | 0 | 1 | 3 | 2 |
Definition: Compatible base lines are a set of t base lines that have the same base line unit length and can be combined in one dimension such that the combination, 2^{(t-1)}L_{(t-1)} + 2^{(t-2)}L_{(t-2)} + … + 2^{1}L_{1} + 2^{0}L_{0} = t-1∑i=02^{i}L_{i}, has uniform integral distribution.
Definition: A compatible base line set is a group of p compatible base lines of length 2^{p} that contains all the numbers from 0 to 2^{p}-1.
Combining 2^{3}(D_{0}) + 2^{2}(D_{15}) + 2^{1}(D_{51}) + 2^{0}(D_{85}) gives the sequence 0, 1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, and 8. Thus D_{0}, D_{15}, D_{51}, and D_{85} are a compatible base line set for p = 4.
Definition: A base square, M, is a 2^{p}x2^{p} bit pattern composed of equal numbers of 0's and 1's where p ≥ 2.
Two base lines of the same length but with different base line unit lengths, x and y, can be combined to make a base square, xy, with m_{ij} = x_{i} ⊕ x_{j} where ⊕ is the exclusive OR function. Only base squares of this type will be considered in the following discussion. Since every base line by definition has equal amounts of 0's and 1's, the sum of every row or column of the base square is 2^{p}/2. If the base line units of the two base lines are different lengths then every diagonal and broken diagonal of the base square adds to 2^{p}/2. Proof of the latter follows:
B_{0} | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
---|---|---|---|---|---|---|---|---|---|
A_{0} | |||||||||
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
If the base line units of the two base lines of a base square are the same then some diagonals and/or broken diagonals of the base square will not add to 2^{p}/2.
Magic squares of order-2^{p} can be created by combining base squares. Two base squares of the same order may be combined by multiplying one base square by 2 and adding the second: 2^{1}M_{1} + 2^{0}M_{0} = 1∑i=02^{i}M_{i}. Both the multiplication and addition follow the normal rules of matrix math. Another way to look at 1∑i=02^{i}M_{i} is to consider it a three dimensional matrix of 0's and 1's where each position in the original square contains two bits going in the third direction, the pillars. Putting the bits in the pillars together as binary numbers gives the numbers in the intermediate square.
Since both base squares in 1∑i=02^{i}M_{i} have the same addition properties, the resulting composite matrix will also have those properties, i.e. the sum of every row, column, diagonal, and broken diagonal adds to the same sum, 3(2^{p}). The resulting composite matrix may or may not have uniform integral distribution of the numbers 0-3. If the two base squares are the same then the resulting composite will have equal numbers of 0's and 3's but no 1's or 2's. Other combinations will have equal numbers of 0's and 3's but a different number of 1's and 2's. Most combinations of two base squares, however, will have uniform integral distribution.
Composites of t base squares can be constructed using the formula: t-1∑i=02^{i}M_{i} where t ≤ 2p. As each additional base square is added, composites with uniform integral distribution become rarer. If t = 2p and t-1∑i=02^{i}M_{i} has uniform integral distribution then the figure is a pan-magic square of order-2^{p}.
As each base square is added to the composite it is important to maintain uniform integral distribution. If u∑i=02^{i}M_{i} does not have uniform integral distribution then t-1∑i=02^{i}M_{i} will not have uniform integral distribution, where u is any intermediate value less than (t-1). A proof follows:
A magic square is composed of 2p base squares each of which has a different power of 2 multiplier from 0 to (2p-1). These 2p base squares can be arranged in any order relative to the multipliers to give (2p)! different magic cubes.
Definition: Master base lines for magic figures made from base lines are the lines parallel to each axis that pass through the 0.
A magic square created by the process described in the preceding sections has a 0 at some position, t-1∑i=02^{x}(m_{i})_{gh}. Call the lines passing through 2^{u}(m_{u})_{gh} x and y. Then the base lines for 2^{u}M_{u} are either x and y or x and y. Both results are valid because both sets of base lines will generate the same base square. A composite of the x's and y's for all the base squares can be constructed. When these linear composites, t-1∑i=02^{i}X_{i} and t-1∑i=02^{i}Y_{i} are constructed of only the x's and y's and not their inverses, they are identical to the row and column that pass through the zero of the magic square. These are the squares master base lines.
The master base lines therefore contain all the information necessary to construct the magic square because they are composites of base lines that can be used to generate the magic square.
Definition: A magic line square is a 2^{p}x2^{p} magic square containing all the integers from 0 to (2^{p})^{2}-1 where p ≥ 2. They are constructible from master base lines. These magic squares will have the property that every row, column, diagonal, and broken diagonal adds to the same magic constant. The magic line squares are thus pan-magic squares of order-2^{p}.
The three requirements for magic line squares are that they have all the addition properties desired, they contain all of the numbers from 0 to (2^{p})^{2}-1, and they are constructible from base lines. It is possible with the procedure described above to create magic squares of any order-2^{p}. The larger the square, the more difficult it becomes to find a set of base figures that can be combined to give uniform integral distribution at each step of the construction but all combinations will have the correct addition properties. Using a structured base line pattern, it is possible to create very large magic squares that have both the correct addition pattern and uniform integral distribution without the necessity of any other check of the square.
Construction of the structured squares requires the use of compatible base line sets. There are many compatible base line sets for the larger values of p. The set of P type alphanumeric codes with subscripts 0, (2^{(2(p-2))}-1), (2^{(2(p-2))}+1)(2^{(2(p-3))}-1), (2^{(2(p-2))}+1)(2^{(2(p-3))}+1)(2^{(2(p-4))}-1), (2^{(2(p-2))}+1)(2^{(2(p-3))}+1)(2^{(2(p-4))}+1)(2^{(2(p-5))}-1), …, (2^{(2(p-2))}+1)(2^{(2(p-3))}+1)…(2^{(21)}+1)(2^{(20)}-1) are a structured example.
multiplier | row | column |
128 | D_{0} | |
64 | D_{15} | |
32 | D_{51} | |
16 | D_{85} | |
8 | D_{0} | |
4 | D_{15} | |
2 | D_{51} | |
1 | D_{85} |
The example at right illustrates a square that has uniform integral distribution. Only the D alphanumeric codes with their multipliers are given for the eight base squares. The sets of D codes in the row and in the column are compatible base line sets made using the formula above. The base squares in each row of the table can be constructed from the base lines given by assuming that the codes left blank are all zero. Using a similar approach, squares of order-2^{p} can be created with uniform integral distribution for any value of p.
The base lines of the structured square can be split into four parts. The p least significant bits contain a compatible base line set and a blank section. These are the g and h components of p-1∑i=02^{i}(m_{i})_{gh} respectively. In this blank section, the h's are always 0. The other two parts are the p most significant bits' blank section and compatible base line set. These are the g and h components of 2p-1∑i=p2^{i}(m_{i})_{gh} respectively. In this blank section, the g's are always 0.
The bits in the second half of each of the base lines in the construct above are inverses of the first half since the base line units lengths are the same as the base lines lengths. The square requires a cross base line to complete each base square in the construct. The second half of the cross base lines must always be the same as the first half to make a valid base square.
Definition: A shuffling matrix, np-1∑i=02^{i}S_{i}, is a group of 2^{n} numbers in an n-dimensional magic figure, np-1∑i=02^{i}M_{i}. The numbers are located at np-1∑i=02^{i}(m_{i})_{gh…z} where g is either g or ((g + 2^{p}/2) (mod 2^{p})), h is either h or ((h + 2^{p}/2) (mod 2^{p})), etc. Call these positions g and g', h and h', etc. np-1∑i=02^{i}S_{i} can be viewed as the corners of an n-dimensional hypercube within np-1∑i=02^{i}M_{i} with sides of length 2^{p}/2.
There are four numbers in the shuffling matrix of a square, 2p-1∑i=02^{i}(s_{i})_{gh}, 2p-1∑i=02^{i}(s_{i})_{gh'}, 2p-1∑i=02^{i}(s_{i})_{g'h}, and 2p-1∑i=02^{i}(s_{i})_{g'h'}. Call these numbers w, x, y, and z respectively. Each of these numbers can be further split into their p most significant bits and p least significant bits. Call these parts w' and w", x' and x", etc. The shuffling matrix then becomes w' + w", x' + x", y' + y", and z' + z". For the most significant bits w' = y', x' = z', w' = x', and y' = z' and for the least significant bits w" = x", y" = z", w" = y", and x" = z". This is the shuffling matrix rule. Simplifying, let l = w" = x", l = y" = z", m = w' = y', and m = x' = z'. The numbers in the shuffling matrix then become m + l, m + l, m + l, and m + l with m and l representing the most significant and least significant bits respectively.
As an example a shuffling matrix for the square defined above consists of the numbers at (row, column) coordinates (1,6), (9,6), (1,14), and (9,14). The respective binary numbers at these positions are 01100001, 01101110, 10010001, and 10011110. The two halves of each binary number are the two parts, m and l, described above where m = 0110, m = 1001, l = 0001, and l = 1110. There are 64 unique shuffling matrices, (2^{(p-1)})^{2}, within the order-16 square and they all conform to this rule.
multiplier | row | column |
128 | A_{0} | D_{0} |
64 | A_{0} | D_{15} |
32 | A_{0} | D_{51} |
16 | A_{0} | D_{85} |
8 | D_{0} | A_{0} |
4 | D_{15} | A_{0} |
2 | D_{51} | A_{0} |
1 | D_{85} | A_{0} |
The square with uniform integral distribution created above only contains half of the required alphanumeric codes. Since the base lines in the compatible base line sets are all base line units, the remaining base lines must have shorter base line unit lengths. Thus, both halves of the remaining base lines are identical. Placing any of the base lines with shorter base line units in all of the open positions will create a magic square. In the example at right, the A_{0} base line was used but any of the B or C base lines could have been used. Different base lines could also be used for the most significant bit part and the least significant bit part as long as the same base line was used for all of the base squares in that part.
position | g=0 and h=0 | g=1 and h=0 | g=0 and h=1 | g=1 and h=1 |
^{(2p-1),…,0}s_{gh} | m + l | m + l | m + l | m + l |
^{(2p-1),…,0}s_{gh'} | m + l | m + l | m + l | m + l |
^{(2p-1),…,0}s_{g'h} | m + l | m + l | m + l | m + l |
^{(2p-1),…,0}s_{g'h'} | m + l | m + l | m + l | m + l |
Base figures and magic figures of any dimension can be made by simple extensions of the concepts described above for squares.
Definition: A base figure of n-dimensions is a bit pattern composed of equal numbers of 0's and 1's. The figure will have n axes of length 2^{p} where p ≥ n. For this discussion the base figure has the property that every agonal and every pan-s-agonal sums to 2^{p}/2 where 2 ≤ s ≤ n.
The n-dimensional base figures can be made by combining n base lines using the ⊕ function. They are n-dimensional matrices, M, that are subject to the same manipulations as the square matrices. For multiple values the ⊕ function has the effect that a set of numbers with an odd number of 1's = 1 and with an even number of 1's = 0. This is equivalent to (mod 2) of the addition sum.
Since every agonal of the figure is a base line or its inverse, every agonal will add to 2^{p}/2. To make a valid base figure every dimension must have a base line with a different base line unit length.
Higher order s-agonals also add to 2^{p}/2 by a similar argument to that for base squares above. For this proof, it is assumed that all base lines have different base line unit lengths based on the proof immediately above.
Magic figures of n-dimensions can be made by combining base figures of the same dimensions. The process is the same as that described above for squares. Construction will require the successful combination of np base figures. The addition properties of the intermediate figures will be correct if the addition properties for all the base figures are correct even if the composite does not have even integral distribution. The addition properties of the base figures will be correct if they are made as described above. At each step of the construction, the intermediate must have uniform integral distribution. Proof of the uniform integral distribution requirement is a trivial extension of that for squares. All agonals and s-agonals of the intermediates will add to (2^{p}/2)(2^{h}-1) where h is the number of base figures in the intermediate and (2^{p}/2) is 1/2 the order of the figure.
The validity of shuffling the order of the multipliers of the base figures of n-dimensional base figures is an obvious extension of the proof for squares.
The resulting magic figures can be called magic line figures because the lines parallel to each axis that pass through the 0 are master base lines. That is those lines contain all the information necessary to construct the entire magic figure.
Definition: A magic line figure is an n-dimensional magic figure of order-2^{p} containing all the integers from 0 to (2^{p})^{n}-1 where p ≥ n. They can be constructed from master base lines. These magic figures have the property that all agonals and all s-agonals add to the same magic constant, (2^{p}/2)(2^{pn}-1), where 2 ≤ s ≤ n. The magic line figures are pan-2,3,…,n-magic figures of order-2^{p}.
The three requirements for magic line figures are that they have all the addition properties desired, they contain all of the numbers from 0 to (2^{p})^{n}-1, and they can be constructed from master base lines. It is possible to build an n-dimensional magic figure of any 2^{p} order using a structured base line pattern. Using compatible base lines sets and the structured pattern no check of addition properties or uniform integral distribution is needed. There are many possible compatible base line sets for larger values of p. One example for any p is given above. Proof is an extension of the proof for large squares but some elaboration follows.
A structured n-dimensional figure similar to the square example above can be constructed for any order-2^{p} where p≥n. There will be np base figures in the construct each with a different multiplier from 2^{0} to 2^{(np-1)}. There must be n compatible base lines sets containing p members each. The sets may be identical. Each of the n dimensions will contain all the members of one of the compatible base line sets and each base figure will contain only one base line in this initial construction.
It is easier to visualize and to prove the construction when the compatible base line sets in each dimension have consecutive multipliers. This will be the approach used below but the concept is more general. An n-dimensional figure of order-2p contains a compatible base line set in the p least significant bits of one of its dimensions. In the next higher p significant bits will be the same or a different compatible base line set in a second dimension. etc., with the n^{th} dimension getting a compatible base line set in its p most significant bits. The resulting construct will have uniform integral distribution.
The bits in the second half of each of the base lines in the construct above are inverses of the first half since the base line units lengths are the same as the base lines lengths. The figure requires n-1 additional base line to complete each base figure in the construct. The second half of each of these base lines must always be the same as the first half and each must have a different base line unit length in order to make a valid base square.
There are 2^{n} numbers in the shuffling matrix of a figure at 2p-1∑i=02^{i}(s_{i})_{abc…n} where a can be at position a or ((a+(2^{p})/2) (mod 2^{p})), b independently at b or ((b+(2^{p})/2) (mod 2^{p})), etc. Call these positions a and a', b and b', etc. For the figure with uniform integral distribution defined above 2p-1∑i=02^{i}(s_{i})_{abc…n} can be split into n groups of p consecutive bits, G_{e} where 1 ≤ e ≤ n. Each group can be further split into the compatible base line set in one dimension and (n-1)p 0's. These 0's correspond to the missing base lines. The parts of the groups can be designated C_{e} and R_{e} for the compatible base line set and repeating base lines parts respectively. The e's are numbered from least significant bit groups to most significant bit groups.
The figure with uniform integral distribution created above only contains one compatible base line set in each group of base figures, C_{e}. Since the base lines in the compatible base line sets are all base line units, the remaining base lines must have shorter base line unit lengths. Thus, both halves of the remaining base lines that will be placed in R_{e} are identical. For each base figure, the remaining base lines must also have different base line unit lengths as proven above. A valid magic line figure can be made by placing duplicate base lines of different base line unit lengths in each of the n-1 dimensions of each R_{e}'s groups base figures.
The above approach can be generalized to allow the compatible base line sets to be non consecutive in each dimension. The validity of this is most easily seen by generating a magic line figure as above and then shuffling the order of the base figures.
As stated earlier the proof above is not restricted to binary figures. It can be generalized to ternary, quinary, and higher. Some of the definitions need to be modified to accommodate the ternary, etc. bases. Many definitions only require the simple change from base 2 to base o where o is any base. Others require more extensive adjustments. In general, the proofs can be easily extended and are not discussed below. The proofs are applicable to figures of order-o^{(p)} where p ≥ n. They do not apply to figures of order-o where o is prime.
Definition: A base line unit is a linear digit pattern of length o^{q} where q ≥ 1 and o ≥ 2. The base line has o contiguous parts with o^{(q-1)} digits in each part. Digits at the same positions within the o parts must all be different and in the range 0 to o-1.
The sequence 001220112 is a valid ternary base line unit of length 3^{2}. Digits at the same positions in the three parts are 0, 2, 1 and 0, 2, 1 and 1, 0, 2 respectively. The sequence 001221112 is not valid because the third digits of the three parts are 1, 1, 2 repeating a digit at that position.
Definition: A base line for a magic figure of order-o^{p} is composed of o^{(p-q)} identical base line units where p ≥ q.
Definition: A compatible base line set is a group of p compatible base lines of length o^{p} that contains all the numbers from 0 to o^{p}-1.
Definition: A base square, M, is an o^{p}xo^{p} bit pattern, where p ≥ 2 when o ≤ 4 and p ≥ 1 when o ≥ 5 and odd. M is composed of equal numbers of all digits from 0 to o-1.
Two base lines of the same length but with different base line unit lengths, x and y, can be combined to make a base square, xy, with m_{ij} = (i + j) (mod o). Since every base line by definition has even integral distribution, the sum of every row or column of the base square is o^{p}(o-1)/2. If the base line units of the two base lines are different lengths then every diagonal and broken diagonal of the base square also adds to o^{p}(o-1)/2. Proof of the general case is similar to that for the binary:
Magic squares of order-o^{p} can be created by combining base squares. Two base squares of the same order may be combined by multiplying one base square by o and adding the second: o^{1}M_{1} + o^{0}M_{0} = 1∑i=0o^{i}M_{i}. Both the multiplication and addition follow the normal rules of matrix math. Construction will require the successful combination of np base figures.
It is more difficult to combine multiple ternary or larger base squares than the binary. However, a set of properly structured base lines will always yield a valid magic line figure of any order-o^{p}. The construction proceeds as described above. An n-dimensional figure of order-o^{p} will contain n compatible base line sets with p members. Many compatible base lines sets are possible with larger figures. One set is described below.
There are n compatible base line sets placed in the n dimensions of the magic figure as described above. For simplification, each set occupies a group of base figures with consecutive power of o multipliers.
Definition: A shuffling matrix, np-1∑i=02^{i}S_{i}, is a group of o^{n} numbers in an n-dimensional magic figure, np-1∑i=02^{i}M_{i}. The numbers are located at np-1∑i=02^{i}(m_{i})_{gh…z} where g is ((g + ro^{(p-1)}) (mod o^{p})), h is ((h + so^{(p-1)}) (mod o^{p})), etc. The multipliers, r and s etc. range from 0 to o-1. The shuffling matrix is a grid of numbers within the magic figure separated by o along all dimensional axes.
The figure with uniform integral distribution created above only contains one compatible base line set in each group of base figures, C_{e}. Since the base lines in the compatible base line sets are all base line units, the remaining base lines must have shorter base line unit lengths. Thus, the remaining base lines that will be placed in R_{e} repeat every o digits. For each base figure, the remaining base lines must also have different base line unit lengths. A valid magic line figure can be made by placing duplicate base lines of different base line unit lengths in each of the n-1 dimensions of each R_{e}'s groups base figures.