פעילויות השבוע

In this talk, I will describe joint work with Mike Jury and Rob Martin. The focus of this talk will be on noncommutative (NC) rational function, i.e., elements of the free skew field on d generators. Suppose such a function is bounded on all finite-dimensional row contractions. In that case, it admits an inner-outer factorization as elements of the free semigroup algebra (analogous to the classical factorization in function theory on the disc). Both the inner and outer functions are NC rational, as well. I will describe the theory behind this factorization and discuss how one obtains representations of the Cuntz algebra $\mathcal{O}_d$ from inner elements of the free semigroup algebra. I will show that from NC rational inners, one obtains the finitely-correlated representations introduced by Bratelli and Jorgensen. I will finish the discussion with some open questions.

Let f,g be two Hilbert modular newforms (functions on ’n-copies’ of the upper half-plane, satisfying properties similar to usual modular forms). Consider the L-function L(s,f \times \Sym^{2}g) (it is the degree six factor of the triple product L-function L(s,f \times g \times g)). In this talk we will give a formula for the central value of this L-function and work out its rationality in some special cases of relationships between weights of f and g. We will arrive at our formula via the refined Gan-Gross-Prasad formula for SL(2) \times \tilde(SL(2)). Our results on rationality are compatible with Deligne’s conjecture on the rationality of critical values of motivic L-functions.

Identifying and characterizing the groups and fields one can define in various first order structures has had multiple applications within model theory and in other branches of mathematics. We focus here on p-adically closed fields. Let K be a p-adically closed field (for example, Q_p). We will discuss some recent results regarding interpretable groups and interpretable fields in K:

1) Let G be an interpretable group. If G is definably semisimple (i.e. G has no definable infinite normal abelian subgroups) group, then there exists a finite normal subgroup H such that G/H is definably isomorphic to a K-linear group.

2) Let F be an interpretable field. Then F is definably isomorphic to a finite extension of K.

No knowledge in model theory will be assumed, but some basic knowledge in logic will help.

נקודת המוצא שלנו היא בעיית אוסף הקופונים (THE COUPON COLLECTOR‘S PROBLEM, CCP). הבעיה הוזכרה כבר לפני למעלה מ-300 שנה ע״י DE MOIVRE. ניסוח הבעיה הוא כדלקמן: כמה שליפות של קופונים נדרשות בממוצע על מנת להשלים אוסף של $n$ סוגי קופונים, אם בכל שלב נשלף קופון בודד באופן אקראי ובהתפלגות אחידה, כאשר כל השליפות בלתי תלויות.

במאות השנים שחלפו, הוצגו שאלות רבות על בסיס הבעיה. יתר על כן, התברר שהיא מופיעה ביישומים רבים. כאן נציג חלק מתוצאות המחקר שעשינו על כמה גרסאות של הבעיה:

• נתחיל בתיאור מודל רציף לבעיית אוסף הקופונים וכן תוצאה הקשורה למודל זה. השתמשנו במודל הרציף כמה פעמים בעבודתנו.

• טבעי להריץ כמה סימולציות של תהליך ה-CCP כדי לנחש ו/או לאמת את ההתנהגות של משתנים מסויימים. לדוגמה: נסמן ב-$T_{n,m}$ את הזמן עד שהאספן יצליח לאסוף $m$ עותקים מכל אחד מ-$n$ הקופונים ונתבונן בהתפלגות והתוחלת האסימפטוטית שלו כאשר $n$ שואף לאינסוף, ו-$m$ שואף לאינסוף כפונקציה מסויימת של $n$. (בעיה זו נפתרה על ידי ארדש ורניי (1961) עבור $m$ קבוע ונשארה פתוחה עבור $m$ שואף לאינסוף.)

  במהלך המחקר, נתקלנו בקשיים בביצוע סימולציות עבור $T_{n,m}$ ככל ש־n גדל. הבעיה בסימולציה המבוצעת על ידי האלגוריתם הנאיבי והפשוט: כיוון שבכל שלב אנו שולפים קופון בודד, כל ריצה לוקחת זמן של $\Omega(n \log n)$ בהסתברות גבוהה. יתרה מכך, כדי לשמור את הנתונים לגבי מספר הפעמים שראינו כל קופון, אנו זקוקים לשמור $\Theta(n)$ מקום בזיכרון. נוסף על כך, כיוון שידוע כי התכנסות המשתנים ב-CCP היא איטית מאוד, נדרש מספר רב של איטרציות כדי לקבל אומדנים אמינים. לפיכך, עבור $n$-ים גדולים, האלגוריתם הנאיבי הופך לבלתי ישים.

  נציג שני רעיונות הסתברותיים אשר מקצרים באופן משמעותי את זמן הריצה של הסימולציה. בנוסף, נדון בכמה שאלות מעניינות הקשורות לאלגוריתמים שלנו.

• בחלק האחרון אנו נציג מקרה מיוחד שבו הקופונים אינם מתפלגים באופן אחיד — אלא, חלקם מופיעים בתדירות גבוהה יותר מאחרים. העניין בגרסה זו נובע בעיקר מהעובדה שאחת מצורות ההגנה מפני מתקפת סייבר — מה שנקרא מתקפת DDOS — ניתן למידול על ידי גרסה זו. כאן, אנו מציגים את ההתפלגות והתוחלת האסימפטוטית של הזמן עד שאוספים את כל הקופונים במודל זה.