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