AOP_Tom2 (1021737), страница 208
Текст из файла (страница 208)
Следовательно, (г(8ы..., 8 )( < А((дг( — дз) . ((5' ( — 4 ) + (81(((82(. ° . (5.( — ((оз( — иг)... ((о ! — а.)). [В., А. !ьеМ11!о апа В.. ь. 1ьрсоп, 1лб Ргос. 7егеегв 7 (1978), 193-195.! Примечание. Указанная верхняя грань — наилучшая из возможных, так как для полинома /(хц...,х„) = [1(хь — вь ( вь б 8м 1 < Й < 81, 1 < 7' < а) достигается равенство. Однако существует другой подход, при котором верхняя грань может быть значительно улучшена, котя и в другом смысле.
Пусть /~(хц....х,) = /(хц,х ) и пусть / ь~ (х ем..., х„) — любой ненулевой коэффициент при степени х, в /1(х„..., г„). Тогда можем положить д равным степени при х, в /, вместо (зачастую существенно большей) степени хь в /. Например, можем положить А = 3 и Ыг = 1 в полиноме х1хз — Зх[хг+ хе~+ 5. Это наблюдение гарантирует, что А + -ьд < д, .когда каждый член / имеет общую степень < ь(. Следовательно, вероятность в этих случаях равна при равенстве всех множеств 8м Если она < 1 и если /(хм, х„) становится равным нулю для 50 случайно выбранных векторов (х,,..., х„), то /(хм..., х„) тождественно равна нулю с вероятностью как минимум 1 — 2 за. Более того, если / (х,..., х„) имеет специальный вид х„'/~о(хьэц..., х„) с еь > О, можно получить 8 = 1, так как х должно быть равна О, когда /ьь.~(ягель,...,х ) 74 О.
Поэтому разреженные полиномы е только т ненулевыми членами будут иметь дз < 1 для минимум п — 18 т значений /р Применения этого неравенства для вычисления 8сс! и других операций над разреженными полиномами от многих переменных были введены Р. Цнппелем (К. Зйрре() (Ьессаге вогез ш Сошр. Боб 72 (1979), 216-226). Я. Т.
Шварц (Л. Т. 8сЪжагйв) (.1АСМ 27 (1980), 701-717! привел дальнейшие расширения, включая устранение больших чисел с помощью модулярной арифметики: если коэффициенты / целые, если Р является множеством целых чисел > д и если (/(хц...,х„)( < Ь для каждого хь б 5, то количество решений /(х~ ~ . ~ х ) = 0 (глод р) для р б Р не превышает 12. (а) Для удобства опишем алгоритм только для А = (а, 6). Из наших посылок следует, что г1еб(1ч(у) = стеб(ЯгЪ') > О, деб(г".)г) < деб(Яг). Если г1еб(Яг) = О, то Цг представляет собой просто ненулевое рациональное число, так что мы считаем О = ЯгЯг. В противном случае пусть Яг — — асгн + Лагг + гм Яг = аЯг1 + Лгягг + гг, где гг и гг — рациональные числа; отсюда следует, что Огà — гкгК = а(Яг Я вЂ” (ггг1") + 6(1сггбг — ЯггК) + ггпу — ггпу У нас должно быть либо г)еб(Ягг) =бей(Ог) — 1, либо бей(Огг) =бей(Яг)-1.
В первом случае, рассматривая члены высшей степени, которые начинаются с а, имеем бей(Ягг(г'- Ягг1г) < г1еб(Ог г6Г); так что можем заменить Ог на Ян, Ог на Огг и повторить процесс. Подобным образом в последнем случае можно заменить Яп Яг) на (Огг, Ягг) и повторить процедуру.
(Ь) Положим, что бей(1г) > стеб(Г). Если бей(Н) > деб(Ъг), то заметьте, что Яг бг-Яг1г = Я,Н вЂ” (Ог — ЯгЯ)Ъ" имеет степень, меньшую, чем деб(К) < Йеб(ОгН), так что можно повторить процесс с 11, замененным на Н. Получим Н = 41'$'+ Н', бг = (19+ Я')Г + Н', где бек(В') < бей(Н), так что в конце концов решение будет получено. (с) Алгоритм из (Ь) дает рг = бгЪг + Н, г1еб(Н) < г1еб(1'г); в силу однородности Н = О и сГ однородно.
(б) Мы можем положить, что бей(К) < с~об(сг). Если бей(К) = О, установить )(' г — У; в противном случае воспользуемся результатом (с) для поиска ЛГ = Цг', так что ЯЪ'Ъ'= г'1)Ъ; Я1г — 1г1„г)1г = О, Отсюда следует, что ЯК = Ксг', так что можно установить 6г г — Г, 1г +- Я и повторить процесс. Более подробная информация о рассматриваемом вопросе приводится в работе Р. М.
СоЬп, Ргос. Сапгбггс19е Р1нб Яос. 37 (19б1), 18-30, Существенно более сложная задача описания всех строковых полиномав, таких, что (УЪ' = )гьг, была решена Дж. М. Бергманом (С. М. Вегбшап) [РЬ. В. 1Ьевгв, НагчаЫ 1)пгтегвггу, 19бу). 19. [Р. М. СоЬп, Тгапзасг1опз оГ гЛе Атее. Маей. Яос. 109 (1993), 332 — Збб.[ С1.
Установить иг г — 6гг, иг г — 11г, аг г- Ъм аг г- Ъю гг ь- гг ь- юг г- югг г- 1, г[ Ф-гг< иг[ ",— юг ~ О, пг — О. С2. (В этот момент выполняются данные в условии упражнения тождества и игаг —— игог; аг = 0 тогда и только тогда, когда иг = 0.) Если аг = О, алгоритм завершается с НОПД(1гн )гг) = ег, ПОЛК(1гм Кг) = г',)гг = -гг'гг. (Кроме того, в силу симметрии имеем НОЛД(6гг, 6гг) = иг и НОПК(сг,, (гг) = (Ггюг = — Пгюг ) С3.
Найти О и Н, такие, что ег — — Яаг+ Н, где бей(Н) < г1еб(ог). (Имеем и~ (Яег+ Н) = игаг, так что иг В = (иг — и~ Я)ог = Н'ог.) С4. Установить (в>м юг, и'„юг, гм гг, г[, гг, им иг, ем аг) г- (гс', — ичЯ, юг — югЯ, пп, шг, г'„гг, г, — Яг'„гг — Щ, иг — игЯ, им аг, ог — г,гиг) и и г- и+ 1. Вернуться к шагу С2. 3 Это расширение алгоритма Евклида включает большинство особенностей> которые встречались в предыдущих расширениях алгоритма Евклида. Это приводит нас к новому пониманию уже рассмотренных частных случаев. Для доказательства корректности алгоритма сначала заметим, что бей(аг) уменьшается на шаге С4, так что алгоритм обязательно завершается.
По завершении алгоритма вг представляет собой общий правый делитель 1гг и 1гг, поскольку иош = ( — 1)" 1гг и — югог = ( — 1)" Ъд. Также, если 4 является любым общим правым делителем 'гг и )гг, он является н правым делителем г~ Ъг+ггКг = и,. Следовательно, аг — — НОПДЯ,1'г). Кроме того, если пг является любым общим левым кратным Ъг и Ъг, без потери общности можно считать, что т = се = 6гг1гг, поскольку последовательность значений Ог не зависит ат 6гг и ьгг. Значит, гп = (-1)" (-игл[)$~ (-1)" (иггг)1'г кратно г',)гь На практике, чтобы вычислить только НОПД(!гг, Уг), можно опустить вычисление и, шз~ ш[ шг~ гм гг, г',, зг. Эти дополнительные величины были добавлены к алгоритму, в первую очередь, чтобы более просто установить его корректность.
Примечание. Нетривиальное разложение строковых поливанов, таких, как приведенные в качестве примера в этом упражнении, могут быть найдены из матричных тождеств наподобие (' ')(' ')(' 'Н'-'Н'-')('-')=С' ') поскольку эти тождества выполняются даже при некоммутативности умножения, например (аЬс + а + с) (! + Ьа) = (аЬ + 1)(сЬа + а + с). (Сравните это с контииуантами из раздела 4.5.3.) 19.
[См. Енбйпе СаЬеп, ТЛ4ог!е сЫ №пгЬгез 1 (Ране, 1914), 336-338.] Если такой алгоритм существует, то в соответствии с рассуждениями из упр. 18 Р является НОПД. Рассмотрим А и В как единую матрицу С размера 2и х и, первые и строк которой представлены строками А, а следующие и строк — строками В. Точно так же можно комбинировать матрицы Р и !Л в матрицу В размера 2и х и, а Х и У вЂ” в матрицу Я размера и х 2и. Требуемые условия теперь сводятся к двум уравнениям: С = ЕР, Р = ХС. Если можно найти целочисленную матрицу П размера 2и х 2и с детерминантам ш1, такую, что все последние и строк сГ 'С нулевые, то решением будут матрипы В = (первые и столбцов С), Р = (первые и строк Г гС), Я = (первые и строк Ьг ~).
Поэтому можно нспшгьзовать, например, следующий алгоритм (с т = 2и). Алгоритм Т (Триангуллризацил). Пусть С вЂ” целочисленная матрица размера т х и. Данный алгоритм находит целочисленные матрицы П и !г размера т х т такие, что СУ = Л и !'С представляет собой треугольную матрицу (такую, что элемент на пересечении г'-й строки и Лкго столбца матрицы 1'С равен нулю, если з > Л). Т1. [Инициализация.] Установить П ь- У ь- 1 (Л вЂ” единичная матрица размера т х т) и Т г- С. (На протяжении всего алгоритма будут выполняться соотношения т = !гс и !Л' ж 1.) Т2. [Итерация поЛЬ] Выполнить шаг ТЗ для,! = 1, 2,, ш!п(ги, и); затеи прекратить выполнение алгоритма. Т3.
[Обнуление столбца !.] Не выполнять следующие действия или выполнять их до тех пор, пока Тм не станет равным нулю для всех г > Л. Пусть ТЮ вЂ” ненулевой элемент (Т„, Тйч.,у,, Т ), имеющий наименьшее абсолютное значение. Переставим строки Ь и Л матриц Т и !г и переставим столбцы Ь и Л матрицы Г эатем вычтем строку л из строки г )то)т, ] раз в матрицах т и !' и прибавим столько же раз столбец г к столбцу Л в матрице Сдлп у < г < ги. $ Длл приведенного в упражнении примера алгоритм дает (з ~) = (з г)(е -г) (г г) (~ з)(' г) (' г) = (' е)(' г) + (е е)(~ з).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
