Hitro naključno generiranje Liejevih algeber

Povzetek vsebine raziskovalnega projekta Predstavljajte si, da ste izdelovalec mehanskih ugank. Kako bi naredili čim boljšo uganko? Izvrsten zgled najdemo pri Rubikovi kocki. Ta uganka ima ogromno število možnih začetnih stanj, vselej pa obstaja zelo kratka rešitev, če jo le znamo najti. Odličnost Rubikove kocke je v tem, da izvrstno kombinira tri lastnosti: ni kompleksna, je zakomplicirana in je hitro rešljiva. Matematično lahko uganke s temi istimi lastnostmi predstavimo z abstrakcijo simetrij, to je z grupami. Najkrajšo dolžino rešitve take uganke imenujemo premer grupe. Za teoretično razumevanje računske kompleksnosti osnovnih gradnikov simetrij moramo torej razumeti premere končnih enostavnih grup. Vodilna domneva (Babaijeva domneva) v zvezi s tem predvideva, da lahko premer nekomutativne končne enostavne grupe navzgor omejimo s polinomom logaritma velikosti grupe, pri čemer je stopnja polinoma absolutna in neodvisna od same grupe. Z drugimi besedami, premeri osnovnih gradnikov simetrij naj bi bili precej majhni, oziroma še drugače, nekomutativne končne enostavne grupe so vselej hitro generirane. Razrešitev Babaijeve domneve bi teoretično zagotovila hitre rešitve vsakršnih problemov, ki vključujejo obrnljive operacije, kar bi imelo mnogo raznovrstnih aplikacij vsepočez matematike in računalništva. Babaijeva domneva je v splošnem še vedno odprta. Po težkem delu mnogih eminentnih matematikov (med njimi Fieldsovi in EMS nagrajenci) je domneva znana za družino matričnih grup PSL_n(F_q), če je le n omejene velikosti, q pa je neomejen. Pomemben odprt primer Babaijeve domeneve je družina PSL_n(F_q), kjer je n neomejen, q pa je omejene velikosti. Klasične matrične grupe so tesno povezane z njihovimi Liejevimi algebrami. S prehodom na Liejeve algebre se veliko problemov linearizira in na ta način postane lažjih. V predlaganem raziskovalnem projektu bi radi to izkoristili in raziskali linearizirano različico Babaijeve domneve za Liejevo algebro sl_n(F_p) matrik s sledjo 0 nad končnim poljem. Ocenjujemo, da je ta lineariziran problem lažji od originalne Babaijeve domneve, hkrati pa zajema del njene kompleksnosti, zato bi njegova razrešitev lahko ponudila nove ideje za originalno domnevo. Da se bomo lahko približali domnevi o hitrem generiranju sl_n(F_p), bomo razvili orodja iz verjetnosti, ki so v grupah klasična (naključno generiranje, slučajni sprehodi), a ne obstajajo za Liejeve algebre nad končnimi polji. Ta orodja so igrala ključno vlogo pri rezultatih glede Babaijeve domneve za grupe, zato predvidevamo, da bo njihov razvoj tlakoval pot proti hitremu generiranju Liejevih algeber, zelo verjetno celo v bolj poenostavljenih različicah kot v grupah. Razvoj teh orodij je glavni cilj našega predloga raziskovalnega projekta. Najprej bomo dokazali, da naključno izbrani elementi sl_n(F_p) generirajo sl_n(F_p) z visoko verjetnostjo (naključno generiranje). Za tem bomo razvili orodje slučajnega sprehoda v Liejevih algebrah in ga podrobno opisali v primeru sl_n(F_p). Nazadnje bomo uporabili slučajne sprehode za študij hitrega naključnega generiranja sl_n(F_p) v primeru neomejenega n.