1.3: Розподіл простих чисел

Last updated
Save as PDF

Page ID: 105489

Leo Moser
University of Alberta via The Trilla Group

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Мабуть, найвідомішим доказом у всій «реальній» математиці є доказ Евкліда про існування нескінченно багатьох простих чисел.

Теорема$\PageIndex{1}$: existence of infinitely many primes

Якби$p$ були найбільшими простими, то не ділилися$(2 \cdot 3 \cdot 5 \cdot\cdot\cdot p) + 1$ б на жодне з простих чисел аж до$p$ і, отже, було б добутком простих чисел, що перевищують$p$

Незважаючи на свою надзвичайну простоту, цей доказ вже викликає багато надзвичайно складних питань, наприклад, числа$(2 \cdot 3 \cdot ... \cdot p) + 1$ зазвичай прості або складені? Загальних результатів не відомо. Насправді ми не знаємо, чи нескінченність цих чисел є простими, чи нескінченність є складовою.

Доказ може бути різноманітним у багатьох відношеннях. Таким чином, ми могли б розглянути$(2 \cdot 3 \cdot 5 \cdot\cdot\cdot p) - 1$ або$p! + 1$ або$p! - 1$. Знову практично нічого не відомо про те, як такі числа коефіцієнт. Останні два набори чисел приносять на думку проблему, яка розкриває, як в теорії чисел тривіальне може бути дуже близьким до найбільш незрозумілим. Досить тривіально, що для не$n > 2, n! - 1$ є ідеальним квадратом. Про що можна сказати$n! + 1$? Ну$4! + 1 = 5^2$,$5! + 1 = 11^2$ і$7! + 1 = 71^2$. Однак інших випадків не відомо; також не відомо, чи будь-які інші числа$n! + 1$ є ідеальними квадратами. До цієї проблеми ми повернемося в лекціях про діофантові рівняння.

Після Евкліда наступний істотний прогрес в теорії розподілу простих чисел був досягнутий Ейлером. Він довів, що$\sum \dfrac{1}{p}$ розходиться, і описав цей результат, сказавши, що простих чисел численніше квадратів. Я хотів би представити зараз новий доказ цього факту — доказ, який певною мірою пов'язаний з доказом Евкліда про існування нескінченно багатьох простих чисел.

Нам потрібна спочатку (добре відома) лема, що стосується підрядів гармонічного ряду. $p_1 < p_2 < ...$Дозволяти послідовність натуральних чисел і нехай його функція підрахунку бути

\[\pi (x) = \sum_{p \le x} 1.\]

Нехай

\[R(x) = \sum_{p \le x} \dfrac{1}{p}.\]

Лемма

Якщо$R(\infty)$ існує, то

\[\lim_{x \to \infty} \dfrac{\pi(x)}{x} = 0.\]

Доказ

\[\pi(x) = 1 (R(1) - R(0)) + 2 ((R(2) - R(1)) + ... + x(R(x) - R(x - 1))\]

або

\[\dfrac{\pi (x)}{x} = R(x) - \left[\dfrac{R(0) + R(1) + \cdot\cdot\cdot R(x - 1)}{x}\right].\]

Оскільки$R(x)$ наближається до межі, вираз в квадратних дужках наближається до цієї межі і лема доведена.

У наступному ми припускаємо, що$p$ ті є простими числами.

Щоб довести, що$\sum \dfrac{1}{p}$ розходиться, ми припустимо протилежне, тобто$\sum \dfrac{1}{p}$ сходиться (а значить і те$\dfrac{\pi(x)}{x} \to 0$) і виведемо протиріччя.

\[\sum_{p > n} \dfrac{1}{p} < \dfrac{1}{2}.\]

Але тепер$n$ це виправлено, так що буде і$m$ таке, що

\[\dfrac{\pi (n!m)}{n!m} < \dfrac{1}{2n!}.\]

З таким$n$ і$m$ формуємо$m$ цифри

$T_1 = n! - 1, T_2 = 2n! - 1, ..., T_m = mn! - 1.$

Зверніть увагу, що жоден з$T$ них не має простих множників$\le n$ або$\ge mn!$. Крім того, якщо$p | T_i$ і$p | T_j$ то$p | (T_i - T_j)$ так$p | (i - j)$. Іншими словами,$p$ кратні$p$ один від одного в нашому наборі чисел. Отже, не більше$\dfrac{m}{p} + 1$ чисел ділиться на$p$. Оскільки кожне число має принаймні один простий множник, ми маємо

$\sum_{n < p < n! m} (\dfrac{m}{p} + 1) \ge m$

або

$\sum_{n< p} \dfrac{1}{p} + \dfrac{\pi (n!m)}{m} \ge 1.$

Але тепер (1) і (2) права сторона повинна бути < 1, і ми маємо протиріччя, що доводить нашу теорему.

Доказ Ейлера, який є більш значущим, залежить від його дуже важливої ідентичності

$\zeta (s) = \sum_{n = 1}^{\infty} \dfrac{1}{n^s} = \prod_{p} \dfrac{1}{1 - \dfrac{1}{p^s}}.$

Ця ідентичність по суті є аналітичним твердженням унікальної теореми факторизації. Формально його обгрунтованість можна легко побачити. У нас є

$\begin{array} {rcl} {\prod_{p} \dfrac{1}{1 - \dfrac{1}{p^s}}} & = & {\prod_p (1 + \dfrac{1}{p^s} + \dfrac{1}{p^{2s}} + \cdot\cdot\cdot)} \\ {} & = & {(1 + \dfrac{1}{2^s} + \cdot\cdot\cdot)(1 + \dfrac{1}{3^s} + \cdot\cdot\cdot)(1 + \dfrac{1}{5^s} + \cdot\cdot\cdot)} \\ {} & = & {\dfrac{1}{1^s} + \dfrac{1}{2^s} + \dfrac{1}{3^s} + \cdot\cdot\cdot.} \end{array}$

Ейлер тепер стверджував, що для того$s = 1$,

$\sum_{n = 1}^{\infty} \dfrac{1}{n^s} = \infty$

щоб

$\prod_p \dfrac{1}{1 - \dfrac{1}{p}}$

повинно бути нескінченним, що в свою чергу означає, що$\sum \dfrac{1}{p}$ повинно бути нескінченним.

Цей аргумент, хоча і не зовсім справедливий, безумовно, можна зробити дійсним. Насправді, можна без особливих зусиль показати, що

$\sum_{n \le x} \dfrac{1}{n} - \prod_{p \le x} (1 - \dfrac{1}{p})^{-1}$

обмежений. Так як$\sum_{n \le x} \dfrac{1}{n} - \text{log} x$ обмежений, ми можемо, взявши колоди, отримати

$\text{loglog} x = \sum_{p \le x} - \text{log} (1 - \dfrac{1}{p}) + O(1)$

щоб

$\sum_{p \le x} \dfrac{1}{p} = \text{loglog} x + O(1).$

Цей результат ми скористаємося пізніше.

Гаусс і Лежандр першими зробили обґрунтовані оцінки$\pi (x)$. По суті, вони припускали, що

$\pi(x) \thicksim \dfrac{x}{\text{log} x},$

знаменита теорема про прості числа. Хоча це було доведено в 1896 році Дж. Адамард і де ла Валле Пуссен, перший істотний прогрес на шляху до цього результату зумовлений Шебішефф. Він отримав наступні три основних результату:

Існує просте між$n$ і$2n$ ($n > 1$);
Існують позитивні константи$c_1$ і$c_2$ такі, що\[\dfrac{c_2 x}{\text{log} x} < \pi (x) < \dfrac{c_1 x}{\text{log} x};\]
Якщо$\dfrac{\pi (x)}{\text{log} x}$ наближається до межі, то ця межа дорівнює 1.

Доведено три основні результати Чебичефа, використовуючи його методи, модифіковані Ландау, Ердом$\ddot{\text{o}}$ і, в незначній мірі, Л.Мозером.

Ми вимагаємо ряд лем. Перші з них відносяться до величини

$n!$і${2n \choose n}$.

$n!$Що стосується, ми можемо використовувати наближення Стірлінга

$n! \thicksim n^n e^{-n} \sqrt{2 \pi n}.$

Однак для наших цілей вистачить більш простого кошторису. Так як

$\dfrac{n^n}{n!}$

і у нас є наступна лема.

Лемма 1

$n^n e^{-n} < n! < n^n$.

Доказ

Так як

$(1 + 1)^{2n} = 1 + {2n \choose 1} + \cdot\cdot\cdot + {2n \choose n} + \cdot\cdot\cdot + 1,$

з цього випливає, що

${2n \choose n} < 2^{2n} = 4^n.$

Ця оцінка для не${2n \choose n}$ така сира, як виглядає, бо з формули Стірлінга можна легко побачити, що

${2n \choose n} \thicksim \dfrac{4^n}{\sqrt{\pi n}}.$

Використовуючи індукцію, ми можемо показати для$n > 1$ цього

${2n \choose n} > \dfrac{4^n}{2n},$

і таким чином ми маємо

лема 2

$\dfrac{4^n}{2n} < {2n \choose n} < 4^n.$

Доказ: Зверніть увагу, що${2n + 1 \choose n}$ є одним з двох рівних членів в розширенні$(1 + 1)^{2n + 1}$. Отже, ми також маємо

Лемма 3

${2n + 1 \choose n} < 4^n.$

Доказ

Як вправу ви можете використовувати їх, щоб довести, що якщо

$n = a + b + c + \cdot\cdot\cdot$

потім

$\dfrac{n!}{a! b! c! \cdot\cdot\cdot} < \dfrac{n^n}{a^ab^bc^c \cdot\cdot\cdot}.$

Тепер виведемо інформацію про те, як$n!$ і${2n \choose n}$ фактор як добуток простих чисел. Припустимо,$e_p (n) is the exponent of the prime \(p$ в першій потужності факторизація$n!$, тобто

$n! = \prod p^{e_p (n)}.$

Ми легко доводимо

лема 4

(Лежандр). $e_p (n) = [\dfrac{n}{p}] + [\dfrac{n}{p^2}] + [\dfrac{n}{p^3}] + \cdot \cdot\cdot.$

Доказ

Фактично$[\dfrac{n}{p}]$ це кількість кратних$p$ в$n!$, термін$[\dfrac{n}{p^2}]$ додає додатковий внесок у кратні$p^2$, і так далі, наприклад,

$e_3(30) = [\dfrac{30}{3}] + [\dfrac{30}{9}] + [\dfrac{30}{27}] + \cdot\cdot\cdot = 10 + 3 + 1 = 14.$

Цікавий і іноді корисний альтернативний вираз для$e_p (n)$ дається

$e_p(n) = \dfrac{n - s_p (n)}{p - 1}, $

де$s_p (n)$ являє собою суму цифр$n$ коли$n$ виражається в основі$p$. Таким чином, в базі 3, 30 можна записати 1010 так, що$e_3(30) = \dfrac{30 - 2}{2} = 14$ як і раніше. Доказ загального випадку залишаємо як вправу.

Далі розглянемо склад${2n \choose n}$ як добуток простих чисел. Нехай$E_p(n)$ позначають показник$p$ in${2n \choose n}$, т. Е.

${2n \choose n} = \prod_p p^{E_p(n)}.$

Чітко

$E_p (n) = e_p (2n) - 2 e_p (n) = \sum_i {[\dfrac{2n}{p^i}] - 2\ [\dfrac{n}{p^i}]}.$

Наш альтернативний вираз для$e_p(n)$ врожайності

$E_p(n) = \dfrac{2s_p(n) - s_p(2n)}{p - 1}.$

У першому виразі кожен член у сумі можна легко побачити як 0 або 1, а кількість членів не перевищує показник найвищої потужності$p$, що не перевищує$2n$. Звідси

лема 5

$E_p(n) \le \text{log}_p (2n).$

лема 6

Внесок$p$ до${2n \choose n}$ не перевищує$2n$

Наступні три леми є безпосередніми.

лема 7

Кожен просте в діапазоні$n < p < 2n$ з'являється рівно один раз в${2n \choose n}$

лема 8

Жодне просте значення в діапазоні не$p > \sqrt{2n}$ з'являється більше одного разу${2n \choose n}$

Хоча це не потрібно в наступному, забавно відзначити, що з тих пір$E_2(n) = 2s_2 (n) - s_2 (2n)$ і$s_2(n) = s_2 (2n)$, у нас є$E_2(n) = s_2(n)$.

Як перше застосування леми доведено елегантний результат.

Теорема 1

$\prod_{p \le n} p < 4^n$.

Доказ

Доказ - за допомогою індукції$n$. Приймаємо теорему істинною для цілих чисел$< n$ і розглянемо відмінки$n = 2m$ і$n = 2m + 1$. Якщо$n = 2m$ тоді

$\prod_{p \le 2m} p = \prod_{p \le 2m - 1} p < 4^{2m - 1}$

за індукційною гіпотезою. Якщо$n = 2m + 1$ тоді

$\begin{array} {rcl} {\prod_{p \le 2m + 1} p} & = & {(\prod_{p \le m + 1} p)(\prod_{m + 1 < p < 2m + 1} p)} \\ {} & < & {4^{m + 1} {2m + 1 \choose m} \le 4^{m + 1} 4^m = 4^{2m + 1}} \end{array}$

і індукція завершена.

Це може бути показано набагато більш глибокими методами (Россер), що

$\prod_{p \le n} p < (2.83)^n.$

Насправді теорема простих чисел еквівалентна

$\sum_{p \le n} \text{log } p \thicksim n.$

З теореми 1 можна зробити висновок

Теорема 2

$\pi (n) < \dfrac{cn}{\text{log} n}. $

Доказ

Чітко

$4^n > \prod_{p \le n} p > \prod_{\sqrt{n} \le p \le n} p > \sqrt{n} ^{\pi (n) - \pi (\sqrt{n})}$

Беручи логарифми, отримуємо

\ (n\ текст {журнал} 4 > (\ pi (n) -\ pi (\ sqrt {n}))\ dfrac {1} {2}\ текст {лог} n)

або

$\pi(n) - \pi(\sqrt{n}) < \dfrac{n \cdot 4 \text{log } 2}{\text{log } n}$

або

$\pi (n) < (4 \text{log } 2) \dfrac{n}{\text{log } n} + \sqrt{n} < \dfrac{cn}{\text{log } n}$.

Далі ми доводимо

Теорема 3

$\pi(n) > \dfrac{cn}{\text{log} n}$.

Доказ

Для цього використовуємо леми 6 і 2. З них отримуємо

$(2n)^{\pi(2n)} > {2n \choose n} > \dfrac{4^n}{2n}.$

Беручи логарифми, ми знаходимо, що

$(\pi (n) + 1) \text{log } 2n > \text{log } (2^{2n}) = 2n \text{log } 2.$

Таким чином, для рівних$m$

$\pi(m) + 1 > \dfrac{m}{\text{log } m} \text{log } 2$

і результат випливає.

Далі ми отримуємо екстрим для$S(x) = \sum_{p \le x} \dfrac{\text{log }p}{p}.$ Беручи логарифм,$n! = \prod_p p^{e_p}$ ми знаходимо, що

$n \text{log } n > \text{log } n! = \sum e_p (n) \text{log } p > n (\text{log } n - 1).$

Читач може виправдати, що помилка, введена при$e_p(n)$ заміні на$\dfrac{n}{p}$ (звичайно$e_p(n) = \sum [\dfrac{n}{p^i}]$) досить мала, що

$\sum_{p \le n} \dfrac{n}{p} \text{log } p = n \text{log } n + O(n)$

або

$\sum_{p \le n} \dfrac{\text{log }p}{p} = \text{log } n + O(1)$.

Тепер ми можемо довести

Теорема 4

$R(x) = \sum_{p \le x} \dfrac{1}{p} = \text{log log } x + O(1)$.

Доказ

Фактично

$\begin{array} {rcl} {R(x)} & = & {\sum_{n = 2}^{x} \dfrac{S(n) - S(n - 1)}{\text{log } n}} \\ {} & = & {\sum_{n = 2}^{x}S(n) (\dfrac{1}{\text{log } n} - \dfrac{1}{\text{log }(n + 1)}) + O(1)} \\ {} & = & {\sum_{n = 2}^{x} (\text{log } n + O(1)) \dfrac{\text{log }(1 + \dfrac{1}{n}}{(\text{log } n) \text{log } (n + 1)} + O(1)} \\ {} & = & {\sum_{n = 2}^{x} \dfrac{1}{n \text{log } n} + O(1)} \\ {} & = & {\text{log log } x + O(1)} \end{array}$

за бажанням.

Ми зараз окреслимо доказ Чебичефа

Теорема 5

Якщо$\pi(x) \thicksim \dfrac{cx}{\text{log }x}$, то$c = 1$.

Доказ

Так як

$\begin{array} {rcl} {R(x)} &= & {\sum_{n = 1}^{x} \dfrac{\pi(n) - \pi(n - 1)}{n}} \\ {} &= & {\sum_{n = 1}^{x} \dfrac{\pi(n)}{n^2} + O(1)} \end{array}$

$\pi(x) \thicksim \dfrac{cx}{\text{log }x}$означало б

$\sum_{n = 1}^{x} \dfrac{\pi(n)}{n^2} \thicksim c\text{log log }x$.

Але ми вже знаємо, що$\pi(x) \thicksim \text{log log } x$ так випливає$c = 1$.

Далі наведемо доказ Постулату Бертрана, розробленого близько десяти років тому (Л.Мозер). Щоб доказ пройшов більш гладко, ми лише доводимо дещо слабкіше.

Теорема 6: Постулат Бертрана

Для кожного цілого числа$r$ існує просте число$p$ з

$3 \cdot 2^{2r - 1} < p < 3 \cdot 2^{2r}$.

Ми повторюємо кілька наших лем в тому вигляді, в якому вони будуть використовуватися.

Якщо$n < p < 2n$ потім$p$ відбувається рівно один раз в${2n \choose n}$.
Якщо$2 \cdot 2^{2r - 1} < p < 3 \cdot 2^{2r - 1}$ потім$p$ не відбувається в${3 \cdot 2^{2r} \choose 3 \cdot 2^{2r - 1}}$.
Якщо$p > 2^{r + 1}$ потім$p$ відбувається не більше одного разу в${3 \cdot 2^{2n} \choose 3 \cdot 2^{2n - 1}}$.
Жодне просте не відбувається більше$2r + 1$ разів${3 \cdot 2^{2r} \choose 3 \cdot 2^{2r - 1}}$

Ми тепер порівняємо${3 \cdot 2^{2r} \choose 3 \cdot 2^{2r - 1}}$ і

${2^{2r} \choose 2^{2r - 1}} {2^{2r - 1} \choose 2^{2r - 2}} \cdot \cdot \cdot {2 \choose 1} {{2^{r + 1} \choose 2^r}{2^r \choose 2^{r - 1}} \cdot\cdot\cdot {2 \choose 1} }^{2r}.$

Припустимо, що в діапазоні немає прайма$3 \cdot 2^{2r - 1} < p < 3 \cdot 2^{2r}$. Потім, нашими лемами, ми виявляємо, що кожне просте, що зустрічається в першому виразі, також зустрічається у другому з принаймні такою ж високою кратністю; тобто другий вираз не менше першого. З іншого боку, спостерігаючи, що для$r \ge 6$

$3 \cdot 2^{2r} > (2^{2r} + 2^{2r - 1} + \cdot\cdot\cdot + 2) + 2r(2^{r + 1} + 2r + \cdot\cdot\cdot + 2),$

і інтерпретуючи${2n \choose n}$ як кількість способів вибору$n$ предметів з$2n$, робимо висновок, що другий вираз дійсно менше першого. Це протиріччя доводить теорему, коли$r > 6.$ Прості числа 7, 29, 97, 389 і 1543 показують, що теорема також вірна для$r \le 6$.

Доказ Постулату Бертрана цим методом залишають як вправу.

Постулат Бертрана може бути використаний для доведення наступних результатів.

(1) ніколи не$\dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}$ є цілим числом.

(2) Кожне ціле число > 6 можна записати як суму різних простих чисел.

(3) Кожен простий$p_n$ може бути виражений у формі

$p_n = \pm 2 \pm 3 \pm 5 \pm \cdot\cdot\cdot \pm p_{n - 1}$

з похибкою не більше 1 (Щерк).

(4) Рівняння$\pi(n) = \varphi (n)$ має рівно 8 розв'язків.

Близько 1949 року сенсація була створена відкриттям Ердом os і Сельбергом елементарного доказу теореми про просте число. Головним новим результатом стала наступна оцінка, доведена елементарно:

$\sum_{p \le x} \text{log}^2 p + \sum_{pq \le x} \text{log }p\text{log }q = 2x \text{log } x + O(x)$.

Хоча нерівність Сельберга все ще далека від теореми про просте число, остання може бути виведена з неї різними способами, не вдаючись до будь-яких подальших теоретичних результатів чисел. Було дано кілька доказів цієї леми, можливо, найпростіший через Татузаву та Ісекі. Оригінальний доказ Сельберга залежить від розгляду функцій

$\lambda_n = \lambda_{n, x} = \sum_{d|n} \mu (d) \text{log}^2 \dfrac{x}{d}$

$T(x) = \sum_{n = 1}^{x} \lambda_n x^n$.

Десь п'ять років тому Дж. Ламбек і Л.Мозер показали, що можна довести лему Сельберга абсолютно елементарно, тобто використовуючи лише властивості inte- gers. Одним з основних інструментів для цього є наступний раціональний аналог функції логарифма. Нехай

$h(n) = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}$і$\ell_k(n) = h(kn) - h(k).$

Доведемо досить елементарно, що

$|\ell_k (ab) - \ell_k (a) - \ell_k (b)| < \dfrac{1}{k}.$

Встановлені нами результати корисні при дослідженні величини арифметичних функцій$\sigma_k(n)$,$\varphi_k(n)$ і$\omega_k(n)$. Оскільки вони залежать не тільки від величини,$n$ але й сильно від арифметичної структури,$n$ ми не можемо розраховувати на їх наближення за елементарними функціями аналізу. Проте побачимо, що «в середньому» ці функції мають досить просту поведінку.

Якщо$f$ і$g$ є функціями, для яких

$f(1) + f(2) + \cdot\cdot\cdot + f(n) \thicksim g(1) + g(2) + \cdot\cdot\cdot g(n)$

ми говоримо, що$f$ і$g$ мають однаковий середній порядок. Ми побачимо, наприклад, що середній порядок$\tau(n)$ - це журнал$n$, що з$\sigma(n)$ є$\dfrac{\pi ^2}{6} n$ і що$\varphi (n)$ є$\dfrac{6}{\pi ^2} n$.

Розглянемо спочатку чисто евристичний аргумент для отримання середнього значення$\sigma_k(n)$. Ймовірність того, що$r\ |\ n$ є$\dfrac{1}{r}$ і якщо$r\ |\ n$ тоді$\dfrac{n}{r}$$(\dfrac{n}{r})^k$ сприяє$\sigma_k (n)$. Таким чином,$\sigma_k (n)$ очікуване значення

$\begin{array} {rcl} {\dfrac{1}{1} (\dfrac{n}{1})^k} & + & {\dfrac{1}{2} (\dfrac{n}{2})^k + \cdot\cdot\cdot + \dfrac{1}{n} (\dfrac{n}{n})^k} \\ {} & = & {n^k(\dfrac{1}{1^{k + 1}} + \dfrac{1}{2^{k + 1}} + \cdot\cdot\cdot + \dfrac{1}{n^{k + 1}})} \end{array}$

Для$k = 0$ цього буде приблизно$n \text{log } n$. Бо$n \ge 1$ це буде приблизно$n^k \zeta (k + 1)$, наприклад, для$n = 1$ нього буде приблизно$n \zeta(2) = n \dfrac{\pi ^2}{6}$.

Перш ніж перейти до доведення та уточнення деяких з цих результатів, розглянуто деякі застосування інверсії порядку підсумовування у певних подвійних сумах.

$f$Дозволяти арифметичну функцію і пов'язувати з нею функцію

$F(n) = \sum_{d = 1}^{n} f(d)$

і$g = f \times I$, т. е.

$g(n) = \sum_{d|n} f(d).$

Ми отримаємо два вирази для

$\mathcal{F} (x) = \sum_{n = 1}^{x} g(n)$.

$\mathcal{F}(x)$це сума

$2019-11-05 7.25.30.png$

Додавання уздовж вертикальних ліній у нас

$\sum_{d = 1}^{x} [\dfrac{x}{d}] f(d)$;

якщо скласти уздовж послідовних діагональних ліній, що$f(1)$ починаються з і з «нахилами» −1, −2, −3,.,., отримаємо

$\sum_{n = 1}^{x} F([\dfrac{x}{n}]).$

Таким чином

$\sum_{n = 1}^{x} \sum_{d|n} f(d) = \sum_{d = 1}^x [\dfrac{x}{d}] f(d) = \sum_{n = 1}^x F([\dfrac{x}{n}]).$

Особливий випадок$f = \mu$ дає

$1 = \sum_{d = 1}^{x} \mu(d) [\dfrac{x}{d}] = \sum_{n = 1}^{x} M([\dfrac{x}{n}]),$

які ми раніше розглядали.

Від

$\sum_{d = 1}^x \mu(d) [\dfrac{x}{d}] = 1$,

ми маємо, при знятті дужок, допускаючи помилку, і діливши на$x$,

$|\sum_{d = 1}^{x} \dfrac{\mu(d)}{d}| < 1$.

Власне, відомо, що

$\sum_{d = 1}^{\infty} \dfrac{\mu(d)}{d} = 0$,

але доказ цього настільки ж глибокий, як і теорема про просте число.

Далі розглянемо випадок$f = 1$. Тут ми отримуємо

$\sum_{n = 1}^{x} \tau(n) = \sum_{n = 1}^{x} [\dfrac{x}{n}] = x \log x+ O(x)$.

У випадку$f = I_k$ ми виявимо, що

$\sum_{n = 1}^{x} \sigma_k (n) = \sum_{d = 1}^{x} d^k [\dfrac{x}{d}] = \sum_{n = 1}^{x} (1^k + 2^k + \cdot\cdot\cdot + [\dfrac{x}{n}])$.

У випадку$f = \varphi$, нагадавши, що$\sum_{d|n} \varphi (d) = n$, отримуємо

$\dfrac{x(x + 1)}{2} = \sum_{n = 1}^{x} \sum_{d |n} \varphi (d) = \sum_{d = 1}^{x} [\dfrac{x}{d}] \varphi (d) = \sum_{n = 1}^{x} \Phi (\dfrac{x}{n})$,

де$\Phi (n) = \sum_{d = 1}^{n} \varphi (d)$. Від цього ми легко дістаємося

$\sum_{d = 1}^{x} \dfrac{\varphi (d)}{d} \ge \dfrac{x + 1}{2}$,

що показує, що, в середньому,$\varphi (d) > \dfrac{d}{2}$.

Також можна використовувати подібну інверсію порядку підсумовування для отримання наступної важливої другої формули інверсії M$\ddot{o}$ bius:

Теорема

Якщо$G(x) = \sum_{n = 1}^{x} F([\dfrac{x}{n}])$ тоді$F(x) = \sum_{n = 1}^{x} \mu(n) G([\dfrac{x}{n}]).$

Доказ: $\begin{array} {rcl} {\sum_{n = 1}^{x} \mu(n) G([\dfrac{x}{n}])} &= & {\sum_{n = 1}^{x} \mu(n) \sum_{n = 1}^{[x/n]} F([\dfrac{x}{mn}])} \\ {} & = & {\sum_{k = 1}^{x} F([\dfrac{x}{n}]) \sum_{n |k}^{x} \mu (n) = F(x).} \end{array}$

Розглянемо ще раз нашу оцінку

$\tau (1) + \tau(2) + \cdot\cdot\cdot + \tau(n) = n \log n + O(n).$

Корисно отримати геометричне уявлення про цей результат. Ясно$\tau(r)$ це кількість точок решітки на гіперболі$xy = r$,$x > 0$,$y > 0$. Крім того, кожна точка решітки$(x, y)$$x > 0$,$y > 0$,$xy \le n$, лежить на деякій гіперболі$xy = r$,$r \le n$. Звідси

$\sum_{n = 1}^{n} \tau(r)$

- кількість точок решітки в регіоні$xy \le n$,$x > 0$,$y > 0$. Якщо підсумувати по вертикальних лініях, то$x = 1, 2, ..., n$ отримаємо знову

$\tau(1) + \tau (2) + \cdot\cdot\cdot \tau(n) = [\dfrac{n}{1}] + [\dfrac{n}{2}] + \cdot\cdot\cdot + [\dfrac{n}{n}]$.

У цьому підході симетрія$xy = n$ про$x = y$ підказує, як поліпшити цю оцінку та отримати менший термін помилки.

$2019-11-05 9.57.3png$

Використовуючи симетрію наведеного вище малюнка, ми маємо, з$u = [\sqrt{n}]$ і$h(n) = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}$,

$\begin{array} {rcl} {\sum_{r = 1}^{n} \tau(r)} &= & {2([\dfrac{n}{1}] + \cdot\cdot\cdot + [\dfrac{n}{u}]) - u^2} \\ {} &= & {2nh(u) - n + O(\sqrt{n})} \\ {} &= & {2n \log \sqrt{u} + (2 \gamma - 1)n + O(\sqrt{n})} \\ {} &= & {n \log n + (2 \gamma - 1)n + O(\sqrt{n}).} \end{array}$

Приступаємо зараз до$\sum \sigma (r)$ нас

$\sigma(1) + \sigma (2) + \cdot\cdot\cdot \sigma(n) = 1\ [\dfrac{n}{1}] + 2\ [\dfrac{n}{2}] + \cdot\cdot\cdot n\ [\dfrac{n}{n}].$

З метою отримання оцінки множини$\sum_{n = 1}^{x} \sigma (n)$$k = 1$ в особистості (отриманої раніше)

$\sigma_k(1) + \sigma_k (2) + \cdot\cdot\cdot \sigma_k (x) = \sum_{n = 1}^{x} (1^k + 2^k + \cdot\cdot\cdot + [\dfrac{x}{n}]^k).$

У нас є відразу

$\begin{array} {rcl} {\sigma (1) + \sigma (2) + \cdot\cdot\cdot \sigma (x)} & = & {\dfrac{1}{2} \sum_{n = 1}^{x} [\dfrac{x}{n}] [\dfrac{x}{n} + 1]} \\ {} & = & {\dfrac{1}{2} \sum_{n = 1}^{\infty} \dfrac{x^2}{n^2} + O(x \log x) = \dfrac{x^2 \zeta (2)}{2} + O(x \log x)} \\ {} & = & {\dfrac{\pi^2 x^2}{12} + O(x \log x).} \end{array}$

Для отримання аналогічних оцінок$\varphi (n)$ відзначимо, що$\varphi (r)$ це кількість точок решітки, які лежать на відрізку лінії$x = r$$0 < y < r$, і видно з початку. (Точку ($x, y$) можна побачити, якщо$(x, y) = 1$.) Таким чином$\varphi (1) + \varphi(2) + \cdot\cdot\cdot + \varphi (n)$ визначається кількість видимих точок решітки в області с$n > x > y > 0$.

Розглянемо набагато більш загальну проблему, а саме оцінити кількість видимих точок решітки у великому класі регіонів.

Евристично ми можемо сперечатися наступним чином. $(x, y)$Точка невидима в силу простого$p$ if$p\ |\ x$ і$p\ |\ y$. Імовірність того, що це відбувається, є$\dfrac{1}{p^2}$. Звідси ймовірність того, що точка невидима, є

$\prod_p (1 - \dfrac{1}{p^2}) = \prod_p (1 + \dfrac{1}{p^2} + \dfrac{1}{p^4} + \cdot\cdot\cdot)^{-1} = \dfrac{1}{\zeta (2)} = \dfrac{6}{\pi^2}.$

При цьому число видимої точки решітки має бути$\dfrac{6}{\pi^2}$ помножене на площу π області. Зокрема, середній порядок$\varphi(n)$ повинен бути приблизно$\dfrac{6}{\pi^2} n$.

Зараз ми окреслимо доказ того, що в певних великих регіонах частка видимих точок решітки, що містяться в регіоні, приблизно$\dfrac{6}{\pi^2}$.

Le$R$ бути областю в площині, що має кінцеву міру Йордана і скінченний периметр. Нехай$tR$ позначають область, отриману збільшенням$R$ радіально на$t$. $M (tR)$Дозволяти площа$tR$,$L(tR)$ кількість точок решітки в$tR$, і$V (tR)$ кількість видимих точок решітки в$tR$.

Інтуїтивно зрозуміло, що

$L(tR) = M(tR) + O(t)$і$M(tR) = t^2 M(R)$.

Застосування формули інверсії до

$L(tR) = V(tR) + V(\dfrac{t}{2} R) + V(\dfrac{t}{3} R) + \cdot\cdot\cdot$

ми знаходимо, що

$\begin{array} {V(tR)} & = & {\sum_{d = 1} L(\dfrac{t}{d} R) \mu (d) = \sum_{d = 1} M(\dfrac{t}{d} R) \mu (d)} \\ {} & \approx & {M(tR) \sum_{d = 1} \dfrac{\mu (d)}{d^2} \approx M(tR) \dfrac{6}{\pi^2} = t^2 M(R) \dfrac{6}{\pi^2}.} \end{array}$

З$t = 1$ і$R$ регіоном$n > x > y > 0$, у нас є

$\varphi (1) + \varphi (2) + \cdot\cdot\cdot \varphi(n) \approx \dfrac{n^2}{2} \cdot \dfrac{6}{\pi^2} = \dfrac{3}{\pi^2} n^2$

Було показано (Чоула), що термін помилки тут не може бути зведений до$O(n \log \log \log n)$. Вальфіц показав, що його можна замінити на$O(n \log ^{\dfrac{3}{4}} n)$.

Ерд$ddot{o}$ с і Шапіро показали, що

$\varphi(1) + \varphi (2) + \cdot\cdot\cdot \varphi(n) - \dfrac{3}{\pi^2} n^2$

змінюється знак нескінченно часто.

Пізніше ми застосуємо нашу оцінку$\varphi(1) + \varphi (2) + \cdot\cdot\cdot \varphi(n)$ до теорії розподілів квадратичних залишків.

Наш результат також можна інтерпретувати як сказавши, що якщо пара цілих чисел$(a, b)$

вибираються випадковим чином ймовірність того, що вони будуть відносно простими є$\dfrac{6}{\pi^2}$.

На цьому етапі ми без доказів заявляємо ряд пов'язаних результатів.

Якщо$(a, b)$ вибрано випадковим чином, очікуване значення$(a, b)$ дорівнює$\dfrac{\pi^2}{6}$.

Якщо$f(x)$ є одним з певного класу арифметичних функцій, що включає$x^{\alpha}$$0 < \alpha < 1$, то ймовірність того, що$(x, f(x)) = 1$ є$\dfrac{6}{\pi^2}$, і її очікуване значення дорівнює$\dfrac{\pi^2}{6}$.

Це і пов'язані з ними результати довели Ламбек і Мозер.

Імовірність того, що$n$ числа, вибрані випадковим чином, є відносно простими, є$\dfrac{1}{\zeta(n)}$.

Кількість$Q(n)$ квадратних чисел під$n$ is$\thicksim \dfrac{6}{\pi^2} n$ і кількість$k$ го$O_k (n)$ безпотужних чисел під$n$ є$\dfrac{n}{\zeta(k)}.$ Перший результат випливає майже відразу з

$\sum Q (\dfrac{n^2}{r^2}) = n^2,$

так що за формулою інверсії

$Q(n^2) = \sum \mu(r) [\dfrac{n}{r}]^2 \thicksim n^2 \zeta (2).$

Більш детальний аргумент дає

$Q(x) = \dfrac{6x}{\pi^2} + O(\sqrt{x}).$

Ще один досить кумедний пов'язаний результат, доказ якого залишається як вправа, полягає в тому, що

$\sum_{(a, b) = 1} \dfrac{1}{a^2b^2} = \dfrac{5}{2}.$

Результат на$Q(x)$ можна записати у формі

$\sum_{n = 1}^{x} |\mu(n)| \thicksim \dfrac{6}{\pi^2} x$

Можна попросити оцінки для

$\sum_{n = 1}^{x} \mu(n) = M(x).$

Дійсно, відомо (але важко довести) це$M(x) = o(x)$.

Звернемо увагу на$\omega (n)$. У нас є

$\omega(1) + \omega(2) + \cdot\cdot\cdot \omega(n) = \sum_{p \le n} [\dfrac{n}{p}] \thicksim n\log \log n$.

Таким чином, середнє значення колоди$\omega(n)$ - це колода$n$.

Те ж саме слід аналогічним чином для$\Omega (n)$

Порівняно недавня розробка за цими напрямками, обумовлена Ерд$\ddot{o}$ s, Kac, Leveque, Tatuzawa та іншими, - це ряд теорем, з яких характерно наступне.

$A(x; \alpha, \beta)$Дозволяти кількість цілих чисел,$n \le x$ для яких

$\alpha \sqrt{\log \log n} + \log \log n < \omega (n) < \beta \sqrt{\log \log n} + \log \log n.$

Тоді

$\text{lim}_{x \to \infty} \dfrac{A(x; \alpha, \beta)}{x} = \dfrac{1}{\sqrt{2\pi}} \int_{\alpha}^{\beta} e^{-\dfrac{u^2}{2}} du.$

Таким чином, ми маємо, наприклад, що$\omega (n) < \log \log n $ приблизно половина часу.

Можна також довести (Tatuzawa), що подібний результат тримає для$B(x; \alpha, \beta)$, кількість цілих чисел у множині$f(1)$,,$f(2)$,,$f(x)$ ($f(x)$є нескорочуваним поліном з інтегральними коефіцієнтами) для якого$\omega (f(n))$ лежить в діапазоні, подібному до тих, які прописані для$\omega(n)$.

Ще одним типом результату, який має значну застосовність, є наступний.

Кількість$C(x, \alpha)$ цілих чисел,$\le x$ що мають простий дільник$> x \alpha$,$1 > \alpha > \dfrac{1}{2}$, дорівнює$\thicksim -x \log \alpha$. По суті, у нас є

$\begin{array} {rcl} {C(x, \alpha)} & = & {\sum_{x^{alpha} < p < x} \dfrac{x}{p} \thicksim x \sum_{x^{alpha} < p x} \dfrac{1}{p}} \\ {} & = & {x (\log \log x - \log \log \alpha)} \\ {} & = & {x (\log \log x - \log \log x - \log \alpha) = - x \log \alpha.} \end{array}$

Наприклад, щільність чисел, що мають простий множник, що перевищує їх квадратний корінь, є log 2$\approx$ .7.

До теперішнього часу ми розглядали переважно середню поведінку арифметичних функцій. Ми також могли б запитати про абсолютні межі. Можна без праці довести, що

$1 > \dfrac{varphi(n) \sigma(n)}{n^2} > \epsilon > 0$для всіх$n$.

Також відомо, що

$n > \varphi(n) > \dfrac{cn}{\log\log n}$

$n < \sigma(n) < cn \log\log n.$

Що стосується$\tau(n)$, то нескладно показати, що

$\tau (n) > (\log n)^k$

нескінченно часто на кожен$k$ час$\tau(n) < n^{\epsilon}$ на кожен$\epsilon$ і$n$ досить великий.

Ми констатуємо, але не доводимо головну теорему в цих напрямках.

Якщо$\epsilon > 0$ тоді

$\tau(n) < 2^{(1 + \epsilon) \log n / \log \log n}$для всіх$n > n_0(\epsilon)$

поки

$\tau(n) > 2^{(1 - \epsilon) \log n / \log \log n}$нескінченно часто.

Дещо інший тип задачі щодо середнього значення арифметичних функцій був предметом магістерської дисертації пана Р.Троллопа Університету Альберти пару років тому.

$s_r(n)$Дозволяти сума цифр n при записі в основі$r$. Мірський довів, що

$s_r(1) + s_r(2) + \cdot \cdot \cdot + s_r(n) = \dfrac{r - 1}{2} n \log_r n + O(n).$

Містер Троллоп розглядав подібні суми, де елементи зліва проходять через певні послідовності, такі як прості числа, квадрати тощо.

Ще один досить кумедний результат, який він отримав, стверджує, що

$\dfrac{s_1(n) + s_2(n) + \cdot\cdot\cdot s_n(n)}{n^2} \thicksim 1 - \dfrac{\pi^2}{12}.$