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

В работах [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 { ⁿ 1 ,ⁿ 2 , . , n k }

  
  

  _–

  
  

  множество

  
  

{ mn 1 , mn ₂, . , mn_k } , ( 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 в произведение простых множителей (не обязательно различных). Тогда, как нетрудно видеть, цепь

• ¹    <  P 1 <  P 1 P 2 <  . <  P 1 P 2 . P_t — 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 ₂ e B , что b 1 | m (5) и m | b ₂ (6).

Доказательство. Так как B – базис D ( n ) , то множество { m , B } ^ B не является антицепью. Но В – антицепь, и поэтому существует b e B , что выполняется (3) или (4).

Если найдутся b 1 , b ₂ e B , что справедливы (5) и (6), то b ₁ | b ₂ , и, так как В – антицепь, 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 – антицепь в множестве Т всех подмножеств множества M_s , а равенство (13) описывает антицепи Т , состоящие из наибольшего числа элемен-

Г s 1

тов, т. е. базисы множества Т и w (T ) = C_s ^{L 2 J} .

Из теоремы Шпернера вытекает

Теорема 1. Пусть n = p 1 p ₂... p_s , где 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

следует, что X_m <  X t , то ф - изоморфизм у-множеств D ( n ) и Т , и потому ϕ переводит базис D ( n ) в базисы Т и w ( D ( n )) = w ( T ) , т.е. в силу замечания 2 справедливо (14).

Но базисы множества Т в теореме Шпернера описываются равенствами (13). Значит, в D(n) при четном s – единствен- ный базис, он является s -однородным и 2

Г - 1

w ( D ( n )) = C_s ^L2J.

Аналогично из теоремы Шпернера получаем справедливость утверждения теоремы 1 и для нечетного s . П

О ширине и базисах D ( p m q k )

Из доказательства теоремы 1 из [1], в которой рассматривались антицепи у-мно-жества всех подгрупп циклической группы порядка p^mq^k вытекает справедливость следующего утверждения:

Лемма 4. Ширина числа n = p^mq^k при 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 ( p^mq^k ) .

Лемма 5. В любой антицепи множества D(pmqk ) не могут содержаться пары чисел {t t m m-> ~t} p , q , pq1} и {p 1, q , p 2 q } (ибо одно из чисел каждой такой пары делит другие).

Теорема 2. Пусть n = pmqk и m sо > s 1 > , > > s + > > sm . (4)

Доказательство. В силу (1) множества из ( m + 1 ) чисел { s i | i = 1, m + 1 } (5), удовлетворяющих неравенствам (4), найдутся. Пусть (5) – любое такое множество. Составим с его помощью множество (3). Из неравенств (4) следует, что (3) – это антицепь. Но в числах (3) в качестве множителей встречаются всевозможные степени числа p , делящие n : это p ⁰, p ¹,... , p^m . В силу леммы 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 = p^mq^m , то D ( n ) имеет единственный базис – это стандартный базис { q^m , pq^{m - 1} ,, p^{m - 1} q , p^m } (см. определение 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 + s_m = t, т. е. t > m, а s₀= t< k, и выполняются неравенства (5). 0

Теорема 2 и ее следствия позволяют оценить, а в ряде случаев и найти ширину чисел вида p^mq^kr^s .

О ширине чисел вида pmqkrs

Лемма 6. Пусть n = hr^s (1), где (h, r) = 1 (2). Если S_j={h1 r^J, h₂r^J, .. ., h_tr^J} , где hi | h (i=1,t) - антицепь в D(n), то |Sj|< w(h) (3) и w(n) < w(h)(s +1) (4).

Доказательство. Так какh_ir^j | h_lr^j тогда и только тогда, когда hi | hl (i,l =1,t), то {h1,,h_t} - антицепь в D (h), и по определениям 8 и 6 t< w(h), т. е. выполняется (3).

Если В – любой базис D(n) , то для всех J = 0, s составим из его элементов попарно не пересекающиеся подмножества S_j из максимального числа элементов, множителем которых является r ^j при фиксированном j. Тогда s

B = U S _j ; отсюда и из (3) получаем

J=о ^J

|B| < w(h)(s +1), и справедливо (4). 0

Следствие. Если n = p^mq^kr^s, где k > m, то в обозначениях леммы 6 и S | < (m +1) и w(n) < (m +1)(s +1). Равенство |S_J | = (m +1) (4) имеет место тогда и только тогда, когда {h1^,• • •^,ht} (5) - базис D(p^mq^k).

Получается из леммы 6 при h = pmqk, ибо по теореме 2 w(h) = (m +1). Равенство (4) имеет место тогда и только тогда, когда t = m +1 = w (pmqk ),   т.е. (5)   - базис

D(p^mq^k).

Лемма 7. Пусть n = p^mq^mr^s, В - некоторый базис D(n) , S_j – множество всех чисел из В, которые делятся на r ^j , но не делятся на r^J+1 при фиксированном j. Тогда из антицепей Sj (j' =0,s) не более одной состоят из (m +1) чисел и w(n) < m (s +1) +1 (6).

Доказательство. Введем обозначение: h = p^m q^m . Предположим, что существуют i и J, что i ^ J , но |Si| = Sjl = m +1 (7). Тогда S = { hri,., hm+1 ri}       ^{(8) и}

Sj={t1 r^j,..., tm₊₁r^J} ⁽⁹⁾, где h_k, tk e D⁽h ) (10) k=1, m+1. Так как Si и Sj. - антицепи (как часть базиса В), то из (8) и (9) следует, что {h1,.,h,m+1} ⁽¹⁰⁾ и {tp., t_m+1} (11) - антицепи из D (h). Но они состоят из (m +1) чисел, а по теореме 2 w(h) = w(pmqm) = (m + 1). Значит, (10) и (11) – базисы D(h) .

Но по следствию 1 теоремы 2 D(h) имеет единственный базис, и потому (10) и (11) совпадают. В частности h1 = t_k для некоторого к. Но тогда h1 ri и h1 r^J' e B , что невозможно, ибо одно из этих чисел делит другое. Значит, для всех i , кроме быть может, одного, |Si| < m. Так как в силу леммы 6

мы 1 оно является антицепью. Теперь из (13) получаем, что В – базис D(n) , т. е. В – m -однородный базис.

Если m = 2, то в силу (13) w(n) < 5 (14). Но в G существует (m +1)-однородное множество R = { p²q, q²p, pqr, p²r, q²r} из 5 чисел. В силу (14) R- (m +1)-однородный базис D(n) , и потому выполняется (12) для m = 2.

Наконец, при m = 1 D (n) имеет базис {pq, pr, qr}. Он (m +1) -однородный и выполняется (12) и при m = 1. □

Следствие 2. Если n = p^mq^mr², то w (n) = 3 m +1 и в D (n) существует (m +1) -однородный базис.

Доказательство. Пусть m > 2. Рассмотрим множества

S0 ={ p^mq, p^m-1q²,..., pq^m } ,

• S1 ={ p^mr, p^m-1qr,., pq^m-1r, q^mr } и

• S2 = {pm-1 r2, pm-2qr2,., pqm-2r2, qm-1 r2}. Они различны, каждое из них (m +1) -однородное и |S1| = m+1, а |S0| = |S2| = m. То

гда S = S₀U S1 U S₂- (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 = p^mq^kr^s , где 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 = pmq^k (6). Пользуясь различными t -однородными базисами D(h) , полученными в следствии 2 теоремы 2, построим антицепи S _j указанного ниже вида (8) для максимального числа возможных при условиях теоремы значений j.

Пусть B = { q^m, 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 - это S₀, S1,., S_s (ибо s – максимальная степень r , на которую делится n). Отметим, что |Sj-| = m +1, Si П Sj =0 (ибо степени числа r в них разные) и S_j – 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 будет S_k-_m = r^k-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 r^k-(m-1)            - R r^k-(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) -однородная антицепь, то S_k-(_m-i) -k-однородная антицепь.

Итак, в пункте II мы дополнительно составили антицепи S_k-(m-1), S_k-(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) |S_J| = |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 = p^mq^mr^sus < 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(p^mq^mr) = 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 равна C_s^{L J}. Если число s четное, то G имеет единственный d -базис, и он является ^s -однородным. Если число s нечетное, 2

то G имеет всего два базиса - s—— -

• - s +1     _           .

однородный и - однородный.

Лемма 7'. Пусть G – циклическая группа порядка       pmqmrs .      Тогда w (G) < (m (s +1) +1).

Следствие 1'. Если G – циклическая группа порядка p^mq^mr , то w(G) = 2m +1 и при m > 2 в G существует m -однородный d -базис, а при m< 2 - (m +1) -однородный d -базис.

Следствие 2'. Если G – циклическая группа порядка pmqmr², то w(G) = 3m +1 и в G существует (m +1) -однородный d -базис.

Теорема 4'. Пусть G – циклическая группа порядка p^mq^kr^s и 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 имеет наибольшее число решений в целых неотрицательных числах.