Граница Ландау-Миньотта

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

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

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

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

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

Обозначения

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

$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}.$

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

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

$\|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}|.$

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

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

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

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

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

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

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

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

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

Мера Малера мультипликативна, т.е. если $f=gh$ затем

$M(f)=M(g)M(h).$

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

Миньотт использовал неравенство Ландау в 1974 году, чтобы доказать базовую версию. следующих границ в введенных выше обозначениях.

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

$\|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}$

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

$|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}$

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

Позволять $f,g,h\in \mathbb {Z} [x]$ такой, что $gh$ делит $f$ затем

$\|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 },$

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

$\|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 },$

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

$\|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}.$

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

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

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

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

$\|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}.$

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

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

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

Циклотомные полиномы

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

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

суперполином, ограниченный в степени $n$.

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

$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)}}}.$

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

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

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

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

Эббот приводит следующий пример связанные с круговыми полиномами. Набор

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

и рассмотрим положительные целые числа $j$

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

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

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

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

$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}}$

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

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

Эббот утверждает, что

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

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

Обратите внимание, что Эббот также сравнивает границу Миньотта с другими типами границ и приводит примеры, где граница Миньотта является лучшей, и примеры, где другие границы лучше. .

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

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

Обобщения

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

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

Приложения

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

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

В частности, это можно применить к факторизации целочисленных полиномов. или для вычисления НОД целочисленных полиномов . Несмотря на свою эффективность , этот подход, возможно, не самый эффективный , как можно видеть на примере факторинга .

См. также

• Разлука Миньотт связана