Полином Суиннертона-Дайера

Семейство многочленов

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

При заданном конечном наборе простых чисел , полином Суиннертона-Дайера, связанный с , является полиномом: где произведение распространяется на все варианты знака в прилагаемой сумме. Полином имеет степенные и целочисленные коэффициенты, которые чередуются по знаку. Если , то является приводимым по модулю для всех простых чисел , на линейные и квадратичные множители, но неприводимым над . Группа Галуа для является . ${\displaystyle P}$ ${\displaystyle P}$ $${\displaystyle f_{P}(x)=\prod \left(x+\sum _{p\in P}(\pm ){\sqrt {p}}\right)}$$ ${\displaystyle 2^{|P|}}$ ${\displaystyle f_{P}(x)}$ ${\displaystyle 2^{|P|}}$ ${\displaystyle |P|>1}$ ${\displaystyle f_{P}(x)}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle f_{P}(x)}$ ${\displaystyle \mathbb {Z} _{2}^{|P|}}$

Первые несколько полиномов Суиннертона-Дайера: $${\displaystyle {\mathcal {P}}=\{2\}:\quad f_{P}(x)=(x-{\sqrt {2}})(x+{\sqrt {2}})=x^{2}-2}$$ $${\displaystyle {\mathcal {P}}=\{2,3\}:\quad f_{P}(x)=(x-{\sqrt {2}}-{\sqrt {3}})(x-{\sqrt {2}}+{\sqrt {3}})(x+{\sqrt {2}}-{\sqrt {3}})(x+{\sqrt {2}}+{\sqrt {3}})=x^{4}-10x^{2}+1}$$ $${\displaystyle {\mathcal {P}}=\{2,3,5\}:\quad f_{P}(x)=x^{8}-20x^{6}+352x^{4}-960x^{2}+576.}$$

Ссылки

• фон цур Гатен, Иоахим; Герхард, Юрген (апрель 2013 г.). Современная компьютерная алгебра (Третье изд.). Издательство Кембриджского университета. ISBN 9781107039032.
• Варди, И (1991), Вычислительные развлечения в Mathematica , Addison-Wesley, стр. 225–226
• Вайсштейн, Эрик В. «Многочлен Суиннертона-Дайера». MathWorld .
• OEIS : A153731