MagicSquare4. Модель КукуСовсем. Квадратные квадраты.
Это, может быть, последняя статья из серии. Но никто не знает, что высрет мой больной разум.
Хорошо. У нас есть простейшая АВС-модель, которую мы записываем иногда так:
А иногда так, когда работаем с квадратными квадратами:
У нас есть модель Бубса и Мумса:
Которая, однако, становится бесполезной, когда мы вводим модель ±x±y:
с красивыми рисунками:
У нас есть модель Нанакккк, которую скорее следует рассматривать как критерий Нанакккк: «для любого делителя Е в квадрате может найтись максимум два элемента, отличных от Е, которые на него делятся».
Есть, назовём это всё же так, критерий КукуПэпэ, благодаря которому мы с уверенностью можем сказать, что E имеет как минимум два простых делителя вида 4k+1, и не имеет делителей другого вида.
Но что важнее всяких моделей и критериев — у нас есть методы и подходы, из которых мы уже сложили целую систему.
В предыдущей части мы говорили про глобальный центр — элемент Е.
Обсудим локальные центры — углы квадрата — элементы C, J, A, G.
Обратим внимание на то, что
2C² = D²+H²
2J² = D²+B²
2A² = H²+F²
2G² = B²+F²
Опытные вы уже сейчас можете заметить, что все эти 2A², 2C² и так далее, представимы в виде сумм квадратов, а значит, должны иметь хотя бы один простой множитель вида p и не должны иметь множителей вида q в нечётных степенях.
Вот, кстати, возможно, я настолько вбил вам в голову мысль о том, что все элементы квадрата не делятся на 2 и на q, что забыл уточнить одну деталь: мы подходили к этому вопросу со стороны делителей Е.
То есть, мы говорили: «если Е делится на q или на 2, то все остальные элементы тоже делятся на q или на 2 и мы можем вынести 4 или q² за магический квадрат и рассматривать меньший квадрат, поэтому можем считать, что Е не делится на q и на 2». Вот — это было конкретно про Е. Если Е не делится на 2 и на q, то остальные элементы могут делиться на 2 и на q.
И нам хорошенько бы уточнить, что можно, а что нельзя, для тех чисел, что не являются делителями 2 и q.
Почему мы можем утверждать, что ни один из элементов не делится на 2 при условии, что Е не делится на 2? Если Е не делится на 2, то E² это число вида 4k+1, значит, магическая константа 3E² это число вида 4k+3. Все прочие числа могут быть либо 4k, либо 4k+1, потому что они тоже квадраты. Мы складываем три таких числа. Единственный способ получить в таком случае 4k+3 — сложить три 4k+1. Значит, каждое из них нечётно. Ура, от двойки избавились.
Теперь, на примере 2A² = H²+F² рассмотрим делитель q. Мы знаем, что Е не имеет делителей вида q. Предположим, что А имеет. Тогда на это же q делятся Н и F. Составим матрицу остатков при делении на q:
Теперь заметим, что G²+J² будет сравнимо по модулю с C²+J². Отсюда — G² сравнимо с C². Аналогично, J² сравнимо с B²:
Теперь, когда мы поставили C² вместо G², можем увидеть, что D² имеет такой же остаток от деления на q, что и B²:
И заметим ещё вот что: побочная диагональ C²+E²+C² равна магической константе 3E², то есть C² сравнимо с E².
Аналогично, B² сравнимо с 2E²:
В принципе, вроде бы ничего не нарушается. То есть пока что никак нарушений не видно, и мы пока не можем утверждать, что А не имеет делителей типа q. С другой стороны, мы можем утверждать, что если А имеет делитель типа q, то на него делятся только F и H, а прочие элементы квадрата должны иметь соответствующие схеме остатки. А схема изображена на последнем скрине после последнего преобразования.
Вот, ладно, от q избавиться не смогли, но если разные углы и имеют делители вида q, то эти q обязательно разные.
Ну и не для любого q, кстати, это возможно. Я имею ввиду, выполнение условия
Например, если q = 3, то полный квадрат, который не делится на 3, может иметь остаток при делении на 3 только 1. Ну и у 1 и у 2 разные остатки при делении на 3, да?
То же самое с 11:
А вот для 7 вполне возможно:
Вот хороший вопрос: для каких чисел это возможно, а для каких нет. Тут нам надо углубиться [побегать по поверхности] в теорию квадратичных вычетов. Всё очень просто:
Так вот, четыре факта:
- Произведения квадратичных вычетов похожи на сумму нечётных чисел:
В нашем случае, B² и E² — гарантировано вычеты, ведь они квадраты. Значит, 2 тоже должно быть вычетом по данному нам модулю q, чтобы было возможно
B² = 2E²
2. Чтобы определить, является ли данное число квадратичным вычетом по простому модулю, используют критерий Эйлера:
Легко выводится из малой теоремы Ферма.
Итак, теперь мы знаем, что любое число q, для которого
не может быть делителем ни одного из углов. Только углов, да… Нам, в будущем, похоже, ещё и со сторонами мучаться.
3. Чтобы удобно обозначать, является ли число a квадратичным вычетом по модулю m, используют символ Лежандра. Это не так страшно, как звучит, всё очень просто:
Теперь мы можем записать критерий Эйлера в одну строку:
4. Есть такая лемма Гаусса, которая утверждает следующее:
Доказательство у неё крайне милое, если хотите, почитаете.
Так вот у этой теоремы есть весёлое следствие, которое нам и надо. Звучит оно так:
Если вы вдруг не умеете xbnfnm yf 'kmabqcrjv, я перепишу это выражение на русском:
Вывод этого факта и доказательство всех теорем выше вы можете почитать в прекрасном файлике, который я нашёл в яндексе. Огромное спасибо автору.
Мы же просто воспользуемся этим знанием, чтобы утвердить:
Вершины А, С, G, J магического квадрата не могут иметь простых делителей вида 8k+3. Они могут иметь делители вида 8k+5, потому что это делители типа p, а, значит, они могут «разламываться» в суммах квадратов. Впрочем, мы это уже обговорили в верхней части статьи.
Справедливости ради остановлю взор на числе 3. Это единственное число, которое не будучи делителем Е является делителем магической константы 3E². Тем не менее, любой квадрат может иметь только остаток 1 или 0 при делении на 3, и чтобы нам из этих квадратов сложить 0, необходимо либо взять три единицы, либо три нуля. Отсюда напрямую следует, что на три либо не делится ни один из элементов квадрата, либо делятся сразу все, но такую ситуацию мы не рассматриваем ввиду её бесполезности. Это мы тоже уже много раз обсуждали.
Ладно, выходит, что вот так вот.
Теперь мы знаем:
- Е имеет минимум два различных простых делителя вида 4k+1 и не имеет делителей вида 4k+3. Причём если Е имеет только два простых делителя 4k+1, пара элементов квадрата также делятся на один из них, и другая пара делится на другой
- A, C, G, J имеют минимум один простой делитель вида 4k+1 и не имеют делителей вида 8k+3.
Возможно, имеет смысл рассмотреть различные совокупности этих двух факторов. Например, предположить, что Е не взаимно просто с двумя углами и двумя серединами сторон или Е не взаимно просто только со сторонами или Е не взаимно просто только с углами. А может быть, угол не взаимно прост с какой-то стороной.
Также можно подойти к различным неучтённым нами комбинациям делителей сторон и углов с точки зрения квадратичных вычетов. Возможно, узнаем что-то новое. Надеюсь, вы поняли предыдущее предложение, а если нет — то не страшно, я тоже не понял.
…
…
…
Прошло чуть больше месяца с последнего дня, когда я писал эту статью, и я снова здесь. Любителей тч я снова попрошу отойти в сторону, а любителей линейной алгебры призываю сюда вот. Хотя одно от другого недалеко находится
Поговорим про магические квадраты как про матрицы, но немного с другой стороны. Мы с вами уже договорились, что магические квадраты обозначаем как m(E,x,y), где E это центр, x — разность центра с левым верхним углом, y — с левым нижним. Проще говоря,
Для удобства иногда я буду писать [E,x,y], то есть вместо m с круглыми скобками использовать квадратные.
Наш подписчик заметил, что хоть бинарное произведение магических квадратов и не даёт магический квадрат, но если мы умножим ТРИ магических квадрата подряд, то получим магический квадрат. ТРИ, ПЯТЬ, СЕМЬ и так далее, любое нечётное количество.
Брать и перемножать три матрицы в лоб мы не будем, тут даже компьютер начнёт возмущаться. Вместо этого введём ещё одно понятие. ЧАРУЮЩИЙ КВАДРАТ. У меня настроение писать капсом, не пугайтесь и не злитесь.
Так вот, чарующий квадрат очень похож на магический, но имеет вид вот такой вот:
Тоже три буквы, поэтому мы можем записать это вот так: c(E,x,y). Вместо c(E,x,y) я могу писать просто (E,x,y), тут круглые скобки. Почему я могу так делать? Потому что я так сказал.
Аналогично магическим квадратам, у нас есть базисы
Теперь, когда у нас есть чарующий квадрат, записанный как тройка чисел в круглых скобках, мы можем уйти от матриц и оперировать только тремя буквами. Ну, очень скоро сможем, для начала заметим правила матричного умножения.
Ещё для моего удобства: м-квадрат и ч-квадрат — так я буду сокращённо записывать магический и чарующий квадраты.
Теперь запаситесь терпением или вольфрамом или чем-нибудь ещё и проверяйте свойства:
Найдёте ошибку — бейте в гонг в точности 137 раз. В этот момент гонг не выдержит и ударит в ответ, а ответ, ничего не дожидаясь, ударит вас, и вы поймёте, что ошибка всё же с вашей стороны, а не с моей.
На самом деле, это одни из самых странных правил умножения, что я когда-либо видел.
Но они похожи на правила умножения неотрицательных и неположительных чисел. Тут стоит заметить, что множество С замкнуто относительно умножения, а множество М — просто иждивенец. Но для нас, как вы знаете, М более интересно.
Так вот, в чём нам ещё сказочно повезло: множество С включает в себя матричную единицу. Элемент c(1/3, 1/3, 0) — нейтральный относительно умножения. Можете сейчас подставить в формулы и проверить. При умножении чего бы то ни было на c(1/3, 1/3, 0), вы получите начальный квадрат.
Этот факт и пара других позволяют нам ввести обратные по умножению элементы:
А тот факт, что у нас есть обратные по умножению элементы, даёт нам право без всяких угрызений совести решать уравнения с квадратами. Вот вам примерчики:
Пока всё складывается максимально хорошо. Точнее, умножается. Или делится. Мы с вами же сейчас делим по сути. Я решил все существующие такие уравнения и получил вот что:
Запись W_mcr означает: «на этот квадрат надо умножить справа m, чтобы получить с». То есть первая буква — умножаемый квадрат, вторая буква — получаемый квадрат, третья буква — сторона умножения.
Давайте проверим умножение на ассоциативность. Это то свойство, которое позволяет нам умножать числа, не учитывая порядок умножения:
(a*b)*c = a*(b*c)
Для этого нам нужно произвести примерно 32 умножения. Или сколько? Давайте посчитаем.
Существует 2 варианта для первого множителя, 2 варианта для второго, 2 варианта для третьего. 8 вариантов произведений. Нам нужно произвести для каждого умножения:
a*b, b*c, ab*c, a*bc. 4 умножения для каждого варианта, 8 вариантов всего. Значит, 32 умножения.
Хотя погодите. У нас же матричное умножение. Оно ассоциативно для всех матриц. Значит, в нашем случае оно тоже ассоциативно. Чего-то я затупил, ага.
Но тем не менее, смотрите как круто перемножаются три магических квадрата:
Что в этом умножении приятно? Первый и третий член коммутируют. То есть при их перестановке произведение не изменится.
Ок, вроде всё что было можно мы с вами научились делать: умножать, брать обратное, делить со всех сторон.
Давайте ещё введём квадраты-трансформаторы: квадрат, на который нужно умножить [E,x,y], чтобы получить (E,x,y) и наоборот. Обозначать их будем trans_mc и trans_cm.
И, чтобы всё было на виду, перепишем результаты отдельно:
Теперь, наверное, правда в общем всё.
Возвращаемся в область квадратных квадратов, но с акцентом на нововыведенных свойствах.
Вернёмся ненадолго к вот такому виду:
И к вот таким вот штукам:
И вспомним, что мы пришли во 2 статье к вот такой штуке:
Это можно записать иначе:
И теперь, подставляя в верхние формулы, получим:
Последние два уравнения можем вычесть друг из друга, чтобы выразить x и сложить, чтобы выразить y.
В итоге мы получим две формы квадратных квадратов
Первая гарантирует нам, что элементы A, C, G, J будут целыми квадратами, а вторая — что B, D, F, H. Причём эти формы охватывают все существующие такие квадраты.
Альфа и бета одного индекса — любые взаимно простые целые. Е — любое число, такое, что 2Е делится на сумму квадратов альфы и беты. Поэтому алгоритм постройки квадратов по формуле такой:
- Подбираем alpha1 и alpha2. Например, 2 и 7
- Подбираем взаимно простые альфам beta1 и beta2 больше их. Например, 3 и 8
- Подбираем Е такое, что 2Е делится на суммы квадратов альф с бетами. В нашем случае, делится на 4+9 = 13 и 49+64 = 113. Самое маленькое такое Е — это 13*113 = 1469
- Подставляем в форму квадрата:
И то же самое для второй формы:
Вдоволь насладившись примерчиками, говорим дальше. На самом деле, существуют вполне универсальные методы нахождения квадратов 6/9, поэтому сейчас мы с вами никого не удивили.
Что я хочу сделать, и зачем мы сейчас усердно выводили свойства умножения магических квадратов и вводили чарующие? Во-первых, это прикольно, и даже очень. Во-вторых, те две формы, что мы ввели, выглядят достаточно жутко, если искать квадратный квадрат через них в лоб, то нужно решить в целых числах систему
А это уж для совсем отбитых, если даже и решается.
Что если представить наш квадрат в виде произведения более простых квадратов? И работать с уже более простыми квадратами, зависящими от параметров линейно? Это, конечно, мечты, но я планирую двигаться в этом направлении.
И публикую статью. Возможно, когда-нибудь выйдет пятая часть