قضیه هیلز–جووت

در ریاضیات قضیهٔ هیلز-جووت یکی از نتایج اصلی نظریه رمزی می‌باشد، اسم این قضیه برگرفته از اسم دو شخص به نام‌های Alfred W. Hales و R. I. Jewett می‌باشد. این دو نفر می‌خواستند نشان دهند که اشیاء با ابعاد بالا، باید ساختار ترکیبیاتی قانونمندی داشته باشند و ممکن نیست که خواص چنین اشیائی به‌طور کامل رندوم و تصادفی باشد.^[۱]

یک توصیف نادقیق هندسی از قضیه این است که برای هر دو عدد صحیح مثبت مانند $n$ و $c$ عددی مانند $H$ وجود دارد که، اگر خانه‌های یک شبکهٔ مکعبی $H$ بعدی $n*n*n*...*n$ ، با $c$ رنگ، رنگ شوند، باید سطر، ستون یا قطری وجود داشته باشد که همهٔ خانه‌های آن یکرنگ هستند. به بیانی دیگر، برای نسخهٔ تعمیم یافته از بازی ایکس-او $n$ تایی، عدد $H$ وجود دارد که اگر این بازی در مکعب $H$ بعدی $n*n*n*...*n$ انجام شود، بازی هرگز مساوی نخواهد شد! مهم نیست که $n$ چقدر بزرگ باشد یا این که چند بازیکن در بازی شرکت می‌کنند و کدام یک از در کدام نوبت بازی خواهد کرد! فقط کافی است که بازی در یک صفحه با بعد $H$ مناسب انجام شود. با استفاده از استدلال استراتژی دزدی، شاید کسی فکر کند که اگر دو بازیکن یکی درمیان بازی کنند، آنگاه نفر اول برای $H$ های به اندازهٔ کافی بزرگ، استراتژی برد خواهد داشت، با این حال تا به الان الگوریتمی عملی برای اجرای این استراتژی شناخته نشده‌است!

برای توصیف دقیق تر، $W_{n}^{H}$ را مجموعهٔ کلمات به طول $H$ روی یک الفبای $n$ حرفی تعریف می‌کنیم که این الفبا همان مجموعهٔ $\{1,2,3,..,n\}$ می‌باشد، و با این تعریف تمام کلمات $H$ حرفی این الفبا عضو $W_{n}^{H}$ هستند! این مجموعه، ابرمکعبی که موضوع قضیه است را شکل می‌دهد .(در واقع اینطور تصور می‌کنیم که هر کلمه آدرس یک خانه از این ابر مکعب است) یک کلمهٔ متغیر مانند $w(x)$ روی $W_{n}^{H}$ کلمه‌ای است که در جای حداقل یکی از حروف آن متغیر $x$ قرار دارد. به‌طور مثال $w(x)=11x4$ کلمه‌ای با ۴ حرف است! کلمات $w(1),w(2),w(3),...,w(n)$ یک خط ترکیبیاتی را در فضای $W_{n}^{H}$ تشکیل می‌دهند، خطوط ترکیبیاتی شامل سطرها، ستون‌ها و بعضی از اقطار ابرمکعب می‌باشند، قضیه هیلز جووت بیان می‌کند که برای اعداد داده شدهٔ $n$ و $c$ ، عدد مثبت وصحیح $H$ وجود دارد که وابسته به $c$ و $n$ است و برای هر افراز $W_{n}^{H}$ به $c$ دسته، حداقل یک دسته وجود دارد که یک خط ترکیبیاتی به‌طور کامل عضو آن دسته است!

برای مثال قرار می‌دهیم: n=3, c=2,H=۳، ابر مکعب $W_{n}^{H}$ به دست آمده در این حالت خاص، در واقع همان صفحهٔ بازی معروف ایکس-او است!

۱۱ ۱۲ ۱۳

۲۱ ۲۲ ۲۳

۳۱ ۳۲ ۳۳

به‌طور مثال کلمهٔ $2x$ را در نظر بگیرید، با قرار دادن ۱٬۲،۳ به جای متغیر $x$ خط ۲۱ ۲۲ ۲۳ به دست می‌آید. یا برای مثال کلمهٔ متغیر $xx$ را در نظر بگیرید، به قرار دادن ۱٬۲،۳ به جای $x$ ، خط ترکیبیاتی یا همان قطر ۱۱ ۲۲ ۳۳ به دست می‌آید.(توجه کنید که در بازی ایکس-او، اگر تمام قطر ۱۳ ۲۲ ۳۱ توسط یکی از بازیکنان علامت گذاری شود، آن بازیکن برنده می‌شود، اما این خط، یک خط ترکیبیاتی نیست. در این حالت خاص $(n=3,c=2,H=3)$ ، قضیه هیلز–جووت برقرار نیست. در این حالت امکان‌پذیر است که خانه‌ها را به دو دسته افراز کنیم (به‌طور مثال {۱۱٬۲۲٬۲۳٬۳۱} و {۱۲٬۱۳٬۲۱٬۳۲٬۳۳}) که هیچکدام از دسته‌ها شامل یک خط ترکیبیاتی نباشند.(در واقع در این حالت بازی مساوی می‌شود!) از طرف دیگر اگر H را به عدد ۸ افزایش دهیم ،(دقت کنید که تعداد خانه‌های زمین بازی در این حالت برابر با ۳۸ = ۶۵۶۱ می‌شود!) و این زمین بازی را به دو دسته تقسیم کنیم (همان "ضربدر" و" دایره"های مشهور که در بازی استفاده می‌شود!)، یکی از دسته‌ها حتماً شامل یک خط ترکیبیاتی است .(یا به عبارتی بازی مساوی نمی‌شود!) برای اثبات پایین را نگاه کنید.

اثبات قضیه در حالتی خاص

اکنون به اثبات قضیه هیلز–جووت در حالت خاص $n=3,c=2,H=8$ که در بالا بحث شد می‌پردازیم. ایده این است که این حکم را به اثبات حالات ساده‌تر قضیه هیلز–جووت کاهش دهیم.(در این حالت خاص منظور $n=2,c=2,H=2$ و $n=2,c=6,H=6$ است.) حالت کلی قضیه هیلز–جووت را می‌توان با روشی مشابه با استفاده از استقرای ریاضی اثبات کرد.

هر عضو ابرمکعب $w_{3}^{8}$ رشته‌ای از هشت عدد از ۱ تا ۳ است مثلاً ۱۳۲۱۱۳۲۱ یک عضو ابرمکعب است. ما فرض می‌کنیم که ابر مکعب کاملاً از "دایره" و "ضربدر" پر شده باشد. ما برای اثبات از برهان خلف استفاده می‌کنیم و فرض می‌کنیم که نه دسته دایره‌ها و نه دسته ضربدرها شامل خط ترکیبیاتی نیستند. اگر ما ۶ عضو اینچنین رشته‌ای را ثابت بگیریم و ۲ عضو اخر را متغیر فرض کنیم یک صفحه بازی ایکس-او عادی خواهیم داشت برای مثال ??۱۳۲۱۱۳ چنین صفحه‌ای را به ما می‌دهد. برای صفحه‌ای مانند ??abcdef، حالت‌های abcdef11 ,adcdef12, abcdef22 را در نظر می‌گیریم. هر یک از این حالت‌ها باید یا با دایره یا با ضربدر پر شوند پس طبق اصل لانه کبوتری ۲ تا از آن‌ها باید با علامت مشابه پر شوند. از آن جهت که هر یک از این حالت‌ها قسمتی از خطوط ترکیبیاتی ما هستند، عضو سوم باید با علامت مخالف پر شود (زیرا ما فرض کردیم که هیچ‌کدام از خطوط ترکیبیاتی، ۳ عضو پر شده با علامت مشابه را ندارد). به عبارت دیگر، برای هر یک از انتخاب‌های abcdef (که می‌توان آن را به عنوان عضو ابر مکعب ۶ بعدی در نظر گرفت) ۶ حالت می‌توان در نظر گرفت:

Abcdef11 و12 abcdef دایره هستند و abcdef13 یک ضربدر است.
Abcdef11 و abcdef22 دایره هستند و abbcdef33 یک ضربدر است.
Abcdef12 و abcdef22 دایره هستند و abcdef32 یک ضربدر است.
Abcdef11 و abcdef12 ضربدر هستند و abcdef13 یک دایره است.
Abcdef11 و abcdef22 ضربدر هستند و abcdef33 یک دایره است.
Abcdef12 و abcdef22 ضربدر هستند و abcdef32 یک دایره است.

از این رو ما می‌توانیم ابر مکعب ۶ بعدی $w_{3}^{6}$ را با توجه به حالت‌های بالا به ۶ دسته تقسیم بندی کنیم.(اگر یک عضو از چند دسته پیروی کند می‌توانیم یک حالت قرار دادی در نظر بگیریم مثلاً بالاترین دسته در دسته بندی بالا). حال هفت عضو ۱۱۱۱۱۱، ۱۱۱۱۱۲ ،۱۱۱۱۲۲، ۱۱۱۲۲۲، ۱۱۲۲۲۲، ۱۲۲۲۲۲ ،۲۲۲۲۲۲ را در $w_{3}^{6}$ در نظر بگیرید. طبق قضیه لانه کبوتری ۲ تا از این عضوها باید در یک دسته قرار بگیرند. برای مثال فرض کنید ۱۱۱۱۱۲ و ۱۱۲۲۲۲ در یک دسته قرار بگیرند، پس ۱۱۱۱۱۲۱۱، ۱۱۱۱۱۲۲۲، ۱۱۲۲۲۲۱۱، ۱۱۲۲۲۲۲۲ دارای علامت ضربدر و ۱۱۱۱۱۲۳۳، ۱۱۲۲۲۲۳۳ دارای علامت دایره هستند. اما حال، حالت ۱۱۳۳۳۲۳۳، که باید یا با دایره یا با ضربدر پر شود را در نظر می‌گیریم اگر با ضربدر پر شود، پس خط ترکیبیاتی 11xxx2xx کاملاً با ضربدر پر می‌شود که با فرض ما در تضاد است. برعکس اگر با دایره پر شود خط ترکیبیاتی کاملاً با دایره پر شده‌است که دو باره با فرض ما در تضاد است. این وضعیت برای هر یک از دو عضو از هفت عضو بالا از $w_{3}^{6}$ که در یک دسته مشابه قرار گیرند مشابه است. از آن جهت که ما برای همه دسته‌ها تضاد داریم، پس فرض اولیه ما غلط بوده، پس باید حداقل یک خط ترکیبیاتی وجود داشته باشد که کاملاً از دایره یا ضربدر تشکیل شده باشد.

بحث بالا به گونه‌ای یک کار بی‌فایده بود، در حقیقت این قضیه برای $H=4$ نیز برقرار است.^[۲] اگر کسی بحث بالا را برای مقادیر عمومی $n$ و $c$ گسترش دهد، $H$ به سرعت رشد خواهد کرد، حتی زمانی که $c=2$ است (که به ۲ بازیکن بازی ایکس او بر می‌گردد) $H$ ای که از روابط بالا محاسبه شود حتی سریع تر از تابع اکرمن $H$ رشد خواهد کرد. اولین کران به دست آمده از $H$ مربوط به Saharon Shelah^[۳] است، که با استفاده از توابع اصلی بازگشتی به دست آمد، و همچنان، در حالت کلی، بهترین کران برای عدد هالس-جووت، $H=h(n,c)$ می‌باشد.

ارتباط با دیگر قضایا

دقت کنید که استدلال بالا نتیجهٔ روبه رو را نیز می‌دهد :اگر فرض کنیم که $A$ مجموعه تمام اعداد ۸ رقمی با ارقام ۱٬۲،۳ باشد،(برای مثال A شامل ۱۱۳۳۳۲۳۳ نیز می‌باشد) اگر مجموعهٔ $A$ را با دو رنگ، رنگ کنیم، دنباله‌ای حسابی به طول ۳ وجود دارد که همهٔ اعضای آن یک رنگ هستند، چرا که تمام خطوط ترکیبیاتی که در اثبات قضیه هیلز–جووت ظاهر می‌شوند، دنبالهٔ حسابی نیز هستند. با حالت کلی تر این استدلال، می‌توان نشان داد که قضیه هیلز–جووت ،قضیهٔ ون در واردن را تعمیم می‌دهد! در واقع، قضیهٔ هیلز-جووت ذاتاً قضیه‌ای قوی تر است!

همچنین قضیهٔ هیلز-جووت نسخهٔ قوی تری نیز در مبحث چگالی دارد^[۴] که درقضیهٔ سمردی مطرح می‌شود، در این نسخهٔ قوی تر شده، به جای رنگ کردن ابر مکعب با $c$ رنگ، ابر مکعب $W_{n}^{H}$ و زیر مجموعه‌ای از آن به اسم $A$ با چگالی δ بین صفر و یک داده شده‌است، این قضیه می‌گوید که برای $H$ به اندازهٔ کافی بزرگ، که وابسته به $n$ وδ است، مجموعهٔ $A$ باید شامل یک خط ترکیبیاتی باشد به طوری که کل اعضای این خط در $A$ قرار دارند. شماره‌ای از مجلهٔ نیویورک تایمز که در تاریخ ۱۳ دسامبر ۲۰۰۹ منتشر شد از پروژه‌ای گزارش داد که توسط آقای Timothy Gowers، استاد دانشگاه کمبریج و دارندهٔ مدال فیلدز، انجام شد. این پروژه شامل اثبات آسان تری از قضیه هیلز–جووت در صورت چگالی این قضیه بود. این مقاله با نام مستعار D.H.J. Polymath منتشر شد.(اینجا را ببینید: http://arxiv.org/abs/0910.3926)

پیوند به بیرون

منابع

↑ Alfred W. Hales, Robert Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229.
↑ Neil Hindman, Eric Tressler, The first nontrivial Hales-Jewett number is four, to appear in Ars Combinatoria.
↑ Saharon Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), 683–697.
↑ Hillel Furstenberg, Yitzhak Katznelson, A density version of the Hales–Jewett theorem, J. d'Analyse Math. 57 (1991), 64–119.

[1] Alfred W. Hales, Robert Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229.

[2] Neil Hindman, Eric Tressler, The first nontrivial Hales-Jewett number is four, to appear in Ars Combinatoria.

[3] Saharon Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), 683–697.

[4] Hillel Furstenberg, Yitzhak Katznelson, A density version of the Hales–Jewett theorem, J. d'Analyse Math. 57 (1991), 64–119.

[۱]

[۲]

[۳]

[۴]