Raqamli kutubxona Kibernetikadan matematik masalalar

§ 2, 6-bandning 5-bandidan va kodlash nazariyasi natijalaridan foydalanadi
ē o'lchovli kubning uchlarini Hamming birligi sharlari bilan qoplash. Ga binoan
5-tasdiq, agar funktsiya / ni uning birligi bilan ajratish mumkin bo'lsa
cho'qqilari shunday qilib, uning barcha birlik uchlari sharlar ichida bo'lsin
radiusi 1 ning tanlangan uchlarida markazlashtirilgan, keyin t (f) ^ k. Uchun
soddaligi uchun biz birinchi navbatda n = 2T - 1 va mavjud bo'lgan holatni ko'rib chiqamiz
mukammal Hamming kodi (qarang [78]), ya'ni 2n / (n + 1) cho'qqilar to'plami
shunday qilib, ularda markazlari bo'lgan birlik radiusli sharlar kesishmaydi va
butun kubni yoping. O'zgartirish orqali koddan olingan to'plam
uning barcha cho'qqilarining t-x koordinatalarining qarama-qarshi tomonidagi qiymatlari deyiladi
kodning i-kosetasi, 1 sinf. Shunday qilib, kubning istalgan cho'qqisi biriga tushadi
/ r + 1 kosets, va agar biz i-ro ixtiyoriy cho'qqisini ko'rib chiqsak
sinf, keyin uning n qo'shnilari orasida barcha tabaqalarning vakillari bo'ladi,
i-dan tashqari.
Endi biz n + 1 kosetlardan ixtiyoriy [log n] tanlaymiz
sinflar, ularni tuzatish, va tasodifiy Mantiqiy funktsiyasi uchun sifatida
to'plarning markazlari, biz uning ichiga tushadigan birlik uchlarini olamiz
tanlangan sinflar. Ularning sonining matematik kutilishi [log n] 2n ~ ll (n + 1),
va katta sonlar qonuniga ko'ra, asimptotik tarzda deyarli har doim ularning soni shunchalik ko'p bo'ladi va
bo'ladi. Funksiyaga tegishli boʻlmagan har bir birlik choʻqqisi
tanlanganlardan [log n] uchlari bilan oʻralgan tanlangan kosetlar
qo'shni sinflar, shuning uchun birlik sonini kutish
sharlar bilan qoplanmagan uchlari teng
G (2P - 2 "[log p] / (p fl)) 2 - [, ogn] ~ o (| log p] 2" "70 + 1)),
va har bir ochilgan cho'qqi uchun alohida yozish mumkin
tengsizliklar sonini asimptotik oshirmasdan tengsizlik.
Umumiy holatda, qachon n F 2G - 1 va mukammal kod emas
mavjud bo'lsa, siz Kabatianskiy va Panchenko natijalaridan foydalanishingiz mumkin [21,
22], har qanday ē -> °° uchun mavjud ekanligini ko'rsatgan
asimptotik ravishda 2n!n shardan iborat boʻlgan ķ oʻlchamli kubning qoplamasi. Hozir
qo'shni sinflar bir xil tuzilishga ega emas va mumkin
bir-biriga mos kelishi, shuning uchun zarur munosabatlarning isboti
Matematik taxminlarni tasodifiy yordamida amalga oshirish eng oson
[log n] sinflarini tanlash. Bu teoremani isbotlashni tugatadi.
4. Monoton funksiyalarni ifodalash. Ko'p vazifalarda
chiziqli mantiqiy dasturlash, (32) koeffitsientlari ac
chiziqli tengsizliklar manfiy emas. Shuning uchun ular belgilaydigan mantiqiy funktsiya

47-bet

50
Yu A, Zuev
tion monotondir. Bu qiziqish ortishi bilan izohlanadi
monoton funksiyalarning chegaraviy tasvirlari. Ularni o'rganishga o'tsak,
birinchi navbatda, ruxsat etilgan o'zboshimchalik bilan maksimal miqdorga e'tibor bering
monoton funktsiyaning chegara to'plami har doim belgilanishi mumkin
manfiy bo'lmagan koeffitsientlar bilan tengsizlik. Haqiqatan ham, agar
ruxsat etilgan chegara to'plami tengsizlik bilan beriladi
manfiy og'irlik koeffitsientlari mavjud, keyin ularni nol bilan almashtiring,
biz asl chegarani o'z ichiga olgan ruxsat etilgan chegara to'plamini ham olamiz.
Muammolardagi tengsizliklarni yig'ish imkoniyatlarini o'rganish
(32) ga o'xshash, pol qiymatlari uchun taxminlarni olishni rag'batlantirdi
monoton funksiyalar sinfidagi raqamlar. Pastki birliklar sonidan
monoton funksiyalar uchun ([n ”2j) dan oshmaydi va 1-taklifdan cp
Bundan kelib chiqadiki, monotonlar sinfida chegara raqamlarining qiymatlari ishlaydi
dan oshmasligi kerak [[n / 2]) 9 ^ bundan tashqari "([J / 2]) pastroq bo'lgan funktsiyalar
birliklar chegara hisoblanadi, shuning uchun chegara qiymatlari emas
bu qiymatga erishing. Bundan tashqari, Hammer, Ibaraki va Pild tomonidan [64]
chegarasi bo'lgan ph (# 1, ..., xn) monoton funksiyasiga misol tuzildi.
soni t (cp) ^ ([w / 2]) / w * Keyinchalik xuddi shu misol muallif tomonidan qurilgan
va o'sha paytda ish bilan tanish bo'lmagan Trishin [8] [64]. Uning
qurilishi quyidagicha.
rc o'lchovli kubning o'rta qatlamida, bilan cho'qqilar to'plami
cho'qqilar orasidagi minimal masofa 4 ga teng (muvozanat
kod), va ph funktsiyaning quyi birliklari to'plami sifatida qabul qilinadi.
ph funktsiyaning ikkita pastki birligi bo'lishi mumkin emasligini ko'rsatish oson
nol uchlari kesilmasdan bitta tengsizlik bilan kesiladi
funktsiyalari (2-bandning 3-taklifining analogi, qatlam uchun 4-band). Shuning uchun £ (ph)
kodning kardinalligi bilan mos keladi. Muvozanat kodining mavjudligi
quvvat ([J / 2]) | Minimal masofa 4 bo'lgan Vtni ko'rsatish oson
kodlash nazariyasidan yaxshi ma'lum bo'lgan quyidagi fikrlashdan foydalanish. Uchun
har qanday /, 0 ^ ^ n - 1, o'rta qatlamning cho'qqilari to'plami, koordinatalari
Bu tenglamani qanoatlantiradi
NS
2 ixi == j (mod n),
i = i
shunday koddir. Birgalikda bu n kodlar o'rta qatlamni beradi.
Shuning uchun ular orasida quvvat kodi ([n / 2]) / "•
Yuqoridagi mulohazalar bizga quyidagi taxminlarni berishga imkon berdi
monoton funksiyalar sinfidagi chegara sonining maksimal qiymati
(["/ 2]) /" Keyinchalik, [10, 13] da muallif buni ko'rsatgan
maksimal t (ph) ^% n / n, n
Bu erda% n - raqamlangan kubning uchlari to'plamining maksimal kardinalligi,
qaysi juftlik bilan birligi Hamming sharlari bilan qoplangan bo'lishi mumkin
beqiyos markazlar. Hatto arzimas pastki chegaradan foydalanish
X „sS2n (33) dagi yuqori chegarani sezilarli darajada kamaytirishga imkon berdi. muallif
aniqroq yordami bilan uning yanada qisqarishi hisoblangan
% n ni taxmin qilish, % "= ^ (([n / 2])) imkoniyatini istisno qilmasdan

48-bet

MATQIY FUNKSIYALARNING EOS FUNKSIYALARI VA BOSHQA FUNKSIYALARI.
bu max £ (ph) uchun asimptotiklarning tartibini darhol o'rnatishga imkon berdi.
% n ni mustaqil kombinatsion masala sifatida baholash masalasi
1983-1985 yillarda seminar va konferentsiyalarda u tomonidan bir necha bor taklif qilingan
SSSRda va [10] da ochiq muammo sifatida shakllantirilgan. U
professor G. Buroshning seminaridagi nutqining mavzusi ham bo‘ldi
1985 yil aprel oyida Rostok universitetida
“^ (([J / 2])) VSK0Re gipotezasi Kospanov tomonidan rad etilgan.
[26], u ergashgan go'zal misolni qurgan
% n f * - n ~ ll (l2P. Bu taxmin tartibni to'g'ri aks ettirganga o'xshaydi.
o'sish% n, lekin 1988 yil boshida SSSRda shaklida
Dastlabki nashrni Furedi, Kan va Kleitman oldi
[59], unda Xn> 0,1 • 2P ekanligi ko'rsatilgan. Bu ajoyib
natija ilgari ishlab chiqilgan texnika yordamida olingan
Suyak [27], kuchning yana bir ishonchli namoyishi edi
kombinatsion tahlilda ehtimollik usullari va rag'batlantirilgan yangi
sa'y-harakatlari. Tez orada Chuxrov [41] pastki bahoni 0,2 x 2P ga keltirdi,
va Kostochka [28, 29] birinchi asimptotik jihatdan farqlanuvchini olishga muvaffaq bo'ldi.
2n dan yuqori baho% n <0,9987 • 2n va shu bilan gipotezani isbotlang
Furedi, Kan va Kleytman bu% n asimptotik emas
2p ga to'g'ri keladi.
Chegara raqamlarining ekstremal qiymatlari bilan bir qatorda,
ularning tipik qiymatlari. Muallif va Trishin [9] buni uchun ko'rsatdi
deyarli barcha monoton funktsiyalarning chegara raqamlari
t (cp)> 2n / n2 va muallifning Linkin bilan birgalikdagi ishida [11]
sezilarli darajada mustahkamlandi. Korshunov tomonidan kashf etilgan strukturadan foydalanish [24]
deyarli barcha monoton funktsiyalari va yanada nozik tadqiqot usullari,
[11] da deyarli barcha monoton funksiyalar uchun ekanligi aniqlandi
Shunday qilib, [8, 64] da tuzilgan misol aniqlandi.
istisno emas, balki qoidadir. Tartib masalasi
monoton funksiyalar sinfidagi chegara sonining maksimal qiymati
ochiq qoladi. Gipoteza hali ham isbotlanmagan yoki rad etilmagan
muallif [10]:
Keling, (34) va (35) baholarning isbotiga o'tamiz. Ular qiladi
4-bandning 3-bandida allaqachon ishlatilgan 7-bayonotga tayaning, Kabatian natijasi
Skogo va Panchenko kubni qoplash imkoniyati haqida (1 + o (1)) 27! / ^
birlik sharlari, shuningdek, dan kelib chiqadigan quyidagi lemmaga
muallifning G.A bilan muammoni muhokama qilish.
uning aniq formulasi tegishli. Tegishli havola bilan birinchi marta u
[13] da nashr etilgan.
Lemma 3. Q ^ {0, 1} n cho‘qqilarning ixtiyoriy to‘plami bo‘lsin.
n o'lchamli kub, H - kubni qoplagan birlik sharlar to'plami.
Keyin kubni birlik sharlar bilan qoplash mavjud bo'lib, unda ichkariga kiradi
Q to'plamida ko'pi bilan \ H \ • \ Q \ / 2n to'p markazlari mavjud.
Isbot. Olingan 2P qoplamalarni ko'rib chiqing {H + a}
dan siljishlar bo'yicha (mod 2) barcha mumkin bo'lgan vektorlar bo'yicha a ^ {0, 1} n. Bularni hisobga olgan holda
siljishlar tasodifiy va teng ehtimolli va matematik hisoblash
Q ga tushadigan markazlar sonini kutsak, biz unga teng ekanligini olamiz
1 (D • \ H \ / 2n. Lemma isbotlangan.
Endi taxminni isbotlaymiz (34).

49-bet

52
Yu. A. Zuev
27-teorema [10, 13]. In chegara raqamining maksimal qiymati
monoton funksiyalar sinfi asimptotik ravishda% Jn dan oshmaydi, bu erda
Xp - Hammingning birlik sharlarini birlashtirishning maksimal quvvati
juftlik bilan taqqoslanmaydigan markazlar bilan.
Isbot. cp ixtiyoriy monoton bo'lsin
funktsiya, H - kubni qoplaydigan birlik sharlar to'plami, \ H \ =
= (1 + o (1)) 2n / 2. Q to'plami sifatida biz birlashmani olamiz
ph funktsiyasining pastki birliklarida markazlari bo'lgan birlik sharlari. Lemma 3 tomonidan
Q to'plamida kubni birlik sharlar bilan qoplash mavjud
endi | # | • \ Q \ / 2n <% Jn markazlari. Ushbu markazlar bilan to'plar qoplaydi
barcha pastki birliklar ph, va quyi birliklar uchun 7-taklifga muvofiq
har bir to'pda bitta chiziqli tengsizlik etarli. Teorema
isbotlangan.
Endi biz taxminiy dalilga (36) murojaat qilamiz
monoton funktsiyalarning chegara raqamlari qiymatlari. Korshunovning yozishicha [24].
n o‘zgaruvchining deyarli barcha monoton funksiyalari quyi birliklarga ega
faqat uchta o'rta qatlamda x, m - 1 va m + 1, bu erda n teng uchun x = n / 2
va n = [n / 2] yoki n =] n / 2 [n toq bo'lganda. Bunday holda, lg qatlamida mavjud
x - 1 va x + 1 qatlamlaridagi birliklar 2n / 2 dan oshmaydi, ya'ni bu
lg qatlamidagilar sonining ahamiyatsiz qismi.
Oddiy (sinf chegarasi qiymatini) o'rganayotganda
monoton funktsiyalar uchun quyidagi ehtimollik modeli qo'llaniladi
dan olingan deyarli barcha monoton funktsiyalar to'plamini yaratish
muallif A. A. Sapozhenko bilan munozaralardan. Buni oqlash mumkin
[37] dan 1-teoremadan foydalanib.
Dastlab kubning barcha uchlari nolga teng deb hisoblanadi. Keyin qismlar
uchta o'rta qatlamdagi cho'qqilarga birlik qiymatlari beriladi
quyidagi qoida. Birinchidan, qatlamning uchlari mustaqildir
1/2 ehtimoliga 1 qiymati beriladi. Keyin n + 1 qatlamida biz tanlaymiz
x qavatdagi birlik cho'qqilarini qoplamagan cho'qqilar va bilan
1/2 ehtimollik bilan ularga 1 qiymati beriladi. Va nihoyat, qatlamda n = 1
m qatlamda ularni qoplagan barcha uchlari bilan cho'qqilarni tanlang
yagona va 1/2 ehtimollik bilan ularga 1 qiymati beriladi. Bunda
tasodifiy hosil qilish jarayoni tugaydi va keyin funktsiya
monotonlik bilan belgilanadi, ya'ni barcha cho'qqilarda, katta cho'qqilarda,
ga teng deb hisoblanadigan yagona qiymatlar berilgan
birlik.
Qatlamlarning uchlari lg + 1 va lg - 1 bo'lib, ular tasodifiy jarayonda
yumurtlama 1 qiymati bilan belgilandi, pastki bo'lishi kerak
funktsiya birliklari. Pastroq bo'lganlar sonining kutilishi
2p / 2 dan kam. Bu n - 1 qatlam uchun ham amal qiladi.
Bu deyarli barcha monotonni yaratish uchun ehtimollik modeli
funktsiyalari § 4, 3-bandda ishlatiladigan usullarga o'xshash usullardan foydalanishga imkon beradi,
sinfdagi chegara sonlarining tipik qiymatlarining asimptotikasini baholang
monoton funktsiyalari. 26-teoremani isbotlashdagi roli
butun kubga tegishli edi, endi uning o'rta qatlamiga o'tadi. Shunung uchun
ostona to'plamlari bilan birga, pol
qatlam to'plamlari, ya'ni uning quyi to'plamlari,
qatlamdagi ularning to‘ldiruvchilaridan giperplan orqali uzib qo‘yilishi mumkin.
Markaz, radius va diametr tushunchalari § 2, 6-bandda kiritilgan
chegara to'plamlari hisobga olingan holda qatlamning chegara to'plamlariga o'tkaziladi
to'plam cho'qqilari orasidagi masofa endi oladi, deb haqiqat
faqat teng qiymatlar. Agar A qatlamning chegara to'plami bo'lsa va uning
asimptotik tarzda
pastki birliklar va pastki umumiy soni
qatlam
shuning uchun ular deyarli har doim

50-bet

MATQIY FUNKSIYALARNING EOS FUNKSIYALARI VA BOSHQA FUNKSIYALARI 53.
Markaz,
: -A va r (a, p) - = 2k, keyin hammasi .2 (7-) ^ (“, *)
qatlamning uchlari u shunday
bu r (a, ^) = 2fc, A ga tegishli. Demak, taxminni olishimiz mumkin
3-bayonotda keltirilgan diametrga o'xshash diametrga ega.
Keling, yuqoridan qatlamning chegara to'plamlari sonini taxmin qilaylik [n / 2],
quvvati cn dan oshmaydigan.
Lemma 4 [13]. O'rta qatlamning chegara to'plamlari soni n o'lchovli
eng ko'p cn kardinallikka ega bo'lgan kubning, n-> ° o uchun biz oshib ketamiz
22 "(1 + (c + 1/2) log (c + l / 2) - c log c + o (1))
Isbot. 9-teoremada T to‘plam sifatida olamiz
qatlam mn, bu erda m = [m / 2] va biz yuqoridan turli Chow parametrlarining sonini taxmin qilamiz
kardinalligi SN dan oshmaydigan qatlamning chegara to'plamlarida. Bo'lsin
A - qatlamning chegara to'plami, birliklar to'plami teng bo'lmaganligi sababli belgilangan
NS
2-sonli b. aar2 a \ n koeffitsientlarini joylashtiramiz. Muallif ¬
k - [2Un] ni qo'yamiz va koordinatalar to'plamini 3 guruhga ajratamiz: / 11ax =
l / l, • •., lm — h} i / cp ft + 1, • • •, - ^ Kort '^' mf / il-b • • • "/ D • BUNDAYLAR SONI
bo'limlar - 2n (1 + 0 (1)) ga teng. E'tibor bering, cho'qqi
qatlam, birlik koordinatalariga ega ..., / n, A ning markazi,
va A ue dan hech bir cho'qqi / na11 ichida birdan ortiq birlikka ega bo'lishi mumkin emas, shuning uchun
qanday aks holda IA ​​bo'lardi | > cn. Haqiqatan ham, in / sr u / kon y
qatlam cho'qqilarida ko'proq k nolga ega va ularning istalgan ikkitasi bilan almashtiriladi
ikkita sobit birliklarni bir vaqtning o'zida almashtirish bilan birliklar v / 11ach pa
nollar A dan tepani beradi va bunday almashtirishlar ^)> cn. Chow vektori uchun
S (A) = (demak, si, ..., sn) bizda, demak, 2 si ^ cn, n marta soni
** = * boshlash
Chow vektorlarining shaxsiy / start-fragmentlari ^ ^ Ana¬ dan oshmaydi
mantiqan, 7Kgsh da bitta noldan ko'p bo'lmasligi mumkin va raqam / shhgfragmept
oshmaydi ^ ^ [c1] K ° H- / soni (p-parchalar oshmaydi
(cn + 1) 2 \ Va nihoyat, s0 cn + 1 dan ortiq qiymatlarni qabul qila olmaydi.
Shunday qilib, aniq Chow vektorlari soni oshmaydi
■> n (io (D)
(cn + 1)
[cn] + | /NS
[cn]
2nNO (1)) t \ cn] - | - [n / 2] V __ 22n (l'b (c'hl / 2) log (c 1-1 / 2) -clo "c 1 0 (D)
V [si] /
Lemma isbotlangan. Uning monoton funktsiyalardagi roli ga o'xshaydi
Barcha mantiqiy funktsiyalarni o'rganishda 1-8 teoremaning 2-holati.
Endi tipik bo'lgan asosiy natijani shakllantiramiz
monoton funktsiyalarning chegara raqamlari qiymatlari.
28-teorema [13]. n -> ° o kabi x (n) funksiya mavjud
Deyarli barcha monoton mantiqiy funktsiyalar uchun η o'zgaruvchilarda ph / (ph) ~
~ x (n). m (n) ning asimptotik harakati taxminlarni qondiradi
VfT ([n / 2]) 1P Bu yerda c, 2 «4.76 tenglamaning ildizi
1/2 + (s + 1/2) log (s + 1/2) - s log s - s / 2 = 0.

51-bet

54
Yu. A. Zuev
Isbot. Teoremaning pastki chegarasi usul bilan olinadi
26-teoremani isbotlashda ishlatiladiganga o'xshash. Uchun
monoton funktsiyalarni tasodifiy hosil qilish, kutish
kardinallik qatlamining ruxsat etilgan chegara to'plamlari soni cn, quyidagicha
Lemmadan 4 dan oshmaydi
22n (l + (c + l / 2) log (c + l / 2) -c log c — c / 2 + o (1))
Shuning uchun deyarli barcha funktsiyalar m qatlamida ruxsat etilgan chegara qiymatlariga ega emas.
c> cs uchun cn kardinallik to'plamlari, bu erda cs ~ 6.11 - * tenglamaning ildizi
1 + (s + 1/2) log (s + 1/2) - s log s - s / 2 - 0.
Bunday funksiyalar uchun t (cp) ^ {^ [n12] ^ c ^ n 'va Two FuN | KDi? ega
m qatlamdagi bir xil to'plamlar va faqat pastki qismida farqlanadi
m - 1 va m + 1 qatlamlaridagi birliklar, ularning soni 2n / 2 dan oshmaydi,
asimptotik jihatdan bir xil chegara raqamlariga ega. Shunung uchun
yordamida asimptotiklar mavjudligining isbotini osongina olish mumkin
monoton funktsiyalarni uchlari bilan kodlash orqali o'zgaruvchanlik printsipi
(N2]) ~ Me1) N0G0 kub '
Bundan tashqari, c> uchun kardinallikning ruxsat etilgan chegara to'plamlari soni cn
> C2 deyarli har doim oshmaydi
22n (l + (c + l / 2) log (c + l / 2) - c log c — c / 2 + o (1)) ^ 2nn ~ s)
bu erda b> 0 va qatlamning shuncha chegara to'plamlari sondan tanlanadi
aniq 2P dan oshmaydi. Ostona to'plamlar soni hisobga olinsa
eng ko'p kardinallik qatlami c ^ n dan oshmaydi
22n (l + (c2 + l / 2) log (c24-l / 2) —c2logc2-fo (l)) __
m tengsizliklar yordamida ko'proq n @ ni aniqlash mumkinligiga erishamiz
9P2 2P (3 ~ 6> 2 ^ C2 + 1 + 0 (1))
lrn / ai (1 + 0 (1))
monoton funktsiyalari. Shuning uchun, deyarli barcha 2 1 o'rnatish uchun
monoton funktsiyalar kamida asimptotik tarzda talab qilinadi ([n / 2j) | ^ 2 ^ n
chiziqli tengsizliklar.
Teoremaning yuqori chegarasini isbotlash uchun biz qoplamani olamiz
kubning (1 + o (1)) 2n / n birlik to'plari va Lemma 3 dan foydalaning, olib
to'siq Q sifatida, qatlamlar birlashmasi mm - 1 va m + 1 pastki bilan
m qatlamdagi birliklar.Xulosa qilib aytganda, m qatlamning barcha quyi birliklari bo'ladi
ichida - | (1 + o (l)) ^ 2]) / ^ sharlar va yuqori chegara quyidagilardan kelib chiqadi.
bayonotlar 7.