Неприводимость и иррациональность

Квант 1986, №11 с. 12, 13, 14, 16 Тег YEUB

Неприводимость и irrationalность

В. А. ОЛЕЙНИКОВ

В прощлом номере автор расскажал о много-
вековой истории irrationalных радиkalов
и неприводных многочленов, о признаке
Эйзенштейна. Здесь же речь пойдет о дости-
жении XX века в этой области, но на более
наглядном геометрическом языке.

Созданная на рубеже XIX и XX
веков теория алгебраических чисел
стала новым стимулом для изучения
неприводных многочленов. Алгебраическое число α — это просто ко-
рень многочлена с целыми коэффици-
центами:

$P(\alpha) = a_0 + a_1\alpha + \ldots + a_n\alpha^n = 0.$

Все радикалы, которые мы рассматривали в предыдущей статье, — алгебраические числа. Однако понятие алгебраического числа значительно шире: еще в начале прошло века П. Руффини (1765—1822) и Н. Г. Абель (1802—1829) показали, что не всякое уравнение степени выше четвертой разрешимо в радикалах. Алgebraические числа, таким образом, не исчерпывают irrationalными радикалами и рациональных числам.

Но это алgebraические числа тесно связаны с неприводимыми многочленами. Именно, любое алgebraическое число является корнем единственного (с точностью до числового множителя) неприводимого многочлена. Это следует из ТЕОРЕМЫ («Квант» № 10, с. 7).

Свойство неприводимости стало предметом пристального внимания многих выдающихся математиков. Наряду с поисками общих свойств (таких, как в ТЕОРЕМЕ) исследователи не давал покоя признак Эйзенштейна. Чувствовалось, что за этим признаком скрывается какой-то общий принцип, выявление которого позволяет получить новые более общие признаки. Так и оказалось на самом деле. Дальнейшее продвижение здесь связано с возможностью перевода свойства неприводимости на язык геометрических образов. Основа этого языка была заложена вликом Ньюотом за 200 лет до описываемых событий и носит его имя.

Диаграмма Ньюотона

Для построения диаграммы Ньюотона многочлена $P(x)$ по заданному простому $p$ необходимо:

координатная плоскость OKM (OK — горизонтальная, а OM — вертикальная оси);
линейка, гвозди, молоток;
немного терпения.

Потому что сначала наносится основа — каждому однолету $a_k x^k$ из $P(x)$ ставится в соответствии точка с координатами $(k; l)$ ; $l$ — это наиболее степень числа $p$ , при которой $a_k$ делится на $p^l$ . Набор всех таких точек $(k=0, 1, ..., n)$ и есть основа диagrаммы.

На рисунке 1 — основа многочлена $P(x) = 12 + 2x + 4x^2 + x^4 + x^5 + 2x^6 + 4x^7$

при $p=2$ . Свободный член $a_0$ делится на $p^2$ , но уже не делится на $p^3$ — имеем точку (0; 2), $a_1$ делится на $p$ — точка (1; 1), $a_2$ дает точку (2; 2).

Внимание! Если $a_k=0$ , то точку основы вообще не наносим.

В нашем случае $a_3=0$ не дает точки основы.

Если $a_k$ не делится на $p$ , то $l=0$ и точка $(k; 0)$ попадает на ось OK.

В нашем случае $a_4$ и $a_5$ не делятся на $p$ , $a_6$ делится на $p$ , $a_7$ делится на $p^2$ (см. рис. 1).

Будем считать, что вместе со старшим коэффициентом $a_n$ у многочлена $P(x)$ не равен нулю и свободный член $a_0$ . Иначе $P(x)$ всегда приводим (доказите!) и поэтому нам не интересен. На плоскости OKM, таким образом, будет нанесены по крайней мере две точки:

начальная точка основы — у нас (0; 2) и ее конечная точка — (7; 2)

А теперь диagrамма (рис. 2). Берем молоток и выбиваем гвозди во все точки основы, затем приставляем линейку вертикального к гвоздию, вбитому в начальное точку. Вращаем ее против часовой стрелки, пока она не упрется в другой гвоздь основы (у нас (1; 1)). Соединия эти точки отрезком, получаем первое звено диagrаммы. Для получения следующого звена нужно врашать линейку вокруг второго гвоздя (1; 1) до встречи с новой точкой основы.

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

Диagrамма Ньюотона готова и изображена на рисунке 2. Она представляется собой вогнутую вверх ломанную и всегда имеет хотя бы одно звено.

Построите сами диаграмму Ньютона для многочлена
$Q(x) = 16 + 4x + 8x^2 + 2x^3 + 8x^6$
по простому $p = 2$ .

Лищние точки (у нас — (2; 2)) не должны смещать читателя — во всяком стойшем производстве не обойтись без отходов.

О звеньях. Они бывают трех сортов:

Составные, простые, примененные

Звено диаграммы Ньютона называем простым, если кроме концов на нем нет других точек с целочисленными координатами. В противном случае, если такое имеется внутри звена, будем называть его составным (рис. 3). Далее, простое звено называем применным, если длина его проекции на горизонтальной ось OK равна единице.

Вот и все. Знакомство с образным языком неприводимости законено. Пора начать на нем разговаривать. За все труды по изготовлению диаграммы Ньютона нас вознаграждает

Признак Дюма

Если при неокотором простом $p$ диаграмма многочлена $P(x)$ состоит робно из одного простого звена, то такой многочлен неприводим.

Гистав Дюма жил в Швейцарии и активно занимался задачей о неприводимости в начале нашего столета. Этот признак получен им в 1906 году.

Признак Дюма позволяет … нарисовать признак Эйзенштейна,

глубже понять его и запомнить.

По условию признак Эйзенштейна все коэффициенты многочлена $P(x)$ , кроме старого, делятся на $p$ , а свободный член $a_0$ делится на $p$ и не делится на $p^2$ . Эту ситуацию и отражает рисунок.

XX век не терпит остановок *) и созалейной об упущенныхвозможностей.

Признаки, признаки, признаки…

На рисунке 4 еще один признак.

Заключенный в словесную форму, он прибретает «больший вес»:

Если для многочлена $P(x)$ нечетной степени $2n+1$ можно указать такое простое число $p$ , что старший коэффициент $a_{2n+1}$ не делится на $p$ , а все остальные коэффициенты
$a_k$ делятся на $p$ , $k=0, 1, ..., 2n$ , но дополительно коэффициенты
$a_k$ при $k=0, 1, ..., n$ делятся и на $p^2$ , а свободный член
$a_0$ , делясь на $p^2$ , не делится на $p^3$ , то такой многочлен $P(x)$ неприводим.

Признак Дюма не исчерпан! Каждый желающий может стать обладаателем собственного признака, поднимавая все выше конец звена и следя за тем, чтобы оно оставалось простым.

Вывод очевиден: массовое производство признаков — перспективное и в то же время абсолитно безопасное дело**).

Снова irrationalность

Средние изобилия признаков неприводимости нашлось место и признаку irrationalности (доказательство в Приложении на c. 16).

Если при неокотором простом $p$ диаграмма многочлена $P(x)$ не содержит примененных звенев (составные разбицы на простые), то среди его корней не может быть рациональных.

*) Кое-что о доказательстве признака Дюма нетопопливый читатель найдет в Приложении на c. 16.
**) Но вряд ли оно доставит нам лавры Эйзенштейна.

Зародилось алгоритмическое направление во времена Л. Кронекера (1823—1891) — известного немецкого математика, когда был придуман самый верный (но не самый быстрый) способ узнать — приводим данный многочлен или нет (весьма похожий на тот, о котором шла речь в нашем первом примере: с. 15). Обогащенное идеями получабитых признаков, это направление набирает темп. В самом последнее время (в 1982 г.) оно выразило шеедевром мастеров Голландской школи (А. Ленстра, Г. Ленстра, Л. Ловас) под названием «Алгоритм приведенного базиса», разрешившим скоростной вопрос в принципальном плане.

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

В страну неприводимых многочленов сделан первый шаг — мы познакомились с ее признаными лиDEPами. Но другие ее представители — как известные, так и не исследованные — остались за кадром. Страна неприводимых многочленов полна загадок и каждой новый шаг в нее рождает новые вопросы.

Приложение

Здесь мы приводим общеанное посяжение доказательства признака Дюма. Но сначала Разборка и сборка. Диаграмма Ньютона несет важную информацию о многочлене $P(x)$ . Хранить ее удобно в разобранном виде.

Правило разборки. Разломаем диаграмму на звенья, в конце нарисуем стрелки и пересечем их параллельно себе (как векторы) в начальной точку (рис. 8). Так получается

Рис. 8.

связка многочлена по простому $p$ . Если точка основы лежит внутри звена (у нас — точка (6; 1) на последнем звене), то ломать звено в этой точке не следует.

Правило сборки. Двигаясь сизу вверх (против часовой стрелки) выкладываем векторы связи друг за другом (см. рис. 8). Итак: Заданной диаграмме Ньютона соответствуетровно одна связка, и по заданной диаграмме восстанавливается однозначно.

Остается заметить, что местоположение на оси ОМ точки приложения связи не играет существенной роли. Умножая $P(x)$ на подходящую степень $p'$ (что не меняет свойства неприводимости), можно произвольно перемещать всю диаграмму, а вместе с ней и начальную точку, вдоль оси ОМ.

Теорема Дюма. Связка произведения $P(x)Q(x)$ представляет собой объединение связискомителей $P(x)$ и $Q(x)$ (рис. 9).

Рис. 9.

Здесь $Q(x)=b_0+b_1x+\dots+b_mx^m$ — это еще один, какий-нибудь, многочлен (подойдёт и $Q(x)$ со страницами 14). Его основа, диаграмма и связка — красные.

Теорема Дюма показывает, как, зная диаграммы многочленов $P(x)$ и $Q(x)$ по одному и тому же простому $p$ , построить диаграмму их произведения. Для этого следует наложить друг на другу связки компонентей, совместив их начальные точки, а затем построить ломанную по правилам сборки (рис. 10).

Рис. 10.

Добавление. Если в связи произведения $P(x)Q(x)$ два звена частично или полностью совпадают, то одно из них следует вытянуть из связки и поставить вслед за другим.

Секрет призника Дюма теперь прост — если $P(x)$ приводим, то по теореме Дюма его связка всегда состоит либо из нескольких звеньев, либо из одного, но тогда непреемно составляет (см. Добавление еще раз).

Для доказательства призника ингредиентов теорему ТЕОРЕМУ («Квант» № 10, с. 7), написавы диagrмму линейного движения (она состоитровно из одного примитивного звена) и вывести из теоремы Дюма утверждение:

Если все простые связи связи имеют проекцию на ось ОК длины > k, то все делители многочлена $P(x)$ имеют степени > k.

Доказательство теоремы Дюма основано на том, что умножению многочлена $P(x)$ на одной $b_kx^k$ соответствует на плоскости ОКМ перенос основных $P(x)$ на вектор с координатами $(k; l)$ , где $(k; l)$ — точка основы $Q(x)$ , отвечающая однозначну $b_kx^k$ . Дальнейшие рассудения (вплоне элементарные) не вошли в рамках этой статьи и мы их опускаем.