فیلترِ ریشه‌های واحد و مسئلهٔ ششم المپیاد ۱۹۹۵

شمردنِ چیزهایی که با یک باقی‌مانده تعریف می‌شوند — کارِ تخصصیِ ریشه‌های واحد

در برگهٔ کاشی‌کاری دیدیم که جای‌گذاری در ریشه‌های واحد، از دلِ یک مسئلهٔ کاشی‌کاری «معادله» بیرون می‌کشد. در این برگه همان ابزار را به میدانِ اصلی‌اش می‌بریم: شمارش. مسئلهٔ ما یکی از مشهورترین‌های المپیاد جهانی است؛ و راه‌حلش الگویی است که بارها به کارتان خواهد آمد.

---

صورت مسئله

مسئله (المپیاد جهانی ریاضی ۱۹۹۵، تورنتو — مسئلهٔ ششم). فرض کنید $p$ عددی اول و فرد است. چند زیرمجموعهٔ $p$-عضوی از مجموعهٔ $\lbrace 1, 2, \dots, 2p \rbrace$ هست که مجموعِ اعضایش بر $p$ بخش‌پذیر باشد؟

جوابی که باید به آن برسیم:

$$N = 2 + \frac{\dbinom{2p}{p} - 2}{p}$$

---

پیش از حل: جواب را بخوانیم

دو زیرمجموعه همیشه در شمارش هستند: خودِ $\lbrace 1, \dots, p \rbrace$ با مجموعِ $\frac{p(p+1)}{2}$، و $\lbrace p+1, \dots, 2p \rbrace$ با مجموعِ $p^2 + \frac{p(p+1)}{2}$. چون $p$ فرد است، $\frac{p+1}{2}$ عددی صحیح است و هر دو مجموع مضربِ $p$ اند. این دو، همان «$2$»ی اولِ فرمول‌اند.

سختیِ واقعیِ مسئله جای دیگری است: باید دو قید را هم‌زمان نگه داریم — اندازهٔ زیرمجموعه دقیقاً $p$ باشد، و باقی‌ماندهٔ مجموعش صفر. هر کدام به‌تنهایی ساده است؛ با هم، نه.

و به شکلِ جواب دقت کنید؛ خودش دارد قصه‌ای تعریف می‌کند: «دو استثنا؛ و بقیهٔ زیرمجموعه‌ها در بسته‌های $p$-تایی، که از هر بسته دقیقاً یکی قبول است.» این قصه را نگه دارید — آخرِ برگه به آن برمی‌گردیم.

پیش از ادامه، حدس بزنید. برای $p = 3$ فرمول می‌گوید $N = 2 + \frac{20 - 2}{3} = 8$. می‌توانید هر هشت زیرمجموعهٔ ۳-عضویِ $\lbrace 1, \dots, 6 \rbrace$ با مجموعِ بخش‌پذیر بر ۳ را پیدا کنید؟ الگویی می‌بینید؟

پاسخ

اعضا را بر حسبِ باقی‌مانده بر ۳ دسته کنید: $\lbrace 3, 6 \rbrace$ و $\lbrace 1, 4 \rbrace$ و $\lbrace 2, 5 \rbrace$. مجموعِ سه عضو دقیقاً وقتی مضربِ ۳ است که از هر دسته یکی برداریم ($0 + 1 + 2 \equiv 0$؛ راهِ دیگرِ بخش‌پذیری، سه عضو از یک دسته بود که ممکن نیست — هیچ دسته‌ای سه عضو ندارد). پس $2 \times 2 \times 2 = 8$ زیرمجموعه؛ همان که فرمول گفت.

لمِ فیلتر

ابزارِ اصلی، یک «آشکارسازِ بخش‌پذیری» است. $\omega = e^{2\pi i / p}$ نخستین ریشهٔ $p$-اُم واحد باشد. ادعا می‌کنیم برای هر عدد صحیحِ $s$، جمعِ

$$\sum_{j=0}^{p-1} \omega^{\,j s}$$

برابر $p$ است اگر $p \mid s$، و برابرِ صفر است اگر $p \nmid s$.

چرا؟ اگر $p \mid s$، همهٔ جمله‌ها $1$ اند و جمعشان $p$. و اگر $p \nmid s$: چون $p$ اول است، ضرب در $s$ باقی‌مانده‌ها را به پیمانهٔ $p$ فقط جابه‌جا می‌کند؛ پس اعدادِ $\omega^{\,js}$ به ازای $j = 0, \dots, p-1$ چیزی نیستند جز همهٔ $p$ ریشهٔ واحد، هر یک دقیقاً یک بار — و جمعِ همهٔ ریشه‌های واحد صفر است.

اسمش را فیلتر گذاشته‌ایم چون اگر این جمع را، تقسیم‌شده بر $p$، به عددِ $s$ بدهیم، خروجی ۱ است برای مضرب‌های $p$ و ۰ برای بقیه: عبورِ آزاد برای بخش‌پذیرها، سدِ کامل برای دیگران.

---

فیلتر روی مسئله

مجموعِ اعضای زیرمجموعهٔ $A$ را $\sigma(A)$ بنویسیم. می‌خواهیم زیرمجموعه‌های $p$-عضوی با $p \mid \sigma(A)$ را بشماریم؛ پس فیلتر را روی تک‌تکشان اعمال و نتیجه‌ها را جمع می‌کنیم:

$$N = \frac{1}{p} \sum_{\lvert A\rvert = p}\; \sum_{j=0}^{p-1} \omega^{\,j\,\sigma(A)}$$

حالا جای دو جمع را عوض کنیم — اول روی $j$، بعد روی $A$:

$$p\,N = \sum_{j=0}^{p-1} S_j, \qquad S_j = \sum_{\lvert A\rvert = p} \omega^{\,j\,\sigma(A)}$$

جملهٔ $j = 0$ ساده است: همهٔ توان‌ها $1$ اند و $S_0$ فقط زیرمجموعه‌های $p$-عضوی را می‌شمارد:

$$S_0 = \binom{2p}{p}$$

همهٔ زورِ مسئله در $S_j$های دیگر است.

---

تابعِ مولدِ دومتغیره: هر دو قید در یک حاصل‌ضرب

برای این‌که «اندازه» و «مجموع» را با هم دنبال کنیم، از همان ترفندِ چندجمله‌ای‌نویسیِ مسئلهٔ تاس‌ها کمک می‌گیریم — این بار با دو متغیر: $y$ اندازه را می‌شمارد و $x$ مجموع را. حاصل‌ضربِ

$$\prod_{k=1}^{2p}\left(1 + y\,x^k\right)$$

را باز کنید: از هر پرانتز یا $1$ را برمی‌داریم (عضوِ $k$ را نمی‌گیریم) یا $y\,x^k$ را (می‌گیریم). پس بسط، جمله‌به‌جمله متناظر با زیرمجموعه‌هاست و سهمِ زیرمجموعهٔ $A$ برابرِ $y^{\lvert A\rvert} x^{\sigma(A)}$ است. حالا $x = \omega^{\,j}$ بگذارید: $S_j$ — جمعِ $\omega^{\,j\,\sigma(A)}$ روی زیرمجموعه‌های $p$-عضوی — دقیقاً ضریبِ $y^p$ است در:

$$\prod_{k=1}^{2p}\left(1 + y\,\omega^{\,j k}\right)$$

---

حاصل‌ضرب رام می‌شود

فرض کنید $j \not\equiv 0$. به توان‌های $\omega^{\,jk}$ نگاه کنید وقتی $k$ از ۱ تا $2p$ می‌رود. اول، فقط باقی‌ماندهٔ $jk$ بر $p$ مهم است. دوم، مجموعهٔ $\lbrace 1, \dots, 2p \rbrace$ هر باقی‌مانده بر $p$ را دقیقاً دو بار دارد ($k$ و $k + p$ هم‌باقی‌مانده‌اند). و سوم — نکتهٔ آشنا از لم — چون $p$ اول است و $p \nmid j$، ضرب در $j$ باقی‌مانده‌ها را فقط جابه‌جا می‌کند.

نتیجه: چندمجموعهٔ توان‌ها «هر باقی‌مانده، دو بار» است؛ یعنی:

$$\prod_{k=1}^{2p}\left(1 + y\,\omega^{\,jk}\right) = \left[\,\prod_{r=0}^{p-1}\left(1 + y\,\omega^{\,r}\right)\right]^{2}$$

همه‌چیز به یک حاصل‌ضربِ مشخص گره خورد؛ حاصل‌ضربی که ارزشش را دارد بخشی از آنِ خود داشته باشد.

---

اتحاد کلیدی

$$\prod_{r=0}^{p-1}\left(1 + y\,\omega^{\,r}\right) = 1 + y^p$$

چرا؟ اگر بسط دهیم، ضریبِ $y^t$ جمعِ حاصل‌ضرب‌های $t$-تاییِ ریشه‌هاست — همان چیزی که در روابطِ ویت $e_t$ می‌نامند و در تجزیهٔ

$$x^p - 1 = \prod_{r=0}^{p-1}\left(x - \omega^{\,r}\right) = x^p - e_1 x^{p-1} + e_2 x^{p-2} - \cdots + (-1)^p\, e_p$$

نشسته است. اما سمتِ چپ هیچ جملهٔ میانی ندارد! پس $e_1 = e_2 = \cdots = e_{p-1} = 0$؛ و از جملهٔ ثابت، $(-1)^p\, e_p = -1$، که چون $p$ فرد است $e_p = 1$ می‌دهد. در بسطِ ما فقط دو جمله زنده می‌مانند: $1$ و $y^p$.

تنها جایی که فرد بودنِ $p$ به کار آمد همین‌جا بود — و بی‌دلیل هم نیست: برای $p = 2$ حکمِ مسئله به‌راستی غلط است. از $\lbrace 1, 2, 3, 4 \rbrace$ فقط دو زیرمجموعهٔ ۲-عضوی با مجموعِ زوج داریم ($\lbrace 1, 3 \rbrace$ و $\lbrace 2, 4 \rbrace$)، اما فرمول $2 + \frac{6 - 2}{2} = 4$ می‌گفت.

---

جمعِ آخر

پس برای هر $j = 1, \dots, p-1$، جمعِ $S_j$ ضریبِ $y^p$ است در:

$$\left(1 + y^p\right)^2 = 1 + 2\,y^p + y^{2p} \qquad\Longrightarrow\qquad S_j = 2$$

و شمارش تمام است:

$$p\,N = S_0 + \sum_{j=1}^{p-1} S_j = \binom{2p}{p} + 2\,(p - 1) \qquad\Longrightarrow\qquad N = 2 + \frac{\binom{2p}{p} - 2}{p}$$

سنجش با $p = 3$: همان $N = 8$ که در حدسِ بالا با دست پیدا کردید. و یک هدیهٔ سرِ راهی: چون $N$ عددی صحیح است، $p \mid \binom{2p}{p} - 2$ — بخش‌پذیریِ کلاسیکی که این‌جا مجانی به‌دست آمد. (نسخهٔ قوی‌ترش را در تمرین ۲ می‌سازید.)

---

پشتِ صحنه: قصهٔ بسته‌های $p$-تایی

قرار بود به قصهٔ شکلِ جواب برگردیم: دو استثنا، و بقیه در بسته‌های $p$-تایی. آن قصه یک قهرمانِ ترکیبیاتی دارد: دوران.

زیرمجموعهٔ $p$-عضویِ $A$ را بردارید که هیچ‌یک از آن دو استثنا نباشد، و $A_1 = A \cap \lbrace 1, \dots, p \rbrace$. اگر $A_1$ تهی بود، $A$ ناچار همان $\lbrace p+1, \dots, 2p \rbrace$ می‌شد؛ و اگر $A_1$ همهٔ $\lbrace 1, \dots, p \rbrace$ بود، $A$ خودِ آن. پس برای $A$های غیراستثنایی، $0 < \lvert A_1 \rvert < p$.

حالا $A_1$ را درونِ $\lbrace 1, \dots, p \rbrace$ بچرخانید: به هر عضوش یک واحد اضافه کنید و $p$ را به $1$ برگردانید؛ به نیمهٔ بالایی — $A \cap \lbrace p+1, \dots, 2p \rbrace$ — دست نزنید. هر دوران، مجموع را به پیمانهٔ $p$ دقیقاً $\lvert A_1 \rvert$ واحد جلو می‌برد: هر عضو یک واحد جلو می‌رود، و عضوی هم که از $p$ به $1$ برمی‌گردد، $p - 1$ واحد عقب رفته که به همان پیمانه، یک واحد جلو است.

مدارِ $A = \lbrace 1, 2, 6 \rbrace$ برای $p = 3$: بخشِ $A_1$ روی دایره می‌چرخد و $6$ ثابت می‌ماند؛ باقی‌مانده‌های مجموع — $0, 2, 1$ — هر سه مقدار را یک بار می‌بینند و فقط حالتِ نخست قبول است.

پس $p$ دورانِ پیاپی، مجموع‌هایی می‌سازد که به پیمانهٔ $p$ برابرند با:

$$\sigma,\quad \sigma + \lvert A_1\rvert,\quad \sigma + 2\,\lvert A_1\rvert,\quad \dots,\quad \sigma + (p-1)\,\lvert A_1\rvert$$

و چون $p$ اول است و $0 < \lvert A_1\rvert < p$، این $p$ عدد همهٔ باقی‌مانده‌ها را دقیقاً یک بار می‌پوشانند. یعنی هر مدارِ دوران، دقیقاً یک قبولی دارد. (و هر مدار دقیقاً $p$ عضو دارد: اندازهٔ مدار مقسوم‌علیهی از $p$ است، و $1$ نیست — تنها زیرمجموعه‌هایی از $\lbrace 1, \dots, p \rbrace$ که زیرِ دوران ثابت می‌مانند، تهی و کامل‌اند که کنار گذاشته شدند.)

شمارش از این‌جا خودش را می‌نویسد — دو استثنا، به‌علاوهٔ یک قبولی از هر بستهٔ $p$-تایی:

$$N = 2 + \frac{\dbinom{2p}{p} - 2}{p}$$

دقیقاً همان فرمول، این بار بی‌هیچ عددِ مختلطی. پس فیلتر چه بود؟

فیلترِ ریشه‌های واحد، نسخهٔ جبریِ همین دوران است: میانگین‌گیری روی گروهِ دوران‌ها، با توان‌های $\omega$ به‌جای جابه‌جا کردنِ عضوها. دو راه‌حل، یک ایده‌اند — یکی با دست می‌چرخاند، دیگری با جبر.

---

تمرین‌ها

تمرین ۱. برای $p = 3$، مدارِ زیرمجموعهٔ $\lbrace 2, 4, 5 \rbrace$ را زیرِ همین دوران بنویسید. کدام عضوِ مدار قبول می‌شود؟

پاسخ

این‌جا $A_1 = \lbrace 2 \rbrace$ است و بخشِ ثابت $\lbrace 4, 5 \rbrace$. مدار: $\lbrace 2, 4, 5 \rbrace$ با مجموعِ $11 \equiv 2$، سپس $\lbrace 3, 4, 5 \rbrace$ با $12 \equiv 0$، سپس $\lbrace 1, 4, 5 \rbrace$ با $10 \equiv 1$. باقی‌مانده‌ها — طبقِ وعده — هر سه مقدار را یک بار گرفتند و قبولی $\lbrace 3, 4, 5 \rbrace$ است.

تمرین ۲. با اتحادِ وندرموند، $\binom{2p}{p} = \sum_{k=0}^{p} \binom{p}{k}^2$، نشان دهید که حتی $p^2$ هم $\binom{2p}{p} - 2$ را می‌شمارد.

پاسخ

برای $0 < k < p$ داریم $p \mid \binom{p}{k}$: در اتحادِ $k\binom{p}{k} = p\binom{p-1}{k-1}$ سمتِ راست مضربِ $p$ است و $k$ با $p$ نسبت به هم اول است. پس در جمعِ وندرموند، جمله‌های $k = 0$ و $k = p$ روی هم $2$ می‌دهند و هر جملهٔ میانی، مربعِ یک مضربِ $p$ است، یعنی مضربِ $p^2$:

$$\binom{2p}{p} = 2 + \sum_{k=1}^{p-1} \binom{p}{k}^2 \equiv 2 \pmod{p^2}$$

یک قدم فراتر. ثابت کنید تعدادِ زیرمجموعه‌های $\lbrace 1, \dots, n \rbrace$ — با هر اندازه، و مجموعهٔ تهی هم قبول — که مجموعشان بر $n$ بخش‌پذیر است، دستِ‌کم $\frac{2^n}{n}$ است.

پاسخ

فیلتر را این بار تک‌متغیره به کار بیندازید — قیدِ اندازه نداریم، پس $y$ لازم نیست. با $\omega = e^{2\pi i / n}$:

$$N = \frac{1}{n}\sum_{j=0}^{n-1}\; \prod_{k=1}^{n}\left(1 + \omega^{\,jk}\right)$$

جملهٔ $j = 0$ برابرِ $2^n$ است. ادعا: هیچ جمله‌ای منفی نیست — و از همین، حکم نتیجه می‌شود. برای جملهٔ $j$، بگذارید $d = \gcd(j, n)$ و $m = \frac{n}{d}$. توان‌های $\omega^{\,jk}$ این بار همهٔ ریشه‌ها نیستند: توان‌های یک ریشهٔ $m$-اُمِ اولیه مانند $\zeta$ اند که هر کدام دقیقاً $d$ بار می‌آیند؛ پس آن جمله برابر است با:

$$\left[\,\prod_{t=0}^{m-1}\left(1 + \zeta^{\,t}\right)\right]^{d}$$

و حاصل‌ضربِ داخلِ کروشه از اتحادِ $\prod_{t=0}^{m-1}\left(x - \zeta^{\,t}\right) = x^m - 1$ با $x = -1$ به‌دست می‌آید:

$$\prod_{t=0}^{m-1}\left(1 + \zeta^{\,t}\right) = 1 - (-1)^m$$

که برای $m$ فرد $2$ است و برای $m$ زوج صفر. پس هر جمله یا صفر است یا $2^d$ — هیچ‌کدام منفی نیست — و $N \ge \frac{2^n}{n}$. (این کران گاهی دقیق است: برای $n = 8$ تساوی رخ می‌دهد و $N = 32$.)

---

جمع‌بندی

• فیلترِ ریشه‌های واحد، «بخش‌پذیریِ مجموع» را به جمعِ توان‌های $\omega$ تبدیل می‌کند: میانگینِ $\omega^{\,js}$ روی $j$، برای مضرب‌های $p$ یک است و برای بقیه صفر.
• قیدِ دومِ مسئله — اندازهٔ زیرمجموعه — با متغیرِ دومِ $y$ در تابعِ مولدِ $\prod \left(1 + y\,x^k\right)$ مهار شد.
• اتحادِ $\prod_r \left(1 + y\,\omega^{\,r}\right) = 1 + y^p$ همهٔ $S_j$های ناصفر را به $2$ رساند؛ فرد بودنِ $p$ فقط همین‌جا لازم شد.
• همان جواب، روایتی ترکیبیاتی هم دارد: دورانِ $A_1$، زیرمجموعه‌های غیراستثنایی را در مدارهای $p$-تایی می‌چیند که از هر مدار دقیقاً یکی قبول است؛ فیلتر، نسخهٔ جبریِ همین دوران است.
• و مجانی: $\binom{2p}{p} \equiv 2 \pmod{p}$ — و با وندرموند، حتی به پیمانهٔ $p^2$.

اکنون باید بتوانید… برای هر شمارشِ «به پیمانهٔ $n$» فیلترِ مناسب را بنویسید؛ جای دو جمع را عوض کنید و کار را به جمله‌های $S_j$ بکشانید؛ با جابه‌جاییِ باقی‌مانده‌ها و اتحادهای حاصل‌ضربی، $S_j$ها را رام کنید؛ و هر جا شکلِ جواب «استثناها به‌علاوهٔ بسته‌ها» بود، دنبالِ دورانِ پنهانش بگردید.

قصه ادامه دارد: برای $n$ فرد، همین فیلتر جوابِ دقیقِ تمرینِ آخر را هم می‌دهد:

$$N = \frac{1}{n} \sum_{d \mid n} \varphi\left(\frac{n}{d}\right) 2^d$$

و شاید این فرمول را بشناسید: تعدادِ گردن‌بندهای دودوییِ $n$-مهره‌ای. تصادفی نیست — لمِ برنساید در نظریهٔ گروه‌ها خودِ همین فیلتر است در لباسی دیگر؛ و شاید روزی برگه‌ای از آنِ خود بگیرد.