Квазирадоновы меры. Метод орбит в исследовании совершенных кодов тема автореферата и диссертации по математике, 01.01.01 ВАК РФ

ИНСТИТУТ МАТЕМАТИКИ ИМ. С. Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК

На правах рукописи

МАЛЮГИН Сергей Артемьевич

КВАЗИРАДОНОВЫ МЕРЫ. МЕТОД ОРБИТ В ИССЛЕДОВАНИИ СОВЕРШЕННЫХ КОДОВ

01.01.01 - математический анализ 01.01.09 - дискретная математика и м ат е м ат и ч ее к ая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск 2002

Диссертация выполнена в Институте математики им. С. Л. Соболева Сибирского отделения РАН.

Официальные оппоненты: доктор физико-математических наук,

профессор A.B. Бухвалов,

доктор физико-математических наук, профессор В. А. Васильев,

доктор физико-математических наук, профессор В. К. Леонтьев.

Ведущая организация: Московский государственный

университет им. М. В. Ломоносова.

Защиту диссертации состоится « Я '0 » О К- Д оузД. 2002 г. в часов на заседании специализированного совета Д. 003.015.03 в Институте математики им. С. Л. Соболева СО РАН по адресу: 630090 Новосибирск, пр. Академика Коитюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева СО РАН.

Автореферат разослан «. 3 Р» сея >чх /рсялш г.

Ученый секретарь специализированного совета д.ф.-м.н.

%OAjJ

Н. С. Даирбеков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В современной теории векторных мер можно выделить два направления, слабо связанных друг с другом.

Первое направление - изучение мер со значениями в нормированных или в локально выпуклых пространствах - начиная с классических работ С. Бохнера, И. М. Гельфанда, Н. Данфорда и Б. Петтиса второй половины 1930-х годов. В настоящее время оно представляет собой теорию с богатыми приложениями и хорошо освещено в монографической литературе, см. книги Н. Динкуляну [13], Дж. Дистеля и Дж. Улья [12] о векторных мерах, а также соответствующий том из трактата Н. Бурбаки.

Второе направление - изучение мер, принимающих значения из упорядоченного векторного пространства. Здесь вместо топологии используется сходимость, связанная с порядком, а роль топологической полноты играет порядковая полнота. Такие меры как самостоятельный объект исследования возникли, по видимому, в связи с вопросом об аналитическом представлении линейных операторов в полуупорядоченных пространствах, см. монографии Л. В. Канторовича, Б. 3. Вулиха и А. Г. Пинскера [5] и Б. 3. Вулиха [4]. ' Начиная с 1950-х годов, под влиянием теории упорядоченных векторных пространств для булевых мер стали рассматриваться вопросы, характерные для классической теории меры (В. И. Соболев, Б. 3. Ву-лих, Д. А. Владимиров и др.). Меры со значениями в векторных решетках с тех же позиций интенсивно изучал М. Райт в серии публикаций с конца 1960-х годов. После этих работ интерес к мерам в упорядоченных пространствах резко возрос. За истекший период в этом направлении накоплен весьма богатый материал.

В настоящей работе предлагается единый подход к указанным выше двум направлениям в теории меры на основе концепции решеточ-но нормированного пространства и мажорируемого оператора. Дело в том, что специальными случаями решеточно нормированного пространства являются как нормированные и локально выпуклые пространства, так и векторные решетки. Поэтому многие встречающиеся в математической литературе векторные меры являются мерами со значениями в РНП. Понятие решеточно нормированного пространства и мажорируемого оператора появилось во второй половине 1930-х го-

дов в работах Л. В. Канторовича. Теория мажорируемых операторов, как самостоятельное направление, сформировалась в 80-ые годы в работах А.Г.Кусраева, С. С. Кутателадзе [6, 7, 8, 9, 14], и их учеников.

В качестве отправной точки к такому подходу было взято понятие радоновой меры. На основе понятия радоновой меры строится теория интегрирования в хорошо известном трактате Н. Бурбаки. Дальнейшее развитие эта теория получила в книге Л. Шварца [16].

Но при переходе от скалярных мер к мерам со значениями в частично упорядоченном пространстве возникают существенно новые нюансы. Здесь следует подробнее остановиться на свойстве слабой (т-дистрибутивности К--пространства. В исследованиях Л. В. Канторовича, К. Маттеса, М. Райта, Д. Фремлина, С. Хураны, Б. Ричана и др. было показано, что А'-пространства со свойством слабой сг-дистрибутивности являются экстенсорами. Это означает, что линейные секвенциально о-непрерывные операторы со значениями в таких пространствах продолжаются с векторной решетки на борелевскую надстройку, меры продолжаются с алгебры множеств на с-алгебру, в таких пространствах можно строить теорию интегрирования по классической схеме Даниэля. Причем это свойство является характеристическим, т. е. оно не только достаточно, но и необходимо для реализации вышеуказанных конструкций.

Тем не менее, в последнее время интенсивно развивается функциональный анализ на базе произвольного порядково полного упорядоченного пространства. Прежде всего, это булевозначный анализ векторных решеток, см. [б, 7]. Никаких дополнительных ограничений на Л'-пространство в этой теории не налагается. Исходя из всего этого следует ожидать, что какой-то фрагмент теории меры можно развивать для произвольных ./^-пространств. В данной диссертации как раз предпринята такая попытка.

Во второй части диссертации рассмотрены некоторые задачи теории кодирования. Важную роль в теории кодирования играют совершенные двоичные коды. Далее рассматриваются совершенные двоичные коды длины п с минимальным расстоянием 3. Известно, что такие коды существуют лишь при п~ 2к — 1, где А: € N. Код называется линейным, если его слова образуют линейное подпространство. Линейные совершенные коды с минимальным расстоянием 3 называются кодами Хемминга. Существует единственный, с точностью до

перестановки координат, код Хемминга длины п. Известны также нелинейные совершенные коды с параметрами кода Хемминга, которые были впервые построены Ю. Л Васильевым [3]. Они появляются начиная с п = 15.

В последние годы интерес к нелинейным кодам сильно возрос. Появилось много новых конструкций: коды Хедена, коды Маллара, коды Лобстейна и Зиновьева, коды Фелпса—Соловьевой и др. Выли построены коды с различными интересными, даже неожиданными, свойствами: коды полного ранга, коды с тривиальным ядром и с тривиальной группой автоморфизмов, несистематические коды. Число нелинейных кодов настолько большое, что до сих пор отсутствует какая либо их классификация.

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

Теорема об интегральном представлении мажорируемого линейного оператора квазирадоновой мерой, теорема о продолжении квазирадоновой меры с плотной алгебры множеств на борелевскую сг-алгебру, теорема о существовании проективного предела последовательности и направленности квазирадоновых мер.

Получен новый критерий слабой сг-дистрибутивности Л'^-простран-ства.

Решена проблема моментов Гамбургера для последовательности векторов произвольного Кст-пространства с анализом случаев неоднозначной разрешимости. Решена проблема моментов Гамбургера для последовательности векторов в решеточно нормированном пространстве.

Получен аналог теоремы Бохнера для порядково непрерывных мажорируемых отображений.

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

Во второй части диссертации исследуются совершенные двоичные коды.

Получена конструктивная новая нижняя оценка числа совершенных двоичных кодов с расстоянием 3.

В «-мерном булевом кубе найдены все орбиты векторов веса не более семи относительно группы перестановочных автоморфизмов кода Хемминга.

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

В терминах орбит получен критерий несистематичности совершенного кода. Построены новые несистематические коды, дающие ответы на вопросы К. Т. Фелпса и М. Ли-Вана.

Методика исследований. В первой части применяются методы теории упорядоченных пространств, развитых в работах Л. В. Канторовича, Б. 3. Вулиха, Д. А. Владимирова, Л. Шварца, М. Райта, С. Хураны и др. Применяются также методы теории векторных мер и топологические методы.

Во второй части, применительно к совершенным кодам, развивается метод орбит.

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

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

Апробация работы. Автор выступал по теме диссертации на научных семинарах. В частности, на семинаре лаборатории функционального анализа, на семинаре по теории кодирования и семинаре по дискретному анализу лаборатории дискретного анализа Института математики СО РАН. Результаты диссертации докладывались также на:

- XII школе по теории операторов в функциональных пространствах (Тамбов, 1987г.),

- Сибирской конференции по прикладной и индустриальной математике (Новосибирск, 1994г.),

- III Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ - 98. Новосибирск, 1998г.),

- II Сибирской конференции по исследованию операций (Новосибирск 1998г.),

- Международной Сибирской конференции по дискретному анализу и исследованию операций (Новосибирск, 2000г.),

- IV молодежной школе по дискретной математике и ее приложениям (Москва, 2000г.),

- VII Международном семинаре по дискретной матетатике и ее приложениям (Москва, 2001г.),

- XIII Международной конференции по проблемам теоретической кибернетики (Казань, 2002г.).

Публикации. Результаты диссертации, представленные к защите, опубликованы . . в 21 работе [18-38]. Работы [18-24] выполнены в соавторстве с А. Г. Кусраевым.

Структура и объем работы. Диссе ртация состоит из введения к первой части, введения ко второй части и четырех глав, в каждой части по две главы. Список цитированной литературы состоит из 135 наименований. Объем диссертации 234 стр.

>

СОДЕРЖАНИЕ РАБОТЫ Часть первая: КВАЗИРАДОНОВЫ МЕРЫ

Глава I. Меры ограниченной векторной вариации. В этой главе изучаются общие, свойства' < квазирадоновых мер, принимающих значения в о-полном решеточно нормированном пространстве. Результаты, полученные в этой главе, являются основным инструментом для всего дальнейшего изложения.

В § 1 вводятся обозначения, даются определения, примеры, и отмечаются основные свойства решеточно нормированных пространств.

Решеточно нормированное пространство — это тройка (У, |-|,F), где У - векторное пространство, F — векторная решетка, а [ | : Y —> F+ — отображение, удовлетворяющее аксиомам: (1) Н = 0 <=> г = 0; (2) |Аж| = |А|И (Л £ R); (3) \х + у\ < М + Ы (x,y€Y).

Пусть (У, Е) — решеточно нормированное пространство. Линейный оператор Т : Е —У называется мажорируемым, если существует положительный оператор [I : Е —> F такой, что \Те\ < £/(|е|) (е £ Е). Оператор и называется мажорантой опрератора Т. Наименьшую мажоранту оператора Т обозначаем через |г|.

Пусть задана алгебра ¿2/ подмножеств из множества X. Говорят, что мера ¡1 : У имеет ограниченную векторную вариацию, если существует положительная мера V : «с/ —> такая, что |/л(Л)| < г/(Л) (А £ ¿г/). Наименьшая мера V, удовлетворяющая этому неравенству, называется векторной вариацией меры ¡л и обозначается через

В § 2 даются основные определения радоновой (квазирадоновой) и регулярной (квазирегулярной) меры.

Пусть X — вполне регулярное топологическое пространство; 2?х (соответственно — семейство всех открытых (замкнутых) под-

множеств X. Пусть ¿г/ - алгебра подмножеств множества X и Рассмотрим два направленных множества Хе — {К : К £ х П

, К С Е] и - {С : С £ &х Пй'.СС Е), элементы которых считаются упорядоченными по включению.

Мера /г : £/ У называется радоновой (квазирадоновой), если для любого Е € (для любого Е 6 2?х О справедливо равенство^

ц(Е) = о-Ит{1л{К) : К € ХЕ}.

Мера ¡1 : -» У называется регулярной (квазирегулярной), если для любого Е € (для любого Е £ 2?х О выполняется равенство ц(Е) = о-Нш{р(С) : в €

Наименьшую алгебру (сг-алгебру), порожденную семейством множеств

обозначаем через (соответственно, через

Теорема 1.2.2. Пусть мера ¡1 : „<</ —» У, имеющая ограниченную векторную вариацию, удовлетворяет одному из следующих двух условий:

(1) я/= Щ&Х П £/);

(2) я/ = Л л/) и Ц € Е-Ьса(£/, У).

В этом случае мера ц является квазирадоновой (квазирегулярной) тогда и только тогда, когда векторная вариация квазирадонова (квазирегулярна).

В теореме 1.2.5 доказано, что если на /^-пространстве Е выгюлня-

ется закон слабой (<т, оо)-дистрибутивности, то свойства квазирадо-новости и радоновости (а также квазирегулярности и регулярности) эквивалентны.

В § 3 доказана основная теорема об интегральном представлении мажорируемого оператора квазирадоновой мерой.

На вполне регулярном топологическом пространстве X рассмотрим векторную решетку функций Jz? С Сь{Х). Слабейшую топологию, в которой непрерывны все функции из будем обозначать через Если совпадает с исходной топологией на

X, то говорят, что 5£ порождает топологию

Теорема 1.3.1. Пусть векторная решетка С Сь(Х) содержит единичную функцию 1х и порождает топологию 2?х- Для мажорируемого оператора Т : -S? —У Y существует единственная квазирадо-нова а-аддитивная мера ¡л : х -+Y, удовлетворяющая условию

Tf = j fdvl

тогда и только тогда, когда > |Т|(1Л-) = V{A(lTb хк) : К G JfTxJ-

Далее доказывается теорема о продолжении квазирадоновой меры с плотной алгебры на борелевскую сг-алгебру.

Алгебра S2Í С 2х называется плотной, если выполняются условия:

(а) для любого V £ существует функция <р 6 S(£/)nCb(X) такая, что V = {х 6 X : tp(x) > 0};

(б) векторная решетка — S(Sif) П Сь(Х) порождает Э.х ■

Теорема 1.3.2. Пусть квазирадонова а-аддитивная мера fio : £/ —У Y определена на плотной алгебре — Тогда суще-

ствует единственная квазирадонова а-аддитивная мера /1 : 3$х —У Y, продолжающая

Обычно в таких теоремах о продолжении сг-аддитивных мер со значениями в упорядоченном пространстве предполагается выполнение в пространстве образов закона слабой (а, оо)-дистрибутивности или

слабой <т-дистрибутивности. На самом деле свойство слабой а-дистрибутивности Л'-пространства F необходимо для того, чтобы можно было продолжить любую положительную <т-аддитивную .F-значную меру с. произвольной алгебры множеств на порожденную и-алгебру. В этом случае продолжение осуществляется классическим методом Ка-ратеодори. В теореме 1.3.2 продолжение меры ро методом Каратеодо-ри невозможно.

В следствиях 1.3.2,1.3.3 и 1.3.4 приводятся некоторые классы квазирадоновых мер. Примеры, построенные в леммах 1.3.1 и 1.3.2, показывают, что все условия, налагаемые на меры в теореме о продолжении 1.3.2, являются существенными.

В § 4 строится тензорное произведение двух квазирадоновых мер.

Теорема 1.4.2. Пусть X и X' — полные по Чеху топологические пространства и р, : —> ^ > ^ ¿$Х' —>■ У — квазирадоповы а-

аддитивные меры. Тогда существует их произведение —> Z,

являющееся квазирадоновой а-аддитивной мерой. Для векторных вариаций справедливо неравенство < Если умножения х и о связаны кросс-равенством, то \р ® ц'\ =

Затем определяется интеграл от векторнозначной функции по векторной мере. Для корректности такого определения небходимо требо- ^ вать, чтобы интегрируемая функция была (г)-пределом ступенчатых векторнозначных функций. Доказывается один вариант теоремы Фу-бини.

Глава II. Применение квазирадоновых мер. В § 1 строится проективный предел согласованной последовательности квазирадоновых мер рп, заданных на полных по Чеху пространствах Хп (п £ N).

Теорема II.1.1. Для любой согласованной последовательности квазирадоновых а-аддитивных мер ßn : ¿$п -4- У (п е N) существует проективный предел р. = lim/in, являющийся единственной квазирегулярной мерой из ^ в У, для которой цп = ц о 7Г"1 (n G N).

Как оказалось, в случае, когда на Ä'-пространстве F не выполняется закон слабой (<т, оо)-дистрибутивности, проективный предел не обязательно будет квазирадоновой мерой (тем не менее, свойство сг-адцитивности проективного предела сохраняется). Этот факт является главной отличительной особенностью теории квазирадоновых мер.

Теорема 11.1.3. Пусть даны система ( Ха,Ка ) > 6 которой

V / а,0€А

все Ха компактны, и согласованная направленность квазирадоновых мер : 3$а —> У (а £ А). Тогда существует проективный предел

рь — 1ш1/:1а, являющийся единственной квазирадоновой мерой из ¿З^о в У, для которой //.„ = ц о я-"1 (л £ А).

Эта теорема усиливает результат Ю. Ричапа, полученный для положительных мер со значениями в пространстве, на которой выполняется закон слабой счетной дистрибутивности.

Далее строится бесконечное произведение квазирадоновых мер. В теореме II. 1.5, являющейся следствием теоремы II. 1.1, утверждается существование бесконечного произведения.

Теорема 11.1.6. Для К-пространства Р с фиксированной порядковой единицей 1 следующие условия эквивалентны:

(1) на F выполняется закон слабой (а, оо)-дистрибутивности;

(2) для любых о-полного К-нормированного пространства У с Р-значпой нормой, системы (А"п,7г" + 1) полных по Чеху топологических пространств и согласованной последовательности квазирадоновых <х-аддитивных мер р.п : ¿¡$п —> У и.г проективный предел Птрп является квазирадоновой мерой па ¿¡3^!

(3) для любой последовательности локально компактных пространств (Zn)n£N и любой последовательности квазирадоновых спек-

оо

тральных мер Хп : 3?п —> .Р их бесконечное произведение А„

п = 1

является квазирадоновой мерой на оо •

Эта теорема, показывает, что отсутствие квазирадоновости у бесконечного произведения квазирадоновых F-знaчныx мер характеризует Л'-пространства на которых не выполнен закон слабой (<т, оо)-дистрибутивности. Аналогичную характеристику имеют А'ст-простран-ства, на которых не выполнен закон слабой а-дистрибутивности.

Теорема 11.1.7. Пусть В — а-полная булева алгебра. Следующие условия эквивалентны:

(1) на В выполняется закон слабой а-дистрибутивности;

(2) для любой последовательности спектральных мер Хп : —> В

бесконечное произведение (£> Хп является квазирадоновой спектраль-

п = 1

ной мерой на борелевской а-алгебре пространства Б.14.

Неквазирадоновы произведения спектральных мер применяются далее в доказательстве теоремы фон Неймана о функциях от элементов произвольного Ка-простраиства.

Теорема 11.1.11. Для любого К „-пространства Р1 с порядковой единицей и любой последовательности (жп)п€м, элементов из Р существуют элемент х £ Р и последовательность функций такие, что хп = /„(ж) (п 6 14).

В § 2 изучается векторная проблема моментов.

Последовательность векторов {ук)^-1 из У называется мажорируемой по Хаусдорфу, если существует последовательность — ^ такая, что

. п п

)кскпУк+1 <£(-1 )ксц8к+,

к =О

—О

Теорема 11.2.1. Для данной последовательности из У .

существует единственная борелевская мера // : ^[од] —> У ограни- \ ченной векторной вариации, удовлетворяющая равенствам

1

Ук = 1 хк^\) (к ег+)

тогда и только тогда, когда последовательность {ук)1^-о мажорируема по Хаусдорфу.

В случае, когда У = Р и является Ка-пространством со свойством слабой а--дистрибутивности, аналог теоремы II.2.1 был недавно получен М. Духонем и И. Клуванеком. (Свойство слабой а-дистрибутивности требуется для доказательства векторного варианта теоремы Хелли).

Затем решается проблема моментов Гамбургера для позитивной последовательности из Ка-пространства Р.

о

Последовательность (в^^д из А называется позитивной по Гамбургеру, если

Здесь возникают некоторые сложности. Во-первых, поскольку А не К-пространство, нельзя применять теорему Канторовича о продолжении положительного оператора. Во вторых, из за того, что решение проблемы моментов Гамбургера может быть неоднозначным, возникает проблема «склеивания» некоторого семейства решений скалярных задач в одно решение векторной задачи. Поэтому сначала рассмотрено решение более простого случая — проблемы моментов Гамбургера в А'-пространстве без анализа случаев неоднозначной разрешимости.

Теорема II.2.2. Пусть А является К -пространством. Для данной последовательности (я^к-а из А существует положительная борелевская мера р : —> А такая, что

тогда и только тогда, когда последовательность (в/гпозитивна по Гамбургеру.

При переходе от Л'-пространства к Ка-пространству А теорема II.2.2 остается верной, но прежнее ее доказательство теряет силу.

После ряда подготовительных лемм (леммы 11.2.1 - II.2.4) дается полное решение проблемы моментов в произвольном А'^-пространстве.

Для комплексного числа А определяются центр С £ А и радиус А € А векторного круга Вейля—Гамбургера А'(А). Одна из идей, дающих решение задачи, состоит в том, параметры круга Вейля— Гамбургера задаются здесь не через ортогональные полиномы, а через величины, более удобные для задач в упорядоченных векторных пространствах.

Другая идея состоит в том, что удалось найти подходящий аналог теоремы Канторовича о тотальном продолжении положительного

п

8к+1ак(Т1 > О (Ы£=0 С Я, П € г+).

Л,1=0

\

Г1

линейного оператора. Именно, специфика задачи позволяет усилить свойство линейности продолжаемого оператора.

Обозначим через проекцию последовательности в/, на компоненту {Я}^, а через й]? на компоненту {Я}4, дополнительную к . Рассмотрим миноры

-1=0,

S о si

«i «2

Sn+1

sn Sn + 1

S2n

(n6Z+).

Обозначим через nn оператор проектирования на компоненту {@n-i}dd П {@n}d.

Теорема II.2.3. Для позитивной последовательности (sa)^-0 и комплексного числа Л g С \ R определим по формулалг (2.3)—(2.9) оператор U, векторы С, R и круг Л'оо(Л). Тогда имеют место следующие утверждения.

1. Для любого ui € А'оо(А) существует такая положительная мера ц : —> F, являющаяся решением проблемы моментов для

о- что (

Г 1

ги = I -- u(du).

J и- А

R

Обратно, для любого решения ц : —> F этой проблемы моментов вектор w принадлежит Л'оо(А).

2. В любой ненулевой главной компоненте Е С {R}dd решение проблемы, моментов для проекций sff на Е не единственно.

3. В компоненте {i?}d проблема моментов для проекций UÁieem единственное решение ¡iq : Зёъ. —> F.

4. Справедливо равенство я"о о ц = 0 и для любого п > 1 выполняется {3>n-i}dd П С {R}d, при этом мера 7r„ о fi0 представляется суммой п дизъюнктных спектральных мер. Если имеются два различных представления

п

о = И i-1

(п)

т

Е(т) Vi

j=1

в виде суммы дизъюнктных спектральных мер и

то т — п и существует такая матрица порядковых проекторов что

тт^ о щк = 0, о ттк{ = О и ф к),

п п п

Далее, дается определение мажорируемой последовательности по Гамбургеру и доказывается, что такая последовательность представляется квазирадоновой мерой.

Теорема 11.2.4. Пусть в секвенциально о-полном решетопно нормированном пространстве (У, ||, Г) с нормирующем Ка-пространством дана последовательность (ук)к'-о- Допустим, что последовательность {э^к^о С .Р удовлетворяет условиям

п п

Ук+1Сгк(Т1 < як+!<тк(Г1 ((<т*)Г=о С II, п £ г+)

к,1 = 0 к,1=0

' и при некотором а £ К, а > 0, в Ка-пространстве Р сходится положительный ряд

£

Ik

a S2k

Тогда существует такая борелевская мера ц : —> У ограниченной векторной вариации, что

- J AV(rfA) {к Е Z+).

Ук

п

Если fi\ — еще одно региение данной проблемы моментов и еоЛ £ Li(n\), то //1 = ц.

§ 3 посвящен векторнозначной теореме Бохнера. Вводится поня-. тие положительно определенного отображения, заданного на группе и принимающего значения в комплексном /^-пространстве Fc — F + iF.

Отображение ф : б —> Ас называется положительно определенным, если все элементы вида

принадлежат А+ для любых п 6 1М, 171,..., дп 6 С, сх,..., сп € С.

Такого рода определение для самосопряженных операторов, дей-свующих в гильбертовом пространстве, уже встречалось у Г. Такеути, М. А. Наймарка и М. Кристенсена.

Далее дается новое определение мажорируемого отображения группы в в решеточно нормированное пространство У (линейное над полем С).

Определение II.3.2. Отображение : (7 —> У называется мажорируемым, если существует положительно определенное отображение ф : (7 —> Ас такое, что

для любых тг € К, </1,...,</п 6 С, С1,..,,СП € С. В этом случае говорим, что ф является мажорантой для ¡р.

В теореме II.3.1 доказано необходимое в дальнейшем неравенство для мажорируемых отображений и установлена его неулучшаемость в случае, если группа С неабелева. Для абелевых групп это неравент-сво можно улучшить и в результате получается мажорантный аналог неравенства Коши — Буняковского — Шварца.

Теорема 11.3.2. Пусть б — абелева группа и отображение <р : С? —» У имеет мажоранту ф : С —> Ас- Тогда для любых п € 1М, </ъ • • • 19п € б, с\,..., с„, (¡1,..., йп £ С справедливы следующие неравенства

п

ЧскФ{Зз 19к)

Это неравенство является ключевым в доказательстве основного результата.

Теорема II.3.4. Для отображения <р : G —У Y следующие условия эквивалентны:

(1) ip имеет о-непрерывную (е нуле) мажоранту,

(2) существует единственная квазирадонова а-аддитивная мера f.i : ¿¡$х —У Y такая, что

<р(9) = J x(gMdx) (9 G G).

x

Для положительно определенных отображений, принимающих значения в коммутативной алгебре фон-Неймана эта теорема доказана в [17] методами булевозначного анализа.

Затем для любого мажорируемого билинейного отображения определяется свертка квазирадоновых мер, порожденная этим отображе- 4 нием, и доказывается, что произведение мажорируемых отображений представляется сверткой мер, представляющих каждый сомножитель (теорема II.3.6). Далее для /i-пространственных представлений ло-^ кально компактной абелевой группы доказан аналог теоремы Стоуна (теорема И.3.7). Построено также преобразование Фурье для положительно определенных отображений в монотонно полном частично упорядоченном пространстве (теорема II.3.8).

В § 4 рассмотрена задача о лифтинге квазирадоновых мер.

Пусть i ; X -t П - борелевское отображение пространства X на другое локально компактное пространство П. Скажем, что мера /л € qca(¿%x,Y) является 7г-лифтингом меры ¡i Е qca(^n,Y), если fi = J1 о я-1. Мажорируемым квазирадоновым лифтингом будем называть пару линейных операторов L : qca(£$n,Y) qcaи |i| : qca(^n, F) —> qca{£$x,F) обладающих следующими свойствами: (1) Ьц о 7г-1 = ¡л, ц £ qca(«S?n> У); {2)\L\vott~1 i/€qca(^n, F);

(3) \Lfi\= |L|H, neqc&i&n,У);

(4) i/ € qca(^n, ®(1)) => N f € qca(^x, ®(1)).

Теорема о существовании лифтинга доказана для векторных мер в случае, когда пространство П паракомпактно, а отображение я- непре-

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

Теорема 11.4.2. Пусть X, П - локально компактные пространства, причем пространство П паракомпактно а отображение тт : X —> П непрерывно и открыто. Тогда для пары пространств Х,П существуют мажорируемый квазирадоновый ж-лифтинг

Ь : Чса-> Чса

Этот результат получается из теоремы о существовании линейного мажорируемого оператора одновременного продолжения мер (теорема 11.4.1). В качестве следствия построен линейный оператор одновременного продолжени мажорируемых отображений с замкнутой подгруппы Я на всю локально компактную абелеву группу б.

Теорема 11.4.3. Существуют линейные отображения I : У)

и |/| : М0{Н, F) -»■ •/#„(£?, F), обладающие следующими

свойствами:

(1) ад = (зен, У))\ |

(2) 11\ф(д) = ф(д) (ден,фе '

(3) М = иы

(4) если ф : Н —Р - унитарное представление подгруппы Н, то 1ф — унитарное представление группы С.

Часть вторая: МЕТОД ОРБИТ В ИССЛЕДОВАНИИ СОВЕРШЕННЫХ КОДОВ

Глава III. Нижняя оценка числа совершенных кодов. Метод орбит и перечисление совершенных кодов. § 1 является вспомогательным, В нем дается определение совершенного кода. Двоичным кодом длины п обычно называют подмножество С векторов из линейного пространства {0,1}" над полем Галуа СР(2) (пространство {0,1}" называют также двоичным кубом). Для вектора и £ {0,1}" множество его ненулевых координат называем носителем этого вектора и обозначаем через [и]. Число элементов в [и] называем весом вектора и. Векторы, принадлежащие коду С, называются кодовыми словами. Расстояние

Хемминга с?(х, у) между векторами х £ {0, 1}" и у G {0, 1}" — это число координат, в которых эти векторы различаются. Наименьшее расстояние d между двумя кодовыми словами называется минимальным кодовым расстоянием.

Далее рассматриваются совершенные двоичные коды с минимальным расстоянием 3. Известно, что такие коды существуют лишь при п = 2к — 1, где к 6 N. Код называется линейным, если его слова образуют линейное подпространство. Линейные совершенные коды с минимальным расстоянием 3 называются кодами Хемминга. Существует единственный, с точностью до перестановки координат, код Хемминга длины п, который далее обозначается через Я". Известны также нелинейные совершенные коды с параметрами кода Хемминга.

Число совершенных кодов длины п и кодовым расстоянием 3 обозначим через F(n). Ю. Л. Васильевым [3] была получена следующая оценка:

log2 F(n) > +

Более высокая оценка получена С. В. Августиновичем и Ф. И. Соловьевой [2]:

log2 F(n) > 2iïi-loS2(n+1) + ]0g2 g . 2^-i°g2(n+i)_

В § 2 доказывается следующщая:

Теорема III.2.1. При любом п = 2к - 1, к G N,

log2 F(n) > 2iiJ-Iûs2("+1) + 2^.

Позднее, используя конструкцию К. Т. Фелпса, Д. С. Кротовым эта оценка была немного улучшена,

log2 F(n) > +1оё23-2^

Группа перестановочных автоморфизмов кода Хемминга Sym(i/n) состоит из всех перестановок координат, оставляющих неподвижным код Я". Множество всех векторов пространства {0,1}" при действии перестановок из группы Sym(ff") разбивается на непересекающиеся орбиты. В § 3 перечислены все такие орбиты векторов веса не больше семи. Нелинейные коды обычно строятся путем некоторых преобразований кода Хемминга Я". Поэтому свойства получаемых кодов

сильно зависят от свойств группы автоморфизмов 8ут(Яп), многие из этих свойств можно получить, изучая представители различных орбит.

С помощью орбитного подхода решены три задачи: (1) задача перечисления кодов длины 15; (2) в терминах орбит получен критерий несистематичности совершенного двоичного кода; (3) получена нетривиальная верхняя оценка порядка группы автоморфизмов нелинейного кода (этот результат на защиту не выносится).

В § 4 решается первая из перечисленных задач. Для ее решения требуется разложить на орбиты конкретное пространство {О, I}15, состоящее из 215 векторов.

В коде Хемминга Я™ рассматривается подпространство Д;, порожденное всеми векторами и веса 3 с г-й координатой, равной единице (носители таких векторов называют кодовыми тройками, или тройками Штейнера). Всевозможные смежные классы вида 7?" = Д,-фи (и 6 Я") представляют собой совокупность всех ¿-компонент кода Хемминга Я", г — 1,..., п. Нелинейные коды можно получать из кода Хемминга Я", сдвигая в нем попарно непересекающиеся компоненты Н" (г = 1,..15; и £ Я"). Важную роль здесь играет следующая лемма, которая справедлива только для кодов длины 15.

Лемма III.4.1. Если тройка {г^,к} является кодовой в Я15, ( то для любых векторов и,у,лу € Я15 среди компонент Я", Щ, найдутся две с непустым пересечением.

Поэтому необходимо перечислить все орбиты, представители которых не содержат кодовых троек (лемма III.4.2). Теперь для описания нелинейных кодов небходимо перечислить все наборы из попарно непересекающихся компонент. Таких наборов, в силу запрета, налагаемого леммой III.4.2, остается не так много. Оказалось, что все такие коды разбиваются на пять групп. Первая группа — это коды Васильева, которые здесь называются (1 х 16)-кодами. Далее идут (2 х 8)-коды, (4 х 4)-коды, (8 х 2)-коды и (5 х 2)-коды. (к х /)-код характеризуется следующим образом. Рассмотрим множество индексов I С {1,..., 15}, число элементов в котором равно одному из чисел 1, 2, 4, 5, 8. При этом, если / = {г'ь г2, г3, г4}, то г'х ф ¿2 Ф Ф Н = 0; если I = {н, г2, г'з,г4, г5}, то чФг'гфг'зФцфг'Б = 0; если /={?!,... ,г'8}, то дополнение к I является плоскостью Фано (т. е. из г, ^ ф I следует

г Ф .7 0 /)• Эти условия означают, что множество I является носителем некоторого вектора из соответствующей орбиты, на которые разбивается пространство {О, I}15. Для любого множества индексов I, удовлетворяющего вышеуказанным ограничениям и число элементов к в котором равно одному из чисел 1, 2, 4, 8, существует разбиение кода Хемминга Н15 на ¿-компоненты, в котором для каждого 1 £ / имеется I = 16/к непересекающихся ¿-компонент. Это разбиение названо (к х ¿)-разбиением. Кроме этого, для любого пятиэлементного множества /, с вышеуказанным ограничением, существует тупиковый набор из десяти непересекающихся ¿-компонент, в котором для каждого г € / имеется две ¿-компоненты. Назовем (к х /)-кодом любой код, получаемый из кода Хемминга Я15 сдвигами некоторого семейства г-компонент, являющегося частью, либо некоторого (к х /)-разбиения, либо некоторого тупикового набора из десяти компонент.

Итогом классификации является следующая

Теорема Ш.4.2. Любой совершений код С, полученный из кода Хемминга Н15 сдвигами его непересекающихся компонент, является (к х 1)-кодом, где (к х I) может принимать следующие значения: (1 х 16), (2 х 8), (4 х 4), (8 х 2), (5 х 2).

( Глава IV. Несистематические совершенные двоичные коды. В § 1 кратко освещена история несистематических кодов.

Совершенный код С длины п = 2к — 1 называется систематическим, если множество всех координат векторов и £ С можно разбить на множество из п — к информационных координат г/^^^ . .. Щп_к и множество из к проверочных координат ... которые явля-

ются функциями от информационных координат, т. е. =

/1 ("и, ■ ■ ■, «!„_*), • • ■, Щп = !к(«,-,,..«¿„_4). В противном случае код С называется несистематическим. Хорошо известно, что код Хемминга Н" является систематическим (см. [10]). Все коды Васильева тоже являютс.я систематическими. Используя этот факт, Ф. Хергерт перечислил все неэквивалентные коды Васильева длины 15. Поэтому возник вопрос о существовании несистематических кодов.

Несистематические совершенные двоичные коды любой длины п = 2к — 1 (к > 8) впервые были построены С. В. Августиновичем и Ф. И. Соловьевой [1]. М. Ли-Ван и К. Т. Фелпс [15] предложили модификацию конструкции из [1], которая позволяет строить такие коды для всех

п > 31. Несистематические коды длины п = 15 и п = 31 были найдены в [15] с помощью компьютера (см., также [11]).

В § 2 дается определение расширенного несистематического кода и излагается способ их построения. Для любого кода С длины п молено построить расширенный код С длины п +1, добавляя к векторам кода С проверку на четность в качестве нулевой координаты. Обратно, если дан расширенный код С, то для любого г = 0,..., п, вычеркивая г-ю координату во всех векторах кода С, можно получить обычный код С'.

Определение IV.2.1. Расширенный код С длины п = 2к называется систематическим, если существует (к + 1)-элементное подмножество номеров К С {0,..., п) такое, что для любых двух различных векторов и, V 6 С носитель их суммы [ифу] не лежит в К. В противном случае расширенный код С называется несистематическим.

Определение IV.2.2. Расширенный код С длины п = 2к называется вполне систематическим, если при любом г 6 {0, ...,п} существует (к + 1)-элементное подмножество К С {0,..., и} такое, что г € К и для любых двух различных векторов и, V £ С носитель суммы [и ф у] не лежит в К.

Все рассматриваемые далее коды строятся по следующей схеме. В коде Хемминга Я" выделяется семейство непересекающихся ¿-компонент В = {Д^1,..., Я"™ }. Затем в Я" сдвигаются по соответствующим координатам все компоненты выделенного семейства. Полученное таким способом множество Нп(В) является совершенным кодом.

Обозначим через 1ц множество всех номеров г таких, что существуют г-компоненты, принадлежащие семейству В. Рассмотрим независимое множество К С {1,..., п.}. Положим Ь{К) = Ки((К©Л')\{0}), т. е. в Ь(К) входят все элементы из К и все попарные суммы различных элементов из К. Относительно группы перестановочных автоморфизмов кода Я™ векторы и £ {0,1}", носители которых совпадают с некоторым множеством Ь(К), образуют одну орбиту веса к(к + 1)/2.

Теорема IV.2.1. Пусть для некоторого независимого множества К и семейства В непересекающихся компонент кода Я" множество Iв является подмножеством множества Ь(К). Тогда код

С = Нп(В) является систематическим. Кроме этого, полученный из него расширенный код С является вполне систематическим.

Определение IV.2.3. Говорим, что вектор и 6 {О, I}" принадлежит систематической орбите, если существует такой вектор V из максимально!! систематической орбиты, что [и] С [V]. В противном случае говорим, что и принадлежит несистематической орбите.

Для любого вектора и из несистематической орбиты существует семейство непересекающихся компонент В такое, что [и] = /в и код С = Нп(В) является несистематическим. Приведем условия, которым должно удовлетворять семейство В.

(а) Для любого г 6 1в существует ¿-компонента из семейства В, расстояние Хемминга от которой до любой другой ¿-компоненты семейства больше к + 1.

(¡3) При ¿ 6 /в множество и£> не содержит ни одной ¿-компоненты, отличной от ¿-компонент семейства В.

(7) Для множества Е — Л" \ (и£?) сумма Е ф Е содержит все векторы кода Я", вес которых не больше к + 1.

. Существует такой вектор и из несистематической орбиты, что

)[и] = /в.

Теорема IV.2.2. Пусть семейство В непересекающихся г-компонент кода Н" удовлетворяет условиям (а-) — (6). Тогда код С = Нп(В) и полученный из него расширенный код С являются несистематическими.

Следствие IV.2.1. Все векторы веса меньше 7 принадлежат систематическим орбитам. Для любого п > 15 (га = 2к — 1) в пространстве {0,1}" существуют две различные несистематические орбиты веса 7.

Для кодов длины больше 15 все условия (а) — (7) автоматиче-ки удовлетворяются для семейства В, не содержащего кратных компонент, т. е. для любого индекса г £ /в существует только одна •/-компонента, принадлежащая В.

Следовательно, несистематический совершенный код любой допустимой длины га > 15 можно получить, если сдвинуть н коде Хемминга

Нп только семь непересекающихся компонент. Этот результат дает ответ на вопрос, поставленный К. Т. Фелпсом и М. Ли-Ваном в [15].

В § 3 найдены все несистематические коды длины 15, которые получаются из кода Н15 сдвигами непересекающихся компонент, и доказано, что получаемые из них расширенные коды являются несистематическими. Раньше несистематичность кодов длины 15 проверялась с помощью компьютера [11, 15].

В § 4 приводится ряд примеров, дополняющих и иллюстрирующих изложенный выше материал. Из определения следует, что для любого систематического совершенного кода С построенный из него расширенный код С также будет систематическим. Обратное утверждение неверно. Для любого п — 2к — 1 > 31 строится пример такого несистематического кода длины п, что полученный из него расширенный код является систематическим (пример IV.4.1). Строится также пример такого системаческого кода Нп(В), что множество номеров /в сдвигаемых координат семейства непересекающихся компонент В соответствует несистематической орбите (пример IV.4.2). Этот пример оправдывает условия (а)—(<5), накладываемые на семейство Б при построении несистематических кодов.

В [15] был поставлен следующий вопрос. Верно ли, что в несистематическом коде С для любого ¿-элементного множества К имеются такие векторы и,у £ С, что расстояние Хемминга между ними равно 3 и [и ф у] С К? Пример IV.4.3 дает отрицательный ответ на этот вопрос.

Автор выражает благодарность А. Г. Кусраеву за многолетнее и плодотворное сотрудничество.

Литература

[1] Августиновин С. В., Соловьева Ф. И. О несистематических совершенных двоичных кодах // Проблемы передачи информации. 1996. Т. 32, вып. 3. С. 47-50.

[2] Августинович С. В., Соловьева Ф. И. Построение совершенных двоичных кодов последовательными сдвигами 5-компонент // Проблемы передачи информации. 1997. Т. 33, вып. 3. С. 15-21.

[3] Васильев Ю. Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. М.: Физматгиз, 1962. вып. 8. С. 75-78.

[4] Вулих Б. 3. Введение в теорию полуупорядоченных пространств.— М.: Физматгиз, 1961.

[5] Канторович Л. В., Вулих Б. 3., Пинскер А. Г. Функциональный анализ в полуупорядоченных пространствах.—M.-JL: Гостехиздат, 1950.

[6] Кусраев А. Г. Векторная двойственность и ее приложения.— Новосибирск: Наука, 1985.

[7] Кусраев А. Г., Кутателадзе С. С. Булевозначный анализ.— Новосибирск. Изд-во Ин-та математики, 1999.

[8] Кусраев А. Г., Кутателадзе С. С. Нестандартные методы и пространства Канторовича //В кн.: Гутман А. Е., Емельянов Э. Ю., Кусраев А. Г., Кутателадзе С. С. Нестандартные методы анализа и векторные решетки, с. 1-95. Изд-во Ин-та математики Сибирск. Отделение РАН. Новосибирск, 1999.

[9] Кусраев А. Г. Порядковый анализ. 4: Мажорируемые операторы,-Владикавказ, 2001. 100 с. (Изд. РАН. Ин-т прикладной математики и информатики Владикавказкого научного центра).

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

[11] Романов А. М. О несистематических совершенных кодах длины 15 // Дискрет, анализ и исслед. операций. Серия 1. 1997. Т. 4, № 4. С. 75-78.

[12] Diestel J. and Uhl J. J. Vector measures.—Providence, RI: Amer. Math. Soc., 1977. (Mathematical Surveys; 15).

[13] Dinculeanu N. Vector measures.—Berlin: VEB Deutscher Verlag der Wissenschaften, 1966.

[14] Kusraev A. G. Dominated operators. Dordrecht: Kluver, 2000.— 464p.

[15] Phelps К. Т., LeVan M. J. Nonsystematic perfect codes // SIAM J. Discrete Math. 1999. V. 12, N 1. P. 27-34.

[16] Schwartz L. Radon measures on arbitrary topological spaces and cylindrical measures.—London: Oxford Univ. Press, 1973.

[17] Takeuti G. A transfer principle in harmonic analysis //J. Symbolic Logic. 1979. V. 44, no. 3. P. 417-440.

Список работ по теме диссертации

[18] Кусраев А.Г., Малюгин С.А. Некоторые вопросы теории векторных мер.- Ин-т математики АН СССР. Новосибирск, 1988.- 180 стр.

[19] Кусраев А.Г., Малюгин С.А. Произведение и проективный предел векторных мер // В сб.: Современные проблемы геометрии и анализа, с. 132-152. Труды Ин-та математики Сибирск. Отделение АН СССР. Т. 14. Новосибирск, 1989; Siberian Adv. Math. 1991. V. 1, no. 2. P. 77-98.

[20] Кусраев А.Г., Малюгин С.А. О проективном пределе векторных мер // Докл. АН СССР. 1989. Т. 307, №. 2. С. 273-276.

[21] Кусраев А.Г., Малюгин С.А. О векторной проблеме моментов // В сб.: Оптимизация. Вып. 45, с. 99-107. Новосибирск, 1989.

[22] Кусраев А. Г., Малюгин С. А. О продолжении конечно аддитивных векторных мер // Мат. заметки. 1990. Т. 48, № 1. С. 56-60.

[23] Кусраев А.Г., Малюгин С.А. О преобразовании Фурье мажорируемых отображений // Сиб. мат. журнал. 1994. Т. 35, №. 6. С. 1287-1304.

[24] Кусраев А.Г., Малюгин С.А. Векторные меры и мажорируемые отображения // В кн.: Гутман А. Е., Емельянов Э. Ю., Кусраев А. Г., Кутателадзе С. С. Нестандартные методы анализа и векторные решетки, с. 289-370. Изд-во Ин-та математики Сибирск. Отделение РАН. Новосибирск, 1999.

[25] Малюгин С.А. О теореме фон Неймана. Тезисы XII школы по теории операторов в функциональных пространствах (часть 2). Тамбов, 1987. С. 7.

[26] Малюгин С. А. О векторной проблеме моментов Гамбургера //В сб.: Оптимизация. Вып. 48. С. 124-141. Новосибирск, 1990.

[27] Малюгин С.А. Квазирадоновы меры // Сиб. мат. журнал. 1991. Т. 32,№. 5.С. 101-111.

[28] Малюгин С.А. Проблема моментов в /^-пространстве // Сиб. мат. журнал. 1993. Т. 34, №. 2. С. 110-120.

[29] Малюгин С.А. Неравенства для мажорируемых отображений // Сиб. мат. журнал. 1996. Т. 37, №. 6. С. 1350-1355.

[30] Малюгин С. А. О продолжении мажорируемых отображений // Тезисы III Сибирского конгресса по прикладной и индустриальной математике (ИНПРИМ - 98). Июнь 22-27, 1998. Ин-т математики СО РАН, 1998. С. 81.

[31] Малюгин С. А. О лифтинге квазирадоновых мер// Сиб. мат. ) журн. 2001. Т. 42, № 2. С. 407-413.

[32] Малюгин С. А. О перечислении совершенных двоичных кодов длины 15, полученных из кода Хэмминга сдвигами компонент,- Тезисы II Сибирской конференции по исследованию операций. Июнь 22-27, 1998. с. 130.

[33] Малюгин С. А. О нижней оценке числа совершенных двоичных кодов // Дискр. анализ и исслед. операций. Серия 1. 1999. Т. 6, №. 4. С. 44-48.

[34] Малюгин С. А. О перечислении совершенных двоичных кодов длины 15 // Дискр. анализ и исслед. операций. Серия 2. 1999. Т. 6, №. 2. С. 48-73.

[35] Малюгин С. А. О критерии несистематичности совершенных двоичных кодов // Тезисы Международной Сибирской конференции по дискретному анализу и исследованию операций. 26 июня - 1 июля, 2000. с. 77.

[36] Малюгин С. А. О критерии несистематичности совершенных двоичных кодов // Докл. РАН. 2000. Т. 375, № 1. С. 13-16.

[37] Малюгин С. А. Несистематичиские совершенные двоичные коды // Сб. лекций по дискретная математике и ее приложениям. С. 218228. М.: Из-во центра прикладных исследований при механико-математическом факультете МГУ, 2001.

[38] Малюгин С. А. Несистематичиские совершенные двоичные коды // Дискр. анализ и исслед. операций. Серия 1. 2001. Т. 8, № 1. С. 55-76.

Малюгин Сергей Артемьевич Квазирадоновы меры.

Метод орбит в исследовании совершенных кодов

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

>

Подписано к печати 25.09.02. Формат 60x84 1/16. Печать офсетная. Усл. печ. л. 1,7. Уч.-изд. л. 1,4. Тираж 100 экз. Заказ № 68.

Лицензия ПЛД 57-43 от 22 апреля 1998 г. Отпечатано на полиграфическом участке ИМ СО РАН, 630090 Новосибирск, пр. Академика Коптюга, 4.