# PROOF OF BASE LINE METHOD OF CREATING MAGIC FIGURES

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 2p 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.

## BASE LINES

Definition: A base line unit is a bit pattern of length 2q where q>=1 and bits spaced 2q/2 apart are inverses where inversion means 0 = 1 and 1 = 0.

 a0 = 01 b0 = 0011 c0 = 00001111 a1 = 10 b1 = 0110 c1 = 00011110 b2 = 1001 c2 = 00101101 b3 = 1100 c5 = 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 2q/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 2q/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 c0 and c1 and the other by c2 and c5. 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-2p 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 B0 base line for an order-4 square is the same as the b0 base line unit above whereas the B0 base line for an order-8 cube is 00110011.

## COMPATIBLE BASE LINES

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.

 21 x B0 0 0 2 2 0 0 2 2 20 x B1 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) + … + 21L1 + 20L0 = t-1i=02iLi, has uniform integral distribution.

Definition: A compatible base line set is a group of p compatible base lines of length 2p that contains all the numbers from 0 to 2p-1.

Combining 23(D0) + 22(D15) + 21(D51) + 20(D85) gives the sequence 0, 1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, and 8. Thus D0, D15, D51, and D85 are a compatible base line set for p = 4.

## BASE SQUARES

Definition: A base square, M, is a 2px2p 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 mij = xi ⊕ xj 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 2p/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 2p/2. Proof of the latter follows:

 B0 A0 0 1 1 0 0 1 1 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
##### Thus, if the length of the base line units of the two base lines are different then every diagonal and broken diagonal of the base square they generate adds to 2p/2.

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 2p/2.

## COMBINING BASE SQUARES

Magic squares of order-2p 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: 21M1 + 20M0 = 1i=02iMi. Both the multiplication and addition follow the normal rules of matrix math. Another way to look at 1i=02iMi 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 1i=02iMi 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(2p). 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-1i=02iMi where t ≤ 2p. As each additional base square is added, composites with uniform integral distribution become rarer. If t = 2p and t-1i=02iMi has uniform integral distribution then the figure is a pan-magic square of order-2p.

As each base square is added to the composite it is important to maintain uniform integral distribution. If ui=02iMi does not have uniform integral distribution then t-1i=02iMi will not have uniform integral distribution, where u is any intermediate value less than (t-1). A proof follows:

## SHUFFLING BASE SQUARES

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.

##### Select one of those groups of four numbers and call their initial values a, b, c, and d where a is the number that did not change after the removal of the two base squares. Then after removing the two squares the value at:
1. point 1 is a.
2. point 2 is b - 2u = a.
3. point 3 is c - 2v = a.
4. point 4 is d - 2u - 2v = a.
##### Switch the multipliers for the two removed squares and put them back. Then the value at:
1. point 1 is a.
2. point 2 is a + 2v = c.
3. point 3 is a + 2u = b.
4. point 4 is a + 2v + 2u = d.

## MAGIC LINE SQUARES

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-1i=02x(mi)gh. Call the lines passing through 2u(mu)gh x and y. Then the base lines for 2uMu 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-1i=02iXi and t-1i=02iYi 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 2px2p magic square containing all the integers from 0 to (2p)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-2p.

## STRUCTURED MAGIC LINE SQUARES

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 (2p)2-1, and they are constructible from base lines. It is possible with the procedure described above to create magic squares of any order-2p. 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.

### Uniform Integral Distribution

 multiplier row column 128 D0 64 D15 32 D51 16 D85 8 D0 4 D15 2 D51 1 D85

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-2p can be created with uniform integral distribution for any value of p.

##### Adding the two partial squares obtained above results in a square with all the numbers from 0 to (2p)2-1 in a structured array. The square has uniform integral distribution but it is not a magic square because agonals do not add correctly.

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-1i=02i(mi)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-1i=p2i(mi)gh respectively. In this blank section, the g's are always 0.

### Shuffling Matrix

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-1i=02iSi, is a group of 2n numbers in an n-dimensional magic figure, np-1i=02iMi. The numbers are located at np-1i=02i(mi)gh…z where g is either g or ((g + 2p/2) (mod 2p)), h is either h or ((h + 2p/2) (mod 2p)), etc. Call these positions g and g', h and h', etc. np-1i=02iSi can be viewed as the corners of an n-dimensional hypercube within np-1i=02iMi with sides of length 2p/2.

There are four numbers in the shuffling matrix of a square, 2p-1i=02i(si)gh, 2p-1i=02i(si)gh', 2p-1i=02i(si)g'h, and 2p-1i=02i(si)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 A0 D0 64 A0 D15 32 A0 D51 16 A0 D85 8 D0 A0 4 D15 A0 2 D51 A0 1 D85 A0

### Shuffling Base Lines

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 A0 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.

##### Proof: Select a base square, 2uMu, within 2p-1∑i=02iMi. When u ≤ (p-1) the value for b in 2u(mu)gh in the initial base square created above is always 0. Select a shuffling matrix, 2uSu, within the base square. Introduction of the second base line with its repeating base line units either leaves h = 0 or makes h = 1 for all 2u(su)gh. This is because h and h' in 2u(su)gh, 2u(su)gh', 2u(su)g'h, and 2u(su)g'h' must be the same for a repeating base line. Half of the possible shuffling matrices will have h = 0 and half will have h = 1. Since the same base line is used for all base squares in p-1∑i=02iMi the h's for all base squares in any given shuffling matrix, p-1∑i=02i(si)gh will be either all 0 or all 1. By the same argument for 2p-1∑i=p2iMi, the g's for all base squares in any given shuffling matrix, 2p-1∑i=p2i(si)gh, are either all 0 or all 1.
 position g=0 and h=0 g=1 and h=0 g=0 and h=1 g=1 and h=1 (2p-1),…,0sgh m + l m + l m + l m + l (2p-1),…,0sgh' m + l m + l m + l m + l (2p-1),…,0sg'h m + l m + l m + l m + l (2p-1),…,0sg'h' m + l m + l m + l m + l

## HYPERCUBES

Base figures and magic figures of any dimension can be made by simple extensions of the concepts described above for squares.

### Base Figures

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 2p where p ≥ n. For this discussion the base figure has the property that every agonal and every pan-s-agonal sums to 2p/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 2p/2. To make a valid base figure every dimension must have a base line with a different base line unit length.

##### Proof: Diagonals of every square in the n-dimensional base figure are constructed from two base lines and thus by the proof for base squares above all add to 2p/2 when the two base lines have different base line unit lengths. If two dimensions have the same base line unit length, then some of the diagonals of the squares defined by those two dimensions will not add to 2p/2. Therefore, the n-dimensional base figure will not be pan-2-agonal unless all the base lines have different base line unit lengths. If the n-dimensional base figure is not pan-2-agonal, it is not a valid base figure by the definition above.

Higher order s-agonals also add to 2p/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.

### Combining Base Figures

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 (2p/2)(2h-1) where h is the number of base figures in the intermediate and (2p/2) is 1/2 the order of the figure.

### Shuffling Base Figures

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.

### Magic Line Figures

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-2p containing all the integers from 0 to (2p)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, (2p/2)(2pn-1), where 2 ≤ s ≤ n. The magic line figures are pan-2,3,…,n-magic figures of order-2p.

### Structured Magic Line Figures

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 (2p)n-1, and they can be constructed from master base lines. It is possible to build an n-dimensional magic figure of any 2p 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.

#### Uniform Integral Distribution

A structured n-dimensional figure similar to the square example above can be constructed for any order-2p where p≥n. There will be np base figures in the construct each with a different multiplier from 20 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 nth dimension getting a compatible base line set in its p most significant bits. The resulting construct will have uniform integral distribution.

#### Shuffling Matrix

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 2n numbers in the shuffling matrix of a figure at 2p-1i=02i(si)abc…n where a can be at position a or ((a+(2p)/2) (mod 2p)), b independently at b or ((b+(2p)/2) (mod 2p)), etc. Call these positions a and a', b and b', etc. For the figure with uniform integral distribution defined above 2p-1i=02i(si)abc…n can be split into n groups of p consecutive bits, Ge 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 Ce and Re 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.

#### Shuffling Base Lines

The figure with uniform integral distribution created above only contains one compatible base line set in each group of base figures, Ce. 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 Re 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 Re's groups base figures.

##### The same process can be applied to a second group, Gf. Since the affected bits in Gf are different than those in Ge addition of the Rf base lines can only exchange pairs of numbers aligned with the axes of Cf. The Gf exchanges are independent of the Ge exchanges because they affect different bits of the numbers in the shuffling matrix. Continuing this process for the remaining n-2 groups will result in a valid magic line figure.

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.

## TERNARY, QUINARY, ETC.

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.

### Base Lines

Definition: A base line unit is a linear digit pattern of length oq 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 32. 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-op is composed of o(p-q) identical base line units where p ≥ q.

### Compatible Base Lines

Definition: A compatible base line set is a group of p compatible base lines of length op that contains all the numbers from 0 to op-1.

### Base Squares

Definition: A base square, M, is an opxop 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 mij = (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 op(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 op(o-1)/2. Proof of the general case is similar to that for the binary:

### Combining Base Squares

Magic squares of order-op 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: o1M1 + o0M0 = 1i=0oiMi. Both the multiplication and addition follow the normal rules of matrix math. Construction will require the successful combination of np base figures.

### Structured Magic Line Figure with Uniform Integral Distribution

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-op. The construction proceeds as described above. An n-dimensional figure of order-op 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.

##### Continue dividing the base line by higher powers of o until the pth base line is reached. This will look like: 012…o-123…o0-234…o01-…-o01…(o-1)--123…o0-234…o01-…-012…o--234…o01-345…o012-…-123…0--…--…--o01…(o-1)-012…o-…-(o-1)o0…(o-2)---123…o0-234…o01-…-012…o--234…o01-345…o012-…-123…0--…--…--012…o-123…o0-…-o01…(o-1)---etc. where the -'s are as above.

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.

### Shuffling Matrix

Definition: A shuffling matrix, np-1i=02iSi, is a group of on numbers in an n-dimensional magic figure, np-1i=02iMi. The numbers are located at np-1i=02i(mi)gh…z where g is ((g + ro(p-1)) (mod op)), h is ((h + so(p-1)) (mod op)), 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.

### Valid Magic Line Figures of Any Order-op

The figure with uniform integral distribution created above only contains one compatible base line set in each group of base figures, Ce. 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 Re 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 Re's groups base figures.