(0,1-а;

(1,1)

1 1 а

• у = -х-\----

"222

• у = х-а

(0,0)

(1,0)

Рис. А-3. Область перестановок для генератора с потенциалом 2; а = (а - 1)с/т.

исключением следующих:

т = 2q, q - нечетное, е > 3, а = 2" (по модулю 2), а = 1 (по модулю q), vl = vl = 2; т = 3g, 3J-g, e>2, a = l± 3" (no модулю 3), a = 1 (no модулю g), 14 = 2; ТП = 9, a = 4 или 7, vl = vl = 5.

4. (a) Единственным выбором для {X\,x2) является (j/l«22 - y2U2i,-yiui2 + y2Uii), и

это равно = (yiU22 + y2a«22, -У1И12 -y2aui2) = (0, 0) (no модулю 1), т. e. Xl и Ж2 являются целыми числами, (b) Когда (xi,X2) # (О, 0), получим (xiUu +Ж2И21) + (xiui2 + x2u22) = 2i("ii+"i2) + xiivii + U22) + 2xiX2(uii«2i + И12И22), a согласно предположению

это > (xf + xi - xiX2)(Uii + U?2) > "U + "12-

{Заметим, что полученный результат сильнее леммы А, которая утверждает только, что Xl < (ufi + и?2)("21 + U22)/n» И Х2 < (ufi + "DV"*) где последний может быть > 1. Идея, по существу, является Гауссовским методом приведения двоичной квадратичной формы (см. Disquisitiones Aritbmeticse (Leipzig, 1801), §171).]

5. Условия (30) остаются неизменными; следовательно, h не может быть нулем на щаге S2, когда а и m - взаимно простые числа. Так как h всегда уменьшается на этом шаге, S2 в конце концов завершится с и + к > s. Заметим, что рр < О на протяжении всего вычисления.

6. Если + > s > {и - h) + {v - p) в предыдущем ответе, получим (и - р) > v. Следовательно, {u - hY < если q = aj, то, поскольку h - ajh + u, мы должны получить aj+r= 1. Из замечания к упр. 3.3.3-16 следует, что il = mino<j<t(Tn +p] i).

Получим mo=Tnjpj + mj+ipj-i=ajmjPj-i+mjpj-2+mj+ipj-i<{aj + l + l/aj)mjPj-i< (i4 + 1 + l/A)mjpj-i, a TTij + p i > 2mjpj-i, откуда и следует ответ.

7. Докажем, используя условие (19), что Uj [4=0 для всех к ф j тогда и только тогда, когда Vj • Vit = О для всех к ф j. Предположим, что Uj - Uk =0 для всех fc ф j, и пусть Uj = ai Vl + • • • + QtVt. Тогда Uj Uk = ак для всех fc. Следовательно, Uj = ajVj и Vj - Vk = aJ{Uj Vk) - Q для всех к ф j. Аналогично доказывается обратное утверждение.

8. Ясно, что vt+i < щ (факт безоговорочно использован в алгоритме S, так как s не изменяется при возрастании t). Для t = 2 это эквивалентно (тп/хг/тг) > (тп/хз/7г), т. е. рз < s/rnjix. Эта граница доведена до для заданных параметров, но для больщих т и фиксированного р2 граница (40) лучще.

9. Пусть /(yi,... ,yt) = в; gcd(yi,... ,у() = 1 (gcd - наибольщий общий делитель) - целочисленная матрица с определителем, равным 1, первая строка которой - (yi,..., yt). (Последнее доказать по индукции по наименьщей ненулевой величине, занесенной в строку.) Если X = {xi,... ,xt) - вектор-строка, получим XW = X тогда и только тогда, когда X = XW~, а если - целочисленная матрица с определителем, равным 1, форма д, определенная WU, удовлетворяет g{xi,...,Xt) = f{xi,...,xt). Кроме того, g{\,Q,...,Q) = e.

Без уменьшения общности предположим, что f = д. Если S - любая ортогональная матрица, матрица US определяет ту же форму, что и U, поэтому {XUS){XUS) = {XU){XU). Выберем 5 так, чтобы ее первый столбец был кратным U, а все другие столбцы - любые подходящие векторы. Тогда получим

US =

fai О ... 0

«2

; и

\at J

для некоторых а\, а2, at и некоторой матрицы U размера (t - 1) х (t - 1).

Следовательно, f{x\,...,xt) = {aix\ -I- • • • -I- atXt) Л- h{x2, ,xt). Из этого следует, что Ql = [фактически Oj = {Ui Uj)l\fQ для 1 < j < t] и что h. -- положительно определенная квадратичная форма, порожденная С/, где det С/ = (det[/)/\/. Индукцией по t можно показать, что существуют целые числа (жг,... ,xt), для которых выполняется

h{x2, ...,xt)< (1)*- det c/2/(*-i)/ei/(*-i)

и для этих целых чиселж1 можно выбрать таким образом, что \xi+{a2X2-i------atxt)/ai\< ,

а это эквивалентно (aixi +----1- atxt) < \в. Значит,

в < /(XI,. ..,xt)<\e+ ()<-> [det [/V(-i)/eV(-i)

и желаемое неравенство получается немедленно.

[Замечание. Для t = 2 это наилучший из возможных результатов. В общем случае из теоремы Эрмита следует, что pt < 7r(4/3)*~/(V2) Из фундаментальной теоремы Минковского ("Каждое t-мерное выпуклое множество, симметричное относительно начала координат с объемом > 2, содержит не равную нулю точку с целыми координатами") следует, что pt < 2. Это более точное неравенство, чем то, которое следует из теоремы Эрмита для t > 9. Известен еще более точный результат (см. (41)).]

10. Так как yi и уг - взаимно простые числа, можно найти решение уравнения «12/2 - И2У1 = т. Кроме того, {щ + qyi)y2 - (u2 + gy2)yi = т для всех q, поэтому, выбирая подходящее целое q, можно убедиться, что 2uiyi + игуг! < Уг + Уг- Сейчас У2(и1 + au2) = У2Щ - yiU2 s О (по модулю тп), уг и тп должны быть взаимно простыми числами. Следовательно, ui + au2 = 0. Окончательно, пусть uiyi + «гуг! = am, Ui + U2 = рт, У1 + Уг = ут, справедливо О < а < 57 и остается показать, что а < /3 и /З7 > 1. Тождество (uiy2 - игуО + («iyi + игуг) = ("i + «2)(yi + у) влечет равенство 1 + = /З7. Если а > то справедливо 2а7 > 1 + а, т. е. 7 - л/у - 1 < а < 7. Но 7 < 7 - 1 влечет неравенство 7 > , что приводит к противоречию.

11. Так как а нечетно, yi +у2 должна быть четной. Чтобы избежать решения, где и yi, и уг четные, положим yi = Х1+Х2, уг = Ж1-Ж2 и решим уравнение Xi+Xj = тп/\/3-е при xi ± Х2 и четном Хх. Соответствующий множитель а будет решением уравнения (жг - Xi)a = Х2 + х\ (по модулю 2"). Не составляет труда доказать, что а = 1 (по модулю 2**) тогда и только тогда, когда х\ = Q (по модулю 2*"), поэтому получим наилучший потенциал, когда ximod4 = 2. Проблема сводится к нахождению относительно простого решения х\+х% = N, где N - большое число вида 4fc + 1. Разлагая N на комплексные целые числа (гауссовские целые числа), мы получим, что решение существует тогда и только тогда, когда каждый простой множитель N (среди обычных целых чисел) имеет вид 4fc + 1.

В соответствии с известной теоремой Ферма каждое простое р вида 4fc + 1 можно с точностью до знаков и и v записать единственным способом: р = u+v = {u+iv){u-iv), где V четное. Числа unv эффективно могут быть вычислены, если решить уравнение ж = -1 (по модулю р) и затем вычислить и + iv - gcd(ж + г, р) с помощью алгоритма Евклида по комплексным целым числам (гауссовским целым числам). [Можно взять ж = nS~* modp для почти половины всех целых п. Это применение алгоритма Евклида, по существу, такое же, как и нахождение наименьшей не равной нулю величины и + и, такой, что и±жг) = О (по модулю р). Значения unv также появляются, когда алгоритм Евклида для целых чисел применяется обычным образом к р и ж; см. работу Ж. А. Серре и К. Эрмита (J. А. Serret and С. Hermite, J. de Math. Pures et AppJ. 5 (1848), 12-15).] Если разложение на простые множители N имеет видр.. .р = (ui+JVi) (ui-ivi)... {ur+iVrY{ur-iVrY, то получим 2" различных решений ж? +Ж2 = N, х\ ± жг, Ж1 четное, полагая ж2 + гж1 = {ui+iviY {u2±iV2Y • • {ur+.iVrY Подобным методом можно получить все такие решения.

Замечание. Аналогичная процедура может использоваться, когда тп = 10, но для этого потребуется в пять раз больше работы, так как необходимо хранить информацию до нахождения решения с Ж1 = О (по модулю 10). Например, когда т = 10°, получим [m/x/aj = 5773502691 и 5773502689 = 53 • 108934013 = (7 + 2г)(7 - 2г)(2203 + 10202г) х (2203 - 10202г). Из решений ж2 + i\xr \ = (7 + 2г)(2203 + 10202г) и (7 + 2г)(2203 - 10202г) первое дает ж1 = 67008 (не хорошее) и второе - ж1 = 75820, ж2 = 4983 (это подходит). Строка 9 из табл. 1 была получена, когда мы положили Ж1 = 75820, жг = -4983.

Строка 14 таблицы была получена следующим образом. [2/\/3J = 2479700524; спустимся вниз kN = 2479700521, равному 37-797-84089, и получим четыре решения: N = 4364 + 49605 = 26364 + 42245 = 38640 + 31411 = 11960 + 48339. Соответствующими множителями будут 2974037721, 2254986297, 4246248609 и 956772177. Проверим также Л - 4, но это число не подходит, поскольку оно не делится на 3. С другой стороны, простое число N - 8 = 45088 + 21137 приводит к получению множителя 3825140801. Аналогично получим дополнительные множители для Л - 20, Л - 44, iV - 48 и т. д. Множитель строки 14 - наилучший из первых шестнадцати множителей, найденных с помощью данной процедуры; это один из четырех множителей для N - 68.

12. Uj -и/ = Uj Uj+2 qi{Ui Uj) + Eij Efcj QiMUi Uk). Взята вторая частная производная по qk от левой части (26). Если достигается минимум, то частная производная должна обращаться в нуль.