close

Вход

Забыли?

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

?

О распределении элементов полугрупп натуральных чисел.

код для вставкиСкачать
ЧЕБЫШЕВСКИЙ СБОРНИК
Том 13 Выпуск 3 (2012)
УДК 511.29
О РАСПРЕДЕЛЕНИИ ЭЛЕМЕНТОВ
ПОЛУГРУПП НАТУРАЛЬНЫХ ЧИСЕЛ
1
Ю. Н. Штейников (г. Москва)
Аннотация
В работе рассматриваются полугруппы натуральных чисел, порядок
которых на отрезке
[1, q]
есть
q? .
В этой работе получены нетривиальные
верхние оценки числа таких элементов на множестве
сравнению с любой степенью
[1, t],
где
t
мало по
q.
џ1. Предварительные сведения
Пусть A ? N полугруппа, то есть если a1 , a2 ? A, то a1 a2 ? A.
В частности, можно взять множество A = {n ? N : n ? G (mod m)}, где
m ? N, а G мультипликативная подгруппа группы Z?m .
Например, если положить m = p2 , где p простое число и
G = {g ? Z?p2 : g p?1 = 1},
то мы получаем
A = Ap = {n ? N : np?1 ? 1 (mod p2 )}.
Нас будет интересовать случай, когда для некоторых действительных q ;
? < 1 выполнено неравенство:
|{n ? A; n ? q}| < q ? .
(1)
Например, пусть A = Ap . Так как группа Z?p2 циклическая, то отсюда
следует, что |G| = p ? 1. Значит для этого примера |{n ? A : n ? p2 }| = p ? 1.
Здесь, как несложно видеть, можно положить q = p2 и ? = 21 .
Пусть для x > 0 определим:
f (x) = |A ? [1, x]|.
1 Работа
поддержана грантом РФФИ ќ11-01-00329, а также грантом ведущей научной шко-
лы НШ-6003.2012.1
92
Ю. Н. ШТЕЙНИКОВ
Мы хотим оценить сверху f (x) как функцию от q и от u.
В работе [3] получены оценки на количество чисел не превосходящих n, которые принадлежат подгруппе порядка t группы Z?p . Эти оценки содержательны,
когда t мало по сравнению с p. Из нашей работы вытекают оценки в случае,
когда t растет как степень p, а n мало.
Покажем, что верно следующее утверждение.
Пусть полугруппа A удовлетворяет условию (1) и
x = (log q) . Тогда
1) если log log x = o(log log q), то
Теорема
1.
u
f (x)
? exp{?(C + o(1))u(1 ? ?)2 log(u(1 ? ?)2 )}
x
где C некоторая абсолютная константа;
log x
2) если ? = log
и log x = o(log q), то
log log q
f (x) ? x1?max{L? ,C? }+o(1) , q ? ?,
где
(
L? = ?
1??+
?
1??
(1 ? ?)2 + ?(1 ? ?)
)2
и C? =
{
(1??)2 ?
,
4(1??)
2 ? ? ? ?1 ,
если ? ? 3??2 ,
если ? > 3??2 .
џ2. Вспомогательные утверждения
Предположим, что задано целое y . Каждое натуральное n представим в виде
n = n1 n2 , так что если простое p делит n1 , то p ? y , а если делит n2 , то p > y .
Пусть также даны x, z . Определим множество:
N (x, y, z) = {n ? x : n1 > z}.
Мы хотим оценить сверху количество элементов множества N (x, y, z).
На довольно большой области изменения x, y, z была получена асимптотика
N (x, y, z) в работе [4]. Нам нужен будет более грубый результат, но при еще
слабых ограничениях на параметры x, y, z. Мы будем следовать технике, разработанной в [4].
Нам потребуются оценки для множеств чисел, у которых все простые делители малы либо наоборот, большие. Для натурального n пусть P + (n) и P ? (n)
соответственно наибольший и наименьший простой делитель числа n, P + (1) =
1, P ? (1) = ?. Для x > y > 2 полагаем:
?(x, y) = |{n 6 x : P + (n) 6 y}|, ?(x, y) = |{n 6 x : P ? (n) > y}|.
О РАСПРЕДЕЛЕНИИ ЭЛЕМЕНТОВ ПОЛУГРУПП НАТУРАЛЬНЫХ . . . 93
Также нужны следующие оценки на ?(x, y) ([1]) и также оценки на ?(x, y)
(следствие из теоремы 3, 3 часть, 6 глава [5] ).
x
Пусть x ? y ? 2, v = log
Тогда для любого ?
log y
1??
множестве v ? y имеет место неравенство:
Теорема A [1].
> 0
на
?(x, y) = xv ?v(1+o(1)) ,
если v ? ?.
Теорема B [5].
Пусть x ? y ? 2. Тогда
?(x, y) ?
xw(v)
,
log y
x
где v = log
, w() функция Бухштаба.
log y
Пусть ? > 0 и ?0 < ? фиксированы. Также пусть имеются
положительные ?, ?, ? , причем 0 < ? < 1, ? < ?0, ? < 1, ? < ?(1 ? ?) и также
x = (log q)u , x ? exp{(log q)? }, y = (log q)? , z = x? . Тогда
1.
Лемма
|N (x, y, z)| ? xexp{?
?u
?u
(1 + o(1)) log( )}, u ? ?.
?
?
Доказательство.
|N (x, y, z)| =
?
?(
z<n1 ?x,P + (n1 )?y
x
, y) =
n1
?
?(
z<n1 ? x
,P + (n1 )?y
y
x
x
, y) + (?(x, y) ? ?( , y)).
n1
y
Последнее слагаемое несложно оценить:
x
u
u
?(x, y) ? ?( , y) ? ?(x, y) = xexp{? (1 + o(1)) log }.
y
?
?
Распишем сумму, используя теорему B:
?
?(
z<n1 ? x
,P + (n1 )?y
y
x
x
, y) ?
n1
log y
?
w( ?u ?
log n1
)
log y
n1
z<n1 ? x
,P + (n1 )?y
y
Применим
к последней сумме преобразование Абеля, обозначив через S(t) =
?
1
. Получаем:
n1
z<n1 ?t,P + (n1 )?y
?
z<n1 ? x
,P + (n1 )?y
y
w( ?u ?
log n1
)
log y
n1
x
= S( )w(1) +
y
?
z
x
y
w? ( ?u ?
log t
)
log y
t log y
S(t)dt ?
94
Ю. Н. ШТЕЙНИКОВ
x
? S( ) +
y
?
u
?1
?
?u
?
|w? (
u
? s)|S(y s )ds.
?
Оценим S(y s ), для этого вновь воспользуемся преобразованием Абеля:
?
s
S(y ) =
z<n1 ?y s ,P + (n1 )?y
1
?(y s , y) ? ?(z, y)
=
+ log y
n1
ys
?(y s , y)
?
+ log y
ys
?
s
?u
?
?
s
?u
?
?(y ? , y) ? ?(z, y)
d?
y?
?(y ? , y)
d?.
y?
Теперь воспользуемся теоремой A, условия которой выполнены, получаем,
? s
s
(y ) ? exp{?s(1 + o(1)) log s} + (log y)
exp{?? (1 + o(1)) log ? }d? ?
?u
?
?u
?u
(1 + o(1)) log
}, u ? ?.
?
?
Теперь подставляя полученные оценки и используя неравенства на w(v) (см
теорема 4, 3 часть, 6 глава [5] )
? (log y) exp{?
|w? (v)| ? exp{?v(1 + o(1)) log v},
мы получаем требуемый результат.
Теперь докажем еще одну лемму.
2 Количество делителей числа n < Q, не превосходящих z , не
превосходит ?(z, (1 + o(1)) log Q), Q ? ?.
Лемма
.
Доказательство.
Пусть pt11 ...ptss разложение на простые множители, при-
чем p1 < p2 < . . . < ps .
Рассмотрим отображение делителей числа n
1
s
? : pl11 ...plss ? pl(1)
...pl(s)
,
где p(i) i-ое простое число в натуральном ряду, то есть p(1) = 2, p(2) = 3, p(3) =
5, ...
Это отображение инъективно. Также, ?(d) ? d ? z.
Известно, что если n := pt11 ...ptss < Q то p(s) ? (1 + o(1)) log Q. Отсюда количество чисел в образе отображения ? , которые не превосходят z не больше
?(z, (1 + o(1)) log Q). А это и есть исходное утверждение. Лемма доказана.
џ3. Доказательство теоремы
О РАСПРЕДЕЛЕНИИ ЭЛЕМЕНТОВ ПОЛУГРУПП НАТУРАЛЬНЫХ . . . 95
Пусть x = (log q)u . Определим ? из равенства :
|A ? [1, x]| = ?x.
Введем параметры ?, ? ; ? < 1 и соответственно y = (log q)? , z = x? . Для
каждого натурального n, как и раньше, n = n1 n2 , так что если простое p делит
n1 , то p ? y , а если p делит n2 , то p > y .
Напомним, что N (x, y, z) = {n ? x : n1 > z} . Теперь рассмотрим множество A? = A ? [1, x]\N (x, y, z). Положим также |A? | = ?? x. Использую лемму 1,
несложно заметить, что :
? ? ?? + exp{?
?u
?u
(1 + o(1)) log( )},
?
?
здесь o(1) по u ? ?.
log q
Рассмотрим B = {m1 . . . mr }, где r = [ log
] и m1 , . . . , mr ? A? . Оценим сверx
ху размер этого множества, используя, что произведение чисел из A является
числом из A : |B| ? |{m1 . . . mr }| ? |A ? [1, q]| ? q ? . Теперь оценим снизу |B|.
Пусть каждое mi = n1,i n2,i , так что если простое p делит n1,i , то p ? y , а если p делит n2,i , то p > y . Определим из равенства N1 , N2 : m = m1 . . . mr =
n1,1 . . . n1,r n2,1 . . . n2,r = N1 N2 , где N1 = n1,1 . . . n1,r и N2 = n2,1 . . . n2,r .
Возьмем конкретный представитель, например элемент m ? A? . . . A? (r сомножителей) и оценим сверху число представлений его в виде произведения
A? . . . A? .
Пусть m = N1 N2 , оценим количество представлений для N2 в виде произведения r чисел n2,1 . . . n2,r , N2 = n2,1 . . . n2,r = p1 . . . ps ,где все pi > y и являются
log q
простыми числами. Видим, что s ? s0 = [ log
].
y
Каждый делитель pi , i = 1, . . . , s может входить в разложение некоторого
n2,j , j = 1, . . . , r. Значит количество представлений числа N2 не превосходит
r s ? r s0 .
Теперь оценим количество представлений для N1 , N1 = n1,1 . . . n1,r . Каждое
n1,i не превосходит z и является y? гладким числом. Значит для каждого n1,i
имеется не более |?(z, y)| возможностей. Заметим также, что каждое n1,i ? z является делителем N1 . Значит, по лемме 2 каждое n1,i может принимать не более
?(z, (1 + o(1)) log q) значений. Отсюда получаем, что количество представлений
для N1 не превосходит каждого из 2-ух чисел |?(z, y)|r , |?(z, (1 + o(1)) log q)|r .
Число же представлений для числа m не превосходит произведения числа представлений для N1 и N2 .
Отсюда получается и нижняя оценка для B :
?
?
?x
( |?(z,(1+o(1))
)r
log q)|
?x
)r
( |?(z,y)|
, |B| ?
r s0
r s0
Значит должно выполняться 2 соотношения:
|B| ?
.
?
?x
( |?(z,y)|
)r
r s0
? q?
(2)
96
Ю. Н. ШТЕЙНИКОВ
?
?x
( |?(z,(1+o(1))
)r
log q)|
? q?
(3)
r s0
для любых выбранных параметров (?, ?). Из этого неравенства можно получить оценку для ?? , а значит и для ?. Теперь найдем соответствующие значения
параметров (?, ?), которые дают наилучшую (наименьшую) оценку для ?.
Пусть log log x = o(log log p). В этом случае, в (2)
Первый случай.
?
( ?zx )r
rs0
используя, что ?(z, y) ? z мы получаем
? q ? . Распишем левую часть и
?
напишем условие на ? , предварительно сделав преобразования.
?
( ?zx )r
rs0
log q
?
(?? x1?? ) log x
log q
log q log y
( log
)
x
?1
log q
log q
= exp{( log
? 1)(log ?? + (1 ? ?) log x) ? ? log
(log log q ?
x
log q
?
?
log log x)} ? exp{log q( log
+1???
log x
1
?
+
log log x
? log log q
?
(1??) log x
)}.
log q
Отсюда и из (2) получаем соотношение :
log ??
1
log log x
(1 ? ?) log x
+1??? +
?
? ?,
log x
? ? log log q
log q
Выразим теперь отсюда ?? :
log ?? ? log x(
1
log log x
(1 ? ?) log x
?1+?+??
+
).
?
? log log q
log q
То есть,
log log x
?? ? x ? ?1+?+?? ? log log q +
1
(1??) log x
log q
(4)
А тогда получаем оценку на ?:
log log x
? ? x ? ?1+?+?? ? log log q +
1
(1??) log x
log q
+ exp{?
?u
?u
(1 + o(1)) log( )}.
?
?
Так как x ? exp{(log q)?0 }, ?0 < 1, то первое слагаемое в неравенстве для ?
есть:
1
1
(x) ? ?1+?+?
(x) ? ?1+?+?
,
=
u
log x
(log x) ? (1+o(1))
(log x) ? log log q (1+o(1))
при q ? ?. Значит,
?u
(x) ? ?1+?+?
?u
??
+ exp{? (1 + ou (1)) log( )}.
u
(1+o
(1))
q
?
?
(log x) ?
1
Здесь в первом слагаемом o(1) это по q , а во втором слагаемом o(1) по u.
2
Берем следующие значения параметров : ? = 1??
, ? = 1??
? ?, где ? > 0 2
произвольное фиксированное. Тогда получаем :
? ? C(x?? ) + exp{?Cu(1 ? ?)2 log(Cu(1 ? ?)2 )},
О РАСПРЕДЕЛЕНИИ ЭЛЕМЕНТОВ ПОЛУГРУПП НАТУРАЛЬНЫХ . . . 97
где C - некоторая абсолютная константа. Первое слагаемое меньше второго для
достаточно больших q.
Поэтому, для первого случая мы получили:
f (x)
? exp{?(C + oq (1))u(1 ? ?)2 log(u(1 ? ?)2 )},
x
для некоторой абсолютной константы C и при q ? ?.
log x
Рассмотрим случай, когда ? = log
и log x = o(log q).
log log q
Пусть ? ? (1 + ?)? для некоторого ? > 0. Вспоминая, что z = x? =
exp{?(log q)? }, y = (log q)? согласно теореме [A], мы получаем:
?
|?(z, y)| = z 1? ? +o(1) , |?(z, (1 + o(1)) log q)| = z 1??+o(1) .
Второй случай.
Исходя из этого, заменяя ? на ?(1 ? ?? + o(1)) в (4) первый раз и ? на
?(1 ? ? + o(1)) , заключаем 2 неравенства :
?
log log x
?? ? x ? ?1+?(1? ? +o(1))+?? ? log log q +o(1)
1
log log x
?? ? x ? ?1+?(1??+o(1))+?? ? log log q +o(1)
1
Окончательно получаем,
??
?
1
f (x)
?u
?u
? x ? ?1+?? ? +?? ? +o(1) + exp{? (1 + o(1)) log( )}.
x
?
?
?
1
f (x)
?u
?u
? x ? ?1+????+?? ? +o(1) + exp{? (1 + o(1)) log( )}.
x
?
?
?
(log q)
, поэтому можно
Во втором слагаемом o(1) по u. В нашем случае u = log
log q
считать, что o(1) зависит от q .
?
Последнее слагаемое это exp{? ?? ?(log q)? (1 + o(1))} = x? ? ?(1+o(1)) .
Итак, одновременно выполняются
??
?
?
1
f (x)
? x ? ?1+?? ? +?? ? +o(1) + x? ? ?(1+o(1)) .
x
?
?
1
f (x)
? x ? ?1+????+?? ? +o(1) + x? ? ?(1+o(1)) .
x
Будем искать параметры (?, ?).
Рассмотрим случай, когда ? ? 1. Тогда будем минимизировать наибольшее
+ ? ? ?? ? 1 + ?. Если ? ? 1. то берем такие параметры
из значений : ? ?? ?, 1??
?
:
?
?
1??+ (1??)2 +?(1??)
?
?=
;
1??
1??
? ? = ??1 = ?
2
(1??) +?(1??)+1??
98
Ю. Н. ШТЕЙНИКОВ
Подставляя эти параметры получаем: f (x) ? x1?C? +o(1) , где
(
C? = ?
1??+
?
1??
)2
(1 ? ?)2 + ?(1 ? ?)
Пусть теперь ? < ? ? 1. Тогда будем минимизировать наибольшее из значе2
ний: ? ?? ? и 1??
+ ? ? ?? ? ? 1 + ?. В случае если ? ? 3??
, берем такие параметры:
?
? = 1??
, ? = (1 + ?) 2(1??)
, где ? > 0? произвольное фиксированное. В случае
2
1??
2
если ? > 3?? , берем такие параметры: ? = 2 ? ? ? ?1 , ? = ?(1 + ?), где также
? > 0? произвольное фиксированное.
Подставляя такие параметры получаем f (x) ? x1?L? +?+o(1) , где ? > 0 2?
2
произвольное фиксированное и L? = (1??)
, если ? ? 3??
, L? = 2 ? ? ? ?1 , если
4(1??)
2
? > 3??
. В силу произвольного ? отсюда следует исходное неравенство:
f (x) ? x1?L? +o(1) , q ? ?.
Отсюда заключаем неравенство:
f (x) ? x1?max{L? ,C? }+o(1) , q ? ?.
Теорема доказана.
џ4. Комментарии
1. Покажем на примере полугруппы гладких чисел, какие есть оценки снизу
на функцию f ((log q)u ).
Возьмем любое число 0 < ? < 1 и положим Aq ? полугруппа y - гладких
чисел, где
y = (log q)? ,
1
где ? = 1??
+ ?, где ? малое число.
Пользуясь теоремой [A] о количестве гладких чисел при при q ? q(?, ?)
получаем,
?
|Aq [1, q]| < q ? .
Тогда выполнено неравенство (1).
?
Возьмем теперь какое-нибудь u, |Aq [1, (log q)u ]| = (log q)u exp{?u(1 ? ? +
?? )(1 + o(1)) log u(1 ? ?)}, по u ? ?, ?? > 0 - некоторое малое число.
Здесь, как видно, линейный порядок по (1 ? ?). Теорема дает правильный
характер зависимости по u. Однако в нижней оценке зависимость от (1 ? ?)
линейная, а в теореме квадратичная.
2. Если x намного больше q , то оценить сверху f (x) не удается. Это становится ясно если рассмотреть A = {n : n > q}. Если x растет как степень q c
показателем, меньшим 1, то иногда также нельзя дать нетривиальную оценку
О РАСПРЕДЕЛЕНИИ ЭЛЕМЕНТОВ ПОЛУГРУПП НАТУРАЛЬНЫХ . . . 99
?
на |A [1, x]|. Для этого возьмем достаточно большое q и рассмотрим полугруп0.1
0.1
пу Aq , которая состоит
? из любых произведений чисел взятых из (q 0.1 , 1.5q 0.1 ].
Заметим, если
? n ? A ?[1, q], то0.1nr = n10.9. . . nr , r ? 9 и n1 , . . . , nr ? (q , 1.5q ].
Значит |Aq [1, q]| ?
(0.5q ) ? q .
1?r?9
Теперь возьмем x = 1.5q 0.1 . Тогда
?
x
|Aq [1, x]| ? .
4
Таким образом, хороших оценок на функцию f (x) при x порядка степени q для
произвольных полугрупп получить не удается.
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
[1] Hildebrand A., Tenenbaum G., Integers without large prime factors, J Theorie
des Nombres de Bordeaux, 5 (1993) no. 2 411-484.
[2] Прахар К., Распределение простых чисел, Издательство Мир, 1984.
[3] Bourgain J., Konyagin S., Shparlinski I., Distribution of elements of cosets of
small subgroups and applications, International Math Research Notices, 19682009, 2012:9 (2012).
[4] Shparlinsky I., Integers with a large smooth divisor, Electronic journal of
combinatorial number theory 7, 2007.
[5] Tenenbaum G., Introduction to analytic and probabilistic number theory,
Cambridge Universit Press, Cambridge, UK, 1995.
Механико-математический факультет, Московский Государственный Университет им. М.В. Ломоносова, Москва, Россия
Поступило 29.10.2012
Документ
Категория
Без категории
Просмотров
3
Размер файла
195 Кб
Теги
элементов, полугруппы, натуральних, чисел, распределение
1/--страниц
Пожаловаться на содержимое документа