RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2014, том 50, выпуск 4, страницы 22–42 (Mi ppi2151)

Эта публикация цитируется в 6 статьях

Теория кодирования

Верхние границы наименьшего размера полных дуг в $PG(2,q)$ при некотором вероятностном предположении

Д. Бартолиa, А. А. Давыдовb, Дж. Фаинаa, А. А. Крещукb, С. Маркуджиниa, Ф. Памбьянкоa

a Университет Перуджи, Италия, факультет математики и компьютерных наук
b Институт проблем передачи информации им. А. А. Харкевича РАН

Аннотация: В проективной плоскости $PG(2,q)$ рассматривается итеративная конструкция полных дуг, добавляющая одну новую точку на каждом шаге. Доказано, что непокрытые точки равномерно распределены на плоскости. Для более чем половины шагов итеративного процесса доказана оценка числа новых покрытых точек. Сделано естественное (и обоснованное) предположение, что эта оценка справедлива и для остальных шагов. В результате получены верхние границы наименьшего размера $t_2(2,q)$ полных дуг в $PG(2,q)$, в частности,
\begin{align*} &t_2(2,q)<\sqrt q\sqrt{3\ln q+\ln\ln q+\ln 3}+\sqrt{\frac q{3\ln q}}+3,\\ &t_2(2,q)<1{,}87\sqrt{q\ln q}. \end{align*}
Рассмотрены нестандартные типы верхних границ для $t_2(2,q)$, один из которых является новым. Эффективность новых границ проиллюстрирована сравнением с наименьшими известными размерами полных дуг, полученными в недавних работах авторов и в данной статье путем компьютерного поиска в широком диапазоне значений $q$. Отмечена связь рассматриваемых вопросов с так называемым парадоксом дней рождения.

УДК: 621.391.1+519.1

Поступила в редакцию: 19.04.2014
После переработки: 25.08.2014


 Англоязычная версия: Problems of Information Transmission, 2014, 50:4, 320–339

Реферативные базы данных:


© МИАН, 2024