С1. Показательная функция и логарифмическая оценка

Х п 4—1 к х

Г п п гп

V xdx + 1 ^^ Vfc^ V xdx +V n,

1 fc=1 1

т. е.

₂ (VH) 3 + ₁ 2^ ^ ₂ (VH) 3 + v;

fc=1

и, как следствие,

2^=²₃(^)³ + 0 (УН).

fc=1

Аналогично выводится, что при любом вещественном а ^ 0 и п —»оо

выполняется X! к^а

к=0

аф-1?)

_а+1

а+1.

(Справедлива ли эта формула при всех

220 Приложение В

Функция - не возрастает при х=г 1. Имеем х

1 fc=i i

это дает нам
	In П S= ^ i S= In П + 1, fc = l
и, как следствие,
	Л=ln n + 0(l). fc=i

Приложение C Проблема орбит

В этом разделе приложения рассказывается об одной вычислитель­ной задаче и об эффективном решении ее некоторого частного слу­чая; почти все факты приводятся без доказательств. В разделе C 2 мы рассмотрим оставшийся случай с большими подробностями.

Речь идет об одном из вариантов известной «проблемы орбит». Даны две квадратные матрицы A и B одинакового порядка с элемен­тами из поля Q. Существуют ли натуральные m такие, что A^m = B? Если да, то надо указать все такие m. Рассмотрение собственных зна­чений матриц A и B приводит к вопросу о распознавании существо­вания и поиске натуральных m таких, что

a^m = b (C.1)

для данных алгебраических чисел a и b.

Напомним, что число a ∈С называется алгебраическим, если су­ществует полином над полем Q, для которого a является корнем. В качестве такого полинома удобно рассматривать унитарный ^г по­лином, т. е. полином с единичным старшим коэффициентом. Можно показать, что для всякого алгебраического числа существует един­ственный унитарный неприводимый над Q полином, для которого a является корнем. Алгебраическое число a ∈С называется целым ал­гебраическим, если соответствующий неприводимый унитарный по­лином является полиномом над Z, т.е. имеет целые коэффициенты². Нетрудно, например, убедиться, что число (1 + л/5) / 2 — целое алгеб­раическое, а число (3 + 4- ^Т) / 5 —нецелое алгебраическое.

¹ Используются также термины приведенный, нормированный.

² Для избежания терминологической путаницы между целыми алгебраическими чис­
лами и обычными целыми, т.е. элементами Ъ, последние в теории алгебраических
чисел часто называют целыми рациональными числами.

Приложение C

Если \а\ Ф 1, то с исследованием и решением уравнения (C.1) се­рьезных трудностей не возникает, так как модуль значения показа­тельной функции а^т монотонно возрастает или монотонно убывает, и можно получить логарифмическое ограничение на т. Задача ста­новится интересной при \а\ = 1 и при дополнительном условии, что а не является корнем из 1. (Если а есть корень из единицы, то задача тривиальна.)

Как это следует из элементарной теории алгебраических чисел, вопрос можно переформулировать так: дан неприводимый над Q по­лином /(х), deg/(x) = n, и некоторый полином q (x) над Q степени deg q (x) <n; существуют ли такие натуральные т, что

a^m = q{a) (C.2)

при любых а е С, для которых /(а) = 0, и если да, то как найти та­кие т? Мы сосредоточимся на последнем вопросе, опуская мелкие подробности перехода к нему от проблемы орбит.

Особенность постановки вопроса об уравнении (C.2) состоит в том, что речь идет не об одном фиксированном корне полинома /(х), но обо всех его корнях. Легко показать, что если равенство (C.2) вер­но для одного какого-то корня а₀ полинома /(х), то оно верно для всех корней этого полинома. В самом деле, если для некоторого фик­сированного т полиномы x^m - q (x) и /(х) имеют общий корень а₀, то эти полиномы имеют нетривиальный общий делитель. Наиболь­ший общий делитель этих полиномов может быть найден алгоритмом Евклида и, следовательно, должен иметь рациональные коэффициен­ты. Из этого и из неприводимости /(х) над Q следует, что наиболь­ший общий делитель равен /(х). Отсюда получаем, что х^т - q (x) де­лится на /(х). Это означает, что каждый корень /(х) является также корнем x^m - q (x).

Таким образом, задача о всей совокупности корней эквивалент­на задаче об одном фиксированном корне, и задача об одном фик­сированном корне эквивалентна задаче о любом другом корне. Это обстоятельство позволяет справиться со случаем целого алгебраиче­ского а. К решению подводит серия результатов о корнях унитарных полиномов над Z, начавшаяся с работ Кронекера и завершившаяся в 60—70-е годы XX века исследованиями А. Шинцеля, Г. Цассенхауза, П.Бланксби и Х.Монтгомери¹. Выяснено, что если унитарный поли­ном над Z степени п таков, что его корни не являются корнями из

^:Cм. [58], [45]. Результаты Кронекера, Шинцеля и Цассенхауза изложены в [29, разд. 20.2].

Проблема орбит

единицы, то у него найдется по меньшей мере один корень a, для которого |a| > 1. Бланксби и Монтгомери показали, что по меньшей мере для одного корня выполняется неравенство

Из этого позднее было выведено, что если корни неприводимого уни­тарного полинома f (x) степени n c целочисленными коэффициента­ми не являются корнями из единицы, то для любого натурального решения m уравнения (C.2) выполнено неравенство

m^n + 60n² 1п(6 n) (1п(n + 1) + ln| q (x) |), (C.4)

где | q (x)| обозначает длину вектора коэффициентов полинома q (x): если q(x) = c_kx^k +... + c₁x + c₀, то

| q (x)|=₁/ c 2 +... + c 2 + c 2.

Решения уравнения (C.2) для различных корней a полинома f (x) совпадают. Доказанное может быть сформулировано следующим об­разом.

Предложение С.1. Пусть f (x) — неприводимый над Q полином степени n, корни которого не являются корнями из единицы. Пусть q (x) — некоторый полином над Q, степень которого меньше n. То­гда для любого корня a полинома f (x) существует не более одного натурального решения уравнения (C.2), при этом решения m уравне­ния (C.2) для различных корней a полинома f (x) совпадают, и имеет место оценка (C.4).

Несложно показать, что верны следующие утверждения:

1. Пусть h (x)eQ и r (x) — остаток от деления h (x) на f (x). Пусть a еС, f (a) = 0. Тогда h{a) = r{a).

2. Пусть q ₁(x), q ₂(x), q ₃(x),... суть остатки от деления x, x ², x ³,... на f{x). Тогда

• при k> l полином q_k (x) равен остатку от деления xq_k __x(x) на

f (x);

• равенство (C.2) имеет место, если и только если q (x) = q_m (x).

Из этих утверждений следует, что после того, как установлена гра­ница M для возможного значения m, распознавание существования и поиск натурального решения уравнения (C.2) можно выполнить, затратив O{nM) арифметических операций над рациональными чис­лами.

Приложение C

С2. Неудачно выбранный размер входа

Обратимся к уравнению (C.2), предполагая, что среди коэффициентов унитарного неприводимого над Q полинома /(х) имеется по крайней мере один нецелый рациональный; без специальных оговорок счи­таем, что корни /(х) не являются корнями из единицы. Возникает вопрос: можно ли и для этого случая получить подобную (C.4) верх­нюю оценку величины т? На протяжении ряда лет считалось, что ответ положительный¹ и что существует полином трех переменных Р (х ₁, х₂,х ₃ ) такой, что даже при наличии среди коэффициентов /(х) нецелых рациональных чисел имеет место оценка

m<P (n,log₂|/|,log₂| q |), (C.5)

но затем выяснилось, что это неверно². Проблема заслуживает де­тального рассмотрения, поскольку ряд ее моментов является прин­ципиальным. Вывод о существовании полинома Р(х₁, х₂,х₃) был сде­лан на основании утверждения о том, что если среди коэффициентов /(х) есть нецелые числа, то имеет место неравенство

m sS(n -1)log₂|/|. (C.6)

Неравенство (C.6) опровергается несложно (сразу заметно, что пра­вая часть этого неравенства не зависит от вида полинома q (x), что подозрительно). Мы, тем не менее, сосредоточим усилия на дру­гом— покажем, что верхняя оценка (C.5) не может иметь места не только при полиномиальной, но и, например, при показательной

X*3

функции того или иного вида (скажем, вида 2^{х 2}) и вообще при любой непрерывной функции Р(х₁,х₂,х₃). Это, в частности, лишает возможности характеризовать вычислительную сложность алгоритма как полиномиальную, экспоненциальную и т.д.

Указанное обстоятельство в значительной мере является следстви­ем плохо выбранных параметров п, |/(х)| и | q (x)| размера входа. Если мы зафиксируем п и /(х), а затем будем слегка изменять зна­чения коэффициентов полинома q (x) (тем самым два параметра раз­мера остаются фиксированными, а третий изменяется очень мало), то при этом могут возникать уравнения вида (C.2), имеющие нату­ральные решения т, и эти т для разных уравнений могут, как бу­дет показано, отличаться друг от друга сколь угодно сильно. Мы ука­жем натуральное п, неприводимый полином /(x)∈(Q>[ x ] степени п,

См. [51]; в этой же работе получена оценка (C.4) как следствие оценки (C.З). См. [41].

Проблема орбит

последовательность q₁(x),q₂(x),... е Q[ x ] полиномов степени мень­шей, чем п, и вещественные А, В, А < В, такие, что A<|q_k(x)|<B, к = 1, 2,..., и при этом каждое из уравнений

a^m = q _fc(a), /(a) = О, (C.7)

имеет решение т = к. Возьмем

а = --------------, (C.8)

тогда /(х) = х² - |х + 1, п = 2 и |/(х) | = ^ 1 + Щ+1 = ^. Пусть

|х + 1, п = 2 и |/(x)| = yi + || + l = ^

Ь_ъ b₂,... и с_ъ с₂,... —последовательности рациональных чисел таких, что а^к = Ъ_ка + с_к, и пусть q _fc(x) = b_kx + c_k gQ[x] (таким образом, q (x)

равен остатку от деления х^к на /(х) = х² --х + 1). Очевидно, что b ₁ = l, _Cl = 0.

Используя утверждения 1, 2, сформулированные в конце предыду­щего раздела этого приложения, индукцией по к легко доказывается, что

Ъ_{к +1} = 1 ъ_к + с_к, с_{к +1} = - Ъ_к

для к > 0. Последняя система двух рекуррентных уравнений решает­ся легко, так как второе уравнение позволяет заменить в первом с_к на -Ъ_к-_г и получить для Ъ_к линейное рекуррентное уравнение второ­го порядка с постоянными коэффициентами. В итоге имеем (см. при­ложение G)

с_к = - -у- 111--------------- г ----- J -(---------- г ----- J J _________________________

8-1-------------- 5------------- ----------- 5--------------- =-4s^[nttk-V^e^

где (9 еЖ выбрано так, чтобы выполнялось а = е^е^ ¹. Получаем | q _fc| = ^T^=|Vsin²fc0 + sin²(fc-l)0<|V2.

Для функции Их) = \/sin² x + sin²(x -0) положим ц = min (h (x)) > 0.

0<х < 2я

4 Так как sin(0) = =, то в не является целым кратным п, поэтому д > 0.

Таким образом,

| q _fc| = | h (fc0)>|/i > O.

Приложение C

Положим A = ^м, B = ^л/2. Для любой функции F {x_ъ x₂, x_ъ), непре­рывной на множестве

V = |(x _l5 x ₂, x ₃): x_г = 2, x ₂ = ^, A < x ₃ < B },

мы можем выбрать целое k, большее максимума функции F (x _ls x ₂, x ₃) на V, и это приведет к уравнению (C.7) с решением m, большим F{n, | f (x)|, | q (x)|).

Таким образом, нами доказана следующая теорема.

Теорема С.1. Пусть алгоритм распознавания существования и по­иска решения m уравнения (C.2) состоит в получении верхней грани­цы M для m и в последующей проверке всех значений m = 1,2,...,M. Тогда сложность этого алгоритма по числу таких проверок не допус­кает оценки сверху вида F{n, | f (x) |, | q (x) |), где F — какая-либо непре­рывная функция трех переменных.

Отсутствие непрерывной функции, ограничивающей затраты, яв­ляется, как уже упоминалось, следствием неудачно выбранных па­раметров размера входа. Можно показать¹, что если среди коэффи­циентов унитарного неприводимого полинома f (x) имеется хотя бы один, не являющийся целым рациональным, и если C, D eZ таковы, что Ca является целым алгебраическим для любого корня a полинома f (x) и Dq{x) eZ[ x ], то для решения m уравнения (C.2) выполнено

m ^(n -l)log₂ C + log₂ D. (C.9)

Границы (C.4) и (C.9) приводят к алгоритму решения проблемы орбит.

В качестве C может быть взято наименьшее общее кратное знаме­нателей коэффициентов полинома f (x), в качестве D — наименьшее общее кратное знаменателей коэффициентов полинома q (x).

Неверно, что C всегда можно взять меньшим², чем | f (x) |. В этом

можно убедиться, вернувшись к f (x) = x ² - | x + 1.

См. уже упоминавшуюся работу [41].

В [51] авторы исходили из предположения, что всегда можно взять C< | f (x)|.

Приложение D

Дата добавления: 2014-01-11