6.3. Подъем (mod p) - разложения до разложения над целыми числами

В этом разделе мы рассмотрим, как поднять разложение до разложения над целыми числами, и в этом процессе мы откажемся от ограничения, что полином нормирован. Читателю следует в этом месте еще раз просмотреть разд. 6.1.2.

Прежде всего давайте соберем вместе различные соображения о разложении полинома в общем случае. Предположим, что полином разлагается на множители над целыми числами и что тогда по теореме для всех простых , так что за исключением случал существует нетривиальное разложение по модулю р. Поэтому в попытке восстановить возможное разложение полинома над целыми числами можно использовать эффективный алгоритм полиномиального разложения в [рассматривавшийся в разд. 6.2]. Если, например, для данного полинома степени 8 выполняются со отношения а для другого простого числа — соотношения то, поскольку в разложении нет сомножителей степени 2, полином должен быть неприводимым над целыми числами.

Приведенный выше пример, мажет быть, слишком прост и прямолинеен, и следует отметить, что неприводимость далеко не всегда устанавливается так легко. Следует помнить, что для всех к 2 Свиннертон-Дайер (Swinnerton-Dyer, 1970) построил полиномы степени 2, неприводимые над целыми числами, но полностью разлагающиеся на линейные и квадратичные множители по модулю любого простого числа.

Если мы попытаемся найти сомножители полинома рассматривая его поведение по модулю разных простых чисел, то в общем случае результаты не так легко свести воедино. Поэтому желательно ограничиться одним простым числом и посмотреть, какие «дивиденды» могут быть из него извлечены при условии, что по нашему убеждению сомножители по модулю этого простого числа имеют нужные степени. Мы в деталях рассмотрим два подхода: выбор одного большого простого числа и выбор одного маленького простого числа в комбинации с «подъемом».

Мы начнем с первой идеи, а именно разлагать полином по модулю большого простого , где — некоторое число, большее удвоенного значения абсолютной величины коэффициентов всех возможных делителей полинома , т.е. коэффициенты любого истинного разложения над целыми числами должны в действительности лежать между . [Ниже мы вычисляем границы коэффициентов делителей полинома не вычисляя самих этих делителей.] Тогда все возможные делители над целыми числами могут быть «вычитаны из делителей по модулю , которые мы умеем вычислять. За этим подходом скрываются следующие рассуждения. Если мы выберем маленькое простое ), то в общем случае мажет существовать много способов согласовать это разложение с разложением на множители полинома над целыми числами. Например, рассмотрим полином

По модулю 13 полином разлагается следующими способами:

(См. также пример в разд. 6.2.4.) Заметим, что существует много полиномов, сравнимых с каким-либо сомножителем которые могут быть сомножителями полинома над целыми числами, и для того чтобы обнаружить истинные сомножители в потребуются определенные усилия. [Этой проблемы не существует, если мы работаем с нормированным полиномом Итак, предположим теперь, что , где достаточно велико, так что коэффициенты любого возможного делителя полинома степень которого равна степени полинома лежат между более того, предположим, что мы выбрали так, что все его коэффициенты лежат в этом интервале. Тогда если где ), то должно выполняться равенство . [В противном случае существует коэффициент полинома , отличающийся от соответствующего коэффициента полинома ненулевым кратным числа . Но тогда этот

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

Рассмотрим теперь, как найти подходящее большое . (В этом месте читателю следует еще раз посмотреть определения различных норм полиномов, введенные в разд. 1.2.)

Ограничения на коэффициенты делителей полинома.

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

Теорема 6.3.1. Пусть — нормированный полином с комплексными коэффициентами, и предположим, что все его комплексные корни по абсолютной величине меньше некоторого положительного вещественного числа b. Если — нормированный делитель полинома , то все коэффициенты полинома по абсолютной величине

Локазательство. В пусть где — — комплексные корни полинома Перемножая разложение и приравнивая коэффициенты, получаем

Поскольку каждый , является корнем полинома имеет место неравенство b. Поэтому, пользуясь неравенством треугольника, для каждого мы получаем, что не превосходит суммы, полученной заменой всех на 6. Например, при

Заменяя каждый s на 6, получаем полином Таким образом,

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

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

Теорема 6.3.2 (Specht, 1949). Пусть нормированный полином с комплексными коэффициентами. Кроме того, пусть — корни полинома (с соответствующими кратностями), такие, что Тогда

Локазательство. Доказательство достаточно громоздко, и мы его опускаем. Оно имеется в работе Шпехта (Specht, 1949) на немецком языке и (другое) в статье Миньотта (Mignotte, 1974) на английском. (См. также историческое замечание

Из хорошо известного выражения для коэффициентов полинома замечаем, что для выписанного выше полинома

и

Теперь мы готовы получить границу для коэффициентов делителей полинома

Теорема 6.3.3 (Mignotte, 1974). Пусть — нормированный полином в и предположим, что где нормированные полиномы в Тогда

где кроме того, если — один из этих сомножителей, где то

Доказательство. Оно непосредственно следует из теорем 6.3.1, 6.3.2 и хорошо известной формулы для коэффициентов полинома, выписанной выше.

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

Рассмотрим теперь второй подход. Вместо использования больших простых чисел , которые должны быть чрезвычайно велики, если у полинома высокая степень или большие коэффициенты (или и то, и другое), мы можем также использовать маленькие простые числа при условии, что полином свободен от квадратов. Один из лучших методов разложения полинома над целыми числами, известных к настоящему времени, состоит в том, чтобы разложить его по модулю для маленького простого , а затем расширить (или «поднять») это разложение единственным способом до разложения по модулю для подходящего к, определенного условием