MagicSquare3. Модель КукуПэпэ. Квадратные квадраты.
Ладно, я шучу, такой модели нет. Просто надо же как-то сохранять настроение
Итак, если вы читали прошлую статью, то можете помнить, я дал вам домашнее задание. Доказать 4 факта. Я их продублирую
- Любое простое число вида 4k+3 не представимо в виде суммы квадратов
- Любое простое число вида 4k+2 представимо в виде суммы квадратов, причём единственным образом
- Любое простое число вида 4k+1 представимо в виде суммы квадратов, причём единственным образом
- Любое простое число вида 4k одновременно представимо и не представимо в виде суммы квадратов
Четвёртый пункт, разумеется, был шуточным, не существует простых чисел вида 4k. Если я сформулировал четвёртое утверждение неверно, напишите об этом в комментарии, пожалуйста. А то я чего-то сомневаюсь.
Второй пункт был полу шуточным. Единственное просто число вида 4k+2 это 2. 2 представимо в виде суммы квадратов 1²+1² и никак больше, это даже не надо доказывать, пожалуй.
Первый пункт доказывается очень легко с помощью простого факта: «любой квадрат имеет остаток либо 0, либо 1, при делении на 4». Как вы ни складывайте нули и единицы, 3 вы не получите. Выходит, первое выражение верно. Сам факт можно доказать даже простым перебором. А если нет, то идите читайте конец статьи про яйца и Никит.
Остаётся третий пункт, и он действительно пугающий. Называется третий пункт Теоремой Ферма-Эйлера, или рождественской теоремой Ферма. И знаете… Я так рад, что дал вам это в качестве домашнего задания, мне теперь не придётся расписывать вам доказательство. Давайте вы поверите мне на слово, или, если интересно, посмотрите какое-нибудь видео на ютубе. Там куча всяких доказательств, но ни одного такого, какое бы мне хотелось вам тут писать.
А сам факт нам очень-очень важен.
Итак, что мы знаем? Что простые числа вида 4k+3 не представимы в виде суммы двух квадратов, что простые числа вида 4k+1 представимы единственным образом, а число 2 особенное — это сумма квадратов двух одинаковых чисел.
Давайте все простые числа типа 4k+1 обозначать буквами p, а простые числа типа 4k+3 обозначать буквами q. У этих букв также могут быть индексы, чтобы обозначать различные простые одного типа. Будем называть p хорошими, а q плохими. Но не с целью обидеть их, конечно же.
Пусть какое-то число имеет набор простых делителей типа p в разных степенях, какой-то набор простых делителей типа q в разных степенях и ещё делится на 2 в какой-то степени, может быть и в нулевой.
Вот. В таком виде представляется вообще любое число, например, 15!
Надеюсь, понятно. У 15! два хороших делителя и три плохих.
Тогда вот такой факт:
Этот факт мы будем доказывать.
Невероятно просто он доказывается через гауссовы числа и комбинаторику. Мы пойдём другим путём и, возможно, у нас ничего не выйдет.
Доказывать будем по математической индукции. С базисом проблем не будет, подойдёт первое попавшееся число, потому что факт, записанный выше, работает для всех натуральных чисел. А вот во время индуктивного шага, нам потребуется перебрать все возможные варианты, но я пока не знаю, как их лучше сформулировать.
Вспомним тождество Брахмагупты:
И увеличим теперь количество этих самых…
Ладно, это всё не работает. Я не понимаю, как доказать промежуточные факты, необходимые для доказательства по индукции, поэтому мне придётся доказывать это через гауссовы числа. Буду рассчитывать на то, что вы знаете комплексные или хотя бы читали статью про яйца и Никит.
Может быть, так даже лучше. Если совсем никак, то можете пролистнуть доказательство, там дальше будет проще.
Итак, простой факт: любая сумма квадратов записывается в виде произведения двух комплексно-сопряжённых чисел:
Если эти квадраты целые, как у нас, то и их комплексные множители — целые. Но не просто целые, а гауссовы целые. Ну понятно.
Если же мы возьмём простое число типа p, то его гауссовы делители неизбежно будут простыми гауссовыми числами. То есть их мы уже ни на что разделить не сможем:
Это свойство я вам тоже не докажу, но его вы, как минимум, сможете нагуглить. Я уже говорил, что на русскоязычной Википедии по ним удивительно хорошая статья? Это моя любимая статья на Википедии, надо сказать.
Любое простое число типа q является так же простым гауссовым числом, то есть не делится ни на какое другое гауссово простое число.
Наши потребности в разных буквах растут, ведь a и b мы уже использовали выше, а нам сейчас надо переписать число t через гауссовы делители. Поэтому давайте использовать греческие буквы, чтобы хоть как-то облегчить себе жизнь.
Все числа типа p будем записывать в виде суммы квадратов или через их гауссовы делители. Для этого вместо а и б будем писать альфа и бета:
Ещё одна штука — число 2 не является гауссовым простым:
И тогда запишем наше число t вот так:
И теперь что сделаем? Давайте введём самое маленькое из возможных t и обзовём его t0. Оно будет равно какому-то простому числу типа p
Тогда t0 представимо в виде суммы квадратов единственным образом. Теперь домножим его на другое число p.
И да, теперь мы будем записывать половину всех сопряжённых делителей t с одной стороны, а другую половину — с другой. В результате, произведение всех множителей слева будет сопряжено с произведением всех множителей справа. Давайте докажем. Тут уже можно просто по индукции относительно количества множителей.
Итак, идём сверху вниз. Изначально у нас каждому множителю слева стоит комплексно-сопряжённый справа. То есть база индукции есть.
Предположим, мы перемножили в правом столбике первые k множителей и получили A+Bi, где A и B рандомные целые числа. И оказалось, что наша гипотеза верна и справа оказалось сопряжённое A-Bi. То есть, тут гипотеза сработала. И нам надо доказать, что тогда она сработает и для k+1 множителя. Имеем
Как видите, произведения получились сопряжёнными. Это, конечно же, нас не удивляет, мы на это и рассчитывали.
Теперь ещё более простой факт — произведение сопряжённых гауссовых чисел — это сумма квадратов. И t у нас записывается в виде двух столбиков
Произведение первого столбика снова обозначим за A + Bi. Значит, t = A²+B². Поменяем местами
Если мы поменяем местами пару элементов, то всё равно каждому элементу первого столбца найдётся пара во втором:
Однако произведение первого столбца изменится. И мы получим другое представление t в виде суммы квадратов.
И мы можем менять и менять и менять до тех пор, пока все элементы второго столбца не перейдут в первый и наоборот. Всего таких вариантов здесь будет 2^k. Потому что у нас есть 2 варианта первой скобки в левом столбце, 2 варианта второй, 2 варианта третьей и так далее…
Но что, если t делится на один и тот же множитель несколько раз?
Тогда две перестановки будут одинаковыми:
То есть если мы будем считать по старой формуле, то окажемся не правы. Здесь верной формулой будет 3*2^(k-1). Потому что для первых двух всего 3 различных перестановки, а для прочих как и раньше.
В общем виде, как вы могли догадаться, это будет как раз наша формула. Наша формула, в которой там много скобок и в каждой скобке стоит +1. Вот.
То есть вот так:
Это можете доказать сами как-нибудь с помощью комбинаторики. На деле, здесь достаточно показать, что в каждом блоке ровно m+1 вариантов. А это уж очень легко: в блоке может быть от 0 до m минусов, то есть всего m+1. Других вариантов нет. Вот и всё, даже без комбинаторики обошлись.
Отлично. Значит, теперь мы точно можем утверждать, что такое t будет иметь именно столько представлений в виде суммы квадратов. НО!
Если вдруг ваши альфа и бета одновременно оказались единицами, то перестановка плюсов и минусов не поменяет ничего. Умножение на 2 не меняет количество представлений в виде суммы квадратов. Понятно? Ну это легко показать. Пусть у нас при перемножении всего левого столбика получалось, как обычно, А+Bi. Тогда, если мы умножим его ещё и на 2, оно будет иметь вид:
Покажем, что при перестановке ничего не меняется:
В любом случае, t = (A+B)²+(A-B)².
А что будет при любых других альфах и бетах?
Очевидно, это одна и та же сумма квадратов лишь в том случае, если альфа и бета равны или противоположны по знаку.
Если при этом они не равны единицам, то они не составляют простой гауссов делитель, а значит, нами не рассматриваются. Поэтому 2 в разложении числа представляет особый случай. И теперь мы точно знаем, что наша формула верна.
Последнее — попробуем умножить наше число на простой делитель вида 4k+3, в наших обозначениях q. Поскольку он является простым гауссовым числом, он займёт место лишь в одном столбике. И ему не найдётся пары. И у числа пропадут все представления в виде суммы квадратов. Обидно. Чтобы вернуть все представления, надо добавить такое же число в другой столбик, то есть домножить наше число ещё раз. Но их перестановка не даст ничего нового, ведь они равны.
То есть, если умножать наше число на q, то либо представления в виде сумм квадратов пропадут, либо не изменятся по сравнению с этим же числом без q в разложении. Причём если t делится на q и t = A²+B², то А и В тоже делятся на q. Это вполне очевидно из написанного выше.
Вот и выходит, что наша формула верна, и мы, в конце концов, можем ею пользоваться.
Запишем её ещё раз?
Здесь стоит сказать, что это утверждение работает и в другую сторону. То есть, если число t не представляется в виде суммы квадратов, то оно имеет в разложении делитель типа q в нечётной степени. А если представляется, то не имеет делителей q в нечётной степени. И количество представлений определяется только делимостью. То есть, если у числа 7 представлений в виде суммы квадратов, то оно имеет делитель p в 6 степени. Если у числа 6 представлений, то оно либо имеет один делитель p в 5 степени, либо два делителя p в степенях 1 и 2.
Думаю, понятно. Пора применять в наших квадратах:
Как вы знаете ещё из самой первой статьи,
То есть 2E² представимо в виде суммы квадратов как минимум пятью различными способами.
Но по нашей формуле девятью. Потому что A²+J² и J²+A² для нас разные представления.
Чтобы представляться в виде суммы квадратов девятью различными способами, нужно иметь один из двух видов:
Под o имеются ввиду все прочие делители: степени двойки, делители вида p, делители вида q в чётных степенях.
Но давайте вспомним, что если 2E² делится на q, то и все пары квадратов, на суммы которых он раскладывается, делятся на q. А это ABCDFGHJ — весь магический квадрат. А зачем нам рассматривать квадрат с большими числами, если мы можем рассматривать такой же квадрат, но с маленькими?
В общем что? Нам с вами из всех пропорциональных квадратов интересно рассматривать только самый маленький, то есть такой, что если Е делится на какое-то число, то кроме него в квадрате на это число может делиться не больше двух элементов. Простые множители типа q нам не подходят, а значит, Е их не содержит. По той же причине мы уже ранее откинули 2 как делитель Е.
Вот и выходит, что Е это либо какое-то простое число p в степени как минимум 4, либо произведение как минимум двух простых чисел, возможно, возведённых в степень. Вау, да?
Претенденты на положение Е в квадрате резко сокращаются в очень-очень много раз. Если делить их на две группы, то вот первые варианты из каждой:
Несложно заметить, что вторых намного больше. Но, на самом деле, первые нам не подходят.
Давайте введём понятие простое разложение на сумму квадратов. И будем иметь под этим ввиду, что
t = A²+B² и
t не имеет общих делителей с А и В.
Тогда, если E = p^4+, у 2E² всего лишь одно простое разложение. Потому что, если мы обратимся к нашим столбикам, в случае, когда в одном столбце стоят комплексно-сопряжённые числа, квадраты в разложении начинают делиться на их произведение. А их произведение — это p. То есть квадраты имеют с Е общий делитель. Вот так.
Есть только два способа составить столбцы так, чтобы в них не встречались сопряжённые: выстроить все множители с одинаковыми альфами и бетами в одном столбце только со знаком плюс, либо только со знаком минус:
Но в данном случае, поменяв все плюсы и минусы местами, мы сделали то же самое, что было бы, переставь мы просто 1+i и 1-i местами. А их перестановка, как вы помните, ни на что не влияет. То есть столбик из одних плюсов даст те же квадраты, что и столбик из одних минусов. И у Е будет только одно простое разложение. Остальные будут делиться на p в разных степенях. А это, безусловно, нельзя, ведь тогда либо не выполнится условие Нанакккк, либо мы сможем вынести множитель за магический квадрат [и уже после этого у нас нарушится Нанакккк].
Вот и выходит, что единственный способ поступить правильно — отказаться от варианта с одним p. Е должно иметь как минимум два простых делителя p.
Если же оно имеет ровно два делителя, то у 2E² в точности 5 разложений на суммы квадратов, если не учитывать повторы. Одно из них тривиально — E²+E². Два других — простые разложения. Четвёртое делится на p1, пятое на p2. Ничего не нарушается. Но, возможно у нас выйдет доказать, что такой вариант нас тоже не устраивает. Возможно, через Бубса и Мумса. Возможно, в следующей статье.
Кстати, заметим, что количество различных простых разложений всегда
2^(a-1). Докажете сами, моя задача была только заметить.
Кстати, метод через гауссовы числа первым придумал Нерегулярный автор. Он у нас молодец.
Итак, порядки уже пошли на десятки тысяч и, надо сказать, что вообще-то доказано, ещё в 2001 году, что квадратный квадрат нельзя построить ни на одном из первых 250*10²³ чисел. Под «построить магический квадрат на числе M» я имею ввиду «найти квадрат, магическая константа которого М», то есть даже если мы переберём все Е до 10^12, мы не дадим миру ничего нового. Нам нужно что-то более мощное, но я пока ничего такого не придумал.
Пожалуй, всё. Мы собрали всю ту информацию, что мы собрали. В следующей статье мы попробуем связать материал всех трёх написанных и обратим внимание на локальные центры, поработаем с уже известными вам картинками
Всем приятного чего-нибудь.