Про одну необычную инволюцию

Часть 1. О чём заметка

Сегодня я хочу обсудить одно очень необычное доказательство, о котором обычно говорят в контексте магического доказательства без мотивировки.

Теорема (Ферма, 1640). Простое число $p$ представимо в виде суммы двух квадратов целых чисел тогда и только тогда, когда оно равно $2$ или имеет вид $4 k + 1$ .

Доказательство. Как и в прошлой заметке, случай $p = 4 k + 3$ очевиден, пусть теперь $p$ имеет вид $4 k + 1$ .

Рассмотрим множество положительных целочисленных троек

S = {(x, y, z) \in N_{> 0}^{3} : x^{2} + 4 y z = p} .

Определим на нём инволюцию следующим образом:

ι (x, y, z) = ⎩ ⎨ ⎧ (x + 2 z, z, y - x - z), (2 y - x, y, x - y + z), (x - 2 y, x - y + z, y), x < y - z, y - z < x < 2 y, x > 2 y .

Заметим, что эта инволюция имеет только одну неподвижную точку — $(1, 1, k)$ . Значит, $S$ содержит нечётное количество элементов.

Рассмотрим тогда другую инволюцию:

σ (x, y, z) = (x, z, y) .

Поскольку в множестве $S$ нечётное число элементов, у этой инволюции есть неподвижная точка $(x, y, y)$ , а значит,

p = x^{2} + 4 y^{2} = x^{2} + (2 y)^{2} .

Теорема доказана. $□$

Небольшое пояснение к доказательству. Все три ветви $ι$ сохраняют уравнение $x^{2} + 4 y z = p$ , положительность координат и действительно задают инволюцию. Граничные равенства $x = y - z$ и $x = 2 y$ для простого $p \equiv 1 (mod 4)$ невозможны: первое даёт $p = (x + 2 z)^{2}$ , а второе — $p = 4 y (y + z)$ . Неподвижная точка может находиться только во второй области. Там из $2 y - x = x$ получаем $x = y$ , а тогда $p = x (x + 4 z)$ ; простота $p$ влечёт $x = y = 1$ и $z = k$ .

Я попробую предложить некую мотивировку, как это доказательство можно придумать, обобщить и применить ту же идею в других задачах.

Часть 2. Снова геометрия чисел

Начнём совсем издалека, а именно с квадратичной формы. Я буду в данном разделе всё делать в $R^{2}$ , однако всё это легко обобщается и на большие размерности.

Итак, рассмотрим

q (x, y) = a x^{2} + b x y + c y^{2}

и зададимся фундаментальным вопросом: какое множество значений она может принимать на $Z^{2}$ ? И как по двум формам понять, что у них общее множество значений?

Геометрическая интерпретация. Есть решётка, у которой квадрат длины одного вектора равен $a$ , другого — $c$ , а скалярное произведение равно $b /2$ . Как понять множество квадратов длин векторов этой решётки?

Эквивалентность и дискриминант

Определение 1. Две бинарные квадратичные формы называются эквивалентными, если одна получается из другой целочисленной линейной заменой координат с матрицей перехода определителя $1$ :

(y x) ⟼ (α γ β δ) (y x), α δ - β γ = 1.

Замечание. У эквивалентных форм совпадают множества значений на $Z^{2}$ и дискриминанты

D = b^{2} - 4 a c .

Как всегда в таких случаях, хочется выбрать для каждого класса эквивалентности какого-нибудь главного представителя.

Приведение по Гауссу

Определение 2. Назовём положительно определённую форму приведённой по Гауссу, если

∣ b ∣ \leq a \leq c,

а если $∣ b ∣ = a$ или $a = c$ , дополнительно потребуем $b \geq 0$ .

В разных источниках приняты немного различающиеся соглашения о знаках на границе.

Вопрос о том, как найти приведённую форму, носит название Gauss reduction — приведение по Гауссу. В разных источниках оно также встречается как Lagrange reduction.

Для преобразований используются, в частности, элементарные замены

(x, y) ⟼ (x + y, y)

(x, y) ⟼ (- y, x) .

Их матрицы имеют определитель $1$ , так что обе сохраняют класс эквивалентности.

Замечание: я пропущу доказательство корректности алгоритма, однако отмечу очень интересное наблюдение. Он очень похож на алгоритм Евклида. И действительно, это его прямое геометрическое обобщение: если рассматривать линейные формы, поиск малых целочисленных комбинаций буквально возвращает нас к алгоритму Евклида.

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

Часть 3. От общего к частному

Теперь с высоты знаний по приведению форм посмотрим на формы вида

q (u, v) = a u^{2} + b uv - c v^{2} .

Их дискриминант равен

D = b^{2} + 4 a c .

Мы уже знаем, что эквивалентность сохраняет дискриминант. Давайте посмотрим на формы с $D = p$ , где $p$ — нечётное простое число.

Для положительных $a, b, c$ это в точности те же тройки, что были в первом доказательстве: сопоставим $(x, y, z) \in S$ форму

q_{x, y, z} (u, v) = y u^{2} + xuv - z v^{2} .

Её дискриминант

D = x^{2} + 4 y z = p .

При редукции неопределённых форм возникают циклы преобразований координат. Идея, которую использует Хит-Браун в геометрической мотивировке инволюции Загора, состоит в том, чтобы увидеть за неожиданной формулой естественные шаги изменения базиса.

Представим, что у нас есть множество форм с фиксированным дискриминантом. Мы хотим показать, что какая-то инволюция имеет неподвижную точку. Для этого сначала удобно разбить положительные тройки на три области:

R_{1} R_{2} R_{3} = {(x, y, z) \in S : x > 2 y}, = {(x, y, z) \in S : y - z < x < 2 y}, = {(x, y, z) \in S : x < y - z} .

Граничные случаи, как мы уже заметили, для нашего простого $p$ не возникают.

В терминах редукции эти области позволяют представить кусочное преобразование как три вполне естественных шага:

Область $R_{1}$ : применяем преобразование, связанное с шагом редукции (в частности, с заменой $u \mapsto v - u$ ). После пересчёта коэффициентов и выбора удобного порядка координат получаем переход в $R_{3}$ .
Область $R_{2}$ : делаем отражение внутри этой области, соответствующее замене $x \mapsto 2 y - x$ .
Область $R_{3}$ : выполняем обратный переход к тому, что делали на $R_{1}$ .

Именно поэтому $R_{1}$ и $R_{3}$ меняются местами, а в $R_{2}$ остаётся симметричная часть преобразования. Если расписать тройки, получится знакомая инволюция:

⎩ ⎨ ⎧ (x, y, z) \mapsto (x + 2 z, z, y - x - z), (x, y, z) \mapsto (2 y - x, y, x - y + z), (x, y, z) \mapsto (x - 2 y, x - y + z, y), (x, y, z) \in R_{3}, (x, y, z) \in R_{2}, (x, y, z) \in R_{1} .

Так необычное преобразование из первой части приобретает геометрическую мотивировку: оно связано с целочисленными преобразованиями бинарных квадратичных форм, а его неподвижная точка выделяется симметрией.

Важная оговорка. Здесь изложена именно мотивировка, а не полное доказательство связи с алгоритмом редукции неопределённых форм. Для строгого вывода нужно отдельно выбрать область приведённых неопределённых форм и проследить действие замен базиса. В отличие от прямого доказательства части 1, этот переход намеренно дан схематично.

Часть 4. Бонус

Ну и напоследок — то, что решается похожими приёмами.

Задача 1. Докажите, что простые числа вида $8 k + 1$ и $8 k + 3$ представимы в виде
$p = x^{2} + 2 y^{2} .$

Указание. Рассмотрите множество

S_{p} = {(x, y, z) \in N_{> 0}^{3} : x^{2} + 2 y z = p}

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

Задача 2. Докажите, что любое натуральное число представимо в виде суммы четырёх квадратов целых чисел, используя подобную инволюционную идею.

Указание. Здесь существенно сложнее. Для начала заметим, что

x^{2} + y^{2} + 2 z^{2} + 2 w^{2} = x^{2} + y^{2} + (z + w)^{2} + (z - w)^{2} .

Поэтому полезно сначала смотреть на форму с коэффициентами $(1, 1, 2, 2)$ , а затем на конструкции вида

x^{2} + y^{2} + 2 (z w + mn) = k p .

Дальше понадобится нетривиальный спуск, а в конце — инволюция, связанная с перестановкой $z$ и $w$ . Другая инволюция, обеспечивающая нужную нечётность, строится аналогично предыдущим идеям.

Оригинал: «Об одной необычной инволюции» — «Задача дня», Telegram.

description	Доказательство теоремы Ферма о двух квадратах через инволюцию Загора и связь с бинарными квадратичными формами.
tags	теория-чисел, инволюции, квадратичные-формы, красивые-доказательства

Задача дня