Magic Cubes

I had a dream some nights ago in which I dreamt of the number 42. I hadn't been reading or thinking about The Hitchhiker's Guide to the Galaxy but I was prompted by the dream to investigate some of the properties of this number. As I discovered, it's a pronic number or a product of consecutive digits, in this case 6 and 7. It's also a partition number since it is equal to the number of partitions of 10. For information about its being the sum of three cubes, see this blog post of mine. The number is also associated with the 3 x 3 x 3 magic cube as shown in Figure 1:

Figure 1: dissection of a 3 x 3 x 3 magic cube
Source: https://mathematicscentre.com/taskcentre/174magic.htm

In such a cube, all the rows and columns in each of the three square "slices" shown in Figure 1 add to 42. It would be the same if we sliced in other similar ways. The long diagonals (19, 14, 9 for example) also add to 42 but the diagonals within the slices do not. Figure 2 shows another possible configuration:

Figure 2: source 

9 rows, such as 1 - 17 - 24, sum to 42.
9 columns, such as 1 - 15 - 26, sum to 42.
9 Pillars, such as 1 - 23 - 18, sum to 42.
4 triagonals, such as 26 - 14 - 2 sum to 42. 

Some of the squares may have diagonals summing to 42, but this is not a requirement. In fact, order-8 is the smallest cube for which it is possible for all the diagonals to sum correctly. 

What is required is that the 4 triagonals or 3-agonals, such as 1 - 14 - 27 sum to 42. 

There are four different basic pure (using numbers 1 to 27) magic cubes. Each of these have 48 equivalents due to rotations and/or reflections.

To quote from Wikipedia:

In mathematics, a magic cube is the 3-dimensional equivalent of a magic square, that is, a number of integers arranged in a \(n × n × n \) pattern such that the sums of the numbers on each row, on each column, on each pillar and on each of the four main space diagonals are equal to the same number, the so-called magic constant of the cube, denoted \(M_3(n)\). It can be shown that if a magic cube consists of the numbers \(1, 2, ..., n^3\), then it has magic constant (sequence A027441 in the OEIS):

$$
M_3(n) = \frac{n(n^3+1)}{2}
$$The OEIS sequence runs:

0, 1, 9, 42, 130, 315, 651, 1204, 2052, 3285, 5005, 7326, 10374, 14287, 19215, 25320, 32776, 41769, 52497, 65170, 80010, 97251, 117139, 139932, 165900, 195325, 228501, 265734, 307342, 353655, 405015, 461776, 524304, 592977, 668185, 750330, 839826, 937099

Of course, the formula above for 3 dimensions can be generalised to any number of dimensions. To quote again from Wikipedia:

In mathematics, a magic hypercube is the k-dimensional generalisation of magic squares, magic cubes and magic tesseracts; that is, a number of integers arranged in an \(n × n × n × ... × n\) pattern such that the sum of the numbers on each pillar (along any axis) as well as the main space diagonals is equal to a single number, the so-called magic constant of the hypercube, denoted \(M_k(n)\). It can be shown that if a magic hypercube consists of the numbers \(1, 2, ..., n^k\), then it has magic number: 

$$
M_k(n) = \frac{n(n^k+1)}{2}
$$For \(n=4\), the OEIS sequence A021003 is:

0, 1, 17, 123, 514, 1565, 3891, 8407, 16388, 29529, 50005, 80531, 124422, 185653, 268919, 379695, 524296, 709937, 944793, 1238059, 1600010, 2042061, 2576827, 3218183, 3981324, 4882825, 5940701, 7174467, 8605198, 10255589, 12150015

This whole topic leads in all sort of interesting directions but I'll have to leave off there and pursue some of these directions at another time.

Factoring Numbers Using Polynomials

Consider a number such as \(45\) and suppose we have no idea how to factor it. Let's convert \(45_{10}\) to its binary equivalent \(101101_2\). From this binary number, let's form a polynomial using the indices of the placeholder values \(2^5, 2^4, 2^3, 2^2, 2^1, 2^0\) as the indices of an associated polynomial, namely \(x^5 + x^3 + x^2 + 1\). This polynomial factorises as follows:$$

x^2(x^2+1)+1(x^2+1) = (x^2+1)(x^3+1) = (x+1)(x^2-x+1)(x^2+1)

$$If we now substitute \(x=2\), the result is 3 * 3 * 5 which are the prime factors of 45. Let's try another number, this time \(111\) that is \(1101111_2\) in binary form. The associated polynomial is \(x^6+x^5+x^3+x^2+x+1\) that factorises to the following:$$

x^5(x+1)+x^2(x+1)+1(x+1) = (x+1)(x^5+x^2+1)

$$Substituting \(x=2\) gives 3 * 37, the prime factors of \(111\).

The useful idea behind such a technique is that it can be applied to factor very large composite numbers. I came across the idea in a Quanta Magazine article titled: Mathematicians Seal Back Door to Breaking RSA Encryption. The article states:

This seems like a complicated way to find the prime factors of a small number like 15, whose factors are easy to spot straightaway. But with very large numbers — numbers with hundreds of digits — this polynomial method gives you a remarkable advantage. There’s no fast algorithm for factoring large numbers. But there are fast algorithms for factoring large polynomials. So once you convert your large number to a large polynomial, you’re very close to finding the number’s prime factors.

Does this mean RSA encryption is in trouble? Actually, no. The reason for this has to do with the new proof about polynomials. The mathematicians Emmanuel Breuillard and Péter Varjú of the University of Cambridge proved that as polynomials with only 0 and 1 as coefficients get longer, they’re less and less likely to be factorable at all. And if a polynomial can’t be factored, it can’t be used to identify the prime factors of the number it’s based on. 

Breuillard and Varjú’s proof effectively slams shut the polynomial back door for breaking RSA encryption. The very large numbers used in RSA encryption correspond to very long polynomials. Breuillard and Varjú proved that it’s nearly impossible to find polynomials of that length that can be factored. Mathematicians and cryptographers alike have long suspected this is the case. But when the cybersecurity of the entire world depends on some mathematical hack not working, it’s good to have proof that it doesn’t. 

Regardless of RSA encryption, the key point for me was the fact that every number can be represented as a unique polynomial. For example:

45 -->  \(x^5 + x^3 + x^2 + 1\) and 111 --> \(x^6+x^5+x^3+x^2+x+1\)

All such polynomials have coefficients that are either 0 or 1. This makes the factorisation, if possible, fairly straightforward as can be seen in examples chosen. Of course, a unique polynomial can be created in any base. In base 3:

45 --> \(x^3+2x^2=x^2(x+2)\) and 111 --> \(x^4+x^3+x=x \,(x^3+x^2+1)\)

Substituting \(x=3\) into the above factorised expressions gives the factorisation as before. However, in some bases, the polynomials do not factorise. For example, in base 5:

45 --> \(x^2+4x=x \, (x+4) \) but 111 --> \(4x^2+2x+1\) which doesn't factorise.