Метрические следствия условия различимости точек в Bn

Рассмотрим множество В булевых векторов? размерности п, имеющее мощность 1&-п1 ^ 2,. Алгебраически Вп трактуется как линейное пространство над двухэлементным полем Fz = {{D, ij}. Иначе говоря, под суммой векторов Вп понимается покомпонентная сумма по модулю 2, так что? +рь = р, с геометрической точки зрения Зп естественно интерпретируется как множество вершин единичного п> -мерного куба. Одна из наиболее важных.

I’U прикладных интерпретаций В связана с тем, что булевы векторы могут рассматриваться как сообщения, передаваемые по некоторому каналу связи.

— ч Hs Г 1.

Будем считать, что в & = l^j введена норма Хэммин-га w (называемая также весом), равная числу ненулевых компонент вектора °с е- 3п — иначе говоря п. vr (Z) = ZL^l ,.

L = ± сумма обычная, а не mocL Z). Эта норма порождает метрику Хэмминга р: для Х>р&В>>ъ) f (Z, jb) = 2a (Z-JS), так что вес vf (?) совпадает с расстоянием 31 до точки Для ряда прикладных задач представляет интерес изучение.

0 пподмножеств о, экстремальных (или близких к экстремальным) относительно какого-либо критерия, определяемого метрикой р. Критерием может быть сумма расстояний мевду точками подмножества, максимальное расстояние между его точками и т. д.- величины такого типа мы будем называть метрическими функционалами. Свойства экстремальных подмножеств могут использоваться, например, при рассмотрении конструкций теории помехоустойчивого кодирования. Изучение этих вопросов представляет и теоретический интерес, поскольку дает сведения о том, «как устроено» пространство & с метрической точки зрения.

Целью данной диссертационной работы является изучение свойств некоторых экстремальных подмножествглавным образомполучение оценок для экстремальных значений соответствующих метрических функционалов. Общая черта изучаемых задач состоит в том, что исследуются подмножества, отвечающие «наиболее компактным», в том или ином смысле, расположениям точек в В’г — именно, в качестве 1фитериев рассматриваются минимум среднего расстояния, минимум максимального расстояния до заданной точки и некоторые другие величины того же типа. Все эти задачи изучаются на основе единого подхода, опирающегося на применение одного теоретико-информационного неравенства, которое мы в данной работе называем условием различимости точек в & Прежде чем описать этот подход, перечислим рассмотренные задачи и укажем их связь с известными результатами.

Расстояние jd позволяет определить для любой точки ot6 Ь метрическую окрестность радиуса t (шар) мощность такой окрестности KW = z С п % где.

Гк к'-° W — биномиальный коэффициент. п>п.

При рассмотрении конструкций в о часто возникает необходимость определить t из уравнения й=s' (ол) или из системы неравенств ь-1. * г к к^о п ' ЫО.

0.2) гу П где S — заданное число, S <^. Геометрически уравнению (0.1) отвечает задача отыскания радиуса шара по заданной мощности S, а системе (0.2) — более общая задача отыскания радиуса наименьшего шара, содержащего не менее 5 точек-эту величину мы будем называть упаковочным радиусом для мощности S в 3* .

Предложенный в данной работе подход позволяет получить в достаточно широком диапазоне мощностей s точное аналитическое выражение для решения уравнения (0.1) как функции от ft/, 5 и распространить этот результат на решения системы (0.2). Помимо этого при произвольных S для упаковочного радиуса получены оценки сверху и снизу, которые являются асимптотически близкими при ^s—. Отметим, что решение задачи об упаковочном радиусе опирается на полученное в данной работе уточнение асимптотического разложения для биномиальной суммы? С^, которое представляет и самостоятельный инк = 0 терес.

Обозначим 01 = (X Cs) совокупность всех 5 -точечных подмножеств В^. Для любого множества Й = — Вг определим метрический функционал, называемый диаметром: и положим.

А. (n.s) — тгп.

Минимум диаметра тесно связан с упаковочным радиусом. В работе получены верхняя и нижняя границы для cLlriin, которые являются асимптотически близкими.

Помимо того, что оценки для упаковочного радиуса и минимального диаметра представляют самостоятельный интерес, в данной работе они используются как вспомогательные при изучении метрических функционалов аддитивной структуры.

Назовем весом множества, А J — & следующий функционал:

WCfli) = ILvrCZj) = Е f&M (0<в) оСу^А Uy-ae и положим.

W^s) = тйг М/Сй) в Ol (s).

Нижнял граница для в некотором диапазоне мощностей 5 известна [23] - она использовалась при оценивании параметров каскадных кодов (см., например, [э]). В настоящей работе получена несколько более сильная граница, справедливая при произвольных S, а также показано, что она асимптотически не-улучшаема. Наряду с V/ мы исследуем более общий функционал называемый обобщенным весом: wYA) =? чЫхЛ.

Zj В (где f — некоторая функция. Для случая, когда f моно. у тонно возрастает и выпукла, получены границы Wmin. s) ,.

— 7 аналогичные границам для ^min.

Другой тип изучаемых нами аддитивных метрических функцио— налов определяется попарными расстояниями между элементами подмножеств В. Для ^t^j^A обозначим J^yJ^C^i^j) • Пусть опять? — некоторая функциятогда можно определить величину и положить.

При ^(z) = 2 получаем важный частный случай — сумму попарных расстояний ft :

Zl^J) — (о.б) ее минимум обозначим я nnin¦ п} S).

По аналогии с физической задачей о взаимодействии заряженных частиц функционал вида (0.5) называют энергией множества й. Изучение асимптотического поведения минимума энергии для случая монотонно убывающих f проводилось в работах [х2,1з]. В [l4j изучался максимум ft* для = У? J S^ it+i * а в [iej — 0г3 s) при S ^ а+1, для случая, когда.

Y монотонно возрастает и удовлетворяет условию i/z [4(d)+Ч>(3)1 (0.7).

В работе [15] вычислено точное значение &mtlv (a, s) при гО IX~i.

S = <,, и показано, что этот минимум достигается на подкубе размерности 0^-4-). Известна также [21] оценка для максимума ft (ft), которая использовалась при получении кодовых границ.

18,24.

В настоящей работе установлены нижняя и верхняя границы для (я-, при произвольных /г, 5 и показано, что эти границы являются асимптотически близкими при S —.

D Y.

Аналогичные оценки получены для (/г, s) в случае, когда функция У9 монотонно возрастает и выпукла.

В ряде работ изучались экстремальные свойства шаров в В. Так, известно [l4], что шар единичного радиуса доставляет при п.^ IS максимум энергии ft^ для Y^) = /4, а также [1б], при /г > 8, минимум в случае, если f монотонно возрастает и удовлетворяет условию (0.7). Известна [25] теорема Катоны, устанавливающая, что шар в В>ъ имеет минимальную границу, и некоторые ее обобщения [l?]. Сюда же можно отнести очевидное свойство, состоящее в том, что шар произвольного радиуса с центром в 0 имеет наименьший вес W в классе равномощных ему подмножеств В*1.

В настоящей работе установлено следующее экстремальное свойство шара ~Vn в метрике Хэмминга: при любом фиксированном t для достаточно больших значений размерности П шар радиуса t в В доставляет строгий минимум функционалу энергии fL, определяемому (0.6), то есть шар имеет меньшее среднее расстояние между точками, чем любое равномощное ему множествопри этом значение размерности, начиная с которого можно гарантировать экстремальность шара Vn, указывается в явном виде.

Как упоминалось выше, исследование перечисленных задач проводится на базе единого подхода. Напомним некоторые теоретико-информационные определения и факты, которые можно найти, например, в [з, 4] .

Для случайной величины? , принимающей значения в конечном множестве X = fVj с расцределением вероятностей Р: Р (? = = Р&определяется энтропия распределения этой величины.

Ж?) = pj %pj, 1.

0.8) при этом полагают О locjO = D — под tag X обычно понимают Еод^ х.

Пусть f = (. ^ Tyv) ~ слУчайный вектор, принимающий значения в множестве Х^Ххх с распределением вероятностей Р. Каждая из его компонент Тi также является случайной величиной, распределение которой Pi однозначно определяется совокупным распределением Р. Если.

— энтропия исходного распределения, а Л (J-L) — энтропия распределения iтой компоненты, то справедливо соотношение:

Ш) X), (0.9) i — i причем равенство в (0.9) имеет место тогда и только тогда, когда компоненты вектора Т взаимно независимы.

Рассмотрим теперь произвольное 5 -точечное множество й s Вп, й- {Zj} и цредположим, что векторы oLj выписаны в виде строк (Ъ * п.) -матрицы. Пусть зе- - доля единиц в Iтом столбце этой матрицы, тогда (i, очевидно, доля нулей. Рассмотрим при функцию (0.10) называемую функцией энтропии. Если предположить, что на, А задано равномерное распределение вероятностей, = Vs «то, как легко проверить, из определений (0.8), (0.10) и неравенства (0.9) вытекает соотношение п, gV^) = (0.11).

Известно, что (0.11) допускает интерпретацию как необходимое условие того, что все строки в соответствующей булевой матрице попарно различны [ь], поэтому неравенство (0.11) мы будем называть условием различимости.

Хорошо известное соотношение (0.11) использовалось многими авторами при решении задач комбинаторной природы, например — задач оптимального поискаобзор ряда результатов по этой проблематике имеется, в частности, в [V/.

Отметим, что условие различимости (0.11) является по своей природе чисто теоретико-вероятностнымв его формулировке и при его выводе не используются никакие метрические соображения. Тем не менее, оно налагает специфические ограничения на структуру точечных множеств в В, и — косвенным образомна их метрические свойства. Поэтому, как продемонстрировано в настоящей работе, условие различимости удается эффективно использовать и при изучении некоторых вопросов, связанных с метрической структурой пространства &.

Материал распределен по главам следующим образом.

В главе I получено уточнение асимптотического разложения.

— ь ^ для шаровой мощности И С, как функции ri, t (§ I), v= о точное решение задачи об упаковочном радиусе в некотором диапазоне мощностей 5 (§§ 2,3), оценки упаковочного радиуса для произвольной мощности (§ 4) и оценки для минимального да-аметра Sточечных множеств в В (§ 5).

В главе П оценивается минимальное значение аддитивных метрических функционалов W, (§ I) и Fl, (§ 2) для случая выпуклых, монотонно возрастающих^, и обсуждаются полученные результаты (§ 3).

В главе Ш изучается вопрос о том, при каких условиях шар в ?5 представляет собой множество с минимальной суммой расстояний г .

В Приложение вынесено исследование свойств и получение различных оценок для используемых в основном изложении функций k, ч, у .

Вспомогательные утверждения в данной работе формулируются либо как леммы (утверждения содержательного характера), либо как предложения (утверждения чисто технического характера). Нумерация теорем, лемм, предложений двойная. Первая цифра указывает номер главы, вторая — номер утверждения данного типа в главетот же принцип применяется и при нумерации формул (при этом Введение имеет номер 0, Приложение — номер 4).

Результаты диссертационной работы докладывались на заседаниях Советско-германского семинара по дискретной математике 1982 и 1983 гг., неоднократно обсуждались на семинарах в Вычислительном центре АН СССР, в Институте проблем передачи информации, на факультете вычислительной математики и кибернетики МГУ. Основные результаты опубликованы j^I9, 2о].

Автор выражает признательность В. К. Леонтьеву и А. А. Петрову за поддержку, оказанную данной работе, а также И. Г. Поспелову за многочисленные полезные обсуждения.

1. Дискретная математика и математические вопросы кибернетики./ под ред. О. Б. Дупанова и С.В.Яблонского/ T.1. М.: Наука, 1974. — 312 с.

2. Фано Р. Передача информации. Статистическая теория связи. -М.: Мир, 1965. 438с.

3. Файнстен А. Основы теории информации. М.: ИЛ, I960, — 140с.

4. Яглом A.M., Яглом И. М. Вероятность и информация. М.:Наука, 1973. — 512 с.

5. Сачков В. Н.

Введение

в комбинаторные методы дискретной математики. М.: Наука, 1982. — 382 с.

6. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971. — 477 с.

7. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976. — 594 с.

8. Касами Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования. М.: Мир, 1978. — 576с.

9. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. — 744 с.

10. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М.: Наука, 1977. — 368 с.

11. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. М.: Наука, 1979. — 352 с.

12. Круглова Т. Н. Об асимптотическом методе решения задачи о зарядах. В кн.: Проблемы кибернетики. Вып. 13. М.: Наука, 1965, с.29−44.

13. Леонтьев В. К. Асимптотически устойчивые расположения зарядов в вершинах единичного П, -мерного куба. В кн.: Проблемы кибернетики. Вып. 23. М.: Наука, 1970, с.27−42.

14. Перина Е. В. 0 множествах вершин /7- -мерного единичного куба с максимальной энергией. В кн.: Проблемы кибернетики. Вып. 27. М.: Наука, 1973, с.279−292.

15. Воронин В. П. 0 множествах вершинмерного единичного куба с минимальной суммой попарных расстояний. В кн.: Вопросы кибернетики. Вып. 64. Комбинаторный анализ и теория графов. М.: Наука, 1980, с.48−57.

16. Мовсисян Г. Л. Об одном функционале, заданном на подмножествах вершин 1Ъмерного единичного куба. Еритасард гиташ-хатог. Бнакан гитуюнтир, Молодой научн.работник. Естеств.н., 1980, № 2/32, с.88−92.

17. Асланян Л. А. Изопериметрическая задача и смежные экстремальные задачи для дискретных пространств. В кн.: Проблемы кибернетики. Вып. 36. М.: Наука, 1979, с.85−128.

18. Бассалыго Л. А. Новые верхние границы для кодов, исправляющих ошибки. Проблемы передачи информации, I, № 4, с.41−44.

19. Федоров С. А. Об одном экстремальном свойстве шаров в пространствах Хэмминга. Докл. АН СССР, 1980, 254, J* 6, с.1353−1357.

20. Федоров С. А. Об одном подходе к оцениванию мощно. сти и меры шаров в двоичных пространствах Хэмминга. Докл. АН СССР, 1984, 276, & 6, с.1360−1364.

21. Joshi D*D" A note an upper bounds for minimum distance codes. Inf. Control, 1958, 1, N3, p.289−295.

22. Feller W. On the normal approximation to the binomial distribution. Ann. Math. Statist., 1945, 16, N 4, p.319−329.

23. Justesen J. A class of constructive asymptoticaly good algebraic codes. IEEE Trans. Inform. (Theory, 1972, 18, p.652−656.

24. Johnson S.M. A new upper bound for errorcorrecting codes. -IEEE Trans. Infoira. Theory, 1962, 8, p.203−207.

25. Katona G. The Hamming sphere has minimum boundary. -Studia Scient. Math. Hungaiica, 1975, 10, p.131−140.

26. Chernoff H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist., 1952, 23, p. 493−507.