О максимальных антицепях решеток делителей натуральных чисел некоторых видов

1 В Е С Т Н И К П Е Р М С К О Г О У Н И В Е Р С И Т Е Т А 04 Математика. Механика. Информатика Вып. 3 (6) МАТЕМАТИКА УДК О максимальных антицепях решеток делителей натуральных чисел некоторых видов Я. Д. Половицкий, А. А. Волочков. Пермский государственный национальный исследовательский университет Россия, 64990, Пермь, ул. Букирева, 5 (34) Для натуральных чисел n видов p p p и p q r, где p, q, r и p, (, ) различные простые числа, оценивается максимальное число элементов в антицепях множества D ( n ) всех делителей n, частично упорядоченного относительно делимости (ширина w ( n ) множества D ( n ) ). Для ряда случаев эта ширина и антицепи из w ( n ) элементов находятся. Указывается приложение этих результатов к теории групп. Ключевые слова: натуральное число, делитель, ширина решетки, антицепь. Введение В работах [] и [] Я.Д. Половицким начато рассмотрение вопроса о нахождении в произвольной группе конечных подмножеств попарно неинцидентных (не содержащихся одна в другой) подгрупп, состоящих из максимального числа подгрупп, и числа составляющих их подгрупп. Как нетрудно видеть, для конечных циклических групп эти вопросы равносильны следующим вопросам о натуральных числах: Вопрос. Для натурального числа n найти максимальное число делителей n, ни один из которых не делит другой (этот вопрос сформулирован Я.Д. Половицким в статье []). Вопрос. Для натурального числа n найти подмножества множества D ( n ), в каждом из которых ни одно из входящих в него чисел не делит другое, состоящее из наибольшего числа элементов. Половицкий Я. Д. Волочков А. А, 04 Вначале приведем некоторые понятия из теории частично упорядоченных множеств (в основном из [3]). В работе используются следующие обозначения: n n делит ( n, натуральные числа); n n не делит ; [ a ] целая часть числа действительного числа a ; D ( n ) множество всех делителей натурального числа n ; конец доказательства; n, n,, n множество n, n,, n,, n N. Вначале приведем некоторые понятия из теории частично упорядоченных множеств (в основном из [3]). Основные определения и некоторые утверждения о D( n ) Определение. Частично упорядоченное множество будем называть у-множеством. 5

2 Я. Д. Половицкий, А.А. Волочков У-множество, в котором любые два элемента сравнимы, называют цепью (см. [3]). Определение. Если a a a n a n конечная цепь у-множества А, то ее длиной называют число n. Определение 3. Точная верхняя грань длин цепей у-множества А называется длиной А и обозначается через l( A ). Рассмотрим множество D ( n ) всех делителей числа n. Если a, b D ( n), то, полагая a b тогда и только тогда, когда a b, мы делаем D ( n ) у-множеством. Пусть n p p p () разложение числа n в t произведение простых множителей (не обязательно различных). Тогда, как нетрудно видеть, цепь p p p p p p n t длины t имеет максимальную длину из всех цепей в D ( n ) и по определению 3 l( D( n)) t (). В связи с этим естественно ввести следующее понятие: Определение 4. Если натуральное число n разлагается в произведение t простых множителей, то число t назовем длиной числа n и будем обозначать ее через l( n ). Другими словами, из () и определения 4 следует, что l( n) l( D( n)). Замечание. Введенное в определении 4 понятие длины натурального числа можно рассматривать и как частный случай приведенного в [4] ( главы III, с. 04) понятия длины слова над некоторым множеством А натуральных чисел в качестве А можно взять (несколько обобщив понятие длины из [4]) множество всех простых чисел. Легко проверяются следующие свойства длины натурального числа: l( n) l( n) l ;.. Если n и l( n) l( ), то n ; 3. Если n и n, то l( ) l( n) ; 4. Если n и l( n) l( ), то n и n. Определение 5 (см. [3]). Антицепью у-множества называется его подмножество, в котором никакие два его элемента не сравнимы. Введем понятие базиса у-множества. Определение 6. Антицепь у-множества Х, состоящая из наибольшего числа его элементов, называется базисом Х. Определение 7 (см. [3]). Число элементов в базисе у-множества Х назовем шириной Х и обозначим через w( X ). Введем понятие ширины натурального числа. Определение 8. Ширину у-множества D ( n ) назовем шириной числа n и обозначим ее через w( n ) (т. е. w( n) w( D( n)) ). В терминологии определений 8 и 6 сформулированные выше вопросы и принимают следующие виды: Вопрос '. Для n N \ найти w( n ). Вопрос '. Для n N \ найти базисы D ( n ). Определение 9. Подмножество у-множества D ( n ), состоящее из чисел одной и той же длины t, назовем t -однородным. Если оно является базисом D ( n ), то его назовем t -однородным базисом. Из отмеченного выше свойства 4 длины числа n вытекает справедливость следующего утверждения: Лемма. Любое t -однородное подмножество различных чисел из у-множества D ( n ) является антицепью в D ( n ). Лемма. Если B базис D ( n ), то для любого D( n) \ B существует b B, что выполняется одно из соотношений: b (3) или b (4), причем для не могут существовать такие b, b b (6). B, что b (5) и Доказательство. Так как B базис D ( n ), то множество, B B не является антицепью. Но В антицепь, и поэтому существует b B, что выполняется (3) или (4). Если найдутся b, b B, что справедливы (5) и (6), тоb b, и, так как В антицепь, b b. Но тогда из b и b следует, что b в противоречие с тем, что B. Лемма 3. Пусть В t -однородный базис D( n ) и D( n). Тогда l( ) t (7) тогда и только тогда, когда B. Если l( ) t (8), то делится на некоторое число из В; если же l( ) t (9), то делит некоторое число из В. 6

3 О максимальных антицепях решеток делителей натуральных чисел некоторых видов Доказательство. В силу леммы для данного существует b B, что выполняется (3) или (4). Так как В t -однородный базис, то l( b) t (0). Если выполняется (7), то l( ) l( b) и потому из (3) или (4) ввиду свойства длины числа справедливо равенство b и B (). Обратно, из () и того, что В t -однородный базис следует, что справедливо (7). Если выполняется (8), то по доказанному выше B и ввиду (0) l( ) l( b). Отсюда в силу свойства 3 длины числа следует, что b, т. е. (3) не выполняется, и потому справедливо (4). Аналогично из (9) получаем, что справедливо (3). Ширина и базисы D( n ) для чисел n, не делящихся на квадраты простых чисел Для таких чисел решение вопросов ' и ' можно получить из следующей хорошо известной теоремы: Теорема Шпернера (см. [5]). Пусть положительное целое число, F множество подмножеств множества M. таких, что никакой элемент из F не содержится ни в каком другом элементе из F, то есть для любых X, Y F имеем X Y. Тогда F C (). Равенство в () имеет место тогда и только тогда, когда F при четном и F при нечетном, где (3). Замечание. Очевидно, что F антицепь в множестве Т всех подмножеств множества M, а равенство (3) описывает антицепи Т, состоящие из наибольшего числа элементов, т. е. базисы множества Т и w( T) C. Из теоремы Шпернера вытекает Теорема. Пусть n p p p, где p различные простые числа (, ). То- гда w( n) C (4). Если число четное, то D ( n ) имеет единственный базис, являющийся -однородным. Если нечетное, то в D ( n ) существуют всего два базиса - однородный и -однородный. Доказательство. Отметим, что из вида n следует, что D( n) тогда и только тогда, когда p p p, где и M. Рассмотрим отображение у-множества D ( n ) в множество Т всех подмножеств множества M. ваемое так: ( ) Х. зада-. Нетрудно видеть, что биекция D ( n ) на Т. Так как, очевидно, при, t D( n) из t следует, что X X t, то изоморфизм у-множеств D ( n ) и Т, и потому переводит базис D ( n ) в базисы Т и w( D( n)) w( T ), т.е. в силу замечания справедливо (4). Но базисы множества Т в теореме Шпернера описываются равенствами (3). Значит, в D ( n ) при четном единственный базис, он является -однородным и w( D( n)) C. Аналогично из теоремы Шпернера получаем справедливость утверждения теоремы и для нечетного. О ширине и базисах ( D p q ) Из доказательства теоремы из [], в которой рассматривались антицепи у-множества всех подгрупп циклической группы порядка p q вытекает справедливость следующего утверждения: Лемма 4. Ширина числа n p q при равна ( ). Одним из базисов D ( n ) является q, pq,, p q, p. Определение 0. Указанный в лемме 4 базис у-множества D ( p q ) назовем стандартным базисом. 7

4 Я. Д. Половицкий, А.А. Волочков Отметим, что стандартный базис является -однородным. Ниже (в теореме ) будет передоказана лемма 4 и найдены все базисы D( p q ). Лемма 5. В любой антицепи множества ( D p q ) не могут содержаться пары чисел t l t l p, q, p q t t и,, p q p q (ибо одно из чисел каждой такой пары делит другие). Теорема. Пусть n p q и (). Тогда w( n) () и все базисы у- множества D ( n ) исчерпываются множествами чисел q, pq,, p q (3), где 0 неотрицательные целые числа, удовлетворяющие неравенствам 0. (4) Доказательство. В силу () множества из, (5), удовле- чисел творяющих неравенствам (4), найдутся. Пусть (5) любое такое множество. Составим с его помощью множество (3). Из неравенств (4) следует, что (3) это антицепь. Но в числах (3) в качестве множителей встречаются всевозможные степени числа p, делящие n : это 0 p, p,, p. В силу леммы 5 антицепей из большего числа элементов в D ( n ) быть не может, и потому (3) базис D ( n ). Так как в нем ( ) чисел, то справедливо равенство (). Обратно, если В произвольный базис D ( n ), то в силу () он состоит из ( ) чисел и по лемме 5 все степени числа p в них разные, т. е. В это множество чисел (3). Так как p q p q (по определению базиса), то для всех,, и потому выполняются неравенства (4). Следствие. Если n p q, то D ( n ) имеет единственный базис это стандартный базис q, pq,, p q, p (см. определение 0). Действительно, при множество из ( ) чисел, удовлетворяющих неравенствам (4), единственно это числа. 0. Следствие. Если n p q и, то в D ( n ) для каждого целогоt, такого, что t (5), существует единственный t - однородный базис это t t t t q, pq,, p q q B (6), где В стандартный базис D ( n ). Для других t в D ( n ) t -однородных базисов нет. Доказательство. В силу теоремы множество (6) является базисом D ( n ). По определению 9 он является t -однородным. Очевидно, что он единственный t -однородный базис для данногоt. С другой стороны, если базис (3) множества D ( n ) t -однородный, то t, т. е. t, а 0 t, и выполняются неравенства (5). Теорема и ее следствия позволяют оценить, а в ряде случаев и найти ширину чисел вида p q r. О ширине чисел вида (, ) Лемма 6. Пусть p q r n hr (), где h r (). Если hr, hr,, ht r, где h h (, t) антицепь в D ( n ), то w( h) (3) и w( n) w( h)( ) (4). Доказательство. Так как h r h r тогда и только тогда, когда h h (, l, t), то D h, и по определе- h,, h t антицепь в ( ) ниям 8 и 6 t w( h) l, т. е. выполняется (3). Если В любой базис D ( n ), то для всех 0, составим из его элементов попарно не пересекающиеся подмножества из максимального числа элементов, множителем которых является r при фиксированном. Тогда B ; отсюда и из (3) получаем 0 B w( h)( ), и справедливо (4). Следствие. Если n p q r, где, то в обозначениях леммы 6 и ( ) и w( n) ( )( ). Равенство ( ) (4) имеет место тогда и только тогда, когда h h (5) базис D( p q ). t Получается из леммы 6 при h p q, ибо по теореме w( h) ( ). Равенство (4) имеет место тогда и только тогда, когда l 8

5 О максимальных антицепях решеток делителей натуральных чисел некоторых видов t w( p q ), т.е. (5) базис ( D p q ). Лемма 7. Пусть n p q r, В некоторый базис D ( n ), множество всех чи- сел из В, которые делятся на r, но не делятся на при фиксированном. Тогда из r антицепей ( 0, ) не более одной состоят из ( ) чисел и w( n) ( ) (6). Доказательство. Введем обозначение: h p q. Предположим, что существуют и, что, но (7). Тогда h r,, hr tr,, t r (8) и (9), где h, t D ( h ) (0),. Так как и - антицепи (как часть базиса В), то из (8) и (9) следует, что h,, h (0) и t,, t () антицепи из D ( h ). Но они состоят из ( ) чисел, а по теореме ( ) ( w h w p q ) ( ). Значит, (0) и () базисы D ( h ). Но по следствию теоремы D ( h ) имеет единственный базис, и потому (0) и () совпадают. В частности h t для некоторого. Но тогда h r и h r B, что не- возможно, ибо одно из этих чисел делит другое. Значит, для всех, кроме быть может, одного,. Так как в силу леммы 6 w( h) для всех, B и 0 при, то B ( ) ( ), т. е. выполняется неравенство (6). Следствие. Если n p q r, то w( n) () и при в D ( n ) существует -однородный базис, а при и ( ) -однородный базис. Доказательство. Из леммы 7 при получаем: w( n) ( ) (3). Пусть. Тогда существует антицепь из ( ) чисел например, B q, q p,, qp, p, q r, q pr,, qp r, p r это -однородное множество и в силу леммы оно является антицепью. Теперь из (3) получаем, что В базис D ( n ), т. е. В -однородный базис. Если, то в силу (3) w( n) 5 (4). Но в G существует ( ) -однородное множество R p q, q p, pqr, p r, q r из 5 чисел. В силу (4) R ( ) -однородный базис D ( n ), и потому выполняется () для. Наконец, при D ( n ) имеет базис pq, pr, qr. Он ( ) -однородный и выполняется () и при. Следствие. Если n p q r, то w( n) 3 и в D ( n ) существует ( ) -однородный базис. Доказательство. Пусть. Рассмотрим множества 0 p q, p q,, pq, p r p qr pq r q r и. p r, p qr,, pq r, q r. Они различны, каждое из них ( ) - однородное и, а 0. Тогда 0 ( ) -однородная антицепь (по лемме ) из ( ) 3 элементов. Но при условиях следствия имеем, и из леммы 7 получаем: w( n) (3 ). Значит, базис D ( n ). Если, то есть n pqr, то по лемме 7 w( n) 4, и потому B pq, pr, qr, r -однородный базис D ( n ). Значит, w( n) 4, и потому утверждение следствия справедливо и для. Теорема 4. Пусть n p q r, где (). Если ( ) (), то w( n) ( )( ) (3) и в D ( n ) существует -однородный базис. Если ( ) (4), то w( n) l, где ( )( ) l ( )( ) (5) и в D ( n ) существует -однородная антицепь из l чисел. 9

6 Я. Д. Половицкий, А.А. Волочков Доказательство. Введем обозначение: h p q (6). Пользуясь различными t -однородными базисами D ( h ), полученными в следствии теоремы, построим антицепи указанного ниже вида (8) для мак- симального числа возможных при условиях теоремы значений. Пусть B q, q p,, pq, p стандартный базис D ( h ). Тогда по следствию теоремы для всех t, таких что t (7), существуют t -однородные базисы D ( h ) вида t q B. Составим 0 q B. Если ( ) ( ) 0, то полагаем q rb и так далее: ( ) q r B (8) (если ( ) 0 и ). Составление закончится таким множеством l, что должно выполняться одно из условий: I. l l или II.. ( l) 0 ( l) 0 Рассмотрим каждый из этих случаев. I. Пусть выполняется условие I. Оно равносильно неравенству ( ) 0, т. е. условию (). При его выполнении будут построены все возможные это 0. (ибо максимальная степень r, на которую делится n). Отметим, что, (ибо степени числа r в них разные) и -однородные множества. Поэтому состоит из ( )( ) 0 -однородных чисел и является по лемме антицепью. Но в силу следствия леммы 6 w( n) ( )( ), и поэтому -однородный базис D ( n ). Доказана первая часть теоремы 4. II. Пусть выполняется условие II. Тогда l ( ), т. е. выполняется (4). Последний из составленных выше антицепей будет r B. Больше антицепей типа из ( ) чисел составить нельзя. Но подобные антицепи можно составить из меньшего числа элементов. Рассмотрим множества ( ) ( ) B p, p q,, pq, q для,. B ( ) -однородная антицепь и B ( ) (9). Получаем B r ( ) ( ), ( ) ( ) и так B r далее. Чтобы составление таких антицепей закончилось на множестве на t -м шаге, требуется, чтобы ( t) (0) и выполнялось условие t (). Из (0) вытекает равенство t ( ) (). В силу неравенства (4), выполняемого в пункте II, число t вида () положительно. Из () следует, что t ( ) (ибо в силу () ), и потому выполняется (). Так как ( ) ( ) Br (3) и B ( ) ( ) -однородная антицепь, то ( ) -однородная антицепь. Итак, в пункте II мы дополнительно составили антицепи ( ), ( ). В силу (9) и (3) ( ) ( ) (4),,( ). Всего вместе с составленными в начале доказательства антицепями, 0, мы составили -однородные антицепи 0. Они попарно не пересекаются (ибо содержат различные степени числа r ), и потому множество (5) -однородная антицепь. 0 Так как в силу (8) B ( ) для 0,, то отсюда из (4) и (5) получаем: ( )( ) [( ) ( ) ( t) ] ( )( ) ( ) ( t) ( t t) ( )( ) ( ) ( t) t( ) ( )( ) ( ) ( )( ) ( )( ) (мы использовали равенство ()). Так как w( n), то этим доказано неравенство (5). 0

7 О максимальных антицепях решеток делителей натуральных чисел некоторых видов Следствие. Если n p q r и, ( ) то ( ) w( n) ( ). Доказательство. При из теоремы 4 получаем ( ) w( n) ( ) ( ) ( ) ( ) ( ). Неравенство ( ) w( n) доказано в лемме 7. Замечание 3. При и из следствия теоремы 4 получаем w( p q r), как и установлено в следствии леммы 7. При других w( n ) вычисляется в следствии теоремы 4 с точностью до слагаемого, и потому более ( ) точным получается при малых. Некоторые приложения в теории групп Укажем на одно из применений полученных выше результатов в теории групп. В работе [] было введено понятие ранга инцидентности группы, которое мы заменяем введенным ранее Л.Н. Шевриным понятием d -ширины группы. Определение. Пусть G группа. Множество из максимального числа подгрупп группы G, ни одна из которых не содержится в другой, назовем d -базисом группы G. Определение. d -базис из подгрупп, порядки которых имеют одинаковую длину l, назовем l -однородным d -базисом. Определение 3. Число подгрупп в d -базисе группы G назовем d -шириной группы G и обозначим через w( G ). Хорошо известно, что если G конечная циклическая группа порядка n, то решетка ее подгрупп ubg изоморфна решетке D ( n ) (ибо для любого n в G существует единственная подгруппа порядка ). Отсюда и из определения 8 вытекает справедливость следующего утверждения: Лемма 8. d -ширина циклической группы порядка n равна ширине числа n. Из этой леммы из доказанных выше теорем и 4 и леммы 7 вытекают следующие теоретико-групповые утверждения: Теорема. Пусть G циклическая группа порядка n p p p, где p (, ) различные простые числа. Тогда d -ширина группы G равна C. Если число четное, то G имеет единственный d -базис, и он является -однородным. Если число нечетное, то G имеет всего два базиса - однородный и - однородный. Лемма 7'. Пусть G циклическая группа порядка p q r. Тогда w( G ) ( ( ) ). Следствие '. Если G циклическая группа порядка p q r, то w( G ) и при в G существует -однородный d -базис, а при ( ) -однородный d -базис. Следствие '. Если G циклическая группа порядка p q r, то w( G ) 3 и в G существует ( ) -однородный d -базис. Теорема 4'. Пусть G циклическая группа порядка p q r и. Если ( ), то w( G ) ( )( ). Если ( ), то w( G) t, где ( )( ) t ( )( ), и в G существует -однородная антицепь из t подгрупп. Заключение В настоящей работе найдена ширина натуральных чисел видов p q p q r p q r p q r. при ( ), p p pl, и для каждого из этих случаев в D ( n ) находились t -однородные базисы для некоторых t.

8 Я. Д. Половицкий, А.А. Волочков Указаны приложения этих результатов в теории групп. В связи с полученными результатами естественно поставить следующий Вопрос 3. Для всякого ли натурального числа n в D ( n ) существует t -однородный базис хотя бы одного t? Этот вопрос тесно связан со следующим вопросом. Вопрос 4. Пусть n N \ и n p p p каноническое разложение числа n. Найти натуральное число t, для которого уравнение x x x t при ограничениях x, x,, x имеет наибольшее число решений в целых неотрицательных числах. Список литературы. Половицкий Я.Д. Ранг инцидентности // Алгебра и линейная оптимизация: тр. междунар. сем. Екатеринбург, 00. С Половицкий Я.Д. Группы, имеющие небольшие ранги инцидентности // Вестник Пермского университета. Сер. Математика. Механика. Информатика Вып. 5. С Биркгоф Г. Теория решеток. М.: Наука, с. 4. Калужнин Л.А. Введение в общую алгебру. М.: Наука. 447 с. 5. Conrad Engel. perner theory. Kebrdge unverty pre p. About axal antchan of gratng dvor of natural nuber Ja. D. Polovty, A. A. Volochov Per tate Unverty, Rua, 64990, Per, Bureva t., 5 (34) For the natural nuber of apect p p p and p q r, where p, q, r and p,, n are dfferent prer nuber, axal quantty of eleent n antchan of the et D ( n ) of dfferent dvor n, partly-ordered regardng dvon (the wdth w ( n ) of the et D ( n ) ) etated n th paper. For the ae cae w ( n ) and antchan fro w ( n ) eleent are found. Thee reult are appled to the theory of group. Key word: natural nuber; dvor; wdth of the gratng; antchan.