Теормин (2012) (1133351), страница 7
Текст из файла (страница 7)
. , p. Çàìåòèì òàêæå, ÷òî ìîùíîñòü ìíîæåñòâà G(i) , i = 1, . . . , p, ðàâíà 2si , ãäå si = |πi |,(i)è ÷òî ìíîæåñòâî G∩ G(j) ñîñòîèò èç ÔÀË, òîæäåñòâåííî ðàâíîé 0, åñëè 1 ≤ i < j ≤ p.ppPPÑëåäîâàòåëüíî, λ = |G| =|G(i) | − (p − 1) ≤2si ≤ p2s , ãäå s = max si . Òàêîå ÄÓÌ GΠ = (π1 , . .
. , πp ) ðàçáèåíèå êóáài=11≤i≤pi=1ñâÿçàííîå ñ ðàçáèåíèåì Π. Êîìïîíåíòûχδ1 , . . . , χδp õàðàêòåðèñòè÷åñêèå ÔÀË. Çàìåòèì, ÄÓÌ,ðàçáèåíèÿΠïîëîñûÄÓÌG,ÔÀË÷òî õàðàêòåðèñòè÷åñêèå ÔÀË ïîïàðíîG. Ïðåäñòàâëåíèåg = ψ1 g1 ∨ . . . ∨ ψp gp .s ≤ 2m , ñâÿçàííîå ñ ðàçáèåíèåìîðòîãîíàëüíû, òî åñòü îäíîâðåìåííî â 1 íå îáðàùàþòñÿ, è ïðèíàäëåæàòg = g1 ∨ . . .
∨ gpâ ñëó÷àå ðàññìàòðèâàåìîãî ÄÓÌÑòàíäàðòíîåΠ = (π1 , . . . , πp )ÄÓÌ ÄÓÌ ïîðÿäêàêóáàBmmGðàâíîñèëüíîè âûñîòûs,ãäåíà ïîñëåäîâàòåëüíûå îòðåçêè, äëÿ êîòîðîãî íîìåð ëþáîãî íàáîðà19πi ìåíüøål m m íîìåðà ëþáîãî íàáîðà èç ìíîæåñòâà πj , åñëè i < j , è âûïîëíåíû2mñîîòíîøåíèÿ p =s , s1 = s2 = · · · = sp−1 = s, sp = 2 − (p − 1)s ≤ s.l mmËåììà. Äëÿ ëþáûõ íàòóðàëüíûõ p, m è s, ãäå p = 2s , ñóùåñòâóåò ñòàíäàðòíîå ÄÓÌG ïîðÿäêà m è âûñîòû s, êîòîðîå ÿâëÿåòñÿ ÄÓÌ ðàíãà p è äëÿ êîòîðîãî:èç ìíîæåñòâàλ = |G| ≤ p2s1.2. ñèñòåìà èçpψ1 , . . . , ψp ÄÓÌ G îáëàäàåò òåì ñâîég, g ∈ P2 (m), è íåêîòîðûõ ÔÀË g1 , . . .
, gp èç G ñïðàâåäëèâîg = g1 ∨ . . . ∨ gp , íî è g = ψ1 g1 ∨ . . . ∨ ψp gp .îðòîãîíàëüíûõ õàðàêòåðèñòè÷åñêèõñòâîì, ÷òî äëÿ ëþáîé ÔÀËíå òîëüêî ïðåäñòàâëåíèåÝòàïû äîêàçàòåëüñòâà. Ïî ïîñòðîåíèþ ñòàíäàðòíîãî ÄÓÌ.Òåîðåìà. Ìåòîä Ëóïàíîâà.ñóùåñòâóåò ðåàëèçóþùàÿ ååÑÔÝΣf , Σf ∈ U C ,òàêàÿ, ÷òîf, f ∈ P2 (n),nL(Σf ) ≤ 2n (1 + 5 log n+O(1)).nÄëÿ ëþáîé ÔÀËf ïî (n − q) ïîñëåäíèìf , â âèäå Σf = Σ00 (Σ0 ), ãäå Σ00 ìóëüòèïëåêñîð00ïîðÿäêà (n − q), à Σ ðåàëèçóåò ñèñòåìó ôóíêöèé, êîòîðàÿ ðåàëèçóåò âñå ÔÀË âèäà fσ 00 (x ),000n−q0000ãäå x = (x1 , . . .
, xq ), σ ∈ B, è fσ 00 (x ) = f (x , σ ). Êàæäàÿ òàêàÿ ÔÀË áóäåò ðåàëèçîâàíà,Ýòàïû äîêàçàòåëüñòâà. Êàê è â ìåòîäå Øåííîíà, ðàçëîæèì ÔÀËïåðåìåííûì. Íàéäåì ÑÔÝ, ðåàëèçóþùóþ ÔÀËêàê äèçúþíêöèÿ õàðàêòåðèñòè÷åñêèõ ÔÀË ñòàíäàðòíîãî ÄÓÌ G.Ïîñòðîèì ñòàíäàðòíîå ÄÓÌ G ïîðÿäêàçóåò ñèñòåìó ÔÀË~G2ëååè âûñîòûs ≤ 2q . ΣG ÑÔÝ, êîòîðàÿ ðåàëè-è ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèå ñõåì, ïîñòðîåííûå ìîäåëèðîâàíèåìôóíêöèé èõ ñîâåðøåííûìè ÄÍÔ.
ÂqqGíå áîëååp · 2sôóíêöèé, â êàæäîé èç êîòîðûõ íå áî-åäèíèö. Òîãäà, ïî ëåììå î ñëîæíîñòè ÔÑÝ, ðåàëèçóþùåé ñîâåðøåííóþ ÄÍÔ ôóíêöèè,L(ΣG ) ≤ 3p2s+q . Ñëîæíîñòü ìóëüòèïëåêñîðà óæå ðàññìàòðèâàëàñü. L(Σ00 ) ≤ 4 · 2n−q .0n−qÄëÿ ðåàëèçàöèè êàæäîé ÔÀË fσ 00 (x ) íóæíî (p − 1) ÔÝ ∨. Âñåãî òàêèõ ÔÀË 2. Òàêèì00n−qn−qn−qîáðàçîì ïîëó÷èì ñõåìó Σ : L(Σ ) = 2(p − 1) + L(ΣG ). L(Σf ) ≤ 2(p − 1) + 4 · 2+ 3p2s+q .Âçÿâ ïàðàìåòðû s, m, q íóæíûì îáðàçîì, ïîëó÷èì òðåáóåìóþ îöåíêó.
nÑëåäñòâèå. LC (n) ∼ 2n .ïîëó÷èì:5δ, δ ⊆ B q , íàçûâàåòñÿ m-ðåãóëÿðíûì ìíîæåñòâîì íàáîðîâ êóáà B q , åñëè m <q, |δ| = 2 è âñå ïðåôèêñû äëèíû m íàáîðîâ èç δ ðàçëè÷íû. m-ðåãóëÿðíîìó ìíîæåñòâó δ, δ ⊆B q , ìîæíî âçàèìíîîäíîçíà÷íî ñîïîñòàâèòü ñèñòåìó ÔÀË ψ = (ψ1 , . . . , ψq−m ) èç P2q−m (m) òàê,mq−m÷òî íàáîð α = (β, γ), ãäå β ∈ Bè γ ∈ B, ïðèíàäëåæèò δ òîãäà è òîëüêî òîãäà, êîãäàψ(β) = γ .
Ëþáàÿ ÔÀË g, g ∈ P2 (q), ñîâïàäàåò íà m-ðåãóëÿðíîì ìíîæåñòâå íàáîðîâ δ, δ ⊆ B q ,ñ íåêîòîðîé ÔÀË èç P2 (m), åñëè ðàññìàòðèâàòü P2 (m), êàê ìíîæåñòâî âñåõ ÔÀË èç P2 (q) ñíåñóùåñòâåííûìè ÁÏ xm+1 , . . . , xq . Ïðè ýòîì ëþáàÿ ÔÀË èç ñâÿçàííîé ñ δ ñèñòåìû ôóíêöèéqñîâïàäàåò íà δ ñ ñîîòâåòñòâóþùåé ÁÏ êóáà B .Ëåììà. Äëÿ ëþáûõ íàòóðàëüíûõ m, λ è q = m + λ è äëÿ ëþáîé ñèñòåìû ÔÀË g =(g1 , .
. . , gλ ) èç P2λ (m) ñóùåñòâóåò m-ðåãóëÿðíîå ðàçáèåíèå ∆ = (δ1 , . . . , δ2q−m ) êóáà B q òàêîå,÷òî ëþáàÿ ÔÀË gi íà ëþáîé êîìïîíåíòå δj ñîâïàäàåò ëèáî ñ îäíîé èç ÁÏ xm+1 , . . . , xq , ëèáîÌíîæåñòâîmñ åå îòðèöàíèåì.gi íà ëþáîé êîìxm+1 , . . . , xq , ëèáî ñ åå îòðèöàíèåì. Ýòî çíà÷èò,÷òî ñòîëáåö çíà÷åíèé ëþáîé ÔÀË gi íà ïåðâûõ m ïåðåìåííûõ íàáîðîâ èç δj ñîâïàäàåò ñîñòîëáöîì çíà÷åíèé îäíîé èç ÁÏ xm+1 , .
. . , xq , ëèáî ñ åãî îòðèöàíèåì. êà÷åñòâå δ1 ìû áåðåì m-ðåãóëÿðíîå ìíîæåñòâî, îòâå÷àþùåå ñèñòåìå ÔÀË g =(g1 , . . . , gλ ). ×òîáû ïîëó÷èòü δ2 , . . . , δ2q−m , ìû âñåìè âîçìîæíûìè ñïîñîáàìè íàêëàäûâàåìqîòðèöàíèå íà (q − m) ïîñëåäíèõ ñòîëáöîâ. Ëþáîé íàáîð èç B åñòü â δ ñ òî÷íîñòüþ äî (q − m)ïîñëåäíèõ ñòîëáöîâ. Ïîñêîëüêó ìû ïåðåáèðàëè âñå âîçìîæíûå îòðèöàíèÿ (q − m) ïîñëåäíèõqñòîëáöîâ, â îäíîì èç δi íàéäåòñÿ èñêîìûé íàáîð. Èç ýòîãî è èç òîãî, ÷òî |∆| = 2 ïîëó÷àåì,q÷òî ∆ ðàçáèåíèå B . Òåîðåìà. Äëÿ ëþáîé ÔÀË f, f ∈ P2 (n), â U Φ ñóùåñòâóåò ðåàëèçóþùàÿ åå ôîðìóëà Ff ,2 log log n+O(1)2näëÿ êîòîðîé L(Ff ) ≤).log n (1 +log nÝòàïû äîêàçàòåëüñòâà. Ïîÿñíþ, ÷òî èìååòñÿ â âèäó ïîä ëþáàÿ ÔÀËïîíåíòåδjñîâïàäàåò ëèáî ñ îäíîé èç ÁÏ20Ýòàïû äîêàçàòåëüñòâà. Ïîñòðîèì ñòàíäàðòíîå ÄÓÌ|G| = λ, q = m + λ, ∆ = (δ1 , .
. . , δ2λ )ùåé ëåììå. Ïîñòðîèì äëÿf ðàçáèåíèåôîðìóëó, èìåþùóþ âèäBqGïîðÿäêàè âûñîòû, ïîëó÷åííîå äëÿFef =λ2Wi=1Fbn−q (x00 , y0 , . . . , y2n−q −1 )m~Gs ≤ 2m ,ïî ïðåäûäó-Ui (x0 )Fbn−q (x00 , Je0,i , . . . , Je1,i ).(n − q), Ui , i ∈ [1, 2λ ] ñîâåðøåííàÿ ÄÍÔõàðàêòåðèñòè÷åñêîé ÔÀË δi , Jσ 00 ,i ìîäåëèðóåò ÔÀË f íà êîìïîíåíòå δi . Ïîñëå îïòèìèçàef ïî ÷èñëó îòðèöàíèé, ïîëó÷èì L&,∨ (Ff ) ≤ 2q−m (q · 2m + (p − 1)2n−q + 3 · 2n−q ),öèè FL¬ (Ff ) ≤ q · 2q + 2 · 2n−m . Âçÿâ m è s ïðàâèëüíûì îáðàçîì, ïîëó÷èì íåîáõîäèìóþ îöåíêó. e f , êîòîðàÿ ìîÇàìå÷àíèå.
Óñòàíîâëåííàÿ îöåíêà ñïðàâåäëèâà è äëÿ ñëîæíîñòè π -ñõåìû Σeäåëèðóåò ïîñòðîåííóþ â õîäå ïîëó÷åíèÿ ôîðìóëû Ff ôîðìóëó Ff ñ ïîäíÿòûìè îòðèöàíèÿìèè ðåàëèçóåò ÔÀË f .ef ) ≤ Alt(Fbn−q ) + 3.Çàìå÷àíèå. Alt(F2n2nπΦÑëåäñòâèå. L (n) ∼ logn , L (n) ∼ log n .Òåîðåìà. Äëÿ n = 1, 2, . . .
âûïîëíÿåòñÿ íåðàâåíñòâî D(n) ≤ n − log log n + O(1). ìóëüòèïëåêñîð ïîðÿäêàÝòàïû äîêàçàòåëüñòâà. Âìåñòî ìóëüòèïëåêñîðà èç ïðåäûäóùåãî äîêàçàòåëüñòâà ñëåäóåòâçÿòü ÊÄ ïîðÿäêà(n − q).Îòêóäà è ïîëó÷èì òðåáóåìóþ îöåíêó.Ñëåäñòâèå. D(n) = n − log log n ± O(1).6Òåîðåìà. Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä.Äëÿ ëþáîé ÔÀË f, f ∈ P2 (n), ñóùå2n(1+O( √1n )).nmÝòàïû äîêàçàòåëüñòâà.
Ïîñòðîèì ñòàíäàðòíîå ÄÓÌ G ïîðÿäêà m è âûñîòû s ≤ 2 ,ñòâóåò ðåàëèçóþùàÿ åå ÊÑΣfòàêàÿ, ÷òîL(Σf ) ≤|G| = p, q = m + p. ψ1 , . . . , ψp õàðàêòåðèñòè÷åñêèå ôóíêöèè G. ∆ = (δ1 , . . . , δ2p ) ðàçáèåíèå~ . Ïî ñâîéñòâàì äàííîãî ðàçáèåíèÿ, ëþáàÿ ÔÀË g, g ∈ P2 (q) íà ëþáîéB q , ïîëó÷åííîå äëÿ Gêîìïîíåíòå ðàçáèåíèÿ âèäà δ1 ⊕ α, ãäå α = (0, . . . , 0, αm+1 , . . . , αm+p ) ñîâïàäàåò ñ ÔÀË ǧ =ᾱᾱm+1xm+1· g1 ∨ .
. . ∨ xq q · gp , ãäå gi = gψi .~ íà îñíîâå ÊÄ. ÏîñòðîèìÏóñòü q = m + p, ΣG (1, λ)-ÊÑ, ðåàëèçóþùàÿ ñèñòåìó ÔÀË G2p (1, 2n−q )-ÊÑ, êîòîðûå ñîäåðæàò ÊÑ ΣG â êà÷åñòâå ïîäñõåìû è ðåàëèçóþò êàæäóþ ÔÀËǧσ00 . Σ0 ïîëó÷àåòñÿ â ðåçóëüòàòå îòîæäåñòâëåíèÿ âõîäîâ âñåõ ïîñòðîåííûõ ÊÑ.σq+1Σ00 ñòðîèì, êàê ÊÑ, ðåàëèçóþùóþ ñòîëáåö èç âñåõ ÔÀË âèäà χi (x0 ) · xq+1. . . xσnn . Ñòðîèìpn−qpîáúåäèíåíèåì 2 ÊÄ ïîðÿäêà (2, 1) è (2 , 1) ÊÄ, ðåàëèçóþùèì χi îòîæäåñòâëåíèåì âûõî000n−mäîâ. Σf = Σ (Σ ). L(Σf ) ≤ (p + 2)2+ (λ + 1)2q+1 . Âçÿâ ïàðàìåòðû m è s íóæíûì îáðàçîì,ïîëó÷èì íåîáõîäèìóþ îöåíêó. nÑëåäñòâèå.
LK (n) ∼ 2n .pn−m+1Çàìå÷àíèå. Ïîñòðîåííóþ ÊÑ Σf ìîæíî ðàçáèòü íà íå áîëåå, ÷åì λp · 2 + 2+ (λ +n2√q+11)2= O( n n ) çâåçä, êàæäàÿ èç êîòîðûõ ñîñòîèò èç êîíòàêòîâ îäíîãî è òîãî æå òèïà.7Q, Q = Q(1), Q(2), . . . , Q(n), . . .,Ψ(Q(n)) = max Ψ(f ).ãäåQ ⊆ P2èQ(n) = Q ∩ P2 (n), n = 1, 2, . . ..f ∈Q(n)||U(Ψ(Q(n)), n)|| ≥ |Q(n)|.Ëåììà.Äëÿ êëàññà ÔàëQòàêîãî, ÷òîn = o( logloglog|Q(n)||Q(n)| )(log n = o(log log |Q(n)|)),ïîëíÿþòñÿ ñëåäóþùèå àñèìïòîòè÷åñêèå íåðàâåíñòâàKL (Q(n)) &CL (Q(n)) &âû-log |Q(n)|log log |Q(n)| , (ñîîòâåòñòâåííîlog |Q(n)|log log |Q(n)| ).Ýòàïû äîêàçàòåëüñòâà.
Äîêàçûâàåòñÿ àíàëîãè÷íî ïîñëåäíåé òåîðåìå âòîðîãî ïàðàãðàôà.Ëåììà.(1, m)-ÊÑ Σ ðåàëèçóåò m ðàçëè÷íûõ ÔÀË,L(Σ) ≥ 2m − 2.nÝòàïû äîêàçàòåëüñòâà. Σ ñâÿçíàÿ ÊÑ. Èç åå ðàçäåëèòåëüíîñòè ñëåäóåò, ÷òî ∀α, α ∈ Bñåòü Σ|α ñîñòîèò íå ìåíåå ÷åì èç m êîìïîíåíò ñâÿçíîñòè. Çíà÷èò, áûëî óäàëåíî íå ìåíåå, ÷åìÅñëè ðàçäåëèòåëüíàÿ ïî âûõîäàìîòëè÷íûõ îò 0, òî21m−1 êîíòàêòîâ. Òàêèì îáðàçîì ïîëó÷èì, ÷òî |E(Σ|ᾱ)| ≥ m−1. Ñóììèðóÿ ýòî íåðàâåíñòâî ïîB n è ó÷èòûâàÿ, ÷òî êàæäûé êîíòàêò ÊÑ Σ íå ïðîâîäèò ðîâíî íà ïîëîâèíåâñåì íàáîðàì êóáàâñåõ íàáîðîâ (êàæäûé êîíòàêò áûë ïîñ÷èòàí ñòîëüêî ðàç, ñêîëüêî íàáîðîâ îí ïðîâîäèò, òîåñòü2n−1ðàç) ïîëó÷èì2n−1 L(Σ) ≥ 2n (m − 1).Îòêóäà è ñëåäóåò äîêàçûâàåìîå íåðàâåíñòâî.Ñëåäñòâèå.Êîíòàêòíîå äåðåâî ïîðÿäêàn ÿâëÿåòñÿ ìèíèìàëüíîé ðàçäåëèòåëüíîé (1, 2n )-Qn .F = (f1 , .
. . , fm ) ñîñòîèòmP|Nfj |.LK (F ) ≥ 21−nÊÑ, ðåàëèçóþùåé ñèñòåìó ÔÀËËåììà.X(n),Åñëè ñèñòåìà ÔÀËîòëè÷íûõ îò 0 è 1, òîèç ïîïàðíî ðàçëè÷íûõ ÔÀË îò ÁÏj=1Ýòàïû äîêàçàòåëüñòâà.∀α, α ∈ B nâ ñåòèΣ|αèìååòñÿ êîìïîíåíòà ñâÿçíîñòè, âêëþ-÷àþùàÿ âõîä è ñòîëüêî âûõîäîâ, ñêîëüêî ôóíêöèé îáðàùàþòñÿ â åäèíèöó íà|E(Σ|α)| ≥ f1 (α) + · · · + fm (α).mPn−12L(Σ) ≥|Nfj |.ïîëó÷èìα.ÎòñþäàÑóììèðóÿ íåðàâåíñòâî âî âñåì íàáîðàì ïîëó÷èìj=1Ñëåäñòâèå. LK (Jn ) ≥ 2n+1 − 2.Ëåììà.
Äëÿ n = 1, 2, . . . âûïîëíÿþòñÿíåðàâåíñòâàn2n+1 + O( 2n ).nLK (Q~n ) ≤ 2n + O( 2n ), LK (J~n ) ≤λ = 2m , q = m + λ, q ≤ n. ∆ = (δ1 , . . . , δ2λ )~ m ñèñòåìå ÔÀË èç ÝÊ ðàíãà m. m-ðåãóëÿðíîå ðàçáèåíèå êóáà B , îòâå÷àþùåå ñèñòåìå Qσqσ100Ëþáàÿ ÝÊ ðàíãà q K(x ) = x1 . . . xq , σ = (σ1 , . . . , σq ) ∈ δi ñîâïàäàåò íà ìíîæåñòâå δi ñ~ m .
Èíà÷å ãîâîðÿ, ñîâïàäàåò ñ ÁÏ xασ0 , m+1 ≤ jσ0 ≤ q , ασ0 ∈ B . Ëþáàÿîäíîé èç ÝÊ ñèñòåìû Qjσ 0ασ 0σ1σ000ÝÊ K = x1 . . . xnn ìîæåò áûòü ïðåäñòàâëåíà â âèäå K = χi (x ) · xj 0 · Kσ 00 (x ).σ(1, 2λ )-ÊÑ Σ0 ðåàëèçóåò ñèñòåìó ÔÀË χ~ îáúåäèíåíèåì ÊÑ äëÿ χi , ïîñòðîåííûõ íà îñíîâå(&)00èõ ñîâåðøåííûõ ÄÍÔ. Kσ 00 (x ) ðåàëèçóþòñÿ ÊÄ. Ïîëó÷àåòñÿ ñõåìà Σn .(&) λ2 ïîäñõåì ñëîæíîñòüþ q2m (ñëîæíîñòü Σ0i ) + 2n−q+1 − 2 (ñëîæíîñòü ÊÄ ñõåìå Σnn−qïîðÿäêà n − q ) + 2· λ (ê êàæäîìó èç âûõîäîâ ÊÄ ïðèñîåäèíåíî λ êîíòàêòîâ). Ïîëó÷àåì(&)λmL(Σn ) = 2 (q2 +2n−q+1 −2+λ2n−q ). Âñïîìíèì, ÷òî λ = q −m, ðàñêðîåì ñêîáêè è ïîëó÷èì:(&)L(Σn ) = λ2n−m + 2n−m+1 + q2q .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
