הצגת המקור של הדף "פונקציית דן"

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

תהי G חבורה הנוצרת על ידי קבוצה X עם [[ייצוג של חבורה|קבוצת יחסים]] R. כל מילה w המייצגת את איבר היחידה אפשר להציג כמכפלה של צמודים <math>\ w = (p_1 r_1 p_1^{-1})\cdots (p_t r_t p_t^{-1})</math>, כאשר <math>\ r_1,\dots,r_t \in R^{\pm 1}</math> הם יחסים. המספר המינימלי של יחסים כאלה הוא ה'''שטח''' של w. פונקציית דן המתאימה ל-X מוגדרת כך ש-<math>\ f(n)</math> הוא השטח הגדול ביותר של מילים באורך n.

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

כל פונקציית דן תת-ריבועית היא ליניארית. חבורה היא [[חבורה היפרבולית|היפרבולית]] אם ורק אם יש לה פונקציית דן ליניארית. יש חבורות רבות עם פונקציית דן ריבועית: כל [[חבורה אבלית]], כל חבורה חופשית-על-ציקלית, [[חבורת תומפסון]], וגם החבורות <math>\ \operatorname{SL}_n(\mathbb{Z})</math> כאשר <math> n \geq 5</math>.

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

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

== ראו גם ==
* [[גידול של חבורה]]
* [[בעיות דן]]

[[קטגוריה:תורת החבורות הקומבינטורית]]
[[קטגוריה:תורת החבורות הגאומטרית]]