Activities This Week

A long-standing open problem, known as Hadwiger’s covering problem, asks what is the smallest natural number N(n) such that every convex body in $R^n$ can be covered by a union of the interiors of at most N(n) of its translates. Despite continuous efforts, the best general upper bound known for this number remains as it was more than sixty years ago, of the order of $\binom{2n}{n}n\ln n$.

In this talk, I will discuss some history of this problem and present a new result in which we improve this bound by a sub-exponential factor. Our approach combines ideas from previous work, with tools from Asymptotic Geometric Analysis. Namely, we make use of measure concentration in the form of thin-shell estimates for isotropic log-concave measures.

If time permits we shall discuss some other methods and results concerning this problem and its relatives.

Joint work with H. Huang, B. Vritsiou, and T. Tkocz

In the Steiner Point Removal (SPR) problem, we are given a weighted graph $G=(V,E)$ and a set of terminals $K\subset V$ of size $k$. The objective is to find a minor $M$ of $G$ with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer and Nguyen [SICOMP2015] devised a ball-growing algorithm with exponential distributions to show that the distortion is at most $O(\log^5 k)$. Cheung [SODA2018] improved the analysis of the same algorithm, bounding the distortion by $O(\log^2 k)$. We devise a novel and simpler algorithm (called the Relaxed Voronoi algorithm) which incurs distortion $O(\log k)$. This algorithm can be implemented in almost linear time ($O(|E|\log |V|)$).

הפונקציות אותן פגשתם ברב הקורסים באנליזה הן פונקציות של כמה וכמה משתנים שמקבלים ערכים מספריים; דהיינו המשתנים של הפונקציה הם קומוטטיביים (מתחלפים). גם חיות קצת יותר אקזוטיות, אם פגשתם כאלה, אינן שונות בתכלית: פונקציה על מרחב הילברט או מרחב בנך היא פונקציה של אינסוף משתנים קומוטטיביים, ופונקציה על יריעה $N$ מימדית היא באופן מקומי פונקציה של $N$ משתנים קומוטטיביים.

דוגמא שכולנו מכירים מהגן (או לפחות משנה א) למשתנים לא קומוטטיביים היא מטריצות. מסתבר שלמרות שמטריצות $2\times 2$ אינן מתחלפות, הן מקיימות איזשהם יחסים אלגבריים, והוא הדין לגבי מטריצות מכל סדר קבוע. אבל לא קשה לראות כי אין אף יחס אלגברי שמתקיים למטריצות מכל הסדרים. הדבר מוביל אותנו (או ביתר דיוק, הוביל את ג’וזף ל. טיילור בעבודה פורצת דרכים בראשית שנות ה-70 של המאה הקודמת) להגדיר פונקציה של $N$ משתנים לא קומוטטיביים חפשיים להיות פונקציה שהתחום שלה הוא קבוצה באיחוד הזר של $N$-יות של מטריצות ריבועיות מסדר $M$, כאשר $M$ רץ מ-1 עד אינסוף. כמובן כדי להיות פונקציה לא קומוטטיבית אמיתית - ולא סתם אספסוף של פונקציות שונות לכל סדר $M$ - על הפונקציה שלנו לקיים איזשהם יחסי תיאום כאשר אנו משנים את סדר המטריצות.

מסתבר שליחסי התיאום הפשוטים האלה יש השלכות מרחיקות לכת. פונקציות לא קומוטטיביות דומות לפונקציות אנליטיות (או לפתרונות של משוואות דיפרנציאליות חלקיות אליפטיות, אם יצא לכם להכיר) בכך שיש להן תכונות רגולריות מדהימות: פונקציה לא קומוטטיבית שהיא חסומה באפן מקומי הינה אנליטית וניתנת לפיתוח לטור חזקות (לא קומוטטיבי) שאנו קוראים לו טור טיילור–טיילור, על שם ברוק טיילור מאינפי 1 וג’וזף ל. טיילור שהוזכר למעלה. הסיבה לניסים ונפלאות אלה, ורבים אחרים, היא כי ניתן לפתח חשבון דיפרנציאלי עבור פונקציות לא קומוטטיביות.

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

Automorphic L-functions, initially defined on some right half plane, are conjectured to be have meromorphic continuation to the whole complex plane. An effective method to prove this in some cases is by using an integral representation. Since the 1960’s, many such integrals were discovered, some of them representing the same L-function, but seemingly unrelated. Using recent discoveries of D.Ginzburg and D. Soudry, I will explain the relation between different integrals representing the same L-function.