Chaitanya's Random Pages

August 28, 2012

(2,3)-multigrade equations

Filed under: mathematics — ckrao @ 2:02 pm

(This post is inspired by this recent post at the Futility Closet blog.)

Here is a pretty cool equation.

\displaystyle 1830 + 5637 + 6105 = 7218 + 3411 + 2943\quad \quad (1)

Why is it cool? Permute the digits of each term in the same way and the equation is still true.

e.g. swapping the second and fourth digits gives

\displaystyle 1038 + 5736 + 6501 = 7812 + 3114 + 2349

Furthermore, take any subset of the digits of each term and equality still holds.

e.g. taking the first and third digits of each term (1) gives

\displaystyle 13 + 53 + 60 = 71 + 31 + 24

Now for the coolest part – all of the above is true when each term of any of the sums is squared!

e.g.

\displaystyle 1830^2 + 5637^2 + 6105^2 = 7218^2 + 3411^2 + 2943^2

\displaystyle 1038^2 + 5736^2 + 6501^2 = 7812^2 + 3114^2 + 2349^2

\displaystyle 13^2 + 53^2 + 60^2 = 71^2 + 31^2 + 24^2

It may not take too long to see why the initial statements are true (i.e. before we started squaring things). The original sum has this form:

\begin{array}{lcl} & & (1000r_3 + 100 r_2 + 10r_1 + r_0) + (1000 s_3 + 100s_2 + 10s_1 + s_0)\\ & & \quad + (1000 t_3 + 100t_2 + 10t_1 + t_0)\\ & = & (1000 u_3 + 100u_2 + 10 u_1+ u_0) + (1000 v_3 + 100 v_2 + 10 v_1 + v_0)\\ & & \quad + (1000 w_3 + 100 w_2 + 10 w_1 + w_0) \end{array}

where the variables indicate digits.

As long as we have for each digit r_i + s_ i + t_i = u_i + v_i + w_i for i = 0, 1,2,3, the above sum follows by multiplying both sides by powers of 10 and adding.

This is true in our case for indeed we have 1 + 5 + 6 = 7 + 3 + 2, 8 + 6 + 1 = 2 + 4 + 9, 3 + 3 + 0 = 1 + 1 + 4, 0 + 7 + 5 = 8 + 1 + 3.

As long as these sums appear in the same digits place (units, tens, hundreds or thousands), the digits can appear in any order. This explains why any subset or permutation of the digits of (1) should preserve equality.

Now it’s time to look at why equality should hold when the terms are squared.

Firstly notice that the sums of the squares of respective digits are equal.

i.e.

\displaystyle 1^2 + 5^2 + 6^2 = 7^2 + 3^2 + 2^2 = 62

\displaystyle 8^2 + 6^2 + 1^2 = 2^2 + 4^2 + 9^2 = 101

\displaystyle 3^2 + 3^2 + 0^2 = 1^2 + 1^2 + 4^2 = 18

\displaystyle 0^2 + 7^2 + 5^2 = 8^2 + 1^2 + 3^2 = 74

Using the notation r_i, s_i, t_i, u_i, v_i, w_i as before, we have

\begin{array}{lcl} & & \left(\sum_{i=0}^3 10^i r_i\right)^2 + \left(\sum_{i=0}^3 10^i s_i\right)^2 + \left(\sum_{i=0}^3 10^i t_i\right)^2\\& = & \sum_{i=0}^3 10^{2i} r_i^2 + 2\sum_{i<j}10^{i+j} r_i r_j + \sum_{i=0}^3 10^{2i} s_i^2 + 2\sum_{i<j}10^{i+j} s_i s_j + \sum_{i=0}^3 10^{2i} t_i^2 + 2\sum_{i<j}10^{i+j} t_i t_j \end{array}

For this to equal the desired right side, we know \sum_{i=0}^3 10^{2i} (r_i^2 + s_i^2 + t_i^2) = \sum_{i=0}^3 10^{2i} (u_i^2 + v_i^2 + w_i^2), but we also need to show that the cross terms \sum_{i<j}10^{i+j} (r_i r_j + s_i s_j + t_i t_j) are equal to \sum_{i<j}10^{i+j} (u_i u_j + v_i v_j + w_i w_j). It turns out that this is indeed the case for our special choice of digits.

For convenience let e_i denote the column vector (r_i, s_i, t_i)^T and let f_i = (u_i, v_i, w_i)^T (the T represents transpose). Then we need to verify the vector dot products e_i^T e_j = f_i^T f_j,

where

\displaystyle e_1 = (1,5,6)^T, \quad f_1 = (7,3,2)^T

\displaystyle e_2 = (8,6,1)^T, \quad f_2 = (2,4,9)^T

\displaystyle e_3 = (3,3,0)^T, \quad f_3 = (1,1,4)^T

\displaystyle e_4 = (0,7,5)^T, \quad f_4 = (8,1,3)^T.

(For example, e_1^T e_2 = 8 + 30 + 6 = 44, f_1^T f_2 = 14 + 12 + 18 = 44.)

Note that each coordinate of e_i + f_i is equal to (2/3) of the sum of the coordinates of e_i. In matrix notation this fact can be stated by the relation

\displaystyle e_i + f_i = \frac{2}{3} S e_i

where

\displaystyle S = \left[ \begin{array}{ccc}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1\end{array} \right].

This can be written as f_i = (\frac{2}{3}S - I)e_i where I represents the 3×3 identity matrix.

We may then verify that S^TS = S^2 = 3S and so for i = 0, 1, 2, 3,

\begin{aligned} f_i^T f_j &= e_i^T(\frac{2}{3}S-I)^T (\frac{2}{3}S-I) e_j\\ &= e_i^T (\frac{4}{9}S^T S - \frac{4}{3}S + I) e_j \\&= e_i^T (\frac{4}{3}S - \frac{4}{3}S + I) e_j\\ &= e_i^T I e_j\\ &= e_i^T e_j. \end{aligned}

It follows that the squared sums are equal:

\begin{array}{lcl} & & \left(\sum_{i=0}^3 10^i r_i\right)^2 + \left(\sum_{i=0}^3 10^i s_i\right)^2 + \left(\sum_{i=0}^3 10^i t_i\right)^2\\ &=&\left(\sum_{i=0}^3 10^i u_i\right)^2 + \left(\sum_{i=0}^3 10^i v_i\right)^2 + \left(\sum_{i=0}^3 10^i w_i\right)^2 \end{array}

and it can be seen that any subset or permutation of the indices {1,2,3,4} could be chosen in each sum for equality to hold.

(Aside: Note the above is also true if instead of f_i = (\frac{2}{3}S - I)e_iwe had the relation f_i = (\frac{2}{3}S - P)e_i, where P is any 3×3 permutation matrix (P operates by swapping any two indices of a vector). The orthogonality of the matrix (\frac{2}{3}S - P) follows from the relations SP = PS = S and P^2 = I. The important thing is that the same  permutation P is used for each i.)

In summary the following steps were made in coming up with (1).

  1. Start with randomly chosen pairs of digits (1,5), (8,6), (3,3), (0,7) and add a third digit to each pair so that their sum is a multiple of 3. In our case we chose 6, 1, 0, 5 so that the resulting triples have sum 1+5+6 = 12, 8+6+1 = 15, 3+3+0 = 6, 0+7+5 = 12.
  2. Given a triple e_i^T = (a_i,b_i,3k_i-(a_i+b_i)) with sum 3k_i define the second triple to be f_i^T = (2k_i-a_i, 2k-b, a+b-k). Then it can be verified that e_i^T e_j=f_i^T f_j for any 0 \leq i,j \leq 3. In our example, we obtain the triples (8-1,8-5,8-6), (10-8,10-6,10-1), (4-3,4-3,4-1), (8-0,8-7,8-5), or (7,3,2), (2,4,9), (1,1,4), (8,1,3). We make sure the f_i triples are also digits (between 0 and 9).
  3. Concatenate corresponding digits of each triple e_i, f_i to form our sum in (1):

\displaystyle 1830 + 5637 + 6105 = 7218 + 3411 + 2943

At last we come to the meaning of the title of this post. Integer equations such as

\displaystyle a + b + c = u + v + w

\displaystyle a^2 + b^2 + c^2 = u^2 + v^2 + w^2

are known as (2,3)-multigrade equations. The 2 represents the highest power and the 3 represents the number of terms in each side of the equation.

The following are known about the solutions to such equations.

  1. If (a,b,c,u,v,w) is a solution, so are (a+k, b+k, c+k, u+k, v+k, w+k) and (ak, bk, ck, dk, uk, vk, wk) for any integer k.
  2. The general solution has the form (a,b,c,u,v,w)=(g + e,h+e,m+n+e,m+e,n+e,g+h+e) where g,h,e are integers satisfying gh = mn.
  3. Another form for the general solution is (a,b,c,u,v,w) = (wy+xz+e, wz+e,xy+e,wz+xy+e,xz+e,wy+e), where w,x,y,z,e are integers.

Note that 1 is straightforward to show while 2 follows from 3 by setting g = wz, h = xy, m = xz, n = wy. We will show 3 at the end of this post.

Not all solutions have the property a+u =b+v = c+w (even after permuting u,v,w. This was only needed above to ensure that when concatenating two or more digits the squared equation work (i.e. so that the cross-terms equated). For example, 5^2 + 0^2 + 8^2 = 2^2 + 9^2 + 2^2 and 8^2 + 6^2 + 1^2 = 2^2 + 4^2 + 9^2 are valid pairs of (2-3)-multigrade equations but after concatenating to form 2-digit numbers, 58^2 + 06^2 + 82^2 < 22^2 + 94^2 + 82^2. The solution (a,b,c,u,v,w)=(5,0,8,2,9,2) does not have the a+u =b+v = c+w property (the sum a + u + b + v + c + w would need to be a multiple of 3 for this to be possible).

Appearance of (2,3)-multigrade solutions in magic squares

Interestingly, if you take any 3×3 magic square (integers in a 3 by 3 array so that the numbers in each row, column and diagonal have the same sum), the first and third rows or columns form solutions to (2,3)-multigrade equations. As an example, take the following instance (copied from here).

Magicsquareexample.svg

The first and third rows give 2^2 + 7^2 + 6^2 = 4^2 + 3^2 + 8^2 = 89 while the first and third columns give 2^2 + 9^2 + 4^2 = 6^2 + 1^2 + 8^2 = 101. Furthermore by concatenation forwards and backwards we can find many more (2,3)-multigrade equations:

\displaystyle 276^2 + 951^2 + 438^2 = 672^2 + 159^2 + 834^2 (rows)

\displaystyle 294^2 + 753^2 + 618^2 = 492^2 + 357^2 + 816^2 (columns)

\displaystyle 258^2 + 714^2 + 693^2 = 852^2 + 417^2 + 396^2 (diagonals)

\displaystyle 213^2 + 798^2 + 654^2 = 312^2 + 897^2 + 456^2 (counter-diagonals)

\displaystyle 258^2 + 936^2 + 471^2 = 852^2 + 639^2 + 174^2 (diagonals)

\displaystyle 231^2 + 978^2 + 456^2 = 132^2 + 879^2 + 654^2 (counter-diagonals)

All the above hold also when the power indices of 2 are replaced with 1. These six relations (first discovered by Dr Irving Joshua Matrix according to [1]) all follow from the single-digit relations using similar reasoning from before.

The single-digit relations can be verified by using the general form of a 3×3 magic square:

p + q + 2r p p + 2q + r
p + 2q p+q +r p + 2r
p + r p + 2q + 2r p + q

General solution to (2,3)-multigrade equations

Finally for completeness we shall derive the general solution of the equation:

\displaystyle a_1 + a_2 + a_3 = b_1 + b_2 + b_3

\displaystyle a_1^2 + a_2^2 + a_3^2 = b_1^2 + b_2^2 + b_3^2

We use the procedure outlined in [2]. Take S = a_1 + a_2 + a_3, 3A_i = a_i + S, 3B_i = b_i + S. Substituting gives

\displaystyle \sum_{i=1}^3 A_i = \sum_{i=1}^3 B_i = 0, \sum_{i=1}^3 A_i^2 = \sum_{i=1}^3 B_i^2

This is slightly easier to work with since we can reduce this to an equation of fewer variables. Since A_3 = -(A_1 + A_2),

\displaystyle \sum_{i=1}^3 A_i^2 = A_1^2 + A_2^2 + (A_1+A_2)^2 = 2(A_1^2 + A_2^2 + A_1A_2)

and so

\displaystyle A_1^2 + A_2^2 + A_1A_2 = B_1^2 + B_2^2 + B_1B_2 \quad \quad (2)

To proceed we use the fact that x^2 + xy + y^2 be factorised in the complex numbers as (x + y(1 + \sqrt{3}i)/2)(x + y(1 - \sqrt{3}i)/2).

We use unique factorisation in the quadratic ring \mathbb{Z}[(1+\sqrt{3}i)/2] (the Eisenstein integers). We can write numbers in this ring uniquely in the  form z = a + b \omega, where a,b are integers and \omega = (1+\sqrt{3}i)/2, one of the cube roots of -1. Visualize Eisenstein integers as elements of an equilateral triangular lattice in the complex plane (as opposed to Gaussian integers which are elements of a square lattice).

Assume that A_i \neq B_i in (2). Then letting both sides of this equation equal N, equation (2) represents a factorisation of N in two ways.

\displaystyle N = (A_1 + A_2\omega) (A_1 + A_2\bar{\omega}) = (B_1 +B_2\omega) (B_1 + B_2\bar{\omega})

As factorisation in our ring of Eisenstein integers is unique, this equation must imply that one of the terms, say (A_1 + A_2 \omega), must be the product of two non-unit terms, say (a + b\omega)(c + d\omega) where a,b,c,d are integers. Then pairing up products with their conjugates, the factorisation of (2) can be written in the following two ways.

\displaystyle N = (a + b\omega)(c + d\omega)(a + b\bar{\omega})(c + d\bar{\omega}) = (a + b\omega)(c + d\bar{\omega})(a + b\bar{\omega})(c + d\omega)

In other words, A_1 + A_2 \omega = (a + b\omega)(c + d\omega) and B_1 + B_2 \omega = (a + b\omega)(c + d\bar{\omega}), leading to

\begin{array}{lcl}A_1 + A_2 \omega &=& ac + (ad + bc)\omega + bd\omega^2\\ &=& ac + (ad + bc)\omega + bd(\omega-1)\\ &=& (ac-bd) + (ad + bc + bd)\omega\end{array}

\begin{array}{lcl}B_1 + B_2 \omega &=& ac + ad\bar{\omega} + bc \omega + bd \omega \bar{\omega}\\ &=& (ac + bd) + ad (1 - \omega) + bc \omega\\ &=& (ac + bd + ad) + (bc - ad)\omega\end{array}

Matching coefficients then gives us the general solution A_1 = ac-bd, A_2 = ad + bc + bd, B_1 = ac + bd + ad, B_2 = bc - ad. To reach the (wy+xz+e, wz+e,xy+e,wz+xy+e,xz+e,wy+e) form given above, we first note that among the four integers a,b,c,d, two of them, say a and b are the same modulo 3. We then let a = y + z, b = y - 2z, c =x, d = w - x and find that

\begin{array}{lcl}ac-bd &=& (y+z)x-(y-2z)(w-x)\\&=& xy+xz-wy+xy+2wz-2xz\\&=& 2xy - xz - wy + 2wz\\&=& 3(wz+xy) - (w+x)(y+z)\end{array}

\begin{array}{lcl}ad + bc + bd &=& (a+b)(c+d)-ac\\&=& (2y-z)w - x(y+z)\\&=& 2wy-wz-xy-xz\\&=& 3wy - (w+x)(y+z)\end{array}

\begin{array}{lcl}ac + bd + ad &=& (a+b)(c+d)-bc\\&=& (2y-z)w - x(y-2z)\\&=& 2wy-wz-xy+2xz\\&=& 3(xz+wy) - (w+x)(y+z)\end{array}

\begin{array}{lcl} bc - ad & = & (y - 2z)x - (y+z)(w-x)\\& = & wy - txz - wy - wz + xy + xz\\ & = & 2xy - xz - wy - wz \\ &=& 3xy - (w+x)(y+z)\end{array}

Hence after adding S = (w+x)(y+z) and dividing by 3 (if all the numbers are divisible by 3), we arrive at the form above. Finally note that adding any constant to each entry also produces a valid solution.

By computational search, we find the single digit non-trivial solutions to \displaystyle a_1 + a_2 + a_3 = b_1 + b_2 + b_3 and \displaystyle a_1^2 + a_2^2 + a_3^2 = b_1^2 + b_2^2 + b_3^2 (up to permutations) are given by the following 16 forms.

\displaystyle (0, 3, 3, 1, 1, 4) \quad (0, 4, 5, 1, 2, 6) \quad (0,5,7,1,3,8) \quad (0,5,8,2,2,9)

\displaystyle (0,6,6,2,2,8) \quad (0, 7,7,1,4,9) \quad (1,4,4,2,2,5) \quad (1,5,6,2,3,7)

\displaystyle (1,6,8,2,4,9) \quad (1,7,7,3,3,9) \quad (2,5,5,3,3,6) \quad (2,6,7,3,4,8)

\displaystyle (3,6,6,4,4,7) \quad (3,7,8,4,5,9) \quad (4,7,7,5,5,8) \quad (5,8,8,6,6,9)

Most of these can be concatenated to form multi-digit (2,3)-multigrade equations such as (1). The only exceptions are those which do not have sum a multiple of 3:  (0,5,8,2,2,9) and (0,7,7,1,4,9). More information about (2,3)-multigrade equations can be found in [3].

References

[1] A. Benjamin and K. Yasuda, “Magic Squares Indeed!”, Amer. Math. Monthly, Feb. 1999.

[2] Dickson, History of the theory of numbers, available at: http://archive.org/details/historyoftheoryo02dickuoft

[3] T. Piezas, Sum / Sums of three squares – A Collection of Algebraic Identities: https://sites.google.com/site/tpiezas/004

Advertisements

2 Comments »

  1. Hello ckrao. There is a small discussion of the multi-grade a^k+b^k+c^k = d^k+e^k+f^k, for k = 1,2, at mathstackexchange.com http://math.stackexchange.com/questions/456824/

    Comment by tpiezas — August 2, 2013 @ 1:34 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: