Wielomiany Rudina-Shapiro (ang. Rudin–Shapiro polynomials; także wielomiany Shapiro) – dwa powiązane rekurencyjnie ciągi wielomianów Littlewooda
których wszystkie współczynniki są równe albo . Wielomiany stopnia spełniają na okręgu jednostkowym podstawową tożsamość
W szczególności
Jest to jeden z klasycznych przykładów deterministycznej konstrukcji wielomianów o współczynnikach , których norma maksimum na okręgu jednostkowym ma ten sam rząd wielkości co ich norma .
Współczynniki wielomianów są kolejnymi początkowymi odcinkami ciągu Rudina–Shapiro. Pary współczynników wielomianów i tworzą ponadto pary komplementarne Golaya: ich nieokresowe autokorelacje sumują się do zera dla każdego niezerowego przesunięcia.
Definicja rekurencyjna W najczęściej stosowanej współcześnie konwencji przyjmuje się
oraz, dla ,
Rekurencję można zapisać w postaci macierzowej:
Ponieważ stopień obu wielomianów na etapie wynosi , składniki i nie mają wspólnych potęg zmiennej. Wynika stąd indukcyjnie, że: i mają stopień ; każdy z nich ma dokładnie niezerowych współczynników; wszystkie ich współczynniki należą do zbioru .
Jeżeli przez i oznaczy się ciągi współczynników odpowiednio i , rekurencja przyjmuje prostą postać konkatenacji:
Pierwsze wielomiany Pierwsze pary mają postać:
oraz
Przykładowo para ciągów współczynników długości 8 jest równa
Współczynniki i ciąg Rudina–Shapiro Pierwsze współczynników wielomianu są współczynnikami . Istnieje zatem jeden nieskończony ciąg
taki, że
Ciąg ten można zdefiniować rekurencyjnie:
Istnieje również opis za pomocą zapisu dwójkowego. Jeżeli
oraz
to jest liczbą wystąpień – także zachodzących na siebie – bloku „11” w zapisie dwójkowym liczby . Wówczas
Przykładowo zapis dwójkowy liczby ma postać i zawiera dwa zachodzące na siebie wystąpienia „11”, wobec czego
Natomiast zawiera jedno takie wystąpienie, więc .
Pierwsze wyrazy ciągu są równe
Wielomian komplementarny można wyznaczyć bezpośrednio z za pomocą tożsamości
Dla wielomianów zachodzi ponadto samopodobna rekurencja
Tożsamość komplementarna Dla dowolnych liczb zespolonych i zachodzi prawo równoległoboku
Jeżeli , to , a więc z definicji rekurencyjnej:
Ponieważ
indukcja daje
Macierz występująca w rekurencji, po pomnożeniu przez , jest dla macierzą unitarną. To właśnie jej unitarność odpowiada zachowaniu – z dokładnością do czynnika 2 – łącznej energii obu wielomianów.
Jeżeli oznaczy się , to dla każdego :
Ponadto co najmniej jeden z dwóch modułów jest nie mniejszy niż .
Związek z parami komplementarnymi Golaya Niech
będzie wielomianem o współczynnikach rzeczywistych. Nieokresową autokorelację ciągu definiuje się przez
Na okręgu jednostkowym zachodzi
Niech i będą ciągami współczynników i . Ponieważ
jest funkcją stałą, porównanie współczynników Fouriera daje
Dla przesunięcia zerowego suma wynosi
Ciągi i tworzą zatem binarną parę komplementarną Golaya. Autokorelacje poszczególnych ciągów nie muszą znikać, ale dla każdego niezerowego przesunięcia znoszą się po zsumowaniu.
Normy na okręgu jednostkowym Dla wielomianu definiuje się znormalizowaną normę
oraz
Ponieważ i mają po współczynników o module 1, z tożsamości Parsevala wynika
Tożsamość komplementarna daje natomiast
W konsekwencji
Dla każdego wielomianu Littlewooda z współczynnikami norma wynosi , a więc jego norma maksimum musi być co najmniej równa . Konstrukcja Rudina–Shapiro daje zatem uniwersalne oszacowanie górne różniące się od tego koniecznego minimum tylko czynnikiem .
Własność ta jest czasem określana jako płaskość wielomianów Rudina–Shapiro. Nie oznacza ona jednak płaskości dwustronnej: konstrukcja nie zapewnia oszacowania
dla wszystkich punktów okręgu i jednej stałej . Już
Ogólne istnienie dwustronnie płaskich wielomianów Littlewooda zostało udowodnione w 2020 roku.
Norma Dla wielomianów Rudina–Shapiro można dokładnie obliczyć normę :
Stąd
a więc
Dla ciągu jego współczynnik jakości autokorelacji, nazywany często merit factor, definiuje się przez
Ponieważ
dla współczynników wielomianu , przy , otrzymuje się
a zatem
Miara Mahlera Miara Mahlera wielomianu jest określona wzorem
Dla wielomianów Rudina–Shapiro długości zachodzi asymptotyka
Oznacza to, że także geometryczna średnia modułu wielomianu na okręgu jednostkowym jest rzędu .
Wartości w szczególnych punktach Z rekurencji wynika
Dla wielomianów komplementarnych:
Relacja
pokazuje, że zera obu wielomianów są związane przekształceniem
Brillhart i Carlitz wykazali również, że wielomiany i mają równe wyróżniki.
Początkowe odcinki dowolnej długości Klasyczne wielomiany mają liczbę wyrazów będącą potęgą 2. Można jednak rozważyć początkowe odcinki nieskończonego ciągu Rudina–Shapiro:
Rudin wykazał, że można dobrać ciąg znaków w taki sposób, aby dla każdego
Dla właściwego ciągu Rudina–Shapiro Paul Balister uzyskał dokładniejsze oszacowanie
Oszacowanie to jest osiągane dla nieskończenie wielu wartości , w szczególności dla
Historia Harold S. Shapiro wprowadził te wielomiany w swojej pracy magisterskiej z 1951 roku, badając problemy ekstremalne dla wielomianów i szeregów potęgowych. Walter Rudin znalazł tę samą konstrukcję w 1958 roku podczas pracy nad sumami trygonometrycznymi o współczynnikach . Po odkryciu dowiedział się o wcześniejszej rozprawie Shapiro i opublikował konstrukcję oraz dowód w 1959 roku za jego zgodą.
Rudin rozważał pytanie, czy dla każdego można znaleźć znaki
takie, aby
dla pewnej stałej niezależnej od . Tożsamość komplementarna wielomianów Rudina–Shapiro daje twierdzącą odpowiedź.
Niezależnie podobne ciągi komplementarne badał Marcel Golay w związku z kodowaniem masek stosowanych w spektrometrii wieloszczelinowej. Z tego powodu ciąg współczynników nazywany jest niekiedy ciągiem Golaya–Rudina–Shapiro, a sama rekurencja – rekurencją Golaya–Rudina–Shapiro.
Zastosowania W analizie harmonicznej wielomiany Rudina–Shapiro dostarczają jawnej, deterministycznej konstrukcji sum trygonometrycznych o współczynnikach i małej normie maksimum. Rudin zastosował je do problemów dotyczących działań funkcji na współczynnikach Fouriera oraz do konstrukcji przykładów granicznych w teorii szeregów Fouriera.
W przetwarzaniu sygnałów własność komplementarności oznacza, że po zsumowaniu odpowiedzi autokorelacyjnych dwóch zakodowanych sygnałów wszystkie listki boczne odpowiadające niezerowym przesunięciom znikają. Pary tego rodzaju są wykorzystywane między innymi w kodowaniu impulsów, systemach radarowych, sonarowych i telekomunikacyjnych.
Oszacowanie
przy średniej mocy
daje stosunek mocy szczytowej do średniej nie większy niż 2:
Mała wartość tego ilorazu jest pożądana w konstrukcji sygnałów o szerokim widmie i ograniczonej amplitudzie.
Uogólnienia Badane są liczne rodziny wielomianów typu Rudina–Shapiro. Powstają one przez zastosowanie podobnej rekurencji do innych wielomianów początkowych, przez użycie współczynników zespolonych o module 1 albo przez zastąpienie pary wielomianów większym układem wielomianów komplementarnych. Analizuje się dla nich między innymi normy , miarę Mahlera, zera, autokorelacje i współczynniki jakości.
Istnieją także: wielowymiarowe odpowiedniki oparte na wielomianach wielu zmiennych; wielofazowe pary komplementarne, których współczynniki są pierwiastkami z jedności; wersje operatorowe i macierzowe; rekurencje rozpoczynające się od dowolnych par komplementarnych Golaya; ciągi typu Rudina–Shapiro związane z innymi wzorcami w cyfrowych zapisach liczb.
Zobacz też ciąg Rudina-Shapiro wielomian Littlewooda para komplementarna Golaya autokorelacja analiza Fouriera
Przypisy
Literatura Harold S. Shapiro, Extremal Problems for Polynomials and Power Series, Massachusetts Institute of Technology, 1951. Walter Rudin, Some Theorems on Fourier Coefficients, „Proceedings of the American Mathematical Society”, 10, 1959, s. 855–859. John Brillhart, Leonard Carlitz, Note on the Shapiro Polynomials, „Proceedings of the American Mathematical Society”, 25, 1970, s. 114–118. Peter Borwein, Rudin–Shapiro Polynomials, w: Computational Excursions in Analysis and Number Theory, Springer, 2002, s. 27–35. Peter Borwein, Michael J. Mossinghoff, Rudin–Shapiro-like polynomials in L₄, „Mathematics of Computation”, 69, 2000, s. 1157–1166. John J. Benedetto, Jesse D. Sugar Moore, Geometric properties of Shapiro–Rudin polynomials, „Involve”, 2, 2009, s. 451–464.
Linki zewnętrzne Harold S. Shapiro, Extremal Problems for Polynomials and Power Series Walter Rudin, Some Theorems on Fourier Coefficients Peter Borwein, Rudin–Shapiro Polynomials John Brillhart i Leonard Carlitz, Note on the Shapiro Polynomials
Kategoria:Wielomiany Kategoria:Analiza harmoniczna Kategoria:Przetwarzanie sygnałów Kategoria:Kombinatoryka