Теоремы и идеи доказательства (2012) (1133349), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

ïîêðûòèÿ äëÿ ìàòðèöûïàðàãðàôà ïåðâîéFäëÿ ïàðû(M, N )W1≤t≤pM ht,ii6=M ht,jiyt ÿâëÿåòñÿ îäíîâðåìåííî ÔÀËîáðàòíî. Òàê ÷òî ëåììà âåðíà ñîãëàñíî ïåðâîé ëåììå øåñòîãîÑëåäñòâèå.Êàæäàÿ ýëåìåíòàðíàÿ êîíúþíêöèÿ âèäà yt1 · · · ytr ñîêðàùåííîé ÄÍÔ ôóíêf (y1 , . . . , yp ), ïîëó÷àþùàÿñÿ èç ÊÍÔ ëåììû â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ, ñîîòâåòñòâóåò òóïèêîâîìó òåñòó, ñâÿçàííîìó ñ ìíîæåñòâîì T = {t1 , .

. . , tr } è îáöèèðàòíî.Ëåììà.Äëèíà ëþáîãî òóïèêîâîãî äèàãíîñòè÷åñêîãî òåñòà äëÿ îòäåëèìîé ïî ñòîëáöàìB p,sdlog se äî (s − 1).t ñòðîê ìàòðèöû M îáðàçóþò åå òóïèc - ìàòðèöà, ñîñòîÿùàÿ èç ïåðâûõ t ñòðîê ìàòðèöû M . ×èñëîêîâûé äèàãíîñòè÷åñêèé òåñò. Mttðàçëè÷íûõ áóëåâûõ ñòîëáöîâ âûñîòû t ðàâíî 2 . Ïîñêîëüêó âñå s ñòîëáöîâ ðàçëè÷íû, s ≤ 2 ,òî åñòü t ≥ dlog se.∀q, q ∈ [1, t] îïðåäåëèì îòíîøåíèå ýêâèâàëåíòíîñòè: m0 ∼ m00 òîãäà è òîëüêî òîãäà, êîãäàìàòðèöû èç ìíîæåñòâàçàêëþ÷åíà â ïðåäåëàõ îòÝòàïû äîêàçàòåëüñòâà. ÏóñòüM ∈ B p,sè ïåðâûåqc ñîâïàäàþò â ñòðîêàõ ñ íîìåðàìè èç [1, q].

×èñëî êëàññîâ ýêâèâàm0 , m00 ìàòðèöû Mëåíòíîñòè θ(q). Ïîñêîëüêó òåñò òóïèêîâûé, θ(q) < θ(q +1). Ïîñêîëüêó òåñò äèàãíîñòè÷åñêèé,θ(t) = s. Ïîëó÷àåì 1 = θ(0) < θ(1) < · · · < θ(t) = s, òî åñòü t ≤ (s − 1). Ëåììà. Ïóñòü ϕ(s), t(s) è p(s) öåëî÷èñëåííûå íåîòðèöàòåëüíûå ôóíêöèè íàòóðàëüíîãîàðãóìåíòà s, äëÿ êîòîðûõ t(s) = d2 log se + ϕ(s), p(s) ≥ t(s), ϕ(s) −→ ∞. Òîãäà ó ïî÷òè âñåõñòîëáöûs→∞îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èçB p(s),sïåðâûåt(s)ñòðîê îáðàçóþò äèàãíîñòè÷åñêèé òåñò.B p(s),s : 2t (2t − 1) .

. . (2t −(s−1)1s + 1) · 2= 2 (1 − 2t ) . . . (1 − 2t ). Èõ äîëÿ ñðåäè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö(s−1)1s2p,sps−2ϕ(s)èç B(2 ) íå ìåíüøå, ÷åì (1 − t ) . . . (1 −, ÷òî ñòðåìèòñÿ ê 122t ) ≥ 1 − 2t ≥ 1 − 2ïðè s ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè. Ýòàïû äîêàçàòåëüñòâà. Îöåíèì êîëè÷åñòâî çàäàííûõ ìàòðèö(p−t)sÑëåäñòâèå.psÄëÿ ëþáîé íåîòðèöàòåëüíîé è íåîãðàíè÷åííî âîçðàñòàþùåé ôóíêöèèó ïî÷òè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èçòåñòà íå áîëüøå, ÷åì2 log s + ϕ(s).11B p,sϕ(s)äëèíà ìèíèìàëüíîãî äèàãíîñòè÷åñêîãîËåììà.

Äëÿ ëþáûõ p ≥ 0, q ≥ 0 è ëþáîé ÊÑ Σ ñóùåñòâóåò ýêâèâàëåíòíàÿ åé ÊÑ Σ0 , Σ0 ∈KU(p,q) , äëÿ êîòîðîé L(Σ0 ) ≤ (p + 1)(q + 1)L(Σ).Ýòàïû äîêàçàòåëüñòâà. Ñõåìà ñòðîèòñÿ ïóòåì ïàðàëëåëüíîãî è (èëè) ïîñëåäîâàòåëüíîãîäóáëèðîâàíèÿ êîíòàêòîâ.Ëåììà.Äëÿëþáîéñàìîêîððåêòèðóþùèåñÿ ÊÑÊÑΣ0èΣΣ00ñóùåñòâóþòýêâèâàëåíòíûåñîîòâåòñòâåííî òàêèå, ÷òîåé(1,0)-è(0,1)-L(Σ0 ) ≤ L(Σ) + ζ(Σ), L(Σ00 ) ≤L(Σ) + ζ(Σ).LK(n)∼(1,0)Ýòàïû äîêàçàòåëüñòâà. Ñòðîèòñÿ çàìåíîé îäíîðîäíûõ ìåòåëîê íà öèêëû (çâåçäû).Òåîðåìà Äëÿ n = 1, 2, . . .LK(0,1) (n) ∼èìåþò ìåñòî ñëåäóþùèå àñèìïòîòè÷åñêèå ðàâåíñòâà:2nnÝòàïû äîêàçàòåëüñòâà. Íèæíèå îöåíêè ñëåäóþò èç ïåðâîé òåîðåìû âòîðîãî ïàðàãðàôàòðåòüåé ãëàâû.

Âåðõíèå îöåíêè ñëåäóþò èç ïåðâîé òåîðåìû øåñòîãî ïàðàãðàôà òðåòüåé ãëàâûè çàìå÷àíèÿ ê íåé.nζ(Σf ) = o( n2√n ).Òàê ÷òî ñóùåñòâóþò ÊÑ, êîòîðûå ðåàëèçóþò ÔÀË2nñëîæíîñòüþ, àñèìïòîòè÷åñêè íå ïðåâîñõîäÿùåén . Ëåììà. Äëÿ n = 1, 2, . . . èìåþò ìåñòî ðàâåíñòâà LK(0,1) (ln )ñî¯= LK(0,1) (ln ) = 4n.σ, σ ∈ B , èç âõîäà (âûõîäà) ýòîé ñõåìû, ïðîâåäåìxσn (xσ1 ) â âåðøèíó, ñîåäèíåííóþ êîíòàêòîì âèäà xσ̄n (xσ̄q ) ñ åå âûõîäîì (âõîäîì).Ýòàïû äîêàçàòåëüñòâà. Äëÿ êàæäîãîêîíòàêò âèäàf12.

Характеристики

Список файлов ответов (шпаргалок)