Арифметические задачи комбинаторики тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РГВ од

РОССИЙСКАЯ АКАДЕМИЯ НАУК МАТЕМАТИЧЕСКИЙ ИНСТИТУТ им. ВА. СТЕКЛОВА

На правах рукописи

УДК 511

ПАВЛОВ Александр Иванович

арифметические задачи комбинаторики 01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

МОСКВА 1994

Работа выполнена в Отделе теории чисел Математического института им. В.А. Стеклова РАН.

Официальные оппоненты:

доктор физико-математических наук, профессор ЗУБКОВ А.М. доктор физико-математических наук, профессор НЕЧАЕВ В .И. доктор физико-математических наук, профессор ТИМОФЕЕВ Н.М.

Ведущая организация - механико-математический факультет МГУ им. М.В. Ломоносова.

Защита диссертации состоится -И- 1994 г.

в часов на заседании специализированного совета

Д 02.38.02 по защите диссертаций на соискание ученой степени доктора наук при Математическом институте им. В.А. Стеклова РАН по адресу:

117333 Москва, ул. Вавилова 42.

С диссертацией можно ознакомиться в научной библиотеке Математического института.

Автореферат разослан

1994 г.

Ученый секретарь спецсовета,

доктор ф.-м. н. МинеевМ.П.

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность- темы. Серьезная "арифметика" для комбинаторики, по-видимому, началась в 1918 году с публикации эпохальной работы Г.Харди и С.Раианудзана £1"]. В этой работе исследуется асимптотика при У\оо числа р(п) разбиений числа . на натуральные .части Х^ , Ц—1,2,,.. , т.е! р(н) - число решений в натуральных числах уравнения ^ . Если в наборе '(ХцХц... ) имеется у5 чисел, равных 1 & Б 6 ^

указанное уравнение можно записать так X Б У. = У\ . , где V

* »■

целое неотрицательное число. Используя равенство °° и 00 К — <

I р^г. - п а-2 ) |2.|<1,

и учитывая вклад в асимптотику Р(У>) только окрестности точки-2г ^ , Харди и Раиануджан получили равенство

где Х = ~ » из которого, в

частности(следует равенство

Работа знаменита теп, что в ней впервые был применен круговой метод, открытый (изобретенный)автораии этой работы. В свос очередь круговой метод опирается на метод производящих функций, восходящий, как известно, к Г.Лейбницу и П.Лапласу. Этот метод наряду, с другими аналитическими методами, по-видииоыу, является основный

в комбинаторике.

Основным объектом комбинаторики является симметрическая грул- . па степени 1х , т.е. мнодество всех подстановок или перестановок К. различимых символов. Значение этой группы для комбинаторики "подчеркивает высказывание Г.Вейля ([2]): "может оыть простейшей единицей в комоинаторике является группа И.! подстановок Уь предметов. Эта группа имеет различное строение для каздого числа h... Вопрос заключается в том, имеется ли, однако, некоторое

' асимптотическое единоооразие, преооладащее для больших или »

для#некоторого определенного класса больших W. . Математика все еще не дает ответа на такие вопросы".

?Тем. не.менее- в работах [з]-[б] подтверждается "асимптотическое единообразие" в структуре группы $ при и->°о . Именно »тому, в -частности, посвящена настоящая диссертационная работа.

Цель работы. I. Наяти асимптотику числа подстановок с заданным множеством длин циклов. 2. Маити аоишзтотику числа решений классов уравнений в подстановках.

Общая методика исследования.- При решении задачи об асимптотике числа подстановок с заданным множество* длин циклов разработан метод, подобный круговому методу Харди-Диттлвуда-Раыанудхана в классической проблеме о разбиении чисел.

При исследовании задачи об асимптотике числа решений уравнений в подстановках наряду о методом производящих функции используется другие аналитические методы (усиленный вариант метода Г.Дарбу, катод перевала и другие).

Научная новизна. Основные результаты диссертации валяются новыми."

Практическая ценность.. Работа носит теоретический' характер. Её результаты могут быть использованы в теории чисел, аналитической комбинаторике, вероятностной комбинаторике, комбинаторной тео-

рии групп.

Апдробапия. Результаты работы докладывались на следующих семинарах и конференциях:

1. первая всесоюзная конференция "Вероятностное методы в дискретной математика!' (г.Петрозаводск, 1983г.);

2. всесоюзная конференция "Теория чисел и её приложения" (г.Тбилиси, 1986 г.);

3. вторая всесоюзная конференция "Вероятностные методы'в дискретной математике" (г.Петрозаводск, 1988 г.);

международная конференция "Современные проблемы теории чисел" (Г.Тула, 1993 г.);

5. семинар кафедры теории чисел в МГУ им М.В.Ломоносова (1986г.)

6. семинау профессора А.А.Карацубы по аналитической теории-чисал в МГУ им. ¿1. В. Ломоносова (1983-1993гг.).

Публикации. Основные результаты диссертации опубликованы вГ^-[б]работах (I из них в соавторства), список которых приведен л конце автореферата.

Структура и объеу-.работ.ч. Диссертация состоит из введения, двух глав и списка литературы. Объем работы - 136 страниц машинописного текста, список литературы содержит 39 названий.

СОДЕРЖАНИЕ РАБОТЫ

Во введении к диссертации излагается история тематики диссертации, приводятся формулировки основных результатов и кратко описываются методы, использованные при их выводе.

В первой главе диссертации рассматриваются подстановки конечной степени с фиксированный множеством длин циклов.

й прикладной математике часто удобно иметь .дело с множеством подстановок с известной арифметикой длин циклов. 3 связи с этим

- б -

возникает задача: найти асимптотику пои К—> 00 дроби

1 (А)1 _ ф ^ Где • _ фиксированное множество кагу-

и! к •

ральных чисел, выделенное из множества всех натуральных чисел условиями арифметического характера,. $ (А) - множество всех подстано-

1-1 А

аок степени К. , длины всех циклов которых принадлежат У\. . В общем виде задача об асимптотике дроби , по-ввдимому,

впервые была поставлена Е.А..Бендерои (£7}) в 1974- году. Заметим, что подстановки конечной степени южно рассматривать как специальные разбиения конечных множеств с полеченными элементами.

Теоремы 1-4 устанавливают связь асимптотики дроби (А) при^—> ©о с плотностью у последовательности А- •

Теорема I утверждает," что для любой последовательности выполняется .неравенство

л ¿л

Отсюда следует, что если

' л^Мел ^

и ^ - ПЛОТНОСТЬ ТО П • Можно'

показать, что ¿00 принадлежит ^ классу ^ медленно меняющихся функций, т.е. для любой постоянной С. > О выполняется равенство-

к

В тейреие 2 в' частности доказано, что если множества .А, и А..

• - — 1, ' ** *

не пересекаются, ч Ь —■>• оо , где

л)=- • I независящие от К. числа ^ и принадле-

жат интервалу (о, 1) и , X . тоСц (А^Л^К^^М,

.где Э^Г^Л^^Л^МЧ

са= Г(ц)ПХ)/ г (г) >ш ,^гаииа-функция-

Теорема 3 утверядает следующее. Если множества .Л, и А, не

V 4 X *

пересекаются, (Хи (Л,.Й }, Иув(<>, 1)

и на зависит от К , {_ б ^ и плотность равна нулю, то

=. -е/}>|> | 2. ) , 1-0 £ .В связи с теоремой 3 важно отметить, что асимптотика (X ь ^ А-а) Щ?11 00 может не существовать- в класоическом смысле. Это подтверждает следующее утверздение (теорема 5, работы [8"]): пусть последовательность А = { удовлетворяет условиям:

тогда если К. » постоянная »то ^н (А)> О

и при всех 1 и 171-* со получим [Л] ~ ч <Х(А] =

- ^ ; если И = А ^— » постоянная £ > О • 10 ЯР" ^ —> 00

получим. (А) = о^-рр).

Отметим, что доказательство теоремы 3 основано на лемце 2, которая восходит к известным работам Г.Фрейда по тауберозым теоремам с остатком. . . .

у <

• Теорема в частности^отвеЧает 'на вопрос: если ¿/н)

И-^Уоо , где (о, 4.) и не зависит от И. , /_£ ЬС , го что могно сказать о плотности множества А ? В теореме 4 доказано, что тогда логарифмическая плотность последовательности А равна

Г •т-6-

^ — 2 Т--1'' IV! У- > ^ X Л Л € А

Прежде чем говорить о теоремах 5-7, заметим следующее. Известно,

что для любого множества .Л- натуральных чисел производящая

функция (2.) последовательности СХк(Л)имааг ВИД А

л ь=0 \АеЛ. '

где ,|2.|<^ . Следовательно' '

г .

где Г - произвольный замкнутый контур, локаций внутри круга |г{<1 и содержащий внутри точку ¿ = 0 • Поэтому если функция на окружности = имеет конечное число особенностей,

Л

каждая из.которых является алгебраической точкой ветвления, то делая в плоскости 2. надлежащие разрезы и деформируя контур в равенстве (I) так, чтобы он проходил по берегам этих разрезов, можно получить весьма точнуи асимптотическую формулу для )

•при И —00•

В'теореме 5 показано, что если .Л- являются объединением конечного числа непересекающихся арифметических прогрессий

. «да

и Е - некоторое конечное множество корней из единицы, то суцбст-. вуат постоянные

такие, что

где-числа «^(¿.Л определяйте«? равенством П Л.--)

у - плотность Д • * •

В теореме б рассматривается случай А.-^ ■

. г«в - произвольный набор целвс

чисел с условиями: > ч , == $ . ( ^.ч^, )-1 при I , с 1 I

и . При этих условиях доказывается равенство, аналогич-

ное равенству (2).

Точность в теоремах 5 и б стала возможной благбдаря равенству

У 1

сх>Ц Ц(1 -2}_Г= ЬЛ-^+С^.))' и Х - плотность ■

множества ./V •

Завершается первая глава теорешй 7. В этой теореме речь.идет о классе ыноаеств Д. , для которых соответствующая про изводящая функция кимеет окружность | х| = 1 границей аналитичности. Поэтому для исследования асимптотики используется круговой

метод. Учитывая влияние окрестности только точки 2 = 1 , .удается получить асимптотику дляОС^(Л) со степенным пониканием в остатке. Пусть ^ - множество функции ^ , удовлетворяющих условияи;

1. определена на множестве и/ всех натуральных чисел; при люо'ых: УУ1и Илг таких, что (УУ11>1 . выполнено равенство ^"ч)-» -КзЛ-1;

2. \ принимает только значения , О и ;

3. при некотором целом «унхция X принимает только значения О и 1 . ,1 ^

Пусть ~ множество тех Ж £ 1 , для которых

%(**)= 1 • в теореме 7 утверждается, что при фиксированных > 2 » 6 и Ь со выполняется равеистю

™ £ , > »в

зависит от ^ . Доказывается, что плотность множества Л. равна ^ . Причем осли » •

- 10 -

В связи о теорешй 7 рассмотрим два примера. Пусть

функция Шбиуса. Яогда мнохество Л- совпадает с множеством всех -ч::сел. При атом число называется X -числом, если для любого простого р выполняется условие р ^ ^ . Пусть

Л^^ ~ Функция Лиуваяяя. Напомним, что где Т - число простых делителей числа М , считая с кратностью (воли УУ1= • ... • , то т= -+- оСг ). Соответ-

ствующее множество А в этом случае будет состоять из чисел }п. удовлетворяющих условию: если ^» 10 числа

[.Т^! являются четными (здесь [ х] -наибольшее

целое чксао, нз превосходящее X. ).

Бо второй главе диссертации исследуется асимптотика чиола решений .уравнений в подстановках*

1С

Первые шсть теорем этой главы посвящены уравнению К = ОС в 5и > гДв С*. - заданная подстановка из , целое К.

П Л

В теореме 8 установлен критерий разрешимости уравнения 7\ -<Х

в 5М Щ терминах'цикловой структуры подстановки Ос . При атом

набор*, неотрицательных целых чисел называется

.цикловой структурой подстановки £Х6 , еолй для любого $

■ • 1. <• Б Л » & " часяо циклов длины 5 подстановки £Х .

5 ' .к. ^

Теорема 8 утверкдаег, что уравнение X — сх разрешимо я рп

тогда и только тогда, когда дня любого <Л]к и любого 5 ,

Эё К. "» из Л , рледует где с( = П Р » Р ~

простоа число. С помощью этого критерия г теореме 9 доказано, что вояк - ынохаотво тех подстановок СХ£"5К , дяя которые

разрешимо в уравнение х%гОС , то орк фиксирован вон )С > 2. и -ц—выполняема равенотво

• ь^+обГ*))

» с С*л.

где | 5Ц ( -число элементов в нонечноы ыножеотве ои

У(*Л - функция Эйлера, постоянные Д в ^ поло-

0 ^ '

жительны и не зависят от И- . При доказательстве теоремы 9 использован тот факт, что производящая функция 'У^г) последовательности I «ч00!

-1—^1—- имеет вид У~(2)= ^¿^^С2-) . ГД0

И * • -ЬиОУ)!

производящая функция последовательноотк -г... ■ причем •

ь!

Д_= 1а сгвпвнныв коаМВДиенты функции

""М^Сг) стремятся к нулю достаточно быстро. Возникшая при этом

последовательность рассматривалась в теореме б.

В теореме 10 получена формула числа л/ (а.) решений в

1С ь ^

уравнения К —СХ. в терминах цикяовой отруктуры подстановки

Ос & 5. .Эта формула довольно сложна. Поэтому в теоремах

11-13 изучается поведение числа д/^ (а.) как функции 0< б .

Теорема II утверждает, что воли П. = ^хЛХОс. л/ (а). *о

при фиксированной 1С > 2 выполняется равенство

VI Ь

СМ

В теореме 12 доказано, что если К. - число подстановок , для которых уравнение X. ==& имеет едилотванное решение в $к , то оущеотвуют постоянные » ^>0 ,ие

зависящие от \ь , такие, что при и фиксированном К 5 £

выполняется равенство

В иг_^1+<Хн% Г- ^

ь!

Заматш, чю согласно теоремам 9—12 выполняется равенство

Оллъ, --; —>£Ь Развитием этого соображения является

| | ^

теорема 13. , „

Пусть | ^т) - мнокество подстановок (Х€ 5 » ДДЯ которых

'К. г4 ^

уравнение * = <3. имеет 1пг\ рбшений в Я , и

I I

( / Л

Теорема 13 утверадавт, что если произвольные цэлые числа с( и $ удовлетворяют условиям с(>1, $>1»о()к . (¿^

и Ж | Б , ю ¿-У. $ 6 Д/^ ♦ Из теоремы 13, в частности,

следует, что при любом целом К. > % мнокество бесконечно.

Две последние теоремы диссертации посвящены абблевой системе уравнений в подстановках. ^

В работе Г 9] было покааано, что если С? - число решений

г> -1 ь

в N уравнения X, - 6 , где £ - токдественная подстановка из 5 , С?о = £ , целое (п ^ £ , то

оо ^С^ л

К-« 1

Пользуясь равенством (3), в работе [Ю^ было показано, что если р - простое число, го при фиксированном р и К-^- 00

С2._ ц Р

и

ц! ^тгр

А - 13 ~

где Со= - — при р=2. и ео=0 при р>2 А , ' °

Уравнение X. = 6 естественно ассоциируется о циклической группой порядка Иг . Поэтому естественный обобщенней этого уравнения является следующая система уравнений

(4)

которая ассоциируется с абелевой группой порядка И^*...' В связи с систеШй (4) доказываются теорема 14 и 15. Пусть .,»% )=■ С?и - число решений X

системы {Ц ) в » 1 , при этом - произволь-"

ный фиксированный набор натуральных чисел, б - тождественная

подстановка в 5, . .

к

В теореме 14 речь идет о производящей функции последовательности , ^ = <7,1 > и доказано, что существуют натураль-дые числа 1ч^ , , И^/,., -Сп^гакиа, что

и-о ы ; 1 <*. ^

причем 1.

Методом пьравала в теореме 15 получена асимптотика при И—у °° числа 1Д рашений системы (4 ) в : утверждается, что при фиксированных Ип^ ... > ь и И —» <» выполняется равенство

_ I

где Ш А- ^ прии к0=0

.числа I, , ^^ .определены в теорема 14, 5 >0 и не зависит от VI. .

- и -

Литература

1« Hardy G.H., Baaanujan S. Asymptotic formulae in combinatorial analysis, Proc. Lond. Matb.Soc. (2),1?(1918).

2. Weyl H.,Philosophy of liatbeaatiks and Hatural Sclenes, Frlnston University Press, 19*9, Appendices B-S.

3. Пойя Дж., Комбинаторные вычисления для групп, графов и химических соединений. - В кн. Перечислительные задачи комбинаторного анализа. - М.; Мир, 1979. •

Гончаров В.Л., Из области комбинаторики. - Изв.АН СССР,сер.матеы., I9W, Иг I.

5. Erdos P. and Turan P., On some problems of a statistical group-theory, I. Zeitschrift fur Wabrsch. mid verw. Gebiete, 1965,

II, III Acta liatb. Acad. Sci Hung., 1967» 1в; IV.Acta Math. Akad. Sci. Hung., 1968, 19.

6. Павлов А.И., 0 числе классов эквивалентности - матриц. Докл. РАН, 1993, 333, Кг 2.

7. Бендер Э.А., Асимптотические методы в теории перечислений. - В

кн. Перечислительные задачи комбинаторного анализа. - Ы.: Мир,1979.

«

8. Павлов A.id., О числе & цикловой структуре подстановок некоторых классов. - мат.сб., 1984. 12ч, «

d

9. Cbowla S., Herstein I.H., Scott V.R., The solutions of X — d.

in syeeetric groups, HorekeVid. Selsk.,1952, 25, 29-31.

d

IOJioser L., Win an 14., On solutions of X — 1 in syeaetruk groups. Canad. J .Math., 1957. 7, » 2.

Работы по теме диссертации

1. Шнеев М.П., Павлов А.И., 0 числе подстановок специального вида. Изтем.сб., 1976, 99, ie 3.

к

2. Павлов А.И., 0 числе решений уравнения X = О, в симметрической 'группе, Штем.сб., 1980,112, й 3.

3. Павлов А.К., О некоторых классах подстановок о ¿теоретике-числовыми ограничениями на длины циклов.Матем.сб.,1986,129, № 2. Павлов А.И., О числе и цикловой структуре решений одной сиотемы уравнений а подстановках; Дискрет, шт., 1989, I, й I.

5. Павлов А.И., Асимптотика числа решений одной системы уравнений в подстановках, Дискрет, кат., 1989, К! I, Из 2.

6. Павлов А.И., О числе подстановок о длинаш циклов из заданного множества, Дискрет.мат., 1991/3, К» 3.

7. Павлов А.И», Асимптотика чиола подстановок о теоретико-числовыми ограничениями на длины циклов. Докл. РАН, 1994, 335, й 5.