Національна академія наук України
Національна академія наук України
Інститут кібернетики імені В.М. Глушкова
ГЛАЗУНОВ Микола Михайлович
УДК 511:519.6:681
Розробка МЕТОДІВ ОБГРУНТУВАННЯ ГІПОТЕЗ
ТЕОРІЇ алгебраїчних кривих та геометрії чисел
01.05.01 – теоретичні основи інформатики та кібернетики
Автореферат
дисертації на здобуття наукового ступеня
доктора фізико-математичних наук
Київ - 2005
Дисертацією є рукопис.
Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.
Науковий консультант: доктор фізико-математичних наук, академік НАН України,
Шор Наум Зуселевич,
Інститут кібернетики імені В.М. Глушкова НАН України,
завідувач відділу методів розв’язування складних задач
оптимізації.
Офіційні опоненти: доктор фізико-математичних наук, професор,
Варбанець Павло Дмитрович,
Одеський національний університет імені І.І. Мечнікова,
завідувач кафедри комп’ютерної алгебри та дискретної
математики,
доктор фізико-математичних наук, професор,
Дрозд Юрій Анатолійович,
Київський національний університет імені Тараса Шевченка,
професор кафедри алгебри і математичної логіки,
доктор фізико-математичних наук, старший науковий
співробітник,
Левитська Аліна Олександрівна,
Інститут кібернетики імені В.М. Глушкова НАН України,
провідний науковий співробітник відділу математичних
методів теорії надійності складних систем.
Провідна установа: Інститут прикладної математики та механіки НАН України,
відділ теорії керуючих систем, м. Донецьк.
Захист відбудеться “29”_квітня_2005 р. о(об) 1100 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:
03680 МСП Київ-187, проспект Академіка Глушкова, 40.
З дисертацією можна ознайомитися в науково-технічному архіві інституту.
Автореферат розісланий__24_березня______2005 р.
Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Темою дослідження даної роботи є розробка комп’ютерно-алгебраїчних, інтервально-аналітичних і на просторах модулів методів обґрунтування гіпотез теорії алгебраїчних кривих та геометрії чисел, побудова на їхній основі ефективних алгоритмів та комп’ютерних систем розв’язування обчислювальних задач теорії алгебраїчних кривих та геометрії чисел на просторах модулів, розробка та застосування цих методів, алгоритмів та систем до розв’язування деяких задач про розв’язки, множини розв’язків, не пустоту та пустоту розв’язків кривих вигляду y2 = f(x) , де f(x) є поліномом степеня більше або рівній п’яти, гіпереліптичних кривих над простими скінченими полями, про рівнорозподіленість кутів тригонометричних сум Клостермана, вибраних задач стохастичної апроксимації, інтервального оцінювання та теорії динамічних систем, гіпотези Мінковського про критичний визначник області .
Задачі обґрунтування гіпотез теорії алгебраїчних кривих та геометрії чисел виникають як задачі та пов’язані з ними гіпотези на математичних моделях предметних областей при дослідженні багатьох теоретичних і практичних проблем. Їх потрібно вирішувати в теорії кодування та передачі інформації, у теорії оптимізації, у теорії динамічних систем, у теоретичній фізиці, та в деяких інших.
Аналог гіпотези Рімана Hasse H. Abstrakte begrьndung der komplexe multiplication und Riemannsche vermutung in funktionenkцrper // Abh. Math. Sem. Hamburg.- 1934. – Bd.10. – S.325–348. та гіпотези А. Вейля Weil A. Sur les courbes algйbriques et les varieties qui s’en dйduisent // Actuallitйs Sci. Ind., Paris. – 1948. – ? 1041. – P.1–85. для алгебраїчних многовидів над скінченними полями виникли при дослідженні множин рішень та пов’язаних з ними дзета-функцій кривих. Вони стимулювали й стимулюють розробку методів дослідження алгебраїчних многовидів над скінченними полями Deligne P. La conjecture de Weil. I, II // Inst. Hautes Etudes Sci. Publ. Math. – 1974. – 1980. – Vol.43, Vol. 52. – P.273–307, P.137–252. та застосування таких методів. Гіпотеза Дж. Тейта Tate J. Algebraic cycles and poles of Zeta functions // Arithmetic Algebraic Geometry. New York: Harper & Row. – 1965. – P. 93–110. про рівнорозподіленість із щільністю Сато–Тейта кутів ендоморфізму Фробеніуса еліптичних кривих без комплексних множень та її експериментальна перевірка М. Сато стимулювали дослідження питань равнорозподіленості Katz N. Gauss sums, Kloosterman sums, and monodromy groups. – Princetin: Princeton Univ. Press, 1988. – 186 p., розробку відповідних методів та їхнє застосування. Виявлення тригонометричних сум Клостермана як важливого інгредієнта постановки та дослідження багатьох задач Kloosterman H. On the representation of numbers in the form ax2 + by2 + cz2 + dw2 // Acta Math. – 1926. – 49. – P. 407–464. математики та комп’ютерних наук спричинили дослідження та застосування Линник Ю.В. Эргодические свойства алгебраических полей. Ленинград: Изд-во ЛГУ, 1967. – 208 с. таких сум.
Геометрія чисел як розділ теорії чисел сформувалась з публікацією монографії Г. Мінковського Minkowski H. Geometrie der Zahlen. Berlin – Leipzig: Teubner, 1896. – 215 s.. Фундаментальними в геометрії чисел є поняття точкової решітки і пов’язані з точковими решітками критичні визначники та критичні решітки Касселс Дж. Введение в геометрию чисел. – М.: Мир, 1965. – 421с.. Решітки, критичні визначники та їхні властивості є дуже важливими в мінімізації дійсних функцій, діофантових наближеннях, теорії кодування, задачах про укладки та в деяких інших. Однак, як зазначено у відомій монографії Grotschel M., Lovasz L., Schrijver A. Geometric algorithms and combinatorial optimisation. – Berlin: Springer, 1988. – 362 p., присвяченій геометричним алгоритмам та комбінаторній оптимізації, решітки в геометрії чисел досліджуються за більшою частиною із неалгоритмічної точки зору. Тим самим розробка конструктивних та алгоритмічних методів у геометрії чисел являє собою актуальну наукову проблему. В своїй монографії Minkowski H. Diophantische Approximationen. – Leipzig: Teubner, 1907. – Vol. 8. – 235 s. Г. Мінковський розпочав вивчення критичного визначника та критичних решіток області . Назва гіпотеза Мінковського з’явилась у працях англійських дослідників К. Девіса Davis C.S. Note on a conjecture by Minkowski // Journ. London Math. Soc. – 1948. – 23. – P. 172–175., Х. Кона Cohn H. Minkowski’s conjectures on critical lattices in the metric // Annals of Math. – 1950. – 51. – N 3. – P.734–738. та Г. Уотсона Watson G.L. Minkowski’s conjectures on critical lattices of the region , (I) (II) // J. London Math. Soc. – 1953. – 28. – N 3. – N 4. – P.305-309. – P.402–410.. Нехай є критичний визначник області . Розглянемо дві Dp – допустимі решітки та , які мають по три пари точок, лежачих на границі області Dp , причому , – визначники цих решіток. Гіпотеза Мінковського формулюється таким чином.
Гіпотеза (М). Для будь-якого дійсного числа p > 1
.
Тут p(0) – дійсне число, однозначно визначене умовами , 2.57 < р(0) < 2.58 .
Л. Морделл Mordell L. Lattice points in the region |Ax4 + By4| 1, // J. London Math. Soc.. 1941. – 16. – P.152–156. перевірив гіпотезу Мінковського для p = 4 і довів, що в цьому випадку гіпотеза справедлива. Дослідженнями К. Девіса, Х. Кона та Г. Уотсона гіпотеза була уточнена і в ряді випадків доведена. Часткові випадки гіпотези Мінковського досліджувались В.Г. Кухаревим Кухарев В.Г. Критический определитель области // Изв. ВУЗ-ов. Математика. – 1971. – №2. – С. 62–70. , який довів її для p = 1.3, 1.4, 1.5, 1.6, 1.7, 3, 4.5. О.В. Малишев та А.Б. Воронецький довели Malyshev A.V., Voronetsky A.B. The proof of Minkowski’s conjecture concerning the critical determinant of the region xp+yp<1 for p 6 // Acta Arithmetica. – 1975. – XXVII. – P. 447–458. гіпотезу Мінковського для p 6. Надалі гіпотеза Мінковського досліджувалась О.В. Малишевим Малышев А.В. О применении ЭВМ к доказательству гипотезы Минковского из геометрии чисел. 1. 2 // Зап. науч. семинар. ЛОМИ, 1977. – № 71. – С. 163–180; 1979, № 82. С. 29–30. та О.В. Малишевим з колегами Гришмановская К.И., Малишев А.В., Пачев У.М., Фидарова А.Ч. Доказательство гипотезы Минковского о критическом определителе области xp+yp<1 в случае 5 p 6 // Зап. науч. семинар. ЛОМИ. – 1977, № 67. – С. 95–107. , які довели гіпотезу Мінковського для p 2.035, 1.0099 p 1.996.
Задачі обґрунтування гіпотез теорії алгебраїчних кривих та геометрії чисел розв’язуються у теорії передавання інформації Conway J.H., Sloane N.J. Sphere packings, lattices and groups. New York-Berlin: Springer – Verlag, 1988. – 663 p. та криптографії Koblitz N. Hyperelliptic cryptosystems // J. Cryptology. – 1989. – 1. – P.139–150., у теорії динамічних систем Deninger C. Some analogies between number theory and dynamical systems on foliated spaces // Doc. Math. J. DMV Extra volume ICM. – 1998. – P.163–186., у математичній та теоретичній фізиці Виттен Э. Физика и геометрия // Междунар. конгресс математиков в Беркли. – М.: Наука, 1991. – С. 394–442., а також у багатьох інших випадках.
Теорія алгебраїчних кривих нараховує вже не одну сотню років, але як у застосуваннях теорії алгебраїчних кривих, так і в ній самій виникають все нові складні задачі, які треба вирішувати, і зокрема, розвивати та створювати нові методи дослідження як класичних, так і цих нових задач. За останні сто років з’явилося багато праць, присвяченій цій проблемі. Серед них праці Е. Артіна, Н. Гассе, А. Вейля, Л. Морделла, А. Гротендіка, С. Ленга, Ж.-П. Серра, Дж. Тейта, І.Р. Шафаревича, Б. Берча, Х. Суіннертон-Дайера, О.Г. Постникова, Ю.І. Маніна, Дж. Касселса, О.М. Паршина, С.О. Степанова, О.М. Введенського, Г. Фрея, Д. Вайлса, Г. Фалтингса, Ю.А. Дрозда, Д. Харріса, Д. Моррісона та ін.
Геометрія чисел була створена Г. Мінковським приблизно сто років тому. В її розвиток внесли вклад багато вчених. Відмітимо, що деякі з цих учених працювали як в геометрії чисел, так і в теорії алгебраїчних кривих. Серед них, поряд з Г. Мінковським, Б.М. Делоне, Л. Морделл, Р. Ранкін, К. Роджерс, Х. Девенпорт, Б.А. Венков, Д.К. Фаддеєв, Б. Берч, Х. Суіннертон-Дайер, Дж. Касселс, Е. Главка, К. Девіс, Х. Кон, Г. Уотсон, Ю.В. Линник, О.В. Малишев, Б.Б. Венков, Б.Ф. Скубенко, С.С. Ришков, М. Хакслі (M. Huxley) та ін.
На даний час створені розвинені методи як теорії алгебраїчних кривих, так і геометрії чисел. Ці теорії включають у себе методи дослідження структури і властивостей різних класів задач, методи їх розв’язання та інші аспекти. Вагомий внесок у розвиток теорії алгебраїчних кривих, у геометрію чисел, у пов’язану з ними теорію зображень в Україні внесли Г.Ф. Вороний, Ю.В. Ліннік, О.В. Малишев, О.М. Введенський, П.Д. Варбанець, Ю.А. Дрозд, В.В. Кириченко, Ю.І. Манін, А.В. Ройтер, І.Р. Шафаревіч, їхні учні та колеги.
Слід зазначити, що розробка методів обґрунтування гіпотез теорії алгебраїчних кривих та геометрії чисел пов’язана із сформульованою В.М. Глушковим Глушков В.М. О некоторых проблемах теории автоматов и искусственного интеллекта // Кибернетика. – 1970. – № 2. – С. 1–7. загальною проблемою автоматизації досліджень у математиці. Для задач теорії ймовірностей та оптимізації В.С. Михалевич розробив метод послідовного аналізу варіантів. Н.З. Шор Shor N.Z. Nondifferentiable optimization and polynomial problems. Boston: Kluwer Acad. Publ., 1998. – 394 p. запропонував іі розробив клас субградієнтних методів з розтягом простору, які знайшли глибокі застосування як у теорії оптимізації та ефективізації її алгоритмів, так і поза її межами, зокрема, до 17 проблеми Гільберта. Методи дослідження ймовірнісних характеристик функцій та систем рівнянь у скінченних полях розвиває І.М. Коваленко Коваленко И.Н. Левитская А.А. Предельное поведение числа решений системы случайных линейных уравнений над конечным полем и конечным кольцом // ДАН СССР. – 1975. – Т. 221, № 4. – С. 778–781., його учні А.О. Левитська та інші. Алгебраїчні дослідження з застосуванням комп’ютерів розвивали та розвивають Л.А. Калужнін, А.О. Стогній, В.І. Сущанський. У напрямку логічних та алгебраїчних методів доведення теорем та розробки алгоритму очевидності Глушков В.М., Капитонова Ю.В., Летичевский А.А. Инструментальные средства проектирования программ обработки математических текстов // Кибернетика. – 1979. – № 2. – С. 3–14. працюють Ю.В. Капітонова, О.А. Летічевський та їхні учні і колеги. Обґрунтування індуктивного підходу до математики розвиває А.М. Гупал.
Новим загальним підходом до розробки математичних основ створення комп’ютерних систем та їхнього застосування до розв’язання складних інформаційних проблем є підхід на базі теоретико-категорних методів. В Україні цей напрям досліджень розвивають І.М. Парасюк, О.І. Провотар, І.В. Сергієнко Сергиенко И.В., Парасюк И.М., Провотар А.И. О применении категорных методов в computer science // Кибернетика и системный анализ. – 2000. – № 4. – С. 3–11., їхні учні та колеги.
Розширення застосувань, розвинення теорії та вдосконалення обчислень призводять до ускладнення задач алгебраїчних кривих і геометрії чисел, зокрема, до появи класів задач, які параметризуються точками многовидів, мають експоненційне зростання числа досліджуваних випадків, неточну інформацію про значення коефіцієнтів, тощо. Цим задачам властиві свої труднощі, що в свою чергу вимагає розробки та застосування нових або модифікації відомих методів їх розв’язування. Виконанню таких актуальних досліджень і присвячена дана дисертаційна робота.
Не зважаючи на те, що існуючі методи теорії алгебраїчних кривих та геометрії чисел досить розвинені, їх не можна вважати придатними для розв’язання всього широкого спектра обчислювальних та практичних задач. Принципові труднощі, що виникають при цьому, пов’язані з поєднанням підвищеної складності з дуже великою та навіть нескінченною кількістю самих класів задач. До того ж звичайні обчислювальні методи не доводять пов’язаних з цими новими класами задач гіпотез, а дають лише наближені розв’язки. Тому розумно, разом із розробкою гарантованих методів, досліджувати поведінку та розподіл класів задач, будувати скінченні розбиття класів задач із відносно невеликою кількістю елементів. Деякі гарантовані методи для комбінаторних задач та задач диференційних рівнянь запропонував та застосував П.С. Панков Панков П.С. Доказательные вычисления на ЭВМ. Фрунзе: Илим, 1978. – 177 с.. Ю.В. Матіясевіч застосував інтервальні методи до дослідження гіпотези Рімана про нулі дзета-функції Матиясевич Ю.В. Еще один машинный эксперимент в пользу гипотезы Римана // Кибернетика. – 1982. – № 6. – С.10,22..
У зв’язку з цим особливої актуальності набувають методи, які об’єднують точні та наближені методи, а також гарантовані методи. У проведеному нами дослідженні таке об’єднання виконане та застосовувалось при вивченні розподілу кутів тригонометричних сум Клостермана (розділ 2 дисертації). А саме, комп’ютерно-алгебраїчний метод обчислення зворотних елементів скінченного поля об’єднано з наближеними комп’ютерними методами обчислення значень сум Клостермана та обробки результатів таких обчислень, а також для інтерпретації при обчисленні натуральних інтервальних розширень раціональних функцій на раціональних інтервалах (розділ 1). На базі розробки та застосування гарантованих інтервально-аналітичних методів обґрунтовано гіпотезу Мінковського про критичний визначник області (розділи 1, 4, 5). На наш погляд, разом із застосуванням просторів модулів (дивіться нижче), саме на цьому шляху може бути досягнутий значний ефект застосування математичних методів і обчислювальної техніки в області обґрунтування гіпотез теорії алгебраїчних кривих і геометрії чисел.
Простори модулів як алгебраїчні многовиди були введені Б. Ріманом при дослідженні їм ріманових поверхонь. Наприклад, еліптичні криві над полем комплексних чисел параметризуються одним комплексним параметром – модулярним інваріантом еліптичної кривої, а компактні ріманові поверхні роду g (g > 1) параметризуються (3g – 3) комплексними параметрами. Простором модулів даної геометричної структури будемо називати алгебраїчний, або аналітичний многовид, точки якого параметризують об’єкти чи класи об’єктів (за деяким відношенням еквівалентності) цієї геометричної структури. Наведене поняття простору модулів узагальнює поняття алгебро-геометричного простору модулів, яке використовується, наприклад, у монографії Дж. Харриса та Дж. Моррісона Harris J., Morrison J. Moduli of curves. Berlin-N.Y.: Springer, 1998. – 366 p. також і на аналітичні многовиди.
Відомо, що довільна скінченна послідовність, а також нескінченні періодичні послідовності можуть бути породжені скінченними автоматами, які, в свою чергу, є дискретними динамічними системами. Ергодичні динамічні системи відіграють важливу роль у дослідженнях як фізичних процесів, так теоретико-числових задач Коренфельд И.П., Синай Я.Г., Фомин С.В. Эргодическая теория М.: Наука, 1980. – 383 с.. Чисельні методи розв’язування рівнянь мають плодотворну інтерпретацію у вигляді динамічних систем Смейл С. Алгоритмы решения уравнений // Междунар. конгресс математиков в Беркли. – М.: Наука, 1991. – С. 264–296.. Тому в третьому розділі дисертації розглянуто у динамічній інтерпретації застосування розроблених автором методів до оцінки інтегралів, комутативних формальних груп, оцінки дзета-функцій, просторів критичних решіток, а також категорно-динамічну інтерпретацію інтервальних обчислень.
Для комп’ютерного доведення гіпотези Мінковського будуємо інтервальний аналіз на просторі модулів допустимих решіток області Dp, методи, алгоритми та комп’ютерні системи, що їх реалізують (розділи 1,4,5).
Усі п’ять розділів дисертації зв’язані між собою по-перше тим, що їхню тематику можна віднести до теорії алгебраїчних кривих та геометрії чисел, по-друге, що в усіх розділах розглядаємо комп’ютерні методи обґрунтування гіпотез вищезазначених теорій та застосування цих методів.
Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалась у відповідності з планами наукових досліджень відділів 400, 300, лабораторії 391, відділу 100 Інституту кібернетики імені В.М. Глушкова НАН України в рамках наукових тем та програм, у яких М.М. Глазунов був виконавцем, відповідальним виконавцем (у більшості тем), заступником керівника та керівником.
1. С.Г.П.400.22 і Д.Т.0200.011 по проблемі “Розробити та впровадити комплекс типових прикладних засобів загальносистемного призначення та функціонального призначення, прогресивну технологію створення програмних засобів та автоматизованих систем проектування АСК” (19811984 рр.), номер держ. реєстрації 080210509;
2. “Розробка методів дослідження нелінійних динамічних систем великої розмірності”, (вступ, аналітичний огляд, розділи “Чисельно-аналітичні методи дослідження динамічних керованих систем”, “Реалізація чисельно-аналітичних методів на ЕОМ і їхнє розпаралелювання” (1984–1987 рр.), номер держ. реєстрації – 01840005088;
3. В.Г.Е.300.01 та БАСК-УН по проблемі “Застосування обчислювальної техніки у процесах керування, проектування та наукових досліджень (1987 1990 рр.);
4. Р391.03 “Розробити інтервально–аналітичний метод розв’язування складних алгебраїчних, трансцендентних та деяких класів диференційних рівнянь і пакет прикладних програм” (1989 – 1991 рр.), шифр проблеми УП Пр. АН СРСР;
5. В.Г.Е.391.05 Розробити алгебротопологічні методи дослідження багатовимірних динамічних систем з перемінними параметрами у регулярних та особливих випадках(1991 1995 рр.);
6. В.Ф.100.03 “Розробка математичної теорії взаємодії компонент комп’ютерного середовища та ії застосування у системі програмування АПС” (1998–2001рр.), номер держ. реєстрації – 0198U00320;
7. В.Ф.100.04 “Розробка ефективних формалізмів для відродження процесів свідомості (інтелектуальної діяльності) у техногенному середовищі і засобів її комп’ютерної підтримки” (2000–2003 рр.), номер держ. реєстрації – 0198U001775;
8. В.Ф.К.105.01 “Розробити методи та засоби продукування і маніпулювання знаннями у операційному середовищі і інтелектуалізації інформаційних технологій” (2002–2006 рр.), номер держ. реєстрації 0102U003204;
9. В.Ф.100.06 “Розробка ефективних формалізмів та засобів їх підтримки для розв’язування інтелектуальних задач у техногенному середовищі” (20032007 рр.).
Мета і задачі дослідження. Метою дисертації є розробка методів обґрунтування гіпотез теорії алгебраїчних кривих і геометрії чисел, проведення їх дослідження, порівняльний аналіз із відомими методами, створення теоретичних та практичних основ автоматизації обґрунтування гіпотез, застосування розроблених методів, алгоритмів, комп’ютерних систем для обґрунтування гіпотез та зв’язаних з ними задач.
Об’єктом дослідження є задачі та гіпотези теорії алгебраїчних кривих і геометрії чисел.
Предметом дослідження є гіпотеза про рівнорозподіленість з густиною Сато–Тейта кутів тригонометричних сум Клостермана, точність оцінок Хассе–Вейля та Мітькіна кількості рішень алгебраїчних кривих над простими скінченними полями, гіпотеза Мінковського про критичний визначник області.
Методи досліджень є елементарні теоретико-числові та теоретико-графові методи, які безпосередньо опираються на арифметичну, або графову природу досліджуваної задачі й гіпотези, методи математичної статистики та інформатики, методи просторів модулів та аналітичні методи, комп’ютерно-алгебраїчні методи й чисельні методи розв’язування явно та неявно заданих рівнянь, які використовувалися у процесі комп’ютерних експериментів, методи інтервального аналізу, які дають змогу отримувати гарантовані результати, методи теорії формальних груп та теорії категорій.
Наукова новизна. У дисертаційній роботі автором отримані нові теоретичні результати, зокрема:
1. Розроблено метод обґрунтування гіпотез про рівнорозподіленість із заданою густиною кутів тригонометричних сум Клостермана, який базується на теоретико-числових принципах, просторах модулів, комп’ютерній алгебрі й статистичному критерії.
2. Отримано на основі методу О.Г. Постнікова із застосуванням елементарної оцінки С.О. Степанова кількості точок кривої елементарна (в смислі застосовуваних методів) оцінка значення сум Клостермана, яка раніше отримана А. Вейлем методами алгебраїчної геометрії.
3. Поліпшена (знижена) оцінка для границі існування раціональних точок кривих вигляду y2 = f(x) над простими скінченними полями, де f(x) є унітарний поліном степеня 5.
4. Зазначено класи кривих вигляду y2 = f(x) над простими скінченними полями, які вміщують велике число раціональних точок, і класи кривих вигляду y2 = x(p-1)/2 + a, , , поліном справа має непарну степінь, які не містять раціональних точок над простими скінченними полями. Метод отримання таких кривих, розроблений автором, використовує ідею О.Г. Постнікова про представлення кількості рішень через символи Лежандра, доповнює отриманий С.О. Степановим за умови, коли поліном має парну степінь. Експериментально досліджено розподіл кутів сум Клостермана, зв’язаних з накриттями АртинаШрайера та питання існування та не існування раціональних точок гіпереліптичних кривих на просторах модулів таких кривих над простими скінченними полями.
5. Розроблено теорію та методи інтервальних обчислень, які базуються на теоретико-числових принципах.
6. Розроблений і реалізований як інтервальний на просторі модулів допустимих решіток метод доведення відомої гіпотези Мінковського про критичний визначник області в околі (метод є розвитком методу А.В. Малишева).
7. Розроблена теорія і методи інтервального оцінювання та дослідження поведінки досить гладких функцій однієї та двох дійсних змінних.
8. Побудована теорія обґрунтування гіпотез на просторі модулів допустимих решіток області ,, яка базується на інтервальному аналізі на цьому просторі.
9. Для побудови методів проведені теоретичні дослідження та серії великих обчислювальних експериментів. Співставлення їх результатів із відомими підтвердило високу ефективність запропонованих методів розв’язання складних обчислювальних задач теорії алгебраїчних кривих і геометрії чисел, а також дало змогу висунути нові гіпотези про структуру та поведінку досліджуваних об’єктів.
10. Встановлено зв’язок теорії алгебраїчних кривих, критичних ґраток і динамічних систем та отримані наслідки існування такого зв’язку.
11. Розроблено ефективний (і навіть лінійний) метод обчислення розрізаючих множин вершин графів та орієнтованих графів.
12. За допомогою розроблених методів, алгоритмів та обчислень доведена гіпотеза Мінковського про критичний визначник області в околі .
Всі ці результати отримані вперше.
Практична та теоретична цінність. Робота має теоретичний характер. Результати й методи можуть бути використані в теорії передавання інформації та криптографії, у задачах мінімізації, у чисельному аналізі, в теорії динамічних систем, у математичній та теоретичній фізиці, в алгебрі, аналізі, геометрії та теорії чисел.
Апробація результатів дисертації. Результати виконання досліджень дисертації доповідалися на різних конференціях, семінарах, у тому числі на: наукових семінарах Інституту кібернетика ім. В.М. Глушкова НАН України; Всесоюзній конференції із проблем аналітичної теорії чисел (Вільнюс, 1974); Всесоюзній школі-семінарі з теорії чисел (Душанбе, 1977); Всесоюзному симпозіумі з штучного інтелекту і автоматизації досліджень в математиці (Київ, 1978); Всесоюзній конференції “Банки даних” (Тбілісі, 1980); Всесоюзній конференції з аналітичних обчислень в механіці (Горький, 1984); Всесоюзній конференції з теорії чисел та її застосувань (Тбілісі, 1985); Республіканській конференції з надійності та якості програмового забезпечення (Львів, 1985); Міжнародних конференціях “Аналитические вычисления на ЭВМ и их применения в теоретической физике” (Дубна, 1979, 1982, 1985); на семінарах Наукової ради АН СССР з проблеми “Кібернетика” (Москва, 1987); Всесоюзних нарадах з інтервального аналізу (Красноярськ, 1988; Абакан 1989); Всесоюзній школі з конструктивних методів і алгоритмів теорії чисел (Мінськ, 1989); Семінарі по інтервальній математиці (Саратов, 1990); International Symposiums on Computer Arithmetic (SCAN-90, Albena: Bulgarian, 1990; SCAN-93, Wien: Austria, 1993; SCAN-2000, Karlsruhe: Germany, 2000; SCAN-2002, Paris: France, 2002); Міжнародній конференції “ИНТЕРВАЛ-92” (Москва, 1992); International Conference “Numerical Analysis with Automatic Result Verification” (Lafayette: USA, 1993); International Congress of Computer Systems and Applied Mathematics (CSAM'93) (St. Petersburg, 1993); International Conference on Interval and Computer-Algebraic Methods in Science and Engineering (St. Petersburg, 1994); Міжнародній конференції з теорії чисел (Воронеж, 1995); Семінарах Інституту обчислювальних технологій (Новосибірськ, 1994, 1995); International Workshop on New Computer Technologies in Control Systems (Pereslavl’-Zaleskij (Russia), 1996); Міжнародній алгебраїчній конференції (Слов’янськ, 1997); Seminar of Mathematical Institute of Stockholm University (Stockholm, 1998); International seminar "Geometry and Physics" (Mittag-Leffler Institute: Sweden, 1998); International Summer school "Algebraic geometry and physics: Mirror Symmetry in String Theory" (CIRM, Luminy: France, 1999); 6th IMACS International Conference on Applications of Computer Algebra (St. Petersburg: Euler Int. Math. Institute, 2000); International conference "Foliations: Geometry and Dynamics" (S. Banach Math. Center, Warsaw: Poland, 2001); International Conference on Discrete Mathematics (Moscow, 1998, 2001); International Conference "Fractals in Graz 2001. Analysis-Dynamics-Geometry- Stochastics" (Technical University of Graz: Austria, 2001); Міжнародних конференціях з симетрій у нелінійній математичній фізиці (Київ, 2001, 2003); Міжнародних конференціях з геометрії і топології (Черкаси, 2001, 2003); International Conference on Geometrical Structures in the Calculus of Variations (Presov, Slovakia, 2002); Міжнародній конференції пам’яті Б.М. Пшеничного (Київ, 2002); A NATO Advanced Study Institute “Axiomatic, Enriched & Motivic Homotopy Theory” (Cambridge, U.K., Isaac Newton Ins. for Math. Sciences, 2002); International Conferences ACAT (Moscow, 2002; Tsukuba (Japan), 2003); Міжнародній конференції з аналітичної теорії чисел та просторових мозаік пам’яті Г. Вороного (Київ, 2003); International Conference on Computational Noncommutative Algebra and Applications (Pisa, Italy, 2003); Міжнародній конференції пам’яті С.В. Яблонського “Дискретные модели в теории управляющих систем” (Москва, 2004).
Дисертація у цілому доповідалась на об’єднаному науковому семінарі кафедр алгебри і математичної логіки та геометрії Київського національного університету імені Тараса Шевченка, семінарі “Сучасні проблеми криптології” у Національному технічному університеті України “КПІ”, наукових семінарах “Теорія автоматів і застосування” та “Методологія математичного моделювання і дослідження процесів у неоднорідних середовищах” Інституту кібернетика ім. В.М. Глушкова НАН України.
Публікації. Основні результати дисертації опубліковано в 49 наукових статтях, у тому числі 10 статей у співавторстві, 21 стаття опублікована у фахових виданнях, та 38 тезах доповідей на конференціях.
Особистий внесок автора. Усі результати, які виносяться на захист, отримані автором самостійно. Внесок дисертанта в дослідження, за якими опубліковані статті та доповіді в співавторстві, визначається таким чином: [5,53] – розробка структури та алгоритмів підсистеми обчислення з алгебраїчними кривими; [7] – розробка структури системи та між модульного інтерфейсу; [10] – розробка та застосування підсистеми обчислень з алгебраїчними кривими; [13] – форми представлення та інтеграція математичних знань; [15] – інтервальне розширення методу А.В. Малишева, розробка алгоритмів та їхнє застосування, комп’ютерні експерименти та проведення обчислень усередині поверхні Мінковського, [17,57,61] – спеціалізація методу Малишева в околі р = 2 та проведення обчислень в цьому околі; [19] – розробка методу обчислення, алгоритмів та проведення обчислень; [23] – розробка методів інтервального аналізу та методів дослідження алгебраїчних кривих; [26] – математична постановка задачі про інтервальне розширення прямих методів розв’язування вироджених систем лінійних алгебраїчних рівнянь та алгоритми її розв’язання; [31] – математична постановка задачі про інтервальне розширення предметної області та розробка алгоритмів побудови такого розширення; [32] – математична постановка задачі про інтервальне розширення методів розв’язування нелінійних диференціальних рівнянь та інтервальне розширення операторних методів; [36] – розробка методів обчислення та алгоритмів в арифметичній геометрії над скінченними полями; [42] – спеціалізація методів гармонійного аналізу до задач теорії чисел та алгоритми їх реалізації; [47] – розробка методу генерування псевдо випадкових послідовностей на базі тригонометричних сум Клостермана та алгоритмів його реалізації; [48] – розробка концептуальної інформаційної моделі теорії формальних і алгебраїчних груп та індексуючих її ключових термінів.
Структура та обсяг дисертації. Робота складається із вступу, п’яти розділів, які містять 8 таблиць, висновків, списку використаних джерел, трьох додатків. Загальний обсяг дисертації складає 287 сторінок. Обсяг роботи без висновків та списку використаних джерел – 263 сторінки. Список використаних джерел налічує 232 найменувань.
ОСНОВНИЙ ЗМІСТ РОБОТИ
Вступ містить історію дослідження та пояснення взаємозв’язків результатів дисертації із дослідженнями інших науковців, інформацією про публікації, особистий внесок здобувача та апробацію роботи.
Змістовна частина дисертації складається з п’яти розділів: “Попередні відомості та результати”, який складається з шести підрозділів, “Раціональні точки, оцінки і рівнорозподіленість на просторах модулів алгебраїчних кривих над простими скінченними полями”, який складається з п’яти підрозділів, “Деякі задачі теорії динамічних систем”, який складається з шести підрозділів, “Гіпотеза Мінковського про критичний визначник області xp + yp < 1, p > 1. Аналітичне формулювання та метод доведення”, який складається з п’яти підрозділів, “Гіпотеза Мінковського про критичний визначник області xp + yp < 1, p > 1, ефективні алгоритми її дослідження та доведення і їхнє застосування” який складається з чотирьох підрозділів. Кожен розділ закінчується висновком.
Перший розділ дисертації присвячений проблемі алгоритмізації досліджень у теорії алгебраїчних кривих та в геометрії чисел, аналітичному (на базі простору модулів Мінковського – Кона) переформулюванню гіпотези Мінковського про критичний визначник області xp + yp < 1, p > 1, алгоритмам інтервальних обчислень та деяким теоретико-графовим алгоритмам, розробленим автором, викладу потрібних нам у подальшому результатів теорії категорій і функторів та гомологічної алгебри. Наведені в розділі пропозиція 1.4.1 та пропозиція 1.4.2 дають методи обчислення інтервальних розширень раціональних та монотонних функцій, а також суперпозицій таких функцій. Введене поняття та методика найкращого q – наближення (де q є натуральне число) знизу та зверху дійсного числа, яке дає основу ефективної раціональної апроксимації дійсних чисел та їхньої інтервальної раціональної апроксимації. Дано опис досить простої комп’ютерної системи раціональної інтервальної арифметики на мові РЕД’ЮС. Текст програм цієї комп’ютерної системи наведено в додатку А. Наведено розроблені автором оптимальні та близькі до оптимальних методи обчислення у комп’ютерних інтервальних арифметиках, у тому числі для комп’ютерів типу КРЕЙ-2, та реалізуючі їх ефективні алгоритми. Дано опис розробленої автором досить простої та ефективної комп’ютерної системи обчислень розрізаючи множин неорієнтованих та орієнтованих графів. Тексти програм системи наведено, відповідно, у додатках Б та В.
У другому розділі роботи наведено параметризацію досліджуваних у розділі задач, результати про функції щільності, елементарне виведення методом О.Г. Постнікова Постников А.Г. Эргодические вопросы теории сравнений и теории диофантовых приближений. – М.: Наука, 1966. – 112с. з використанням елементарної оцінки С.О. Степанова Степанов С.А. Конструктивный метод в теории уравнений над конечными полями // Тр. Мат. ин-та АН СССР. – 1973. – 132. – С.237–246. отриманого раніше А. Вейлем Weil A. On some exponential sums // Proc. Nat. Acad. Sci. USA. – 1948. – 34. – 204–207. методами алгебраїчної геометрії виразу для сум Клостермана, експериментально вивчаються розподіленість кутів тригонометричних сум Клостермана у функціональному випадку та над замкненою множиною афінної схеми Spec Z, яка параметризує такі суми Клостермана, раціональні точки алгебраїчних кривих вигляду y2 = f(x) над простими скінченними полями, раціональні точки гіпереліптичних кривих над просторами модулів таких кривих. Основні результати розділу містяться у четвертому та п’ятому параграфах. Нехай
yp – y = cx + d/x , c, d Z , c , d ¬--0 (mod p) (1)
– накриття АртінаШраєра Серр Ж.-Р. Алгебраические группы и поля классов. – М.: Мир, 1968. – 285с. над полем Fpr (r > 1) – скінченним розширенням простого скінченного поля Fp . Нехай
f(t) = tn + a1 tn-1 + … + an-1 t + an (2)
многочлен з Fpr[t] із an 0 у Fp. У деякому скінченому розширенні k поля Fp має місце розклад
f(t)=(t - )…(t - ).
Позначимо
l(f) = c(+ …+ ) + d(1/ + …+ 1/) ,
де ,…, корені (2). Для поліномів (2) має місце
. (3)
Нехай Tr: Fpr Fp - відображення сліду. Тоді в умовах (3) має місце
.
Визначимо = , де одне з чисел 0, 1, 2,…, p-1, , якщо an = 0 у Fp. Для накрить вигляду (1) над Fpr L – функцію визначають рівністю
L(z,) = . (4)
Теорема 2.4.2. Добуток (4) збігається при . Функція (4) є поліномом другого степеня і має вигляд
.
Теорема 2.4.6. Корені добутку (4) мають абсолютну величину, яка дорівнює 1/.
Наслідок. =2cos(c, d).
У підрозділі чотири досліджено на ЕОМ розподіл кутів сум Клостермана вигляду А) (функціональний випадок) та Б) (арифметичний випадок) щодо гіпотези (у випадку А нині теорема Деліня–Каца) про рівнорозподіленість кутів на інтервалі [0, ] з функцією щільності .
А) = .
Обчислення та теорія демонструють, що розподіл значень кутів сум за U= [, ], i = 1, 2. 20, при c = const, 1 d p–1 однаковий при різних 1 c p–1. Нехай p = 1597, c = 890, 1 d p–1.
Твердження 2.4.8. У випадку А) з 16 степенями вільності = 7,52
(за - критерієм Пірсона).
Б) = . Обчислення проведені для 1600 послідовних простих від 2 до 13499.
Твердження 2.4.9. У випадку Б) з 15 степенями вільності = 10,43. Із 5% рівнем значимості за критерієм Пірсона гіпотеза про рівнорозподіленість значень кутів на інтервалі [0, ] з функцією щільності справедлива.
У п’ятому підрозділі розділу вивчаються раціональні точки алгебраїчних кривих вигляду y2 = f(x) над простими скінченними полями. Нехай n 3 – непарне число, p > 2 – просте число, f(x) – унітарний поліном степеня n, f(x)Fp[x]. Розглянемо криву
y2 = f(x), (5)
Оцінки Хассе–Вейля для гіпереліптичної кривої роду g,
С(Fp) – р 2g.
Із оцінки Мітькіна Митькин Д.А. Существование рациональных точек // Вест. МГУ. Сер. Математика и механика. – 1975. – № 6. – С. 86–90.
випливає, що при p > (n + 1)2 / 2 – 2 крива
y2 = x5 + ax4 + bx3 + cx2 + dx + e, (6)
при p > 13 завжди має розв’язки у полі Fp. Коли p = 2, 3, 5, 7, 11, існують приклади кривих вигляду (6), які не мають точок у Fp. Автор провів обчислення, із яких випливає, що крива (6) завжди має розв’язки у полі F13. За допомогою відомих оцінок цей результат отриманий бути не може. У зв’язку з цим введемо
Означення. Будемо називати параметричний простір An(k) факторизуючим над полем k, якщо кожна крива над цим простором має точку в k.
З оцінок Гассе, Вейля, Мітькіна випливає
Пропозиція 2.5.1. При достатньо великому p po (границя po залежить від n) простір An(Fp) є факторизуючим для кривих (5).
Нехай
Hg,p = {P2g+1(Fp)\Disk(Cg) = 0}.
Вищенаведений результат з кривою (6) у полі F13 дає
Пропозиція 2.5.2. Виконання оцінок Хассе, Вейля, Мітькіна у афінному та проективному просторах є досить для того, щоб простори, відповідно An(Fp) та Hg,p були факторизуючими, але не є необхідними.
У зв’язку з вищенаведеним постає задача, яку ми назвали задачею Постнікова (проблема точної оцінки). Чи існують для сімейств просторів {An(Fp)} та {Hg,p} кривих точні оцінки, які поділяють ці сімейства на факторизуючі та нефакторизуючі простори? Якщо такі оцінки існують, який їх вигляд?
Інколи важливо мати приклади кривих, які не мають розв’язків.
Теорема 2.5.3. Нехай A(p-1)/2(Fp) – параметричний простір кривих (5), а просте p 3 (mod 4) . Тоді при p 11 над його січенням (a1,…,a(p-3)/2) = (0,…,0) існують криві з a(p-1)/2 0 які
