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 \(s\) legyen ennek a halmaznak a karakterisztikus vektora. Ekkor az \(S\)-hez tartozó karakter az a \(\chi_S\colon \{0,1\}^n \rightarrow \{-1,1\}\) függvény lesz, amelyre: \[\displaystyle \chi_S(x):=(-1)^{\langle s,x \rangle }.\]
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 \(i\)-edik változó hatásfüggvényének az \[\displaystyle I_i(f) = Pr_x(f(x)\neq f(x^{\oplus i}))=\frac{|\{x\colon f(x)\neq f(x^{\oplus i} \}|}{2^n}\] valószínűséget, míg \(f\) 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}|\widehat{f}(S)|^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]}|S||\widehat{f}(S)|^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 \(f\) Boole-függvény. Az \(f\) 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 \(c\) konstans, hogy minden \(f\) 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_s\rangle =\sum_{r,s}\widehat{f}(r)\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.\(\Box\)
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]=\left\langle \frac{f(x)- f(x^{\oplus i})}{2},\frac{f(x)- f(x^{\oplus i})}{2}\right\rangle=\left\langle \sum_{i\in S}\widehat{f}(S)\chi_S,\sum_{i\in T}\widehat{f}(T)\chi_T\right\rangle=\sum_{i\in S}|\widehat{f}(S)|^2.\]
Az utolsó egyenlőségnél a Parseval-egyenlőséget és a karakterek ortonormáltságát használtuk.\(\Box\)
A 3. állítás bizonyítása. \[\displaystyle 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.\tag*{\(\Box\)}\]
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
