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.

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]).