Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (1185330), страница 56
Текст из файла (страница 56)
èÓÒΉӂ‡ÚÂθÌÓÒÚ¸ d1∗ , d2∗ , d3∗ ,...( d1∗ ≤ d2∗ ≤ d3∗ ≤ ...) ̇Á˚‚‡ÂÚÒfl‡ÒÒÚÓflÌÌ˚Ï ÔÓÙËÎÂÏ ÍÓ‰‡. ë‚Ó·Ó‰ÌÓ ‡ÒÒÚÓflÌË ҂ÂÚÓ˜ÌÓ„Ó ÍÓ‰‡ ËÎË ÍÓ‰‡ÔÂÂÏÂÌÌÓÈ ‰ÎËÌ˚ ‡‚ÌÓ max dl∗ lim dl∗ = d∞∗ .ll →∞ùÙÙÂÍÚË‚ÌÓ ҂ӷӉÌÓ ‡ÒÒÚÓflÌËÂíÛ·Ó-ÍÓ‰ÓÏ Ì‡Á˚‚‡ÂÚÒfl ‰ÎËÌÌ˚È ·ÎÓÍÓ‚˚È ÍÓ‰, ‚ ÍÓÚÓÓÏ ËÏÂÂÚÒfl L ‚ıÓ‰fl˘Ëı·ËÚÓ‚ Ë Í‡Ê‰˚È ËÁ ˝ÚËı ·ËÚÓ‚ ÍÓ‰ËÛÂÚÒfl q ‡Á. èË j-Ï ÍÓ‰ËÓ‚‡ÌËË L ·ËÚÓ‚ÔÓÔÛÒ͇˛ÚÒfl ˜ÂÂÁ ·ÎÓÍ ÔÂÂÒÚ‡ÌÓ‚ÓÍ Pj, ‡ Á‡ÚÂÏ ÍÓ‰ËÛ˛ÚÒfl ·ÎÓÍÓ‚˚Ï [Nj, L]ÍÓ‰ÂÓÏ (ÍÓ‰ÂÓÏ ÍÓ‰Ó‚˚ı Ù‡„ÏÂÌÚÓ‚), ÍÓÚÓ˚È ÏÓÊÂÚ ‡ÒÒχÚË‚‡Ú¸Òfl ͇ÍL × Nj χÚˈ‡. íÓ„‰‡ ËÒÍÓÏ˚Ï ÚÛ·Ó-ÍÓ‰ÓÏ fl‚ÎflÂÚÒfl ÎËÌÂÈÌ˚È [N1 + ...
+Nq, L]-ÍÓ‰(ÒÏ., ̇ÔËÏÂ, [BGT93]).i-‚Á‚¯ÂÌÌÓ ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË ‚ıÓ‰‡ di(C) ÚÛ·Ó-ÍÓ‰‡ ë ÂÒÚ¸ ÏËÌËχθÌ˚È ‚ÂÒ ‰Îfl ÍÓ‰Ó‚˚ı ÒÎÓ‚, ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘Ëı ‚ıÓ‰fl˘ËÏ ÒÎÓ‚‡Ï ‚ÂÒ‡ i. ùÙÙÂÍÚË‚Ì˚Ï Ò‚Ó·Ó‰Ì˚Ï ‡ÒÒÚÓflÌËÂÏ ÍÓ‰‡ ë ÔÓ͇Á˚‚‡ÂÚÒfl Â„Ó 2-‚Á‚¯ÂÌÌÓ ÏËÌËχθ-248ó‡ÒÚ¸ IV. ê‡ÒÒÚÓflÌËfl ‚ ÔËÍ·‰ÌÓÈ Ï‡ÚÂχÚËÍÂÌÓ ‡ÒÒÚÓflÌË ‚ıÓ‰‡ d2 (C), Ú.Â. ÏËÌËχθÌ˚È ‚ÂÒ ‰Îfl ÍÓ‰Ó‚˚ı ÒÎÓ‚, ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘Ëı ‚ıÓ‰fl˘ËÏ ÒÎÓ‚‡Ï ‚ÂÒ‡ 2.ê‡ÒÔ‰ÂÎÂÌË ‡ÒÒÚÓflÌËÈÑÎfl ÍÓ‰‡ ë ̇‰ ÍÓ̘Ì˚Ï ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ (X, d) Ò ‰Ë‡ÏÂÚÓÏdiam(X, d) = D ‡ÒÔ‰ÂÎÂÌË ‡ÒÒÚÓflÌËÈ ‰Îfl ë ÂÒÚ¸ (D + 1)-‚ÂÍÚÓ (A0 ,..., AD), „‰Â1Ai =| {(c, c ′) ∈ C 2 : d (c, c ′) = i} | .
í‡ÍËÏ Ó·‡ÁÓÏ, Ï˚ ‡ÒÒχÚË‚‡ÂÏ ‚Â΢ËÌ˚|C|Ai(c) – ˜ËÒÎÓ ÍÓ‰Ó‚˚ı ÒÎÓ‚ ̇ ‡ÒÒÚÓflÌËË i ÓÚ ÍÓ‰Ó‚Ó„Ó ÒÎÓ‚‡ Ò, Ë ·ÂÂÏ Ai ͇Í҉̠ÓÚ Ai(c) ÔÓ ‚ÒÂÏ c ∈ C. A0 = 1 Ë, ÂÒÎË d* = d* (C) fl‚ÎflÂÚÒfl ÏËÌËχθÌ˚Ï ‡ÒÒÚÓflÌËÂÏ ‰Îfl ë, ÚÓ A1 = ... Ad ∗ −1 = 0.ê‡ÒÔ‰ÂÎÂÌË ‡ÒÒÚÓflÌËÈ ‰Îfl ÍÓ‰‡ Ò Á‡‰‡ÌÌ˚ÏË Ô‡‡ÏÂÚ‡ÏË ‚‡ÊÌÓ, ‚ ˜‡ÒÚÌÓÒÚË, ‰Îfl ÓˆÂÌÍË ‚ÂÓflÚÌÓÒÚË Ó¯Ë·ÍË ‰ÂÍÓ‰ËÓ‚‡ÌËfl ÔË ÔËÏÂÌÂÌËË ‡Á΢Ì˚ı‡Î„ÓËÚÏÓ‚ ‰ÂÍÓ‰ËÓ‚‡ÌËfl.
äÓÏ ÚÓ„Ó, ˝ÚÓ ÏÓÊÂÚ ÔÓÏÓ˜¸ ÔË ÓÔ‰ÂÎÂÌËËÒ‚ÓÈÒÚ‚ ÍÓ‰Ó‚˚ı ÒÚÛÍÚÛ Ë ‰Ó͇Á‡ÚÂθÒÚ‚Â Ì‚ÓÁÏÓÊÌÓÒÚË ÒÛ˘ÂÚ‚Ó‚‡ÌËfl ÓÔ‰ÂÎÂÌÌ˚ı ÍÓ‰Ó‚.ê‡ÒÒÚÓflÌË ӉÌÓÁ̇˜ÌÓÒÚËê‡ÒÒÚÓflÌËÂÏ Ó‰ÌÓÁ̇˜ÌÓÒÚË ÍËÔÚÓÒËÒÚÂÏ˚ (òÂÌÌÓÌ, 1949) ̇Á˚‚‡ÂÚÒfl ÏËÌËχθ̇fl ‰ÎË̇ ¯ËÙÓÚÂÍÒÚ‡, ÌÂÓ·ıÓ‰Ëχfl ‰Îfl Û‚ÂÂÌÌÓÒÚË ‚ ÚÓÏ, ˜ÚÓ ÒÛ˘ÂÒÚ‚ÛÂÚÚÓθÍÓ Â‰ËÌÒÚ‚ÂÌÌ˚È ÒÏ˚ÒÎÓ‚ÓÈ ‚‡Ë‡ÌÚ Â„Ó ‡Ò¯ËÙÓ‚ÍË. ÑÎfl Í·ÒÒ˘ÂÒÍËıÍËÔÚÓ„‡Ù˘ÂÒÍËı ÒËÒÚÂÏ Ò ÙËÍÒËÓ‚‡ÌÌ˚Ï Íβ˜Â‚˚Ï ÔÓÒÚ‡ÌÒÚ‚ÓÏ ‡ÒÒÚÓflÌË ӉÌÓÁ̇˜ÌÓÒÚË ‡ÔÔÓÍÒËÏËÛÂÚÒfl ÔÓ ÙÓÏÛΠç(K)/D , „‰Â H(K) – ˝ÌÚÓÔËflÍβ˜Â‚Ó„Ó ÔÓÒÚ‡ÌÒÚ‚‡ („Û·Ó „Ó‚Ófl, log2 N, „‰Â N – ÍÓ΢ÂÒÚ‚Ó Íβ˜ÂÈ), ‡ DËÁÏÂflÂÚ ËÁ·˚ÚÓ˜ÌÓÒÚ¸ ÂÁ‚ËÓ‚‡ÌËfl ËÒıÓ‰ÌÓ„Ó flÁ˚͇ ÓÚÍ˚ÚÓ„Ó ÚÂÍÒÚ‡ ‚ ·ËÚ‡ı̇ ·ÛÍ‚Û.äËÔÚÓÒËÒÚÂχ Ó·ÂÒÔ˜˂‡ÂÚ Ë‰Â‡Î¸ÌÛ˛ ÒÂÍÂÚÌÓÒÚ¸, ÂÒÎË Â ‡ÒÒÚÓflÌË ӉÌÓÁ̇˜ÌÓÒÚË ·ÂÒÍÓ̘ÌÓ. ç‡ÔËÏÂ, Ó‰ÌÓ‡ÁÓ‚˚ ·ÎÓÍÌÓÚ˚ Ó·ÂÒÔ˜˂‡˛Ú ˉ‡θÌÛ˛ ÒÂÍÂÚÌÓÒÚ¸; ËÏÂÌÌÓ Ú‡ÍË ÍÓ‰˚ ËÒÔÓθÁÛ˛ÚÒfl ‰Îfl Ò‚flÁË ÔÓ "͇ÒÌÓÏÛÚÂÎÂÙÓÌÛ" ÏÂÊ‰Û äÂÏÎÂÏ Ë ÅÂÎ˚Ï ‰ÓÏÓÏ.16.2.
éëçéÇçõÖ êÄëëíéüçàü çÄ äéÑÄïê‡ÒÒÚÓflÌË ‡ËÙÏÂÚ˘ÂÒÍÓ„Ó ÍÓ‰‡ÄËÙÏÂÚ˘ÂÒÍËÏ ÍÓ‰ÓÏ (ËÎË ÍÓ‰ÓÏ Ò ËÒÔ‡‚ÎÂÌËÂÏ ‡ËÙÏÂÚ˘ÂÒÍËı ӯ˷ÓÍ)̇Á˚‚‡ÂÚÒfl ÍÓ̘ÌÓ ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ë ÏÌÓÊÂÒÚ‚‡ ˆÂÎ˚ı (Ó·˚˜ÌÓ ÌÂÓÚˈ‡ÚÂθÌ˚ı) ˜ËÒÂÎ. éÌ Ô‰̇Á̇˜‡ÂÚÒfl ‰Îfl ÍÓÌÚÓÎfl ÙÛÌ͈ËÓÌËÓ‚‡ÌËfl ·ÎÓ͇ÒÛÏÏËÓ‚‡ÌËfl (ÏÓ‰ÛÎfl ÒÎÓÊÂÌËfl). äÓ„‰‡ ÒÎÓÊÂÌË ˜ËÒÂÎ ÓÒÛ˘ÂÒÚ‚ÎflÂÚÒfl ‚ ‰‚Ó˘ÌÓÈ ÒËÒÚÂÏ ҘËÒÎÂÌËfl, ÚÓ Â‰ËÌÒÚ‚ÂÌÌ˚È Ò·ÓÈ ‚ ‡·ÓÚ ·ÎÓ͇ ÒÛÏÏËÓ‚‡ÌËfl ‚‰ÂÚ ÍËÁÏÂÌÂÌ˲ ÂÁÛθڇڇ ̇ ÌÂÍÓÚÓÛ˛ ÒÚÂÔÂ̸ ‰‚ÓÈÍË, Ú.Â., Í Ó‰ÌÓÈ ‡ËÙÏÂÚ˘ÂÒÍÓÈ Ó¯Ë·ÍÂ.
îÓχθÌÓ Ó‰Ì‡ ‡ËÙÏÂÚ˘ÂÒ͇fl ӯ˷͇ ̇ ÓÔ‰ÂÎflÂÚÒfl ͇ÍÔÂÓ·‡ÁÓ‚‡ÌË ˜ËÒ· n ∈ ‚ ˜ËÒÎÓ n = n ± 2i, i = 1, 2,... .ê‡ÒÒÚÓflÌË ‡ËÙÏÂÚ˘ÂÒÍÓ„Ó ÍÓ‰‡ ÂÒÚ¸ ÏÂÚË͇ ̇ , ÓÔ‰ÂÎÂÌ̇fl ‰Îfl β·˚ın1 , n2 ∈ Í‡Í ÏËÌËχθÌÓ ˜ËÒÎÓ ‡ËÙÏÂÚ˘ÂÒÍËı ӯ˷ÓÍ, Ô‚Ӊfl˘Ëı n1 ‚ n 2 .Ö„Ó ÏÓÊÌÓ Á‡ÔËÒ‡Ú¸ Í‡Í w 2 (n1 – n 2 ), „‰Â w 2 (n) ÂÒÚ¸ ‡ËÙÏÂÚ˘ÂÒÍËÈ 2-‚ÂÒ n, Ú.Â.̇ËÏÂ̸¯Ó ‚ÓÁÏÓÊÌÓ ˜ËÒÎÓ ÌÂÌÛ΂˚ı ÍÓ˝ÙÙˈËÂÌÚÓ‚ ‚ Ô‰ÒÚ‡‚ÎÂÌËËkn=∑ ei 2i ,i=0„‰Â e i 0, ±1 Ë k – ÌÂÍÓÚÓÓ ÌÂÓÚˈ‡ÚÂθÌÓ ˜ËÒÎÓ.
àÏÂÌÌÓ, ‰ÎflÍ‡Ê‰Ó„Ó n ËÏÂÂÚÒfl ‰ËÌÒÚ‚ÂÌÌÓ ڇÍÓ Ô‰ÒÚ‡‚ÎÂÌËÂ Ò e k ≠ 0, e iei+1 = 0 ‰Îfl ‚ÒÂıÉ·‚‡ 16. ê‡ÒÒÚÓflÌËfl ‚ ÚÂÓËË ÍÓ‰ËÓ‚‡ÌËfl249i = 0,..., k – 1, ÍÓÚÓÓ ӷ·‰‡ÂÚ Ì‡ËÏÂ̸¯ËÏ ˜ËÒÎÓÏ ÌÂÌÛ΂˚ı ÍÓ˝ÙÙˈËÂÌÚÓ‚(ÒÏ. ÄËÙÏÂÚ˘ÂÒ͇fl ÏÂÚË͇ r-ÌÓÏ˚, „Î. 12).ê‡ÒÒÚÓflÌË ò‡Ï˚–äÓ¯Ë͇èÛÒÚ¸ q ≥ 2 Ë m ≥ 2. ê‡Á·ËÂÌË {B0 , B1 ,..., Bq–1} ÏÌÓÊÂÒÚ‚‡ m ̇Á˚‚‡ÂÚÒfl ‡Á·ËÂÌËÂÏ ò‡Ï˚–äÓ¯Ë͇, ÂÒÎË ‚˚ÔÓÎÌfl˛ÚÒfl ÒÎÂ‰Û˛˘Ë ÛÒÎÓ‚Ëfl:1) B0 = {0};2) ‰Îfl β·Ó„Ó i ∈ m, i ∈ Bs ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ m – i ∈ Bs, s = 1, 2,..., q – 1;3) ÂÒÎË i∈ Bs, j ∈ Bt Ë s > t, ÚÓ min{i, m – i} > {j, m – j};4) ÂÒÎË s > t, s, t = 0, 1,..., q – 1, ÚÓ | Bs | ≥ | Bt |, ÍÓÏ s = q – 1, ÍÓ„‰‡1| Bq −1 | ≥ | Bq − 2 | .2ÑÎfl ‡Á·ËÂÌËfl ò‡Ï˚–äÓ¯Ë͇ ÏÌÓÊÂÒÚ‚‡ m ‚ÂÒ ò‡Ï˚–äÓ¯Ë͇ w SK(x)β·Ó„Ó ˝ÎÂÏÂÌÚ‡ x ∈ m ÓÔ‰ÂÎflÂÚÒfl Í‡Í wSK(x) = i, ÂÒÎË x ∈ Bi, i ∈ {0, 1,..., q – 1}.ê‡ÒÒÚÓflÌË ò‡Ï˚–äÓ¯Ë͇ (ÒÏ., ̇ÔËÏÂ, [ShKa97]) ÂÒÚ¸ ÏÂÚË͇ ̇ m,ÓÔ‰ÂÎÂÌ̇fl ͇Íw SK(x – y).ê‡ÒÒÚÓflÌË ò‡Ï˚–äÓ¯Ë͇ ̇ nm ÓÔ‰ÂÎflÂÚÒfl Í‡Í w SK(x – y), „‰Â ‰Îflnnx = ( x1 ,..., x n ) ∈ nm Ï˚ ËÏÂÂÏ wSK( x) =∑ wSK ( xi ).i =1ï˝ÏÏËÌ„Ó‚‡ ÏÂÚË͇ Ë ÏÂÚË͇ ãË ‚ÓÁÌË͇˛Ú Í‡Í ‰‚‡ ˜‡ÒÚÌ˚ı ÒÎÛ˜‡fl ‡Á·ËÂÌËÈ ‚˚¯Â̇Á‚‡ÌÌÓ„Ó ÚËÔ‡: PH = {B0 , B1 }, „‰Â B1 = {1, 2,...., q – 1} Ë PL = {B0 , B1 ,...,qBq/2}, „‰Â Bi = {i, m − i}, i = 1,..., .2ê‡ÒÒÚÓflÌË ‡·ÒÓβÚÌÓ„Ó ÒÛÏÏËÓ‚‡ÌËflê‡ÒÒÚÓflÌË ‡·ÒÓβÚÌÓ„Ó ÒÛÏÏËÓ‚‡ÌËfl (ËÎË ‡ÒÒÚÓflÌË ãË) – ÏÂÚË͇ ãË Ì‡ÏÌÓÊÂÒÚ‚Â nm , ÓÔ‰ÂÎÂÌ̇fl ͇Íw Lee(x – y),n„‰Â wSK ( x ) =∑ min{xi , m − xi} fl‚ÎflÂÚÒfl ‚ÂÒÓÏ ãË ˝ÎÂÏÂÌÚ‡ x = ( x1,..., xn ) ∈ nm .i =1ÖÒÎË ÏÌÓÊÂÒÚ‚Ó nm Ò̇·ÊÂÌÓ ‡ÒÒÚÓflÌËÂÏ ‡·ÒÓβÚÌÓ„Ó ÒÛÏÏËÓ‚‡ÌËfl, ÚÓÔÓ‰ÏÌÓÊÂÒÚ‚Ó ë ÏÌÓÊÂÒÚ‚‡ nm ̇Á˚‚‡ÂÚÒfl ÍÓ‰ÓÏ ‡ÒÒÚÓflÌËfl ãË.
äÓ‰˚ ‡ÒÒÚÓflÌËfl ãË ÔËÏÂÌfl˛ÚÒfl ‚ ͇̇·ı Ò‚flÁË Ò Ù‡ÁÓ‚ÓÈ ÏÓ‰ÛÎflˆËÂÈ Ë Ò ÏÌÓ„ÓÛÓ‚Ì‚ÓÈÍ‚‡ÌÚÓ‚‡ÌÌÓÈ ËÏÔÛθÒÌÓÈ ÏÓ‰ÛÎflˆËÂÈ, ‡ Ú‡ÍÊ ‚ ÚÓÓˉ‡Î¸Ì˚ı ÒÂÚflı Ò‚flÁË.LJÊÌÂȯËÏË ÍÓ‰‡ÏË ‡ÒÒÚÓflÌËfl ãË fl‚Îfl˛ÚÒfl Ì„‡ˆËÍ΢ÂÒÍË ÍÓ‰˚.ê‡ÒÒÚÓflÌË å‡ÌıÂÈχèÛÒÚ¸ [i] = {a + bi: a, b ∈ } – ÏÌÓÊÂÒÚ‚Ó ˆÂÎ˚ı „‡ÛÒÒÓ‚˚ı ˜ËÒÂÎ. èÛÒÚ¸π = a + bi(a > b > 0) – „‡ÛÒÒÓ‚Ó ÔÓÒÚÓ ˜ËÒÎÓ.
ùÚÓ Á̇˜ËÚ, ˜ÚÓ (a + bi)(a – bi) == a2 + b 2 = p, „‰Â p 1(mod 4) ÂÒÚ¸ ÔÓÒÚÓ ˜ËÒÎÓ, ËÎË ˜ÚÓ π = p + 0 ⋅ i = p, „‰Âp 3(mod 4) ÂÒÚ¸ ÔÓÒÚÓ ˜ËÒÎÓ.ê‡ÒÒÚÓflÌË å‡ÌıÂÈχ – ˝ÚÓ ‡ÒÒÚÓflÌË ̇ [i], ÓÔ‰ÂÎÂÌÌÓ ‰Îfl β·˚ı ‰‚ÛıˆÂÎ˚ı „‡ÛÒÒÓ‚˚ı ˜ËÒÂÎ ı Ë Û Í‡Í ÒÛÏχ ‡·ÒÓβÚÌ˚ı Á̇˜ÂÌËÈ ‰ÂÈÒÚ‚ËÚÂθÌÓÈ ËÏÌËÏÓÈ ˜‡ÒÚÂÈ ‡ÁÌÓÒÚË x – y(mod π). è˂‰ÂÌË ÔÓ ÏÓ‰Ûβ Ô‰ ÒÛÏÏËÓ‚‡ÌËÂÏ250ó‡ÒÚ¸ IV. ê‡ÒÒÚÓflÌËfl ‚ ÔËÍ·‰ÌÓÈ Ï‡ÚÂχÚË͇·ÒÓβÚÌ˚ı Á̇˜ÂÌËÈ ‰ÂÈÒÚ‚ËÚÂθÌÓÈ Ë ÏÌËÏÓÈ ˜‡ÒÚÂÈ – ‡ÁÌˈ‡ ÏÂÊ‰Û ÏÂÚËÍÓÈå‡Ìı˝ÚÚÂ̇ Ë ‡ÒÒÚÓflÌËÂÏ å‡ÌıÂÈχ.ùÎÂÏÂÌÚ˚ ÍÓ̘ÌÓ„Ó ÔÓÎfl p = {0, 1,..., p – 1} ‰Îfl p 2(mod 4), p = a2 + b2 Ë˝ÎÂÏÂÌÚ˚ ÍÓ̘ÌÓ„Ó ÔÓÎfl p 2 ‰Îfl p 3(mod 4), p = a ÏÓ„ÛÚ ÓÚÓ·‡Ê‡Ú¸Òfl ̇ ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ˆÂÎ˚ı „‡ÛÒÒÓ‚˚ı ˜ËÒÂÎ Ò ËÒÔÓθÁÓ‚‡ÌËÂÏ ÙÛÌ͈ËË k ( a − bi ) µ( k ) = k − ( a + bi ), k = 0,..., p − 1, „‰Â [.] Ó·ÓÁ̇˜‡ÂÚ ÓÍÛ„ÎÂÌË ‰Ó ·ÎËpÊ‡È¯Â„Ó ˆÂÎÓ„Ó „‡ÛÒÒÓ‚Ó„Ó ˜ËÒ·. åÌÓÊÂÒÚ‚Ó ‚˚·‡ÌÌ˚ı ˆÂÎ˚ı „‡ÛÒÒÓ‚˚ı ˜ËÒÂÎÒ ÏËÌËχθÌ˚ÏË ÌÓχÏË É‡ÎÛ‡ ̇Á˚‚‡ÂÚÒfl ÒÓÁ‚ÂÁ‰ËÂÏ.
í‡ÍÓ Ô‰ÒÚ‡‚ÎÂÌË ‰‡ÂÚÌÓ‚˚È ÒÔÓÒÓ· ÔÓÒÚÓÂÌËfl ÍÓ‰Ó‚ ‰Îfl ‰‚ÛÏÂÌ˚ı Ò˄̇ÎÓ‚. ê‡ÒÒÚÓflÌË å‡ÌıÂÈχ·˚ÎÓ ‚‚‰ÂÌÓ ‰Îfl ÚÓ„Ó, ˜ÚÓ·˚ Ó·ÂÒÔ˜ËÚ¸ ÔËÏÂÌÂÌËÂ Í éÄå-ÔÓ‰Ó·Ì˚Ï Ò˄̇·ÏÏÂÚÓ‰Ó‚ ‡Î„·‡Ë˜ÂÒÍÓ„Ó ‰ÂÍÓ‰ËÓ‚‡ÌËfl. ÑÎfl ÍÓ‰Ó‚ ̇‰ ÒÓÁ‚ÂÁ‰ËflÏË „ÂÍÒ‡„Ó̇θÌ˚ı Ò˄̇ÎÓ‚ ÏÓÊÂÚ ·˚Ú¸ ÔËÏÂÌÂ̇ ‡Ì‡Îӄ˘̇fl ÏÂÚË͇ ̇ ÏÌÓÊÂÒڂˆÂÎ˚ı ˜ËÒÂÎ ùÈ̯ÚÂÈ̇–üÍÓ·Ë. é̇ fl‚ÎflÂÚÒfl Û‰Ó·ÌÓÈ ‰Îfl ·ÎÓÍÓ‚˚ı ÍÓ‰Ó‚ ̇‰ÚÓÓÏ (ÒÏ., ̇ÔËÏÂ, [Hube93], [Hube94]).ê‡ÒÒÚÓflÌË ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡èÛÒÚ¸ (Vn , p− ) – ÛÔÓfl‰Ó˜ÂÌÌÓ ÏÌÓÊÂÒÚ‚Ó Ì‡ Vn = {1,..., n}. èÓ‰ÏÌÓÊÂÒÚ‚Ó IÏÌÓÊÂÒÚ‚‡ Vn ̇Á˚‚‡ÂÚÒfl ˉ‡ÎÓÏ, ÂÒÎË x ∈ I Ë ËÁ ÛÒÎÓ‚Ëfl y p− x ÒΉÛÂÚ, ˜ÚÓ y ∈ I.ÖÒÎË J ⊂ Vn , ÚÓ (J) – ̇ËÏÂ̸¯ËÈ Ë‰Â‡Î ÏÌÓÊÂÒÚ‚‡ Vn , ÒÓ‰Âʇ˘ËÈ J.
ê‡ÒÒÏÓÚËÏ ‚ÂÍÚÓÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó qn ̇‰ ÍÓ̘Ì˚Ï ÔÓÎÂÏ q. ê-‚ÂÒ ˝ÎÂÏÂÌÚ‡x = ( x1 ,..., x n ) ∈qn ÓÔ‰ÂÎflÂÚÒfl Í‡Í Í‡‰Ë̇θÌÓ ˜ËÒÎÓ Ì‡ËÏÂ̸¯Â„Ó Ë‰Â‡Î‡ÏÌÓÊÂÒÚ‚‡ Vn , ÒÓ‰Âʇ˘Â„Ó ÌÂÒÛ˘Â ÏÌÓÊÂÒÚ‚Ó ı: wp(x) = |〈supp(x)〉|, „‰Â supp(x) == {i: xi ≠ 0}. ê‡ÒÒÚÓflÌË ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡ (ÒÏ.
[BGL95]) ÂÒÚ¸ ÏÂÚË͇ ̇qn , ÓÔ‰ÂÎÂÌ̇fl ͇Íw P(x – y).ÖÒÎË qn Ò̇·ÊÂÌÓ ‡ÒÒÚÓflÌËÂÏ ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡, ÚÓ ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ëÏÌÓÊÂÒÚ‚‡ qn ̇Á˚‚‡ÂÚÒfl ÍÓ‰ÓÏ ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡. ÖÒÎË V n Ó·‡ÁÛÂÚˆÂÔ¸ 1 ≤ 2 ≤ ... ≤ n, ÚÓ ÎËÌÂÈÌ˚È ÍÓ‰ ë ‡ÁÏÂÌÓÒÚË k, ÒÓÒÚÓfl˘ËÈ ËÁ ‚ÒÂı ‚ÂÍÚÓÓ‚(0,..., 0, an − k +1 ,..., an ) ∈qn , fl‚ÎflÂÚÒfl Òӂ¯ÂÌÌ˚Ï ÍÓ‰ÓÏ ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡Ò ÏËÌËχθÌ˚Ï ‡ÒÒÚÓflÌËÂÏ (ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡) d P∗ (C ) = n − k + 1. ÖÒÎË VnÓ·‡ÁÛÂÚ ‡ÌÚˈÂÔ¸, ÚÓ ‡ÒÒÚÓflÌË ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡ ÒÓ‚Ô‡‰‡ÂÚ Ò ıÂÏÏËÌ„Ó‚ÓÈ ÏÂÚËÍÓÈ.ê‡ÒÒÚÓflÌË ‡Ì„‡èÛÒÚ¸ q – ÍÓ̘ÌÓ ÔÓÎÂ, = q – ‡Ò¯ËÂÌË ÒÚÂÔÂÌË m ÔÓÎfl q Ë = n –‚ÂÍÚÓÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó ‡ÁÏÂÌÓÒÚË n ̇‰ . ÑÎfl β·Ó„Ó a = (a1 ,..., an ) ∈ „Ӈ̄, rank(a), ÓÔ‰ÂÎflÂÚÒfl Í‡Í ‡ÁÏÂÌÓÒÚ¸ ‚ÂÍÚÓÌÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ ̇‰ q ,ÔÓÓʉ‡ÂÏÓ„Ó ÏÌÓÊÂÒÚ‚ÓÏ {a1 ,..., an }.
ê‡ÒÒÚÓflÌË ‡Ì„‡ ÂÒÚ¸ ÏÂÚË͇ ̇ , ÓÔ‰ÂÎÂÌ̇fl ͇Írank(a – b).èÓÒÍÓθÍÛ ‡ÒÒÚÓflÌË ‡Ì„‡ ÏÂÊ‰Û ‰‚ÛÏfl ÍÓ‰Ó‚˚ÏË ÒÎÓ‚‡ÏË Ì ·Óθ¯Â, ˜ÂÏı˝ÏÏËÌ„Ó‚Ó ‡ÒÒÚÓflÌË ÏÂÊ‰Û ÌËÏË, ‰Îfl β·Ó„Ó ÍÓ‰‡ ë ⊂ Â„Ó ÏËÌËχθÌÓ ‡Ò-É·‚‡ 16. ê‡ÒÒÚÓflÌËfl ‚ ÚÂÓËË ÍÓ‰ËÓ‚‡ÌËfl251∗∗ÒÚÓflÌË (‡Ì„‡) d RK(C ) ≤ min{m, n − log q m | C | +1}. äÓ‰ ë Ò d RK(C ) = n − log q m | C | +1,∗n < m, ̇Á˚‚‡ÂÚÒfl ÍÓ‰ÓÏ É‡·Ë‰ÛÎË̇ (ÒÏ. [Gabi85]).
äÓ‰ ë Ò d RK(C ) = m, m ≤ n,̇Á˚‚‡ÂÚÒfl ÍÓ‰ÓÏ ‡ÒÒÚÓflÌËfl ÔÓÎÌÓ„Ó ‡Ì„‡. í‡ÍÓÈ ÍÓ‰ ËÏÂÂÚ Ì ·ÓΠq n˝ÎÂÏÂÌÚÓ‚. å‡ÍÒËχθÌ˚Ï ÍÓ‰ÓÏ ‡ÒÒÚÓflÌËfl ÔÓÎÌÓ„Ó ‡Ì„‡ ÔÓ͇Á˚‚‡ÂÚÒfl ÍÓ‰‡ÒÒÚÓflÌËfl ÔÓÎÌÓ„Ó ‡Ì„‡ Ò qn ˝ÎÂÏÂÌÚ‡ÏË; ÓÌ ÒÛ˘ÂÒÚ‚ÛÂÚ ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡,ÍÓ„‰‡ m ‰ÂÎËÚ n.åÂÚËÍË É‡·Ë‰ÛÎË̇–ëËÏÓÌËÒ‡ê‡ÒÒÏÓÚËÏ ‚ÂÍÚÓÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó qn (̇‰ ÍÓ̘Ì˚Ï ÔÓÎÂÏ q) Ë ÍÓ̘ÌÓÂÒÂÏÂÈÒÚ‚Ó F = {Fi: i ∈ I} Â„Ó ÔÓ‰ÏÌÓÊÂÒÚ‚, Ú‡ÍËı ˜ÚÓU Fi = qn .
ç ӄ‡Ì˘˂‡fli ∈IÓ·˘ÌÓÒÚË, ÏÓÊÌÓ Ò˜ËÚ‡Ú¸, ˜ÚÓ F – ‡ÌÚˈÂÔ¸ ÎËÌÂÈÌ˚ı ÔÓ‰ÔÓÒÚ‡ÌÒÚ‚ qn . F-‚ÂÒ wF‚ÂÍÚÓ‡ x = ( x1 ,..., x n ) ∈qn ÓÔ‰ÂÎflÂÚÒfl Í‡Í Í‡‰Ë̇θÌÓ ˜ËÒÎÓ Ì‡ËÏÂ̸¯Â„ÓÔÓ‰ÏÌÓÊÂÒÚ‚‡ J ËÁ I, Ú‡ÍÓ„Ó ˜ÚÓ x ∈U Fqn .i ∈IåÂÚË͇ ɇ·Ë‰ÛÎË̇–ëËÏÓÌËÒ‡ (ËÎË F-‡ÒÒÚÓflÌËÂ, ÒÏ. [GaSi98]) ÂÒÚ¸ ÏÂÚË͇̇ qn , ÓÔ‰ÂÎÂÌ̇fl ͇Íw F(x – y).ï˝ÏÏËÌ„Ó‚‡ ÏÂÚË͇ ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ ÒÎÛ˜‡˛, ÍÓ„‰‡ Fi, i ∈ I Ó·‡ÁÛ˛Ú Òڇ̉‡ÚÌ˚È ·‡ÁËÒ. åÂÚË͇ LJ̉ÂÏÓ̉‡ – ˝ÚÓ F-‡ÒÒÚÓflÌËÂ Ò Fi, i ∈ I, ÍÓÚÓ˚ fl‚Îfl˛ÚÒflÒÚÓηˆ‡ÏË Ó·Ó·˘ÂÌÌÓÈ Ï‡Úˈ˚ LJ̉ÂÏÓ̉‡.
åÂÚË͇ÏË É‡·Ë‰ÛÎË̇–ëËÏÓÌËÒ‡fl‚Îfl˛ÚÒfl Ú‡ÍÊÂ: ‡ÒÒÚÓflÌË ‡Ì„‡, ‡ÒÒÚÓflÌË b-Ô‡ÍÂÚ‡, ÍÓÏ·Ë̇ÚÓÌ˚ ÏÂÚËÍË É‡·Ë‰ÛÎË̇ (ÒÏ. ê‡ÒÒÚÓflÌË ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ÒÓÏÌÓÊÂÒÚ‚‡).ê‡ÒÒÚÓflÌË êÓÁÂÌ·Î˛Ï‡–ñÙ‡Òχ̇èÛÒÚ¸ Mm,n(Fq ) – ÏÌÓÊÂÒÚ‚Ó ‚ÒÂı m × n χÚˈ Ò ˝ÎÂÏÂÌÚ‡ÏË ËÁ ÍÓ̘ÌÓ„Ó ÔÓÎflFq (‚ Ó·˘ÂÏ ÒÎÛ˜‡Â ËÁ β·Ó„Ó ÍÓ̘ÌÓ„Ó ‡ÎÙ‡‚ËÚ‡ = {a1 ,..., aq }). çÓχ êÓÁÂÌ·Î˛Ï‡–ñÙ‡Òχ̇ || ⋅ ||RT ̇ Mm,n(Fq ) ÓÔ‰ÂÎflÂÚÒfl ÒÎÂ‰Û˛˘ËÏ Ó·‡ÁÓÏ: ÂÒÎË m = 1 Ëa = (ξ1 , ξ 2 ,..., ξn ) ∈ M 1,n, ÚÓ || 01,n ||RT = 0 Ë || a ||RT = max{i | ξi ≠ 0} ‰Îfl a ≠ 0 1,n; ÂÒÎËmA = ( a1 ,..., am )T ∈ Mm, n ( Fq ), a j ∈ M1, n ( Fq ), 1 ≤ j ≤ m, ÚÓ || A || RT =∑ || a j || RT .j =1ê‡ÒÒÚÓflÌË êÓÁÂÌ·Î˛Ï‡–ñÙ‡Òχ̇ ([RoTs96]) ÂÒÚ¸ ÏÂÚË͇ (·ÓΠÚÓ„Ó, ÛθڇÏÂÚË͇) ̇ Mm,n(Fq ), ÓÔ‰ÂÎÂÌ̇fl ͇Í|| A − B || RT .ÑÎfl Í‡Ê‰Ó„Ó Ï‡Ú˘ÌÓ„Ó ÍÓ‰‡ C ⊂ Mm, n ( Fq ) Ò q k ˝ÎÂÏÂÌÚ‡ÏË ÏËÌËχθÌÓÂ∗‡ÒÒÚÓflÌË (êÓÁÂÌ·Î˛Ï‡–ñÙ‡Òχ̇) d RT(C ) ≤ mn − k + 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
