Anatoliy Karatsuba - Anatoly Karatsuba

Anatoliy Alekseyevich Karatsuba
Tug'ilgan	(1937-01-31)1937 yil 31-yanvar Grozniy, Sovet Ittifoqi
O'ldi	2008 yil 28 sentyabr(2008-09-28) (71 yosh) Moskva, Rossiya
Millati	Ruscha
Olma mater	Moskva davlat universiteti
Ilmiy martaba
Maydonlar	Matematik

Anatoliy Alekseyevich Karatsuba (uning ismi ko'pincha yozilgan Anatoliy) (Ruscha: Anatóliy Alekseevich Karatsuba; Grozniy, Sovet Ittifoqi, 1937 yil 31-yanvar - Moskva, Rossiya, 2008 yil 28 sentyabr^[1]) edi a Ruscha matematik sohasida ishlash analitik sonlar nazariyasi, p- oddiy raqamlar va Dirichlet seriyasi.

Talabalik va kasbiy hayotining aksariyat qismida u bilan bog'liq edi Mexanika va matematika fakulteti ning Moskva davlat universiteti, himoya a D.Sc. 1966 yilda "trigonometrik yig'indilar usuli va oraliq qiymat teoremalari" deb nomlangan.^[2] Keyinchalik u Steklov nomidagi Matematika instituti ning Fanlar akademiyasi.^[2]

Uning darsligi Asoslari Analitik sonlar nazariyasi 1975 va 1983 yillarda ikkita nashrga chiqdi.^[2]

The Karatsuba algoritmi eng qadimgi algoritmni ajratish va yutish uchun ko'paytirish va sifatida yashaydi maxsus ish uning to'g'ridan-to'g'ri umumlashtirilishi, Toom-Cook algoritmi.^[3]

Anatoliy Karatsubaning asosiy tadqiqot ishlari 160 dan ortiq ilmiy ishlar va monografiyalarda nashr etilgan.^[4]

Uning qizi, Yekaterina Karatsuba, shuningdek, matematik FEE usuli.

Mukofotlar va unvonlar

• 1981: Sovet Fanlar Akademiyasining P.L.Tchebyshev mukofoti
• 1999: Rossiyaning taniqli olimi
• 2001: Rossiya Fanlar akademiyasining I.M.Vinogradov mukofoti

Dastlabki informatika bo'yicha ishlar

Lomonosov nomidagi Moskva davlat universiteti talabasi sifatida Karatsuba seminarda qatnashgan Andrey Kolmogorov va Kolmogorov tomonidan o'rnatilgan ikkita muammoga echim topdi. Bu avtomatika nazariyasini ishlab chiqish uchun juda zarur edi va tezkor algoritmlar nazariyasining yangi matematikasini boshladi.

Avtomatlar

Ning qog'ozida Edvard F. Mur,^[5] ${displaystyle (n; m; p)}$avtomat (yoki mashina) ${displaystyle S}$, bilan moslama sifatida belgilanadi ${displaystyle n}$ davlatlar, ${displaystyle m}$ kirish belgilari va ${displaystyle p}$ chiqish belgilari. Tuzilishi bo'yicha to'qqiz teorema ${displaystyle S}$ va bilan tajribalar ${displaystyle S}$ isbotlangan. Keyinchalik bunday ${displaystyle S}$ mashinalar nomini oldi Mur mashinalari. Maqolaning oxirida «Yangi muammolar» bobida Mur 8 va 9-teoremalarda olgan baholarini takomillashtirish masalasini quyidagicha bayon qildi:

Teorema 8 (Mur). O'zboshimchalik bilan berilgan ${displaystyle (n; m; p)}$ mashina ${displaystyle S}$Shunday qilib, har ikki holatni bir-biridan ajratish mumkin, uzunlik tajribasi mavjud ${displaystyle n (n-1) / 2}$ holatini aniqlaydigan ${displaystyle S}$ ushbu tajriba oxirida.

1957 yilda Karatsuba o'zining ikkita teoremasini isbotladi, ular Mur muammosini to'liq echib oldilar. Teorema 8.

Teorema A (Karatsuba). Agar ${displaystyle S}$ a ${displaystyle (n; m; p)}$ Shunday qilib, har ikkala holatni bir-biridan ajratib turadigan qilib, maksimal uzunlikdagi kengaytirilgan tajriba mavjud ${displaystyle (n-1) (n-2) / 2 + 1}$, uning yordamida davlatni topish mumkin ${displaystyle S}$ tajriba oxirida.

Teorema B (Karatsuba). Mavjud a ${displaystyle (n; m; p)}$ har bir holatini bir-biridan farqlash mumkin bo'lgan mashina, shunda tajriba oxirida mashina holatini topadigan eng qisqa tajribaning uzunligi ${displaystyle (n-1) (n-2) / 2 + 1}$.

Ushbu ikki teoremani Karatsuba o'zining 4-kursida o'zining 4-yillik loyihasi asosida isbotladi; tegishli hujjat 1958 yil 17 dekabrda "Uspekhi Mat. Nauk" jurnaliga topshirilgan va 1960 yil iyun oyida nashr etilgan.^[6] Keyinchalik "Mur-Karatsuba teoremasi" unvoniga sazovor bo'lgan Karatsubaning shu kungacha (2011 y.) Natijasi avtomatika nazariyasida ham aniq (bahoning yagona aniq chiziqli bo'lmagan tartibi) natija bo'lib qolmoqda. hisoblashlarning murakkabligi nazariyasining o'xshash masalalarida.

Raqamlar nazariyasida ishlaydi

A.A.Karatsubaning asosiy tadqiqot ishlari 160 dan ortiq ilmiy ishlar va monografiyalarda nashr etilgan.^{[7][8][9][10]}

The p-adik usul

A.A.Karatsuba yangisini qurdi ${displaystyle p}$-trigonometrik yig’indilar nazariyasidagi usul.^[11] Deb nomlangan taxminlar ${displaystyle L}$- shaklning yig'indisi

${displaystyle S = sum _ {x = 1} ^ {P} e ^ {2pi i (a_ {1} x / p ^ {n} + nuqta a_ {n} x ^ {n} / p)}, to'rtinchi ( a_ {s}, p) = 1, to'rtlik 1leq sleq n,}$

LED^[12] Dirichlet nollari uchun yangi chegaralarga ${displaystyle L}$- asosiy sonning kuchini modul bilan seriyaning mos keladigan sonining assimtotik formulasiga seriya qiladi.

${displaystyle x_ {1} ^ {n} + nuqta + x_ {t} ^ {n} ekviv N {pmod {p ^ {k}}}, to'rtlik 1leq x_ {s} leq P, to'rtlik 1leq sleq n, to'rtinchi P$

butun koeffitsientlar bilan modulli polinomning kasr qismlarini taqsimlash masalasini hal qilish uchun ${displaystyle p ^ {k}}$. A.A. Buni birinchi bo'lib Karatsuba tushundi^[13] ichida ${displaystyle p}$- Eyler-Vinogradovning "joylashtirish printsipi" ni shakllantirish va hisoblash uchun a ${displaystyle p}$- Vinogradovning odatiy analogi ${displaystyle u}$- Waring turiga mos keladigan echimlar sonini hisoblashda raqamlar.

Faraz qiling: ${displaystyle x_ {1} ^ {n} + nuqta + x_ {t} ^ {n} ekviv N {pmod {Q}}, to'rtlik 1leq x_ {s} leq P, to'rtlik 1leq sleq t, quad (1)}$ va bundan tashqari: ${displaystyle P ^ {r} leq Q$

qayerda ${displaystyle p}$ asosiy son. Karatsuba har qanday natural son uchun buni isbotladi ${displaystyle ngeq 144}$ mavjud a ${displaystyle p_ {0} = p_ {0} (n)}$ har qanday kishi uchun ${displaystyle p_ {0}> p_ {0} (n)}$ har bir tabiiy son ${displaystyle N}$ formasida (1) ifodalanishi mumkin ${displaystyle tgeq 20r + 1}$va uchun ${displaystyle t$ bor ${displaystyle N}$ shuning uchun (1) muvofiqlik echimlarga ega emas.

Karatsuba tomonidan topilgan ushbu yangi yondashuv yangisini keltirib chiqardi ${displaystyle p}$- ning asosli isboti Vinogradov o'rtacha qiymat teoremasi, bu Vinogradovning trigonometrik yig'indilar usulida markaziy rol o'ynaydi.

Ning yana bir tarkibiy qismi ${displaystyle p}$- A.A.ning uslubiy usuli Karatsuba - bu mahalliy hisobidan to'liq bo'lmagan tenglamalar tizimidan to'liq tizimlarga o'tish ${displaystyle p}$- noma'lum narsalarning tubdan o'zgarishi.^[14]

Ruxsat bering ${displaystyle r}$ o'zboshimchalik bilan tabiiy son bo'lishi, ${displaystyle 1leq rleq n}$. Butun sonni aniqlang ${displaystyle t}$ tengsizliklar bo'yicha ${displaystyle m_ {t} leq rleq m_ {t + 1}}$. Tenglamalar tizimini ko'rib chiqing

${displaystyle {egin {case} x_ {1} ^ {m_ {1}} + nuqta + x_ {k} ^ {m_ {1}} = y_ {1} ^ {m_ {1}} + nuqta + y_ {k } ^ {m_ {1}} nuqta nuqta nuqta nuqta nuqta nuqta nuqta nuqta x_ {1} ^ {m_ {s}} + nuqta + x_ {k} ^ {m_ {s}} = y_ {1} ^ { m_ {s}} + nuqta + y_ {k} ^ {m_ {s}} x_ {1} ^ {n} + nuqta + x_ {k} ^ {n} = y_ {1} ^ {n} + nuqta + y_ {k} ^ {n} end {case}}}$

${displaystyle 1leq x_ {1}, nuqta, x_ {k}, y_ {1}, nuqta, y_ {k} leq P, to'rtlik 1leq m_ {1}$

Karatsuba echimlar sonini isbotladi ${displaystyle I_ {k}}$ uchun tenglamalar tizimining ${displaystyle kgeq 6rnlog n}$ smetani qondiradi

${displaystyle I_ {k} ll P ^ {2k-delta}, to'rtburchak delta = m_ {1} + nuqta + m_ {t} + (s-t + 1) r.}$

O'zgaruvchilar kichik tub bo'linadigan raqamlar bo'ylab harakatlanadigan to'liq bo'lmagan tenglamalar tizimlari uchun Karatsuba o'zgaruvchilarning multiplikativ tarjimasini qo'llagan. Bu trigonometrik yig'indilarning mohiyatan yangi bahosiga va bunday tenglamalar tizimlari uchun o'rtacha qiymat teoremasiga olib keldi.

Terri muammosidagi birlik integralining konvergentsiya ko'rsatkichi bo'yicha Xua Luogeng muammosi

${displaystyle p}$- A.A.Karatsubaning uslubiy usuli funktsiyalarning kichik qiymatlari bilan nuqtalar to'plamining o'lchovini ularning parametrlari (koeffitsientlari va boshqalar) qiymatlari bo'yicha baholash texnikasini va aksincha, ushbu parametrlarni ushbu to'plamning o'lchovi haqiqiy va ${displaystyle p}$-adik ko'rsatkichlar. Karatsuba uslubining bu tomoni trigonometrik integrallarni baholashda ayniqsa aniq namoyon bo'ldi, bu esa muammoning echimiga olib keldi. Xua Luogeng. 1979 yilda Karatsuba shogirdlari bilan birgalikda G.I. Arxipov va V.N. Chubarikov to'liq echimni oldi^[15] integralning yaqinlik ko'rsatkichini topish bo'yicha Xua Luogeng muammosidan:

${displaystyle vartheta _ {0} = int chegaralari _ {- infty} ^ {+ infty} cdots int chegaralari _ {- infty} ^ {+ infty} {iggl |} int chegaralari _ {0} ^ {1} e ^ { 2pi i (alfa _ {n} x ^ {n} + cdots + alfa _ {1} x)} dx {iggr |} ^ {2k} dalfa _ {n} ldots dalfa _ {1},}$

qayerda ${displaystyle ngeq 2}$ belgilangan raqam.

Bunday holda, yaqinlik ko'rsatkichi qiymatni anglatadi ${displaystyle gamma}$, shu kabi ${displaystyle vartheta _ {0}}$ uchun birlashadi ${displaystyle 2k> gamma + varepsilon}$ va uchun farq qiladi ${displaystyle 2k$, qayerda ${displaystyle varepsilon> 0}$ o'zboshimchalik bilan kichikdir. Bu ajralmas ekanligini ko'rsatdi ${displaystyle vartheta _ {0}}$ uchun birlashadi ${displaystyle 2k> {frac {1} {2}} (n ^ {2} + n) +1}$ va uchun farq qiladi ${displaystyle 2kleq {frac {1} {2}} (n ^ {2} + n) +1}$.

Shu bilan birga, integral uchun o'xshash muammo hal qilindi: ${displaystyle vartheta _ {1} = int _ {- infty} ^ {+ infty} cdots int _ {- infty} ^ {+ infty} {iggl |} int _ {0} ^ {1} e ^ {2pi i ( alfa _ {n} x ^ {n} + alfa _ {m} x ^ {m} + cdots + alfa _ {r} x ^ {r})} dx {iggr |} ^ {2k} dalfa _ {n} dalfa _ {m} ldots dalfa _ {r},}$ qayerda ${displaystyle n, m, ldots, r}$ shartlarni qondiradigan butun sonlar: ${displaystyle 1leq r$

Karatsuba va uning shogirdlari ajralmas ekanligini isbotladilar ${displaystyle vartheta _ {1}}$ yaqinlashadi, agar ${displaystyle 2k> n + m + ldots + r}$ va agar ajralib chiqsa ${displaystyle 2kleq n + m + ldots + r}$.

Integrallar ${displaystyle vartheta _ {0}}$ va ${displaystyle vartheta _ {1}}$ deb nomlangan narsalarni o'rganishda paydo bo'ladi Prouhet-Tarri-Escott muammosi. Karatsuba va uning shogirdlari Tarri muammosining ko'p o'lchovli analogi bilan bog'liq qator yangi natijalarga erishdilar. Xususan, ular buni isbotladilar ${displaystyle F}$ in polinomidir ${displaystyle r}$ o'zgaruvchilar (${displaystyle rgeq 2}$) shakli:${displaystyle F (x_ {1}, ldots, x_ {r}), =, yig'indining chegaralari _ {u _ {1} = 0} ^ {n_ {1}} cdots yig'indisining chegaralari _ {u _ {r} = 0 } ^ {n_ {r}} alfa (u _ {1}, ldots, u _ {r}) x_ {1} ^ {u _ {1}} ldots x_ {r} ^ {u _ {r}}, }$ nolli bepul muddat bilan, ${displaystyle m = (n_ {1} +1) ldots (n_ {r} +1) -1}$, ${displaystyle {ar {alpha}}}$ bo'ladi ${displaystyle m}$koeffitsientlaridan tashkil topgan o'lchovli vektor ${displaystyle F}$, keyin integral: ${displaystyle vartheta _ {2} = int chegaralari _ {- infty} ^ {+ infty} cdots int chegaralari _ {- infty} ^ {+ infty} {iggl |} int chegaralari _ {0} ^ {1} cdots int chegaralari _ {0} ^ {1} e ^ {2pi iF (x_ {1}, ldots, x_ {r})} dx_ {1} ldots dx_ {r} {iggr |} ^ {2k} d {ar {alfa} }}$ uchun birlashadi ${displaystyle 2k> mn}$, qayerda ${displaystyle n}$ raqamlarning eng yuqori ko'rsatkichidir ${displaystyle n_ {1}, ldots, n_ {r}}$. Natijada, yakuniy emas, trigonometrik integrallar nazariyasida konvergentsiya ko'rsatkichi chegaralarini takomillashtirish bilan bog'liq yangi maydon paydo bo'ldi. ${displaystyle vartheta _ {2}}$ (I. A. Ikromov, M. A. Chaxkiev va boshqalar).

Ko'p trigonometrik yig'indilar

1966—1980 yillarda Karatsuba rivojlandi^[16][17] (uning shogirdlari G.I. Arxipov va V.N. Chubarikov ishtirokida) ko'plik nazariyasi Hermann Veyl trigonometrik yig'indilar, ya'ni shaklning yig'indilari

${displaystyle S = S (A) = sum _ {x_ {1} = 1} ^ {P_ {1}} nuqta sum _ {x_ {r} = 1} ^ {P_ {r}} e ^ {2pi iF ( x_ {1}, nuqta, x_ {r})}}$ , qayerda ${displaystyle F (x_ {1}, nuqtalar, x_ {r}) = sum _ {t_ {1} = 1} ^ {n_ {1}} nuqtalar sum _ {t_ {r} = 1} ^ {n_ {r }} alfa (t_ {1}, nuqtalar, t_ {r}) x_ {1} ^ {t_ {1}} x_ {r} ^ {t_ {r}}}$ ,

${displaystyle A}$ haqiqiy koeffitsientlar tizimidir ${displaystyle alfa (t_ {1}, nuqtalar, t_ {r})}$. Ushbu nazariyaning markaziy nuqtasi, xuddi Vinogradov trigonometrik yig'indilari nazariyasida bo'lgani kabi, quyidagilar o'rtacha qiymat teoremasi.

Ruxsat bering ${displaystyle n_ {1}, nuqta, n_ {r}, P_ {1}, nuqta, P_ {r}}$ tabiiy sonlar, ${displaystyle P_ {1} = min (P_ {1}, nuqta, P_ {r})}$,${displaystyle m = (n_ {1} +1) nuqta (n_ {r} +1)}$. Bundan tashqari, ruxsat bering ${displaystyle Omega}$ bo'lishi ${displaystyle m}$- shaklning o'lchovli kubi :: ${displaystyle 0leq alfa (t_ {1}, nuqtalar, t_ {r}) <1}$ , ${displaystyle 0leq t_ {1} leq n_ {1}, nuqtalar, 0leq t_ {r} leq n_ {r}}$, evklid kosmosida: va :: ${displaystyle J = J (P_ {1}, nuqtalar, P_ {r}; n_ {1}, nuqtalar, n_ {r}; K, r) = {pastki qator {Omega} {int nuqtalar int}} | S (A ) | ^ {2K} dA}$ . : Keyin har qanday kishi uchun ${displaystyle au geq 0}$ va ${displaystyle Kgeq K_ {au} = m au}$ qiymati ${displaystyle J}$ quyidagicha baholanishi mumkin

${displaystyle Jleq K_ {au} ^ {2m au} varkappa ^ {4varkappa ^ {2} Delta (au)} 2 ^ {8mvarkappa au} (P_ {1} nuqtalar P_ {r}) ^ {2K} P ^ {- varkappa deltasi (au)}}$ , :

qayerda ${displaystyle varkappa = n_ {1} u _ {1} + nuqta + n_ {r} u _ {r}}$ , ${displaystyle gamma varkappa = 1}$, ${displaystyle Delta (au) = {frac {m} {2}} (1- (1-gamma) ^ {au})}$ , ${displaystyle P = (P_ {1} ^ {n_ {1}} nuqtalar P_ {r} ^ {n_ {r}}) ^ {gamma}}$va natural sonlar ${displaystyle u _ {1}, nuqta, u _ {r}}$ shunday: :: ${displaystyle -1 <{frac {P_ {s}} {P_ {1}}} - u _ {s} leq 0}$ , ${displaystyle s = 1, nuqta, r}$ .

O'rtacha qiymat teoremasi va ko'p o'lchovli parallelepipedlarning kesishishi ko'pligidagi lemma, Karatsuba tomonidan olingan (ikki o'lchovli holat G.I. Arxipov tomonidan olingan) ko'p trigonometrik yig'indining asosini tashkil etadi.^[18]). Belgilash orqali ${displaystyle Q_ {0}}$ raqamlarning eng kichik umumiy ko'paytmasi ${displaystyle q (t_ {1}, nuqtalar, t_ {r})}$ shart bilan ${displaystyle t_ {1} + nuqta t_ {r} geq 1}$, uchun ${displaystyle Q_ {0} geq P ^ {1/6}}$ smeta amal qiladi

${displaystyle | S (A) | leq (5n ^ {2n}) ^ {ru (Q_ {0})} (au (Q_ {0})) ^ {r-1} P_ {1} P_ {r} nuqtalar Q ^ {- 0.1mu} + 2 ^ {8r} (rmu ^ {- 1}) ^ {r-1} P_ {1} nuqtalar P_ {r} P ^ {- 0.05mu}}$ ,

qayerda ${displaystyle au (Q)}$ butun sonning bo'linuvchilar soni ${displaystyle Q}$va ${displaystyle u (Q)}$ sonning aniq bosh bo'linuvchilarining soni ${displaystyle Q}$.

Waring muammosidagi Hardy funktsiyasini taxmin qilish

Uni qo'llash ${displaystyle p}$- trigonometrik yig'indilarni baholash uchun Hardy-Littlewood-Ramanujan-Vinogradov usulining sodda shakli, bu erda yig'ish kichik tub bo'linadigan sonlar ustiga olinadi, Karatsuba olingan^[19] taniqli yangi baho Hardy funktsiya ${displaystyle G (n)}$ ichida Waring muammosi (uchun ${displaystyle ngeq 400}$):

${displaystyle! G (n) <2nlog n + 2nlog log n + 12n.}$

Waring muammosining ko'p o'lchovli analogi

Keyinchalik Karatsubaning Waring muammosini tekshirishda^[20] ushbu muammoning quyidagi ikki o'lchovli umumlashtirilishi:

Tenglamalar tizimini ko'rib chiqing

${displaystyle x_ {1} ^ {n-i} y_ {1} ^ {i} + nuqta + x_ {k} ^ {n-i} y_ {k} ^ {i} = N_ {i}}$ , ${displaystyle i = 0,1, nuqta, n}$ ,

qayerda ${displaystyle N_ {i}}$ bir xil tartibda yoki o'sishda musbat tamsayılar berilgan, ${displaystyle N_ {0} o + infty}$va ${displaystyle x_ {varkappa}, y_ {varkappa}}$ noma'lum, ular ham musbat butun sonlardir. Ushbu tizim echimlarga ega, agar ${displaystyle k> cn ^ {2} log n}$ va agar bo'lsa ${displaystyle k$, unda shunday narsalar mavjud ${displaystyle N_ {i}}$, tizimning echimlari yo'qligi.

Nolni forma bilan lokal ravishda namoyish etish Artin muammosi

Emil Artin muammoni keltirib chiqargan edi ${displaystyle p}$- nolni ixtiyoriy daraja shakli bilan odatiy aks ettirish d. Dastlab Artin natijani taxmin qildi, endi bu shunday deb ta'riflanadi p-adik maydon bo'lish a C₂ maydon; boshqacha qilib aytganda, o'zgaruvchilar soni kamida bo'lsa, nolning ahamiyatsiz ifodasi paydo bo'ladi d². Bu misol emasligi ko'rsatib o'tilgan Gay Terjanian. Karatsuba shuni ko'rsatdiki, nolni ariza bilan ahamiyatsiz ifodalash uchun o'zgaruvchilar soni darajadagi polinomga qaraganda tezroq o'sishi kerak d; bu raqam aslida darajaga qarab deyarli eksponent o'sishga ega bo'lishi kerak. Karatsuba va uning shogirdi Arxipov isbotladilar,^[21] bu har qanday tabiiy son uchun ${displaystyle r}$ mavjud ${displaystyle n_ {0} = n_ {0} (r)}$, har qanday kishi uchun shunday ${displaystyle ngeq n_ {0}}$ integral koeffitsientlarga ega shakl mavjud ${displaystyle F (x_ {1}, nuqta, x_ {k})}$ darajadan kichikroq ${displaystyle n}$, ularning o'zgaruvchilar soni ${displaystyle k}$, ${displaystyle kgeq 2 ^ {u}}$,

${displaystyle u = {frac {n} {(log _ {2} n) (log _ {2} log _ {2} n) nuqtalar ostidagi chiziqlar {(log _ {2} nuqtalar log _ {2} n)} _ {r} pastki chiziq {(log _ {2} nuqta log _ {2} n) ^ {3}} _ {r + 1}}}}$

2-adik sonlarda nolning ahamiyatsiz ifodasiga ega. Ular har qanday g'alati asosiy modul uchun ham shunga o'xshash natijaga erishdilar ${displaystyle p}$.

Qisqa Kloosterman summalarining taxminlari

Karatsuba rivojlandi^[22][23][24] (1993—1999) qisqa baholashning yangi usuliKloosterman summasi, ya'ni shaklning trigonometrik yig'indilari

${displaystyle sum limitlari _ {nin A} exp {{iggl (} 2pi i, {frac {an ^ {*} + bn} {m}} {iggr)}},}$

qayerda ${displaystyle n}$ to'plam orqali ishlaydi ${displaystyle A}$ raqamlar, nusxa ko'chirish ${displaystyle m}$, elementlarning soni ${displaystyle | A |}$ unda asosan kichikroq ${displaystyle m}$va belgi ${displaystyle n ^ {*}}$ teskari tomonga muvofiqlik sinfini bildiradi ${displaystyle n}$ modul ${displaystyle m}$: ${displaystyle nn ^ {*} equiv 1 (mod m)}$.

1990-yillarning boshlariga qadar ushbu turdagi taxminlar asosan summandlar soni ko'proq bo'lgan summalar uchun ma'lum bo'lgan. ${displaystyle {sqrt {m}}}$ (H. D. Kloosterman, I. M. Vinogradov, X.Sali, L. Karlitz, S. Uchiyama, A. Vayl ). Istisno faqat shaklning maxsus modullari edi ${displaystyle m = p ^ {alfa}}$, qayerda ${displaystyle p}$ sobit asosiy va ko'rsatkichdir ${displaystyle alfa}$ cheksizgacha ko'payadi (bu holat A. G. Postnikov tomonidan Vinogradov usuli yordamida o'rganilgan). Karatsubaning usuli Kloosterman summalarini summandlar soni ko'p bo'lmagan joyda taxmin qilishga imkon beradi

${displaystyle m ^ {varepsilon},}$

va ba'zi hollarda hatto

${displaystyle exp {{(ln m) ^ {2/3 + varepsilon}}},}$

qayerda ${displaystyle varepsilon> 0}$ o'zboshimchalik bilan kichik sobit raqam. Karatsubaning ushbu mavzu bo'yicha yakuniy ishi^[25] vafotidan keyin nashr etildi.

Karatsuba uslubining turli jihatlari analitik sonlar nazariyasining quyidagi masalalarida qo'llanilishini topdi:

• shaklning kasr qismlari yig'indisining asimptotikasini topish: ${displaystyle {sum _ {nleq x}} '{iggl {} {frac {an ^ {*} + bn} {m}} {iggr}}, {sum _ {pleq x}}' {iggl {} {frac {ap ^ {*} + bp} {m}} {iggr}},}$ : qaerda ${displaystyle n}$ shartni qondiradigan butun sonlar orqali birin-ketin ishlaydi ${displaystyle (n, m) = 1}$va ${displaystyle p}$ modulni ajratmaydigan tub sonlar orqali ishlaydi ${displaystyle m}$ (Karatsuba);

• shakldagi tengsizlik echimlari sonining pastki chegarasini topish: ${displaystyle alfa <{iggl {} {frac {an ^ {*} + bn} {m}} {iggr}} leq eta}$ : butun sonlarda ${displaystyle n}$, ${displaystyle 1leq nleq x}$, nusxa ko'chirish ${displaystyle m}$, ${displaystyle x <{sqrt {m}}}$ (Karatsuba);

• segmentdagi ixtiyoriy haqiqiy sonni taxminiy aniqligi ${displaystyle [0,1]}$ shaklning kasr qismlari bo'yicha:

${displaystyle {iggl {} {frac {an ^ {*} + bn} {m}} {iggr}},}$ : qaerda ${displaystyle 1leq nleq x}$, ${displaystyle (n, m) = 1}$, ${displaystyle x <{sqrt {m}}}$ (Karatsuba);

• aniqroq doimiy ${displaystyle c}$ ichida Brun-Titchmarsh teoremasi  :

${displaystyle pi (x; q, l) <{frac {cx} {varphi (q) ln {frac {2x} {q}}}},}$ : qaerda ${displaystyle pi (x; q, l)}$ asosiy sonlar soni ${displaystyle p}$, oshmasligi kerak ${displaystyle x}$ va arifmetik progressiyaga tegishli ${displaystyle pequiv l {pmod {q}}}$ (J. Fridlander, H. Ivaniec );

• shakl sonlari ko'paytmasining eng katta bosh bo'luvchisi uchun pastki chegara:

${displaystyle n ^ {3} +2}$, ${displaystyle N$ (D. R. Xit-Braun );

• shaklning cheksiz sonlari borligini isbotlash:

${displaystyle a ^ {2} + b ^ {4}}$ (J. Fridlander, H. Ivaniec );

• raqamlar to'plamining kombinatorial xususiyatlari:

${displaystyle n ^ {*} {pmod {m}}}$${displaystyle 1leq nleq m ^ {varepsilon}}$ (A. A. Glibichuk).

Riemann zeta-funktsiyasi

Selberg nollari

1984 yilda Karatsuba isbotladi,^[26][27] bu sobit uchun ${displaystyle varepsilon}$ shartni qondirish${displaystyle 0$, etarlicha katta ${displaystyle T}$ va ${displaystyle H = T ^ {a + varepsilon}}$, ${displaystyle a = {frac {27} {82}} = {frac {1} {3}} - {frac {1} {246}}}$, interval ${displaystyle (T, T + H)}$ kamida o'z ichiga oladi ${displaystyle cHln T}$ haqiqiy nollari Riemann zeta funktsiyasi ${displaystyle zeta {Bigl (} {frac {1} {2}} + it {Bigr)}}$.

Maxsus ish ${displaystyle Hgeq T ^ {1/2 + varepsilon}}$ tomonidan isbotlangan Atle Selberg ilgari 1942 yilda.^[28] Ning taxminlari Atle Selberg va o'sish tartibi bo'yicha Karatsubani takomillashtirish mumkin emas ${displaystyle T o + yaroqsiz}$.

Riemann zeta funktsiyasining nollarini kritik chiziqning qisqa intervallarida taqsimlanishi

Karatsuba ham qo'lga kiritdi ^[29] nollarining taqsimlanishi haqida bir qator natijalar ${displaystyle zeta (lar)}$ tanqidiy chiziqning «qisqa» oralig'ida. U shunga o'xshashligini isbotladi Selberg gumoni "deyarli" intervallarni ushlab turadi ${displaystyle (T, T + H]}$, ${displaystyle H = T ^ {varepsilon}}$, qayerda ${displaystyle varepsilon}$ o'zboshimchalik bilan kichik sobit son. Karatsuba (1992) Riemann zeta-funktsiyasining nollarini kritik chiziqning "supershort" oralig'ida, ya'ni intervallarida tekshirishga yangi yondashuvni ishlab chiqdi. ${displaystyle (T, T + H]}$, uzunligi ${displaystyle H}$ ularning har qandayidan, hatto o'zboshimchalik bilan kichik darajadan sekinroq o'sadi ${displaystyle T}$. Xususan, u har qanday berilgan sonlar uchun buni isbotladi ${displaystyle varepsilon}$, ${displaystyle varepsilon _ {1}}$ shartlarni qondirish ${displaystyle 0$ deyarli barcha intervallar ${displaystyle (T, T + H]}$ uchun ${displaystyle Hgeq exp {{(ln T) ^ {varepsilon}}}}$ kamida o'z ichiga oladi ${displaystyle H (ln T) ^ {1-varepsilon _ {1}}}$ funktsiyaning nollari ${displaystyle zeta {igl (} {frac {1} {2}} + it {igr)}}$. Ushbu taxmin quyidagidan kelib chiqqan bahoga juda yaqin Riman gipotezasi.

Dirichlet L seriyasining chiziqli birikmalarining nollari

Karatsuba yangi usulni ishlab chiqdi ^[30][31] ning chiziqli kombinatsiyasi sifatida ifodalanishi mumkin bo'lgan nol funktsiyalarni o'rganish Dirichlet ${displaystyle L}$- seriyalar. Ushbu turdagi funktsiyalarning eng oddiy misoli, tenglik bilan aniqlangan Davenport-Heilbronn funktsiyasi

${displaystyle f (s) = {frac {1} {2}} (1-ikappa) L (s, chi) + {frac {1} {2}} (1, +, ikappa) L (s, {ar) {chi}}),}$

qayerda ${displaystyle chi}$ asosiy bo'lmagan belgi modulidir ${displaystyle 5}$ (${displaystyle chi (1) = 1}$, ${displaystyle chi (2) = i}$, ${displaystyle chi (3) = - i}$, ${displaystyle chi (4) = - 1}$, ${displaystyle chi (5) = 0}$, ${displaystyle chi (n + 5) = chi (n)}$ har qanday kishi uchun ${displaystyle n}$),

${displaystyle kappa = {frac {{sqrt {10-2 {sqrt {5}}}} - 2} {{sqrt {5}} - 1}}.}$

Uchun ${displaystyle f (s)}$ Riman gipotezasi ammo bu juda to'g'ri emas ${displaystyle Re s = {frac {1} {2}}}$ Shunga qaramay, juda ko'p nollarni o'z ichiga oladi.

Karatsuba (1989) intervalni isbotladi ${displaystyle (T, T + H]}$, ${displaystyle H = T ^ {27/82 + varepsilon}}$, kamida o'z ichiga oladi

${displaystyle H (ln T) ^ {1/2} e ^ {- c {sqrt {ln ln T}}}}}$

funktsiyaning nollari ${displaystyle f {igl (} {frac {1} {2}} + it {igr)}}$. Shunga o'xshash natijalarni Karatsuba o'zboshimchalik bilan (cheklangan) sonli yig'indilarni o'z ichiga olgan chiziqli kombinatsiyalar uchun ham qo'lga kiritdi; daraja ko'rsatkichi ${displaystyle {frac {1} {2}}}$ bu erda kichikroq raqam bilan almashtiriladi ${displaystyle eta}$, bu faqat chiziqli birikmaning shakliga bog'liq.

Zeta funktsiyasining nollari chegarasi va Dirichlet bo'luvchilarining ko'p o'lchovli masalasi

Karatsuba uchun yangi yutuq natijasi ^[32] sonni topish bilan bog'liq bo'lgan Dirichlet bo'luvchilarining ko'p o'lchovli masalasida ${displaystyle D_ {k} (x)}$ tengsizlikning echimlari ${displaystyle x_ {1} * ldots * x_ {k} leq x}$ tabiiy sonlarda ${displaystyle x_ {1}, ldots, x_ {k}}$ kabi ${displaystyle x o + infty}$. Uchun ${displaystyle D_ {k} (x)}$ shaklning asimptotik formulasi mavjud

${displaystyle D_ {k} (x) = xP_ {k-1} (ln x) + R_ {k} (x)}$ ,

qayerda ${displaystyle P_ {k-1} (u)}$ daraja polinomidir ${displaystyle (k-1)}$, ularning koeffitsientlari bog'liq ${displaystyle k}$ va aniq topilishi mumkin va ${displaystyle R_ {k} (x)}$ qolgan atamadir, uning barcha ma'lum taxminlari (1960 yilgacha) shaklda bo'lgan

${displaystyle | R_ {k} (x) | leq x ^ {1-alfa (k)} (cln x) ^ {k}}$ ,

qayerda ${displaystyle alfa = {frac {1} {ak + b}}}$, ${displaystyle a, b, c}$ ba'zi bir mutlaq ijobiy konstantalar.

Karatsuba aniqroq taxminni qo'lga kiritdi ${displaystyle R_ {k} (x)}$, unda qiymat ${displaystyle alfa (k)}$ tartibda edi ${displaystyle k ^ {- 2/3}}$ va nisbatan ancha sekin pasayib borardi ${displaystyle alfa (k)}$ oldingi taxminlarda. Karatsubaning bahosi bir xil ${displaystyle x}$ va ${displaystyle k}$; xususan, qiymat ${displaystyle k}$ kabi o'sishi mumkin ${displaystyle x}$ o'sadi (ning logaritmasining ba'zi kuchlari kabi ${displaystyle x}$). (Shunga o'xshash ko'rinishdagi, ammo kuchsizroq natijani 1960 yilda nemis matematikasi Rixert qo'lga kiritdi, uning qog'ozi Sovet matematiklari uchun kamida yetmishinchi yillarning o'rtalariga qadar noma'lum bo'lib qoldi.)

Smetasining isboti ${displaystyle R_ {k} (x)}$ Vinogradov usuli bilan olingan Riemann zeta funktsiyasining nollari chegarasidagi teoremaga teng keladigan bir qator da'volarga asoslanadi, ya'ni ${displaystyle zeta (lar)}$ mintaqada nolga ega emas

${displaystyle Re sgeq 1- {frac {c} {(ln | t |) ^ {2/3} (ln ln | t |) ^ {1/3}}}, quad | t |> 10}$ .

Karatsuba topildi ^[33](2000) qiymatlarni baholashning orqaga aloqasi ${displaystyle R_ {k} (x)}$ ning harakati bilan${displaystyle zeta (lar)}$ chiziq yaqinida ${displaystyle Re s = 1}$. Xususan, agar u buni isbotlagan bo'lsa ${displaystyle alfa (y)}$ shartni qondiradigan ixtiyoriy ravishda ko'paymaydigan funktsiya ${displaystyle 1 / yleq alfa (y) leq 1/2}$, barchasi uchun ${displaystyle kgeq 2}$ smeta

${displaystyle | R_ {k} (x) | leq x ^ {1-alfa (k)} (cln x) ^ {k}}$

ushlab turadi, keyin ${displaystyle zeta (lar)}$ mintaqada nolga ega emas

${displaystyle Re sgeq 1-c_ {1}, {frac {alfa (ln | t |)} {ln ln | t |}}, quad | t | geq e ^ {2}}$

(${displaystyle c, c_ {1}}$ ba'zi bir muttasil konstantalar).

Kritik domenning kichik mintaqalarida va kritik chiziqning kichik intervallarida zeta funktsiyasi modulining pastki qismidan pastgacha

Karatsuba tanishtirdi va o'rgandi ^[34] funktsiyalari ${displaystyle F (T; H)}$ va ${displaystyle G (s_ {0}; Delta)}$, tengliklar bilan belgilanadi

${displaystyle F (T; H) = max _ {| tT | leq H} {igl |} zeta {igl (} {frac {1} {2}} + it {igr)} {igr |}, to'rtinchi G ( s_ {0}; Delta) = max _ {| s-s_ {0} | leq Delta} | zeta (s) |.}$

Bu yerda ${displaystyle T}$ bu juda katta ijobiy raqam, ${displaystyle 0$, ${displaystyle s_ {0} = sigma _ {0} + iT}$, ${displaystyle {frac {1} {2}} leq sigma _ {0} leq 1}$, ${displaystyle 0$. Qiymatlarni baholash ${displaystyle F}$ va ${displaystyle G}$ quyida ko'rsatilgan qiymatlar (modulda) qanchalik katta ${displaystyle zeta (lar)}$ kritik chiziqning qisqa oralig'ida yoki kritik chiziqda joylashgan nuqtalarning kichik mahallalarida olishi mumkin ${displaystyle 0leq Re sleq 1}$. Ish ${displaystyle Hgg ln ln T}$ ilgari Ramachandra tomonidan o'rganilgan; ish ${displaystyle Delta> c}$, qayerda ${displaystyle c}$ juda katta doimiy, ahamiyatsiz.

Karatsuba, ayniqsa, agar qadriyatlar bo'lsa, buni isbotladi ${displaystyle H}$ va ${displaystyle Delta}$ ba'zi etarlicha kichik konstantalardan, keyin hisob-kitoblardan oshib ketadi

${displaystyle F (T; H) geq T ^ {- c_ {1}}, to'rtinchi G (s_ {0}; Delta) geq T ^ {- c_ {2}},}$

ushlab turing, qaerda ${displaystyle c_ {1}, c_ {2}}$ aniq muttasil konstantalardir.

Zeta-funktsiya argumentining tanqidiy chiziqdagi harakati

Karatsuba bir qator yangi natijalarga erishdi^[35][36] funktsiya harakati bilan bog'liq ${displaystyle S (t) = {frac {1} {pi}} arg {zeta {igl (} {frac {1} {2}} + it {igr)}}}$, ning argumenti deb ataladi Riemann zeta funktsiyasi tanqidiy chiziqda (bu erda ${displaystyle arg {zeta {igl (} {frac {1} {2}} + it {igr)}}}$ ning ixtiyoriy uzluksiz filialining o'sishidir ${displaystyle arg zeta (lar)}$ nuqtalarni birlashtirgan singan chiziq bo'ylab ${displaystyle 2,2 + it}$ va ${displaystyle {frac {1} {2}} + it}$). Ushbu natijalar orasida funktsiya uchun o'rtacha qiymat teoremalari mavjud ${displaystyle S (t)}$ va uning birinchi integrali ${displaystyle S_ {1} (t) = int _ {0} ^ {t} S (u) du}$ haqiqiy chiziq oralig'ida, shuningdek, har bir intervalni da'vo qiladigan teorema ${displaystyle (T, T + H]}$ uchun ${displaystyle Hgeq T ^ {27/82 + varepsilon}}$ kamida o'z ichiga oladi

${displaystyle H (ln T) ^ {1/3} e ^ {- c {sqrt {ln ln T}}}}}$

funktsiyani bajaradigan joylar ${displaystyle S (t)}$ o'zgarishlar belgisi. Ilgari shunga o'xshash natijalar tomonidan olingan Atle Selberg ish uchun${displaystyle Hgeq T ^ {1/2 + varepsilon}}$.

Dirichlet belgilar

Cheklangan maydonlarda qisqa belgilar yig'indisini taxmin qilish

Oltmishinchi yillarning oxirida Karatsuba, qisqa summalarni taxmin qilmoqda Dirichlet belgilar, ishlab chiqilgan ^[37] qisqa metrajli belgilarning ahamiyatsiz baholarini olish imkonini beradigan yangi usul cheklangan maydonlar. Ruxsat bering${displaystyle ngeq 2}$ aniq bir tamsayı bo'lishi, ${displaystyle F (x) = x ^ {n} + a_ {n-1} x ^ {n-1} + ldots + a_ {1} x + a_ {0}}$ maydonda kamaytirilmaydigan polinom ${displaystyle mathbb {Q}}$ ratsional sonlar, ${displaystyle heta}$ tenglamaning ildizi ${displaystyle F (heta) = 0}$, ${displaystyle mathbb {Q} (heta)}$ maydonning tegishli kengaytmasi ${displaystyle mathbb {Q}}$, ${displaystyle omega _ {1}, ldots, omega _ {n}}$ asosi ${displaystyle mathbb {Q} (heta)}$, ${displaystyle omega _ {1} = 1}$, ${displaystyle omega _ {2} = heta}$, ${displaystyle omega _ {3} = heta ^ {2}, ldots, omega _ {n} = heta ^ {n-1}}$. Bundan tashqari, ruxsat bering ${displaystyle p}$ etarlicha katta boshlang'ich bo'ling, shunday qilib ${displaystyle F (x)}$ qisqartirilmaydigan modul ${displaystyle p}$,${displaystyle mathrm {GF} (p ^ {n})}$ The Galois maydoni asos bilan ${displaystyle omega _ {1}, omega _ {2}, ldots, omega _ {n}}$, ${displaystyle chi}$ asosiy bo'lmagan Dirichlet belgisi maydonning ${displaystyle mathrm {GF} (p ^ {n})}$. Nihoyat, ruxsat bering ${displaystyle u _ {1}, ldots, u _ {n}}$ salbiy bo'lmagan tamsayılar bo'ling, ${displaystyle D (X)}$ elementlar to'plami ${displaystyle {ar {x}}}$ Galois maydonining ${displaystyle mathrm {GF} (p ^ {n})}$,

${displaystyle {ar {x}} = x_ {1} omega _ {1} + ldots + x_ {n} omega _ {n}}$ ,

har qanday kishi uchun ${displaystyle i}$, ${displaystyle 1leq ileq n}$, quyidagi tengsizliklar mavjud:

${displaystyle u _ {i}$ .

Karatsuba har qanday qat'iy uchun buni isbotladi ${displaystyle k}$, ${displaystyle kgeq n + 1}$va o'zboshimchalik bilan ${displaystyle X}$ shartni qondirish

${displaystyle p ^ {{frac {1} {4}} + {frac {1} {4k}}} leq Xleq p ^ {{frac {1} {2}} + {frac {1} {4k}}} }$

quyidagi taxmin mavjud:

${displaystyle {iggl |} summa chegaralari _ {{ar {x}} d (X)} chi ({ar {x}}) {iggr |} leq c {Bigl (} X ^ {1- {frac {1) } {k}}} p ^ {{frac {1} {4k}} + {frac {1} {4k ^ {2}}}} {Bigr)} ^ {!! n} (ln p) ^ {gamma },}$

qayerda ${displaystyle gamma = {frac {1} {k}} (2 ^ {n + 1} -1)}$va doimiy ${displaystyle c}$ faqat bog'liq ${displaystyle n}$ va asos ${displaystyle omega _ {1}, ldots, omega _ {n}}$.

Ko'chirilgan tub sonlar bo'yicha belgilarning chiziqli yig'indilarini baholash

Karatsuba bir qator yangi vositalarni ishlab chiqdi, bular Vinogradovning dastlabki sonlar bilan yig'indilarni hisoblash usuli bilan birlashganda, unga 1970 yilda erishishga imkon berdi. ^[38] oddiy bo'lmagan modul qiymatlari yig'indisi taxminiy qiymati ${displaystyle q}$ siljigan tub sonlar ketma-ketligi bo'yicha, ya'ni shaklning bahosi

${displaystyle {iggl |} yig'indisi chegaralari _ {pleq N} chi (p + k) {iggr |} leq cNq ^ {- {frac {varepsilon ^ {2}} {1024}}},}$

qayerda ${displaystyle k}$ shartni qondiradigan butun son ${displaystyle kot equiv 0 (mod q)}$, ${displaystyle varepsilon}$ o'zboshimchalik bilan belgilangan raqam, ${displaystyle Ngeq q ^ {1/2 + varepsilon}}$va doimiy ${displaystyle c}$ bog'liq ${displaystyle varepsilon}$ faqat.

Ushbu da'vo Vinogradovning taxminidan ancha kuchliroq, chunki bu ahamiyatsiz emas ${displaystyle Ngeq q ^ {3/4 + varepsilon}}$.

1971 yilda 80 yilligi munosabati bilan raqamlar nazariyasi bo'yicha xalqaro konferentsiyada so'zga chiqdi Ivan Matveyevich Vinogradov, Akademik Yuriy Linnik quyidagilarni ta'kidladi:

«Vinogradov tomonidan asimptotiklar sohasida olib borilgan tekshiruvlar katta ahamiyatga ega Dirichlet belgisi almashtirilgan tub sonlarda ${displaystyle summasi chegaralari _ {pleq N} chi (p + k)}$, bilan solishtirganda pasaygan quvvatni beradi ${displaystyle N}$ ga solishtirganda ${displaystyle Ngeq q ^ {3/4 + varepsilon}}$,${displaystyle varepsilon> 0}$, qayerda ${displaystyle q}$ belgining moduli. Ushbu taxmin juda muhim, chunki u chuqurroq, kengaytirilganidan ko'proq narsani beradi Riman gipotezasi, va, ehtimol, bu yo'nalishlarda bu taxmindan ko'ra chuqurroq haqiqat (agar taxmin to'g'ri bo'lsa). Yaqinda ushbu taxminni A.A.Karatsuba takomillashtirdi ».

Ushbu natija Karatsuba tomonidan qachongacha kengaytirildi ${displaystyle p}$ arifmetik progresiyada tub sonlardan o'tadi, uning o'sishi modul bilan o'sib boradi${displaystyle q}$.

Asosiy argumentli polinomlar bo'yicha belgilar yig'indisini taxmin qilish

Karatsuba topildi ^[37][39] polinomning argumenti keyingi asosiy sonlarning qisqa ketma-ketligidan o'tadigan bo'lsa, ikkinchi darajali polinomlardagi Dirklet belgilar yig'indilarining bir qator taxminlari. Masalan, ${displaystyle q}$ etarlicha yuqori darajaga ega bo'ling, ${displaystyle f (x) = (x-a) (x-b)}$, qayerda ${displaystyle a}$ va ${displaystyle b}$ shartni qondiradigan butun sonlardir ${displaystyle ab (a-b) ot equiv 0 (mod q)}$va ruxsat bering ${displaystyle chap ({frac {n} {q}} ight)}$ ni belgilang Legendre belgisi, keyin har qanday sobit uchun ${displaystyle varepsilon}$ shart bilan ${displaystyle 0$ va ${displaystyle N> q ^ {3/4 + varepsilon}}$ summa uchun ${displaystyle S_ {N}}$,

${displaystyle S_ {N} = yig'indining chegaralari _ {pleq N} {iggl (} {frac {f (p)} {q}} {iggr)},}$

quyidagi taxmin mavjud:

${displaystyle | S_ {N} | leq cpi (N) q ^ {- {frac {varepsilon ^ {2}} {100}}}}$

(Bu yerga ${displaystyle p}$ keyingi tub sonlar orqali ishlaydi, ${displaystyle pi (N)}$ asosiy sonlar sonidan oshmaydi ${displaystyle N}$va ${displaystyle c}$ ga bog'liq bo'lib, doimiy bo'ladi ${displaystyle varepsilon}$ faqat).

Xuddi shunday taxmin Karatsuba tomonidan qachon olinganligi uchun ham olingan ${displaystyle p}$ ortishi modul bilan birga o'sishi mumkin bo'lgan arifmetik progresiyada tub sonlar ketma-ketligidan o'tadi. ${displaystyle q}$.

Karatsuba yig'indining ahamiyatsiz bahosi deb taxmin qildi ${displaystyle S_ {N}}$ uchun ${displaystyle N}$, ular bilan solishtirganda "kichik" ${displaystyle q}$, qachon bo'lgan taqdirda ham haqiqiy bo'lib qoladi ${displaystyle f (x)}$ daraja ixtiyoriy polinom bilan almashtiriladi ${displaystyle n}$, bu kvadrat modul emas ${displaystyle q}$. Ushbu taxmin hali ham ochiq.

Polinomlardagi belgilar yig'indisining pastki chegaralari

Karatsuba qurilgan ^[40] tub sonlarning cheksiz ketma-ketligi ${displaystyle p}$ va polinomlarning ketma-ketligi ${displaystyle f (x)}$ daraja ${displaystyle n}$ tamsayı koeffitsientlari bilan, shunday qilib ${displaystyle f (x)}$ to'liq kvadrat modul emas ${displaystyle p}$,

${displaystyle {frac {4 (p-1)} {ln p}} leq nleq {frac {8 (p-1)} {ln p}},}$

va shunday

${displaystyle summasi chegaralari _ {x = 1} ^ {p} chap ({frac {f (x)} {p}} ight) = p.}$

Boshqacha qilib aytganda, har qanday kishi uchun ${displaystyle x}$ qiymati ${displaystyle f (x)}$ kvadrat qoldiqlari modul bo'lib chiqadi ${displaystyle p}$. Ushbu natija shuni ko'rsatadiki Andr Vayl taxminiy

${displaystyle {iggl |} yig'indisining chegaralari _ {x = 1} ^ {p} chap ({frac {f (x)} {p}} ight) {iggr |} leq (n-1) {sqrt {p}} }$

mohiyatan yaxshilanib bo'lmaydi va oxirgi tengsizlikning o'ng tomonini qiymat bilan almashtirish mumkin emas ${displaystyle C {sqrt {n}} {sqrt {p}}}$, qayerda ${displaystyle C}$ mutlaq doimiydir.

Qo'shimcha ketma-ketlikdagi belgilar yig'indisi

Karatsuba yangi usulni topdi,^[41] qo'shimchalar ketma-ketligi bo'yicha, ya'ni shakldagi raqamlardan tashkil topgan ketma-ketliklar bo'yicha asosiy bo'lmagan Dirichlet belgilarining qiymatlari yig'indisining aniq baholarini olishga imkon beradi. ${displaystyle x + y}$, bu erda o'zgaruvchilar ${displaystyle x}$ va ${displaystyle y}$ ba'zi to'plamlar orqali ishlaydi${displaystyle A}$ va ${displaystyle B}$ bir-biridan mustaqil ravishda. Ushbu turdagi eng xarakterli misol Dirichlet belgilarining qiymatlarini yig'ish bilan bog'liq bo'lgan juda ko'p sonli muammolarni hal qilishda qo'llaniladigan quyidagi da'vo hisoblanadi. Ruxsat bering ${displaystyle varepsilon}$ o'zboshimchalik bilan kichik raqam, ${displaystyle 0$, ${displaystyle q}$ etarlicha katta boshlang'ich, ${displaystyle chi}$ asosiy bo'lmagan modul ${displaystyle q}$. Bundan tashqari, ruxsat bering ${displaystyle A}$ va ${displaystyle B}$ muvofiqlik sinflarining to'liq tizimining ixtiyoriy kichik to'plamlari modul bo'lishi ${displaystyle q}$, faqat shartlarni qondiradigan ${displaystyle | A |> q ^ {varepsilon}}$, ${displaystyle | B |> q ^ {1/2 + varepsilon}}$. Keyin quyidagi taxmin mavjud:

${displaystyle { iggl |}sum limits _{xin A}sum limits _{yin B}chi (x+y){ iggr |}leq c|A|cdot |B|q^{-{frac {varepsilon ^{2}}{20}}},quad c=c(varepsilon )>0.}$

Karatsuba's method makes it possible to obtain non-trivial estimates of that sort in certain other cases when the conditions for the sets ${displaystyle A}$ va ${displaystyle B}$, formulated above, are replaced by different ones, for example: ${displaystyle |A|>q^{varepsilon }}$, ${displaystyle {sqrt {|A|}}cdot |B|>q^{1/2+varepsilon }.}$

Bunday holatda ${displaystyle A}$ va ${displaystyle B}$ are the sets of primes in intervals ${displaystyle (1,X]}$, ${displaystyle (1,Y]}$ respectively, where ${displaystyle Xgeq q^{1/4+varepsilon }}$, ${displaystyle Ygeq q^{1/4+varepsilon }}$, an estimate of the form

${displaystyle { iggl |}sum limits _{pleq X}sum limits _{p'leq Y}chi (p+p'){ iggr |}leq cpi (X)pi (Y)q^{-c_{1}varepsilon ^{2}},}$