Модулярные кривые и коды с полуноминальной сложностью построения тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ВВВДЕНИЕ.

ГЛАВА I. Рациональные точки на кривых и корректирующие коды.

§1. Рациональные точки яа кривых над конечными полями.

§2, Корректирующие коды и их асимптотические границы.

§3. ЧЙодулярньгё* коды и их параметры.

§4. Применение к бинарным кодам.

ГЛАВА 2. "Модулярные" коды для классических модулярных кривых.

§1. Основная теорема.

§2. Реализация "модулярных" кодов.

§3. Формулы.

§4. Вычислительный процесс.

§5. Стандартные процедуры.

ГЛАВА 3. "Модулярные" коды: эллиптические модули

В.Г.Дринфельда.

§1. Основная теорема.

§2. Многообразия модулей эллиптических модулей.

§3. Реализация "модулярных" кодов.

§4. Формулы.

§5. Вычислительный процесс.

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

Линейным а -ичным кодом С называется к -мерное под-гр ь. пространство в г^ , минимальное число ненулевых координат в ненулевом векторе из С обозначается d = d (С) . Одной из основных задач теории кодирования является изучение соотношений между величинами ж S- d-in цри длине кода Уь , стремящейся к бесконечности. Здесь ставится задача существования сколь угодно длинных кодов с заданными параметрами { R, <5* ), а также задача эффективного построения такой последовательности кодов, коль скоро известно, что она существует. Частичное решение этих задач дают нижние границы Варшамова-Гильберта (для цроизвольных линейных кодов) и Блоха-Зяблова (для эффективно конструируемых последовательностей кодов).

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

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

Методика исследования. Применяется конструкция В.Д.Гоппы кодов по кривым над конечным полем, вычисление числа рациональных точек на модулярных кривых. Для алгоритмического анализа конструкции кодов применяется детальный анализ плоских моделей модулярных кривых.

Апробация работы. Результаты диссертации докладывались на ){У1 Всесоюзной алгебраической конференции (Ленинград, 1981 г.), на Школе-семинаре по алгебраической геометрии (Ярославль,

1982 г.), на семинаре по теории кодирования в Институте проблем передачи информации АН СССР (1983 г.), на семинаре Отдела прикладной математики Центрального экономико-математического института АН СССР (1983 г.), на УШ Всесоюзном симпозиуме по проблеме избыточности в информационных системах (Ленинград,

1983 г.).

Объем и структура диссертации. Диссертация содержит 125 страниц и состоит из введения и трех глав, разбитых на 14 параграфов; библиография - 39 названий.

1. Ахо Дж., Хопкрофт А., Ульман А., Построение и анализ вычилительных алгоритмов.-М.:Мир, 1979.

2. Бассалыго JI.A., Зяблов В.В., Пинскер М.С., Проблемы сложности в теории корректирующих кодов.-Проблемы передачи информации,1977, 13, $3, с. 5-17.

3. Блох Э.Л., Зяблов В.В., Линейные каскадные коды.-М.: Связь, 1982.

4. Влэдуц С.Г., О числе точек на модулярной кривой.-В кн.: ХУ1 Всесоюзная алгебраическая конференция.Тезисы, ч.П.-Л., 1981, с. I4I-I42.

5. Влэдуц С.Г., Два эффективных алгоритма построения асимптотически хороших "модулярных" кодов.-Вкн.: УШ Симпозиум по проблеме избыточности в информационных системах.Тезисы, ч.1.-Л., 1983, с. 139-142.

6. Влэдуц С.Г., Модулярные кривые и коды с полиномиальной сложностью построения. ЦЭМИ АН СССР.-М.:1983.-65 с. (Рукопись деп. в ВИНИТИ 15.06.83, № 3302-83ДЕП).

7. Влэдуц С.Г., Дринфельд В.Г., О числе точек алгебраической кривой.-Функц. анализ, 1983, т. 17, №1, с. 68-69.

8. Влэдуц С.Г., Кацман Г.Л., Цфасман М.А., Модулярные кривые и коды с полиномиальной сложностью построения.-Проблемы передачи информации, 1983, 19, 13, с.

9. Гоппа В.Д., Коды на алгебраических кривых.-Докл. АН СССР,1981, 259, 16, с. 1289-1290.

10. Гоппа В.Д., Алгебраико-геометричеекие коды.-Изв. АН СССР1982, 47, И, с. 762-781.

11. Гриффите Ф., Харрис Дж., Принципы алгебраической геометрии, т. 1-2.-М.:Мир, 1982.

12. Дринфельд В.Г., Эллиптические модули.-Матем. сб., 1974, 94(136), №4, с. 594-627.

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

14. Касселс Дж., Диофантовы уравнения со специальным рассмотрением эллиптических кривых.-Математика, 1968, 12:1.

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

16. Мамфорд Д., Абелевы многообразия.-М.:Мир, 1971.

17. Слисенко А.О., Теория сложности вычислений.-Успехи математических наук, 1981, №3, с. 22-103.

18. Серр Ж.-П., Алгебраические группы и поля классов.-М.: Мир, 1968.

19. Серр Ж.-П., Курс арифметики.-М.:Мир, 1971.

20. Хартсхорн Р., Алгебраическая геометрия.-М.:Мир, 1981.

21. Чеботарёв Н.Г., Теория алгебраических функций.-М.:ГТТИ, 1948.

22. Шафаревич И.Р., Основы алгебраической геометрии.-М.: Наука, 1972.

23. Шимура Г., Введение в теорию автоморфных функций.-М.:Мир, 1973.- 12424« Deligne P., Rapoport M., Les sh^mas de modules de courbes elliptiques.-In:Modular Functions of One variable II.-Berlin e.a.sSpringer,1973 (Lect. Notes Math., 349),143-316.

24. Gobs D., Modular Forms over .-Crelle's J. ,1980,31 16-39.

25. Goss D., tic -adic Eisenstein Series for Function Fields.-Compos. Math., 1980, 41, 3-38.

26. Goss D., The Algebraist*s Upper Half-Plane.-Bull. Amer. Soc.,1980,2, 391-415.

27. Ihara y., On the Problems of Congruence Monodromy, 2 vols.-Tokyo, 1968.

28. Ihara Y., On Modular Curves over Finite Fields.-In:Discr. Subgroups of Lie Groups and Applictions to Moduli.-Ox-ford, 1975, 161-203.

29. Katsman G.L., Tsfasman M.A., Vladut S.G., Modular Curves and Codes of Polynomial Construction.-IEEE Trans. Inform. Theory, 1983,

30. Katz N.M., p -adic Properties of Modular Forms.-In« Modular Functions of One Variable III.-Berlin e.a.: Springer, 1973 (Lect. Notes Math., 350).

31. Kluit P.G., On the Normalizer of Г^ .-In: Modular Functions of One Variable V.-Berlin e.a.:Springer, 1976 (Lect. Notes Math., 601),239-247.

32. Lang S., Elliptic Functions.-H.Y.:Addison-Wesleyt 1973.

33. Manin Yu.I., What is the Maximal Uumber of Points on a Curve over ?-J.Pac.Sci.Univ.Tokyo, sec. IA, 1982, 28n° 3, 715-720.

34. Serre J.*P., Sur le потЪге des points rationnels d'une courbe algebrique sur un corps finis,- C.R. Acad.Sci.Pvtis, Mb, ^^ г, 3 9 7-40Л.

35. Tsfasman M.A., Vladuf S.G., Zink fh., Modular Curves, Shi-mura Curves, and Goppa Codes better than Varshamov-Gil-bert bound.-Math.Nachr., 1982, 109, 21-28.3g "WtiC VartU-Us cj^^vn^^ еЛ- Portal Шлм^гЩъ} 194S.i /