Furstenberg – Sarkozi teoremasi - Furstenberg–Sárközy theorem

The Furstenberg – Sarkozi teoremasi natijasi qo'shimchalar soni nazariyasi ikkitasi kvadrat bilan farq qilmaydigan raqamlar to'plamida. Unda, agar ${ displaystyle S}$ to'plamidir natural sonlar ikkita raqam bo'lmagan xususiyat bilan ${ displaystyle S}$ a bilan farq qiladi kvadrat raqam, keyin tabiiy zichlik ning ${ displaystyle S}$ nolga teng. Ya'ni, har bir kishi uchun ${ displaystyle varepsilon> 0}$va barchasi etarlicha katta ${ displaystyle n}$, raqamlarning qismigacha bo'lgan qismi ${ displaystyle n}$ ular ichida ${ displaystyle S}$ dan kam ${ displaystyle varepsilon}$. Bunga teng ravishda, musbat yuqori zichlikka ega bo'lgan har bir tabiiy sonlar to'plami farqi kvadratga teng bo'lgan ikkita sonni o'z ichiga oladi (va shunday kuchli juftlik cheksiz ko'p).^[1] Teorema nomlangan Xill Furstenberg va András Sárközy, 1970-yillarning oxirlarida kim buni isbotladi.

Misol

Kvadrat farqlari bo'lmagan to'plamga misol, ning o'yinida paydo bo'ladi kvadratni olib tashlash tomonidan ixtiro qilingan Richard A. Epstein va birinchi tomonidan tasvirlangan Sulaymon V. Golomb. Ushbu o'yinda ikki o'yinchi navbatma-navbat to'plangan tangalardan tangalarni olib tashlashadi; oxirgi tangani olib tashlagan o'yinchi g'alaba qozonadi. Har bir burilishda o'yinchi qoziqdan faqat nolga teng kvadrat sonli tangalarni olib tashlashi mumkin.^[2] Ushbu o'yindagi har qanday pozitsiyani butun son bilan, uning tangalar soni bilan tasvirlash mumkin, manfiy bo'lmagan sonlarni "sovuq" holatga bo'lish mumkin, u erda harakatlanayotgan o'yinchi yutqazmoqda va "issiq" pozitsiyalar, harakat qilmoqchi bo'lgan o'yinchi sovuq holatga o'tish orqali g'alaba qozonishi mumkin. Ikkala sovuq pozitsiyani kvadrat bilan farqlash mumkin emas, chunki agar ular shunday bo'lsa, ikkala pozitsiyaning kattasi bilan duch kelgan o'yinchi kichikroq joyga o'tib g'alaba qozonishi mumkin edi. Shunday qilib, sovuq pozitsiyalar kvadrat farqi bo'lmagan to'plamni hosil qiladi:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44,… (ketma-ketlik A030193 ichida OEIS )

Ushbu pozitsiyalar a tomonidan yaratilishi mumkin ochko'zlik algoritmi unda sovuq pozitsiyalar raqamli tartibda hosil qilinadi, har bir qadamda ilgari tanlangan har qanday raqam bilan kvadrat farqi bo'lmagan eng kichik raqam tanlanadi.^[2][3] Golomb kuzatganidek, sovuq pozitsiyalar cheksizdir va ko'proq sovuq pozitsiyalar soni ${ displaystyle n}$ hech bo'lmaganda mutanosibdir ${ displaystyle { sqrt {n}}}$. Agar sovuq pozitsiyalar kamroq bo'lsa, har bir issiq pozitsiyaga yutuqli harakatni ta'minlash uchun ular etarli bo'lmas edi.^[2]Furstenberg-Sarkozi teoremasi shuni ko'rsatadiki, sovuq holat issiq holatga qaraganda kamroq: har biri uchun ${ displaystyle varepsilon> 0}$va barchasi etarlicha katta ${ displaystyle n}$, gacha bo'lgan sovuq pozitsiyalarning nisbati ${ displaystyle n}$ ko'pi bilan ${ displaystyle varepsilon}$. Ya'ni, 1 dan oralig'ida boshlang'ich pozitsiyasiga duch kelganda ${ displaystyle n}$, ushbu pozitsiyalarning ko'pchiligida birinchi o'yinchi g'alaba qozonishi mumkin.^[4]Raqamli dalillar shuni ko'rsatadiki, sovuq pozitsiyalarning haqiqiy soni ${ displaystyle n}$ taxminan ${ displaystyle n ^ {0.7}}$.^[5]

Yuqori chegaralar

Furstenberg-Sarkozi teoremasi taxmin qilingan Laslo Lovásh va 1970-yillarning oxirlarida mustaqil ravishda isbotlangan Xill Furstenberg va András Sárközy, uning nomi bilan nomlangan.^[6][7] Ularning ishidan boshlab, xuddi shu natijalarning bir nechta boshqa dalillari nashr etildi, odatda avvalgi dalillarni soddalashtiradilar yoki kvadrat farqlarsiz to'plamning qanchalik kam bo'lishi kerakligi chegaralarini kuchaytiradilar.^[8][9][10] Xususan, endi ma'lumki, kvadrat farqlarsiz to'plam ko'pi bilan o'z ichiga olishi mumkin

${ displaystyle O (n / ( log n) ^ {{ frac {1} {4}} log log log log n})}$

dan butun sonlar ${ displaystyle 0}$ ga ${ displaystyle n}$, ifoda etilganidek katta O yozuvlari.^[11]

Ushbu dalillarning ko'pchiligidan foydalaniladi Furye tahlili yoki ergodik nazariya. Biroq, bu har bir kvadrat farqsiz to'plam nol zichlikka ega ekanligini teoremaning asosiy shaklini isbotlash uchun zarur emas.^[10]

Pastki chegaralar

Pol Erdos har bir kvadrat farqsiz to'plamga ega deb taxmin qilmoqda

${ displaystyle O (n ^ {1/2} log ^ {k} n)}$

gacha bo'lgan elementlar ${ displaystyle n}$, ba'zi bir doimiy uchun ${ displaystyle k}$, ammo buni Sarkozi rad etdi, u zichroq ketma-ketliklar mavjudligini isbotladi. Sarkozy Erdo'zning gumonini zaiflashtirdi, shunda hammasi uchun ${ displaystyle varepsilon> 0}$, har bir kvadrat farqsiz to'plamga ega

${ displaystyle O (n ^ {1/2 + varepsilon})}$

gacha bo'lgan elementlar ${ displaystyle n}$.^[12] Bu, o'z navbatida, rad etildi Imre Z. Ruzsa, kim kvadratgacha farqsiz to'plamlarni topdi

${ displaystyle Omega chap (n ^ {(1+ log _ {65} 7) / 2} o'ng) taxminan n ^ {0.733077}}$

elementlar.^[13]

Ruzsa qurilishi a ni tanlaydi kvadratsiz butun son ${ displaystyle b}$ sifatida radix bazaning-${ displaystyle b}$ butun sonlar uchun yozuv, masalan, katta to'plam mavjud ${ displaystyle R}$ dan raqamlar ${ displaystyle 0}$ ga ${ displaystyle b-1}$ ularning birortasi ham kvadratchalar modulli emas ${ displaystyle b}$. Keyin u kvadrat farqlarsiz to'plamini bazada joylashgan raqamlar sifatida tanlaydi.${ displaystyle b}$ yozuvlari, a'zolari bor ${ displaystyle R}$ ularning juft raqamli pozitsiyalarida. Ushbu raqamlarning toq holatidagi raqamlar o'zboshimchalik bilan bo'lishi mumkin. Ruzsa etti elementli to'plamni topdi ${ displaystyle R = {0,15,21,27,42,48,59 }}$ modul ${ displaystyle b = 65}$Shunday qilib, Ruzsa qurilishi boshqa asos yordamida yaxshilandi, ${ displaystyle b = 205}$, o'lchamlari bilan kvadrat farqlarsiz to'plamlarni berish

${ displaystyle Omega chap (n ^ {(1+ log _ {205} 12) / 2} o'ng) taxminan n ^ {0.733412}.}$^[14][15]

Baza uchun qo'llanilganda ${ displaystyle b = 2}$, xuddi shu qurilish Mozer-de-Bruyn ketma-ketligi Furstenberg - Sarkozy teoremasida noan'anaviy pastki chegaralarni ta'minlash uchun juda kam, ammo boshqa matematik xususiyatlarga ega kvadratik farqsiz to'plam.^[16]

Matematikada hal qilinmagan muammo: Ko'rsatkich mavjudmi? ${ displaystyle c <1}$ har bir kvadrat farqsiz kichik to'plami ${ displaystyle [0, n]}$ bor ${ displaystyle O (n ^ {c})}$ elementlarmi? (matematikada ko'proq hal qilinmagan muammolar)

Ushbu natijalarga asoslanib, har bir kishi uchun taxmin qilingan ${ displaystyle varepsilon> 0}$va har biri etarlicha katta ${ displaystyle n}$ dan raqamlarning kvadrat farqsiz kichik to'plamlari mavjud ${ displaystyle 0}$ ga ${ displaystyle n}$ bilan ${ displaystyle Omega (n ^ {1- varepsilon})}$ elementlar. Ya'ni, agar bu taxmin to'g'ri bo'lsa, Furstenberg - Sarkozy teoremasi uchun yuqori chegaradagi ko'rsatkichni tushirish mumkin emas.^[9]Shu bilan bir qatorda, 3/4 ko'rsatkichi "Ruzsa qurilishining tabiiy chegarasi" va ushbu to'plamlarning haqiqiy maksimal o'sish sur'ati uchun yana bir nomzod sifatida aniqlandi.^[17]

Boshqa polinomlarga umumlashtirish

Furstenberg - Sarkozi teoremasining yuqori chegarasi kvadrat farqlardan saqlanadigan to'plamlardan farqlarni oldini oladigan to'plamlarga umumlashtirilishi mumkin. ${ displaystyle p ( mathbb {N})}$, polinomning butun sonlaridagi qiymatlar ${ displaystyle p}$ ning qiymatlari ekan, butun son koeffitsientlari bilan ${ displaystyle p}$ har qanday sonning butun soniga ko'paytmani o'z ichiga oladi.Bu natija uchun ko'p sonli shart shart, chunki agar butun son bo'lsa ${ displaystyle k}$ ko'paytmalari ko'rinmaydi ${ displaystyle p ( mathbb {N})}$, keyin ko'paytmalari ${ displaystyle k}$ farqlari bo'lmagan nolga teng bo'lmagan zichlik to'plamini hosil qiladi ${ displaystyle p ( mathbb {N})}$.^[18]

Adabiyotlar