Метрические следствия условия различимости точек в Bn тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Глава I. Параметры шарового расположения точек в &

Глава П. Оценки для минимальных значений аддитивных метрических функционалов в В>

Глава Ш. Одно экстремальное свойство шаров в

Рассмотрим множество В булевых векторов £ размерности п , имеющее мощность 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^y- J^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.