Точное решение экстремальной задачи Дельсарта для неотрицательных полиномов
Автор: Афонин Р.Е., Певный А.Б.
Журнал: Известия Коми научного центра УрО РАН @izvestia-komisc
Рубрика: Физико-математические науки
Статья в выпуске: 3, 2010 года.
Бесплатный доступ
Максимум целевой функции в задаче Дельсарта является оценкой снизу для количества элементов сферического дизайна порядка t. В статье находится точное решение экстремальной задачи Дельсарта в случае, когда степень полиномов равна t.
Сферические дизайны, неотрицательные полиномы
Короткий адрес: https://sciup.org/14992396
IDR: 14992396
Текст научной статьи Точное решение экстремальной задачи Дельсарта для неотрицательных полиномов
Экстремальная задача Дельсарта заключается в нахождении величины b D ( n, t ) , определяемой далее формулой (5). Эта величина является оценкой снизу для количества элементов сферических дизайнов порядка t на сфере S n- 1 .
Начало изучению сферических дизайнов положили статьи [1,2]. Множество Ф = {ф 1 ,..., ф т } на единичной сфере S n- 1 называется сферическим дизайном порядка t , если выполняется условие
m
-
— P ( x ) dS = - ^ P ( ф i )
σn m sn-1 i-1
для любого полинома P ( x ) степени не выше t . Здесь a n - площадь сферы S n- 1 .
Установлено [1, 2], что количество элементов m такого дизайна удовлетворяет неравенству m > b D ( n, t ) . Упрощенное доказательство этого неравенства приводится в [3]. Авторы работ [1, 2] не занимались решением экстремальной задачи Дельсарта, но указали полиномы (разные при t четном и нечетном), которые, в конечном счете, оказались экстремальными полиномами. Наша работа посвящена доказательству экстремальности полиномов, указанных в работе [2].
1. Полиномы Гегенбауэра
Зафиксируем натуральные числа n и t , n > 3 , t > 2 .
Пусть {Q k ( x ) } k -0 - система ортогональных полиномов степени k для веса
W n ( x ) = (1 - x 2 ) ( n- 3) / 2 .
Запишем условие ортогональности:
Q k ( x ) Q l ( x ) W n ( x ) dx = 0 при k = l. (1)
- 1
Это частный случай полиномов Якоби P k а,в ) при а = в = ( n - 3) / 2 .
При а = в эти полиномы называются полиномами Гегенбауэра или ультрасферическими многочленами [4]. Следуя [5], будем использовать нормировку
Q k (1) = ^Q k h 2 : =
1 2 (2)
:= j [ Q k ( x )]2 w n ( x ) dx, k = 0 , 1 ,...
- 1
Полином Q 0 ( x ) равен константе, которую также обозначаем Q 0 и в силу (2) Q о = hQ о h 2 .
Пусть P t - множество алгебраических полиномов F ( x ) степени не выше t , удовлетворяющих условиям
F ( x ) > 0 для всех x е [ - 1 , 1] и F (1) > 0 . (3)
Каждый полином F ( x ) разложим по полиномам Ге-генбауэра
t
F(x) = ^ Fk Qk (x), k-0
где, в частности,
F 0 =
hQ о h 2
j F ( x ) Q о w n ( x ) dx =
- 1
j F ( x ) w n ( x ) dx > 0 .
- 1
2. Экстремальная задача Дельсарта
Сформулируем задачу Дельсарта [1, 2]. Требуется найти максимум bD (n,t)
F (1) max . F e P t Q 0 F 0
Величина b D ( n, t ) является оценкой снизу количества элементов сферического дизайна порядка t в R n и называется границей Дельсарта (Delsarte bound).
Для задачи (5) можно явно указать экстремальный полином и точно найти b D ( n,t ) . Основным результатом статьи является следующая теорема. Теорема. При t четном, t = 2 s , полином
(1 , 1 ,..., 1) . Тогда F 1 ( x ) — [\ Q k ( x ) ] будет экстре- k =0
мальным полиномом, при этом
s
F 1 (1)— 52 Q k (1)
k =0
s 2
E Q i 2
k =0
,
s
F ( x ) =
Г 52 Q k ( x )12
L k =0 J
F 1 , 0 —
/ |E Q k ( .x )
s
W n ( x ) dx — E IQ k I I2 .
k =0
В результате получим
является экстремальным и
П 1 /"*П 1
b D ( n, 2 s ) — C n + s— 1 + C n + s — 2 . (6)
b D ( n, 2 s ) — F 1^
Q 0 F 1 , 0
s
E E^Q k 0 2 .
Q 0 k =0
При t нечетном, t — 2 s +1 , полином
F ( x ) — (1 + x )
[ s/ 2]
E Q s— 2 j ( x ) j =0
является экстремальным и bD (n, 2s + 1) —2 Cn—1—1. (7)
-
3. Доказательство теоремы для t четного
Пусть t — 2 s , s - натуральное число. Общий вид отрицательного на [ - 1 , 1] полинома приведен в книге Полиа и Сегё ([6], раздел VI). При t — 2 s полином F е P t представляется в виде
F(x) — [A(x)]2 + (1 - x2) [B(x)]2 —: F1(x) + F2(x), где A(x) - полином степени 6 s, а B(x) - полином степени 6 s - 1.
Нулевые коэффициенты Фурье F 1 , 0 и F 2 , 0 неотрицательных на [ - 1 , 1] функций F 1 ( x ) и F 2 ( x ) неотрицательны. Поскольку F 2 (1) — 0 , то
F 1 (1)+ F 2 (1) 6 F 1 (1) . (8)
Q 0 F 1 , 0 + Q 0 F 2 , 0 Q 0 F 1 , 0
Поэтому в задаче (5) достаточно максимизировать по ненулевым полиномам F 1 ( x ) вида F 1 ( x ) — [ A ( x )] 2 .
Разложим полином A ( x ) по полиномам Геген-бауэра
s
A ( x ) — 52 a k Q k ( x ) .
k =0
Предыдущее рассуждение показывает, что
F (1) F 1 (1)
sup —z— — sup —-- , (9)
F e P t F 0 ( a 0 --a ) F 1 ' 0
где F i ( x ) — [ A ( x )] 2 . В докладе [3] доказана следующая лемма.
Лемма 1. Супремум в (9) достигается тогда и только тогда, когда a0 — a 1 — ... — as — 0, т. е. когда все числа {ak} равны между собой и отличны от нуля.
В силу однородности целевой функции в задаче (9) в качестве точки максимума можно взять точку
Величина (10) довольно громоздкими вычислениями найдена в [3] и она равна числу C n . !. 1 + C n— 1 — 2 , что завершает доказательство теоремы при t — 2 s .
-
4. Доказательство теоремы для t нечетного
Пусть теперь t нечетное, t — 2 s + 1 . Полином F е P t можно представить в форме
F ( x ) —(1 + x ) [ A ( x )] 2 + [ B ( x )] 2 +
+ (1 - x ) [ C ( x )] 2 + (1 - x 2 ) [ D ( x )] 2 —:
—: F1( x) + F2( x) + Fз( x) + F4( x), и притом так, что все четыре слагаемых были самое большее степени t (см. [6], раздел VI). Два последних слагаемых можно откинуть, пользуясь тем же рассуждением, что и при t — 2s. Допустим, что хоть один из полиномов C(x) и D(x) отличен от тождественного нуля. Тогда
F 3 , 0 + F 4 , 0 > 0 , F 3 (1) + F 4 (1)—0
и, следовательно,
F (1) — F 1 (1) + F 2 (1) < F 1 (1) + F 2 (1)
F0 F1,0 + F2,0 + F3(1) + F4(1) F1,0 + F2,0 , поэтому экстремальный полином не может содержать слагаемых F3(x) и F4(x).
Более тонко доказывается, что слагаемое F 2 ( x ) — [ B ( x )] 2 также нужно откинуть. Разложим A ( x ) и B ( x ) по полиномам Гегенбауэра:
ss
A ( x ) — E a k Q k ( x ) , B ( x ) — E b k Q k ( x ) , k =0 k =0
и будем рассматривать ненулевые векторы a — ( a 0 , . . . , a s ) и b — ( b 0 , . . . , b s ) . Ранее показано, что
F2(1) a / о A max n F — bD (n, 2s) — ber s+1 Q 0 F 2,0
n— 1 n— 1
— C n + s— 1 + C n + s — 2 —: M 2 .
Введем подпространство
L — {a е R s +1 I a s— 1 — 0 , a s— 3 — 0 , a s— 5 — 0 ,...}.
Для a е L полином A ( x ) имеет вид
[ s/ 2]
A ( x ) — a s— 2 j Q s— 2 j ( x ) .
j =0
Такие полиномы рассматривались в работе [3], лемма 2. Было показано, что ma? F^" = 2 Cn+L1 =: M1 • (12)
a ∈ L Q 0 F 1 , 0
Здесь F 1 ( x ) = (1 + x ) [ A ( x )] 2 . Очевидно, что M 1 > M 2 , так как C n n + - s 1 - 1 > C n n + - s 1 - 2 . Если в (12) взять максимум по всему пространству R s +1 , то максимум не уменьшится:
M 1* := sup -F M- > M 1 . (13)
aE R s +1 Q 0 F 1 , 0
Возьмем произвольные a, b e R s +1 , b _ 0 . В силу (11) и (13)
F 1 (1) 6 M 1 Q 0 F 1 , 0 , F 2 (1) 6 M 2 Q 0 F 2 , 0 < M 1 Q 0 F 2 , 0
Поэтому решение задач (16) и (17) существует и единственно. Когда в (17) стоит +1 , решение обозначим a * , а для - 1 решением будет -a * .
В дальнейшем нам удастся явно решить задачу (16)–(17), но предварительно необходимо вычислить интегралы I kl .
-
4.1. Вычисление интегралов I kl
Нам потребуется рекуррентное соотношение для полиномов Гегенбауэра. Особенно просто оно выглядит для полиномов G k ( x ) с нормировкой G k (1)_1 , k > 0:
( k + n - 2) G k +1 ( x ) _(2 k + n - 2) x G k ( x ) —
- kG k- 1 ( x ) , k > 1 ,
и поэтому
F (1) < M* Q 0 F1,0 + M* Q 0 F2,0 _ m * Q 0 F0 Q 0 F1,0 + Q 0 F2,0 1, и, значит, слагаемое F2(x) _ [B(x)]2 не может входить в экстремальный полином.
Перейдем к нахождению величины где G0(x) = 1, Gi(x) _ x. Перепишем (18) в виде xGk(x)_2kk '. nnt-22 Gk+1(x) +
+ 2 k + kn - 2 G k - 1 ( x ) .
M * _ sup F i) , aE R s +1 Q 0 F 0
Полиномы Gk (x) с постоянным множителем отличаются от Qk(x): Gk(x) _ ckQk(x). При x _ 1 получаем 1 _ CkQk(1) _ Ck 0Qk02. Отсюда где F(x) _ (1 + x) [A(x)]2, A(x) _ £ akQk(x) - произ-k=0
вольный ненулевой полином степени 6 s .
Вычислим F (1) и F 0 . Имеем
c k _
∥ Q k ∥ 2 ,
G k ( x ) _
Q k ( x ) ∥ Q k ∥ 2 .
F (1) _ 2
Е a k ^Q k 0 2
k =0
Подставив последнее выражение в (19), получим
xQ k ( x )_ a k Q k +1 ( x ) + e k Q k- 1 ( x ) , k > 1 , (20)
F 0
_ j [ A ( x )] 2 w n ( x ) dx + x [ A ( x )] 2 w n ( x ) dx _
- 1
- 1
ss
_ Eak Q02 +E Iklakai, k=0 k,l=0
где
I kl _ / .
xQ k ( x ) Q i ( x ) W n ( x ) dx.
Отметим сразу, что I kl _ I lk и I kk _ 0 , так как при k _ l получается интеграл от нечётной функции.
При решении задачи (14) можно фиксировать числитель и минимизировать знаменатель. Можно считать, что вектор a ∈ R s +1 удовлетворяет ограничению F (1) _ 2 . Приходим к задаче квадратичного программирования
s
F э ( a ) _ Е a k HQ k H 2 + 2 Е ^k a ^ min , (16)
k
=0
k
_ k + n - 2 ||Q k | |2
ak- 2 k + n - 2' 0Q k +1 0 2 , (21)
e _ k 0Q k 0 2
e k 2 k + n - 2 0Q k_ 1 0 2 .
По формуле (7) доклада [3]
Il/l I 2 _ 2 k + n - 2 Г( k + n - 2)
0 Q k 0 _ 2 n- 2 ‘ k !Г 2 ( n- 1 ) .
Если подставить в (21), то получим k +1 o k + n - 3 /Пих ak I , ek i л" (22)
2 k + n 2 k + n - 4
Теперь можно вычислить интеграл (15) при l > k :
s
E a k 0Q k 0 2 _ ± 1 . (17)
k =0
Собственно здесь две задачи - для +1 и - 1 . Целевая функция F 0 ( a ) является положительно определенной квадратичной формой:
F 0 ( a ) _ j F ( x ) W n ( x ) dx > 0 при a _ 0 .
- 1
I kl _ У a k ( x ) [ a i Q i +1 ( x ) + e i Q l- 1 ( x )]
- 1
W n ( x ) dx.
В силу ортогональности системы {Q k } справедливы равенства I ki = 0 при l = k + 2 , k + 3 , . . . , s , а при l _ k +1 получаем (в силу (21))
I k,k +1 _ e k + 1 °Q k ° 2 .
-
4.2. Явное решение задачи (16) – (17)
Подставив вычисленные интегралы I kl в (16) придем к задаче
s
F о ( a ) = E a k Q | |2 + k =0
s- 1
+ 2 E a k a k +i в к +1 hQ k I I2 ^ min , (23)
k =0
s
E a k hQ k 1 2 = ± 1 k =0
Решение a * задачи с +1 существует и единственно, a * =0 .
Необходимое и достаточное условие максимума имеет вид
^FM = A IQk ||2 , k e 0: s, ∂ak где λ – множитель Лагранжа. Придем к системе уравнений
По индукции можно доказать, что ai = ц — a о при i нечётном, ai = a о при i чётном -
Если s чётно, то из уравнения Y s a s - 1 + a s = ц получим Y s ( ц — a о ) + a о = ц , откуда a о = ц и получаем решение (27). Если же s нечётно, то Y s a о + ц — a о = ц , значит, a о = 0 и снова получим решение (27).
Лемма доказана.
Вектор a ∗ , определенный равенствами (27), является точкой максимума в задаче (16)–(17) (неизвестный параметр µ определяется из ограничения s
Z a k I Q k h = 1 ).
k =о
Этот же вектор a ∗ будет являться точкой максимума в задаче (14). Экстремальный полином имеет вид
F * ( x ) = (1 + x )
[ s/ 2]
ц E Q s- 2 j ( x ) j =о
2 a о IQ о | 2 + 2 a i в i |Q о I I2 = A |Q о | 2 ,
2 a k lQ k I I2 + 2 a k- 1 e k | Q k- 1 I I2 +
+ 2 a k +1 e k +1 | Q k 1 2 = A | Q k 1 2 , k e 1 : s — 1 , 2 a s ||Q s | |2 + 2 a s- 1 e s IQ s- 1 | |2 = A |Q s | 2 .
а максимальное значение целевой функции равно bD (n, 2s + 1) =
F * (1)
Q о F о ( a * ) •
Здесь (с учетом формулы (23))
Поскольку a * = 0 , то A = 0 .
Поделим k -е уравнение на 2 |Q k | |2 и обозначим ц = - . Основное уравнение (при k e 1 : s — 1 ) примет вид
„ I „ Q I Q k- 1 1
a k + a k- 1 e k 2 I a k + 1 e k +1 = ц-
∥ Q k ∥
Вычислим коэффициенты этого уравнения. В силу (21) и (22)
iQ-lf
Yk "k QII2 2k + n - 2 •(24)
_ k + n — 2
Ok := ek + 1 = 771—.77
+ 2 k + n - 2
Окончательно систему уравнений для определения a ∗ можно записать в виде
{ Y k a k- 1 + a k + 8 k a k +1 = Ц, k e 0 : s, 1 a - 1 = 0 , a s +1 = 0 .
Здесь ц = A/ 2 = 0 ив силу (24) справедливы соотношения
8 о = 1; Y k > 0 , 8 k > 0 • Y k + 8 k = 1 • k e 1 : s- (26)
Лемма 2. Единственное решение a ∗ системы (25) при условиях (26) состоит из чисел ц и 0 в чередующемся порядке:
a * = ц, a *- 1 = 0 , a *- 2 = ц, a *- 3 = 0 ,--- (27)
Доказательство. Допустим,что {a k } k =о - решение системы (25). Последовательно будем выражать все неизвестные a k через a о .
При k = 0 : a о + a 1 = ц , отсюда a 1 = ц — a о .
При k = 1 : y 1 a о + ц — a о + 8 1 a 2 = ц , отсюда a 2 = a о .
При k = 2 : y 2 a 1 + a о + 8 2 a 3 = ц , отсюда a 3 = ц — a о .
При k = 3 : y 3 a 2 + ц — a о + 8 3 a 4 = ц , отсюда a 4 = a о .
F * (1) = 2
[ s/ 2]
ц Е » Q s- 2 j II 2 j =о
[ s/ 2]
F о ( a * ) = ц 2E I Q s- 2 j | 2 - j =о
Поделив (28) на (29), придем к окончательной формуле
[ s/ 2]
b D ( n, 2 s + 1) = ^ E I Q s- 2 j I 2 - (30)
Q о “ j=о
В докладе [3] доказано, что величина (30) равна 2 С П +1 - 1 , что завершает доказательство теоремы.
Список литературы Точное решение экстремальной задачи Дельсарта для неотрицательных полиномов
- Delsarte Ph. An algebraic approach to the association schemes of coding theory//Philips Res. Reports (Suppl.), 1973. No. 10. P. 1-97.
- Delsarte Ph., Goethals J.M., Seidel J.J. Spherical codes and designs//Geometricae Dedicata, 1977. Vol. 6. No. 3. P. 363-388.
- Афонин P.E., Малозёмов B.H., Певный А.Б. Оценка Дельсарта для количества элементов сферического дизайна//Семинар DHA & CAGD. Избранные до
- Сегё Г. Ортогональные многочлен
- Bannai E., Munemasa A., Venkov B. The nonexistence of certain tight spherical designs//Алгебра и анализ, 2004. Т. 10.
- Полиа Г., Сегё Г. Задачи и теоремы из анализ