Thursdays 16:00-17:30, Déli Épület, 3-204.
Old homepage: https://zabradi.web.elte.hu/algszam_szem.html
2022.11.13. Gyarmati Katalin:
Absztrakt and cím: A tricky method for calculating the square root of residue classes modulo p using 2x2 matrices is presented (Chapman's description of Perelta's result). Following that, we will see a proof of the fact that 1=2. Finally, I will talk about the results of my own research, specifically how to generate pseudorandom sequences from seemingly random polynomials.
2022.10.27. Kátay Tamás: Tipikusság a kompakt metrizálható Abel-csoportok körében
Absztrakt: Egy megszámlálhatóan végtelen csoportról mindig feltehetjük, hogy az alaphalmaza \mathbb{N}. Így a megsz. végt. csoportok szorzótáblái mint \mathbb{N}\times\mathbb{N}\to\mathbb{N} függvények egy \mathcal{G} teljes metrikus teret alkotnak. A \mathcal{G} térben tehát van értelme Baire-kategória értelemben tipikusságról beszélni, vagyis feltehető a kérdés, hogy mely csoporttulajdonságok tipikusak. A tipikusság a mértékelméleti "majdnem mindenütt" topológiai analógja, vagyis szemléletesen az érdekel minket, mely csoporttulajdonságok igazak majdnem minden csoportra. Tavaly ősszel már meséltem arról (is), hogy az Abel-csoportok alterében van tipikus izomorfiaosztály (létezik a tipikus megszámlálhatóan végtelen Abel-csoport), először ezt tekintjük át röviden. Ezután a kompakt metrizálható Abel-csoportokat szervezzük teljes metrikus térré. A Pontrjagin-dualitás és a diszkrét eredményeink segítségével belátjuk, hogy a kompakt metrizálható Abel-csoportok körében létezik tipikus izomorfiaosztály (létezik a tipikus kompakt metrizálható Abel-csoport). A bizonyításokat természetesen csak vázolni fogom.
2022.10.13. Chenfeng He: Isogeny-based cryptography
Absztrakt: Currently the most frequently used cryptography is based on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem, and the elliptic-curve discrete logarithm problem. All these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm. So, we should create some different schemes that can protect our secrets from quantum computer. This talk is about introducing two schemes based on isogenies of elliptic curves, i.e., SIDH and CSIDH.
2022.10.6. Pálfy Péter Pál: Egy kérdés véges csoportok feloldási halmazának méretéről
Legyen G véges csoport, g egy eleme. Az F_G(g) feloldási halmaz a csoportnak azon elemeiből áll, amelyek g-vel együtt feloldható részcsoportot generálnak. Igaz-e, hogy a feloldási halmaznak az elemszáma mindig osztható a g elem által generált ciklikus csoport normalizátorának rendjével? Doron Hai Reuven szellemes bizonyítást adott arra, hogy g centralizátorának rendjével osztható.
2022.04.21. Kocsis Anett, Matolcsi Dávid: Multiplicative complements
A pozitív egészek A és B halmazait akkor nevezzük multiplikatív komplementumoknak, ha bármely pozitív egész megkapható mint egy A-beli és egy B-beli szám szorzata. Kutatásunkban becsléseket adunk az A és B halmazok lehetséges sűrűségére.
2022.04.07. Halasi Zoltán: A Klasszikus csoportok Cayley gráfjairól szóló Babai-sejtésről
Babai egy híres sejtése szerint, ha egy G véges egyszerű csoport, minden összefüggő Cay(G,X) Cayley gráfjának átmérője legfeljebb log|G|^c, ahol c abszolút konstans. Ezen sejtés két alesetéről lesz szó: Amikor G egy klasszikus csoport, és az X generátorrendszer tartalmaz nyírást, illetve amikor X egy korlátos, véletlen részhalmaza SL(n,q)-nak.
2022.03.24. Tran Hoang Anh.: Applications of resultant of two p-adic power series
Given a prime p, and v_p(a) stands for the p-adic valuation of the element a in a finite extension K of Q_p, or more generally the field C_p which is a complete field of the algebraic closure Q_p with respect to the p-adic absolute value denoted by |ˇ|_p. Let F and G be two (p-adic) power series with no common roots. We aim to estimate the maximal value S and the minimal value s of the function ?(x)=min(v_p(F(x)),v_p(G(x))) over various domains, namely open and closed unit discs of K or C_p. To do this, we use partial resultants of two power series over certain domains defined by varied versions of the Weierstrass preparation theorem. Furthermore, the resultant of power series provides an efficient tool while studying the irreducibility and calculating the maximal value of ?.
2022.03.17. Imolay András: Ehrhart elmélet
Adott egy P politóp R^n-ben aminek az összes csúcsa egész. Jelölje f(k) azt a számot, ahány rácspont van a P politóp origóból k-szorosára nagyítottjában, ahol k pozitív egész. A témakör alaptétele azt állítja, hogy ekkor f(k) egy polinom. Az előadásom során ennek a bizonyításáról és alkalmazásairól fogok beszélni, illetve egy keveset arról, hogy én mit kutatok.
2022.03.03. Pálfy Péter Pál: Részben rendezett halmazokon értelmezett függvények konvolúciója.
Wiegandt Richárd egy 1959-es cikkében definiálta lokálisan véges részben rendezett halmazokon értelmezett függvények konvolúcióit és meghatározta, hogy ez az - általa Möbius-szorzásnak nevezett - művelet mikor lesz kommutatív és asszociatív. Azt vizsgáltam, hogy mely részben rendezett halmazokon lehet ilyen Möbius-szorzást definiálni. A témának meglepően sokféle kapcsolatát találtam, pl. kombinatorikával (Steiner hármasrendszerek, az Erdős-Rényi-T.Sós-féle "Friendship Theorem"), univerzális algebrával (teljesen szimmetrikus kvázicsoportok, parciális Abel-monoidok). Néhány érdekes részeredményt sikerült elérni (pl. meghatároztam az összes lokálisan véges moduláris hálót, amin van kommutatív és asszociatív Möbius-szorzás), de még számos irányba lehetne folytatni a kutatást.
2021.10.21. Kátay Tamás: Typical groups
Egy megszámlálhatóan végtelen csoportról mindig feltehetjük, hogy az alaphalmaza \mathbb{N}. Így a megsz. végt. csoportok szorzótáblái mint \mathbb{N}\times\mathbb{N}\to\mathbb{N} függvények egy \mathcal{G} teljes metrikus teret alkotnak. A \mathcal{G} térben tehát van értelme Baire-kategória értelemben tipikusságról beszélni, vagyis feltehető a kérdés, hogy mely csoporttulajdonságok tipikusak. A tipikusság a mértékelméleti "majdnem mindenütt" topológiai analógja, vagyis szemléletesen az érdekel minket, mely csoporttulajdonságok igazak majdnem minden csoportra. Szó lesz konkrét csoporttulajdonságok tipikusságárol és általanosabb eredményekről is. Mesélek majd a modellelméleti általánosítási lehetőségekről, és megnézzük, mi a kapcsolat a végtelen játékokkal. Az előadás alapját egy beadás előtt álló cikk képezi, a szerzők: Elekes Márton, Gehér Boglárka, Kanalas Kristóf, Kátay Tamás, Keleti Tamás.
2021.10.07. Inga Valentiner-Branth: Quantum Magic Squares, Quantum Latin Squares and their connection
Quantum Latin squares and quantum magic squares are generalizations of Latin squares and magic squares, where the entries are no longer numbers but quantum states in vector or matrix form. The famous Birkhoff-von Neumann Theorem characterizes magic squares as convex combinations of permutation matrices. We will formulate a generalization to quantum magic squares and show that it does not hold there. Quantum Latin squares can be used to construct unitary error bases which are needed for procedures in quantum information. In the end, we will bring these two notions together and see which structures they imprint on each other.
2021.03.18. Kutas Péter: Egy véges test felett definiált elliptikus görbét szuperszingulárisnak nevezünk, ha az endomorfizmus gyűrűje nem kommutatív. Két szuperszinguláris görbe közötti adott fokú izogénia keresése egy klasszikus nehéz probléma az algoritmikus számelméletben. Ennek a problémának a nehézsége adja az izogénia-alapú kriptográfia alapját, amely az egyik leggyorsabban fejlődő területe a kvantum-rezisztens kriptográfiának. Kriptográfiai szempontból fontos ennek a problémának az a változata, amikor nem csak a két görbe ismert, hanem a titkos izogéniának a hatása is egy adott torziócsoporton. Az ezzel kapcsolatos algoritmusokat tekintjük át az előadásban és néhány érdekes nyitott kérdést is megemlítünk.
2021.02.18. Kátay Tamás: Tipikus csoportok. Megszámlálhatóan végtelen csoportokat vizsgálva mindig feltehető, hogy az alaphalmaz a természetes számok halmaza. Alkalmasan választott topológiával a természetes számokon adott csoportstruktúrák lengyel teret alkotnak. Itt tehát teljesül a Baire kategória tétel, ezért van értelme a kérdésnek, hogy mely csoporttulajdonságok tipikusak (generikusak). Rövidtávú célunk, hogy minél pontosabb képet kapjunk arról, "hogy néz ki egy tipikus csoport". Hosszú távon nyitott algebrai problémákat szeretnénk támadni, potenciálisan nem konstruktív bizonyításokat adni egzisztencia kérdésekre.
2020.11.19. Szabó Kristóf: Polinomok rezultánsának becslése a $p$-adikus értékeléssel. Adott f,g relatív prím, normált, egészegyütthatós polinomok esetén milyen értékeket vehet fel lnko(f(n),g(n)) egész n esetén? Utóbbi kérdésről kiderült, hogy a válasz szorosan kötődik a rezultánshoz, mely motiválta v_p(r) becslését. Többek között az előadásomban egy új alsó korlátot adok és egy általánosabb esetre is kitérek. A bizonyítás során p-adikus értékelés néhány alapvetőbb tulajdonságával, illetve egy jól megválasztott indikátor függvénnyel a problémát átvezetjük egy jóval könnyebben kezelhető optimalizációs problémára.
2020.11.19. Bodor Bertalan: Bevezetés a CSP-k világába, Absztrakt: Egy A struktúra feletti CSP (Constraint Satisfaction Problem) a következő eldöntési probléma. Adott egy B struktúra A-val azonos szignatúrával, és a kérdés az, hogy létezik-e homomorfizmus B-ből A-ba. Ebben az előadásban arról fogok mesélni, hogy a CSP-k bonyolultsága hogyan fogható meg hatékonyan univerzális algebrai eszközökkel. Ezen eszközök használatával Bulatov és Zhuk 2017-ben bebizonyították, hogy ha A véges, akkor CSP(A) vagy P-ben van vagy NP-teljes. Továbbá azt is tudjuk, hogy melyik eset milyen algebrai feltételek mellett áll fenn. Ezen eredményen felbuzdulva felmerül a kérdés, hogy az előbbi dichotómia mikor és hogyan általánosítható végtelen struktúrákra. Az ezen irányban fennálló aktuális sejtés a következő. Legyen A egy végesen korlátos homogén struktúra, és legyen B egy elsőrendű reduktja A-nak. Ekkor CSP(B) vagy P-ben van vagy NP-teljes. Az előadásomban beszélek arról, hogy mit lehet tudni végtelen struktúrák feletti CSP-kről, és hogy milyen módszerekkel támadható az előbbi sejtés.
2020.11.12. Hoang Anh Tran A simple counterexample for the permanent-on-top conjecture,
2020.10.15. és 22.: Halasi Zoltán , Lineáris csoportok Cayley gráfjának átmérője, Babai László egy sokat vizsgált sejtése szerint egy G véges egyszerű csoport bármely Cay(G,X) Cayley gráfjának az átmérője felülről becsülhető log|G| egy polinomjával. A klasszifikációt figyelembe véve, ezen probléma legkevésbé megoldott része az, amikor G egy klasszikus csoport, melynek rangja nem korlátos. Az előadás témája ezen probléma megoldása abban a "triviális" esetben, amikor G=SL(n,p) és X tartalmaz legalább egy nyírást.
2020.05.22: Jakovac Gergely , Corner konstrualt Abel csoportokat, amiknek kulonbozo kitevos hatvanya izomorf, ezzel belatva, hogy Lovasz tetele nem terjed ki vegtelen csoportokra. A bizonyitas az alabb olvashato allitast hasznalja. Minden megszamlalhato, redukalt, torziomentes gyuru izomorf valamely megszamlalhato, torziomentes csoport endomorfizmus gyurujevel.
2020.02.20: Kanalas Kristóf, A theorem of Lovász: We prove that if A is finite and A*A is isomorphic to B*B, then A is isomorphic to B. The statement is false for infinite abelian groups.
2019.12.12: Matolcsi Dávid, Az előadás azzal foglalkozik, hogy egy $Z^d$ -beli $A$ halmazban milyen részstruktúrák jelenléte biztosítja, hogy az $A + A$ összeghalmaz az $A$ méretéhez képest szükségszerűen nagy legyen.
2019.11.28: Csahók Tímea, kvaternióalgebrák explicit izomorfizmusait szeretnénk meghatározni, ehhez szükségünk van négyváltozós kvadratikus formák megoldására. Végig F_q(t) felett dolgozunk, Kutas Petiék a ptl (és 0) karakterisztikás esetet teljesen megoldották (algoritmust adtak egy általános négyváltozós kvadratikus alak megoldására), nekünk ez egyelőre nincs meg teljesen 2 karakterisztikában, de a kvaternióalgebrák izomorfizmusait már így is ki tudjuk polinomidőben számítani.
2018.11.29: Tóthmérész Lillav, Egy gráf sandpile csoportja egy a Laplace mátrix segítségével definiált csoport, melynek rendje a gráf feszítőfáinak száma. Az irodalomban több hűséges csoporthatását is definiálták a csoportnak a feszítőfák halmazán, ezek közül az egyik a Bernardi hatás. A Bernardi hatás függ a gráf egy felületbe ágyazásától, és egy kezdőpont választásától. Baker és Wang eredménye hogy a hatás pontosan akkor független a kezdőponttól, ha a gráf síkbaágyazott. Ekkor azt is megmutatják hogy a Bernardi hatás kompatibilis a síkdualitással. Mi síkbarajzolt gráfokra adunk egy kanonikus definíciót a csoporthatásra, amiből a síkdualitással való kompatibilitás is azonnal látszik. Az eredmények Kálmán Tamással közösek.
2018. 11.17: Sokvári Olivér