Przeskocz do treści

Delta mi!

Loading

Analiza na kostce dyskretnej

Kostką dyskretną wymiaru n nazywamy {−1; 1}n; czyli zbiór wierzchołków kostki [−1;1]n; stanowiącej |n -wymiarowy odpowiednik sześcianu...

Rozważmy na niej działanie mnożenia po współrzędnych,

(x1,x2,...,xn)⋅(y1,y2,...,yn) = (x1y1,x2y2,...,xnyn).

Nietrudno sprawdzić, że dla dowolnych wierzchołków kostki |u,v,w :

  • u ⋅v również jest wierzchołkiem kostki oraz (u ⋅v) ⋅w
  • u ⋅(1,1,...,1) = (1,1,...,1) ⋅u = u, czyli |(1,1,...,1) jest "wierzchołkiem neutralnym" przedstawionego działania,
  • u ⋅u = (1,1,...,1), zatem dla każdego wierzchołka istnieje "wierzchołek odwrotny", czyli... on sam,
  • u ⋅v = v ⋅u, w związku z czym badane działanie jest przemienne.

Przedstawione własności czynią z kostki dyskretnej z mnożeniem po współrzędnych grupę przemienną. Na skończonych (a także, ogólniej, lokalnie zwartych) grupach przemiennych można uprawiać analizę harmoniczną - jak zaraz zobaczymy, na kostce dyskretnej wystarczy do tego bardzo elementarny język.

obrazek

Przyporządkujmy każdemu z wierzchołków liczbę rzeczywistą. Możemy oczywiście zrobić to na wiele różnych sposobów i każde takie przyporządkowanie jest niczym innym, jak funkcją określoną na kostce dyskretnej. Mając do dyspozycji dwie takie funkcje,  f i |g, wprowadźmy ich iloczyn skalarny, czyli sumę iloczynów wartości tych funkcji, rozciągającą się po wszystkich 2n wierzchołkach:

⟨ f ,g⟩= Q f(x)g(x). x> !− 1,1 n

Każdy wierzchołek ma |n współrzędnych, więc dla każdego A możemy rozpatrzyć funkcję, która wierzchołkowi przyporządkowuje iloczyn współrzędnych o wskaźnikach ze zbioru |A, tzn. funkcję

wA(x)

Przyjmujemy ponadto w Oczywiście, funkcji tych jest dokładnie tyle co podzbiorów |[n], czyli 2n. Dla A mamy

 Q wA(x) x>!−1,1 n (1)

Aby się o tym przekonać, wybierzmy dowolną liczbę |k∈ A i zauważmy, że

wA(x1,

zatem składniki sumy (1) można pogrupować w "anulujące się" pary. Dla dowolnych A, i dowolnego wierzchołka x mamy też

pict

gdzie A Równości (1) oraz (2) pozwalają łatwo sprawdzić, że jeśli A to |⟨wA, a ⟨wA, Funkcje |wA dla A | tworzą zatem układ ortogonalny. Nietrudno udowodnić, że jest to układ zupełny, tzn. każdą funkcję | n f { −1,1} R można w dokładnie jeden sposób przedstawić w postaci sumy PAb aAwA, gdzie |[n] = {1,2,...,n}, zaś |(aA)Ab są współczynnikami rzeczywistymi. Sumy takie, zwane rozwinięciami Fouriera-Walsha, pełnią na kostce dyskretnej rolę zbliżoną do tej, którą w klasycznej analizie harmonicznej odgrywają rozwinięcia funkcji okresowych w trygonometryczne szeregi Fouriera, tj. szeregi postaci |a0 + Pn∞ 1an cos(nt)+ Pn∞ 1bnsin(nt). Nieco więcej na ten temat można przeczytać w [1].

Wśród funkcji określonych na kostce dyskretnej szczególne zainteresowanie budzą w ostatnich latach funkcje przyjmujące tylko wartości | −1 i | 1. Każdą funkcję | n f {− 1,1} {−1,1} można bowiem naturalnie utożsamić z podzbiorem  −1 f (1) zbioru wszystkich podzbiorów zbioru |[n]. To jednoznaczne przyporządkowanie przydaje się w badaniu zagadnień kombinatorycznych, natomiast z punktu widzenia informatyki teoretycznej ciekawsze jest rozumienie | f jako procedury, która z | n bitów danych wejściowych (input) tworzy jeden bit wyniku, co odpowiada rozmaitym procesom decyzyjnym czy klasyfikacyjnym. O przydatności tego typu rozważań pisał w Delcie 4/2015 Andrzej Dąbrowski. Badaniem funkcji  n | f { −1,1} {− 1,1}, które bliskie są funkcjom afinicznym, zajmujemy się również na Wydziale Matematyki, Informatyki i Mechaniki UW ([2]).


Do czytania
[1]
K. Oleszkiewicz, O pewnym zastosowaniu analizy harmonicznej w rachunku prawdopodobieństwa, Matematyka-Społeczeństwo-Nauczanie 27 (2001), |44 45 (dostępne on-line).
[2]
J. Jendrej, K. Oleszkiewicz i J. O. Wojtaszczyk, On some extensions of the FKN theorem, ma niebawem ukazać się w ogólnodostępnym internetowym czasopiśmie Theory of Computing.