Az entrópia-hatásfüggvény-sejtés

Bevezetés

Ebben a cikkben egy érdekes sejtést fogunk bemutatni, ami a matematika számos területéről tartalmaz elemeket. A sejtés szerteágazó, ezt jól mutatja, hogy gráftulajdonságok vizsgálata során fogalmazták meg, Boole-függvényeket használ, és a Fourier-analízis eszközeivel vizsgálják. Ezek mind a matematika egy-egy igen széles területét képezik, azonban a sejtés megértéséhez nem kell szakértőnek lenni egyik területen sem.

A számítógép-tudomány megjelenésével a matematikában előtérbe került az irányzat számára fontos területek vizsgálata. Ide tartoznak a bitsorozatokon értelmezett 0-1 értékű függvények (Boole-függvények) is, amelyek például áramkörök tervezésénél játszanak fontos szerepet. Az elméleti matematika segítségével, esetünkben a Fourier-analízis eszközeit használva, igen általános kontextusban is vizsgálhatóak ezek a függvények. Az így elért eredményeket aztán eredményesen tudják alkalmazni a kutatók és a fejlesztők a gyakorlati projektek megvalósításában.

Az entrópia-hatásfüggvény-sejtés ennek a területnek egy máig bizonyítatlan elméleti állítása. A jelentősége többek között abban is rejlik, hogy alsó becslést ad a címben szereplő hatásfüggvénynek nevezett mennyiségre. Ez ugyanis szorosan kapcsolódik az ún. küszöbjelenséghez (threshold phenomena, [4]): Tegyük fel, hogy egy rendszer rendelkezik egy valós paraméterrel és valamilyen esemény valószínűsége ezen paraméter változtatásától monoton módon függ. Gyakran a paraméterskála azon része az érdekes, ahol ez a valószínűség gyorsan változik a paraméter apró módosításától is. Ezeket az intervallumokat hívjuk küszöbintervallumnak. Ilyesfajta vizsgálódások nemcsak a fent említett számítógép-tudomány területén érdekesek, hanem alkalmazzák gazdasági folyamatok elemzésében és a politikatudományban is (lásd: [6]).

Az alábbiakban bemutatunk néhány fogalmat és állítást, amelyek segítségével aztán formába önthetjük az 1995-ben Ehud Friedgut és Gil Kalai által megfogalmazott sejtést. További érdekességként bemutatunk egy eredményt a kérdéskörben arról, hogy véletlen függvényekre a sejtés állítása „nagy valószínűséggel” teljesül.

Jelölések, alapfogalmak

Előzetesen néhány szó a jelölésekről, szóhasználatról. Az alábbiakban Boole-függvényekkel fogunk dolgozni. Ezek az irodalomban több különböző formában szerepelnek, előfordulnak $\{-1,1\}^n \rightarrow \{-1,1\}$ , $\{0,1\}^n \rightarrow \{-1,1\}$ , $\{-1,1\}^n \rightarrow \{0,1\}$ és $\{0,1\}^n \rightarrow \{0,1\}$ alakban is. Mi a második alakkal foglalkozunk, így ha Boole-függvényről beszélünk, akkor a képhalmaz mindig a $\{-1,1\}$ halmaz lesz, az alaphalmaz pedig $\{0,1\}^n$ .

Néhány jelölés: Az $f\colon \{0,1\}^n \rightarrow \mathbb{R}$ várható értékén az $\mathbb{E}(f)= \frac{1}{2^n} \sum_{x \in \{0,1\}^n} f(x)$ , míg az $f$ és $g$ függvények skaláris szorzatán az $\langle f,g \rangle =\mathbb{E}(f \cdot g)$ mennyiséget értjük. Egy $S\subseteq\{1,2,\ldots,n\}$ halmaz karakterisztikus vektora az az $s \in \{0,1\}^n$ vektor, amelynek az $i$ -edik koordinátája akkor és csak akkor $1$ , ha $i\in S$ , egyébként 0.

A cikkben igyekszünk csak a sejtés megfogalmazásához szükséges definíciók és állítások kimondására szorítkozni. Néhány állítás bizonyítása azonban kellően rövid és megértésükkel jobb betekintés nyerhető a terület gondolatvilágára. Ezeket a bizonyításokat a cikk végén gyűjtöttük össze.

Ahogy már a bevezetőben is említettük, a sejtéshez vezető úton a Fourier-analízis eszközeit fogjuk használni. Ehhez először definiáljuk a területen nagyon fontos szerepet játszó ún. karaktereket a mi speciális alaphalmazunk esetén:

1. definíció. Legyen $S\subseteq\{1,2,\ldots,n\}$ és legyen ennek a halmaznak a karakterisztikus vektora. Ekkor az -hez tartozó karakter az a $\chi_S\colon \{0,1\}^n \rightarrow \{-1,1\}$ függvény lesz, amelyre:

A kitevőben $\mathbb{R}^n$ -beli vektorok szokásos skaláris szorzását használjuk.

A továbbiakban az alsó indexekben egyaránt használjuk a halmazos és a karakterisztikus vektoros jelölést is, amikor egy halmazhoz tartozó karakterről beszélünk.

Mielőtt rátérnénk a Boole-függvényekre, először általánosabb, valós számokba képező függvényeket fogunk tekinteni. Belátható, hogy a $\chi_S$ karakterek, ahol $S$ befutja az $\{1,2,\ldots,n\}$ halmazt, ortonormált bázisát adják az $f\colon \{0,1\}^n \rightarrow \mathbb{R}$ függvények alkotta vektortérnek. Azaz minden $S,T\subseteq\{1,2,\ldots,n\}$ halmaz esetén $\langle\chi_S, \chi_T\rangle=1$ , ha $S=T$ , és 0 különben, valamint minden $f\colon \{0,1\}^n \rightarrow \mathbb{R}$ függvény felírható az alábbi módon:

$\displaystyle f(x)=\sum_{r\in \{0,1\}^n}\widehat{f}(r)\chi_r(x).$

Az $\widehat{f}(r)$ értékeket az $f$ függvény $r$ -hez tartozó Fourier-együtthatóinak nevezik. Az $\widehat{f}(r)$ értékek seregét (ahogy $r$ végigfut $\{0,1\}^n$ elemein) értelmezhetjük úgy, mint egy $\widehat{f}\colon \{0,1\}^n \rightarrow \mathbb{R}$ függvényt. Ezt a függvényt az $f$ Fourier-transzformáltjának nevezik. Hasonlóan a karakterekhez, $\widehat{f}$ argumentumába időnként nem a karakterisztikus vektort, hanem a hozzá tartozó halmazt írjuk: $\widehat{f}(r)=\widehat{f}(R)$ , ha $r$ az $R\subseteq\{1,2,\ldots,n\}$ halmaz karakterisztikus vektora.

A következő néhány összefüggés rámutat a Fourier-együtthatók és az $f$ függvény kapcsolatára. Az olvasó mind a négy állítást könnyen ellenőrizheti a definíciók alapján.

1. állítás. Igazak a következő egyenlőségek:

(i) $\widehat{f}(r)=\langle f,\chi_r\rangle$ ;

(ii) $\langle f,g\rangle =\sum_{r\in \{0,1\}^n}\widehat{f}(r)\widehat{g}(r)$ (Plancherel-tétel)

(iii) $\mathbb{E}(f^2)=\langle f,f\rangle = \sum_{r\in \{0,1\}^n}\widehat{f}^2(r)$ (Parseval-egyenlőség)

(iv) Boole-függvényekre $\sum_{r\in \{0,1\}^n}\widehat{f}^2(r)=1$ .

Hatásfüggvény, entrópia

Térjünk rá most kifejezetten a Boole-függvényekre, azon belül is a hatásfüggvény definíciójára. Legyen tehát adva egy $f\colon \{0,1\}^n \rightarrow \{-1,1\}$ leképezés. Kérdés: mennyire függ a függvény értéke az $i$ -edik argumentumtól? Azaz, ha megváltoztatjuk az argumentum $i$ -edik koordinátáját, változik-e a függvény értéke? $x=(x_1,\dots, x_i,\dots, x_n)$ esetén jelölje $x^{\oplus i}:=(x_1,\dots, \bar{x}_i,\dots, x_n)$ ezt a változást, ahol a felülvonás jelenti azt, hogy az $x$ $i$ -edik koordinátáját az ellenkezőjére változtatjuk.

2. definíció. Az -edik változó hatásfüggvényének az

$\displaystyle I_i(f) = Pr_x(f(x)\neq f(x^{\oplus i}))=\frac{\vert\{x\colon f(x)\neq f(x^{\oplus i} \}\vert}{2^n}$

valószínűséget, míg teljes hatásfüggvényének az

$\displaystyle I(f)=\sum_{i=1}^n I_i(f)$

értéket nevezzük.

E definíció egy ügyes átfogalmazásával és némi számolással meg lehet mutatni, hogy az így definiált hatásfüggvény felírható pusztán a Fourier-együtthatók segítségével:

2. állítás.

$\displaystyle I_i(f)=\sum_{S \subseteq [n], i\in S}\vert\widehat{f}(S)\vert^2.$

Ebből az összefüggésből, az összegzések némi átrendezésével, a teljes hatásfüggvényre nézve a következő adódik:

3. állítás.

$\displaystyle I(f)=\sum_{S \subseteq [n]}\vert S\vert\vert\widehat{f}(S)\vert^2.$

Most térjünk át a címben is megjelenő másik fogalom, a Shannon-entrópia tárgyalására. Ez a fogalom számos más kontextusban is felbukkan a matematikában, de mindenhol hasonló jelentéssel (és definícióval) rendelkezik. A mi Boole-függvényekkel kapcsolatos vizsgálódásainkban a következőképpen vezethető be:

3. definíció. Legyen Boole-függvény. Az függvény (Shannon-féle) entrópiáján a

$\displaystyle \mathbb{H}(f):=\sum_{S \subseteq [n], \widehat{f}(S)\neq 0 } {\widehat{f}}^2(S)\log\frac{1}{\widehat{f}^2(S)}$

kifejezést értjük.

Mivel Boole-függvényeknél létezik nullától különböző Fourier-együttható, így ez az összeg nem lesz üres. Könnyen látható, hogy nemnegatív értékeket vesz fel, valamint a Jensen-egyenlőtlenség alkalmazásával (a $-\log\frac{1}{x}$ függvény konvexitását felhasználva) igazolható, hogy nem nagyobb mint $n$ .

Az entrópia és a hatásfüggvény is valamilyen formában azt fejezik ki, hogy a Fourier-együtthatók kis helyre koncentrálódnak. A két mennyiség viszonyát illetően máig nem bizonyított az a sejtés, hogy az entrópia nem lehet nagyobb, mint a hatásfüggvény:

Entrópia-hatásfüggvény-sejtés. Létezik olyan konstans, hogy minden Boole-függvényre

$\displaystyle \mathbb{H}(f) \leq c \cdot I(f).$

Néhány egyszerű függvény, amelyekre a sejtés igaz: például az AND (értéke pontosan akkor 1, ha a bemeneti vektor összes koordinátája 1), OR (értéke pontosan akkor 1, ha a bemeneti vektor legalább egy koordinátája 1), és egyéb alapvető logikai függvények. Ezek direkt kiszámolásánál az is kiderül, hogy a konstans legalább 4 kell legyen. A [5] cikkben olvasható, hogy az eddig belátott legjobb alsó korlát már $\frac{60}{13} \approx 4{,}615$ .

A sejtést először Kalai és Friedgut vetette fel monoton gráftulajdonságok vizsgálata közben [2]. A vizsgálataik során a sejtés állítását a hatásfüggvényre adott alsó becslésként használták volna fel. A problémával és annak különböző következményeivel sokan foglalkoztak. Gil Kalai 2007-es Terrence Tao blogjára írt bejegyzésében kitűnő áttekintést nyújt a kérdés jelentősségéről az addig ismert eredmények alapján [3]. Itt olvasható például, hogy Mansour sejtése is következne Kalai és Friedgut eredeti sejtéséből. Ez nagy vonalakban arról szól, hogy, amennyiben egy Boole-függvény „tömören reprezentálható”, akkor a Fourier-együtthatók „kis helyre koncentrálódnak”.

A sejtés véletlen függvényekre

Sok eredmény született Kalai 2007-es írása óta is a témában, például a sejtés bizonyítása különböző speciális függvényosztályokra ([5]). Mi egy eredményre szeretnénk még kitérni, miszerint véltelenül választott Boole-függvény esetén a sejtés „nagy valószínűséggel igaz”. Mit jelent ez pontosan?

Válasszunk egy véletlen $\{0,1\}^n \rightarrow \{-1,1\}$ Boole-függvényt úgy, hogy minden $\{0,1\}^n$ -beli ponthoz $1/2$ valószínűséggel rendelünk $-1$ -et vagy $1$ -et. Ekkor minden $\{0,1\}^n \rightarrow \{-1,1\}$ függvényt $\frac{1}{2^{2^n}}$ valószínűséggel kapunk. Legyenek $I_r$ és $H_r$ valószínűségi változók, amelyek az így választott függvény teljes hatásfüggvényét és entrópiáját jelölik. Az állítás gyakorlatilag azt mondja ki, hogy amennyiben a sejtésben $c=3$ -at választunk konstansnak, akkor az előbbi módon véletlenül választott Boole-függvény nagyon kis valószínűséggel lehet egyáltalán ellenpélda. Vagyis, ha léteznek is függvények, amelyek cáfolják a sejtést $c=3$ -ra, akkor azok csak nagyon ( $n$ -ben exponenciálisan) kis hányadát teszik ki az össze Boole-függvénynek. Formálisan az állítás:

$\displaystyle Pr(H_r > 3 I_r) \leq \frac{36}{n \cdot 2^{n+1}}.$

Tehát egyenletesen véletlenül választott függvényre $c=3$ konstanssal legalább $1-\frac{36}{n \cdot 2^{n+1}}$ valószínűséggel teljesül az entrópia-hatásfüggvény-sejtés.

Ennek az állításnak a bizonyítása már bőven meghaladja ennek az írásnak a terjedelmi korlátait. Azonban részben azért is emeltük ki ezt az eredményt, mert bár a bizonyításban néhol megjelennek hosszabb számítások, az eddig bevezetett fogalmakon kívül nem igazán igényel magasabb szintű matematikai tudást, csupán elemi valószínűségszámítási ismereteken alapul. Akit érdekel a gondolatmenet, és nem riad vissza néhány hosszabb, de helyenként kifejezetten ötletes számolás végigolvasásától, az a levezetését teljes egészében elolvashatja [1]-ben.

Bizonyítások

Az 1. állítás bizonyítása.

(i) $\langle f,\chi_r\rangle =\langle \sum_t\widehat{f}(t)\chi_t,\chi_r\rangle=\sum_t\widehat{f}(t)\langle\chi_t,\chi_r\rangle=\widehat{f}(r)$ .

(ii) $\langle f,g\rangle=\langle \sum_r\widehat{f}(r)\chi_r,\sum_s\widehat{g}(s)\chi_... ...)\widehat{g}(s)\langle\chi_r,\chi_s\rangle=\sum_{r}\widehat{f}(r)\widehat{g}(r)$ .

(iii) az (ii) speciális esete, amikor $f=g$ .

(iv) A Boole-függvények értékei $-1,1$ ezért (iii)-at felhasználva kapjuk az állítást. $\qedsymbol$

A 2. állítás bizonyítása. Vegyük észre, hogy a definíció egyszerű következménye, hogy $I_i(f)= \mathbb{E}_x\left[\frac{(f(x)- f(x^{\oplus i}))^2}{4}\right]$ .

Valóban, $f(x)- f(x^{\oplus i})$ értéke vagy 0, nincs változás, vagy $\pm 2$ . Tehát $\frac{(f(x)- f(x^{\oplus i}))^2}{4}$ értéke pontosan akkor 1, ha $f(x)$ értéke változik az $i$ -edik koordináta előjelváltásával, és akkor 0, ha nem. Vagyis ez a mennyiség pont a nekünk szükséges esemény indikátorfüggvénye, melynek várható értéke épp a valószínűség.

Most igazoljuk, hogy $I_i(f)=\sum_{S\colon i\in S}\vert\widehat{f}(S)\vert^2$ .

Tekintsük az $f(x)- f(x^{\oplus i})$ különbséget; $f(x^{\oplus i})$ jelentése, amikor az $i$ -edik koordinátát az ellenkezőjére változtatjuk. Ha vesszük $f(x)$ és $f(x^{\oplus i})$ Fourier-előállítását, azon $S$ -ekhez tartozó tagok, amelyekben az $i$ nem szerepel mind a két függvényben azonosak, tehát a különbségben kiesnek. Ha az $i\in S$ akkor $\chi_S(x^{\oplus i}) = -\chi_S(x)$ , tehát a különbségben ennek a tagnak a kétszerese szerepel. (Nem nehéz, de érdemes ellenőrizni, hogy ez a karakter mindkét formájára valóban igaz a megfelelően adott Boole-függvény esetén.) Röviden azt kaptuk, hogy

$\displaystyle f(x)- f(x^{\oplus i})=2\sum_{i\in S}\widehat{f}(S)\chi_S(x).$

Végül

$\displaystyle \mathbb{E}_x\left[\frac{(f(x)- f(x^{\oplus i}))^2}{4}\right]=\lef... ...n T}\widehat{f}(T)\chi_T\right\rangle=\sum_{i\in S}\vert\widehat{f}(S)\vert^2.$

Az utolsó egyenlőségnél a Parseval-egyenlőséget és a karakterek ortonormáltságát használtuk. $\qedsymbol$

A 3. állítás bizonyítása.

$I(f)=\sum_i I_i(f)=\sum_i\sum_{S\colon i\in S}\vert\widehat{f}(S)\vert^2=\sum_S\sum_{i}\vert\widehat{f}(S)\vert^2=\sum_{S}\vert S\vert\vert\widehat{f}(S)\vert^2$ . $\qedsymbol$

Irodalomjegyzék

[1] Bireswar Das, Manjish Pal, and Vijay Visavaliya. The entropy influence conjecture revisited. arXiv preprint arXiv:1110.4301, 2011.

[2] Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993–3002, 1996.

[3] Gil Kalai. (Gil Kalai) The entropy/influence conjecture, 2007 (accessed February 15, 2020). https://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/.

[4] Gil Kalai and Shmuel Safra. Perspectives from mathematics, computer science, and economics. Computational complexity and statistical physics, page 25, 2006.

[5] Ryan O’Donnell, John Wright, and Yuan Zhou. The Fourier entropy-influence conjecture for certain classes of Boolean functions. In International Colloquium on Automata, Languages, and Programming, pages 330–341. Springer, 2011.

[6] Wikipedia. Condorcet's jury theorem -- Wikipedia, the free encyclopedia. http://en.wikipedia.org/w/index.php?title=Condorcet's%20jury%20theorem&oldid=1026667834, 2021. [Online; accessed 04-August-2021].

A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg (EFOP-3.6.3-VEKOP-16-2017-00002).

Bakos Bence MSc hallgató, ELTE Matematikai Intézet

Pálfy Máté doktorandusz, ELTE Matematikai Intézet

Információk

Főmenü