Działania łączne w zbiorze n-elementowym

Problem dotyczy wyznaczenia liczby Asso(n) wszystkich dwuargumentowych operacji łącznych:

f : X² $$\rightarrow$$ X

(czyli spełniających: f (f (xy)z) = f (xf (yz)) w n -elementowym zbiorze X.

* * *

Oczywiście wszystkich operacji 2-argumentowych w n-elementowym zbiorze mamy nⁿ². Dla n = 2, 3, 4 otrzymujemy odpowiednio 16 19683 oraz ponad 4 ^. 10⁹, bo 4294967296. Już dla n = 3 sprawa jest nietrywialna.

Dla n = 2 mamy dwie stałe operacje; cztery niestałe, które zależą istotnie tylko od jednej zmiennej - z tych sześciu 4 są łączne: nie są łączne te (tabelki):

	a	b
a	b	a
b	b	a

gdyż:

(bb)b = ab = a, b(bb) = ba = b

oraz:

	a	b
a	b	b
b	a	a

gdyż:

(bb)b = ab = b, b(bb) = ba = a

Następnie mamy dodawanie mod 2 (XOR), równoważność (która też jest taką samą operacją grupową, tyle, że nazwy 0 i 1 są zamienione) oraz AND i OR. To wszystko, gdy chodzi o operacje łączne, w sumie jest ich 8 (na 16). Ciekawe, że wszystkie nietrywialne operacje łączne (zależne istotnie od obu zmiennych) są przemienne.

* * *

Oczywiście dla n = 3 (od biedy nawet dla n=4) można puścić prymitywny program, który sprawdziłby wszystkie operacje binarne.

Ciąg Asso(n) opisany jest w The On-Line Encyclopedia of Integer Sequences.

* * *

Ze zbioru Assno(n) chciałoby się utworzyć jak najbogatszą algebrę.

Ponadto dla specjalnych mocy | X| można uzyskać dodatkowe operacje. Dlatego pomocnym jest tworzenie operacji dla danego X, gdy zna się operacje w innym (lub innych) zbiorze X' (X" itd).

Tyle uwag ogólnych. Powtórzmy do znudzenia, że mamy |X| operacji stałych.

Następnie mamy

2 ^. | IdemNC(X)| - | X|

operacji niestałych, które zależą tylko od jednej ze zmiennych; IdemNC(X) jest tu zbiorem wszystkich odwzorowań idempotentnych f : X $\rightarrow$ X (takich ze fof = f, tzn. f (f (x)) = f (x) dla każdego x $\in$ X), które nie są stałe.

Dla | X| = 2 mamy | IdemNC(X)| = 1, co możemy napisać jako IdemNC(2) = 1; podobnie IdemNC(3) = 7.

Jednym z elementów zbioru IdemNC(X) jest identyczność Id_X : X $\rightarrow$ X, gdzie ID_X(x) : = x dla każdego x $\in$ X.

* * *

Dla | X| = 2 mamy dokładnie 4 różne operacje łączne, które istotnie zalezą od obu zmiennych.

Tak wiec Asso(X) liczy sobie 2 funkcje stale, 2 zależne od jednej zmiennej oraz 4 od obu, czyli Asso(2) = | Asso(X)| = 2 + 2 + 4 = 8

* * *

Niech ID_X $\neq$ f $\in$ IdemNC(X). Niech Y = f (X). Niech G $\in$ Asso(Y).

Pamiętajmy, że f (y) = y dla y $\in$ Y, wiec f (G(xy)) = G(xy) dla dowolnych x, y $\in$ Y.

Możemy zdefiniować F : X² $\rightarrow$ X tak:

F(x, y) = G(f (x), f (y))$$\forall$$x, y $$\in$$ X.

Okazuje się, że F $\in$ Asso(X):

= G(f (G(f (x), f (y))), f (z))

= G(G(f (x), f (y)), f (z)) = G(f (x), G(f (y), f (z)))

= G(f (x), f (G(f (y), f (z))) = F(x, G(f (y), f (z))

= F(x, F(y, z))

dla x, y, z $\in$ X.

Uwaga: dla | X| = 3 skorzystaliśmy z tej konstrukcji już wcześniej, ale bez tak pełnego opisu formalnego.

Dla | X| = 2 nie otrzymujemy nowych operacji, bo nie istnieją dla tak małego X odwzorowania idempotyczne, niestałe i różne od identyczności. Ale dla | X| = 3 jest takich 6. Więc 4 niezdegenerowane operacje w zbiorze 2-elementowym dają 6*4=24 nowe operacje łączne w zbiorze 3-elementowym. Ich uderzającą cechą jest to, że zbiór wartości za każdym razem jest różny od całego X.

* * *

Niech F $\in$ Asso(X). Niech na dodatek F będzie przemienne: F(x, y) = F(y, x) dla xy $\in$ X. Niech a $\in$ X będzie dowolnie ustalone. Zdefiniujmy przesunięcie F o element a:

G(x, y) : = F(F(x, y), a)$$\forall$$xy $$\in$$ X

Wtedy, co łatwo sprawdzić, G $\in$ Asso(X) (przy czym G jest także przemienne).

Na przykład, dla | X| = 3 można wprowadzić w

X : = { -1, 0, 1}

dodawanie modulo 3: F(x, y) : = x + ymod3 Wtedy na przykład G(x, y) : = x + y + 1mod3 też daje operację łączną (i przemienną). Ponieważ wcześniej rozpatrywaliśmy wszystkie 3 różne operacje grupowe w X, to operacja G nie jest dla nas nowa, bo jest to operacja grupowa (której elementem neutralnym jest -1; w miejsce 0). Szkoda :-)

Popatrzmy teraz na operację mnożenia w (ciele) X:

M(x, y) : = x ^. y

Możemy, zgodnie z ogólną receptą, zdefiniować nowa operacje łączną:

N(x, y) : = x ^. y ^. (- 1)

Ponieważ już rozpatrywaliśmy poprzednio wszelkie struktury ciała w X, i ich mnożenia, to operacja N znowu nie jest nowa: jest mnożeniem w ciele X, w którym rolę zera gra dalej 0, a rolę jedności gra -1.

Podobnie operacja max : X² $\rightarrow$ X, skombinowana z przesunięciem, znowu nie prowadzi do nowych operacji.

* * *

TWIERDZENIE (trywialne :-) Niech dane będą f : X $\rightarrow$ X oraz L, R : X² $\rightarrow$ X takie, że:

L(x, y) : = f (x), R(x, y) : = f (y)

Wtedy L jest łączne wtw. R jest łączne wtw. f jest idempotentne (czyli f (f (x)) = f (x) dla dowolnego x $\in$ X).

DOWÓD Gdy f nie jest idempotentne, to f (f (a) $\neq$ f (a) dla pewnego a $\in$ X. Wtedy

L(L(aa)a) = f (f (a)) $$\neq$$ f (a) = L(aL(aa))

i podobnie niełączne jest R.

Natomiast gdy f jest idempotentne, to:

L(L(xy)z) = f (f (x)) = f (x) = L(xL(yz))

i podobnie łączne jest R. KONIEC trywialnego dowodu :-)

* * *

Można powiedzieć, że odwzorowanie idempotentne f : X $\rightarrow$ X jest retrakcją na swój obraz czyli że jest tożsamością na swoim obrazie: jeżeli y jest równe f (x) dla pewnego x $\in$ X, to f (y) = y.

* * *

Łatwo więc policzyć liczbę idempotentnych odwzorowań w zbiorze n-elementowym, których obrazy mają k elementów:

idem(nk) = $$\binom{n}{k}$$ ^. k^n-k

Tak więc w zbiorze 3-elementowym dostajemy:

$$\binom{3}{2}$$ ^. 2¹ + $$\binom{3}{3}$$ ^. 3⁰ = 6 + 1 = 7

niestałych odwzorowań idempotentnych.

* * *

Łącznie z operacjami stałymi dostajemy więc

3 + 2 ^. 7 = 17

operacji łącznych, które są zdegenerowane (nie zależą w sposób istotny od obu zmiennych).

Mieliśmy też (3+6)+6*4 = 33 operacji łącznych, niezdegenerowanych. Łącznie mamy więc 50 operacji łącznych w zbiorze 3-elementowym, dotąd skonstruowanych.

Słabo :-)

* * *

Można też wykorzystać "zwykłe" operacje łączne i niemalejące dla obu argumentów, w liczbach naturalnych z zerem.

np.

f (a, b) = min{2, a + b}
f (a, b) = min{2, a ^. b}
f (a, b) = min{2, a + b + 1}
f (a, b) = min{1, a ^. b}

itp.

Trudno będzie policzyć takie funkcje nie powtarzając się z już policzonymi. Wszystkich jest 113.

Poniższa funkcja "laczne(n)" wypisuje wszystkie operacje łączne dla n -elementowego zbioru w postaci tabelek, w które można się długo wpatrywać aż się coś zobaczy :-)

Toporna jest ale dla n=4 znajduje jeszcze w sensownym czasie te 3492 operacji, może tutaj będzie łatwiej zauważyć bardziej ogólne zależności.

bool czy_laczne(const int* T, const int n) {
     int a, b, c;
     for (a = 0; a < n; a++)
         for (b = 0; b < n; b++)
             for (c = 0; c < n; c++)
                 if (T[T[a*n+b]*n+c] != T[a*n+T[b*n+c]])
                     return false;
     return true;
}

void laczne(const int n) {

     int T[100];
     int count = 0;
     int i, j;

     for (i = 0; i < n; i++)
         for (j = 0; j < n; j++)
             T[i*n+j] = 0;
     T[n*n] = 0;

     while (!T[n*n]) {

         if (czy_laczne(T, n)) {
             count++;
             printf(" \ n# % d: \ n", count);
             for (i = 0; i < n; i++) {
                 printf(" ");
                 for (j = 0; j < n; j++)
                     printf("%d", T[i*n+j]);
                 printf(" \ n");
             }
         }

         i = 0;
         while (true) {
             T[i]++;
             if (T[i] == n) {
                 T[i] = 0;
                 i++;
             } else
                 break;
         }
     }
}

* * *

Niech X = Y $\cup$ {a}. Niech F : Y² $\rightarrow$ Y będzie operacja łączna. Wprowadzmy nastepujace przedluzenia tej operacji na cale X:

F0(a, y) = F0(y, a) : = a

F1(a, y) = F1(y, a) : = y

dla dowolnego y $\in$ Y. Ponadto niech

F0(x, y) = F1(x, y) : = F(x, y)$$\forall$$x, y $$\in$$ Y

Wtedy F0, F1 sa operacjami lacznymi w X, przy ktorych element a gra role odpowiednio zerowego lub jedynkowego.

Otrzymamy w ten sposob nowe operacje laczne dla | X| = 3.

* * *

Powstal w sumie niezly balagan jakby przypadkowych metod. Czy musi tak byc, czy tez wyloni sie cos klarownego?

Zalozmy, ze Y jest niepuste.

Popatrzmy na wlasnosci F0, F1. Obie te operacje maja element a za jedna ze swych wartosci oraz co najmniej jeden z elementow z Y. A wiec nigdy nie sa stale. Co wiecej, nie sa otrzymane z pomoca zadnej funkcji idempotentnej f : X $\rightarrow$ X z operacji w Y. Oczywiscie F1 ma za zbior wartosci cale X, wiec rozni sie od wszelkich operacji otrzymanych za pomoca funkcji idempotentnej, roznej od identycznosci w X.

W wypadku F0 sytuacja jest ciut bardziej zlozona. Ograniczmy sie do 3-elementowego X : = {a, b, c}. Niech Ft : X² $\rightarrow$ X, dla t $\in$ Y bedzie dane nastepujaco:

Ft(a, x) = Ft(x, a) : = a$$\forall$$x $$\in$$ X

Ft(x, y) = t$$\forall$$x, y $$\in$$ Y

Operacje Fb oraz Fc sa jedynymi dwoma typu F0, powstalymi takze z odpowiedniej operacji w Y z pomoca funkcji idempotentnej.

* * *

Niech b $\in$ Y. Wtedy jasnym jest, ze:

F0(a, b) = a $$\neq$$ F0(b, b) $$\in$$ Y

a wiec F0 zalezy w sposob istotny od pierwszej zmiennej. Podobnie takze od drugiej. Takze:

F1(a, a) = a $$\neq$$ b = F1(a, b)

a wiec F1 zalezy istotnie od drugiej zmiennej. Podobnie takze od pierwszej.

Tak wiec operacje typu F0, F1 sa niezdegenerowane (zaleza istotnie od obu zmiennych).

* * *

Operacje mnozenia w X, wzgledem dowolnej struktury ciala w X, o elementcie zerowym a, sa typu F0. Dlatego w dalszym ciagu mnozen nie bedziemy liczyc, a jedynie operacje typu F0.

Operacje dodawania (na ogol nieprzemiennego) grupowego nie sa ani typu F0 ani F1, bo ograniczone do Y = X $\setminus$ {a} nie daja dzialania (nie sa przedluzeniami dzialan w Y).

* * *

Operacje max wzgledem uporzadkowan liniowych w X sa zariowno typu F0, jak i typu F1 (dla roznych wyborow elementu a -warto to przemyslec).

Mamy juz podstawe, zeby lepiej niz uprzednio oszacowac Asso(3) z dolu. Nawet sprawa sie chyba nieco uproscila... hm, no, w kazdym razie niezbyt sie skomplikowala :-)

* * *

Zeby skorzystac w liczeniu Asso(3) z operacji typu F0, F1, dobrze wiedziec ile operacji jest jednoczesnie obu rodzajow. Zadna operacja nie moze byc obu rodzajow przy tym samym elemencie a $\in$ X, bo elementy zerowe nie sa jednosciami. Niech wiec

X : = {0, 1, c}

oraz niech dla operacji F : X² $\rightarrow$ X, 0 bedzie elementem zerowym, 1 - elementem jedynkowym. Zeby F bylo typu F0 i F1, to warunkiem koniecznym i dostatecznym jest, zeby F(c, c) = c, bo F(c, c) musi nalezec do odpowiednich zbiorow Y = X $\setminus$ {0} = {1, c} oraz X $\setminus$ {1} = {0, c}, a wiec do ich przeciecia {c}.

Wszystkich operacji lacznych, ktore sa jednoczesnie typu F0 i F1 jest wiec tyle, ile wyborow elementow 0 i 1, czyli 6 - w zbiorze 3-elementowym X.

* * *

Niech Asso(X) bedzie zbiorem wszystkich operacji lacznych f : X² $\rightarrow$ X. Niewiele algebry potrafimy sie w tym doszukac. Mozna probowac uzyskac negatywne wyniki, ale czy beda mialy zastosowanie? Pozytywne, czyli doszukanie sie strultury algebraicznej w Asso(X), moze ulatwic liczenie Asso(n) : = | Asoo(X)| dla n = | X|.

Nieco wiecej struktury widzimy w Absso(X), czyli w zbiorze operacji przemiennych (abelowych) i lacznych.

PROBLEM Dla jakich naturalnych n liczba

Absso(n) : = | Absso(X)|

dla | X| = n jest parzysta, a dla jakich nieparzysta?

Oczywiscie zbior stalych operacji jest zawarty w Abssso(X), a ten w Asso(X).

* * *

Przez doszukanie sie algebraicznej struktury mam na mysli znalezienie operacji w Asso(X). Zamiast traktowac X jako algebre, traktujmy Asso(X) jako pewna algebre (wciaz do zdefinowania).

Transpozycja T : Asso(X) $\rightarrow$ Asso(X) niech dana bedzie wzorem:

(T(f ))(x, y) : = f (y, x)

Teraz moglibysmy Absso(X) zdefiniowac elegancko jako zbior punktow stalych transpozycji T:

f $$\in$$ Absso(X) $$\Leftrightarrow$$ T(f )= f

dla dowolnego f $\in$ Asso(X).

Teraz jest jasnym, ze:

Asso(n) = Absso(n)mod2

(Dlatego w PROBLEMIE powyzej pytamy o parzystosc Absso(n)).

Oczywiscie T przeprowadza stale na stale.

Tak wiec mamy juz jedna 1-argumentowa operacje w Asso(X), a takze w Absso(X), mianowicie T : Asso(X) $\rightarrow$ Asso(X).

* * *

Ponizsza konstrukcje juz wykorzystywalismy przy znajdowaniu operacji lacznych w Asso(X) dla | X| = 3.

Dla ogolnosci i dla wiekszej jasnosci wyjdzmy teraz poza Asso(X) i rozpatrzmy cos jakby operacje zewnetrzne. Niech Y bedzie dowolnym zbiorem. Niech:

r : X $$\rightarrow$$ Y, j : Y $$\rightarrow$$ X

beda dowolna retrakcja i prawym odwzorowaniem odwrotnym, to znaczy niech roj = id_Y, czyli niech r(j(y) = y dla dowolnego y $\in$ Y. Otrzymujemy wtedy indukowane zanurzenie:

I : Asso(Y) $$\rightarrow$$ Asso(X)

dane wzorem:

(I(f ))(x', x") : = j(f (r(x'), r(x"))

dla dowolnego f $\in$ Asso(Y) i dowolnych x', x" $\in$ X.

Nalezy wykazac, ze I(f ) $\in$ Asso(X) dla f $\in$ Asso(Y). Jest to naprawde latwe, wiec zaoszczedzimy nudzenia.

Zanurzenie I pozwala przenosic operacje laczne z mniejszych zbiorow w wieksze zbiory. Zachowuje sie przy tym przemiennosc.

* * *

Wrocmy do samego Asso(X). Niech p : X $\rightarrow$ X bedzie dowolna permutacja (bijekcja na siebie). Wtedy

P_p : Asso(X) $$\rightarrow$$ Asso(X)

moze byc zdefiniowane jako odwzorowanie I powyzej, dla r : = p^-1 oraz j : = p; czyli tak:

(P_p(f))(x', x") : = p(f (p^-1(x'), p^-1(x"))

dla dowolnego f $\in$ Asso(X) i dowolnych x', x" $\in$ X.

UWAGA Sytuacja jest dosyc ciekawa, bo mamy pewna raczej jednorodna klase obiektow, mianowicie obiekty Asso(X), mamy dla nich jednorodnie wprowadzone operacje T oraz P_p, ale zbior operacji nie ma, jak to w Algebrze Uniwersalnej, ustalonej mocy, tym bardziej nie jest ustalonym zbiorem (np. dla wszystkich polgrup mamy jedna operacje laczna, dla monoidow mamy dwie operacje: jedna stala 1, i mnozenie; itd). Tutaj zbior operacji w Asso(X) poza T zawiera grupe symetryczna X, mianowicie S(X), zalezne od X.

Jest jasnym, ze operacje P_p musza tez byc automorfizmami obiektu Asso(X). W kazdym razie mozna je komponowac podobnie jak permutacje w S(X). Zachodzi wzor (homomorfizm):

P_qoP_p = P_qop

Faktycznie:

= q((P_p(f ))(q^-1(x), q^-1(y))

= q(p(f (p⁽ -1)(q⁽ -1)(x))p⁽ -1)(q⁽ - 1)(x)))

= (qop)(f ((qop)^-1(x)(qop)^-1(x)))

= P_qop

Widzimy ze operacje na Asso(X) same maja pewna strukture algebraiczna. Sytuacja jest podobna do przestrzeni liniowej (wektorowej), dla ktorej tez mamy wiele operacji 1-argumentowych, mianowicie mnozenie przestrzeni liniowej przez skalar. Skalary (a raczej mnozenie przez skalary) graja podobna role do operacji P_p. Jedne i drugie dopuszczaja pewna strukture, bo skalary mozna dodawac i mnozyc w sposob harmonizujacy ze struktura samej przestrzeni liniowej.

UWAGA. Podobna kompozycje, jak dla operacji P_p, mozna zdefiniowac bylo ogolniej dla operacji zewnetrznych typu I, opisanych wyzej tuz przed P_p.

Operacje P_p zachowuja przemiennosc: jezeli f $\in$ Absso(X), to takze P_p(f) $\in$ Absso(X).

* * *

Przypomnijmy jeszcze, ze w Absso(X) mamy specjalne dodatkowe operacje S_a : Absso(X) $\rightarrow$ Absso(X), dla kazdego a $\in$ X:

(S_a(f))(x, y) : = f (f (x, y), a)

dla dowlnego f $\in$ Absso(X) oraz x, y $\in$ X.

Znowu uzyskalismy regularny zbior operacji, tym razem w Absso(X), ale ktory nie ma ustalonej mocy, bo moc {S_a : a $\in$ X} zalezy od X, jest po prostu rowna | X|.

Zachodzi oczywista tozsamosc:

(S_boS_a)(f )= (S_{f(a, b)})(f )

dla dowolnych f $\in$ Absso(X), a, b $\in$ X.

* * *

Mizerna na razie ta algebra. Nie wiemy, czy mozna doszukac sie wiecej w Asso(X) lub Absso(X). Mozna, gdy X samo jest specjalne. Ale jednorodnie dla dowolnych X?

* * *

Gdy moc | X| jest potega liczby pierwszej, to X dopuszcza struktire ciala skonczonego. Wtedy wszystkie operacje w X mozna przedstawic, jako funkcje wielomianowe.

Dal | X| = 3 mozemy traktowac X jako cialo 3-elementowe X = GF(3) (cialo Galois). Od reki zauwazamy tylko nastepujace wielomiany 2 zmiennych dajace operacje laczne (rozne od oczywistych: dodawania X + Y oraz mnozenia XY):

f (X, Y) : = X²Y

oraz

g(X, Y) : = XY²

Lacznosc ich (jako funkcji w X, a nie jako symbolicznych wielomianów) wynika z tego, ze w ciele 3-elementowym X mamy t³ = t dla kazdego t $\in$ X, na przyklad:

f (f (X, Y), Z) = (X²Y)²Z = X²Y²Z = X²f (Y, Z) = f (X, f (Y, Z))

Są to nietrywialne operacje łączne i nieprzemienne!

(- 1)^{2 .} 1 $$\neq$$ 1^{2 .} (- 1)

(Jest oczywistym, że zależą istotnie od obu zmiennych, bo gdy jedna jest nierówna zeru, to wynik operacji zmienia się, gdy za drugą podstawimy raz zero, a drugi raz niezero).

Czy da się wielomianowo wyrazić łączność w elegancki sposób? Wątpliwe...

Zachęcamy do podania dalszych operacji łącznych w formie wielomianowej, nawet tych już znanych nam. Niby rozpisanie dowolnej funkcji w 3-elementowym X jako wielomianu jest czymś mechanicznym, ale mimo to może być ciekawie.

Co więcej, można raz przedstawić ciało X, jako {0, 1, 2}, a innym razem jako { -1, 0, 1}. Wtedy te same wielomiany będą mogły mieć różne interpretacje.

* * *

Uogólnimy w pewnym sensie powyższe dwa wielomiany.

Ich łączność opiera się na następujących własnościach operacji sq : X $\rightarrow$ X podnoszenia do kwadratu w ciele 3-elementowym X:

(a) sq jest idempotentem: sqosq = sq (t⁴ = t² dla dowolnego t $\in$ X);

(b) sq jest endomorfizmem semigrupy (X,*), gdzie * jest mnożeniem w ciele X:

sq(x*y) = sq(x)*sq(y)

Podobnie, w wypadku ogólnym, zachodzi:

TWIERDZENIE. Niech X będzie dowolnym zbiorem. Niech F : X² $\rightarrow$ X będzie dowolną operacją łączną. Niech f : X $\rightarrow$ X będzie endomorfizmem półgrupy (X, F) (tzn. f (F(x, y)) = F(f (x), f (y)) dla dowolnych x, y $\in$ X). Wreszcie, niech f będzie idempotentne (tzn. f (f (x)) = f (x) dla dowolnego x $\in$ X). Zdefiniujmy dwie operacje G, H : X² $\rightarrow$ X następująco:

G(xy) : = F(f (x), y)

H(xy) : = F(x, f (y))

dla dowolnych x, y $\in$ X. Wtedy G oraz H są operacjami łącznymi.

Dowód jest rutynowy, ale przyjemnie widzieć, jak wszystko w trzech kroczkach chętnie wychodzi.

Włodzimierz Holsztyński, Andrzej Komisarski, Michał Śliwka, lipiec 2003

Linki do oryginalnych dyskusji: [1], [2], [3], [4], [5]