close

Вход

Забыли?

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

- Вестник Пермского университета. Математика

код для вставкиСкачать
ВЕСТНИК ПЕРМСКОГО УНИВЕРСИТЕТА
Математика. Механика. Информатика
2014
Вып. 3 (26)
МАТЕМАТИКА
УДК 512.544.2+511.218
О максимальных антицепях решеток делителей
натуральных чисел некоторых видов
Я. Д. Половицкий, А. А. Волочков.
Пермский государственный национальный исследовательский университет
Россия, 614990, Пермь, ул. Букирева, 15
[email protected]; (342) 2 396 321
Для натуральных чисел n видов
p1 p 2  p k и p m q k r s , где p, q, r и pi , ( i  1, k ) –
различные простые числа, оценивается максимальное число элементов в антицепях множества D ( n ) всех делителей n , частично упорядоченного относительно делимости (ширина
w ( n ) множества D ( n ) ). Для ряда случаев эта ширина и антицепи из w ( n ) элементов
находятся. Указывается приложение этих результатов к теории групп.
Ключевые слова: натуральное число, делитель, ширина решетки, антицепь.
Введение
Вначале приведем некоторые понятия
из теории частично упорядоченных множеств
(в основном из [3]).
В работе используются следующие обозначения:
n | m – n делит m ( n, m – натуральные числа);
n | m – n не делит m ;
[a] – целая часть числа действительного
числа a ;
D ( n ) – множество всех делителей натурального числа n ;
– конец доказательства;
m n1 , n2 , , nk 
–
множество
В работах [1] и [2] Я.Д. Половицким начато рассмотрение вопроса о нахождении в
произвольной группе конечных подмножеств
попарно неинцидентных (не содержащихся
одна в другой) подгрупп, состоящих из максимального числа подгрупп, и числа составляющих их подгрупп. Как нетрудно видеть,
для конечных циклических групп эти вопросы
равносильны следующим вопросам о натуральных числах:
Вопрос 1. Для натурального числа
n  1 найти максимальное число делителей
n , ни один из которых не делит другой (этот
вопрос сформулирован Я.Д. Половицким в
статье [2]).
mn1 , mn2 , , mnk  ,  m, ni  N , i  1, k  .
Вначале приведем некоторые понятия
из теории частично упорядоченных множеств
(в основном из [3]).
Вопрос 2. Для натурального числа
n  1 найти подмножества множества D ( n ) ,
в каждом из которых ни одно из входящих в
него чисел не делит другое, состоящее из
наибольшего числа элементов.
Основные определения и некоторые
утверждения о D(n)
Определение 1. Частично упорядоченное
множество будем называть у-множеством.
© Половицкий Я. Д.,. Волочков А. А, 2014
5
Я. Д. Половицкий, А .А. Волочков
У-множество, в котором любые два элемента
сравнимы, называют цепью (см. [3]).
Определение 2. Если
a 1  a 2    a n 1  a n
– конечная цепь у-множества А, то ее длиной
называют число n1.
Определение 3. Точная верхняя грань
длин цепей у-множества А называется длиной
А и обозначается через l ( A) .
Рассмотрим множество D ( n ) всех делителей числа n. Если a , b  D ( n ) , то, полагая a  b тогда и только тогда, когда a | b ,
мы делаем D ( n ) у-множеством. Пусть
n  p1 p 2  p t (1) – разложение числа n в
произведение простых множителей (не обязательно различных). Тогда, как нетрудно видеть, цепь
Определение 6. Антицепь у-множества
Х, состоящая из наибольшего числа его элементов, называется базисом Х.
Определение 7 (см. [3]). Число элементов в базисе у-множества Х назовем шириной
Х и обозначим через w( X ) .
Введем понятие ширины натурального числа.
Определение 8. Ширину у-множества
D ( n ) назовем шириной числа n и обозначим
ее через w(n) (т. е. w(n)  w( D (n)) ).
В терминологии определений 8 и 6
сформулированные выше вопросы 1 и 2 принимают следующие виды:
Вопрос 1'. Для n  N \1 найти w(n) .
Вопрос 2'. Для n  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  D(n) \ B существует b  B , что
выполняется одно из соотношений: m | b (3)
или b | m (4), причем для m не могут сущест-
1  p1  p1 p2    p1 p2  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)  l  m  ;
вовать такие b1 , b2  B , что b1 | m
(5) и
m | b 2 (6).
Доказательство. Так как B – базис
D ( n ) , то множество m, B  B не является
антицепью. Но В – антицепь, и поэтому существует b  B , что выполняется (3) или (4).
Если найдутся b1 , b2  B , что справед-
2. Если m | n и l (n)  l (m) , то m  n ;
3. Если m  n и m | n , то l (m)  l (n) ;
ливы (5) и (6), то b1 | b2 , и, так как В – анти-
4. Если m  n и l ( n )  l ( m ) , то n | m и
следует, что m  b1 в противоречие с тем,
m | n.
Определение 5 (см. [3]). Антицепью
у-множества называется его подмножество, в
котором никакие два его элемента не сравнимы.
Введем понятие базиса у-множества.
что m B .
Лемма 3. Пусть В – t -однородный базис
D (n) и m  D(n) . Тогда l (m)  t (7) тогда и
только тогда, когда m  B . Если l (m)  t (8),
то m делится на некоторое число из В; если же
l (m)  t (9), то m делит некоторое число из В.
цепь, b1  b 2 . Но тогда из b1 | m и m | b1
6
О максимальных антицепях решеток делителей натуральных чисел некоторых видов
__________________________________________________________________________
Доказательство. В силу леммы 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).
s
 
гда w(n)  Cs 2  (14). Если число s четное, то
D ( n ) имеет единственный базис, являющийs
ся
-однородным. Если s нечетное, то в
2
D ( n ) существуют всего два базиса –
однородный и
s 1
2
s 1
-однородный.
2
Доказательство. Отметим, что из вида
n следует, что m  D(n) тогда и только тогда, когда m  p j1 p j2  p jk , где k  s и
Рассмотрим отображение

у-множества D ( n ) в множество Т всех под-
ji  M s .
множеств множества M s  1, 2, , s , зада-
Ширина и базисы D (n) для чисел n,
не делящихся на квадраты простых
чисел
ваемое так:  ( m)  Х m   j1 , j2 , , jk  . Нетрудно видеть, что  – биекция D ( n ) на Т.
Так как, очевидно, при m, t  D(n) из m | t
Для таких чисел решение вопросов 1' и
2' можно получить из следующей хорошо известной теоремы:
Теорема Шпернера (см. [5]). Пусть s
– положительное целое число, F– множество
следует, что X m  X t , то  – изоморфизм
у-множеств D ( n ) и Т, и потому  переводит
базис D ( n ) в базисы Т и w ( D ( n ))  w (T ) ,
т.е. в силу замечания 2 справедливо (14).
Но базисы множества Т в теореме
Шпернера описываются равенствами (13).
Значит, в D ( n ) при четном s – единственs
ный базис, он является
-однородным и
2
подмножеств множества M s  1,2,, s таких, что никакой элемент из F не содержится
ни в каком другом элементе из F, то есть для
любых X , Y  F имеем X  Y . Тогда
F C
тогда
s
 2 
s
s
 
(12). Равенство в (12) имеет место
и
только
тогда,
w( D ( n))  C s 2  .
когда
Аналогично из теоремы Шпернера получаем справедливость утверждения теоремы
1 и для нечетного s .
s
F  {X  M s :| X | } при четном s и
2
s 
F  {X  M s :| X |
} при нечетном s ,
2
где  {1,1} (13).
m
k
О ширине и базисах D ( p q )
Из доказательства теоремы 1 из [1], в
которой рассматривались антицепи у-множества всех подгрупп циклической группы
порядка p m q k вытекает справедливость следующего утверждения:
Лемма 4. Ширина числа n  p m q k при
m  k равна ( m  1) . Одним из базисов D ( n )
Замечание 2. Очевидно, что F – антицепь в множестве Т всех подмножеств множества M s , а равенство (13) описывает антицепи
Т, состоящие из наибольшего числа элеменs
2
 
s
тов, т. е. базисы множества Т и w(T )  C
.


является q m , pq m 1 , 
, p m1q, p m .
Из теоремы Шпернера вытекает
Теорема 1. Пусть n  p1 p 2  p s , где
Определение 10. Указанный в лемме 4
базис у-множества D ( p m q k ) назовем
стандартным базисом.
p i – различные простые числа (i  1, s) . То-
7
Я. Д. Половицкий, А .А. Волочков
Отметим, что стандартный базис является m -однородным. Ниже (в теореме 2) будет передоказана лемма 4 и найдены все базисы D ( p m q k ) .
Лемма 5. В любой антицепи множества
D ( p m q k ) не могут содержаться пары чисел
p ,q , p q  и p
t
l
t
l1
m1
однородный
q , pq
t
q
s0
, q t , p m2 q t  (ибо одно из
, pq s1 , 
, p m q sm

(3), где

где h i | h

Пусть
(i 1, t) – антицепь в D ( n ) , то
Доказательство. Так как hi r j | hl r j тогда и только тогда, когда h i | h l (i,l 1,t) , то
, ht 
h1 , 
– антицепь в D ( h ) , и по определе-
ниям 8 и 6 t  w(h) , т. е. выполняется (3).
Если В – любой базис D ( n ) , то для всех
j  0, s составим из его элементов попарно не
пересекающиеся подмножества S j из максимального числа элементов, множителем которых является r j при фиксированном j . Тогда
s
няются неравенства (4).
Следствие 1. Если n  p m q m , то D ( n )
имеет единственный базис – это стандартный
q
6.
S j  w ( h ) (3) и w ( n )  w ( h )( s  1) (4).
si  si 1 для всех i  1, m 1, и потому выпол-
m
B (6), где В –
n  hr s (1), где
j
j
j
( h , r )  1 (2). Если S j  h1r , h2 r , , ht r  ,
Лемма
большего числа элементов в D ( n ) быть не может, и потому (3) – базис D ( n ) . Так как в нем
( m  1) чисел, то справедливо равенство (2).
Обратно, если В – произвольный базис
D ( n ) , то в силу (2) он состоит из ( m  1) чисел и по лемме 5 все степени числа p в них
разные, т. е. В – это множество чисел (3). Так
как piqsi | pi1qsi 1 (по определению базиса), то
m 1
это
О ширине чисел вида p m q k r s
p 0 , p 1 ,  , p m . В силу леммы 5 антицепей из
m 1
q
–
t m
Теорема 2 и ее следствия позволяют оценить, а в ряде случаев и найти ширину чисел
вида p m q k r s .
творяющих неравенствам (4), найдутся. Пусть
(5) – любое такое множество. Составим с его
помощью множество (3). Из неравенств (4)
следует, что (3) – это антицепь. Но в числах
(3) в качестве множителей встречаются всевозможные степени числа p , делящие n : это
m
, , p q
t m
s0  t  k , и выполняются неравенства (5).
si –
неотрицательные целые числа, удовлетворяющие
неравенствам
k  s 0  s1    s i  s i  1    s m . (4)
Доказательство. В силу (1) множества
из  m 1 чисел si | i  1, m  1 (5), удовле-

базис
m
стандартный базис D ( n ) . Для других t в
D ( n ) t -однородных базисов нет.
Доказательство. В силу теоремы 2
множество (6) является базисом D ( n ) . По
определению 9 он является t -однородным.
Очевидно, что он – единственный t -однородный базис для данного t . С другой стороны,
если базис (3) множества D ( n ) t -однородный, то m  s m  t , т. е. t  m , а
чисел каждой такой пары делит другие).
Теорема 2. Пусть n  p m q k и m  k
(1). Тогда w ( n )  m  1 (2) и все базисы умножества D ( n ) исчерпываются множествами чисел
t 1
B   Sj
; отсюда и из (3) получаем
j 0
B  w(h)( s  1) , и справедливо (4).
(см. определе-
Следствие. Если n  p m q k r s , где k  m ,
ние 10).
Действительно, при k  m множество из
( m  1) чисел si , удовлетворяющих неравенствам (4), единственно – это числа
m , m  1,  , 2,1, 0 .
то в обозначениях леммы 6 и S j  ( m  1) и
Следствие 2. Если n  p m q k и m  k ,
то в D ( n ) для каждого целого t , такого, что
m  t  k (5), существует единственный t -
Получается из леммы 6 при h  p m q k ,
ибо по теореме 2 w ( h )  ( m  1) . Равенство
(4) имеет место тогда и только тогда, когда
базис
, pq
,
,p
q, p
w(n)  (m  1)(s  1) . Равенство S j  (m  1)
(4) имеет место тогда и только тогда, когда
h1,, ht  (5) – базис D ( p
8
m
qk ) .
О максимальных антицепях решеток делителей натуральных чисел некоторых видов
__________________________________________________________________________
t  m  1  w( p m q k ) ,
D( p mq k ) .
т.е.
(5)
–
мы 1 оно является антицепью. Теперь из (13)
получаем, что В – базис D ( n ) , т. е. В –
m -однородный базис.
Если m  2 , то в силу (13) w ( n )  5
(14). Но в G существует ( m  1) -однородное
базис
Лемма 7. Пусть n  p m q m r s , В – некоторый базис D ( n ) , S j – множество всех чи-

сел из В, которые делятся на r j , но не делятся на r j 1 при фиксированном j . Тогда из
из ( m  1) чисел и w ( n )  m ( s  1)  1 (6).
Доказательство. Введем обозначение:
h  p m q m . Предположим, что существуют
m 2.
Наконец, при m  1 D ( n ) имеет базис
 pq, pr, qr . Он
i и j , что i  j , но Si  S j  m  1 (7). Тогда
Si  h1r , , hm1r
i

(8)
и
(10) k 1, m1. Так как Si и S j - антицепи (как
Доказательство. Пусть
смотрим множества
часть базиса В), то из (8) и (9) следует, что
m  2 . Рас-
S0   p m q , p m 1q 2 ,  , pq m  ,
(10) и t1,, tm1 (11) – антицепи
S1   p m r , p m 1qr , , pq m 1r , q m r и
из D ( h ) . Но они состоят из ( m  1) чисел, а
по теореме 2 w ( h )  w ( p m q m )  ( m  1) . Значит, (10) и (11) – базисы D ( h ) .
Но по следствию 1 теоремы 2 D ( h )
имеет единственный базис, и потому (10) и
(11) совпадают. В частности h1  t k для неi
( m  1) -однородный и выпол-
няется (12) и при m  1 .
Следствие 2. Если n  p m q m r 2 , то
и в
существует
w ( n )  3m  1
D (n )
( m  1) -однородный базис.
S j  t1r j , , tm1r j  (9), где h k , t k  D ( h )
h1,, hm1
из 5
чисел. В силу (14) R– ( m  1) -однородный
базис D ( n ) , и потому выполняется (12) для
антицепей S j ( j  0, s) не более одной состоят
i

множество R  p 2 q, q 2 p, pqr , p 2 r , q 2 r
S 2   p m1r 2 , p m 2 qr 2 ,  , pq m 2r 2 , q m 1r 2  .
Они различны, каждое из них
( m  1) -
однородное и S1  m 1, а S0  S2  m . Тогда S  S0  S1  S2
антицепь
(по
– ( m  1) -однородная
лемме
1)
из
2m  (m  1)  3m  1 элементов. Но при условиях следствия 2 имеем s  2 , и из леммы
7 получаем: w(n)  (3m  1) . Значит, S– базис
D (n ) .
j
которого k . Но тогда h1r и h1r  B , что невозможно, ибо одно из этих чисел делит другое. Значит, для всех i , кроме быть может,
одного, Si  m . Так как в силу леммы 6
s
Si  w(h)  m  1 для всех i , B   Si и
то
Если m  1 , то есть n  pqr 2 , то по
лемме
7
и
потому
w( n)  4 ,
B  sm  (m  1)  m( s  1)  1 , т. е. выполня-
B   pq, pr , qr , r 2  – 2-однородный базис
i0
Si  S j  
при
i  j,
D ( n ) . Значит, w ( n )  4 , и потому утверждение следствия 2 справедливо и для m  1 .
Теорема 4. Пусть n  p m q k r 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)
(5)
l  ( m  1)( k  m  1) 
2
и в D ( n ) существует k -однородная антицепь
из l чисел.
ется неравенство (6).
m
m
Следствие 1. Если n  p q r , то
w( n )  2 m  1 (12) и при m  2 в D ( n ) существует m -однородный базис, а при m  1 и
m  2 – ( m  1) -однородный базис.
Доказательство. Из леммы 7 при s  1
получаем: w ( n )  (2 m  1) (13).
Пусть m  2 . Тогда существует антицепь из (2 m  1) чисел – например,
B qm,qm1p,, qpm1, pm, qm1r,qm2 pr,,qpm2r, pm1r
– это m-однородное множество и в силу лем-
9
Я. Д. Половицкий, А .А. Волочков
Доказательство. Введем обозначение:
(6).
Пользуясь
различными
h  p qk
t -однородными базисами D ( h ) , полученными в следствии 2 теоремы 2, построим антицепи S j указанного ниже вида (8) для мак-
Рассмотрим
Bi   p
m
mi
,p
m  ( i 1)
множества
q, , pq
m  ( i 1)
,q
mi

для
i  1, m 1. Bi – (m  i) -однородная антицепь и
Bi  (m  i )  1
симального числа возможных при условиях
теоремы значений j .
S k ( m1)  B1r
k  ( m 1)
(9).
, S k ( m 2)  B2 r
Получаем
k  ( m  2)
и так
(если
далее. Чтобы составление таких антицепей
закончилось на множестве S s на 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). Так как
S k ( mi )  Bi r k ( mi )
(13) и
Bi  ( mi )
–
k  ( m  j )  0 и j  s ). Составление S j за-
(m  i) -однородная антицепь, то S k ( mi ) –
кончится таким множеством Sl , что должно
выполняться
одно
из
условий:
I.
k -однородная антицепь.
B  q m , q m 1 p , , pq m 1 , p m  –
Пусть
стандартный базис D ( h ) . Тогда по следствию 2 теоремы 2 для всех t , таких что
m  t  k (7), существуют t -однородные базисы D ( h ) вида qt m B .
S0  q k m B .
Составим
Если
k  ( m 1)
rB и
k  ( m  1)  0 , то полагаем S1  q
так
S j  q k ( m j ) r j B
далее:
(8)
Итак, в пункте II мы дополнительно составили антицепи S k ( m1) , S k  ( m 2) ,  , S s .
l  s
l  s
или II. 
.

k  (m  l )  0
k  (m  l )  0
Рассмотрим каждый из этих случаев.
I. Пусть выполняется условие I. Оно
равносильно неравенству k  ( m  s )  0 , т. е.
условию (2). При его выполнении будут построены все возможные S j – это S 0 , S1 , , S s
(ибо s – максимальная степень r , на которую
делится n). Отметим, что
S j  m 1,
Si  S j   (ибо степени числа
r
В силу (9) и (13) S k ( mi )  (m  i )  1
(14), i  1, ( s  m)  k . Всего вместе с составленными в начале доказательства антицепями
S j , j  0, k  m мы составили k -однородные
антицепи S 0 , S1 , , Sk  m , S k m 1 ,  , S s . Они
попарно не пересекаются (ибо содержат различные степени числа r ), и потому множестs
во S   S j (15) – k -однородная антицепь.
в них раз-
j 0
ные) и S j – k -однородные множества. По-
Так как в силу (8)
s
этому
S   Sj
состоит из ( m  1)( s  1)
S j  B  (m  1) для
j  0, k  m , то отсюда из (14) и (15) получаем:
j 0
S  (m  1)( k  m  1)  [( m  1)  1  ( m  2) 
k -однородных чисел и является по лемме 1
антицепью. Но в силу следствия леммы 6
–
w ( n )  ( m  1)( s  1) , и поэтому S
k -однородный базис D ( n ) . Доказана первая
часть теоремы 4.
II.
Пусть выполняется условие II.
Тогда l  (k  m)  s , т. е. выполняется (4).
Последний из составленных выше антицепей
S j будет S k m  r k m B . Больше антицепей
1    ( m  t )  1]  (m  1)( k  m  1) 
( m  1)  ( m  t )
 t )  ( m  1)( k  m  1) 
2
( m  1)  ( m  t )
 t (1 
)  ( m  1)( k  m  1) 
2
 (t 1 
2m  s  m  k  1

2
( s  m  k )( m  k  s  1)
 ( m  1)( k  m  1) 
2
(мы использовали равенство (12)). Так как
w(n)  S , то этим доказано неравенство (5).
 (s  m  k )
типа S j из ( m  1) чисел составить нельзя.
Но подобные антицепи можно составить из
меньшего числа элементов.
10
О максимальных антицепях решеток делителей натуральных чисел некоторых видов
__________________________________________________________________________
Лемма 8. d -ширина циклической
группы порядка n равна ширине числа n .
Из этой леммы из доказанных выше
теорем 1 и 4 и леммы 7 вытекают следующие
теоретико-групповые утверждения:
Теорема 1. Пусть G – циклическая
Следствие. Если n  p m q m r s и s  m ,
s ( s  1)
то m ( s  1)  1  w ( n )  1  m ( s  1) 
.
2
Доказательство. При k  m из теоремы
4 получаем
s (2m  s  1)

2
s ( s  1)
(m  1)  ms 

2
s ( s  1)
m( s  1)  1 
.
2
группа порядка n  p1 p2  ps , где pi (i  1, s )
w(n)  (m  1) 
– различные простые числа. Тогда d -ширина
группы G равна C
s
 2
 
s
. Если число s четное,
то G имеет единственный d -базис, и он являs
ется
-однородным. Если число s нечетное,
2
s 1
то G имеет всего два базиса –
2
s 1
однородный и
- однородный.
2
Лемма 7'. Пусть G – циклическая группа
порядка
pmqmr s .
Тогда
w (G )  ( m ( s  1)  1) .
Следствие 1'. Если G – циклическая
группа порядка p m q m r , то w ( G )  2 m  1 и
при m  2 в G существует m -однородный
d -базис, а при m  2 – ( m  1) -однородный
d -базис.
Следствие 2'. Если G – циклическая
группа порядка p m q m r 2 , то w ( G )  3 m  1 и
в
G
существует
( m  1) -однородный
d -базис.
Теорема 4'. Пусть G – циклическая
группа порядка p m q k r 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) 
2
,
и в G существует k -однородная антицепь из t
подгрупп.
Неравенство m ( s  1)  1  w( n) доказано в
лемме 7.
Замечание 3. При s  1 и m  2 из
следствия
теоремы
4
получаем
m m
w( p q r )  1  2m , как и установлено в
следствии 1 леммы 7. При других s w(n)
вычисляется в следствии теоремы 4 с точноs ( s  1)
стью до слагаемого
, и потому более
2
точным получается при малых 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 вытекает справедливость следующего утверждения:
Заключение
В настоящей работе найдена ширина натуральных чисел видов
pmqk , pmqmr, p mq mr 2, p mq kr s
при k  ( m  s ) , p1 p2 pl , и для каждого из
этих
случаев
в
находились
D (n )
t -однородные базисы для некоторых t .
11
Я. Д. Половицкий, А .А. Волочков
Указаны приложения этих результатов в теории групп.
В связи с полученными результатами
естественно поставить следующий
наибольшее число решений в целых неотрицательных числах.
Список литературы
1. Половицкий Я.Д. Ранг инцидентности //
Алгебра и линейная оптимизация: тр. междунар. сем. Екатеринбург, 2002. С.184–186.
2. Половицкий Я.Д. Группы, имеющие небольшие ранги инцидентности // Вестник
Пермского университета. Сер. Математика.
Механика. Информатика. 2003. Вып. 5.
С.65–69.
3. Биркгоф Г. Теория решеток. М.: Наука,
1984. 564 с.
4. Калужнин Л.А. Введение в общую алгебру.
М.: Наука. 447 с.
5. Conrad Engels. Sperner theory. Kembridge
university press. 1997. 417 p.
Вопрос 3. Для всякого ли натурального
числа n в D ( n ) существует t -однородный
базис хотя бы одного t ?
Этот вопрос тесно связан со следующим
вопросом.
4.
Пусть
и
n  N \1
n  p p  p – каноническое разложение
числа n . Найти натуральное число t , для которого уравнение x1  x2    xs  t при огВопрос
k1
1
k2
2
ks
s
раничениях x1  k1 , x2  k2 , …, xs  k s имеет
About maximal antichains of gratings divisors
of natural numbers
Ja. D. Polovitsky, A. A. Volochkov
Perm State University, Russia, 614990, Perm, Bukireva st., 15
[email protected]; (342) 2 396 321
For the natural numbers of aspects p1 p 2  p k and p m q k r s , where p, q, r and p i , i  1, n are
different primer numbers, maximal quantity of elements in antichains of the set D ( n ) of different divisors n, partly-ordered regarding divisions (the width w ( n ) of the set D ( n ) ) estimated
in this paper. For the same case w ( n ) and antichains from w ( n ) elements are found. These results are applied to the theory of group.
Key words: natural number; divisor; width of the grating; antichain.
12
1/--страниц
Пожаловаться на содержимое документа