Метод Кронекера

Метод Кронекера — метод разложения многочлена с целыми коэффициентами на неприводимые множители над кольцом целых чисел; предложен в 1882 Кронекером.

Алгоритм Кронекера находит для данного многочлена ${\displaystyle F(x)}$ многочлен ${\displaystyle f(x)}$, такой, что ${\displaystyle F(x)}$ делится на ${\displaystyle f(x)}$, или доказывает, что такого многочлена нет.

Описание метода

Алгоритм Кронекера основан на следующих соображениях:

1. Если степень многочлена ${\displaystyle F}$ равна ${\displaystyle n}$, то степень хотя бы одного множителя ${\displaystyle f}$ многочлена не превосходит ${\displaystyle \left\lfloor {n \over 2}\right\rfloor }$ ;
2. Значения как ${\displaystyle F}$ , так и ${\displaystyle f}$ в целых точках — целые числа, причем ${\displaystyle f(i}$) делит ${\displaystyle F(i)}$ для любого целого ${\displaystyle i}$;
3. При фиксированном ${\displaystyle i}$, если ${\displaystyle F(i)}$ не равно 0, то ${\displaystyle f(i)}$ может принимать только конечное множество значений, состоящее из делителей числа ${\displaystyle F(i)}$;
4. Коэффициенты многочлена ${\displaystyle f}$ однозначно восстанавливаются по его значениям в точке.

Таким образом, для ${\displaystyle f}$ получается конечное число возможностей; непосредственным делением проверяем, получили ли делитель многочлена ${\displaystyle F}$.

Строгое Изложение:

Рассмотрим ${\displaystyle f(x)\in \mathbb {Z} [x]}$ — многочлен степени ${\displaystyle n}$. Пусть ${\displaystyle f(x)}$ приводим над ${\displaystyle \mathbb {Z} }$. Тогда ${\displaystyle f(x)=g(x)h(x)}$ и один из двух многочленов ${\displaystyle g(x)}$ и ${\displaystyle h(x)}$ имеет степень не выше ${\displaystyle n/2}$. Пусть без ограничения общности ${\displaystyle \operatorname {deg} \,g(x)\leqslant n/2}$. Тогда ${\displaystyle \forall a\in \mathbb {Z} \;g(a)\in \mathbb {Z} }$, следовательно ${\displaystyle f(a)\vdots g(a)}$. Рассмотрим ${\displaystyle m=n/2+1}$ различных целых чисел ${\displaystyle a_{i},i={\overline {1,m}}}$ таких, что ${\displaystyle f(a_{i})\not =0}$. Поскольку числа ${\displaystyle f(a_{i})}$ имеют конечное количество целых делителей, можно перебрать всевозможные наборы значений для ${\displaystyle g(a_{i})}$. По каждому такому набору построим интерполяционный многочлен ${\displaystyle g^{*}(x)}$ степени ${\displaystyle m-1=n/2}$. Если теперь ${\displaystyle f(x){\mathrel {\vdots }}g^{*}(x)}$, к многочленам ${\displaystyle g^{*}(x)}$ и ${\displaystyle {\frac {f(x)}{g^{*}(x)}}}$ можно применить тот же метод, и так до тех пор, пока все множители не станут неприводимыми. В противном случае, если ${\displaystyle \forall g^{*}(x)\ f(x){\mathrel {\cancel {\vdots }}}g^{*}(x)}$, многочлен ${\displaystyle f(x)}$ уже является неприводимым.

Одномерный алгоритм Кронекера

Запись алгоритма

Дано: ${\displaystyle f(x)\in \mathbb {Z} [x]}$

Надо: ${\displaystyle g(x)\in \mathbb {Z} [x]}$

Где: ${\displaystyle n}$ — степень полинома ${\displaystyle f}$, ${\displaystyle m}$ — степень полинома ${\displaystyle g}$, ${\displaystyle i}$ — целочисленное.

Цикл от ${\displaystyle i=0}$ до ${\displaystyle [n/2]}$

Если (${\displaystyle f(i)=0}$) то

${\displaystyle g=x-i}$

${\displaystyle m=1}$

Ответ найден.

Конец если

Конец цикла

Если (ответ не найден) то

${\displaystyle U}$ — множество делителей ${\displaystyle f(0)}$ (целочисленных)

Цикл от ${\displaystyle i=1}$ до ${\displaystyle [n/2]}$

${\displaystyle M}$ — множество делителей ${\displaystyle f(i)}$ (целочисленных)

${\displaystyle U:=}$ декартово произведение ${\displaystyle U}$ и ${\displaystyle M}$

Цикл для каждого ${\displaystyle u\in U}$

Построить многочлен ${\displaystyle g}$ степени ${\displaystyle i}$, такой, что ${\displaystyle g(j)=u(j)}$ для ${\displaystyle j=0...i}$

Если (${\displaystyle f}$ делится на ${\displaystyle g}$) то

${\displaystyle m=i}$

Решение успешно найдено, ответ ${\displaystyle g}$

Конец если

Конец цикла

Конец цикла

Конец если

Конец.

ЗАМЕЧАНИЕ. Достаточно научиться разлагать на множители многочлены со старшим коэффициентом, равным единице. Действительно, если старший коэффициент равен ${\displaystyle a}$, то домножив на ${\displaystyle a^{n-1}}$ и сделав замену ${\displaystyle x=y/a}$, сводим задачу к этому случаю. После её решения остается сделать обратную замену и сократить на общий множитель a_n−1 . Однако этот метод обычно оказывается неэффективным: из-за увеличения коэффициентов ухудшаются различные оценки и скорость работы алгоритмов. Поэтому в большинстве работающих алгоритмов таких преобразований не производится.

Реализация на Maple

kronecker:=proc(f::polynom)
 local g,i,n,U,V,j;
 with(linalg);
 n:=degree(f)/2; 
 U:=myfactor(subs(x=0,f));
 for i from 1 to n do
   U:=U,myfactor(subs(x=i,f));
   V:=mcarp(U);
   for j in V do   
    g:=interp([$0..i],j,x);
    if rem(f,g,x)=0 and not type(g,'constant') then     
      print(g);               
    end if;
   end do;
  end dо;  
end proc;

myfactor:=proc(n::integer)
 local a,b,i,j;
 b:=[];
 for i from 1 to abs(n) do
  if (irem(n,i)=0) then  
   b:=ArrayTools[Concatenate](2,b,i);
   b:=ArrayTools[Concatenate](2,b,-i);
  end if;
 end do;
 convert(b,'list');
end proc;

# Next 2 functions computes cartesian product of multiple sets.
# They are taken from http://people.oregonstate.edu/~peterseb/mth355/docs/355f2001-cartesian-product.pdf
carp:=proc(X,Y)
 local Z,x,y;
 Z:={};
 for x in X do
  for y in Y do
   Z:=Z union {[x,y]};
  end do;
 end do;
 return Z;
end proc;

mcarp:=proc()
 local Z,k,x,y; option remember;
  if nargs=0 then
   Z:={};
  elif nargs=1 then
   Z:=args[1];
  else Z:={};
   for x in mcarp( seq(args[k], k=1..nargs-1) ) do
    for y in args[nargs] do
    Z:= Z union {[op(x),y]};
    end do;
   end do;
  end if;
 return Z;
end proc;

Пример

${\displaystyle f(x)=x^{5}-x^{4}-2x^{3}-8x^{2}+6x-1}$(это многочлен с целыми коэффициентами и без рациональных корней). Если ${\displaystyle f(x)=g(x)h(x)}$ где степень k многочлена ${\displaystyle g(x)}$ не больше степени ${\displaystyle h(x)}$, то ${\displaystyle k=2}$. Тогда ${\displaystyle f(0)=-1;f(1)=-5;f(2)=-21}$. Делители этих чисел: для первого +1 и −1, для второго +1, −1, +5, −5, для третьего +1,-1, +3, -3, +7,-7,+ 21, -21. Всего получается ${\displaystyle 2\cdot 4\cdot 8=64}$ комбинации. Две комбинации отличающиеся лишь знаком, дают по сути один многочлен. Поэтому можно проверять лишь половину. Остаются 32 случая. Перебирая все эти случаи, можно найти лишь один многочлен 2-й степени, делящий ${\displaystyle f(x)}$. Это ${\displaystyle g(x)=x^{2}-3x+1}$. Оба сомножителя этого разложения неприводимы (как многочлены 2-й и 3-й степеней, не имеющие рациональных корней).

Многомерный алгоритм Кронекера

Запись условий задачи

Пусть ${\displaystyle D}$ — область целостности с однозначным разложением на множители, ${\displaystyle f(x_{1},...,x_{n})\in D[x_{1},...,x_{n}]}$. Требуется разложить ${\displaystyle f}$ на неприводимые множители.

Запись алгоритма

Дано: ${\displaystyle f\in \mathbb {Z} [x_{1},...,x_{n}]}$

Надо: ${\displaystyle G}$ — разложение

Переменные: многочлен ${\displaystyle {\bar {f}}\in \mathbb {Z} [y]}$, разложение ${\displaystyle {\bar {G}}}$ многочлена ${\displaystyle {\bar {f}}}$, множество ${\displaystyle M}$ элементов типа ${\displaystyle \mathbb {Z} }$.

Идея реализации: Редуцировать задачу к одномерному случаю, путём введения новой неизвестной и заменой всех переменных достаточно высокими степенями этой неизвестной. Факторизовать получившийся многочлен. Выполнить обратную подстановку, пробным делением убедиться, получено ли желаемое разложение.

Начало
Выбрать целое ${\displaystyle d}$ большее, чем степени отдельных переменных в ${\displaystyle f}$ заменить все переменные степенями новой неизвестной ${\displaystyle y}$:

${\displaystyle {\bar {f}}(y):=S_{d}(f)=f(y,y^{d},...,y^{d^{n-1}})}$

Разложить ${\displaystyle {\bar {f}}(y)}$ на неприводимые множители, то есть

${\displaystyle {\bar {f}}(y)={\bar {g}}_{1}(y)...{\bar {g}}_{s}(y),\quad {\bar {g}}_{i}(y)\in \mathbb {Z} [y],\quad 1\leq i\leq s}$

${\displaystyle G}$.число_множителей := 1

${\displaystyle m:=1}$

${\displaystyle M:=\{1,...,s\}}$

Цикл пока ${\displaystyle m\leq [s/2]}$

Цикл для каждого подмножества ${\displaystyle {i_{1},...,i_{m}}\subset M}$ пока ${\displaystyle m\leq [s/2]}$

${\displaystyle g_{i_{1},...,i_{m}}(x_{1},...,x_{n}):=S_{d}^{-1}({\bar {g}}_{i_{1}}(y){\bar {g}}_{i_{2}}(y)...{\bar {g}}_{i_{m}}(y))}$

Если ${\displaystyle f}$ делится на ${\displaystyle g}$ то

${\displaystyle G}$.множитель[${\displaystyle G}$.число_множителей]:=${\displaystyle g}$

${\displaystyle G}$.число_множителей:=${\displaystyle G}$.число_множителей + 1

${\displaystyle f:=f/g}$

${\displaystyle s:=s-m}$

${\displaystyle M}$.удалить{${\displaystyle i_{1},...,i_{m}}$}

Конец если

Конец цикла

${\displaystyle m:=m+1}$

Конец цикла
${\displaystyle G}$.множитель[${\displaystyle G}$.число_множителей]:=${\displaystyle f}$
Конец

В этом алгоритме обратное преобразование ${\displaystyle S_{d}^{-1}}$ определяется на одночленах по формуле:

${\displaystyle S_{d}^{-1}(y^{b_{1}+db_{2}+...+d^{v-1}b_{v}})=x_{1}^{b_{1}}...x_{v}^{b_{v}}}$

${\displaystyle (0\leq b_{i}<d}$ для ${\displaystyle 1\leq i\leq v,\quad v\in \mathbb {Z} )}$, далее ${\displaystyle S_{d}^{-1}}$ распространяется по линейности.

Литература

• Е. В. Панкратьев «Элементы компьютерной алгебры.» М.:МГУ, 2007;
• Kronecker L. «J. reine und angew. Math.», 1882;
• Окунев Л. Я. «Высшая алгебра», М., 1937;
• Курош А. Г. «Курс высшей алгебры», 11 изд., М., 1975;