close

Вход

Забыли?

вход по аккаунту

?

Аддитивные задачи в натуральных числах с двоичным разложениями специального вида.

код для вставкиСкачать
ЧЕБЫШЕВСКИЙ СБОРНИК
Посвящается 65-ой годовщине со дня рождения
профессора Сергея Михайловича Воронина
Том 12 Выпуск 1 (2011)
УДК 511
АДДИТИВНЫЕ ЗАДАЧИ В НАТУРАЛЬНЫХ
ЧИСЛАХ С ДВОИЧНЫМИ
РАЗЛОЖЕНИЯМИ СПЕЦИАЛЬНОГО ВИДА
К. М. Эминян (г. Москва)
E-mail: eminyan@mail.ru
Посвящаю памяти незабвенного
Сергея Михайловича Воронина
1
Введение
Пусть n = e0 + e1 2 + . . . + ek 2k представление натурального числа n в виде
двоичной системе счисление (ej = 0, 1). Пусть N0 множество натуральных
чисел, чьи двоичные разложения имеют четное число 1, N1 = N \ N0 . Пусть
1, если n ? N0 ;
?(n) =
?1, если n ? N1 .
В 1968 году А.О. Гельфонд [1] доказал, что числа классов N0 и N1 регулярно распределены в арифметических прогрессиях. Более того, А.О. Гельфонд
получил для любого вещественного ? оценку
X
?(n)e2?i?n X ? ,
n6X
ln 3
где ? = ln
= 0, 79 . . .
4
Эту оценку мы в дальнейшем будем называть оценкой Гельфонда.
АДДИТИВНЫЕ ЗАДАЧИ В НАТУРАЛЬНЫХ ЧИСЛАХ С . . .
179
В 1991 году автор решил задачу, поставленную перед ним С.М. Ворониным,
и получил [2] асимптотическую формулу для суммы
X
? (n).
n6x, n?N0
В 1996 году автор доказал следующую теорему. Пусть Fj,k (X) число решений уравнений n ? m = 1 в натуральных числах n 6 X , n ? Nj , m ? Nk ,
j, k = 0, 1.
Тогда справедливы асимптотические формулы
F0,0 (X) =
X
+ O(log X),
6
F1,1 (X) =
X
+ O(log X),
6
X
X
+ O(log X), F1,0 (X) =
+ O(log X).
3
3
Отсюда следует, что главные члены определяются значениями j и k .
В настоящей статье рассматриваются две задачи, в которых указанный эффект отсутствует.
Сформулируем основные теоремы статьи.
F0,1 (X) =
1. Пусть h целое число такое, что 0 6 h 6 2. Пусть
Ij,k (X, h) число решений уравнения n ? 3m = h в натуральных числах n 6 X ,
n ? Nj , m ? Nk , где j , k произвольные целые числа из отрезка [0, 1]. Тогда
справедлива асимптотическая формула
Теорема
Ij,k (X, h) =
X
+ O(X ? ),
4
? = 0, 79 . . .
2. Пусть l целое число такое, что 0 6 l 6 4. Пусть Jj,k (X) число решений уравнения n?5m = l в натуральных числах n 6 X , n ? Nj , m ?
Nk , где j , k произвольные целые числа из отрезка [0, 1]. Тогда справедлива
асимптотическая формула
Теорема
Jj,k (X) =
X
+ O(X ? ),
4
? = 0, 79 . . .
Определим суммы
S3 (X, h) =
X
n6X
?(n)?(3n + h),
S5 (X, l) =
X
?(n)?(5n + l),
n6X
где h и l неотрицательные целые числа.
Доказательства теорем 1 и 2 основаны соответственно на леммах 1 и 2 (см.
ниже), а также на оценке Гельфонда.
180
2
К. М. ЭМИНЯН
Леммы
Лемма
оценка
1. Пусть h целое число такое, что 0 6 h 6 2. Тогда справедлива
?
S3 (X, h) = O( X).
Доказательство. Группируя слагаемые, отвечающие четным и нечетным
n соответственно и пользуясь очевидными равенствами ?(2n) = ?(n), ?(2n+1) =
??(n), приходим к следующим соотношениям
X
X
, 0 + S3
, 1 + O(1),
(1)
S3 (X, 0) = S3
2
2
X
X
S3 (X, 1) = ?S3
, 0 ? S3
, 2 + O(1),
(2)
2
2
X
X
, 1 + S3
, 2 + O(1),
(3)
S3 (X, 2) = S3
2
2
Рассмотрим линейную комбинацию
?0 S3 (X, 0) + ?0 S3 (X, 1) + ?0 S3 (X, 2),
где ?0 , ?0 , ?0 константы, которые будут выбраны позже.
Пользуясь (1) (3), имеем
?0 S3 (X, 0) + ?0 S3 (X, 1) + ?0 S3 (X, 2) =
X
X
X
X
= ?0 S3
, 0 + S3
,1
+ ?0 ?S3
, 0 ? S3
,2
+
2
2
2
2
X
X
+ ?0 S3
, 1 + S3
,2
+ O(|?0 |) + O(|?0 |) + O(|?0 |) =
2
2
X
X
X
= ?1 S3
, 0 + ?1 S3
, 1 + ?1 S3
,2 +
2
2
2
+ O(|?0 |) + O(|?0 |) + O(|?0 |),
где
?
? ?1 = ?0 ? ?0 ,
?1 = ?0 + ?0 ,
?
?1 = ?0 ? ?0 .
Повторяя это рассуждение, приходим к равенству
X
X
?0 S3 (X, 0) + ?0 S3 (X, 1) + ?0 S3 (X, 2) = ?j S3
, 0 + ?j S3
,1 +
2j
2j
X
?j S3
, 2 + O(|?0 | + . . . + |?j?1 |)+
2j
+ O(|?0 | + . . . + |?j?1 |) + O(|?0 | + . . . + |?j?1 |),
АДДИТИВНЫЕ ЗАДАЧИ В НАТУРАЛЬНЫХ ЧИСЛАХ С . . .
в котором последовательности ?j , ?j , ?j связаны соотношениями
?
? ?j+1 = ?j ? ?j ,
?j+1 = ?j + ?j ,
?
?j+1 = ?j ? ?j ,
181
(4)
для любого j , 0 6 j 6 log2 X ? 10.
Запишем равенства (4) в матричной форме
?
? ?
??
?
?
?
?j+1
1 ?1 0
?j
?j
? ?j+1 ? = ? 1 0 1 ? ? ?j ? = A ? ?j ? .
?j+1
0 ?1 1
?j
?j
Тогда
?
?
?
?
?j
?0
? ?j ? = Aj ? ?0 ? ,
?j
?0
где 1 6 j 6 log2 X ? 10.
Вычислим Aj . Для этого найдем собственные значения и собственные векторы матрицы A и получим равенство A = CBC ?1 , где
?
?
?
?
1
?1
1?
1 0 0
?
C = ? 0 1?i2 7 1+i2 7 ? , B = ? 0 ?2 0 ? ,
0 0 ?3
?1
1
1
?
?
где ?2 = 1+i2 7 , ?3 = 1?i2 7
Из этого равенства следует, что
?
?
?
?
?j
?0
? ?j ? = CB j C ?1 ? ?0 ? .
?j
?0
Пусть
?
? ? ?
?
? ? ?
?
? ? ?
?0
1
?0
0
?0
0
? ?0 ? = ? 0 ? , или ? ?0 ? = ? 1 ? , или ? ?0 ? = ? 0 ? .
?0
0
?0
0
?0
1
?
Поскольку |?2 | = |?3 | = 2, имеем неравенства
|?j | = O(2j/2 ), |?j | = O(2j/2 ), |?j | = O(2j/2 ),
где постоянные в знаках O абсолютные.
Выберем J наименьшим натуральным числом таким, что
2J <
1
X.
10
182
К. М. ЭМИНЯН
Пусть, например,
?
? ? ?
?0
1
? ?0 ? = ? 0 ? ;
?0
0
тогда
S3 (X, 0) = ?J S3
? J
X
X
X
2 ).
,
0
+
?
S
,
1
+
?
S
,
2
+
O(
J
3
J
3
2J
2J
2J
Теперь, оценивая суммы
X
X
X
S3
, 0 , S3
, 1 , S3
,2
2J
2J
2J
тривиально и пользуясь тем, что
?
?
|?J | + |?J | + |?J | = O( 2 J ) = O( X),
получим оценку
?
S3 (X, 0) = O( X).
Аналогично получаем, что
?
?
S3 (X, 1) = O( X), S3 (X, 2) = O( X).
Лемма
оценка
2. Пусть l целое число такое, что 0 6 l 6 4. Тогда справедлива
S5 (X, l) = O(X µ ),
где µ = 0, 605 . . .
Доказательство.
Рассмотрим линейную комбинацию
?0 S3 (X, 0) + ?0 S3 (X, 1) + ?0 S3 (X, 2) + ?0 S3 (X, 3) + ?0 S3 (X, 4),
где ?0 , ?0 , ?0 , ?0 , ?0 постоянные, которые будут выбраны позже.
Подобно тому, как это сделано в доказательстве леммы 1, получаем, что
?0 S3 (X, 0) + ?0 S3 (X, 1) + ?0 S3 (X, 2) + ?0 S3 (X, 3)+
X
X
X
, 0 + ?j S3
, 1 + ?j S3
,2 +
+ ?0 S3 (X, 4) = ?j S3
2j
2j
2j
X
X
+ ?j S3
, 3 + ?j S3
,4 +
2j
2j
!
j?1
X
+O
(|?k | + |?k | + |?k | + |?k | + |?k |) , (5)
k=0
АДДИТИВНЫЕ ЗАДАЧИ В НАТУРАЛЬНЫХ ЧИСЛАХ С . . .
183
где 1 6 j 6 log2 X ? 10; последовательности ?j , ?j , ?j , ?j , ?j связаны соотношениями:
?
?j+1 = ?j ? ?j ,
?
?
?
?
? ?j+1 = ?j ? ?j ,
?j+1 = ?j + ?j ,
?
?
?j+1 = ?j ? ?j ,
?
?
?
?j+1 = ?j ? ?j ,
1 6 j 6 log2 X ? 10.
Запишем их в матричной форме:
?
? ?
?j+1
1 ?1
? ?j+1 ? ? 0 0
?
? ?
? ?j+1 ? = ? 1 0
?
? ?
? ?j+1 ? ? 0 ?1
?j+1
0 0
??
0 0 0
?j
?
?
1 ?1 0 ? ? ?j
?
0 0 1 ?
? ? ?j
?
1 0 0 ? ?j
0 ?1 1
?j
?
?
?
?.
?
?
Компьютерные вычисления показывают, что собственные значения матрицы
?
?
1 ?1 0 0 0
? 0 0 1 ?1 0 ?
?
?
?
1
0
0
0
1
A=?
?
?
? 0 ?1 1 0 0 ?
0 0 0 ?1 1
имеют вид:
?
(27 + 3 78)2/3 + 3
?
?1 = ?2 = 1, ?3 = ?
,
3(27 + 3 78)1/3
?
? ?
?
? ?
?(27 + 3 3 26)2/3 ? 3 + 3(27 + 3 3 26)2/3 i ? 3 3 i
? ?
,
?4 = ?
6(27 + 3 3 26)1/3
? ?
?
? ?
?
(27 + 3 3 26)2/3 + 3 + 3(27 + 3 3 26)2/3 i ? 3 3 i
? ?
?5 =
.
6(27 + 3 3 26)1/3
Заметим, что с точностью до пропорциональности существует лишь один
собственный вектор, отвечающий собственным значениям ?1 = ?2 = 1.
Воспользуемся известной теоремой о том, что существует базис, в котором
A имеет нормальную жорданову форму (см., например, [4]).
В нашем случае существует матрица C : A = CBC ?1 , где
?
?
1 1 0 0 0
? 0 1 0 0 0 ?
?
?
?.
0
0
?
0
0
B=?
3
?
?
? 0 0 0 ?4 0 ?
0 0 0 0 ?5
184
К. М. ЭМИНЯН
Поэтому
?
?
?
?
?
?
?j
?j
?j
?j
?j
?
?
?
?
?
?
?=C?
?
?
?
?
1
0
0
0
0
1 0 0 0
1 0 0 0
0 ?3 0 0
0 0 ?4 0
0 0 0 ?5
?j
?
?
?
? ?1 ?
? C ?
?
?
?
?
?0
?0
?0
?0
?0
?
?
?
?.
?
?
Заметим, что матрицы C , C ?1 не зависят от j . Поэтому, если в столбце
?
?
?0
? ?0 ?
?
?
? ?0 ?
?
?
? ?0 ?
?0
положить однин из элементов равные 1, а остальные нулю, то в столбце
?
?
?0
? ?0 ?
?
?
j ?1 ?
CB C ? ?0 ?
?
? ?0 ?
?0
все элементы оцениваются как O(j + |?3 |j + |?4 |j + |?5 |j ).
Так как |?3 | = 1.521379707 . . ., |?4 | = |?5 | < |?3 | то |?j |, |?j |, |?j |, |?j |,
|?j |=O(|?3 |j ).
Полагая в равенстве (??) j = J = [log2 X] ? 10, получаем, что для любого
0 6 k 6 4 справедливы неравенства
|S5 (X, l)| = O (X µ ) ,
где µ =
3
ln |?3 |
ln 2
= 0.605 . . .
Доказательства теорем 1 и 2
Докажем теорему 1. Для любого целого h, 0 6 h 6 2, и для любых j, k = 0, 1
имеем
X 1 + (?1)j ?(n) 1 + (?1)k ?(3n + h) Ij,k (X, h) =
=
2
2
n6X
=
X (?1)j X
(?1)k X
(?1)j+k
+
?(n) +
?(3n + h) +
S3 (X, h) + O(1) =
4
4 n6X
4 n6X
4
АДДИТИВНЫЕ ЗАДАЧИ В НАТУРАЛЬНЫХ ЧИСЛАХ С . . .
3
X (?1)j X
(?1)k X ? 2?ich
=
+
?(n) +
e 3
4
4 n6X
4 c=1
X
?(n)e
2?icn
3
185
+
n63X+h
(?1)j+k
S3 (X, h) + O(1).
4
Теперь теорема 1 сразу следует из очевидного равенства
X
?(n) = O(1),
+
n6X
неравенства Гельфонда и леммы 1. Любопытно отметить, что, поскольку оценка
Гельфонда при ? = 1/3 неулучшаема, оценка остаточного члена в теореме 1
неулучшаема.
Доказательство теоремы 2 по существу совпадает с доказательством теоремы 1. Единственное различие использование леммы 2 вместо леммы 1.
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
[1] Gelfond A.O., ѕSur les nombres qui ont des proprietes additives et multiplicatives donneesї. Acta Arith., 13 (1968), 259265.
[2] Эминян К.М., ѕО проблеме делителей Дирихле в некоторых последовательностях натуральных чиселї, Изв. АН СССР. Сер. матем., 55:3
(1991), 680686.
[3] Эминян К.М., ѕОб одной бинарной задачеї, Мат. заметки., 60:4 (1996), 634
637.
[4] Гельфанд И.М. Лекции по линейной алгебре. М.: Наука, 1971.
Финансовый Университет при Правительстве РФ.
Московский государственный технический университет им. Н.Э. Баумана.
Поступило 15.08.2011
Документ
Категория
Без категории
Просмотров
3
Размер файла
236 Кб
Теги
вида, специальное, двоичных, аддитивных, разложениями, натуральних, задачи, числа
1/--страниц
Пожаловаться на содержимое документа