Точное решение экстремальной задачи Дельсарта для неотрицательных полиномов

Экстремальная задача Дельсарта заключается в нахождении величины b D ( n, t ) , определяемой далее формулой (5). Эта величина является оценкой снизу для количества элементов сферических дизайнов порядка t на сфере S n- ¹ .

Начало изучению сферических дизайнов положили статьи [1,2]. Множество Ф = {ф ₁ ,..., ф т } на единичной сфере S n- ¹ называется сферическим дизайном порядка t , если выполняется условие

m

• —    P ( x ) dS = - ^ P ( ф i )

σn            m sn-1                i-1

для любого полинома P ( x ) степени не выше t . Здесь a n - площадь сферы S n- ¹ .

Установлено [1, 2], что количество элементов m такого дизайна удовлетворяет неравенству m >  b _D ( n, t ) . Упрощенное доказательство этого неравенства приводится в [3]. Авторы работ [1, 2] не занимались решением экстремальной задачи Дельсарта, но указали полиномы (разные при t четном и нечетном), которые, в конечном счете, оказались экстремальными полиномами. Наша работа посвящена доказательству экстремальности полиномов, указанных в работе [2].

1.    Полиномы Гегенбауэра

Зафиксируем натуральные числа n и t , n >  3 , t >  2 .

Пусть {Q _k ( x ) } k -₀ - система ортогональных полиномов степени k для веса

W n ( x ) = (1 - x ² ) ⁽ n- ³⁾ / ² .

Запишем условие ортогональности:

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)

:= j [ Q k ( x )]² w n ( x ) dx, k = 0 , 1 ,...

- 1

Полином Q 0 ( x ) равен константе, которую также обозначаем Q 0 и в силу (2) Q о = hQ о h ² .

Пусть 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 ²

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 ⁿ и называется границей Дельсарта (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 ²

E Q i ²

k =0

,

s

F ( x ) =

Г 52 Q k ( x )1²

L k =0       J

F 1 , 0 ^—

/ |E Q k ( .x )

s

W n ( x ) dx — E IQ k I I² .

k =0

В результате получим

является экстремальным и

П 1        /"*П 1

b D ^{( n}, ² s ) — C n + s— 1 ⁺ C n + s — 2 .          ⁽⁶⁾

b D ( n, 2 s ) — F ¹^

Q 0 F 1 , 0

s

E E^Q k 0 ² .

^{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 ₂ ( 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 )] ² .

Разложим полином 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 ⁰    ( a 0 --a ) F ¹ ' ⁰

где F i ( x ) — [ A ( x )] ² . В докладе [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 )] ² + [ B ( x )] ² +

+ (1 - x ) [ C ( x )] ² + (1 - x ² ) [ D ( x )] ² —:

—: 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 )] ² также нужно откинуть. Разложим 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 )] ² . Очевидно, что M 1 > M ₂ , так как C _n ⁿ ₊ ^- _s ¹ _{- 1} > C _n ⁿ ₊ ^- _s ¹ _{- 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 ⁽¹⁾ 6 M 1 ^Q 0 ^F 1 , 0 , ^F 2 ⁽¹⁾ 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 * ^{_ su}p 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 )] ² w n ( x ) dx +    x [ A ( x )] ² 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 | |²

^ak- ² k ⁺ n ^{- 2}' 0Q k +1 0 ^{2 ,}          ₍₂₁₎

_e _ k        0Q k 0 ²

^{e k   2} k + n - ² 0Q k_ 1 0 ² .

По формуле (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 ° ² .

• 4.2.    Явное решение задачи (16) – (17)

Подставив вычисленные интегралы I _kl в (16) придем к задаче

s

F о ( a ) = E a k Q | |² + k =0

s- 1

+ 2 E a k a k +i в к +1 hQ k I I² ^ min ,    (23)

k =0

s

E a k hQ k 1 ² = ± 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 a i в i |Q о I I² = A |Q о | ² ,

^{2 a} k l^Q k I I^{2 + 2 a} k- 1 ^e k ^{| Q} k- 1 I I^{2 +}

^{+ 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 a s- 1 e s IQ s- 1 | |² = A |Q s | ² .

а максимальное значение целевой функции равно bD (n, 2s + 1) =

F * (1)

Q о F о ( a * ) •

Здесь (с учетом формулы (23))

Поскольку a * = 0 , то A = 0 .

Поделим k -е уравнение на 2 |Q _k | |² и обозначим ц = - . Основное уравнение (при k e 1 : s — 1 ) примет вид

„ I „ Q I Q k^{- 1 1}

^a k ^{+ a} k- 1 ^e k       ₂ 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) справедливы соотношения

⁸ о = 1; Y k >  ^{0 , 8} k >  ⁰ • Y k ^{+ 8} k = ¹ • ^{k e 1 : s}-    ⁽²⁶⁾

Лемма 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 ₂ = ц , отсюда a ₂ = a о .

При k = 2 : y 2 a 1 + a о + 8 ₂ 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 ² j =о

[ s/ 2]

F о ( a * ) = ц ²E I Q s- 2 j | ² - j =о

Поделив (28) на (29), придем к окончательной формуле

[ s/ 2]

b D ( n, 2 s + 1) = ^ E I Q s- 2 j I ² -      (30)

Q о “ j=о

В докладе [3] доказано, что величина (30) равна 2 С П +1 - 1 , что завершает доказательство теоремы.