Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 45
Текст из файла (страница 45)
имеет целыеp коэффициенты .Нетрудно, например, убедиться,что число (1 + 5)/2 — целое алгебpраическое, а число (3 + 4 −1)/5 — нецелое алгебраическое.Используются также термины приведенный, нормированный.Для избежания терминологической путаницы между целыми алгебраическими числами и обычными целыми, т. е. элементами Z, последние в теории алгебраическихчисел часто называют целыми рациональными числами.Приложение CЕсли | a | 6= 1, то с исследованием и решением уравнения (C.) серьезных трудностей не возникает, так как модуль значения показательной функции am монотонно возрастает или монотонно убывает,и можно получить логарифмическое ограничение на m.
Задача становится интересной при | a | = 1 и при дополнительном условии, чтоa не является корнем из 1. (Если a есть корень из единицы, то задачатривиальна.)Как это следует из элементарной теории алгебраических чисел,вопрос можно переформулировать так: дан неприводимый над Q полином f (x), deg f (x) = n, и некоторый полином q(x) над Q степениdeg q(x) < n; существуют ли такие натуральные m, чтоam = q(a)(C.)при любых a ∈ C, для которых f (a) = 0, и если да, то как найти такие m? Мы сосредоточимся на последнем вопросе, опуская мелкиеподробности перехода к нему от проблемы орбит.Особенность постановки вопроса об уравнении (C.) состоит втом, что речь идет не об одном фиксированном корне полинома f (x),но обо всех его корнях.
Легко показать, что если равенство (C.) верно для одного какого-то корня a0 полинома f (x), то оно верно длявсех корней этого полинома. В самом деле, если для некоторого фиксированного m полиномы x m − q(x) и f (x) имеют общий корень a0 ,то эти полиномы имеют нетривиальный общий делитель.
Наибольший общий делитель этих полиномов может быть найден алгоритмомЕвклида и, следовательно, должен иметь рациональные коэффициенты. Из этого и из неприводимости f (x) над Q следует, что наибольший общий делитель равен f (x). Отсюда получаем, что x m − q(x) делится на f (x). Это означает, что каждый корень f (x) является такжекорнем x m − q(x).Таким образом, задача о всей совокупности корней эквивалентна задаче об одном фиксированном корне, и задача об одном фиксированном корне эквивалентна задаче о любом другом корне.
Этообстоятельство позволяет справиться со случаем целого алгебраического a. К решению подводит серия результатов о корнях унитарныхполиномов над Z, начавшаяся с работ Кронекера и завершившаясяв —-е годы XX века исследованиями А. Шинцеля, Г. Цассенхауза,П. Бланксби и Х. Монтгомери . Выяснено, что если унитарный полином над Z степени n таков, что его корни не являются корнями изCм. [], []. Результаты Кронекера, Шинцеля и Цассенхауза изложены в [,разд.
.].Проблема орбитединицы, то у него найдется по меньшей мере один корень a, длякоторого | a | > 1. Бланксби и Монтгомери показали, что по меньшеймере для одного корня выполняется неравенство|a| ¾ 1 +1.30n2 ln(6n)(C.)Из этого позднее было выведено, что если корни неприводимого унитарного полинома f (x) степени n c целочисленными коэффициентами не являются корнями из единицы, то для любого натуральногорешения m уравнения (C.) выполнено неравенствоm ¶ n + 60n2 ln(6n)(ln(n + 1) + ln| q(x) |),(C.)где | q(x) | обозначает длину вектора коэффициентов полинома q(x):если q(x) = ck x k + ... + c1 x + c0 , тоÆ| q(x) | = c2k + ... + c21 + c20 .Решения уравнения (C.) для различных корней a полинома f (x)совпадают.
Доказанное может быть сформулировано следующим образом.Предложение C.. Пусть f (x) — неприводимый над Q полиномстепени n, корни которого не являются корнями из единицы. Пустьq(x) — некоторый полином над Q , степень которого меньше n. Тогда для любого корня a полинома f (x) существует не более одногонатурального решения уравнения (C.), при этом решения m уравнения (C.) для различных корней a полинома f (x) совпадают, и имеетместо оценка (C.).Несложно показать, что верны следующие утверждения:. Пусть h(x) ∈ Q и r(x) — остаток от деления h(x) на f (x). Пустьa ∈ C, f (a) = 0.
Тогда h(a) = r(a).. Пусть q1 (x), q2 (x), q3 (x), ... суть остатки от деления x, x 2 , x 3 , ...на f (x). Тогда• при k > 1 полином qk (x) равен остатку от деления xqk−1 (x) наf (x);• равенство (C.) имеет место, если и только если q(x) = qm (x).Из этих утверждений следует, что после того, как установлена граница M для возможного значения m, распознавание существованияи поиск натурального решения уравнения (C.) можно выполнить,затратив O(nM) арифметических операций над рациональными числами.Приложение CC. Неудачно выбранный размер входаОбратимся к уравнению (C.), предполагая, что среди коэффициентовунитарного неприводимого над Q полинома f (x) имеется по крайнеймере один нецелый рациональный; без специальных оговорок считаем, что корни f (x) не являются корнями из единицы.
Возникаетвопрос: можно ли и для этого случая получить подобную (C.) верхнюю оценку величины m? На протяжении ряда лет считалось, чтоответ положительный и что существует полином трех переменныхP(x1 , x2 , x3 ) такой, что даже при наличии среди коэффициентов f (x)нецелых рациональных чисел имеет место оценкаm < P(n, log2 | f |, log2 | q |),(C.)но затем выяснилось, что это неверно . Проблема заслуживает детального рассмотрения, поскольку ряд ее моментов является принципиальным. Вывод о существовании полинома P(x1 , x2 , x3 ) был сделан на основании утверждения о том, что если среди коэффициентовf (x) есть нецелые числа, то имеет место неравенствоm ¶ (n − 1) log2 | f |.(C.)Неравенство (C.) опровергается несложно (сразу заметно, что правая часть этого неравенства не зависит от вида полинома q(x), чтоподозрительно).
Мы, тем не менее, сосредоточим усилия на другом — покажем, что верхняя оценка (C.) не может иметь места нетолько при полиномиальной, но и, например, при показательнойxx 3x1 2функции того или иного вида (скажем, вида 2 ) и вообще прилюбой непрерывной функции P(x1 , x2 , x3 ). Это, в частности, лишаетвозможности характеризовать вычислительную сложность алгоритмакак полиномиальную, экспоненциальную и т. д.Указанное обстоятельство в значительной мере является следствием плохо выбранных параметров n, | f (x) | и | q(x) | размера входа.Если мы зафиксируем n и f (x), а затем будем слегка изменять значения коэффициентов полинома q(x) (тем самым два параметра размера остаются фиксированными, а третий изменяется очень мало),то при этом могут возникать уравнения вида (C.), имеющие натуральные решения m, и эти m для разных уравнений могут, как будет показано, отличаться друг от друга сколь угодно сильно.
Мы укажем натуральное n, неприводимый полином f (x) ∈ Q[x] степени n,См. []; в этой же работе получена оценка (C.) как следствие оценки (C.).См. [].Проблема орбитпоследовательность q1 (x), q2 (x), ... ∈ Q[x] полиномов степени меньшей, чем n, и вещественные A, B, A < B, такие, что A < | qk (x) | < B,k = 1, 2, ..., и при этом каждое из уравненийam = qk (a),f (a) = 0,(C.)имеет решение m = k. Возьмемa=p3 + 4 −1,5(C.)q6p8636тогда f (x) = x 2 − x + 1, n = 2 и | f (x) | = 1 ++1=. Пусть5255b1 , b2 , ... и c1 , c2 , ... — последовательности рациональных чисел таких,что ak = bk a + ck , и пусть qk (x) = bk x + ck ∈ Q[x] (таким образом, q(x)6равен остатку от деления x k на f (x) = x 2 − x + 1).
Очевидно, что5b1 = 1, c1 = 0.Используя утверждения , , сформулированные в конце предыдущего раздела этого приложения, индукцией по k легко доказывается,что6bk+1 = bk + ck , ck+1 = −bk5для k > 0. Последняя система двух рекуррентных уравнений решается легко, так как второе уравнение позволяет заменить в первом ckна −bk−1 и получить для bk линейное рекуррентное уравнение второго порядка с постоянными коэффициентами. В итоге имеем (см. приложение G)pp p 553 + 4 −1 k3 − 4 −1 kbk == sin(k θ )−−18554иck = −58ppp 3 − 4 −1 k −153 + 4 −1 k −1−1= − sin((k − 1)θ ),−554pгде θ ∈ R выбрано так, чтобы выполнялось a = eθ −1 .
ПолучаемpÆ5p5sin2 k θ + sin2 (k − 1)θ ≤2.| qk | = bk2 + c2k =44pДля функции h(x) = sin2 x + sin2 (x − θ ) положим µ = min (h(x)) ≥ 0.0≤ x <2π4Так как sin(θ ) = , то θ не является целым кратным π, поэтому µ > 0.5Таким образом,5454| qk | = h(k θ ) ≥ µ > 0.Приложение C55pПоложим A = µ, B =2. Для любой функции F(x1 , x2 , x3 ), непре44рывной на множествеpno86V = (x1 , x2 , x3 ): x1 = 2, x2 =, A < x3 < B ,5мы можем выбрать целое k, большее максимума функции F(x1 , x2 , x3 )на V, и это приведет к уравнению (C.) с решением m, большимF(n, | f (x) |, | q(x) |).Таким образом, нами доказана следующая теорема.Теорема C..
Пусть алгоритм распознавания существования и поиска решения m уравнения (C.) состоит в получении верхней границы M для m и в последующей проверке всех значений m = 1, 2, ..., M.Тогда сложность этого алгоритма по числу таких проверок не допускает оценки сверху вида F(n, | f (x) |, | q(x) |), где F — какая-либо непрерывная функция трех переменных.Отсутствие непрерывной функции, ограничивающей затраты, является, как уже упоминалось, следствием неудачно выбранных параметров размера входа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
