=============================================== A 19-correct-line 4x4 bimagic square of distinct integers is impossible. By Lee Morgenstern, June 2012. =============================================== A 19-correct line 4x4 bimagic square must contain a nearly-bimagic square; that is, a semi-bimagic square having one bimagic diagonal. The following proof will show that a 4x4 nearly bimagic square containing real numbers must always contain duplicate entries. Many of the intermediate equations are quite long, so to save space, they are omitted. However, complete procedures are given so that a symbolic algebra program can be used to reproduce them. =============================================== Contents Semi-Magic Square Formulation Semi-Magic Square Solving Procedure Semi-Magic Square Solution Semi-Bimagic Square Formulation Semi-Bimagic Square Solving Procedure Semi-Bimagic Square Solution Proofs of Duplication Lemmas Nearly-Bimagic Square Additional Formulation Nearly-Bimagic Square Solving Procedure Nearly-Bimagic Square Solution No-Real-Root Support Theorem No-Real-Root Proof Additional Remarks =============================================== Semi-Magic Square Formulation =============================================== Suppose we have a 4x4 semi-magic square of distinct integers. A B C D E F G H I J K L M N P Q Later, we will also want one magic diagonal. We can always reflect the magic square so that D,G,J,M is the magic diagonal. Magic and bimagic lines remain if we subtract a constant from all entries or divide all entries by a constant. So can reduce the problem by two variables by converting a magic square of integer entries to one with rational entries by subtracting A from all entries and dividing all entries by F. Note that the choice of A and F are on the proposed non-magic diagonal. 0 B C D E 1 G H I J K L M N P Q To be semi-magic, we must have [1] B+C = H+L+Q [2] E+1+G = D+L+Q [3] I+J+K = D+H+Q [4] M+N+P = D+H+L [5] C+G+K+P = D+H+L+Q [6] B+J+N+1 = D+H+L+Q Since the sum of the rows equals the sum of the columns, we don't need a 7th equation. =============================================== Semi-Magic Square Solving Procedure =============================================== Solve [1] for B. Eliminate B from [6]. Solve [2] for E. Solve [3] for I. Solve [4] for N. Eliminate N from [6]. Solve [5] for K. Eliminate K from [3]. Solve [6] for P. Eliminate P from [3], [4], [5]. =============================================== Semi-Magic Square Solution =============================================== [1] B = H+L+Q-C [2] E = D+L+Q-G-1 [3] I = G+H-M+1 [4] N = C+D-J-1 [5] K = D+M+Q-G-J-1 [6] P = H+J+L-C-M+1 Every row and column adds to D+H+L+Q. 0 H+L+Q-C C D D+L+Q-G-1 1 G H G+H-M+1 J D+M+Q-G-J-1 L M C+D-J-1 H+J+L-C-M+1 Q =============================================== Semi-Bimagic Square Formulation =============================================== For a line to be bimagic, it must satisfy the above equations when the entries are squared. Thus when the magic square requires B = H+L+Q-C, the bimagic square requires B^2 = H^2 + L^2 + Q^2 - C^2. Squaring the first equation and eliminating B^2 from the second produces (H+L+Q-C)(H+L+Q-C) = H^2 + L^2 + Q^2 - C^2. Doing this for the six semi-magic square equations produces the following. [B] (H+L+Q-C)(H+L+Q-C) = H^2 + L^2 + Q^2 - C^2 [E] (D+L+Q-G-1)(D+L+Q-G-1) = D^2 + L^2 + Q^2 - G^2 - 1 [I] (G+H-M+1)(G+H-M+1) = G^2 + H^2 - M^2 + 1 [K] (D+M+Q-G-J-1)(D+M+Q-G-J-1) = D^2 + M^2 + Q^2 - G^2 - J^2 - 1 [N] (C+D-J-1)(C+D-J-1) = C^2 + D^2 - J^2 - 1 [P] (H+J+L-C-M+1)(H+J+L-C-M+1) = H^2 + J^2 + L^2 - C^2 - M^2 + 1 =============================================== Semi-Bimagic Square Solving Procedure =============================================== Expand all six equations and divide by 2. [B] C^2 - CH - CL - CQ + HL + HQ + LQ = 0 [E] -DG + DL + DQ - D + G^2 - GL - GQ + G + LQ - L - Q + 1 = 0 [I] GH - GM + G - HM + H + M^2 - M = 0 [K] -DG - DJ + DM + DQ - D + G^2 + GJ - GM - GQ + G + J^2 - JM - JQ + J + MQ - M - Q + 1 = 0 [N] CD - CJ - C - DJ - D + J^2 + J + 1 = 0 [P] C^2 - CH - CJ - CL + CM - C + HJ + HL - HM + H + JL - JM + J - LM + L + M^2 - M = 0 Solve [I] for H. (M - 1)(G - M) [I] H = -------------- G - M + 1 Eliminate H from [B] and [P]. Solve [K] for Q. (D - G)(G + J - M + 1) + J(-J + M - 1) + M - 1 [K] Q = ---------------------------------------------- D - G - J + M - 1 Eliminate Q from [B] and [E]. Solve [P] for L. C^2(-G + M - 1) + C(GJ - JM + J - M + 1) + (J - G)(M - 1) [P] L = --------------------------------------------------------- C(-G + M - 1) + GJ - JM + J - M + 1 Eliminate L from [B] and [E]. Divide [B] by (M-1). [Note that (M-1) can't equal 0 because then M = 1 = F]. Solve [N] for C. J(D - J - 1) + D - 1 [N] C = -------------------- D - J - 1 Eliminate C from [B] and [E]. Divide [B] by G(G-M). Divide [E] by J(D-J)(D-1). [Note that G can't equal 0 because then G = 0 = A]. [E] now matches [B] so discard equation [E]. Let Z = J/(D-1) so that J = Z(D-1). Eliminate J from [B]. Divide [B] by (D-1). Let Y = G/(M-1) so that G = Y(M-1). Eliminate G from [B]. Divide [B] by (M-1). Solve [B] for D. M(Y^2)Z - 2M(Y^2) + MYZ + MY - 2MZ + M - (Y^2)Z + 2(Y^2) + Y(Z^2) - Y - 2(Z^2) + Z [B] D = ---------------------------------------------------------------------------------- (YZ + 2Y - 2Z - 1)(Z - 1) =============================================== Semi-Bimagic Square Solution =============================================== Pick rational values for M, Y, Z. Then compute D, G, J. M(Y^2)Z - 2M(Y^2) + MYZ + MY - 2MZ + M - (Y^2)Z + 2(Y^2) + Y(Z^2) - Y - 2(Z^2) + Z D = ---------------------------------------------------------------------------------- (YZ + 2Y - 2Z - 1)(Z - 1) G = Y(M - 1) J = Z(D - 1) Using D and J, compute C. J(D - J - 1) + D - 1 C = -------------------- D - J - 1 Using C, D, G, J, M, compute L, Q, and H. C^2(-G + M - 1) + C(GJ - JM + J - M + 1) - GM + G + JM - J L = ------------------------------------------------------------ C(-G + M - 1) + GJ - JM + J - M + 1 (D - G)(G + J - M + 1) + J(-J + M - 1) + M - 1 Q = ---------------------------------------------- D - G - J + M - 1 (M - 1)(G - M) H = -------------- G - M + 1 Then follow the semi-magic square solution. B = H+L+Q-C E = D+L+Q-G-1 I = G+H-M+1 K = D+M+Q-G-J-1 N = C+D-J-1 P = H+J+L-C-M+1 F = 1 A = 0 ------------------------- Inverse formula. Starting from a 4x4 semi-bimagic square with no duplicate entries, translate so that A = 0, divide so that F = 1, then Y = G / (M - 1) and Z = J / (D - 1). =============================================== Proofs of Duplication Lemmas =============================================== These are needed to be able to divide by (Z-1), (Y-1), (Y-Z), and (YZ-1) in the upcoming procedure. These expressions cannot be zero without leading to duplications in the semi-bimagic square. If (Z - 1) = 0 then from J = Z(D - 1) we have J = D - 1 but from [4], N = C+D-J-1 = C If (Y - 1) = 0 then from G = Y(M - 1) we have G = M - 1 but from [3], I = G+H-M+1 = H If (Y - Z) = 0 M(Z^3) - 2M(Z^2) + M(Z^2) + MZ - 2MZ + M - Z^3 + 2(Z^2) + Z^3 - Z - 2(Z^2) + Z D = ------------------------------------------------------------------------------ (Z - 1)(Z^2 + 2Z - 2Z - 1) or D = M If (YZ - 1) = 0 then Y = 1/Z and M/Z - 2M/Z^2 + M + M/Z - 2MZ + M - 1/Z + 2/Z^2 + Z - 1/Z - 2Z^2 + Z D = ------------------------------------------------------------------- (Z - 1)(1 + 2/Z - 2Z - 1) or M(1 - Z^2) - (1 + Z^3) D = --------------------- Z(1 - Z^2) Also, from J = Z(D-1) we have DZ(D-1) + D - Z(D-1)Z(D-1) - Z(D-1) - 1 C = --------------------------------------- D - Z(D-1) - 1 or Z^2 - Z + 1 C = DZ + ---------- 1 - Z and then substituting D into C, MZ(1 - Z^2) - Z(1 + Z^3) Z^2 - Z + 1 C = ------------------------ + ----------- Z(1 - Z^2) (1 - Z) or C = M =============================================== Nearly-Bimagic Square Additional Formulation =============================================== We need to add a bimagic diagonal D,G,J,M. This diagonal must have the same magic sum, thus [S1] D+G+J+M = D+H+L+Q or [S1] L = G+J+M-H-Q To be a bimagic diagonal, we must also have [S2] L^2 = G^2 + J^2 + M^2 - H^2 - Q^2 Use the square of [S1] to eliminate L^2 from [S2] [S2] (G+J+M-H-Q)(G+J+M-H-Q) = G^2 + J^2 + M^2 - H^2 - Q^2 Expand [S2] and divide by 2. [S1] L = G+J+M-H-Q [S2] -GH + GJ + GM - GQ + H^2 - HJ - HM + HQ + JM - JQ - MQ + Q^2 = 0 =============================================== Nearly-Bimagic Square Solving Procedure =============================================== Use the Semi-Bimagic Square Solution and eliminate the solved variables from [S1] and [S2]. Eliminate H from [S1] and [S2]. Eliminate Q from [S1] and [S2]. Eliminate L from [S1]. Eliminate C from [S1]. Eliminate J from [S1] adn [S2]. Divide [S1] by (D-1)(D-1). Eliminate G from [S1] and [S2]. Divide by [S1] by (M-1)(M-1). Divide [S2] by (M-1)(M-1). Eliminate D from [S1] and [S2]. Divide [S1] by (Z-1)(Z-1)(Y-Z)(YZ-1). Divide [S2] by (Z-1)(YZ-1)(YZ-1). Let X = (M-1)(Y-1) so that M = 1 + X/(Y-1). Eliminate M from [S1] and [S2]. Divide by [S1] by (Y-1)(Y-1). Divide [S2] by (Y-1)(Y-1)(Y-1)(Y-1). Let W = (Y-1)/(Z-1) so that Z = 1 + (Y-1)/W. Eliminate Z from [S1] and [S2]. Divide [S1] by (Y-1)(Y-1). Divide [S2] by (Y-1)(Y-1)(Y-1). Let V = (Y-2)/W so that Y = VW+2. Eliminate Y from [S1] and [S2]. Divide [S1] by W. Divide [S2] by W. [Note that if W = 0, then (Y-1) = 0, which has been proven to lead to duplicate entries]. solve [S1] for W. 2(2X-1)(V + 2X + 2) [S1] W = -------------------------------------------------------------- (V^2)(X^2) - 3(V^2)X + V^2 - 2V(X^2) - 6VX + 2V + X^2 - 7X + 1 Eliminate W from [S2]. Divide [S2] by 2(2X-1)(2X-1)(V+3). We can divide by (2X-1) because if (2X-1) = 0, then from [S1], W = 0, and then (Y-1) = 0. We can divide by (V+3) because if (V+3) = 0, then from [S1], we would have 2(2X-1)(2X-1) 2(2X-1)(2X-1) W = -------------- = ------------- 16XX - 16X + 4 4(2X-1)(2X-1) or W = 1/2 and from V = (Y-2)/W, we have Y = -1/2 and from W = (Y-1)/(Z-1), we have Z = -2 then following the semi-bimagic solution, we find that C = M. [S2] (V^4)(X^2 - X + 1)(X^2)(X - 1)^2 - (V^3)(X)(X - 1)(8X^3 - 13X^2 + 7X + 1) - (V^2)(2X^6 + 2X^5 - 38X^4 + 56X^3 - 23X^2 - X - 1) + (V)(8X^5 + 29X^4 - 64X^3 + 26X^2 + 5X + 2) + X^6 + 5X^5 + 20X^4 - 49X^3 + 20X^2 + 5X + 1 = 0 =============================================== Nearly-Bimagic Square Solution =============================================== Find rational values for X and V that satisfy f(X,V). f(X,V) = (V^4)(X^2 - X + 1)(X^2)(X - 1)^2 - (V^3)(X)(X - 1)(8X^3 - 13X^2 + 7X + 1) - (V^2)(2X^6 + 2X^5 - 38X^4 + 56X^3 - 23X^2 - X - 1) + (V)(8X^5 + 29X^4 - 64X^3 + 26X^2 + 5X + 2) + X^6 + 5X^5 + 20X^4 - 49X^3 + 20X^2 + 5X + 1 = 0 Use X and V to compute W. 2(2X-1)(V + 2X + 2) W = -------------------------------------------------------------- (V^2)(X^2) - 3(V^2)X + V^2 - 2V(X^2) - 6VX + 2V + X^2 - 7X + 1 Use V and W to compute Y. Y = VW + 2 Use Y and W to compute Z and M. Z = 1 + (Y-1)/W M = 1 + X/(Y-1) Then use M, Y, Z and follow the solution for the semi-bimagic square. ------------------ There are three real solutions of f(X,V) which also happen to be rational. (X = 0, V = -1) (X = 1/2, V = -3) (X = 1, V = -1) But they all lead to duplicate entries in the nearly-bimagic square. We need to prove that there are no other real solutions to f(X,V). In that way, we will have proved that all 4x4 nearly-bimagic squares of real entries always have duplicate entries. =============================================== No-Real-Root Support Theorem =============================================== There is a theorem we can use from the book, "First Course in the Theory of Equations" by Leonard E. Dickson. This is available on the Internet from Project Gutenberg. Page 91 has the following theorem. Given a quartic polynomial in the following form. z^4 + qz^2 + rz + s = 0 Let L = 8qs - 2q^3 - 9r^2 P = -4s - (1/3)q^2 Q = (8/3)qs - r^2 - (2/27)q^3 D = -4P^3 - 27Q^2 If D < 0, then the quartic has two real roots and two complex roots. If D > 0 and q < 0 and L > 0, then the quartic has four real roots. If D > 0 and either q >= 0 or L <= 0, then the quartic has no real roots. We will use this theorem to prove that the f(X,V) equation has only the three real solutions given above. =============================================== No-Real-Root Proof =============================================== f(X,V) is a quartic polynomial in V with coefficients in X. f(X,V) = aV^4 + bV^3 + cV^2 + dV + e = 0 where a = (X^2-X+1)(X^2)(X-1)^2 b = (X)(X-1)(-8X^3 + 13X^2 - 7X - 1) c = (-2X^6 - 2X^5 + 38X^4 - 56X^3 + 23X^2 + X + 1) d = (8X^5 + 29X^4 - 64X^3 + 26X^2 + 5X + 2) e = (X^6 + 5X^5 + 20X^4 - 49X^3 + 20X^2 + 5X + 1) To convert to the form used in the no-real-root theorem, we first divide all terms by a. V^4 + (b/a)V^3 + (c/a)V^2 + (d/a)V + (e/a) = 0 Second, we have to eliminate the cubic term in the polynomial. Let z = V + (1/4)(b/a) so that V = [z - (1/4)(b/a)]. This produces z^4 + z^2[8ac - 3b^2] / (8a^2) + z[8da^2 + b^3 - 4abc] / (8a^3) + [256ea^3 + 16acb^2 - 64bda^2 - 3b^4] / (256a^4) = 0 Substituting the X-expressions for a,b,c,d,e produces z^4 + z^2 (1/8) (1/a^2) X^2 (X-1)^2 (2X-1)^2 (-4X^6 - 4X^5 + 25X^4 - 10X^3 + 7X^2 - 22X + 5) + z (1/8) (1/a^3) X^3 (X-1)^3 (2X-1)^3 (18X^7 - 3X^6 - 15X^5 + 18X^4 - 39X^3 + 42X^2 - 9X - 3) + (1/256) (1/a^4) X^4 (X-1)^4 (2X-1)^4 (16X^12 + 32X^11 + 296X^10 - 984X^9 + 2173X^8 - 3500X^7 + 3922X^6 - 3200X^5 + 2143X^4 - 888X^3 + 50X^2 + 116X + 13) = 0 So now we have the form z^4 + qz^2 + rz + s. q = - q' (1/8) (1/a^2) X^2 (X-1)^2 (2X-1)^2 where q' = (4X^6 + 4X^5 - 25X^4 + 10X^3 - 7X^2 + 22X - 5) r = r' (1/8) (1/a^3) X^3 (X-1)^3 (2X-1)^3 where r' = (18X^7 - 3X^6 - 15X^5 + 18X^4 - 39X^3 + 42X^2 - 9X - 3) s = s' (1/256) (1/a^4) X^4 (X-1)^4 (2X-1)^4 where s' = (16X^12 + 32X^11 + 296X^10 - 984X^9 + 2173X^8 - 3500X^7 + 3922X^6 - 3200X^5 + 2143X^4 - 888X^3 + 50X^2 + 116X + 13) Note that for any real value of X other than 0, 1/2, 1, if q' < 0, then q > 0. Compute L, P, Q, and D from q, r, and s. [L,P,Q,D are being reused for this proof and are not entries in the magic square]. L = - L' (3/2) (1/a^6) X^6 (X-1)^6 (2X-1)^6 (X^2-X+1)^2 where L' = (5X^12 + 6X^11 + 3X^10 + 40X^9 - 100X^8 + 50X^7 - 31X^6 + 38X^5 + 44X^4 - 60X^3 + 11X^2 + 2X + 1) Note that for any real value of X other than 0, 1/2, 1, if L' > 0 then L < 0. P = - (1/3) (1/a^4) X^4 (X-1)^4 (2X-1)^4 (X^2-X+1)^2 (X^8 + 4X^7 + 16X^6 - 26X^5 + 19X^4 - 26X^3 + 16X^2 + 4X + 1) Q = (2/27) (1/a^6) X^6 (X-1)^6 (2X-1)^6 (X^2-X+1)^3 (-X^12 - 6X^11 - 30X^10 - 5X^9 + 117X^8 - 162X^7 + 147X^6 - 162X^5 + 117X^4 - 5X^3 - 30X^2 - 6X - 1) D = D' (36) (1/a^12) X^16 (X-1)^16 (2X-1)^12 (X^2-X+1)^8 where D' = (X^8 + 4X^7 + 22X^6 - 32X^5 + 19X^4 - 32X^3 + 22X^2 + 4X + 1) Note that for any real value of X other than 0, 1/2, 1, if D' > 0, then D > 0. The equation D' = 0 has four pairs of complex roots. -2.637255 +- i(4.567860) -0.223954 +- i(0.974600) -0.094796 +- i(0.164191) 0.956005 +- i(0.293350) Since D' = 0 has no real roots and its highest polynomial coefficient is positive, any real value of X will produce D' > 0. The equation L' = 0 hs two real roots and five pairs of complex roots. -2.915408 -0.808553 -0.243865 +- i(1.008520) -0.103303 +- i(0.177053) 0.046294 +- i(2.153288) 0.631770 +- i(0.161758) 0.931085 +- i(0.289380) Since the highest polynomial coefficient is positive, L' > 0 for X < -2.915408 L' < 0 for -2.915408 < X < -0.808553 L' > 0 for -0.808553 < X The equation q' = 0 has four real roots and one pair of complex roots. -3.257298 0.243358 1.142409 1.627794 -0.378131 +- i(0.839641) Since the highest polynomial coefficient is positive, q' > 0 for X < -3.257298 q' < 0 for -3.257298 < X < 0.243358 q' > 0 for 0.243358 < X < 1.142409 q' < 0 for 1.142409 < X < 1.627794 q' > 0 for 1.627794 < X Conclusion. For any real value of X other than 0, 1/2, or 1, D' > 0 thus D > 0. L' >= 0 thus L <= 0 when X <= -2.915408 q' < 0 thus q > 0 when -2.915408 <= X <= -0.808553 L' >= 0 thus L <= 0 when -0.808553 <= X Therefore there are no real solutions of f(X,V) other than when X = 0, 1/2, 1. =============================================== Additional Remarks =============================================== Although a distinct real number solution is impossible, a complex number solution is definitely possible. There might even be a 19-correct-line solution using distinct Gaussian integers.