ランドー・ミニョット境界

代数学において、ランダウ・ミニョット境界（ランダウ・ミニョットの境界とも呼ばれる^{[1] ）は、}単 変数整数多項式 f ( x ) とその因数の 1 つh ( x )に関する不等式の族の 1 つです。基本的なバージョンでは、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年にランダウの不等式を用いて、上で紹介した表記法の ¹⁶⁴以降にある以下の境界^[2]の基本バージョン^{[4]を証明した。}

の複素多項式について、が を割り切る場合、${\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)}.}$

また、実際には Vaugn の下限が超多項式的に増加するにもかかわらず、円分多項式の例を見ると、の係数はMignotte の下限よりもはるかに小さいことに注意してください。 ${\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。このアプローチは効果的ですが、因数分解の場合に見られるように、最も効率的ではない可能性があります。

• ミニョットの分離境界