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

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

---

مسئله

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

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

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

پاسخ

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

---

از یک حالتِ کوچک تا یک حدس

هشت‌تا از بیست‌تا. اگر باقی‌ماندهٔ مجموع میانِ سه مقدارِ ۰ و ۱ و ۲ عادلانه پخش می‌شد، سهمِ هر کدام $\frac{20}{3}$ می‌شد — که اصلاً عددِ صحیح نیست. پس تقسیمِ کاملاً عادلانه از اولش ناممکن بود و جایی باید می‌شکست — و به سودِ قبولی‌ها شکست: ۸ از سهمِ عادلانه بیشتر است. این اضافه از کجا آمد؟

دو زیرمجموعه در این میان مشکوک‌اند، چون بی‌هیچ زحمتی قبول‌اند: خودِ $\lbrace 1, 2, 3 \rbrace$ با مجموعِ ۶، و $\lbrace 4, 5, 6 \rbrace$ با مجموعِ ۱۵. این دو را کنار بگذارید و دوباره بشمارید: از ۱۸ زیرمجموعهٔ باقی‌مانده، $8 - 2 = 6$ تا قبول‌اند — دقیقاً $\frac{18}{3}$.

اما «عادلانه» ادعایی دربارهٔ هر سه باقی‌مانده است، نه فقط صفر؛ پس هر سه را بشماریم:

باقی‌ماندهٔ مجموع بر ۳	۰	۱	۲
میانِ هر ۲۰ زیرمجموعه	۸	۶	۶
بی‌آن دو استثنا	۶	۶	۶

حالا تصویر کامل است، و شکلی دارد که ارزشِ به‌خاطر سپردن دارد: توزیع کاملاً یکنواخت است، به‌علاوهٔ دو تا اضافه که هر دو روی باقی‌ماندهٔ صفر نشسته‌اند. در پایانِ برگه دقیقاً همین را برای هر $p$ ثابت می‌کنیم.

آن دو استثنا مخصوصِ $p = 3$ نیستند؛ برای هر $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$ اند.

حالا جدولِ $p = 3$ را به زبانِ همهٔ $p$ها بازگو کنیم. حاصل یک قصه است — فعلاً حدسی، نه اثبات‌شده: «دو استثنا؛ و بقیهٔ زیرمجموعه‌ها در بسته‌های $p$-تایی، که از هر بسته دقیقاً یکی قبول است.» و اگر این قصه راست باشد، جواب دیگر جای انتخاب ندارد: $\binom{2p}{p} - 2$ زیرمجموعهٔ غیراستثنایی در $\frac{1}{p}\left[\binom{2p}{p} - 2\right]$ بسته می‌نشینند و از هر بسته یکی قبول است؛ به‌علاوهٔ خودِ دو استثنا:

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

برای $p = 5$ این عدد $2 + \frac{252 - 2}{5} = 52$ است و برای $p = 7$ برابرِ $2 + \frac{3432 - 2}{7} = 492$؛ شمارشِ مستقیم — با حوصله یا با چند خط برنامه — همین دو عدد را می‌دهد. حدس، جانِ سالم به در برد.

اما حدس، حدس است — و حدسِ ما فقط یک عدد نیست، یک ساختار است. دو پرسش باز مانده: چرا بقیه در بسته‌های عادلانه می‌افتند، و چرا فقط همین دو استثنا؟ این قصه را نگه دارید — آخرِ برگه به آن برمی‌گردیم و بسته‌ها را با چشم می‌بینیم.

---

فیلترِ ریشه‌های واحد

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

$\omega$ را نخستین ریشهٔ $p$-اُم واحد پس از ۱ بگیرید — عددی با طول ۱ و زاویهٔ $\frac{2\pi}{p}$ — که ریشه‌های $p$-اُمِ واحد توان‌های همین‌اند: $1, \omega, \omega^2, \dots, \omega^{\,p-1}$. حالا برای هر عددِ صحیحِ $s$ تعریف کنید:

$$F_p(s) = \frac{1}{p}\left[\,1^{\,s} + \left(\omega\right)^{s} + \left(\omega^{2}\right)^{s} + \left(\omega^{3}\right)^{s} + \cdots + \left(\omega^{\,p-1}\right)^{s}\,\right]$$

و چون $\left(\omega^{\,j}\right)^{s} = \omega^{\,js}$، همین را کوتاه‌تر هم می‌شود نوشت:

$$F_p(s) = \frac{1}{p} \sum_{j=0}^{p-1} \omega^{\,j s}$$

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

لم.

$$F_p(s) = \begin{cases} 1, & p \mid s \\ 0, & p \nmid s \end{cases}$$

پیش از اثبات، هر دو حالت را برای $p = 5$ ببینید — هر پیکان یکی از پنج جملهٔ جمع است:

وقتی $5 \mid s$، هر پنج پیکانِ $\omega^{\,js}$ روی $1$ افتاده‌اند: پنج پیکانِ هم‌جهت، میانگین $1$. وقتی $5 \nmid s$، پیکان‌ها رأس‌های پنج‌ضلعی را فقط جابه‌جا کرده‌اند: جمع صفر، میانگین صفر.

وقتی $s$ مضربِ $p$ است، همهٔ صداها هم‌فازند؛ وگرنه یک دورِ کامل می‌سازند و یکدیگر را خاموش می‌کنند.

حالا اثبات. به جمله‌های جمع نگاه کنید: $\left(\omega^{\,s}\right)^{0}$، $\left(\omega^{\,s}\right)^{1}$، $\left(\omega^{\,s}\right)^{2}$ و همین‌طور تا آخر. یعنی جمعِ ما یک تصاعدِ هندسی است با قدرنسبتِ $\omega^{\,s}$.

و برای تصاعدِ هندسی رابطهٔ آشنایی داریم — به شرطی که قدرنسبت ۱ نباشد:

$$1 + q + q^2 + \cdots + q^{\,n-1} = \frac{q^{\,n} - 1}{q - 1} \qquad (q \neq 1)$$

چرا این رابطه درست است؟

جمع را $S$ بنامید و در $q$ ضربش کنید:

$$S = 1 + q + q^2 + \cdots + q^{\,n-1}, \qquad q\,S = q + q^2 + \cdots + q^{\,n-1} + q^{\,n}$$

دو جمع تقریباً یکی‌اند: همهٔ جمله‌های میانی در هر دو هستند. پس وقتی یکی را از دیگری کم کنیم، همه‌شان حذف می‌شوند و فقط دو سرِ ماجرا می‌مانند — $q^{\,n}$ از یک طرف و $1$ از طرفِ دیگر:

$$q\,S - S = q^{\,n} - 1 \qquad\Longrightarrow\qquad S\,(q - 1) = q^{\,n} - 1$$

حالا اگر $q \neq 1$ باشد، $q - 1$ ناصفر است و می‌توانیم بر آن تقسیم کنیم. (و اگر $q = 1$ باشد این تقسیم مجاز نیست — به همین دلیل است که آن حالت باید جداگانه بررسی شود.)

پس اول فرض کنیم قدرنسبت ۱ نیست، یعنی $\omega^{\,s} \neq 1$. آن‌گاه رابطه را با $q = \omega^{\,s}$ و $n = p$ به کار می‌بریم:

$$\sum_{j=0}^{p-1} \left(\omega^{\,s}\right)^{j} = \frac{\left(\omega^{\,s}\right)^{p} - 1}{\omega^{\,s} - 1} = \frac{\left(\omega^{\,p}\right)^{s} - 1}{\omega^{\,s} - 1} = \frac{1 - 1}{\omega^{\,s} - 1} = 0$$

صورت صفر شد چون $\omega^{\,p} = 1$، و مخرج ناصفر است چون فرض کردیم $\omega^{\,s} \neq 1$ — پس تقسیم مجاز بود و $F_p(s) = 0$. جالب این‌جاست که صورتِ کسر همیشه صفر است؛ همهٔ کار را همان یک شرطِ $\omega^{\,s} \neq 1$ کرد.

پس تنها پرسشِ باقی‌مانده این است: قدرنسبت کِی برابرِ ۱ می‌شود؟ ضرب در $\omega$ یعنی چرخشِ $\frac{2\pi}{p}$، پس $\omega^{\,s}$ عددی است با طول ۱ و زاویهٔ $\frac{2\pi s}{p}$. و این عدد وقتی ۱ می‌شود که زاویه‌اش شمارِ درستی از دورِ کامل باشد، یعنی وقتی $\frac{s}{p}$ عددی صحیح باشد — و این دقیقاً یعنی $p \mid s$.

در این حالت هم حساب از هرچه ساده‌تر است: قدرنسبت ۱ است، پس هر $p$ جملهٔ جمع برابرِ ۱ اند، جمع $p$ می‌شود و پس از تقسیم بر $p$، $F_p(s) = 1$.

و اسمِ «فیلتر» از همین‌جاست: $F_p$ به مضرب‌های $p$ اجازهٔ عبور می‌دهد و بقیه را کاملاً سد می‌کند. هر چیزی را در $F_p(s)$ ضرب کنید، اگر $p \nmid s$ باشد ناپدید می‌شود و اگر $p \mid s$ باشد دست‌نخورده رد می‌شود.

---

جابه‌جاییِ باقی‌مانده‌ها

یک نکتهٔ ساده و قابلِ توجه دربارهٔ باقی‌مانده‌ها به پیمانهٔ $p$، که در این برگه چند بار به کارمان می‌آید.

دستگاهِ کاملِ مانده‌ها. به $p$ عددِ صحیح یک «دستگاهِ کاملِ مانده‌ها» به پیمانهٔ $p$ می‌گوییم — یعنی فهرستی که هر باقی‌مانده را دقیقاً یک بار دارد: باقی‌مانده‌هایشان بر $p$ همهٔ مقدارهای $0$ تا $p-1$ را دقیقاً یک بار می‌پوشانند. آشکارترین نمونه خودِ $\lbrace 0, 1, 2, \dots, p-1 \rbrace$ است.

حالا همین دستگاه را بردارید و همه‌اش را در عددِ $s$ ضرب کنید. اعداد بزرگ می‌شوند و ترتیبِ باقی‌مانده‌هایشان به‌هم می‌ریزد — اما دستگاه، دستگاه می‌ماند:

گزاره. اگر $p$ اول باشد و $p \nmid s$، آن‌گاه $\lbrace 0,\, s,\, 2s,\, \dots,\, (p-1)\,s \rbrace$ هم یک دستگاهِ کاملِ مانده‌ها به پیمانهٔ $p$ است.

نمونه‌ای با $p = 5$ و $s = 3$:

$j$	۰	۱	۲	۳	۴
$js$	۰	۳	۶	۹	۱۲
$js \bmod 5$	۰	۳	۱	۴	۲

سطرِ آخر همان پنج باقی‌ماندهٔ $0, 1, 2, 3, 4$ است، فقط جابه‌جا شده.

اثبات. $p$ عدد داریم، و $p$ باقی‌مانده بیشتر در دسترس نیست؛ پس کافی است نشان دهیم هیچ دو تایی از این باقی‌مانده‌ها با هم برابر نمی‌شوند — آن‌وقت ناچار همهٔ جاها پر شده‌اند. فرض کنید برای دو اندیسِ $j_1$ و $j_2$ داشته باشیم $j_1 s \equiv j_2 s \pmod p$؛ آن‌گاه $(j_1 - j_2)\,s$ بر $p$ بخش‌پذیر است. اما $p$ اول است و $s$ بر آن بخش‌پذیر نیست، پس چاره‌ای نمی‌ماند جز این‌که $j_1 - j_2$ بر $p$ بخش‌پذیر باشد — و چون هر دو بینِ $0$ و $p-1$ اند، تنها راهش $j_1 = j_2$ است. $\blacksquare$

و شهودِ ماجرا در یک جمله:

جابه‌جاییِ باقی‌مانده‌ها. ضرب در $s$ باقی‌مانده‌ها را از بین نمی‌برد؛ فقط جایشان را با هم عوض می‌کند.

شرطِ دقیق‌تر — و چطور همین نکته، لمِ فیلتر را دوباره ثابت می‌کند

شرطِ دقیق چیست؟ در این استدلال آنچه واقعاً کار کرد این بود که $s$ و پیمانه نسبت به هم اول باشند، یعنی $\gcd(s, p) = 1$. اول بودنِ $p$ فقط کارِ راحتی می‌کند: وقتی $p$ اول است، همین که $p \nmid s$ باشد کافی است تا $\gcd(s, p) = 1$ برقرار شود. اگر پیمانه اول نباشد این دو شرط از هم جدا می‌شوند — به پیمانهٔ ۶ و با $s = 2$ که $\gcd(2, 6) = 2$ است، باقی‌مانده‌های $js$ می‌شوند $0, 2, 4, 0, 2, 4$: تکرار، نه جابه‌جایی. اما همان پیمانهٔ ۶ با $s = 5$ که نسبت به ۶ اول است، باقی‌مانده‌های $0, 5, 4, 3, 2, 1$ را می‌دهد — جابه‌جاییِ تمام‌عیار. (همین نکته راهِ تعمیم را باز می‌کند؛ در تمرین ۶ به کارش می‌گیریم.)

و همین نکته، حالتِ نخستِ لم را جورِ دیگری هم نشان می‌دهد — بدون محاسبه‌ی مجموعِ یک تصاعدِ هندسی. دو چیز را کنار هم بگذارید. نخست: چون $\omega^{\,p} = 1$، هر بار که توانِ $\omega$ به اندازهٔ $p$ جلو برود به همان نقطهٔ قبلی برمی‌گردیم، پس $\omega^{\,js}$ فقط به باقی‌ماندهٔ $js$ بر $p$ بستگی دارد (مثلاً برای $p = 5$ داریم $\omega^{9} = \omega^{5}\,\omega^{4} = \omega^{4}$). دوم: همین باقی‌مانده‌ها، طبقِ گزارهٔ بالا، همهٔ مقدارهای $0$ تا $p-1$ را دقیقاً یک بار می‌سازند.

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

---

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

مجموعِ اعضای زیرمجموعهٔ $A$ را $\sigma(A)$ بنویسیم. شمارشِ ما، به زبانِ فیلتر، یک جملهٔ کوتاه است: هر زیرمجموعهٔ $p$-عضوی را از فیلتر رد کنید و خروجی‌ها را جمع بزنید. قبول‌شده‌ها ۱ می‌آورند و بقیه ۰:

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

این جمعِ دوگانه، جمعِ متناهی از عددهاست؛ پس می‌توانیم ترتیبِ جمع‌زدن را عوض کنیم — اول روی $j$، بعد روی $A$. ضریبِ $\frac{1}{p}$ را هم برای این‌که سرِ راه نباشد به سمتِ چپ می‌بریم:

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

چرا این جابه‌جایی سود دارد؟ چون حالا جمعِ درونی — که $j$ در آن ثابت است — خودش یک عددِ مشخص است. اسمش را می‌گذاریم $S_j$:

$$S_j = \sum_{\lvert A\rvert = p} \omega^{\,j\,\sigma(A)}$$

و شمارشِ ما به این شکلِ ساده درمی‌آید:

$$p\,N = \sum_{j=0}^{p-1} S_j = S_0 + S_1 + \cdots + S_{p-1}$$

یعنی مسئله تبدیل شد به حسابِ $p$ عددِ $S_0$ تا $S_{p-1}$. جملهٔ $j = 0$ ساده است: هر جملهٔ جمع برابرِ $\omega^{\,0} = 1$ است، و تعدادِ جمله‌ها همان تعدادِ زیرمجموعه‌های $p$-عضوی است. پس $S_0$ جمعِ $\binom{2p}{p}$ عددِ $1$ می‌شود:

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

محاسبهٔ بقیهٔ $S_j$ها کمی دشوارتر است؛ سراغِ همان‌ها می‌رویم.

---

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

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

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

را قدم‌به‌قدم باز کنیم.

یک پرانتز برای هر عضو. به ازای هر عضوِ $k$ از $\lbrace 1, \dots, 2p \rbrace$ یک پرانتز گذاشته‌ایم، و آن پرانتز دقیقاً دو سرنوشتِ ممکنِ آن عضو را در خود دارد: یا $k$ را در زیرمجموعه نمی‌گیریم — که با $1$ نشان داده می‌شود — یا می‌گیریم، که با $y\,x^{k}$ نشان داده می‌شود.

باز کردنِ حاصل‌ضرب یعنی انتخاب کردن. وقتی این $2p$ پرانتز را در هم ضرب می‌کنیم، هر جملهٔ بسط از این به دست می‌آید که از هر پرانتز دقیقاً یکی از دو گزینه‌اش را برداریم و همه را در هم ضرب کنیم. پس جمله‌های بسط دقیقاً به تعدادِ راه‌های «گرفتن یا نگرفتن» اند — یعنی به تعدادِ زیرمجموعه‌های $\lbrace 1, \dots, 2p \rbrace$، و هر جمله سهمِ یک زیرمجموعه است.

سهمِ زیرمجموعهٔ $A$ چیست؟ از پرانتزهای عضوهای $A$ گزینهٔ $y\,x^{k}$ را برمی‌داریم و از بقیه $1$ را؛ ضربشان می‌شود:

$$\prod_{k \in A} y\,x^{k} = y^{\lvert A\rvert}\; x^{\sum_{k \in A} k} = y^{\lvert A\rvert}\, x^{\sigma(A)}$$

و همین است کلِ ترفند: توانِ $y$ اندازهٔ $A$ را می‌شمارد و توانِ $x$ مجموعش را. دو قید، دو متغیر — هر دو هم‌زمان زیرِ نظر.

یک نمونهٔ کوچک. برای $\lbrace 1, 2, 3 \rbrace$ حاصل‌ضرب سه پرانتز دارد:

$$(1 + y x)(1 + y x^2)(1 + y x^3) = 1 + y\left(x + x^2 + x^3\right) + y^2\left(x^3 + x^4 + x^5\right) + y^3 x^6$$

به ضریبِ $y^2$ نگاه کنید: سه جمله دارد، دقیقاً به تعدادِ زیرمجموعه‌های ۲-عضوی، و توان‌هایشان $3, 4, 5$ اند — همان مجموع‌های $\lbrace 1,2 \rbrace$ و $\lbrace 1,3 \rbrace$ و $\lbrace 2,3 \rbrace$.

پس ضریبِ $y^p$، فهرستِ همان زیرمجموعه‌هایی است که می‌خواهیم. ما فقط زیرمجموعه‌های $p$-عضوی را می‌خواهیم، پس از کلِ بسط تنها جمله‌هایی به کارمان می‌آیند که توانِ $y$شان $p$ باشد. یعنی ضریبِ $y^p$ در آن حاصل‌ضرب برابر است با:

$$\sum_{\lvert A\rvert = p} x^{\sigma(A)}$$

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

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

و از این‌جا به بعد، کارِ ما فقط رام کردنِ همین حاصل‌ضرب است.

---

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

از این‌جا به بعد فرض می‌کنیم $j \neq 0$ (حسابِ $S_0$ را که کردیم).

این حاصل‌ضرب $2p$ عامل دارد و همهٔ عامل‌ها یک شکل‌اند: $1 + y\,\omega^{\,jk}$. تنها چیزی که از عاملی به عاملِ دیگر فرق می‌کند، عددِ $\omega^{\,jk}$ است. پس اگر بفهمیم این $2p$ عدد چه‌اند، حاصل‌ضرب را فهمیده‌ایم — و چون در ضرب ترتیب مهم نیست، فقط باید بدانیم هر مقدار چند بار ظاهر می‌شود. سه نکته این را روشن می‌کند.

نکتهٔ اول: از $jk$ فقط باقی‌مانده‌اش بر $p$ مهم است. چون $\omega^{\,p} = 1$، توانِ $\omega$ هر $p$ واحد که جلو برود تکرار می‌شود.

نکتهٔ دوم: در $\lbrace 1, \dots, 2p \rbrace$ هر باقی‌مانده دقیقاً دو بار می‌آید. دو عدد $k$ و $k + p$ هم‌باقی‌مانده‌اند.

نکتهٔ سوم: ضرب در $j$ این تصویر را خراب نمی‌کند. حالا به‌جای $k$ باید $jk$ را نگاه کنیم. اما «جابه‌جاییِ باقی‌مانده‌ها» را داریم: وقتی $p$ اول است و $p \nmid j$، ضرب در $j$ باقی‌مانده‌ها را فقط جابه‌جا می‌کند. جابه‌جایی، تعدادِ تکرارها را عوض نمی‌کند: اگر پیش از آن هر باقی‌مانده دو بار می‌آمد، بعد از آن هم هر باقی‌مانده دو بار می‌آید — فقط شاید نوبتشان فرق کند.

نمونه با $p = 3$ و $j = 2$:

$k$	۱	۲	۳	۴	۵	۶
$2k$	۲	۴	۶	۸	۱۰	۱۲
$2k \bmod 3$	۲	۱	۰	۲	۱	۰

هر یک از باقی‌مانده‌های ۰ و ۱ و ۲ دقیقاً دو بار آمده است.

نتیجه. فهرستِ $2p$ عاملِ حاصل‌ضرب چیزی نیست جز $1 + y\,\omega^{\,r}$ به ازای $r = 0, 1, \dots, p-1$، هر کدام دو بار. و ضربِ چیزی در خودش یعنی مربع:

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

برای همان نمونهٔ $p = 3$ و $j = 2$، سمتِ چپ می‌شود

$$\left(1 + y\omega^2\right)\left(1 + y\omega\right)\left(1 + y\right)\left(1 + y\omega^2\right)\left(1 + y\omega\right)\left(1 + y\right)$$

که با مرتب کردن، دقیقاً مربعِ $\left(1 + y\right)\left(1 + y\omega\right)\left(1 + y\omega^2\right)$ است.

دستاورد را ببینید: حاصل‌ضربی که به $j$ بستگی داشت، به حاصل‌ضربی رسید که هیچ خبری از $j$ در آن نیست. یعنی همهٔ $S_j$ها با $j \neq 0$ یک مقدار دارند. حالا فقط مانده آن حاصل‌ضربِ داخلِ کروشه را حساب کنیم — و آن‌قدر خوش‌رفتار است که ارزشِ یک بخشِ جدا را دارد.

---

اتحاد کلیدی

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

این ادعا در نگاهِ اول عجیب است: حاصل‌ضربی با $p$ عاملِ درهم، و در جواب فقط دو جمله. پیش از اثبات، یک بار با دست ببینیمش.

آزمایش با $p = 3$. سه عامل داریم و بازشان می‌کنیم:

$$(1 + y)\left(1 + y\omega\right)\left(1 + y\omega^2\right)$$

ضریبِ $y$ جمعِ سه ریشه است: $1 + \omega + \omega^2 = 0$. ضریبِ $y^2$ جمعِ حاصل‌ضربِ دوتایی‌هاست: $\omega + \omega^2 + \omega^3$، که چون $\omega^3 = 1$ باز هم $1 + \omega + \omega^2 = 0$ می‌شود. و ضریبِ $y^3$ حاصل‌ضربِ هر سه است: $\omega^3 = 1$. پس همه‌چیز وسط صفر شد و ماند $1 + y^3$. حالا ببینیم چرا این اتفاق تصادفی نیست — اول با یک حسابِ کوتاه که کلِ اتحاد را یک‌جا می‌دهد، بعد با زوم روی خودِ ضریب‌ها.

اثباتِ سریع. همه‌چیز از تجزیه‌ای درمی‌آید که ریشه‌ها از آن آمده‌اند: ریشه‌های $p$-اُمِ واحد دقیقاً ریشه‌های چندجمله‌ایِ $x^p - 1$ اند، پس

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

و این اتحاد برای هر $x$ برقرار است. برای $y \neq 0$ مقدارِ $x = -\frac{1}{y}$ را بگذارید و دو طرف را در $(-y)^p$ ضرب کنید — یعنی یک عاملِ $-y$ به هر پرانتز برسد. هر پرانتز تمیز جمع‌وجور می‌شود:

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

و سمتِ راست هم:

$$(-y)^p \left[\left(-\frac{1}{y}\right)^{p} - 1\right] = \left[(-y)\cdot\left(-\frac{1}{y}\right)\right]^{p} - (-y)^p = 1 - (-y)^p$$

پس به یک اتحادِ عمومی رسیدیم که برای هر $p$ — زوج یا فرد — درست است:

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

(حالتِ $y = 0$ هم که هر دو طرف $1$ اند.) حالا فرد بودنِ $p$ قدمِ آخر را برمی‌دارد: $(-y)^p = -y^p$، پس حاصل $1 + y^p$ است. تمام.

این اثبات کامل است، اما پرسشِ آزمایشِ $p = 3$ را بی‌جواب می‌گذارد: آن‌جا ضریب‌ها یکی‌یکی صفر می‌شدند؛ سازوکارِ این حذف چیست؟ اگر عجله دارید، با همین اثبات جلو بروید — و اگر کنجکاوید:

زوم روی ضریب‌ها — چرا همهٔ جمله‌های میانی صفر می‌شوند؟

گامِ اول: ضریب‌های بسط چه هستند؟ همان منطقِ بخشِ تابعِ مولد: باز کردنِ حاصل‌ضرب یعنی از هر عامل یکی از دو گزینه را برداشتن. اگر از $t$ عامل گزینهٔ $y\,\omega^{\,r}$ را برداریم و از بقیه $1$ را، جمله‌ای به شکلِ $y^t$ ضربدرِ حاصل‌ضربِ آن $t$ ریشه می‌گیریم. پس:

ضریبِ $y^t$ برابر است با جمعِ حاصل‌ضربِ همهٔ دسته‌های $t$-تایی از ریشه‌های $p$-اُمِ واحد.

این عدد نامِ استانداردی دارد؛ آن را $e_t$ می‌نامند. ادعای ما در این زبان یعنی: $e_t$ برای هر $t$ میانِ $1$ و $p-1$ صفر است، و $e_p = 1$.

گامِ دوم: این عددها را از کجا بیاوریم؟ از همان تجزیه‌ای که اثباتِ سریع از آن آغاز شد — این بار به‌جای جای‌گذاری، بازش می‌کنیم؛ همان $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$$

گامِ سوم: مقایسهٔ دو طرف. حالا به سمتِ چپ نگاه کنید: $x^p - 1$ هیچ جملهٔ میانی ندارد — نه $x^{p-1}$، نه $x^{p-2}$، تا $x^1$؛ همه‌شان ضریبِ صفر دارند. پس ناچار

$$e_1 = e_2 = \cdots = e_{p-1} = 0$$

و از جمله‌های ثابتِ دو طرف، $(-1)^p\, e_p = -1$؛ چون $p$ فرد است این یعنی $-e_p = -1$، پس $e_p = 1$.

همین $e_p$ را مستقیم هم می‌شود دید (و جای دقیقی که فرد بودنِ $p$ وارد می‌شود، این‌جا هم پیداست): $e_p$ حاصل‌ضربِ همهٔ ریشه‌هاست، یعنی

$$\omega^{\,0}\,\omega^{\,1}\cdots\omega^{\,p-1} = \omega^{\,0 + 1 + \cdots + (p-1)} = \omega^{\,\frac{p(p-1)}{2}} = \left(\omega^{\,p}\right)^{\frac{p-1}{2}} = 1$$

و این گامِ آخر فقط وقتی مجاز است که $\frac{p-1}{2}$ عددی صحیح باشد — یعنی وقتی $p$ فرد است.

نتیجه. در بسطِ $\prod_{r}\left(1 + y\,\omega^{\,r}\right)$ همهٔ ضریب‌های میانی صفرند و فقط دو جمله زنده می‌مانند: $1$ (از $t = 0$) و $y^p$ (از $t = p$).

در کلِ محاسبهٔ جبریِ $S_j$، فرد بودنِ $p$ فقط همین یک کار را کرد: علامتِ جملهٔ آخر را تعیین کرد. (پیش‌تر هم یک بار به آن تکیه کرده بودیم — آن‌جا که در بخشِ حدس نشان دادیم مجموعِ دو زیرمجموعهٔ استثنایی مضربِ $p$ است.) و بی‌دلیل هم نیست که این‌جا حساس است: برای $p = 2$ خودِ اتحاد می‌شکند:
$(1 + y)(1 + y\omega) = (1+y)(1-y) = 1 - y^2$، نه $1 + y^2$ — دقیقاً همان $1 - (-y)^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}$$

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

---

پژواکِ حدس: آن عددِ ۲ از کجا آمد؟

در بخشِ حدس یک ۲ داشتیم: تعدادِ استثناها. در جمعِ آخر باز یک ۲ بیرون آمد: مقدارِ $S_j$. برگه تا این‌جا این دو را جدا از هم دیده — انگار دو عددِ هم‌نام که تصادفاً کنارِ هم افتاده‌اند. اما یکی‌اند، و دیدنش یک خطِ حساب بیشتر نمی‌خواهد.

اول چیزی را بشماریم که هنوز نشمرده‌ایم. تا این‌جا فقط پرسیده‌ایم چند زیرمجموعه باقی‌ماندهٔ صفر دارند. پرسشِ کامل این است: به ازای هر باقی‌ماندهٔ $t$، چند زیرمجموعهٔ $p$-عضوی هست که $\sigma(A) \equiv t \pmod p$؟ اسمِ این عدد را $N_t$ بگذارید.

کارِ تازه‌ای لازم نیست؛ همان $S_j$ها جواب را در خود دارند. کافی است فیلتر را به‌جای $\sigma(A)$ روی $\sigma(A) - t$ بگذارید — که دقیقاً وقتی ۱ می‌دهد که $\sigma(A) \equiv t$ باشد:

$$N_t = \sum_{\lvert A\rvert = p} F_p\bigl(\sigma(A) - t\bigr) = \frac{1}{p} \sum_{j=0}^{p-1} \omega^{-\,j t}\; S_j$$

حالا مقدارهایی را که به‌دست آورده‌ایم بگذارید — $S_0 = \binom{2p}{p}$ و بقیه همه برابرِ $2$:

$$N_t = \frac{1}{p}\left[\binom{2p}{p} + 2\sum_{j=1}^{p-1} \omega^{-\,j t}\right]$$

آن جمعِ کوچک دو حالت دارد. برای $t = 0$ هر جمله‌اش $1$ است، پس جمع $p - 1$ می‌شود. برای $t \neq 0$، چون $p \nmid t$، توان‌های $\omega^{-\,jt}$ به ازای $j = 0, \dots, p-1$ همهٔ ریشه‌ها را می‌سازند و روی‌هم صفرند؛ جملهٔ $j = 0$ که $1$ است را کنار بگذارید، می‌ماند $-1$. پس:

$$N_t = \frac{\dbinom{2p}{p} - 2}{p} \;+\; \begin{cases} 2, & t = 0 \\ 0, & t \neq 0 \end{cases}$$

برای $p = 5$ که $\binom{10}{5} = 252$ است:

باقی‌ماندهٔ مجموع بر ۵	۰	۱	۲	۳	۴
تعدادِ زیرمجموعه‌ها	۵۲	۵۰	۵۰	۵۰	۵۰

روی‌هم $52 + 4 \times 50 = 252$، همان $\binom{10}{5}$. و این دقیقاً همان شکلی است که در $p = 3$ با دست دیدیم: کاملاً یکنواخت، به‌علاوهٔ دو تا اضافه روی صفر. آن مشاهده حالا برای هر $p$ ثابت شده است.

و حالا این را برعکس بخوانید. زیرمجموعه‌ها را بر حسبِ باقی‌ماندهٔ مجموعشان دسته‌بندی کنید؛ آن‌گاه $S_j$ را می‌شود این‌طور هم نوشت:

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

حالا $N_t$ را به دو تکه بشکنید: تکهٔ یکنواخت، که برای همهٔ $t$ یک عددِ ثابت است، و آن دو تای اضافه که روی $t = 0$ نشسته‌اند. سهمِ تکهٔ یکنواخت در این جمع صفر است — عددی ثابت ضربدرِ جمعِ همهٔ ریشه‌های واحد (چون $j \neq 0$ است، توان‌های $\omega^{\,jt}$ همهٔ ریشه‌ها را دقیقاً یک بار می‌سازند). پس تنها چیزی که زنده می‌ماند سهمِ آن دو تای اضافه است، و چون روی $t = 0$ نشسته‌اند هر کدام $\omega^{\,0} = 1$ می‌آورند:

$$S_j = \underbrace{\frac{\binom{2p}{p} - 2}{p}\sum_{t=0}^{p-1} \omega^{\,j t}}_{=\;0} \;+\; 2 \;=\; 2$$

پس $S_j = 2$ و «دو استثنا» دو جملهٔ یک حرف‌اند. آن عددِ ۲ که از اتحادِ $\left(1 + y^p\right)^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$ است، و چون $p$ اول است، یا $1$ است یا $p$. مدارِ تک‌عضوی هم یعنی زیرمجموعه‌ای که دوران تکانش نمی‌دهد؛ و چنین زیرمجموعه‌ای اگر عضوی داشته باشد، ناچار عضوِ بعدی و بعدیِ آن را هم دارد، تا دورِ کامل — پس از نیمهٔ نخست یا هیچ ندارد یا همه را، و این یعنی همان دو زیرمجموعهٔ $\lbrace p+1, \dots, 2p \rbrace$ و $\lbrace 1, \dots, p \rbrace$. بقیهٔ زیرمجموعه‌ها همه در مدارهای دقیقاً $p$-تایی می‌نشینند، و «$2 +$» در فرمول، شمارشِ همین دو نقطهٔ ثابت است.

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

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

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

و حالا کوتاه‌ترین راه به $S_j = 2$. همین دوران، بی‌هیچ تابعِ مولد و بی‌هیچ اتحادی، آن عددِ ۲ را هم می‌دهد. در $S_j = \sum_A \omega^{\,j\,\sigma(A)}$ — با همان فرضِ $j \neq 0$ — زیرمجموعه‌ها را مدار به مدار جمع بزنید:

• هر مدارِ $p$-تایی مجموع‌هایی دارد که همهٔ باقی‌مانده‌ها را دقیقاً یک بار می‌پوشانند، پس سهمش $\sum_{r=0}^{p-1} \omega^{\,j r} = 0$ است — کلِ مدار پاک می‌شود.
• می‌مانند دو نقطهٔ ثابت، که مجموعشان بخش‌پذیر بر $p$ است و هر کدام $\omega^{\,0} = 1$ می‌آورند.

$$S_j = 0 + 1 + 1 = 2$$

همان نتیجهٔ بخشِ «اتحاد کلیدی» — و این بار پیداست که آن ۲، تعدادِ نقطه‌های ثابت است. حلقه بسته شد: دو استثنایی که در آغازِ برگه با دست پیدا کردیم، همان دو نقطهٔ ثابتِ دورانند، و همان ۲ ای که فیلتر پس داد.

و این تطابق از آنچه به نظر می‌رسد محکم‌تر است. به استدلالِ بالا دقت کنید: هیچ‌جا از فرد بودنِ $p$ استفاده نکردیم. مدارها به‌هرحال پاک می‌شوند، و آنچه می‌ماند سهمِ دو نقطهٔ ثابت است — هرچه که باشد. برای $p$ فرد مجموعِ هر دو نقطهٔ ثابت مضربِ $p$ است و هر کدام $\omega^{\,0} = 1$ می‌دهند، که $S_j = 2$ می‌شود. حالا همین را برای $p = 2$ بنویسید، جایی که $\omega = -1$ است و مجموع‌های دو نقطهٔ ثابت $\lbrace 1, 2 \rbrace$ و $\lbrace 3, 4 \rbrace$ برابرِ ۳ و ۷ اند — هر دو فرد، پس دیگر مضربِ $p$ نیستند:

$$S_1 = (-1)^3 + (-1)^7 = -2$$

و این دقیقاً همان عددی است که راهِ جبری می‌دهد: آن‌جا اتحاد به $\left(1 - y^2\right)^2 = 1 - 2y^2 + y^4$ می‌شکند و ضریبِ $y^2$ برابرِ $-2$ است. یعنی دوران، در حالتی هم که فرمولِ نهاییِ مسئله غلط از آب درمی‌آید، باز عیناً همان خروجیِ فیلتر را می‌سازد.

پس نسبتِ این دو راه‌حل، شباهتِ ظاهری نیست:

دوران، $S_j$ را محاسبه می‌کند — نه فقط جوابِ نهایی را. هرچه فیلتر بیرون بدهد، شمارشِ مدارها و نقطه‌های ثابت همان را می‌دهد.

پس فیلتر چه بود؟

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

پنجره‌ای به ریاضیاتِ دانشگاهی — سرشت‌ها، فوریهٔ گسسته و میانگین‌گیری روی گروه

این جعبه برای خواننده‌ای است که ریاضیاتِ دانشگاهی دیده باشد؛ ادامهٔ برگه به آن نیازی ندارد.

باقی‌مانده‌ها به پیمانهٔ $p$، با جمع، گروهِ دوریِ $\mathbb{Z}/p\mathbb{Z}$ را می‌سازند، و دوران — همان که مدارها را ساخت — یک کنشِ همین گروه روی زیرمجموعه‌هاست. حالا برای هر $j$ تابعِ

$$\chi_j(t) = \omega^{\,jt}$$

را در نظر بگیرید؛ جمع را به ضرب می‌برد: $\chi_j(t_1 + t_2) = \chi_j(t_1)\,\chi_j(t_2)$. این $p$ تابع، سرشت‌های (characters) گروهِ $\mathbb{Z}/p\mathbb{Z}$ اند، و لمِ فیلتر به زبانِ آن‌ها این می‌شود:

$$\frac{1}{p}\sum_{j=0}^{p-1}\chi_j(t) = \begin{cases} 1, & t = 0 \\ 0, & t \neq 0 \end{cases}$$

— حالتِ خاصی از روابطِ تعامدِ سرشت‌ها. و رفت‌وبرگشتی که در «پژواکِ حدس» میانِ $N_t$ و $S_j$ دیدیم — $S_j = \sum_t N_t\,\chi_j(t)$ و بازسازیِ $N_t$ از روی $S_j$ها — دقیقاً تبدیلِ فوریهٔ گسسته روی این گروه و وارونِ آن است: $S_j$ها ضریب‌های فوریهٔ دنبالهٔ $N_t$ اند.

جمع‌زدن روی مدارها هم همین عمل است، از سمتِ کنش. در هر قدمِ دوران، تابعِ $A \mapsto \omega^{\,j\,\sigma(A)}$ در عددِ ثابتِ $\omega^{\,j\,\lvert A_1\rvert}$ ضرب می‌شود — که روی مدارهای $p$-تایی، با $j \neq 0$ و $0 < \lvert A_1\rvert < p$، ناواحد است؛ چنین ضریبی جمعِ روی مدارِ کامل را خنثی می‌کند و فقط سهمِ جاهایی می‌ماند که کنش تکانشان نمی‌دهد: نقطه‌های ثابت. این نمونه‌ای از اصلِ عمومیِ نظریهٔ نمایش است: میانگین‌گیری روی گروه، تصویری است روی زیرفضای ناورداها؛ مؤلفه‌های ناناوردا در میانگین حذف می‌شوند. «بازتابِ جبری» که در متن گفتیم، در این زبان یعنی: هر دو راه‌حل یک میانگین‌گیری روی $\mathbb{Z}/p\mathbb{Z}$ اند — یکی در فضای تابع‌ها با سرشت‌ها، دیگری روی خودِ زیرمجموعه‌ها با دوران.

---

تمرین‌ها

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

راهنمای کوچک

دوران فقط به عضوهای $\lbrace 1, 2, 3 \rbrace$ دست می‌زند؛ اول $A_1$ را جدا کنید.

ایدهٔ اصلی

بخشِ چرخان فقط یک عضو دارد. سه قدمِ دوران را بنویسید و هر بار باقی‌ماندهٔ مجموع بر ۳ را ثبت کنید؛ باید هر سه مقدار را ببینید.

راه‌حلِ کامل

این‌جا $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$ است.

تمرین ۲ — استفاده از دوران. در بخشِ «پژواکِ حدس» با فیلتر نشان دادیم که برای هر باقی‌ماندهٔ $r \neq 0$، تعدادِ زیرمجموعه‌های $p$-عضویِ $\lbrace 1, \dots, 2p \rbrace$ با مجموعِ همنهشتِ $r$ برابرِ $\frac{1}{p}\left[\binom{2p}{p} - 2\right]$ است — یعنی بی‌هیچ «$2+$». همین را این بار فقط با دوران ثابت کنید.

راهنمای کوچک

از تقسیم‌بندیِ «پشتِ صحنه» شروع کنید: نقطه‌های ثابت و مدارهای $p$-تایی. سهمِ هر کدام به باقی‌ماندهٔ $r$ چقدر است؟

ایدهٔ اصلی

مجموعِ هر دو نقطهٔ ثابت همنهشتِ صفر است، پس به $r \neq 0$ هیچ سهمی نمی‌دهند؛ و هر مدارِ $p$-تایی به هر باقی‌مانده دقیقاً یک زیرمجموعه می‌دهد. فقط مانده که مدارها را بشمارید.

راه‌حلِ کامل

زیرمجموعه‌های $p$-عضوی را زیرِ همان دوران به مدارها بشکنید. دو نقطهٔ ثابت — $\lbrace 1, \dots, p \rbrace$ و $\lbrace p+1, \dots, 2p \rbrace$ — مدارهای تک‌عضوی‌اند و مجموعِ هر دو همنهشتِ صفر است؛ پس هیچ‌کدام به باقی‌مانده‌های $r \neq 0$ چیزی نمی‌دهند. بقیهٔ زیرمجموعه‌ها در مدارهای دقیقاً $p$-تایی‌اند و در هر مدار، باقی‌مانده‌های مجموع همهٔ $p$ مقدار را دقیقاً یک بار می‌پوشانند؛ پس هر مدار به هر باقی‌مانده — از جمله به $r$ — دقیقاً یک زیرمجموعه می‌دهد.

تعدادِ این مدارها $\frac{1}{p}\left[\binom{2p}{p} - 2\right]$ است (کلِ زیرمجموعه‌ها منهای دو نقطهٔ ثابت، تقسیم بر $p$)، و حکم به‌دست می‌آید. برای $r = 0$ همین شمارش برقرار است، منتها آن دو نقطهٔ ثابت هم به آن اضافه می‌شوند — و این دقیقاً همان «$2+$» است.

تمرین ۳ — انتقالِ فیلتر. فیلتر را این بار بی‌هیچ مسئلهٔ ترکیبیاتی، مستقیم روی یک جمع به کار ببرید و نشان دهید برای هر $n \ge 0$:

$$\sum_{\substack{0 \le k \le n \\ 3 \,\mid\, k}} \binom{n}{k} = \frac{1}{3}\left(2^n + 2\cos\frac{n\pi}{3}\right)$$

راهنمای کوچک

سمتِ چپ یک جمعِ شرطی است — «فقط $k$های مضربِ ۳» — و فیلتر برای همین ساخته شده. جمعِ $\sum_k \binom{n}{k}\,x^k$ را هم می‌شناسید؛ فیلتر چه چیزی به‌جای $x$ می‌نشاند؟

ایدهٔ اصلی

فیلترِ پیمانهٔ ۳ را روی $k$ بگذارید و جای دو جمع را عوض کنید: $\sum_k \binom{n}{k}\,\omega^{\,jk} = \left(1 + \omega^{\,j}\right)^n$، پس جمعِ شرطی به سه جای‌گذاری در بسطِ دوجمله‌ای تبدیل می‌شود. بعد $1 + \omega$ و $1 + \omega^2$ را قطبی بنویسید و دموآور بزنید.

راه‌حلِ کامل

همان فیلتر، این بار با پیمانهٔ ۳ و $\omega$ی با طول ۱ و زاویهٔ $\frac{2\pi}{3}$. آن را روی $k$ بگذارید و جای دو جمع را عوض کنید:

$$\sum_{3 \,\mid\, k} \binom{n}{k} = \sum_{k=0}^{n} \binom{n}{k}\, F_3(k) = \frac{1}{3}\sum_{j=0}^{2}\; \sum_{k=0}^{n} \binom{n}{k} \left(\omega^{\,j}\right)^{k} = \frac{1}{3}\sum_{j=0}^{2} \left(1 + \omega^{\,j}\right)^{n}$$

گامِ آخر فقط بسطِ دوجمله‌ای است — و همین است کلِ ترفند: جمعِ ناجورِ «فقط $k$های مضربِ ۳» به سه بار جای‌گذاری در یک بسطِ آشنا تبدیل شد. جملهٔ $j = 0$ برابرِ $2^n$ است. برای دو جملهٔ دیگر، $\omega = -\frac{1}{2} + \frac{\sqrt{3}}{2}\,i$ و $\omega^2 = -\frac{1}{2} - \frac{\sqrt{3}}{2}\,i$ را بگذارید:

$$1 + \omega = \frac{1}{2} + \frac{\sqrt{3}}{2}\,i, \qquad 1 + \omega^2 = \frac{1}{2} - \frac{\sqrt{3}}{2}\,i$$

هر دو طولِ ۱ دارند و زاویه‌هایشان $\frac{\pi}{3}$ و $-\frac{\pi}{3}$ است — دو مزدوج روی دایرهٔ واحد. پس توانِ $n$-اُمشان یعنی $n$ برابر شدنِ زاویه (همان دموآور): زاویه‌های $\frac{n\pi}{3}$ و $-\frac{n\pi}{3}$ روی دایرهٔ واحد. جمعِ این دو، چون قسمت‌های موهومی یکدیگر را خنثی می‌کنند، برابر است با $2\cos\frac{n\pi}{3}$. وارسی با $n = 4$: سمتِ چپ $\binom{4}{0} + \binom{4}{3} = 5$ است و سمتِ راست $\frac{1}{3}\left(16 - 1\right) = 5$.

تمرین ۴ — دو راه‌حل. فرض کنید $p$ اول است و $0 < k < p$. نشان دهید برای هر باقی‌ماندهٔ $t$، تعدادِ زیرمجموعه‌های $k$-عضویِ $\lbrace 1, \dots, p \rbrace$ که مجموعشان به پیمانهٔ $p$ برابرِ $t$ است، دقیقاً $\frac{1}{p}\binom{p}{k}$ است — یعنی این بار هیچ استثنایی در کار نیست و تقسیم کاملاً عادلانه است. بعد همین حکم را یک بار هم با دوران ببینید.

راهنمای کوچک

برای باقی‌ماندهٔ دلخواهِ $t$، فیلتر را روی چه عبارتی بگذارید که «$\sigma(A) \equiv t$» را آشکار کند؟ در بخشِ «پژواکِ حدس» یک بار این کار را کرده‌ایم.

ایدهٔ اصلی

با $F_p\bigl(\sigma(A) - t\bigr)$ همان مسیرِ متن را بروید؛ این بار حاصل‌ضرب $p$ عامل دارد، و برای $j \neq 0$ ضریبِ $y^k$ اتحادِ کلیدی با $0 < k < p$ صفر است — پس فقط جملهٔ $j = 0$ می‌ماند و هیچ استثنایی اضافه نمی‌شود. در روایتِ دورانی، همین «هیچ» یعنی: با $0 < k < p$ نقطهٔ ثابتی در کار نیست.

راه‌حلِ کامل

فیلتر را روی $\sigma(A) - t$ بگذارید: $F_p\bigl(\sigma(A) - t\bigr)$ دقیقاً وقتی ۱ است که $\sigma(A) \equiv t$ باشد. پس با جمع‌های $A \subseteq \lbrace 1, \dots, p \rbrace$:

$$N_t = \sum_{\lvert A\rvert = k} F_p\bigl(\sigma(A) - t\bigr) = \frac{1}{p}\sum_{j=0}^{p-1} \omega^{-\,j t}\; T_j, \qquad T_j = \sum_{\lvert A\rvert = k} \omega^{\,j\,\sigma(A)}$$

مثلِ متنِ برگه، $T_j$ ضریبِ $y^k$ است در $\prod_{m=1}^{p}\left(1 + y\,\omega^{\,jm}\right)$. برای $j \neq 0$ ضرب در $j$ باقی‌مانده‌ها را فقط جابه‌جا می‌کند، پس این حاصل‌ضرب همان $\prod_{r=0}^{p-1}\left(1 + y\,\omega^{\,r}\right)$ است — و ضریبِ $y^k$ آن برای $0 < k < p$ صفر است. پس فقط جملهٔ $j = 0$ زنده می‌ماند:

$$N_t = \frac{1}{p}\,T_0 = \frac{1}{p}\binom{p}{k}$$

مستقل از $t$، همان‌طور که ادعا شد. (توجه کنید که این‌جا فقط به صفر بودنِ جمله‌های میانیِ اتحاد نیاز داشتیم، نه به جملهٔ آخرش — و اتحادِ عمومیِ $1 - (-y)^p$ برای هر $p$ جملهٔ میانی ندارد؛ برای همین فرد بودنِ $p$ هم لازم نشد.)

با دوران: زیرمجموعهٔ $k$-عضوی را در $\lbrace 1, \dots, p \rbrace$ بچرخانید. اندازهٔ هر مدار مقسوم‌علیهی از $p$ است، و تنها زیرمجموعه‌های ثابت زیرِ دوران تهی و کامل‌اند — هر دو به همان استدلالِ بخشِ «پشتِ صحنه» — که با $0 < k < p$ کنار می‌روند؛ پس هر مدار دقیقاً $p$ عضو دارد. در هر قدمِ دوران مجموع $k$ واحد جلو می‌رود و چون $\gcd(k, p) = 1$، این $p$ مقدار همهٔ باقی‌مانده‌ها را دقیقاً یک بار می‌پوشانند. پس هر مدار به هر باقی‌مانده دقیقاً یک زیرمجموعه می‌دهد.

تمرین ۵ — چالشِ نظریهٔ اعداد. با اتحادِ وندرموند، $\binom{2p}{p} = \sum_{k=0}^{p} \binom{p}{k}^2$، نشان دهید که $\binom{2p}{p} - 2$ حتی بر $p^2$ هم بخش‌پذیر است.

راهنمای کوچک

دو جملهٔ $k = 0$ و $k = p$ در جمعِ وندرموند روی هم $2$ می‌دهند. پس کافی است هر جملهٔ میانی مضربِ $p^2$ باشد؛ و هر جملهٔ میانی یک مربع است.

ایدهٔ اصلی

برای $0 < k < p$ نشان دهید $p \mid \binom{p}{k}$؛ آن‌وقت $\binom{p}{k}^2$ مربعِ یک مضربِ $p$ است، یعنی مضربِ $p^2$. برای بخش‌پذیریِ خودِ $\binom{p}{k}$، اتحادِ $k\binom{p}{k} = p\binom{p-1}{k-1}$ کار را تمام می‌کند.

راه‌حلِ کامل

برای $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$ به کاری نمی‌آید.

ایدهٔ اصلی

فیلترِ تک‌متغیره $N$ را به $\frac{1}{n}\sum_j \prod_k \left(1 + \omega^{\,jk}\right)$ می‌رساند و جملهٔ $j = 0$ به‌تنهایی $2^n$ است؛ پس کافی است نشان دهید هیچ جمله‌ای منفی نیست. برای این کار، جملهٔ $j$ را بر حسبِ $m = \frac{n}{\gcd(j,\,n)}$ بازنویسی کنید: توان‌های $\omega^{\,jk}$ توان‌های یک ریشهٔ $m$-اُمِ اولیه‌اند، و همان جای‌گذاریِ اثباتِ سریع — این بار $x = -1$ — هر جمله را صفر یا یک توانِ ۲ می‌کند.

راه‌حلِ کامل

این‌جا پیمانه $n$ است که لازم نیست اول باشد — اما اشکالی ندارد: اثباتِ فیلتر با تصاعدِ هندسی هیچ‌جا به اول بودنِ پیمانه تکیه نکرد، پس $F_n$ برای هر $n$ همان‌طور کار می‌کند. فیلتر را این بار تک‌متغیره به کار بیندازید — قیدِ اندازه نداریم، پس $y$ لازم نیست. با $\omega$ی به طول ۱ و زاویهٔ $\frac{2\pi}{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$ — هیچ‌کدام منفی نیست — و چون جملهٔ $j = 0$ به‌تنهایی $2^n$ است، $N \ge \frac{2^n}{n}$. (این کران گاهی دقیق است: برای $n = 8$ تساوی رخ می‌دهد و $N = 32$.)

و در واقع جوابِ دقیق هم همین‌جاست. کافی است جمله‌های زنده را بشماریم. جملهٔ $j$ فقط به $m = \frac{n}{\gcd(j,\,n)}$ بستگی دارد، و تعدادِ $j$هایی در $\lbrace 0, \dots, n-1 \rbrace$ که این $m$ را می‌سازند دقیقاً $\varphi(m)$ است. جمله‌های با $m$ زوج صفرند، پس فقط $m$های فرد می‌مانند:

$$N = \frac{1}{n} \sum_{\substack{m \,\mid\, n \\ 2 \,\nmid\, m}} \varphi(m)\, 2^{\,n/m}$$

وارسی با $n = 6$: مقسوم‌علیه‌های فردِ ۶ عبارت‌اند از ۱ و ۳، پس $N = \frac{1}{6}\left(1 \cdot 2^6 + 2 \cdot 2^2\right) = \frac{72}{6} = 12$ — و شمارشِ مستقیم هم ۱۲ می‌دهد.

---

جمع‌بندی

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

عصارهٔ روش. از این برگه دو ایده می‌ماند، و هر دو فراتر از این مسئله‌اند:

• بخش‌پذیری را می‌شود به جمع ترجمه کرد. «بر $p$ بخش‌پذیر هست یا نه» پرسشی دوحالتی است، و فیلترِ ریشه‌های واحد آن را به عددی بدل می‌کند که می‌شود جمعش زد. همین ترجمه است که یک شمارشِ شرطی را به یک محاسبه تبدیل می‌کند.
• همان ترفندِ چندجمله‌ای‌ها، این بار با دو متغیر. نوشتنِ یک شمارش به‌صورتِ ضریب‌های یک چندجمله‌ای را پیش‌تر در مسئلهٔ تاس‌ها دیده بودیم. این‌جا همان ایده بود، فقط با دو متغیر — یکی برای هر قید.

---

منابع

• سی‌وششمین المپیاد جهانی ریاضی — تورنتوی کانادا، ۱۳ تا ۲۵ ژوئیهٔ ۱۹۹۵
• صورتِ رسمیِ مسئله‌های همان دوره (مسئلهٔ ششم)