פונקציית דן

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

תהי G חבורה הנוצרת על ידי קבוצה X עם קבוצת יחסים R. כל מילה w המייצגת את איבר היחידה אפשר להציג כמכפלה של צמודים $\ w=(p_{1}r_{1}p_{1}^{-1})\cdots (p_{t}r_{t}p_{t}^{-1})$, כאשר $\ r_{1},\dots ,r_{t}\in R^{\pm 1}$ הם יחסים. המספר המינימלי של יחסים כאלה הוא השטח של w. פונקציית דן המתאימה ל-X מוגדרת כך ש-$\ f(n)$ הוא השטח הגדול ביותר של מילים באורך n.

מגדירים יחס שקילות על פונקציות, כך ש-$\ f\equiv g$ אם קיים קבוע c כך ש-$\ f(n)\leq c\cdot g(cn)+cn$, וכן להפך. כל שתי פונקציות דן של אותה חבורה שקולות זו לזו. בפרט, אם פונקציית דן שקולה לחזקה $\ n^{\alpha }$, אז המעלה $\ \alpha$ מוגדרת היטב. יש חבורות מוצגות סופית עם פונקציות דן כאלה עבור קבוצה צפופה של ערכים $2\leq \alpha$. פונקציית דן עשויה להיות אקספוננציאלית, אפילו עבור חבורה מטא-אבלית.

כל פונקציית דן תת-ריבועית היא ליניארית. חבורה היא היפרבולית אם ורק אם יש לה פונקציית דן ליניארית. יש חבורות רבות עם פונקציית דן ריבועית: כל חבורה אבלית, כל חבורה חופשית-על-ציקלית, חבורת תומפסון, וגם החבורות $\ \operatorname {SL} _{n}(\mathbb {Z} )$ כאשר $n\geq 5$.

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

פונקציית דן של תת-חבורה עשויה לגדול מהר יותר מזו של החבורה עצמה.

ראו גם

• גידול של חבורה
• בעיות דן