4. ТЕОРИЯ МАГИЧЕСКИХ КВАДРАТОВ 4-ГО ПОРЯДКА.

Числа.
Преобразования.
Квадраты.
Квадраты и преобразования.

4.1. Числа.

Как правило под "числом" мы будем иметь в виду неотрицательное целое число.

Обозначение 4.1:1: Для n>0 через I(n) обозначим множество целых чисел от 0 до n-1.

Мы будем рассматривать также двоичное представление числа. Если xI(2^m), то x имеет m двоичных разрядов 0,1,...,m-1.

Обозначение 4.1:2: Для xI(2^m) и rI(m) через x|r обозначим значение r-го двоичного разряда числа x.

m-1

xI(2^m) однозначно раскладывается x = 2^r*(x|r)

r=0

Определение 4.1:1: Для xI(2), то есть x=0,1, его отрицанием называется число x, определяемое следующим образом:

x = 0, если x=1

1, если x=0

Определение 4.1:2: Для xI(2^m) его отрицанием называется число x, которое есть поразрядное отрицание x, то есть число, в котором значение каждого двоичного разряда есть отрицание значения соответствующего разряда числа x: rI(m) (x)|r = (x|r). Числа x и x будем называть взаимно-инвертированными.

Определение 4.1:3: Для x,yI(2), то есть x,y=0,1, исключающей дизъюнкцией чисел x и y называется число xy, определяемое следующим образом:

xy = 0, если x=y

1, если xy0

Определение 4.1:4: Для x,yI(2^m) исключающей дизъюнкцией чисел x и y называется число xy, которое есть поразрядная исключающая дизъюнкция x и y, то есть число, в котором значение каждого двоичного разряда есть исключающая дизъюнкция значений соответствующих разрядов чисел x и y: rI(m) (xy)|r = (x|r)(y|r). Число y, фактически, задаёт те двоичные разряды числа x, которые инвертируются при переходе к xy.

Теорема 4.1:1: x,yI(2^m) (x)y = (xy).

Доказательство:

Это утверждение легко проверяются для m=1 (Определения 1,3) и очевидным образом распространяется для поразрядных операций (Определения 2,4).

4.2. Преобразования.

Обозначение 4.2:1: Группу всех взаимно-однозначных преобразований (подстановок) множества I(n) по операции умножения преобразований, определяемой как их последовательное выполнение, иначе называемую группой подстановок, или симметрической группой, степени n, обозначим через (n). Тождественное преобразование (единица группы) будем обозначать .

Обозначение 4.2:2: Подстановку (n) множества I(n) можно записать в виде:

n-1, n-2, ...,1, 0 или, считая верхний ряд фиксированным:

(n-1),(n-2),...,1,0 ( (n-1),(n-2),...,1,0 )

4.2.1. Инвертирующие преобразования.

Теорема 4.2.1:1: Множество I(2^m) по операции является коммутативной группой со следующими свойствами:

единицей группы является число 0: aI(2^m) 0a=a;
каждое число обратно самому себе: a I(2^m) aa=0;
aI(2^m) a(2^m-1) = a, aa=(2^m-1).

Доказательство:

Ассоциативность операции: a,b,cI(2^m) a(bc)=(a b)c.
Коммутативность операции: a,bI(2^m) ab=ba.
Единицей группы является число 0: aI(2^m) 0a=a;
Каждое число обратно самому себе: aI(2^m) aa=0;
aI(2^m) a(2^m-1)= a, aa=(2^m-1).

Все эти свойства легко проверяются для m=1 (Определения 4.1:1,3) и очевидным образом распространяется для поразрядных операций (Определения 4.1:2,4).

Обозначение 4.2.1:1: Для tI(2^m) отображение :I(2^m)I(2^m), определяемое xI(2^m) x=xt, будем обозначать (t).

Теорема 4.2.1:2: Если tI(2^m), то отображение (t) является подстановкой множества I(2^m), то есть (t)(2^m).

Доказательство:

Нужно доказать, что отображение (t) является биекцией (взаимно-однозначным отображением) I(2^m) на I(2^m), то есть оно a) инъективно и b) сюръективно.

a) Отображение (t) инъективно, то есть разным x соответствуют разные x(t): x₁,x₂I(2^m) x₁x₂ x₁(t)x₂(t).

Действительно, если x₁x₂, то rI(m) x₁|r x₂|r, поэтому, как непосредственно следует из определения операции , (x₁|r)(t|r) (x₂|r)(t|r) x₁t x₂t, то есть x₁(t) x₂(t).

b) Отображение (t) сюръективно, то есть это отображение I(2^m) на I(2^m), то есть xI(2^m) yI(2^m) такое, что yt()=x.

Действительно, если y=xt, то yt()=yt=(xt)t=x(tt)=x0=x.

Определение 4.2.1:1: Для tI(2^m) преобразование =(t), определяемое xI(2^m) x(t)=xt, назовём инвертирующим порядка 2^m, поскольку определяется инвертированием некоторых двоичных разрядов чисел из I(2^m).

Теорема 4.2.1:3: Число инвертирующих преобразований порядка 2^m равно 2^m.

Доказательство очевидно.

Обозначение 4.2.1:2: Множество инвертирующих преобразований обозначим T(2^m) и для T(2^m) соответствующее число tI(2^m) будем обозначать t=t().

Теорема 4.2.1:4: Множество T(2^m) есть подгруппа группы T(2^m) изоморфная группе I(2^m) по операции.

Доказательство:

Соответствие =(t) можно рассматривать как соответствие I(2^m) и T(2^m). Оно, очевидно:

a) является отображением, то есть каждому tI(2^m) ставит в соответствие только одно (t) в силу определения (t);

b) сюръективно, то есть это отображение I(2^m) на T(2^m) в силу определения T(2^m);

c) инъективно, то есть t₁,t₂I(2^m) t₁t₂ (t₁)(t₂);
действительно, t₁ t₂ 0t₁ 0t₂, то есть 0(t₁) 0(t₂).

Для доказательства изоморфизма нужно показать, что (t₁t₂) = (t₁)(t₂). Действительно, xI(2^m) x(t₁t₂) = x(t₁t₂) = (xt₁)t₂ = (x(t₁))t₂) = (x(t₁))(t₂) = x((t₁)(t₂)).

Теорема 4.2.1:5: Инвертирующее преобразование, обратное данному инвертирующему преобразованию, совпадает с ним самим: T(2^m) ^-1=.

Доказательство:

xI(2^m) x() = (x) = (xt()) = (xt())t() = x(t()t()) = x0 = x. Поэтому ^-1=.

Теорема 4.2.1:6: Подгруппа T(2^m)имеет систему образующих из m преобразований _r = (2^r), где rI(m).

Доказательство:

	m-1
Поскольку tI(2^m) можно однозначно представить в виде t =		2^r*(x\|r)
	r=0

и поскольку операция определена поразрядно, доказательство теоремы очевидно.

4.2.2. Перестановочные преобразования.

Теорема 4.2.2:1: Если {M,} - группа на множестве M с операцией , и на том же множестве M определена операция : x,yM xy=yx, то {M,} будет группой, изоморфной группе {M,}.

Доказательство:

Рассмотрим отображение :MM, ставящее в соответствие каждому элементу его обратный элемент в группе {M,}: xM x=x^-1. Очевидно, что есть взаимно-однозначное отображение M на M. Для доказательства изоморфизма осталось показать, что (xy)=xy. Действительно: (xy)=(yx)=(yx)^-1=x^-1y^-1=xy.

Обозначение 4.2.2:1: Для (m) отображение :I(2^m)I(2^m), определяемое xI(2^m) rI(m) (x)|r=x|(r) будем обозначать ().

Теорема 4.2.2:2: Если (m), то отображение () является подстановкой множества I(2^m), то есть ()(2^m).

Доказательство:

Нужно доказать, что отображение () является биекцией (взаимно-однозначным отображением) I(2^m) на I(2^m), то есть оно a) инъективно и b) сюръективно.

a) Отображение () инъективно, то есть разным x соответствуют разные x(): x₁,x₂I(2^m) x₁x₂ x₁()x₂().

Действительно, если x₁x₂, то rI(m) x₁|rx₂|r. В силу того, что - подстановка множества I(m), r₁I(m) r=r₁ и значит x₁|(r₁)x₂|(r₁), то есть x₁()x₂().

b) Отображение () сюръективно, то есть это отображение I(2^m) на I(2^m), то есть xI(2^m) yI(2^m) такое, что y()=x.

Действительно, если y=x(^-1), то rI(2^m) (y())|r=y|(r)=(x(^-1))|(r)=x|((r)^-1)=x|(r(^-1))=x|r, то есть y() и x совпадают по всем двоичным разрядам и значит x=y().

Определение 4.2.2:1: Для (m) преобразование =(), определяемое xI(2^m) rI(m) (x)|r=x|(r), назовём перестановочным порядка 2^m, поскольку определяется некоторой перестановкой двоичных разрядов чисел из I(2^m).

Теорема 4.2.2:3: Число перестановочных преобразований порядка 2^m равно m!.

Доказательство очевидно.

Обозначение 4.2.2:2: Множество перестановочных преобразований обозначим P(2^m) и для P(2^m) соответствующую подстановку (m) будем обозначать =().

Теорема 4.2.2:4: Множество P(2^m) есть подгруппа группы (2^m) изоморфная группе (m).

Доказательство:

Соответствие =() можно рассматривать как соответствие (m) и P(2^m). Оно, очевидно:

a) является отображением, то есть каждому (m) ставит в соответствие только одно () в силу определения ();

b) сюръективно, то есть это отображение (m) на (2^m) в силу определения P(2^m);

c) инъективно, то есть ₁,₂(m) ₁₂ (₁)(₂); действительно, ₁₂ rI(m) r₁r₂, и значит для x, имеющего "1" в разряде r₁ и "0" в разряде r₂, x|(r₁) x|(r₂), то есть (x(₁))|r (x(₂))|r.

Теперь покажем, что (₁₂)= (₂) (₁). Действительно, xI(2^m) rI(m) (x (₁₂))|r=x|(r(₁₂))=x|((r₁)₂)=(x (₂))|(r₁)=((x (₂)) (₁))|r=(x( (₂) (₁)))|r.

Таким образом, (m) изоморфно P(2^m) с операцией "обратного последовательного выполнения преобразований". В силу теоремы 1 (m) изоморфно также P(2^m) с нормальной операцией "прямого последовательного выполнения преобразований".

Теорема 4.2.2:5: Перестановочное преобразование, обратное данному перестановочному преобразованию, определяется перестановкой двоичных разрядов чисел, обратной перестановке, определяющей данное перестановочное преобразование: P(2^m) (^-1)=(( ))^-1.

Доказательство:

xI(2^m) 2 rI(m) x(()(^-1))|r = ((x())(^-1)|r = (x())|(r^-1) = x|((r^-1)) = x|(r(^-1)) = x|(r) = x|r.

Поэтому ()(^-1)=, то есть ()^-1 = (^-1), то есть (^-1)=(( ))^-1.

Теорема 4.2.2:6: Подгруппа P(2^m) имеет систему образующих из двух элементов: ₀ = (₀) и ₁ = (₁), где

₀ = (m-2,m-1,...,3,2,0,1) - транспозиция чисел 0 и 1
₁ = (m-2,m-3,...,1,0,m-1) - циклический сдвиг всех элементов

Доказательство: Согласно известной теореме теории групп, (m) имеет систему образующих { ₀,₁}. Поскольку (m) изоморфно (2^m), теорема доказана.

4.2.3. Логические преобразования.

Определение 4.2.3:1: Логическим преобразованием порядка 2^m назовём преобразование, которое является преобразованием или произведением нескольких преобразований, каждое из которых - это инвертирующее или перестановочное преобразование порядка 2^m.

Обозначение 4.2.3:1: Множество логических преобразований обозначим (2^m).

Теорема 4.2.3:1: Множество логических преобразований (2^m) является подгруппой группы (2^m).

Доказательство очевидно.

Теорема 4.2.3:2: Группы T(2^m) и P(2^m) имеют единственный общий элемент - тождественное преобразование: T(2^m)P(2^m)=.

Доказательство:

Пусть T(2^m) P(2^m); t=t() =(). Поскольку , t 0 и поэтому t0 ( не изменяет количество "1" в двоичном представлении числа), но t=tt=0. Следовательно, tt и, значит, .

Лемма 4.2.3:1: x,yI(2^m) P(2^m) (xy)=(x)(y).

Доказательство:

Пусть =().

rI(m) ((xy))|r = (по определению )

= (xy)|(r) = (по определению )

= (x|(r))(y|(r)) = (по определению )

= ((x)|r)((y)|r) = (по определению )

= ((x)(y))|r.

Следовательно, (xy)=(x)(y), что и требовалось доказать.

Теорема 4.2.3:3: Группа T(2^m) перестановочна с любым преобразованием из P(2^m): P(2^m) T(2^m)= T(2^m). Как следствие подгруппы T(2^m) и P(2^m) перестановочны: T(2^m)P(2^m) = P(2^m)T(2^m).

Доказательство:

Нужно доказать, что P(2^m) T(2^m) ₁,₂T(2^m) такие, что = и = ₂.

Обозначая t=t(), возьмём t₁=t^-1 и, соответственно, ₁=(t₁). Тогда t=t₁ и xI(2^m) x() = (x) = (x)t = (x)(t₁) = (по Лемме 1) = (xt₁) = (x₁) = x(₁). Итак: xI(2^m) x() = x(₁), то есть = ₁. Если теперь t₂ =t, то t=t₂^-1 и для ₂ = (t₂), как только что доказано, ₂ = .

Теорема 4.2.3:4: Подгруппа (2^m), порождённая подгруппами T(2^m) и P(2^m) группы (2^m), совпадает с произведением подгрупп T(2^m)P(2^m)= P(2^m)T(2^m) и каждое преобразование (2^m) однозначно раскладывается в произведение инвертирующего и перестановочного преобразований =, или, столь же однозначно, - в произведение перестановочного и инвертирующего преобразований =₁₁, где ,₁T(2^m) и ,₁P(2^m).

Доказательство:

1) То, что (2^m)= T(2^m)P(2^m) следует (Курош,50) из перестановочности T(2^m)P(2^m) = P(2^m)T(2^m). Таким образом (2^m) можно представить как произведения ==₁₁, где ,₁T(2^m) и ,₁P(2^m).

2) Если =₁₁=₂₂, то ₁=₂ и ₁=₂. Действительно, из ₁₁=₂₂ следует ₁=₂₂₁^-1 и ₂^-1₁=₂₁^-1, но левая часть этого равенства T(2^m), а правая часть P(2^m) и значит, по теореме 2, ₂^-1₁==₂₁^-1, поэтому ₁=₂ и ₁=₂.

3) Аналогично, если =₁₁=₂₂, то ₁=₂ и ₁=₂. Действительно, из ₁₁=₂₂ следует ₁=₁^-1₂₂и ₁₂^-1=₁^-1₂, но левая часть этого равенства T(2^m), а правая часть P(2^m) и значит, по теореме 2, ₁₂^-1==₁^-1₂, поэтому ₁=₂ и ₁=₂.

Теорема 4.2.3:5: Число логических преобразований порядка 2^m равно произведению числа инвертирующих преобразований порядка 2^m и числа перестановочных преобразований порядка 2^m, то есть 2^m*m!.

Доказательство непосредственно следует из теоремы 4.

Теорема 4.2.3:6: Группа (2^m) имеет систему образующих из трёх преобразований: ₀= (₀), ₁= (₁) и ₀=(1), где

₀=(m-2,m-1,...,3,2,0,1) - транспозиция чисел 0 и 1
₁=(m-2,m-3,...,1,0,m-1) - циклический сдвиг всех элементов

Доказательство:

Поскольку (2^m) можно представить в виде произведения =, где T(2^m) и P(2^m), и поскольку подгруппы T(2^m) и P(2^m) имеют по теоремам 4.2.1:6 и 4.2.2:6 системы образующих, соответственно, {_i}, где iI(m), и {₀,₁}, то эти две системы образующих в совокупности образуют систему {_i,₀,₁} образующих (2^m).

Легко показать, что iI(m) _i=_i₀_i, где _iP(2^m) и (_i)=(m-1,m-2,...,i+1,0,i-1,...,2,1,i) - транспозиция чисел 0 и i.

Таким образом, (2^m) можно представить в виде произведений ₀, ₁ и _i, где iI(m); далее, раскладываем _i для i>0 в произведение ₀ и перестановочных преобразований; далее каждое перестановочное преобразование раскладываем в произведение ₀, ₁; в результате разложится в произведение трёх преобразований ₀, ₀, ₁. Поэтому система образующих подгруппы (2^m) состоит из трёх преобразований: ₀= (₀), ₁= (₁) и ₀=(1).

4.3. Квадраты.

Определение 4.3:1: Квадратом порядка n назовём матрицу nxn, элементы которой - это все числа из I(n²), то есть каждое целое число от 0 до n²-1 встречается как элемент матрицы и только один раз.

Очевидно, квадрат - это подстановка множества I(n²).

Обозначение 4.3:1: Множество квадратов порядка n обозначим K(n).

Очевидно, K(n)=(n²).

Обозначение 4.3:2: Если kK(n) и i,jI(n), то через k[i,j] обозначим число в i-ой строке и j-ом столбце квадрата k, то есть, учитывая, что k - это подстановка множества I(n²), k[i,j]=(ni+j)k.

4.3.1. Магичность.

Определение 4.3.1:1: Набор n чисел из I(n²) назовём магическим, если сумма этих чисел равна (n²-1)n/2, то есть 1/n от суммы всех чисел из I(n²). Эта сумма (n²-1)n/2 называется магической и обозначается s(n).

Определение 4.3.1:2: Квадрат kK(n) назовём магическим (m-квадратом), если в нём каждая строка, каждый столбец и каждая диагональ - магические, то есть имеют место равенства:

n-1 n-1

iI(n) k[i,j]=s(n) jI(n) k[i,j]=s(n)

j=0 i=0

n-1 n-1

k[i,i]=s(n) k[i,n-1-i]=s(n)

i=0 i=0

Обозначение 4.3.1:1: Множество m-квадратов порядка n обозначим M(n).

4.3.2. Равномерность.

Определение 4.3.2:1: Набор n=2^m чисел x_iI(2^2m), где iI(2^m), назовём равномерным, если в каждом двоичном разряде rI(2m) эти числа имеют поровну "1" и "0", то есть:

n-1 2^m-1

rI(2m) x_i|r = x_i|r = n/2 = 2^m-1

i=0 i=0

Определение 4.3.2:2: Квадрат kK(2^m) назовём равномерным (r-квадратом), если в нём каждая строка, каждый столбец и каждая диагональ равномерные, то есть rI(2m) имеют место равенства:

2^m-1 2^m-1

iI(2^m) k[i,j]|r=2^m-1 jI(2^m) k[i,j]|r=2^m-1

j=0 i=0

2^m-1 2^m-1

k[i,i]|r=2^m-1 k[i,2^m-1-i]|r=2^m-1

i=0 i=0

Обозначение 4.3.2:1: Множество r-квадратов порядка 2^m обозначим R(2^m).

4.3.3. Симметричность.

Определение 4.3.3:1: Два числа назовём симметричными порядка n, если их сумма равна n²-1=2s(n)/n.

Теорема 4.3.3:1: Симметричные числа порядка 2^m взаимно-инвертированы, то есть если x+y=(2^m)²-1=2^2m-1, то x=y.

Доказательство очевидно.

Определение 4.3.3:2: Квадрат kK(n) назовём симметричным (c-квадратом), если в его центрально-симметричных клетках находятся симметричные числа порядка n, то есть:

i,jI(n) k[i,j]+ k[n-1-i,n-1-j]=n²-1.

Обозначение 4.3.3:1: Множество c-квадратов порядка n обозначим C(n).

Обозначение 4.3.3:2: Магические равномерные симметричные квадраты будем называть s-квадратами. Множество s-квадратов порядка 2^m обозначим S(2^m)= M(2^m)C(2^m)R(2^m).

4.3.4. Пять типов квадратов 4-го порядка.

Формально 3 базовых свойства квадрата: магичность, равномерность и симметричность разбивают множество всех квадратов порядка 2^m на 2³=8 подмножеств K_i:

Мы покажем, что при m=2 только 5 из этих множеств непусты: K₀=K\(MCR), K₂=C\(MR), K₄=M\(CR), K₅=(MR)\C, K₇=MCR=S, то есть RM, MCR и S=MCR=MC=CR.

Обозначение 4.3.4:1:

M=M(4)	C=C(4)	R=R(4)	S=S(4)
K=K(4)=(16)=	T=T(16)	P=P(16)	=(16)

Обозначение 4.3.4:2: Шестнадцатиричные цифры будем обозначать так:

0= 0₁₀	1= 1₁₀	2= 2₁₀	3= 3₁₀	4= 4₁₀	5= 5₁₀	6= 6₁₀	7= 7₁₀
8= 8₁₀	9= 9₁₀	A=10₁₀	B=11₁₀	C=12₁₀	D=13₁₀	E=14₁₀	F=15₁₀

Теорема 4.3.4:1: Множество K₀=K\(MCR) непусто, то есть существует числовой квадрат 4-го порядка, не являющийся ни магическим, ни равномерным, ни симметричным.

Доказательство:

1023
4567
89AB
CDEF

Теорема 4.3.4:2: Множество K₂=C\(MR) непусто, то есть существует симметричный квадрат 4-го порядка, не являющийся ни магическим, ни равномерным.

Доказательство:

0123
4567
89AB
CDEF

Теорема 4.3.4:3: Множество K₄=M\(CR) непусто, то есть существует магический квадрат 4-го порядка, не являющийся ни симметричным, ни равномерным.

Доказательство:

F41A
97C2
683D
0BE5

Теорема 4.3.4:4: Множество K₅=(MR)\C непусто, то есть существует магический равномерный квадрат 4-го порядка, не являющийся симметричным.

Доказательство:

F21C
58B6
A749
0DE3

Теорема 4.3.4:5: Множество K₇=MCR=S непусто, то есть существует магический равномерный симметричный квадрат 4-го порядка.

Доказательство:

F21C
49A7
856B
3ED0

Квадрат Дюрера s_d

Теорема 4.3.4:6: Равномерный квадрат порядка 2^m является магическим. Как следствие, RM, S=CR. и множества K₁=R\(MC) и K₃=(CR)\M пусты.

Доказательство:

Учитывая разложение числа по степеням двойки (4.1), для ряда (строки, столбца или диагонали) чисел x_i, где iI(2^m), любого квадрата kK(2^m) можно записать:

2^m-1 2^m-1 2m-1 2m-1 2^m-1 2m-1 2^m-1

s = x_i = 2^r*(x_i|r) = 2^r*(x_i|r) = 2^r (x_i|r)

i=0 i=0 r=0 r=0 i=0 r=0 i=0

		2^m-1
Для равномерного квадрата rI(2m)	имеет место равенство	(x_i\|r)	= 2^m-1
		i=0

		2m-1
Поэтому	s =		2^r*2^m-1 =	(2^2m -1)2^m-1 = ((2^2m -1)2^m)/2 = s(2^m)
		r=0

Теорема 4.3.4:7: Магический симметричный квадрат 4-го порядка является равномерным, то есть MCR, S=MC и множество K₆=(MC)\R пусто.

Вначале мы докажем три леммы.

Лемма 4.3.4:1: В симметричном магическом квадрате 4-го порядка числа "угловых" подквадратов образуют магический ряд:

k[0,0]

k[0,1]

k[0,2]

k[0,3]

	1	1
a,bI(2)			k[2a+i,2b+j] = s(4)
	i=0	j=0

q₀

q₁

k[1,0]

k[1,1]

k[1,2]

k[1,3]

k[2,0]

k[2,1]

k[2,2]

k[2,3]

q₂

q₃

k[3,0]

k[3,1]

k[3,2]

k[3,3]

Доказательство:

При повороте симметричного магического квадрата на 90^o получается, очевидно, тоже симметричный магический квадрат. Поэтому лемму достаточно доказать для подквадрата q₀. С учётом симметричности квадрата k его можно записать в виде (симметричные числа порядка 4 взаимно-инвертированы и их сумма равна F - теорема 4.3.3:1):

k[0,0] k[0,1] k[0,2] k[0,3]

k[1,0] k[1,1] k[1,2] k[1,3]

F- k[1,3] F- k[1,2] F- k[1,1] F- k[1,0]

F- k[0,3] F- k[0,2] F- k[0,1] F- k[0,0]

Запишем условия магичности для строк 0,1 и столбцов 0,1 (для квадрата 4-го порядка s(4)=1E):

k[0,0] + k[0,1] +    k[0,2] +    k[0,3] = 1E
k[1,0] + k[1,1] +    k[1,2] +    k[1,3] = 1E
k[0,0] + k[1,0] + F- k[1,3] + F- k[0,3] = 1E
k[0,1] + k[1,1] + F- k[1,2] + F- k[0,2] = 1E

Складывая эти равенства, получим:

2*( k[0,0] + k[0,1] + k[1,0] + k[1,1]) +4*F = 2*1E

Поэтому k[0,0] + k[0,1] + k[1,0] + k[1,1] = 1E, то есть лемма доказана для подквадрата q₀.

Лемма 4.3.4:2: Диагонали симметричного квадрата 4-го порядка магичны.

Доказательство:

4 клетки диагонали квадрата - это две пары центрально-симметричных клеток. Поэтому на каждой диагонали находятся две пары симметричных чисел 4-го порядка. Сумма чисел каждой пары равна F и поэтому сумма всех четырёх чисел диагонали равна 1E, то есть магической сумме.

Лемма 4.3.4:3: Теорему 7 достаточно доказать для строки 0.

Доказательство:

Учитывая лемму 2, теорему 7 нужно доказывать для строк и столбцов. Доказательство леммы строится на том, что для каждой строки и каждого столбца существует преобразование квадрата, сохраняющее симметричность и магичность квадрата, и такое, что оно переводит эту строку или столбец в строку 0.

Для строки 3, столбцов 0 и 3 такое преобразование - это поворот квадрата на 180^o, 90^o и 270^o по часовой стрелке, соответственно. Для строки 1 это "перекрещивающее" преобразование вида (см. 3.3, преобразование ₁₃):

k[0,0]

k[1,1]
k[0,1]

k[1,0]
k[0,2]

k[1,3]
k[0,3]

k[1,2]
k[2,0]

k[3,1]
k[2,1]

k[3,0]
k[2,2]

k[3,3]
k[2,3]

k[3,2]

строка 1

строка 0
строка 0

строка 1
строка 3

строка 2
строка 2

строка 3
столбец 1

столбец 0
столбец 0

столбец 1
столбец 3

столбец 2
столбец 2

столбец 3

Диагонали остаются на месте.

Центрально-симметричные клетки переходят в центрально-симметричные клетки

Для строки 2 и столбцов 1 и 2 такое преобразование - это сочетание "перекрещивающего" преобразования и поворота по часовой стрелке на 180^o, 90^o и 270^o, соответственно.

Доказательство теоремы 7:

Согласно лемме 3 будем доказывать равномерность строки 0.

1) Сначала докажем равномерность строки 0 для двоичного разряда 0, то есть, что в разряде 0 числа строки 0 имеют две "1" и два "0".

Поскольку магическая сумма 4-го порядка чётная (1E), числа любой строки (в том числе и строки 0) должны иметь в 0-м разряде чётное число "1": 0, 2 или 4. Допустим, что в 0-м разряде чисел строки 0 находятся 0 или 4 "1" и постараемся придти к противоречию.

Если в 0-м разряде чисел строки 0 четыре "1", то в строке 3, состоящей из клеток центрально-симметричных клеткам строки 0, числа имеют в 0-м разряде ноль "1" (все четыре "0"). Повернём квадрат на 180^o и будем в новом симметричном магическом квадрате рассматривать строку 0. Итак, можно считать, что в строке 0 числа имеют в 0-м разряде все "0".

Числа строки 1 не могут иметь в 0-м разряде все "0", так как в противном случае мы получаем сумму всех восьми чётных чисел (в строках 0 и 1), равную удвоенной магической сумме 2*1E, а на самом деле она равна 0+2+4+6+8+A+C+E=2*1C.

Точно также числа строки 1 не могут содержать в разряде 0 все "1", так как тогда строка 2 как центрально-симметричная строке 1 состоит из чисел, имеющих в 0-м разряде все "0" и опять сумма всех восьми чётных чисел (в строках 0 и 2) оказывается равной 2*1E, что неверно.

Значит строка 1 содержит 2 чётных и 2 нечётных числа. Поскольку согласно лемме 1 сумма чисел в угловых подквадратах магическая, то есть чётна, очевидно строки 0 и 1 в 0-м разряде выглядят:

0000 или 0000
0011     1100

Из условия симметричности следует, что весь квадрат в 0-м разряде выглядит:

0000 или 0000
0011     1100
1100     0011
1111     1111

В обоих случаях на диагоналях получается нечётное число нечётных чисел, чего быть не может.

Итак, доказано, что числа строки 0 имеют в 0-м разряде две "1" и, соответственно, два "0".

2) При суммировании четырёх чисел строки 0, очевидно, будет перенос "1" в 1-ый разряд и, поскольку, магическая сумма 1E содержит "1" в 1-ом разряде, числа строки 0 должны иметь в 1-ом разряде чётное число "1": 0, 2 или 4.

Рассуждения для разряда 0 теперь полностью повторяются для разряда 1, так как сумма всех восьми чисел, имеющих "0" в 1-ом разряде, равна 0+1+4+5+8+9+C+D=2*1A 2*1E.

3) Рассуждения для разряда 1 повторяются для разряда 2 с учётом того, что сумма всех восьми чисел, имеющих "0" во 2-ом разряде, равна 0+1+2+3+8+9+A+B=2*16 2*1E.

4) Рассуждения для разряда 2 повторяются для разряда 3 с учётом того, что сумма всех восьми чисел, имеющих "0" в 3-ем разряде, равна 0+1+2+3+4+5+6+7=2*10 2*1E.

Итак, теорема 7 доказана.

4.4. Квадраты и преобразования.

4.4.1. Преобразование чисел как преобразование квадратов.

Каждое преобразование чисел (n) естественно расширяется до преобразования квадратов ': K(n)K(n) следующим образом: i,jI(n) k'[i,j]= k[i,j].

Говоря о преобразованиях чисел из (n²) как преобразованиях квадратов, мы будем без специальных оговорок иметь в виду такие расширения.

Теорема 4.4.1:1: Расширение ' есть гомоморфизм группы (n²) преобразований множества I(n²) в группу преобразований множества K(n)=(n²) по операции умножения преобразований: ,(n²) ()'= ''.

Доказательство:

,(n²) i,jI(n) k()'[i,j] = k[i,j]() = (k[i,j]) = (k'[i,j]) = (k')'[i,j] = k('')[i,j].

4.4.2. Квадраты как преобразования. Умножение.

Поскольку квадрат k порядка n - это преобразование (подстановка) множества I(n²), то есть k(n²), то применение к числам квадрата k преобразования (n²) есть, фактически, умножение преобразований k:

i,jI(n) ( k[i,j]) = (по обозначению 4.3:2) = ((ni+j) k) = (ni+j)(k) = (k)[i,j].

4.4.3. Преобразование клеток квадрата.

Преобразование клеток квадрата kK(n) есть, фактически, преобразование множества индексов квадрата, то есть, учитывая, что

	m-1
xI(2^m) однозначно раскладывается x =		2^r*(x\|r)
	r=0

	n-1, n-2, ...,1, 0		или, считая верхний ряд фиксированным:
	(n-1),(n-2),...,1,0		( (n-1),(n-2),...,1,0 )

rI(m)	((xy))\|r	= (по определению )
=	(xy)\|(r)	= (по определению )
=	(x\|(r))(y\|(r))	= (по определению )
=	((x)\|r)((y)\|r)	= (по определению )
=	((x)(y))\|r.

	n-1			n-1
iI(n)		k[i,j]=s(n)	jI(n)		k[i,j]=s(n)
	j=0			i=0

	n-1			n-1
		k[i,i]=s(n)			k[i,n-1-i]=s(n)
	i=0			i=0

	2^m-1			2^m-1
iI(2^m)		k[i,j]\|r=2^m-1	jI(2^m)		k[i,j]\|r=2^m-1
	j=0			i=0

	2^m-1			2^m-1
		k[i,i]\|r=2^m-1			k[i,2^m-1-i]\|r=2^m-1
	i=0			i=0