close

Вход

Забыли?

вход по аккаунту

?

Оценка снизу мощности 7-дизайна на сфере S2.

код для вставкиСкачать
Известия Тульского государственного университета
Естественные науки. 2010. Вып. 2. С. 15–23
Математика
УДК 517.5
Оценка снизу мощности 7-дизайна
на сфере S 2 ∗
Д.В. Горбачев
Аннотация. В работе показывается, что чебышевский 7-дизайн
на сфере S 2 содержит не менее 22 точек. При этом известен 7-дизайн
из 24 точек.
Ключевые слова: сфера, дизайн, код, многочлены Гегенбауэра,
задача Дельсарта, полуопределенное программирование.
В работе рассматривается в основном случай единичной сферы S 2 пространства R3 . Однако приводимые результаты обобщаются на произвольные
компактные римановы симметричные пространства ранга 1.
Сферическим (чебышевским) дизайном порядка s (s-дизайном) называn−1 (N = |C|), называемое также
ется множество узлов C = {xk }N
k=1 ⊂ S
кодом, для которого кубатурная формула с равными весами
Z
N
1
1 X
f (xk )
f (x) dx =
|S n−1 | S n−1
N
k=1
точна для любого многочлена f степени s.
Минимальным называется s-дизайн C, который при заданном порядке
точности s имеет наименьшее число точек (мощность) Nn (s). Очевидно, что
Nn (0) = 1 (любая точка).
Рассмотрим случай n = 3. Известны значения N3 (1) = 2 (две противоположные точки), N3 (2) = 4 (вершины правильного тетраэдра), N3 (3) = 6
(вершины октаэдра) и N3 (5) = 12 (вершины икосаэдра). В этих случаях правильную оценку снизу мощности N3 (s) дает известная граница Дельсарта–
Геталса–Зейделя [1]:
½
(r + 1)2 ,
s = 2r,
(1)
N3 (s) >
(r + 1)(r + 2), s = 2r + 1.
Ее вывод опирается на решение при n = 3 экстремальной задачи, называемой сейчас задачей Дельсарта. Пусть Pkn (t) =
*
(α,α)
Pk
(t)
(α,α)
Pk
(1)
, α=
n−3
2 ,
Работа выполнена при финансовой поддержке РФФИ (проект № 10-01-00564).
—
16
Д.В. Горбачев
многочлены Гегенбауэра (при n = 3 это многочлены Лежандра). В задаче
Дельсарта требуется найти величину
Anm (s) = max f (1),
n (s)
f ∈Km
n (s) — класс алгебраических многочленов вида
где m > s, Km
f (t) = 1 +
s
X
ak Pkn (t) −
k=1
m
X
ak Pkn (t),
k=s+1
удовлетворяющих условиям:
f (t) > 0,
t ∈ [−1, 1],
ak > 0,
k > s + 1.
(2)
(при m = s последнее условие отсутствует). Справедлива оценка (LP-оценка
Дельсарта)
Nn (s) > dAnm (s)e,
(3)
где dae — ближайшее к a целое число, не меньшее a.
Приведем вывод этой оценки. Он опирается на два известных свойства
многочленов Гегенбауэра [2]:
1) неотрицательная определенность
X
Pkn (cc0 ) > 0, k > 1
(4)
c,c0 ∈C
(cc0 — скалярное произведение векторов c, c0 ∈ S n−1 , cc = 1), при k = 0 сумма
равна |C|2 ;
2) код C будет s-дизайном тогда и только тогда, когда
X
X
(5)
Pkn (ec) = 0,
Pkn (cc0 ) = 0, 1 6 k 6 s,
c,c0 ∈C
c∈C
где e ∈ S n−1 — произвольная точка.
n (s). Тогда
Пусть f ∈ Km
X
X
X
I=
f (cc0 ) =
f (1) +
f (cc0 ) > |C|f (1)
c,c0 ∈C
c=c0
c6=c0
(здесь используется неотрицательность многочлена f , в силу которого сумму
для c 6= c0 можно отбросить),
I=
X
c,c0 ∈C
1+
s
X
k=1
ak
X
c,c0 ∈C
Pkn (cc0 ) −
m
X
k=s+1
ak
X
Pkn (cc0 ) 6 |C|2 .
c,c0 ∈C
(здесь использовались свойства (4), (5) и неотрицательность коэффициентов ak при k > s + 1). Таким образом, |C| > f (1) и осталось учесть, что Nn (s)
целое число.
Оценка снизу мощности 7-дизайна на сфере S 2
17
В работе [1] найдена величина Ans (s). Экстремальными в этой задаче
являются многочлены

³ (1,0) ´2

(r + 1)2 Pr(1,0) (t) ,
s = 2r,
Pr
(1)
³ (1,1) ´2
fs (t) =
fs ∈ Ks3 (s). (6)
P
(t)

1+t
r
(r + 1)(r + 2) 2
, s = 2r + 1,
(1,1)
Pr
(1)
Если в задаче Дельсарта степень многочленов m устремить в бесконечность, то в пределе получим соответствующую задачу An (s) для функций.
Она исследовалась В. А. Юдиным [3]. Он построил пример допустимой функции с достаточно большим значением в единице. В случае n = 3 она дает
оценку A3 (s) > 2/(1 − t1s ), где t1s — ближайший к единице нуль многочлена
(1,1)
Ps (t), откуда
l 2 m
N3 (s) >
(7)
.
1 − t1s
Эта оценка улучшает границу (1) при больших s, а при s = 2, 3, 5 также дает
правильную нижнюю оценку мощности N3 (s).
Границы (1) и (7) неточные уже при s = 4. Они дают оценку N3 (s) > 9,
хотя, как будет показано далее N3 (4) > 10. Правда и последняя оценка
скорее всего неточна для случая чебышевских дизайнов, а верно равенство
N3 (4) = 12. Отметим, что оценка (3) справедлива для дизайнов с произвольными положительными весами, а экспериментально можно показать
существование 4-дизайна с неравными весами из 10 точек.
Рассмотрим случай n = 3, s = 7. Границы (1) и (7) дают оценку N3 (7) >
> 20. При этом известен 7-дизайн [4], состоящий из 24 точек. Следовательно,
N3 (7) 6 24.
В [5] приведена оценка N3 (7) > 21. Она получается, если решать, например, задачу A311 (7). Ее приближенное решение легко получить методом, описанным в книге [6, с. 430], где рассматриваются аналогичные задачи для случая оценки мощности кодов. Этот метод заключается в заn (s) на целом отрезмене условия неотрицательности многочлена f ∈ Km
ке [−1, 1] (непрерывное условие), условием неотрицательности f (ti ) > 0 в
узлах густой равномерной сетки {ti = −1 + i/M }2M
i=0 ⊂ [−1, 1] (дискретное
условие). Это приводит к обычной задаче линейного программирования.
Из ее решения находятся приближенные значения коэффициентов экстремального многочлена и соответствующий им многочлен fe. Далее находится оценка снизу µ минимального значения многочлена fe на [−1, 1].
Значение µ должно быть отрицательным и близким к нулю. Тогда мноn (s) и его применение дает оценку
гочлен f ∗ (t) = (fe(t) − µ)/(1 − µ) ∈ Km
∗
n
Am (s) > f (1). Для случая n = 3, s = 7, m = 11, M = 300 (Maple, Digits равно
100) имеем µ = −0.0001573 и A311 (7) > f ∗ (1) > 20.282581. Отсюда и из (3)
следует, что N3 (7) > 21. Отметим, что действуя по этой схеме в случае s = 4,
m = 7 получаем µ = −0.00002 и A37 (4) > 9.282, откуда N3 (4) > 10.
18
Д.В. Горбачев
В [5] для решения задачи Anm (s) предлагается более прямой метод, основанный на сведении задачи Дельсарта к некоторой задаче полуопределенного
программирования (SDP-задаче). Этот способ приводит к тем же оценкам
A311 (7) и, соответственно, N3 (7). При этом увеличение степени m > 11 лишь
чуть уточняет оценку величины A3m (7), что дает основания предположить,
что A3 (7) < 21. Для доказательства этой гипотезы можно пробовать применить оригинальную методику работы [7], где исследуется задача Дельсарта
для кодов.
Таким образом, для получения лучших границ необходимо усовершенствовать сам метод Дельсарта. Для случая сферических кодов это сделано
в [8], где схема Дельсарта обобщается за счет использования трехточечного
распределения кода и неотрицательной определенности на нем некоторых
матричных функций, выражаемых через многочлены Гегенбауэра. При этом
возникает экстремальная задача для многочленов от трех переменных, также сводящаяся к SDP-задаче. Это позволило авторам работы [8] получить
существенное продвижение в оценке мощности сферических кодов, в частности, контактных чисел. В работе [9] SDP-метод [8] обобщается на случай
оценки энергии электронов на сфере (задачи Томсона).
Далее кратко приведем модификацию SDP-метода [8] на случай сферических s-дизайнов, являющихся τ -кодами. В итоге она позволяет получить
следующий главный результат работы.
Теорема. Справедлива оценка
N3 (7) > 22.
При выводе SDP-оценки будем использовать обозначения и результаты
из работ [8–10]. Конечное множество C ⊂ S n−1 называется τ -кодом, если
maxc6=c0 ∈C cc0 = τ . Рассмотрим трехточечное распределение C:
¯
1 ¯¯
x(u, v, t) =
{c, c0 , c00 ∈ C : cc0 = u, cc00 = v, c0 c00 = t}¯.
|C|
³1 u v´
Здесь −1 6 u, v, t 6 1. При этом матрица Грама u 1 t < 0 (неотрицательно
v t 1
определенная), что дает условие
1 + 2uvt − u2 − v 2 − t2 > 0.
¯
¯
1 ¯
Величина x(u, u, 1) = |C|
{c, c0 ∈ C : cc0 = u}¯ является двухточечным распределением кода C.
Для τ -кода C имеем: x(u, v, t) = 0 при τ < u, v, t < 1, x(u, u, 1) = 0 при
τ < u < 1.
Справедливы равенства (u, v, t пробегают все допустимые значения):
µX
¶2
X
2
|C| =
x(u, v, t) =
x(u, u, 1) ,
u,v,t
u
Оценка снизу мощности 7-дизайна на сфере S 2
19
Свойства многочленов Гегенбауэра (4) и (5) (второе равенство) можно записать в виде
X
X
x(u, u, 1)Pkn (u) > 0, k > 1,
x(u, u, 1)Pkn (u) = 0, 1 6 k 6 s.
u
u
В [8, 10] вводятся симметричные матрицы
©
ªd−k
Skn (u, v, t) = (Skn )ij (u, v, t) i,j=0 ,
k = 0, 1, 2, . . . ,
где d > 0 — некоторое целое число, задаваемое как и m произвольно. Элементы этих матриц (Skn )ij (u, v, t) являются симметричными многочленами
степени, не большей 2d, и выражаются через многочлены Гегенбауэра:
1£ n
(Skn )ij (u, v, t) =
(Yk )ij (u, v, t) + (Ykn )ij (u, t, v) + (Ykn )ij (v, u, t) +
6
¤
+ (Ykn )ij (v, t, u) + (Ykn )ij (t, u, v) + (Ykn )ij (t, v, u) ,
³
´
t − uv
(Ykn )ij (u, v, t) = ui v j [(1 − u2 )(1 − v 2 )]k/2 Pkn−1 p
(8)
.
(1 − u2 )(1 − v 2 )
Для k > 1 значения Skn (1, 1, 1) = 0.
Матрицы Skn (u, v, t) обладают следующим свойством неотрицательной
определенности
X
Skn (cc0 , cc00 , c0 c00 ) < 0,
c,c0 ,c00 ∈C
откуда
X
x(u, v, t)Skn (u, v, t) < 0,
k > 0.
u,v,t
Кратко отметим идею получения этого свойства. Пусть e ∈ C — произвольная точка кода C, Sen−2 — большой круг с направляющим вектором e (это
сфера S n−2 ). Точки кода c ∈ C проецируются на Sen−2 продолжением до
пересечения с Sen−2 геодезических линий ec. На Sen−2 проекции образуют
сферический код, для которого верно свойство неотрицательной определенности (4), только с заменой n на n − 1 (это объясняет появление в (8) для
многочлена Гегенбауэра индекса n − 1).
Положим I = [−1, τ ], D0 = {(u, u, 1) : u ∈ I},
D = {(u, v, t) : − 1 6 u 6 v 6 t 6 τ, 1 + 2uvt − u2 − v 2 − t2 > 0},
(9)
и введем новые переменные
x0 (u, v, t) = m(u, v, t)x(u, v, t) > 0,
(u, v, t) ∈ D ∪ D0 ,
(10)
где m(u, v, t) = 1 при u = v = t, m(u, v, t) = 3 при u = v 6= t, u 6= v = t, u = t 6= v
и m(u, v, t) = 6 при u 6= v 6= t.
20
Д.В. Горбачев
В новых переменных имеем:
X
2
|C| = 1 +
µ
¶2
1X 0
x (u, v, t) = 1 +
x (u, u, 1) ,
3
0
(u,v,t)∈D∪D0
(11)
u∈I
1X 0
x (u, u, 1)Pkn (u) > −1,
3
k > 1,
(12)
u∈I
1X 0
x (u, u, 1)Pkn (u) = −1, 1 6 k 6 s,
3
u∈I
X
Skn (1, 1, 1) +
x0 (u, v, t)Skn (u, v, t) < 0, k > 0.
(13)
(14)
(u,v,t)∈D∪D0
Из (11) следует, что σ + σ 0 − σ 2 = 0, где
1X 0
σ=
x (u, u, 1) = |C| − 1, σ 0 =
3
u∈I
¡1
X
x0 (u, v, t).
(u,v,t)∈D
¢
σ
Это означает, что матрица σ σ+σ
< 0 или
0
µ
¶
¶
µ
X
1X 0
1 0
0 1
+
+
x (u, u, 1)
1 1
0 0
3
u∈I
(u,v,t)∈D
µ
¶
0 0
x (u, v, t)
< 0.
0 1
0
(15)
Выведем усовершенствованную SDP-оценку Дельсарта для s-дизайнов,
являющихся τ -кодами. Необходимо минимизировать количество точек |C|.
Используя выписанные выше соотношения, приходим к следующей экстремальной задаче. Найти
½ X
¾
1
0
1 + min
x (u, u, 1)
(16)
3
u∈I
при выполнении условий (10), (15), (14), (13) и (12) (это условие пересекается
с (13) и поэтому выписывается только при k > s + 1) .
Переменные x0 принимают дискретные значения, поэтому удобно перейти
к двойственной задаче, которая оценивает решение задачи (16) и, как следствие, мощность s-дизайна, являющегося τ -кодом, снизу: найти
½X
¾
s
m
X
n
0
n
Bm,d (s, τ ) = 1 + max
ak −
ak − b11 − tr(F0 S0 (1, 1, 1))
(17)
k=1
k=1
при условиях: для u ∈ I
g(u) =
m
X
k=1
ak Pkn (u) −
s
X
k=1
a0k Pkn (u) + b12
+ b21 + b22 + 3
d
X
k=0
tr(Fk Skn (u, u, 1)) 6 1;
Оценка снизу мощности 7-дизайна на сфере S 2
21
для (u, v, t) ∈ D
h(u, v, t) = b22 +
d
X
tr(Fk Skn (u, v, t)) 6 0
k=0
(в силу симметричности многочленов (Skn )ij (u, v, t) теперь в определении (9)
области D можно считать, что −1 6 u, v, t 6 τ );
¶
µ
b11 b12
+
0
.
< 0, Fk ∈ Sd−k+1
ak , ak > 0, B =
b21 b22
Здесь Sr+ — множество неотрицательно определенных матриц размера r × r.
Для τ -кода C, являющегося s-дизайном, имеем
n
|C| > dBm,d
(s, τ )e.
n (s, τ ) можно свести к конечномерной SDP-заСледуя [8, 10] задачу Bm,d
даче. Неотрицательный на всей оси многочлен f (u) степени 2r представляется в виде неотрицательно определенной квадратичной формы (U z, z), где
+
z = (1, u, u2 , . . . , ur ) и U ∈ Sr+1
. Аналогично можно записывать неотрицательные многочлены от большего числа переменных.
Пусть p0 (u) ≡ 1. Введем неотрицательный на I = [−1, τ ] многочлен
p1 (u) = (u + 1)(τ − u). Тогда условие g(u) 6 1, u ∈ I, эквивалентно тождеству
g(u) +
1
X
pi (u)(Gi z, z) = 1,
+
Gi ∈ Sr+1
,
r = max{dm/2e, d}.
(18)
i=0
Аналогично, полагая p0 (u, v, t) ≡ 1, p1 (u, v, t) = p1 (u), p2 (u, v, t) = p2 (v),
p3 (u, v, t) = p3 (t), p4 (u, v, t) = 1 + 2uvt − u2 − v 2 − t2 ,
z = {ui v j tk : 0 6 i, j, k 6 d, i + j + k 6 d} = (z1 , z2 , . . . , zn ),
условие h(u, v, t) 6 0, (u, v, t) ∈ D можно записать в виде
h(u, v, t) −
4
X
pi (u, v, t)(Hi z, z) = 0,
Hi ∈ Sn+ .
(19)
i=0
Введем матрицу переменных
X = A ⊗ A0 ⊗ F ⊗ B ⊗ G ⊗ H,
(20)
0
0
s
d
где A = ⊗m
k=1 ak и A = ⊗k=1 ak (диагональные матрицы), F = ⊗k=0 Fk , G =
= ⊗1i=0 Gi , H = ⊗4i=0 Hi . Здесь U ⊗ V обозначает блочную матрицу ( U0 V0 ). Из
приведенных выше условий следует, что X < 0.
Выписывая в тождествах (18) и (19) коэффициенты многочленов при
переменных u, v, t, получаем соотношения вида tr(Rj X) = δ0j , где j = 0, 1, . . .
. . . , 2r + n, Rj — некоторые симметричные матрицы, δmn — символ Кронекера.
22
Д.В. Горбачев
Таким образом, окончательно приходим к следующей SDP-задаче. Найти
n
Bm,d
(s) = 1 + max tr(QX),
tr(Rj X) = δ0j ,
j = 0, 1, . . . , 2r + n,
где X < 0 и имеет блочную структуру вида (20). Здесь матрица Q определяется из (17).
Теперь докажем основной результат, n = 3, s = 7. Имеем оценку N3 (7) >
> dA311 (7)e = 21. Из нее следует, что 7-дизайн C содержит не менее 21 точки.
Предположим,
P что он содержит N = 21 точку и является τ -кодом. Пусть
fs (t) = 1 + sk=1 ak Pkn (t) — многочлен из (6), s = 7. Для него fs (1) = 20.
Пусть e — произвольная тока кода C, e0 — ближайшая к ней точка из C,
ee0 = τ . Используя свойства многочлена fs и (5) получаем
X
X
I=
fs (ec) = fs (1) + fs (τ ) +
fs (ec) > fs (1) + fs (τ ),
c6=e,e0
c∈C
I=
X
c∈C
1+
s
X
k=1
ak
X
Pkn (ec) = N.
c∈C
Таким образом, N > fs (1) + fs (τ ) и fs (τ ) 6 N − fs (1). В рассматриваемом
случае f7 (τ ) 6 21 − 20 = 1. Уравнение f7 (τ ) = 1 имеет единственное решение на отрезке [−1, 1], равное 0.776. . . Можно считать, что τ = 0.777. Ре3 (7, 0.777) (использовался online SDP-солвер [11]), получаем
шая задачу B12,8
3 (7, 0.777) > 21.012. Таким образом,
B12,8
N3 (7) > 22.
Отметим, что значение 22 в оценке таким методом, по-видимому, улучшить
нельзя, поскольку существует экспериментальный 7-дизайн с неравными
весами из 22 точек.
Тем не менее, выдвинем следующее предположение.
Гипотеза. Минимальный чебышевский 7-дизайн на сфере S 2 содержит
24 точки.
Список литературы
1. Delsarte P., Goethals J.M., Seidel J.J. Spherical codes and design // Geom. Dedicata. 1977. V. 6. P. 363–388.
2. Андреев Н.Н. Минимальный дизайн 11-го порядка на трехмерной сфере //
Матем. заметки. 2000. Т. 67, № 4. С. 489–497.
3. Юдин В.А. Нижние оценки для сферических дизайнов // Изв. РАН. Сер. матем.
1997. Т. 61, № 3. С. 213–223.
4. Hardin R.H., Sloane N.J.A. McLaren’s improved snub cube and other new spherical
designs in three dimensions // Discr. Comp. Geometry. 1996. V. 15. P. 429–441;
www.research.att.com/∼njas/doc/snub.ps
5. Горбачев Д.В., Перов И.Н. Метод решения экстремальных задач Дельсарта при
помощи SDP // Матер. Межд. научн. конф. «Современные проблемы матема-
Оценка снизу мощности 7-дизайна на сфере S 2
6.
7.
8.
9.
10.
11.
23
тики, механики, информатики», Тула, 17–21 ноября 2008. Тула: Изд-во ТулГУ,
2008. С. 43–46.
Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. Т. 2. — М.: Мир,
1990.
Арестов В.В., Бабенко А.Г. О схеме Дельсарта оценки контактных чисел //
Труды МИРАН. 1997. Т. 219. С. 44–73.
Bachoc C., Vallentin F. New upper bounds for kissing numbers from semidefinite
programming // J. Amer. Math. Soc. 2008. V. 21. P. 909–924; arXiv:math/0608426v4
[math.MG].
Горбачев Д.В., Филиппов Д.В. Оценка энергии зарядов на сфере при помощи
SDP // Труды Межд. летней матем. Школы С. Б. Стечкина по теории функций,
Алексин Тульской обл., 1–9 августа, 2007. Тула: Изд-во ТулГУ, 2007. С. 70–78.
Mittelmann H.D., Vallentin F. High accuracy semidefinite programming bounds for
kissing numbers // arXiv:0902.1105v3 [math.OC].
sdpa.indsys.chuo-u.ac.jp/portal/
Горбачев Дмитрий Викторович (dvgmail@mail.ru), д.ф.-м.н., профессор,
кафедра прикладной математики и информатики, Тульский государственный университет.
A lower estimate for the cardinality of a 7-design
on the sphere S 2
D.V. Gorbachev
Abstract. In this paper we show that Chebychev 7-design on the sphere S 2
contains no less than 22 points. In this case 7-design of 24 points is known.
Keywords: sphere, design, code, Gegenbauer polynomials, Delsarte problem,
semidefinite programming.
Gorbachev Dmitry (dvgmail@mail.ru), doctor of physical and mathematical
sciences, professor, department of applied mathematics and computer science,
Tula State University.
Поступила 05.06.2010
Документ
Категория
Без категории
Просмотров
3
Размер файла
691 Кб
Теги
сферы, оценки, снизу, мощности, дизайн
1/--страниц
Пожаловаться на содержимое документа