• Magic Cube

  Overview Magic Squares Magic Cubes Magic Hypercubes Other Order-8 Cubes Miscellaneous
  • Statistics Überprüfen Feature Builder Pan-Anti-Magic Squares Magic Buckyball Answers

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

BASE LINES

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.

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₀ and c₁ and the other by c₂ and c₅. 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₀ base line for an order-4 square is the same as the b₀ base line unit above whereas the B₀ 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.

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¹L₁ + 2⁰L₀ = t-1∑i=02ⁱ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³(D₀) + 2²(D₁₅) + 2¹(D₅₁) + 2⁰(D₈₅) gives the sequence 0, 1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, and 8. Thus D₀, D₁₅, D₅₁, and D₈₅ are a compatible base line set for p = 4.

BASE SQUARES

Definition: A base square, M, is a 2^px2^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:

Proof: In M let r be the length of the larger base line unit, b₀ in the example, and let s be the length of the smaller base line unit, a₀ in the example. Select the rxr section of the base square with its upper left corner at m₀₀, in red in the example. Every line in one direction of the rxr section will be the larger base line unit or its inverse. In the other direction, every line will be the smaller base line unit or its inverse repeated r/s times.

The larger base line unit, x, and the smaller base line unit repeated r/s times, y, can be considered base lines within the rxr section. For x numbers that are spaced r/2 apart are inverses, x_{((i+r/2) (mod r))} = x_i, and for y they are the same, y_{((i+r/2) (mod r))} = y_i. The rxr section is a matrix, N. The two points n_ij = x_i ⊕ y_j and n_{((i+r/2) (mod r))((j+r/2) (mod r))} = x_{((i+r/2) (mod r))} ⊕ y_{((j+r/2) (mod r))} are inverses. This means that any two points a (r/2,r/2) vector apart must be inverses. Since every diagonal or broken diagonal of the rxr section is composed of pairs of numbers a (r/2,r/2) vector apart then all have equal numbers of 0's and 1's. If r < 2^p then the rxr square is duplicated (2^p/r)² times in the larger square and each diagonal or broken diagonal in that larger figure will also have equal numbers of 0's and 1's.

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

Proof: If the base line units of both base lines are the same then an rxr matrix, N, can be built where r is the length of the base line units and n_ij = x_i ⊕ y_j. For both x and y numbers that are spaced r/2 apart are inverses. The result is that the points n_ij = x_i ⊕ y_j = n_{((i+r/2) (mod r))((j+r/2) (mod r))} = x_i ⊕ y_j. This means that the bit pattern of each half of every diagonal and broken diagonal is the same. Thus if 1/2 of a diagonal does not have equal numbers of 0's and 1's, the whole diagonal does not have equal numbers of 0's and 1's.

The sum of a half diagonal, S₁, = x_0…(r/2-1) ⊕ y_0…(r/2-1). The adjacent half diagonal, S₂, = x_0…(r/2-1) ⊕ y_1…(r/2). If S₁ = 2^p/4, the required sum for a half diagonal, then S₁ is even. Since y_(r/2) is the inverse of y₀ and y_(r/2) replaces y₀ in going from S₁ to S₂, S₂ must be odd and therefore S₂ ≠ 2^p/4. It follows that the full diagonals 2S₁ ≠ 2S₂.

Thus, if the length of the base line units of the two base lines are the same then some diagonals and/or broken diagonals of the base square will not add to 2^p/2 and the resulting figure will not be pan-magic and will not be a base square as defined above.

COMBINING BASE SQUARES

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¹M₁ + 2⁰M₀ = 1∑i=02ⁱM_i. Both the multiplication and addition follow the normal rules of matrix math. Another way to look at 1∑i=02ⁱ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ⁱ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ⁱ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ⁱ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ⁱM_i does not have uniform integral distribution then t-1∑i=02ⁱM_i will not have uniform integral distribution, where u is any intermediate value less than (t-1). A proof follows:

Proof: One way to construct magic squares from base squares is as discussed above, by adding base squares with increasing power of 2 multipliers. Another way is to multiply the intermediate square by 2 and add the next base square until the magic square is attained: 2(u∑i=02ⁱM_(i+1)) + 2⁰M₀ = u+1∑i=02ⁱM_i where the base squares that originally had 2^0…u multipliers have 2^1…(u+1) multipliers in the respective base squares of the resulting construct. The section below will prove that changing the order of the multipliers does not change the validity of the resulting magic square. Using this second method of construction the 0's and 1's in 2⁰M₀ expand to 0's and 2^(2p-1)'s in the magic square, t-1∑i=02ⁱM_i. The addition of each new base square increases half of the numbers in the doubled intermediate by 1. The other half of the numbers is just doubled. If a point was initially 0 and then increased by 1 at every subsequent step, its final value would be 2^(2p-1)-1. Therefore points in t-1∑i=02ⁱM_i that were 0's in the initial 2⁰M₀ must be in the range from 0 to 2^(2p-1)-1 in the final figure. This range constitutes half of the numbers in t-1∑i=02ⁱM_i and the 0's were the same half of the numbers in 2⁰M₀.

If there were 2^(2p-1)+1 0's in the initial 2⁰M₀ then t-1∑i=02ⁱM_i would have 2^(2p-1)+1 points with values in the range 0 to 2^(2p-1)-1. At least one number would have to be repeated resulting in uneven integral distribution in t-1∑i=02ⁱM_i. A similar argument holds for every intermediate composite base square.

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.

Proof: The numbers from 0 to (2^p)²-1 all occur only once in t-1∑i=02ⁱM_i. If one of the base squares, 2^uM_u, is removed from the summation then half the numbers in t-1∑i=02ⁱM_i will be reduced by 2^u. The reduced numbers will then be duplicates of other numbers in t-1∑i=02ⁱM_i - 2^uM_u. Removing a second square, 2^vM_v, results in a square in which all the remaining numbers occur 4 times.

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 - 2^u = a.
3. point 3 is c - 2^v = a.
4. point 4 is d - 2^u - 2^v = a.

The number at point 1 was not changed because there was a 0 at point 1 in both of the removed base squares. The number at point 2 was reduced by 2^(u) because there was a 1 at point 2 in 2^uM_u and a 0 at that point in 2^vM_v, etc.

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 + 2^v = c.
3. point 3 is a + 2^u = b.
4. point 4 is a + 2^v + 2^u = d.

Again, the number at point 1 is not changed. The number at point 4 returns to its initial value since both numbers that were subtracted are added back. The numbers at points 2 and 3 have switched positions.

Thus the effect of exchanging two base squares is to rearrange some numbers but the resulting square still has uniform integral distribution and is thus a different magic square. Therefore, a magic square composed of 2p base squares can be arranged in any order relative to the multipliers to give (2p)! different magic cubes.

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-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^uM_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ⁱX_i and t-1∑i=02ⁱ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^px2^p magic square containing all the integers from 0 to (2^p)²-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.

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 (2^p)²-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⁽²¹⁾+1)(2⁽²⁰⁾-1) are a structured example.

Uniform Integral Distribution

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.

Proof: A square of order-2^p contains a compatible base line set in its p least significant bits. These are the four D codes in the row of the example. A square constructed with only these p bits would contain every number from 0 to 2^p-1 in every row. In the example, the series 0, 1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, and 8 would be in every row of the square.

In its p most significant bits, the square contains the same or a different compatible base line set. These are the four D codes in the column of the example. A square constructed with only these p bits would contain the series from 0 to (2^p)²-2^p in 2^p increments in every column. In the example, the series 0, 16, 32, 48, 64, 80, 96, 112, 240, 224, 208, 192, 176, 160, 144, and 128 would be in every column of the square. This series is 2^p times the first series above since the two compatible base line sets are the same.

Adding the two partial squares obtained above results in a square with all the numbers from 0 to (2^p)²-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-1∑i=02ⁱ(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ⁱ(m_i)_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-1∑i=02ⁱS_i, is a group of 2ⁿ numbers in an n-dimensional magic figure, np-1∑i=02ⁱM_i. The numbers are located at np-1∑i=02ⁱ(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ⁱS_i can be viewed as the corners of an n-dimensional hypercube within np-1∑i=02ⁱM_i with sides of length 2^p/2.

There are four numbers in the shuffling matrix of a square, 2p-1∑i=02ⁱ(s_i)_gh, 2p-1∑i=02ⁱ(s_i)_gh', 2p-1∑i=02ⁱ(s_i)_g'h, and 2p-1∑i=02ⁱ(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))², within the order-16 square and they all conform to this rule.

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 A₀ 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, 2^uM_u, within 2p-1∑i=02ⁱM_i. When u ≤ (p-1) the value for b in 2^u(m_u)_gh in the initial base square created above is always 0. Select a shuffling matrix, 2^uS_u, 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 2^u(s_u)_gh. This is because h and h' in 2^u(s_u)_gh, 2^u(s_u)_gh', 2^u(s_u)_g'h, and 2^u(s_u)_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=02ⁱM_i the h's for all base squares in any given shuffling matrix, p-1∑i=02ⁱ(s_i)_gh will be either all 0 or all 1. By the same argument for 2p-1∑i=p2ⁱM_i, the g's for all base squares in any given shuffling matrix, 2p-1∑i=p2ⁱ(s_i)_gh, are either all 0 or all 1.

After the addition, numbers in the various shuffling matrices are affected as shown in the table at right. In this table, the value for g refers only to its value in the least significant bits and the value for h refers only to its value in the most significant bits.

An examination of the table shows that addition of a consistent set of repeating base lines in the prescribed way to the square with uniform integral distribution created above merely shuffles the numbers within a shuffling matrix. Since all the numbers within the square are part of a shuffling matrix, addition of base lines with repeating base line units in the prescribed way results in a square that retains its uniform integral distribution.

Addition of the set of base lines with repeating base line units has resulted in base squares that are constructed from two base lines with different base line unit lengths. These base squares therefore have valid addition properties and the square created from their combination is a valid magic square.

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

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

Proof: For a t-dimensional base figure within the larger n-dimensional base figure, points on each t-agonal are defined by the intersection of t base lines. Let r be the length of the longest base line unit within the t-dimensional space and define m_ij…o = (l₁)_i ⊕ (l₂)_j ⊕ … ⊕ (l_t)_o. Let L₁ be the longest base line unit, then (l₁)_{((i+r/2) (mod r))} is the inverse of (l₁)_i. For all the other base lines (l_u)_{((v+r/2) (mod r))} is the same as (l_u)_v since they all have repeating base line units within the t-dimensional figure. Therefore, two points m_ij…o and m_{((i+r/2) (mod r))((j+r/2) (mod r))…((o+r/2) (mod r))} on a t-dimensional diagonal are inverses. Thus, any two points separated by a (r/2,r/2,…,r/2) vector are inverses resulting in t-dimensional diagonals with halves that are inverses.

Therefore, every r-agonal of an n-dimensional base figure made from base lines with different base line unit lengths sums to 2^p/2.

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

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-2^p containing all the integers from 0 to (2^p)ⁿ-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.

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 (2^p)ⁿ-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.

Uniform Integral Distribution

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

Proof: A figure constructed as above with just the p least significant bits will have all the numbers from 0 to 2^p-1 in all the agonals of the first dimension by the compatible base line set definition. A figure constructed with the 2p least significant bits will have all the numbers from 0 to (2^p)²-1 in all the squares defined by the dimensions of the first two compatible base line sets. The latter was described in more detail for the square. A figure constructed with the 3p least significant bits will have all the numbers from 0 to (2^p)³-1 in all the cubes defined by the dimensions of the first three compatible base line sets, etc. The n^th compatible base line set added to the n^th dimensions most significant bits creates an n-dimensional figure with all the numbers from 0 to (2^p)ⁿ-1 in a structured array.

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 2ⁿ numbers in the shuffling matrix of a figure at 2p-1∑i=02ⁱ(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ⁱ(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.

Shuffling Base Lines

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.

Proof: Select a group, G_e composed of C_e and R_e from the initial figure that has uniform integral distribution in a structured array. To each of the base figures in that group place duplicate base lines of different base line unit lengths in the n-1 dimensions of R_e. Since both halves of all of these base lines are identical the exclusive OR combination of the n-1 values in any given shuffling matrix will be all 0 or all 1 for R_e. If they are all 0 the numbers in the shuffling matrix will be the same as those in C_e. If they are all 1 then the pairs of numbers aligned with the axes of C_e will be exchanged preserving the uniform integral distribution.

The same process can be applied to a second group, G_f. Since the affected bits in G_f are different than those in G_e addition of the R_f base lines can only exchange pairs of numbers aligned with the axes of C_f. The G_f exchanges are independent of the G_e 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 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². 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.

Compatible Base Lines

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.

Base Squares

Definition: A base square, M, is an o^pxo^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:

Proof: In M let r be the length of the larger base line unit and let s be the length of the smaller base line unit. Select the rxr section of the base square with its upper left corner at m₀₀. Every line in one direction of the rxr section will be the larger base line unit or the digits in the larger base line unit plus a constant (mod o). In the other direction, every line will be the smaller base line unit or the digits in the smaller base line unit plus a constant (mod o) repeated r/s times.

The larger base line unit, x, and the smaller base line unit repeated r/s times, y, can be considered base lines within the rxr section. For x numbers that are spaced r/o apart are always different by definition and for y they are always the same. The rxr section is a matrix, N. The o points n_ij = (x_i + y_j) (mod o), n_{((i+r/o) (mod r))((j+r/o) (mod r))} = (x_{((i+r/o) (mod r))} + y_{((j+r/o) (mod r))}) (mod o), …, n_{((i+(o-1)r/o) (mod r))((j+(o-1)r/o) (mod r))} = (x_{((i+(o-1)r/o) (mod r))} + y_{((j+(o-1)r/o) (mod r))}) (mod o) are all different. This means that the digits in any group of o points spaced at r/o intervals on a diagonal are all different. Every diagonal contains o^(p-1) such groups. The groups all add to o(o-1)/2. Thus every diagonal or broken diagonal of the rxr section sums to o^p(o-1)/2.

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 o^p(o-1)/2.

Combining Base Squares

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¹M₁ + o⁰M₀ = 1∑i=0oⁱM_i. 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-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.

Divide the first base line of the set into o parts. Place o^(p-1) 0's in the first part, o^(p-1) 1's in the second part, …, and o^(p-1) (o-1)'s in the last part.

Divide the second base line of the set into o parts. Divide the first of these parts into o subparts. Place o^(p-2) 0's in the first subpart, o^(p-2) 1's in the second subpart, …, and o^(p-2) (o-1)'s in the last subpart. Each digit in the second part of the base line is the sum of the corresponding digit of the first part plus 1 (mod o). The third part is related to the second in the same way, etc.

The third base line of the set is divided by o three times with each sub subpart getting o^(p-3) of each digit. The digits proceed with the (mod o) progression described above within the subparts and in going from one part to the next. EXAMPLE: The third ternary base line for an order-81 figure is 000111222-111222000-222000111--111222000-222000111-000111222--222000111-000111222-111222000 where the -'s separate the subparts and the --'s separate the parts.

Continue dividing the base line by higher powers of o until the p^th 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-1∑i=02ⁱS_i, is a group of oⁿ numbers in an n-dimensional magic figure, np-1∑i=02ⁱM_i. The numbers are located at np-1∑i=02ⁱ(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.

Valid Magic Line Figures of Any Order-o^p

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.