بزرگ‌ترین مبلغی که نمی‌توان پرداخت، اکنون با کرانی تنگ

صندوقی را تصور کنید که تنها چند نوع سکه را، با موجودی نامحدود، می‌پذیرد و هرگز پول خرد پس نمی‌دهد. برخی مبلغ‌ها را می‌توان دقیقاً پرداخت؛ برخی دیگر را هرگز. ریاضی‌دانان ارزش‌های سکه را مولد (generator) می‌نامند و پرسشی به ظاهر ساده می‌پرسند: بزرگ‌ترین مبلغی که نمی‌توان پرداخت چیست؟

مبلغ‌هایی که هرگز نمی‌توان پرداخت

اعداد صحیح a₁ < a₂ < … < aₙ را بردارید، به‌طوری که هیچ مقسوم‌علیهی میان همه‌شان مشترک نباشد. مجموعی که از جمع کردن این اعداد، هر کدام هر چند بار که بخواهید، به دست آید «نمایش‌پذیر» است. تنها تعداد متناهی از اعداد صحیح نمایش‌پذیر نیستند؛ بزرگ‌ترین آن‌ها عدد فروبنیوس (Frobenius number)، F، است. (اگر یکی از ارزش‌ها 1 باشد، همه چیز را می‌توان پرداخت و F را برابر −1 می‌گیرند.)

مثالی کوچک: با سکه‌های 3، 4 و 6 می‌توانید 3، 4، 6، 7، 8 و هر مبلغ پس از آن را بپردازید، اما هرگز 1، 2 یا 5 را. پس F = 5. توجه کنید که 3 و 6 مقسوم‌علیه مشترکی دارند؛ آنچه اهمیت دارد این است که هیچ مقسوم‌علیهی میان هر سه مشترک نباشد.

برای دو سکه پاسخی دقیق وجود دارد، فرمول سیلوستر (Sylvester): F(a₁, a₂) = a₁a₂ − a₁ − a₂. برای سه سکه یا بیشتر، کار عبارت است از کران‌دار کردن F: اثبات اینکه از مقداری که از روی سکه‌ها محاسبه می‌شود تجاوز نمی‌کند.

ضریب 2 سرسخت

پل اردوش (Paul Erdős) و رونالد گراهام (Ronald Graham) برای سه مولد یا بیشتر ثابت کردند:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

در اینجا aₙ بزرگ‌ترین ارزش است، aₙ₋₁ دومین بزرگ‌ترین، n تعداد ارزش‌ها، و ⌊ ⌋ به معنای گرد کردن به پایین است. این کران، مانند فرمول سیلوستر، دو سکهٔ بزرگ‌تر را در بر دارد.

آن‌ها همچنین بدترین حالت را برآورد کردند، یعنی بزرگ‌ترین F ممکن وقتی همهٔ n ارزش حداکثر t باشند. شکاف میان برآوردهایشان، تقریباً یک ضریب 2، به حدسی انجامید که با عنوان مسئلهٔ اردوش شمارهٔ 433 (Erdős Problem #433) ثبت شده است. ژاک دیکسمیه (Jacques Dixmier) آن را حل کرد و همچنین کران ساده‌تری را ثابت کرد که برای هر مجموعه‌ای برقرار است: F ≤ aₙ²/(n − 1). ضریب 2 از میان رفته، اما دومین سکهٔ بزرگ هم.

نگه داشتن هر دو سکهٔ بزرگ‌تر

لین چن (Lin Chen)، تینگ‌وِی هو (Tingwei Hu)، یوچن مائو (Yuchen Mao) و گوئوچوان ژانگ (Guochuan Zhang)، از دانشکدهٔ علوم و فناوری رایانهٔ دانشگاه ژجیانگ، هر دو را می‌خواستند: بی‌ضریب 2، و با نگه داشتن دومین سکهٔ بزرگ. پاسخ آن‌ها، که برای هر مجموعه‌ای با دو ارزش یا بیشتر برقرار است:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

در اینجا ⌈ ⌉ به معنای گرد کردن به بالا است. در مقایسه با اردوش و گراهام، ضریب 2 ناپدید شده است، به بهای تقسیم بر n − 1 به جای n و گرد کردن به بالا. در مقایسه با دیکسمیه، کران تازه وقتی دومین سکهٔ بزرگ در کنار بزرگ‌ترین سکه کوچک باشد، می‌تواند به‌طور چشمگیری کوچک‌تر باشد.

در مثال 3، 4، 6، کران اردوش و گراهام 10 می‌دهد، کران دیکسمیه 18، و کران تازه 4 × 3 − 6 − 1 = 5، دقیقاً مقدار واقعی. جای شگفتی ندارد: این مجموعه به خانوادهٔ حالت‌های حدی‌ای تعلق دارد که در ادامه توصیف می‌شوند و طوری ساخته شده‌اند که دقیقاً به کران برسند؛ مقاله هیچ مقایسه‌ای روی مجموعه‌های معمولی ارائه نمی‌دهد.

مرتب کردن مبلغ‌ها بر اساس باقی‌مانده

اثبات راه اردوش و گراهام را دنبال می‌کند. هر مبلغ را بر اساس باقی‌ماندهٔ آن پس از تقسیم بر بزرگ‌ترین سکه، aₙ، دسته‌بندی کنید. وقتی مجموعی از سکه‌های کوچک‌تر به یک باقی‌ماندهٔ معین برسد، افزودن نسخه‌هایی از aₙ به هر مبلغ بزرگ‌تر با همان باقی‌مانده می‌رسد. کار این است که نشان دهیم به هر باقی‌مانده‌ای می‌توان با هزینهٔ کم رسید.

ابزار کلیدی قضیهٔ کنزر (Kneser) است، دربارهٔ اینکه یک مجموعه از مجموع‌ها باید چقدر بزرگ باشد. اردوش و گراهام از آن استفاده کردند تا نشان دهند مجموع‌هایی از حدود aₙ/n سکه بیش از نیمی از باقی‌مانده‌ها را پوشش می‌دهند، سپس آن را دو برابر کردند تا همه را بپوشانند. ارزش هر سکه در این مجموع‌ها حداکثر aₙ₋₁ است، پس دو برابر کردن تعداد سکه‌ها هزینه را دو برابر می‌کند: ضریب 2 از همین‌جا می‌آید.

اثبات تازه از مجموع‌هایی با ⌈aₙ/(n − 1)⌉ سکه استفاده می‌کند. وقتی این مجموع‌ها برخی باقی‌مانده‌ها را از دست می‌دهند، قضیهٔ کنزر می‌گوید باقی‌مانده‌های جاافتاده به‌طور تصادفی پراکنده نیستند: خانواده‌هایی کامل از باقی‌مانده‌ها را تشکیل می‌دهند که در فاصله‌های منظم از هم قرار دارند. هرچه خانواده‌های بیشتری جا افتاده باشند، سکه‌های کوچک‌تر بیشتری باید در هر خانواده‌ای که به آن رسیده‌ایم جمع شوند، پس هر یک از این خانواده‌ها چند سکهٔ کوچک در خود دارد، و معدود سکه‌های اضافیِ لازم برای رسیدن به خانواده‌های جاافتاده ارزان‌اند. مجموع هرگز از ⌈aₙ/(n − 1)⌉ × aₙ₋₁ تجاوز نمی‌کند.

این گام نخست کران را بدون «− 1» پایانی‌اش به دست می‌دهد. آخرین واحد از استدلالی جداگانه می‌آید که بر قضیه‌ای از شِرک (Scherk) و کمپرمن (Kemperman) دربارهٔ مجموع‌هایی که تنها به یک شیوه ساخته می‌شوند استوار است: این استدلال نشان می‌دهد که خود مبلغ مرزیِ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ همیشه پرداختنی است. بنا بر بخش قدردانی، نویسندگان نخست کران ضعیف‌تر را ثابت کردند؛ سپس GPT-6 به یافتن استدلالی که آن را یک واحد پایین می‌آورد کمک کرد، و همچنین در اثبات اینکه کران را نمی‌توان پایین‌تر آورد و در ویرایش متن انگلیسی یاری داد. نویسندگان اعلام می‌کنند که مسئولیت دست‌نوشتهٔ نهایی را بر عهده می‌گیرند.

حالت‌هایی که دقیقاً به حد می‌رسند

این کران را نمی‌توان پایین‌تر آورد: برای هر n ≥ 3، نویسندگان بی‌نهایت مجموعه می‌سازند که F در آن‌ها دقیقاً برابر کران است. هر q ≥ 2 را بردارید و ارزش‌های q، 2q، …، (n − 1)q را، به‌علاوهٔ (n − 2)q + 1. همه جز یکی مضرب q هستند، پس هیچ مبلغی را نمی‌پردازند که q به‌تنهایی نتواند. این مجموعه مانند دو سکه، q و (n − 2)q + 1، رفتار می‌کند و فرمول سیلوستر F را به دست می‌دهد که دقیقاً با کران تازه یکی است. با n = 3 و q = 3، این دستور دقیقاً همان مثال 3، 4، 6 بالا را می‌سازد.

سکه‌های کمتر، سقفی پایین‌تر

این کران را می‌توان بر حسب چگالی هم خواند. برای هر مجموعهٔ کاهش‌یافته‌ای که از i ارزش کوچک‌تر به‌علاوهٔ بزرگ‌ترین ارزش ساخته شده باشد کاربرد دارد، به شرطی که این ارزش‌ها همچنان هیچ مقسوم‌علیه مشترکی نداشته باشند. حذف سکه‌ها تنها می‌تواند پرداخت را دشوارتر کند، پس سقفی که برای مجموعهٔ کاهش‌یافته ثابت شده برای مجموعهٔ کامل هم برقرار است. آنچه نتیجه را کنترل می‌کند تقریباً aᵢ/i است، یعنی وارون اینکه i ارزش نخست اعداد 1 تا aᵢ را با چه تراکمی پر می‌کنند: متراکم‌ترین گروه برنده است. به‌ویژه، به گفتهٔ نویسندگان، هرگاه سکه‌های باقی‌مانده همچنان هیچ مقسوم‌علیهی میان همه‌شان مشترک نداشته باشند، می‌توان دومین سکهٔ بزرگ را به‌سادگی کنار گذاشت.

مقاله کاملاً نظری می‌ماند: هیچ عددی دربارهٔ اینکه کران تازه روی مجموعه‌های معمولی سکه چقدر کوچک‌تر است ارائه نمی‌دهد، و تنگ بودن آن تنها برای سه ارزش سکه یا بیشتر ثابت شده است.