О максимальных антицепях решеток делителей натуральных чисел некоторых видов
Автор: Половицкий Я.Д., Волочков А.А.
Журнал: Вестник Пермского университета. Математика. Механика. Информатика @vestnik-psu-mmi
Рубрика: Математика
Статья в выпуске: 3 (26), 2014 года.
Бесплатный доступ
Для натуральных чисел n видов p 1 p 2... p k и p mq kr s, где p, q, r и p i, ( i = 1, k ) - различные простые числа, оценивается максимальное число элементов в антицепях множества D ( n ) всех делителей n, частично упорядоченного относительно делимости (ширина w ( n ) множества D ( n )). Для ряда случаев эта ширина и антицепи из w ( n ) элементов находятся. Указывается приложение этих результатов к теории групп.
Натуральное число, делитель, ширина решетки, антицепь
Короткий адрес: https://sciup.org/14729924
IDR: 14729924
Текст научной статьи О максимальных антицепях решеток делителей натуральных чисел некоторых видов
В работах [1] и [2] Я.Д. Половицким начато рассмотрение вопроса о нахождении в произвольной группе конечных подмножеств попарно неинцидентных (не содержащихся одна в другой) подгрупп, состоящих из максимального числа подгрупп, и числа составляющих их подгрупп. Как нетрудно видеть, для конечных циклических групп эти вопросы равносильны следующим вопросам о натуральных числах:
Вопрос 1. Для натурального числа n ^ 1 найти максимальное число делителей n , ни один из которых не делит другой (этот вопрос сформулирован Я.Д. Половицким в статье [2]).
Вопрос 2. Для натурального числа n ^ 1 найти подмножества множества D ( n ) , в каждом из которых ни одно из входящих в него чисел не делит другое, состоящее из наибольшего числа элементов.
Вначале приведем некоторые понятия из теории частично упорядоченных множеств (в основном из [3]).
В работе используются следующие обозначения:
-
n | m – n делит m ( n , m – натуральные числа);
-
n | m – n не делит m ;
-
[ a ] – целая часть числа действительного числа a ;
D ( n ) – множество всех делителей натурального числа n ;
-
□ - конец доказательства;
m { n 1 ,n 2 , . , n k }
–
множество
{ mn 1 , mn 2, . , mnk } , ( m , n i e N , i = 1, k ) .
Вначале приведем некоторые понятия из теории частично упорядоченных множеств (в основном из [3]).
Основные определения и некоторые утверждения о D ( n )
Определение 1. Частично упорядоченное множество будем называть у-множеством .
У-множество, в котором любые два элемента сравнимы, называют цепью (см. [3]).
Определение 2. Если a i < a 2 < < an-1 < an
– конечная цепь у-множества А , то ее длиной называют число n — 1 .
Определение 3. Точная верхняя грань длин цепей у-множества А называется длиной А и обозначается через l ( A ) .
Рассмотрим множество D ( n ) всех делителей числа n . Если a , b e D ( n ) , то, полагая a < b тогда и только тогда, когда a | b , мы делаем D ( n ) у-множеством. Пусть n = p 1 p 2 ... p t (1) - разложение числа n в произведение простых множителей (не обязательно различных). Тогда, как нетрудно видеть, цепь
-
1 < P 1 < P 1 P 2 < . < P 1 P 2 . Pt — 1 < n длины t имеет максимальную длину из всех цепей в D ( n ) и по определению 3
l ( D ( n )) = t (2). В связи с этим естественно ввести следующее понятие:
Определение 4. Если натуральное число n ^ 1 разлагается в произведение t простых множителей, то число t назовем длиной числа n и будем обозначать ее через l ( n ) .
Другими словами, из (2) и определения 4 следует, что l ( n ) = l ( D ( n )) .
Замечание 1. Введенное в определении 4 понятие длины натурального числа можно рассматривать и как частный случай приведенного в [4] ( § 1 главы III, с. 104) понятия длины слова над некоторым множеством А натуральных чисел – в качестве А можно взять (несколько обобщив понятие длины из [4]) множество всех простых чисел.
Легко проверяются следующие свойства длины натурального числа:
-
1. l ( nm ) = l ( n ) + 1 ( m ) ;
-
2. Если m | n и l ( n ) = l ( m ) , то m = n ;
-
3. Если m ^ n и m | n , то l ( m ) < l ( n ) ;
-
4. Если m ^ n и l ( n ) = l ( m ) , то n \ m и m | n .
Определение 5 (см. [3]). Антицепью у-множества называется его подмножество, в котором никакие два его элемента не сравнимы.
Введем понятие базиса у-множества.
Определение 6. Антицепь у-множества Х , состоящая из наибольшего числа его элементов, называется базисом Х .
Определение 7 (см. [3]). Число элементов в базисе у-множества Х назовем шириной Х и обозначим через w ( X ) .
Введем понятие ширины натурального числа.
Определение 8. Ширину у-множества D ( n ) назовем шириной числа n и обозначим ее через w ( n ) (т. е. w ( n ) = w ( D ( n )) ).
В терминологии определений 8 и 6 сформулированные выше вопросы 1 и 2 принимают следующие виды:
Вопрос 1'. Для n e N \1 найти w ( n ) .
Вопрос 2'. Для n e N \1 найти базисы D ( n ) .
Определение 9. Подмножество у-мно-жества D ( n ) , состоящее из чисел одной и той же длины t , назовем t -однородным . Если оно является базисом D ( n ) , то его назовем t -однородным базисом .
Из отмеченного выше свойства 4 длины числа n вытекает справедливость следующего утверждения:
Лемма 1. Любое t -однородное подмножество различных чисел из у-множества D ( n ) является антицепью в D ( n ) .
Лемма 2. Если B – базис D ( n ) , то для любого m e D ( n ) \ B существует b e B , что выполняется одно из соотношений: m | b (3) или b | m (4), причем для m не могут существовать такие b 1 , b 2 e B , что b 1 | m (5) и m | b 2 (6).
Доказательство. Так как B – базис D ( n ) , то множество { m , B } ^ B не является антицепью. Но В – антицепь, и поэтому существует b e B , что выполняется (3) или (4).
Если найдутся b 1 , b 2 e B , что справедливы (5) и (6), то b 1 | b 2 , и, так как В – антицепь, b 1 = b 2 . Но тогда из b 1 | m и m | b 1 следует, что m = b 1 в противоречие с тем, что m £ B . П
Лемма 3. Пусть В – t -однородный базис D ( n ) и m e D ( n ) . Тогда l ( m ) = t (7) тогда и только тогда, когда m e B . Если l ( m ) > t (8), то m делится на некоторое число из В ; если же l ( m ) < t (9), то m делит некоторое число из В .
Доказательство. В силу леммы 2 для данного m существует b е B , что выполняется (3) или (4). Так как В – t -однородный базис, то l ( b ) = t (10).
Если выполняется (7), то l ( m ) = l ( b ) и потому из (3) или (4) ввиду свойства 2 длины числа справедливо равенство m = b и m е B (11). Обратно, из (11) и того, что В – t -однородный базис следует, что справедливо (7).
Если выполняется (8), то по доказанному выше m ^ B и ввиду (10) l ( m ) > l ( b ) . Отсюда в силу свойства 3 длины числа следует, что m | b , т. е. (3) не выполняется, и потому справедливо (4). Аналогично из (9) получаем, что справедливо (3). П
Ширина и базисы D(n) для чисел n, не делящихся на квадраты простых чисел
Для таких чисел решение вопросов 1' и 2' можно получить из следующей хорошо известной теоремы:
Теорема Шпернера (см. [5]). Пусть s – положительное целое число, F– множество подмножеств множества Ms ={1,2,...,s} та- ких, что никакой элемент из F не содержится ни в каком другом элементе из F, то есть для любых X, Y е F имеем X ^ Y. Тогда il„...
|F < C2(12). Равенство в (12) имеет место тогда и только тогда, когда
s
F = {X с M s :|X| = —} при четном s и
F = {X с M s
S + е
:| X |= z } при нечетном s , где е е {-1,1} (13).
Замечание 2. Очевидно, что F – антицепь в множестве Т всех подмножеств множества Ms , а равенство (13) описывает антицепи Т , состоящие из наибольшего числа элемен-
Г s 1
тов, т. е. базисы множества Т и w (T ) = Cs L 2 J .
Из теоремы Шпернера вытекает
Теорема 1. Пусть n = p 1 p 2... ps , где p i - различные простые числа ( i = 1, s ). То-
I s I гда w(n) = C2^ (14). Если число s четное, то
D(n) имеет единственный базис, являющий- ся s -однородным. Если s нечетное, то в 2
s - 1
D ( n ) существуют всего два базиса –
-
s +1
однородный и -однородный.
Доказательство. Отметим, что из вида n следует, что m е D(n) тогда и только то гда, когда m = pp ... p, , где k < s и j1 j2 jk ji е Ms. Рассмотрим отображение ф у-множества D(n) в множество Т всех подмножеств множества Ms ={1,2,.,s}, задаваемое так: ф(m) = xm = {j..j2,., jk} . Нетрудно видеть, что ϕ – биекция D(n) на Т. Так как, очевидно, при m, t е D(n) из m 11
следует, что Xm < X t , то ф - изоморфизм у-множеств D ( n ) и Т , и потому ϕ переводит базис D ( n ) в базисы Т и w ( D ( n )) = w ( T ) , т.е. в силу замечания 2 справедливо (14).
Но базисы множества Т в теореме Шпернера описываются равенствами (13). Значит, в D(n) при четном s – единствен- ный базис, он является s -однородным и 2
Г - 1
w ( D ( n )) = Cs L2J.
Аналогично из теоремы Шпернера получаем справедливость утверждения теоремы 1 и для нечетного s . П
О ширине и базисах D ( p m q k )
Из доказательства теоремы 1 из [1], в которой рассматривались антицепи у-мно-жества всех подгрупп циклической группы порядка pmqk вытекает справедливость следующего утверждения:
Лемма 4. Ширина числа n = pmqk при m < к равна ( m + 1) . Одним из базисов D ( n ) m mm -1 m -1 m)
q , pq , . p q , p } .
Определение 10. Указанный в лемме 4 базис у-множества D ( p m q k ) назовем стандартным базисом .
Отметим, что стандартный базис является m -однородным. Ниже (в теореме 2) будет передоказана лемма 4 и найдены все базисы D ( pmqk ) .
Лемма 5. В любой антицепи множества D(pmqk ) не могут содержаться пары чисел {t t m m-> ~t} p , q , pq1} и {p 1, q , p 2 q } (ибо одно из чисел каждой такой пары делит другие).
Теорема 2. Пусть n = pmqk и m
Доказательство. В силу (1) множества из ( m + 1 ) чисел { s i | i = 1, m + 1 } (5), удовлетворяющих неравенствам (4), найдутся. Пусть (5) – любое такое множество. Составим с его помощью множество (3). Из неравенств (4) следует, что (3) – это антицепь. Но в числах (3) в качестве множителей встречаются всевозможные степени числа p , делящие n : это p 0, p 1,... , pm . В силу леммы 5 антицепей из большего числа элементов в D ( n ) быть не может, и потому (3) – базис D ( n ) . Так как в нем ( m + 1) чисел, то справедливо равенство (2).
Обратно, если В – произвольный базис D (n), то в силу (2) он состоит из (m +1) чисел и по лемме 5 все степени числа p в них разные, т. е. В – это множество чисел (3). Так как plqs' | p‘+1 qs'+1 (по определению базиса), то si > si+1 для всех i = 1, m -1, и потому выполняются неравенства (4). 0
Следствие 1. Если n = pmqm , то D ( n ) имеет единственный базис – это стандартный базис { qm , pqm - 1 ,, pm - 1 q , pm } (см. определение 10).
Действительно, при k = m множество из
( m + 1) чисел s i , удовлетворяющих неравенствам (4), единственно – это числа m , m - 1, ... ,2,1,0 .
Следствие 2. Если n = pmqk и m Доказательство. В силу теоремы 2 множество (6) является базисом D(n) . По определению 9 он является t -однородным. Очевидно, что он – единственный t -однородный базис для данногоt . С другой стороны, если базис (3) множества D(n) t -однородный, то m + sm = t, т. е. t > m, а s0= t< k, и выполняются неравенства (5). 0 Теорема 2 и ее следствия позволяют оценить, а в ряде случаев и найти ширину чисел вида pmqkrs . О ширине чисел вида pmqkrs Лемма 6. Пусть n = hrs (1), где (h, r) = 1 (2). Если Sj={h1 rJ, h2rJ, .. ., htrJ} , где hi | h (i=1,t) - антицепь в D(n), то |Sj|< w(h) (3) и w(n) < w(h)(s +1) (4). Доказательство. Так какhirj | hlrj тогда и только тогда, когда hi | hl (i,l =1,t), то {h1,,ht} - антицепь в D (h), и по определениям 8 и 6 t< w(h), т. е. выполняется (3). Если В – любой базис D(n) , то для всех J = 0, s составим из его элементов попарно не пересекающиеся подмножества Sj из максимального числа элементов, множителем которых является r j при фиксированном j. Тогда s B = U S j ; отсюда и из (3) получаем J=о J |B| < w(h)(s +1), и справедливо (4). 0 Следствие. Если n = pmqkrs, где k > m, то в обозначениях леммы 6 и S | < (m +1) и w(n) < (m +1)(s +1). Равенство |SJ | = (m +1) (4) имеет место тогда и только тогда, когда {h1,• • •,ht} (5) - базис D(pmqk). Получается из леммы 6 при h = pmqk, ибо по теореме 2 w(h) = (m +1). Равенство (4) имеет место тогда и только тогда, когда t = m +1 = w (pmqk ), т.е. (5) - базис D(pmqk). Лемма 7. Пусть n = pmqmrs, В - некоторый базис D(n) , Sj – множество всех чисел из В, которые делятся на r j , но не делятся на rJ+1 при фиксированном j. Тогда из антицепей Sj (j' =0,s) не более одной состоят из (m +1) чисел и w(n) < m (s +1) +1 (6). Доказательство. Введем обозначение: h = pm qm . Предположим, что существуют i и J, что i ^ J , но |Si| = Sjl = m +1 (7). Тогда S = { hri,., hm+1 ri} (8) и Sj={t1 rj,..., tm+1rJ} (9), где hk, tk e D(h ) (10) k=1, m+1. Так как Si и Sj. - антицепи (как часть базиса В), то из (8) и (9) следует, что {h1,.,h,m+1} (10) и {tp., tm+1} (11) - антицепи из D (h). Но они состоят из (m +1) чисел, а по теореме 2 w(h) = w(pmqm) = (m + 1). Значит, (10) и (11) – базисы D(h) . Но по следствию 1 теоремы 2 D(h) имеет единственный базис, и потому (10) и (11) совпадают. В частности h1 = tk для некоторого к. Но тогда h1 ri и h1 rJ' e B , что невозможно, ибо одно из этих чисел делит другое. Значит, для всех i , кроме быть может, одного, |Si| < m. Так как в силу леммы 6 мы 1 оно является антицепью. Теперь из (13) получаем, что В – базис D(n) , т. е. В – m -однородный базис. Если m = 2, то в силу (13) w(n) < 5 (14). Но в G существует (m +1)-однородное множество R = { p2q, q2p, pqr, p2r, q2r} из 5 чисел. В силу (14) R- (m +1)-однородный базис D(n) , и потому выполняется (12) для m = 2. Наконец, при m = 1 D (n) имеет базис {pq, pr, qr}. Он (m +1) -однородный и выполняется (12) и при m = 1. □ Следствие 2. Если n = pmqmr2, то w (n) = 3 m +1 и в D (n) существует (m +1) -однородный базис. Доказательство. Пусть m > 2. Рассмотрим множества S0 ={ pmq, pm-1q2,..., pqm } , S1 ={ pmr, pm-1qr,., pqm-1r, qmr } и гда S = S0U S1 U S2- (m + 1) -однородная антицепь (по лемме 1) из 2 m + (m +1) = 3 m +1 элементов. Но при условиях следствия 2 имеем s = 2 , и из леммы 7 получаем: w(n) < (3m +1). Значит, S- базис D(n) . Если m = 1, то есть n = pqr2, то по лемме 7 w(n) < 4, и потому B = {pq, pr, qr, r2} - 2-однородный базис D (n). Значит, w(n) = 4, и потому утвержде ние следствия 2 справедливо и для m = 1. □ Теорема 4. Пусть n = pmqkrs , где s< m< k (1). Если k > (m + s) (2), то w (n) = (m +1)( s +1) (3) и в D (n) существует k-однородный базис. Если k< (m + s) (4), то w (n) > l, где / / (s + m -k)(m + k-s +1) l = (m +1)( k - m +1) + ------------------- (5) и в D(n) существует k-однородная антицепь из l чисел. Доказательство. Введем обозначение: h = pmqk (6). Пользуясь различными t -однородными базисами D(h) , полученными в следствии 2 теоремы 2, построим антицепи S j указанного ниже вида (8) для максимального числа возможных при условиях теоремы значений j. Пусть B = { qm, qm-1 p,..., pqm-1, pm } -стандартный базис D(h) . Тогда по следствию 2 теоремы 2 для всех t, таких что m< t< k (7), существуют t -однородные базисы D (h) вида q‘-mB . Составим S0 = qk-mB . Если k - (m +1) > 0 , то полагаем S1 = qk-(m+1) rB и так далее: SJ = qk-(m+j) rJB (8) (если k - (m + J) ^ 0 и J < s ). Составление Sj закончится таким множеством Sl , что должно выполняться одно из условий: I. 11 = s [ k - (m +1) > 0 [ l < s или II. 2 . 1 k - (m +1) = 0 Рассмотрим каждый из этих случаев. I. Пусть выполняется условие I. Оно равносильно неравенству k - (m + s) > 0, т. е. условию (2). При его выполнении будут построены все возможные Sj - это S0, S1,., Ss (ибо s – максимальная степень r , на которую делится n). Отметим, что |Sj-| = m +1, Si П Sj =0 (ибо степени числа r в них разные) и Sj – k-однородные множества. Поэтому S = U S. состоит из (m +1)(s +1) J=0 j k-однородных чисел и является по лемме 1 антицепью. Но в силу следствия леммы 6 w(n) < (m + 1)(s + 1), и поэтому S -k-однородный базис D(n) . Доказана первая часть теоремы 4. II. Пусть выполняется условие II. Тогда l = (k - m) < s, т. е. выполняется (4). Последний из составленных выше антицепей Sj будет Sk-m = rk-mB . Больше антицепей типа Sj из (m +1) чисел составить нельзя. Но подобные антицепи можно составить из меньшего числа элементов. Рассмотрим множества ту ( m-i m-(i+1) m-(i+1) m-i ) Bi={p ,p q,•••,pq ,q } для i = 1,m-1. Bi - (m - i) -однородная антицепь и |Bi| = (m - i) + 1 (9). Получаем V - R rk-(m-1) - R rk-(m-2) И Sk-(m-1) B1 r , Sk-(m-2) B 2 r и так далее. Чтобы составление таких антицепей закончилось на множестве Ss на t-м шаге, требуется, чтобы k - (m - t) = s (10) и выполнялось условие t < m (11). Из (10) вытекает равенство t = (s + m) - k (12). В силу неравенства (4), выполняемого в пункте II, число t вида (12) положительно. Из (12) следует, что t = m - (k - s) < m (ибо в силу (1) s < k), и потому выполняется (11). Так как Sk-,m -, = BP-(m-" (13) и B-.-„ - (m - i) -однородная антицепь, то Sk-(m-i) -k-однородная антицепь. Итак, в пункте II мы дополнительно составили антицепи Sk-(m-1), Sk-(m-2), . , Ss . В силу (9) и (13) Sk-(m-i)| = (m -i) +1 (14), i = 1,(s + m) - k. Всего вместе с составленными в начале доказательства антицепями Sj , J = 0, k - m мы составили k-однородные антицепи S 0, S1,., Sk - m , Sk - m +1,., Ss . Они попарно не пересекаются (ибо содержат различные степени числа r ), и потому множест-s во S = U S - (15) - k-однородная антицепь. J=0 J Так как в силу (8) |SJ| = |B| = (m +1) для J = 0, k - m, то отсюда из (14) и (15) получаем: | S| = (m +1)( k - m +1) + [(m -1) +1 + (m - 2) + +1 +... + (m -1) +1] = (m +1)( k - m +1) + . , (m -1) + (m -1) .. + (t ■ 1 + -----■ t) = (m + 1)(k - m + 1) + (m -1) + (m -1).. +1(1 + ----------------) = (m +1)(k - m +1) + . ,. 2 m - s - m + k +1 +(s + m - k)-------—= / (s + m - k)(m + k - s +1) = (m +1)(k - m +1) + -------------------- (мы использовали равенство (12)). Так как w(n) > |s| , то этим доказано неравенство (5). □ Следствие. Если n = pmqmrsus < m , то m (s +1) +1 > w (n) > 1 + m (s +1) - s (s^ ^ . Доказательство. При k = m из теоремы 4 получаем „ s(2m - s +1) w (n ) > (m +1) +-----= . s (s -1) (m +1) + ms— = s(s -1) m (s +1) +1. Неравенство m(s +1) +1 > w(n) доказано в лемме 7. □ Замечание 3. При s = 1 иm > 2 из следствия теоремы 4 получаем w(pmqmr) = 1 + 2m, как и установлено в следствии 1 леммы 7. При других s w(n) вычисляется в следствии теоремы 4 с точно-s(s -1) стью до слагаемого , и потому более точным получается при малых s . Некоторые приложения в теории групп Укажем на одно из применений полученных выше результатов в теории групп. В работе [1] было введено понятие ранга инцидентности группы, которое мы заменяем введенным ранее Л.Н. Шевриным понятием d -ширины группы. Определение 11. Пусть G – группа. Множество из максимального числа подгрупп группы G, ни одна из которых не содержится в другой, назовем d -базисом группы G. Определение 12. d -базис из подгрупп, порядки которых имеют одинаковую длину l , назовем l -однородным d -базисом. Определение 13. Число подгрупп в d -базисе группы G назовем d -шириной группы G и обозначим через w(G) . Хорошо известно, что если G – конечная циклическая группа порядка n , то решетка ее подгрупп SubG изоморфна решетке D(n) (ибо для любого m | n в G существует единственная подгруппа порядка m). Отсюда и из определения 8 вытекает справедливость следующего утверждения: Лемма 8. d -ширина циклической группы порядка n равна ширине числа n . Из этой леммы из доказанных выше теорем 1 и 4 и леммы 7 вытекают следующие теоретико-групповые утверждения: группы G равна CsL J. Если число s четное, то G имеет единственный d -базис, и он является s -однородным. Если число s нечетное, 2 то G имеет всего два базиса - s—— - - s +1 _ . однородный и - однородный. Лемма 7'. Пусть G – циклическая группа порядка pmqmrs . Тогда w (G) < (m (s +1) +1). Следствие 1'. Если G – циклическая группа порядка pmqmr , то w(G) = 2m +1 и при m > 2 в G существует m -однородный d -базис, а при m< 2 - (m +1) -однородный d -базис. Следствие 2'. Если G – циклическая группа порядка pmqmr2, то w(G) = 3m +1 и в G существует (m +1) -однородный d -базис. Теорема 4'. Пусть G – циклическая группа порядка pmqkrs и s< m< k . Если k > (m + s), то w(G) = (m +1)(s +1). Если k < (m + s), то w(G) > t, где , (k + m - s +1)(m + s - k) t = (m +1)(k - m +1) + ------------------------ , и в G существует k-однородная антицепь из t подгрупп. Заключение Указаны приложения этих результатов в теории групп. В связи с полученными результатами естественно поставить следующий Вопрос 3. Для всякого ли натурального числа n в D(n) существует t-однородный базис хотя бы одного t? Этот вопрос тесно связан со следующим вопросом. Вопрос 4. Пусть n е N \ 1 и n = PkР22 ■•■ Pk — каноническое разложение числа n . Найти натуральное число t, для которого уравнение x1 + x2 +... + xs = t при ограничениях x1 < 21, x2 < 22, ..., xs < 2s имеет наибольшее число решений в целых неотрицательных числах.
Список литературы О максимальных антицепях решеток делителей натуральных чисел некоторых видов
- Половицкий Я.Д. Ранг инцидентности//Алгебра и линейная оптимизация: тр. междунар. сем. Екатеринбург, 2002. С.184-186.
- Половицкий Я.Д. Группы, имеющие небольшие ранги инцидентности//Вестник Пермского университета. Сер. Математика. Механика. Информатика. 2003. Вып. 5. С.65-69.
- Биркгоф Г. Теория решеток. М.: Наука, 1984.564 с.
- Калужнин Л.А. Введение в общую алгебру. М.: Наука. 447 с.
- Conrad Engels. Sperner theory. Kembridge university press. 1997. 417 p.