Связанный Ландау-Миньотт

Ограничение коэффициентов факторного полинома

В алгебре граница Ландау -Миньотта (иногда называемая просто границей Миньотта ^[1] ) — это одно из семейства неравенств, касающихся одномерного целочисленного многочлена f ( x ) и одного из его множителей h ( x ). Базовая версия утверждает, что коэффициенты h ( x ) ограничены независимо от h ( x ) экспоненциальным выражением, включающим только степень и коэффициенты f ( x ), т. е . зависящим только от f ( x ).

Он имеет приложения в компьютерной алгебре , где эти границы могут дать априорные оценки времени выполнения и сложности алгоритмов . ^[2]

Базовая версия

Для такого, что делит обозначает соответственно сумму абсолютных значений коэффициентов соответственно и пусть будет степенью , тогда ${\displaystyle f(x),h(x)\in \mathbb {Z} [x]}$ ${\displaystyle h(x)}$ ${\displaystyle f(x)}$ ${\displaystyle \|h\|_{1}}$ ${\displaystyle \|f\|_{1}}$ ${\displaystyle h(x)}$ ${\displaystyle f(x)}$ ${\displaystyle n}$ ${\displaystyle f(x)}$

${\displaystyle \|h\|_{1}\leq 2^{n}\|f\|_{1}}$

Обозначение

${\displaystyle f,g,h\in \mathbb {C} [x]}$будут одномерными комплексными многочленами , которые позже будут ограничены целочисленными многочленами , т.е. в . Явно ${\displaystyle \mathbb {Z} [x]}$

${\displaystyle f=\sum \limits _{i=0}^{n}f_{i}x^{i},\ \ \ g=\sum \limits _{i=0}^{m}g_{i}x^{i},\ \ \ h=\sum \limits _{i=0}^{k}h_{i}x^{i}.}$

${\displaystyle n,m,k}$- степени , старшие коэффициенты - . ${\displaystyle f_{n},g_{m},h_{k}}$

Определить нормы , рассматривая коэффициенты как векторы, явно

${\displaystyle \|f\|_{\infty }=\max _{0\leq i\leq n}|f_{i}|,\ \ \ \|f\|_{2}=\left(\sum \limits _{i=0}^{n}|f_{i}|^{2}\right)^{1/2},\ \ \ \|f\|_{1}=\sum \limits _{i=0}^{n}|f_{i}|.}$

По основной теореме алгебры имеет корни (с кратностью ). Установим меру Малера равной ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle z_{1},z_{2},\ldots ,z_{n}}$ ${\displaystyle f}$

${\displaystyle M(f)=|f_{n}|\prod \limits _{i=1}^{n}\max\{1,|z_{i}|\}.}$

Аналогично определяют , , и т.д. ${\displaystyle \|g\|_{2}}$ ${\displaystyle M(h)}$

Неравенство Ландау и другие основные свойства

В 1905 году Ландау доказал ^[3] ключевое неравенство, связывающее меру Малера многочлена с его евклидовой нормой .

${\displaystyle M(f)\leq \|f\|_{2}}$

В общем случае нормы подчиняются следующим неравенствам:

${\displaystyle \|f\|_{\infty }\leq \|f\|_{2}\leq \|f\|_{1}\leq {\sqrt {n+1}}\|f\|_{2}\leq (n+1)\|f\|_{\infty }.}$

Мера Малера удовлетворяет , что для нетривиальных целочисленных полиномов подразумевает . См. также гипотезу Лемера . ${\displaystyle M(f)\geq |f_{n}|}$ ${\displaystyle M(f)\geq 1}$

Мера Малера является мультипликативной, т.е. если то ${\displaystyle f=gh}$

${\displaystyle M(f)=M(g)M(h).}$

Миньотта связана

Миньотт использовал неравенство Ландау в 1974 году для доказательства базовой версии ^[4] следующих границ ^{[2] : 164 и далее} в обозначениях, введенных выше.

Для комплексных полиномов в , если делит , то ${\displaystyle \mathbb {C} [x]}$ ${\displaystyle h}$ ${\displaystyle f}$

${\displaystyle \|h\|_{1}\leq 2^{k}M(h)\leq 2^{k}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq 2^{n}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}$

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

${\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq {\binom {n}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}$

Если дополнительно и являются целыми многочленами от тогда и если дополнительно является моническим тогда даже . В этих случаях можно упростить, опустив дробь. Включая произведения в анализ, мы имеем следующую теорему. ${\displaystyle f}$ ${\displaystyle h}$ ${\displaystyle \mathbb {Z} [x]}$ ${\displaystyle 0<{\frac {|h_{k}|}{|f_{n}|}}\leq 1}$ ${\displaystyle f}$ ${\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1}$

Пусть такое, что делит тогда ${\displaystyle f,g,h\in \mathbb {Z} [x]}$ ${\displaystyle gh}$ ${\displaystyle f}$

${\displaystyle \|g\|_{\infty }\|h\|_{\infty }\leq \|g\|_{2}\|h\|_{2}\leq \|g\|_{1}\|h\|_{1}\leq 2^{m+k}\|f\|_{2}\leq 2^{n}{\sqrt {n+1}}\|f\|_{\infty },}$

${\displaystyle \|h\|_{\infty }\leq \|h\|_{2}\leq \|h\|_{1}\leq 2^{k}\|f\|_{2}\leq 2^{n}\|f\|_{2}\leq 2^{n}\|f\|_{1},}$

${\displaystyle \|h\|_{\infty }\leq \|h\|_{2}\leq \|h\|_{1}\leq 2^{k}\|f\|_{2}\leq 2^{k}{\sqrt {n+1}}\|f\|_{\infty }\leq 2^{n}{\sqrt {n+1}}\|f\|_{\infty },}$

${\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}\|f\|_{2}\leq {\binom {n}{i}}\|f\|_{2},}$

${\displaystyle \|h\|_{\infty }\leq {\binom {k}{\lfloor k/2\rfloor }}\|f\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{1}.}$

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

${\displaystyle \|h\|_{\infty }\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{2}\approx 2^{n}{\sqrt {\frac {2}{\pi n}}}\|f\|_{2}.}$

Из границ отдельных коэффициентов можно вывести следующую связанную границу.

Если приводимо , то оно имеет нетривиальный множитель степени такой, что ${\displaystyle f\in \mathbb {Z} [x]}$ ${\displaystyle h}$ ${\displaystyle k\leq \lfloor n/2\rfloor }$

${\displaystyle \|h\|_{\infty }\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|f\|_{2}\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|f\|_{1}.}$

Объединение этого с формулой Стирлинга для замены биномиальных коэффициентов приводит к более явным версиям.

В то время как верхние границы, которые не зависят от и зависят только от , представляют большой теоретический интерес и эстетическую привлекательность, в практическом применении обычно имеется информация о степени . Вот почему более точные границы, которые дополнительно зависят от , часто более актуальны. ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle h}$ ${\displaystyle k}$

Резкость границ

Циклотомические многочлены

Для циклотомических многочленов есть неприводимый делитель степени , функция Эйлера . В этом случае и принято обозначать . Результат Вона утверждает ^[5] для бесконечного множества положительных целых чисел ${\displaystyle f=x^{n}-1}$ ${\displaystyle h=\Phi _{n}(x)}$ ${\displaystyle k=\varphi (n)}$ ${\displaystyle \|f\|_{2}={\sqrt {2}}}$ ${\displaystyle \|h\|_{\infty }=A(n)}$ ${\displaystyle n}$

${\displaystyle \|h\|_{\infty }=A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)},}$

суперполиномиальная оценка в степени . ${\displaystyle n}$

Сравнивая с границей Миньотта и используя формулу Стирлинга, а также границы для функции Эйлера, получаем для бесконечного множества ${\displaystyle n}$

${\displaystyle e^{\left(n^{(\log 2)/(\log \log n)}\right)}<\|h\|_{\infty }\leq {\binom {k}{\lfloor k/2\rfloor }}\|f\|_{2}={\binom {\varphi (n)}{\lfloor \varphi (n)/2\rfloor }}{\sqrt {2}}\approx 2^{\varphi (n)}{\sqrt {\frac {2}{\pi \varphi (n)}}}{\sqrt {2}}\geq 2^{e^{-\gamma }n/(\log \log n)}{\frac {2}{\sqrt {\pi e^{-\gamma }n/(\log \log n)}}}.}$

Это оставляет разрыв между верхней границей Миньотта и тем, что, как известно, достигается с помощью циклотомических многочленов. Циклотомические многочлены не могут закрыть этот разрыв по результату Бейтмана , который утверждает ^[6] для каждого для всех достаточно больших положительных целых чисел мы имеем ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$

${\displaystyle \|h\|_{\infty }=A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}.}$

Также следует отметить, что, несмотря на суперполиномиальный рост нижней границы Вона, на практике при рассмотрении примеров циклотомических полиномов коэффициенты оказываются намного меньше, чем у границы Миньотта. ${\displaystyle h=\Phi _{n}(x)}$

Семейство многочленов с экспоненциальным ростом коэффициентов его множителей

Эббот приводит следующий пример ^[7], связанный с циклотомическими многочленами.

${\displaystyle H(x)=(x+1)(x^{2}+x+1)=x^{3}+2x^{2}+2x+1,\ \ \ F(x)=H(x)\cdot H(-x)=-x^{6}+1}$

и рассмотрим для положительных целых чисел ${\displaystyle j}$

${\displaystyle h=h_{j}=H(x)^{j},\ \ \ f=f_{j}=F(x)^{j}.}$

Обратите внимание, что степени соответственно . Эббот показывает, что асимптотически для больших мы имеем ${\displaystyle k=3j}$ ${\displaystyle n=6j}$ ${\displaystyle j}$

${\displaystyle \|h_{j}\|_{\infty }\geq 6^{j}{\frac {1}{3j+1}},\ \ \ \|f_{j}\|_{\infty }\approx 2^{j}{\sqrt {\frac {2}{\pi j}}}.}$

Используя границу Миньотта в версии, которую мы сравниваем ${\displaystyle \|h\|_{\infty }\leq 2^{k}{\sqrt {n+1}}\|f\|_{\infty }}$

${\displaystyle 3^{n/6}{\sqrt {\frac {\pi }{3n}}}\approx {\frac {6^{j}{\frac {1}{3j+1}}}{2^{j}{\sqrt {\frac {2}{\pi j}}}}}\lesssim {\frac {\|h\|_{\infty }}{\|f\|_{\infty }}}\leq 2^{k}{\sqrt {n+1}}=2^{n/2}{\sqrt {n+1}}}$

Игнорирование корневых терминов приводит к

${\displaystyle 1.2009^{n}\approx {\sqrt[{6}]{3}}^{n}\lesssim {\frac {\|h\|_{\infty }}{\|f\|_{\infty }}}\lesssim {\sqrt {2}}^{n}\approx 1.4142^{n}.}$

Эббот утверждает, что ^{[7] : 24}

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

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

Обратите внимание, что Эббот также сравнивает границу Миньотта с другими типами границ и приводит примеры, где граница Миньотта является лучшей, а также примеры, где другие границы лучше ^{[7] : 7ff} .

Также обратите внимание, что, хотя циклотомические многочлены из предыдущего раздела являются неприводимыми множителями, множители сами имеют много множителей. Эббот размышляет ^{[7] : 32} ${\displaystyle h=\Phi _{n}(x)}$ ${\displaystyle h=h_{j}=H(x)^{j}=(x+1)^{j}(x^{2}+x+1)^{j}}$

Примеры [...] заставляют любую идеальную «неприводимую однофакторную границу» расти со степенью, хотя скорость роста, по-видимому, намного медленнее, чем для однофакторных границ, действительных для любой (соответствующим образом масштабированной) факторизации в . Это говорит о том, что такая идеальная однофакторная граница может быть намного меньше известных в настоящее время. ${\displaystyle \mathbb {C} [x]}$

Обобщения

Обычно границы Миньотта устанавливаются только для комплексных или целочисленных многочленов. Они в равной степени справедливы для любого подкольца , в частности, при рассмотрении только мономических многочленов, для которых . ${\displaystyle R\subset \mathbb {C} }$ ${\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1}$

Любое абстрактное числовое поле и его кольцо целых чисел можно считать подкольцом , однако может быть несколько вложений, которые неэквивалентны относительно абсолютных значений. Границы Миньотта абстрактны и достаточно общны, чтобы они сохранялись независимо от выбранного вложения. Это можно воспринимать как намек на то, что они не настолько узки, насколько это возможно в принципе, как это действительно можно увидеть из конкурирующих границ, которые иногда лучше ^{[7] : 7ff} . ${\displaystyle \mathbb {C} }$

Приложения

В компьютерной алгебре при выполнении эффективных вычислений с целочисленными многочленами часто применяется следующая стратегия. Многочлен редуцируется по модулю подходящего простого числа, ${\displaystyle f}$ ${\displaystyle p}$ чтобы получить , решается связанная задача над вместо , что часто проще, и, наконец, используется поднятие Гензеля для переноса результата обратно в . ${\displaystyle f_{p}}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle f_{p}}$ ${\displaystyle f}$

Подъем Гензеля — это итеративный процесс, и в общем случае неясно, когда его следует остановить. Границы Ландау-Миньотта могут предоставить дополнительную априорную информацию, которая позволяет задать явные границы того, как часто подъем Гензеля должен быть итерирован для восстановления решения для из решения для . ${\displaystyle f}$ ${\displaystyle f_{p}}$

В частности, это может быть применено к факторизации целочисленных многочленов ^[1] или для вычисления НОД целочисленных многочленов ^{[2] : 166.} Несмотря на эффективность , этот подход может быть не самым эффективным , как можно видеть в случае факторизации .

Смотрите также

• Разделительная граница Миньотта

Ссылки

1. Bhatt, Bhuvanesh. «Граница Ландау-Миньотта». MathWorld — веб-ресурс Wolfram, созданный Эриком В. Вайсштейном . Wolfram Research Inc. Получено 06.05.2023 .
2. von zur Gathen, Иоахим; Герхард, Юрген (2013). Современная компьютерная алгебра. Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 9781139856065.
3. Ландау, Эдмунд (1905). «Sur quelques theorèmes de M. Petrovitch relatifs aux zéros des fonctions Analytiques». Бюллетень математического общества Франции . 33 : 251–261. дои : 10.24033/BSMF.760 .
4. Миньотт, Морис (1974). «Неравенство о факторах многочленов». Математика вычислений . 28 (128): 1153–1157. doi : 10.2307/2005373 . JSTOR  2005373.
5. Vaughan, RC (1975). «Границы для коэффициентов циклотомических полиномов». Michigan Math. J . 21 (4): 289–295. doi : 10.1307/mmj/1029001352 .
6. Бейтман, Пол Т. (1981). «О размерах коэффициентов циклотомного полинома». Семинар теории чисел Бордо : 1–17. JSTOR  44165422.
7. Эбботт, Джон (2013). «Границы факторов в Z[x]». Журнал символических вычислений . 50 : 532–563. arXiv : 0904.3057 . doi : 10.1016/j.jsc.2012.09.004. S2CID  15176498.