13. uii = 1, u21 = иррациональны, uu = U22 - 0.

14. После трехкратного применения алгоритма Евклида получим i/ после выполнения шага S4 получим

Затем

/-2 -5 О

18 38 \ -5 -5 О 100/

Результатом преобразования О, 91,92,93) = (1,*,0,2), (2,-4,*, 1), (3,0,0,*), (1,*,0,0) будет

-5 -8 -7 1-2 1 /

/-22 -2 -5 -5 9 -31

18 \ -5

Z = {Q О 1).

Таким образом, из = %/б, как уже известно из упр. 3.

15. Наибольшее достижимое q в (11) минус наименьшее достижимое плюс 1 равно ui + • • • + \ut\ - S, где (5 = 1, если < О для некоторых i и j. В остальных случаях 6 = 0. Например, если t = 5, ui > О, «2 > О, из > О, U4 = О и us < О, наибольшее достижимое значение q равно g = ui + U2 + из - 1, а наименьшее равно g = us + 1 = -lus] + 1.

[Заметим, что число гиперплоскостей остается прежним при изменении с. Следовательно, ответ будет таким же, если вместо Lo покрыть L. Однако приведенная формула не всегда точна для покрытия Lo, поскольку не во всех гиперплоскостях, пересекающих единичный гиперкуб, содержатся точки из Lq. В приведенном выше примере можно никогда не достичь значения q = ui -I- U2 -I- из - 1 в Lo, если ui -I- U2 -I- из > тп. Это значение достигается тогда и только тогда, когда существует решение тп - ui - U2 - из = xiui +x2u2 + x3u3 -I-X4u5, где (ж1,Ж2,жз,а;4) - неотрицательные целые числа. Возможно, верно, что данный предел всегда достижим, когда сумма ui -(-•-(- ut минимальна, но это не кажется очевидным.]

16. Достаточно найти все решения (15), имеющие минимум ui -(-•• -(- u(, и вычесть 1, если какое-нибудь из этих решений имеет компоненты с противоположным знаком.

Вместо положительно определенной квадратичной формы будем использовать функцию, в некотором смысле аналогичную ей, {f{xi,... ,xt) = \xiUi -f • • • -I- xtUt\), определяя У = yi -(-... -(- \yi\. Неравенство (21) можно заменить неравенством \xk\ < /(yi,... ,У() х (maxi<j<t \vkj\).

Таким образом может быть получен следующий работающий алгоритм. Заменить шаг S1 шагом S3: "Присвоить U 4- (тп), V •«- (1), г 1, s <- т, t <- 1". (Здесь U и V - матрицы размера 1x1. Следовательно, двумерный случай сводится к общему методу. Для t = 2 можно, конечно, использовать частную процедуру; см. работу, приведенную в ответе к упр. 5.) На шагах S4 и S7 присвоить s <- min(s, [4). На шаге S7 присвоить Zk «- [maxi<j<t \vkj\s/m\. На шаге S9 присвоить s <- min(s, У - S) и на шаге SlO выход, S = Nt. Иначе - оставьте алгоритм в том виде, в каком он сформулирован, так как он уже производит достаточно короткие векторы. [Math. Сотр. 29 (1975), 827-833.]

17. Когда fc > t на шаге S9 и У-У < s, взять в качестве выхода У и -У. Кроме того, если У - У < S, взять в качестве выхода предыдущие векторы для этого t. [При подготовке табл. 1 автор заметил, что существовал точно один вектор (и он же со знаком "минус") на выходе для i/t, кроме случаев, когда yi = О или yt = 0.]

18. (а) Пусть ж = т, у = (1 - т)/3, «о = у + xSij, uij = -у + Sij. Тогда Vj-Vk = i(m - 1) для j k,VkVk = (m -f i), Uj Uj = (m -f 2), Zk и УJm. (Этот пример удовлетворяет (28) с а = 1 и работает для всех тп = 1 (по модулю 3).)

(b) Необходимо поменять местами [/ и V на шаге S5. После замены присвоить также S <- min(s,[/i • Ui) для всех Ui- Например, когда т = 64, это преобразование с j = 1, примененное к матрице из (а), сводит

[Поскольку преобразование может привести к увеличению длины Vj, алгоритм, объединяющий оба преобразования, должен быть таким, чтобы не допускалось зацикливание. См. также упр. 23.]

19. Нет, так как произведение не единичных матриц со всеми неотрицательными элементами вне диагонали и со всеми диагональными элементами, равными единице, не может быть единичным.

[Однако зацикливание было бы возможным, если бы последующее преобразование с g = -1 осуществлялось тогда, когда -2Vi - Vj = Vj Vj. Правило округления должно быть несимметричным относительно знака, если допустимо несокращенное преобразование.]

20. Когда а mod 8 = 5, точки 2~{x,s{x),... для х в периоде - это те же самые точки, что и 2"(у,сг(у),... ,сг"(у)) для О < у < 2" плюс (Ао mod4)/2, где сг(у) = (ау -I- [a/4J) mod 2~. Поэтому в рассматриваемом случае следовало бы использовать алгоритм S с тп = 2*~.

Когда а mod 8 = 3, максимальное расстояние между параллельными гиперплоскостями, содержащими точки 2" (х, s(a;),..., s~(x)) по модулю 1, такое же, как и максимальное расстояние между параллельными гиперплоскостями, содержащими точки 2~{x,-s{x),..., {-l)~s~\x)), поскольку замена знака координат не изменяет расстояния. Последней будет точка 2~{у,а{у),... ,a{y)), где сг(у) = (-ау - Га/41) mod 2"" плюс постоянное отклонение. Снова применим алгоритм S с тп = 2"; замена а на тп - а не сказывается на результате.

21. Х4„+4 = Х4п (по модулю 4), поэтому сейчас удобно положить Vi = (4,4а, 4а)/тп, Уг = (0,1, 0), Уз = (О, 0,1) и определить соответствующую решетку Lq.

24. Пусть тп = р; можно произвести анализ, подобный приведенному в разделе. Например, когда t = 4, то Хп+з = ((а -I- b)Xn+i + аЬХп) modm, и необходимо так минимизировать Ui +ul + U3 + U4 ф О, чтобы ui + Ьиз + abu4 = U2 + аиз + (а -I- b)u4 = О (по модулю тп). Заменим шаги S1-S3 операцией присвоения

0\ /1 П\ /1

fm 0\ fl 0\ „ А 0\

U Tnj (о ij (о ij

и на выходе получим i/г = тп. Заменим шаг S4 шагом S4.

S4. [Продвижение t.] Если t = Т, алгоритм завершен. Иначе - присвоить t t + 1 и Л •(- R{°)modm. Присвоим Ut новой строке (-ri2, -ггг, 0,..., 0,1) из t элементов и присвоим иц <- 0 для 1 < г < t. Присвоим Vt новой строке (0,..., о, тп). Для I < i < t присвоим q •(- округление((ипГ12 -I-и;2Ггг)/пг), Vit <- Viiri2 +Vi2r22 -qm Я Ut Ut +qUi. Наконец, присвоить s «- min(s, Ut Ut), fc •(- t, j •(- 1.

[Подобное обобщение применяется ко всем последовательностям длиной р*" - 1, удовлетворяющим линейным рекуррентным соотношениям 3.2.2-(8). Дополнительные числовые

примеры приведены в работах А. Grube, Zeitschrift fiir angewandte Mati. und Mechanilc 53 (1973), T223-T225; , LEcuyer, Blouin, and Couture ACM Trans. Modeling and Сотр. Simul. 3 (1993), 87-98.]

25. Рассматриваемая сумма меньше либо равна удвоенной сумме Yi,o<k<m/2d() - 1 + /(m/d), где

/(тп) = - Е csc{nk/m)

1<к<т/2

= - / csc(7rx/m)dx--0( -) =-Intanf-x) +0{ - ]. mJi \mj 7г 42m / \т/

[Когда d = 1, справедливо равенство Eo<fc<m "С) = (/тг) 1пт--Ц-(2/7г) 1п(2е/7г)-1-0(1/т).]

26. Когда m = 1, использовать (52) нельзя, так как fc будет равняться нулю. Если gcd(g, т) = d (gcd - наибольший общий делитель), то доказательство остается прежним, только m заменяется на m/d. Предположим, что справедливо равенство m - pl... р/, gcd(a - 1, m) = р{... р/"" и d = pj... pr. Если т заменить на m/d, то s заменяется на

max(0,ei-/i-di) max(0,e,.-/r-<ir)

Pi • Рг

27. Удобно использовать следующие функции; р{х) = 1, если х = 0; р{х) = х, если О < X < т/2; р(х) = т - х, если т/2 < ж < т; усечение(ж) = [х/2], если О < ж < т/2; усечение(ж) = m - [(m - x)/2J, если m/2 < ж < m; L{x) = О, если ж = 0; L{x) = [lgx\ + 1, есля О < ж < т/2; L(ж) = -(Llg(m - ж)] + 1), если т/2 < ж < т, и 1{х) = max(l, 2""). Заметим, что l{L{x)) < р(ж) < 21{Ь{х)) и 2р(ж) < 1/г(ж) = msin(M/m) < л-р(ж) для О < ж < т.

Скажем, что вектор (ui,...,U() плохой, если он не равен нулю и удовлетворяет (15). Пусть pmin - минимальное значение p(ui).. .р(г*() по всем плохим (г*1,..., U(). Вектор (ui,...,Ut) относят к классу (L(ui),..., L(U()). Поэтому существует не более (2 Igm -(-1) классов и в классе (Li,..., Lt) содержится самое большее l{Li)... l{Lt) векторов. Чтобы получить требуемое утверждение, достаточно доказать, что плохие векторы в каждом фиксированном классе привносят самое большее 2/pmin в сумму Er{ui,..., щ); это позволяет получить желаемую грань, так как 1/pmin < тггтах-

Пусть р = [IgpminJ. р-кратный оператор усечения, применяемый к вектору, определяется следующей операцией, выполненной р раз: "Пусть j - такой минимальный индекс, что p{uj) > 1. Заменим Uj на trunc(uj), но ничего не будем делать, если р{щ) = 1 для всех /. (Эта операция, по существу, отбрасывает один двоичный разряд информации от (ui,..., Ut).) Если (ul,..., ut) и (u",..., и") - два вектора из одного и того же класса, имеющие одно и то же /i-кратное усечение, то мы говорим, что они подобны; в этом случае справедливо неравенство p{ui - и")... p{ut - ul) < 2* < pmin. Например, любые два вектора вида ((1ж2а;1)2, О, m - (1жз)2, (101ж5Ж4)2, (1101)2) подобны, когда m большое и р = Ъ; /х-кратный оператор усечения последовательно удаляет ж1, жг, жз, ж4, ж5. Так как разность двух плохих векторов удовлетворяет (15), невозможно, чтобы два неравных плохих вектора были подобными. Поэтому класс (Li,...,L() может содержать самое большее тах(1, Z(Li)... Z(L()/2) плохих векторов. Если в классе (Li,...,L() содержится точно один плохой вектор (ui,..., ut), то справедливы неравенства r(ui,... ,щ) < Гтах < 1/pmin; если в нем содержится < 1{Ь\)... l{Lt)/2 плохих векторов, то для каждого из них вьшолняется r(ui,...,U() < l/p{ui)...p{ut) < l/l{Li).. .l{Lt) и справедливо неравенство

1/2 < 2/pmin.