1.2: Арифметичні функції

Наступна тема, яку ми розглянемо, - це арифметичні функції. Вони утворюють основні об'єкти, що викликають занепокоєння в теорії чисел. Ми вже згадували дві такі функції двох змінних, g.cd. і l.c.m. з\(m\)\((m, n)\) і\(n\), що позначаються і\([m, n]\) відповідно, а також функції\(c(n)\) і\(p(n)\). Більш пряме занепокоєння на даному етапі викликають функції.

\(\begin{array} {lcl} {\pi(n) = \sum_{p \le n} 1} & & {\text{the number of primes \(n\)не перевищує\(n\);}}\\ {w (n) =\ sum_ {p | n} 1} & & {\ text {кількість різних простих чинників\(n\);}}\\ {\ omega (n) =\ sum_ {p\ le n} 1} & {\ text {кількість простих чисел, що\(n\) не перевищує\(n\);}}\\\ Omega (n) =\ sum_ {p^ {i}\ le n} 1} & & {\ text {кількість простих множників\(n\);}}\\ {\ tau (n) =\ sum_ {d | n} 1} & {\ text {кількість дільників\(n\);}}\\ {\ sigma (n) =\ sum_ {d|n} d} & {\ text {сума дільників\(n\)}}\\ {\ varphi (n) =\ сума _ {(a, n) = 1\\ 1\ ле а\ ле п} 1} & {\ text {функція Ейлера totient;}}\ end {масив}\)

функція Ейлера totient підраховує кількість цілих чисел\(\le n\) і відносно простих до\(n\).

У розділі ми будемо особливо стурбовані функціями\(\tau(n)\)\(\sigma(n)\), і\(\varphi(n)\). Вони мають важливу властивість, що якщо

\(n = ab\)і\((a, b) = 1\)

потім

\(f(ab) = f(a) f(b)\).

Будь-яка функція, що задовольняє цю умову, називається слабо мультиплікативної, або просто мультиплікативної.

Узагальнення\(\tau(n)\) і\(\sigma(n)\) надається

\(\sigma_k (n) = \sum_{d|n} d^k\). то сума\(k^{\text{th}}\) ступенів дільників\(n\),

так як\(\sigma_0 (n) = \tau(n)\) і\(\sigma_1 (n) = \sigma (n)\).

\(\varphi\)Функція також може бути узагальнена різними способами. Пізніше ми розглянемо узагальнення за Йорданом,\(\varphi_k(n) =\) числом\(k\) -кортежів, gcd.\(\le n\) яких відносно просте до n. Виведемо деякі елементарні властивості цих і тісно пов'язаних функцій, а також виведемо деякі особливі розв'язані і нерозв'язані проблеми щодо них. Потім ми обговоримо теорію, яка дає єдиний підхід до цих функцій і виявляє несподівані взаємозв'язки між ними. Пізніше ми обговоримо величину цих функцій. Функції\(\omega(n)\), і\(\Omega(n)\), зокрема,\(\pi(n)\) мають різний характер і їм буде приділена особлива увага.

Припустимо, в чому випливає, що основна влада факторизації\(n\) задається

\(n = p_{1}^{\alpha_1} p_{2}^{\alpha_2} \cdot\cdot\cdot p_{s}^{\alpha_s}\)або коротко\(n = \prod p^{\alpha}\).

Зауважимо, що 1 не є простим і сприймаємо як належний доказовий результат, який, крім порядку, факторизація є унікальною.

У плані цієї факторизації функції\(\sigma_{k}(n)\) і легко\(\varphi(n)\) визначаються. Не важко помітити, що терміни в розширенні продукту

\(\prod_{p|n} (1 + p^k + p^{2k} + \cdot\cdot\cdot + p^{\alpha k})\)

є саме дільниками\(n\) підвищення до\(k^{\text{th}\) влади. Отже, ми маємо бажане розширення для\(\sigma_{k}(n)\). Зокрема

\(\tau (n) = \sigma_0 (n) = \prod (\alpha + 1)\),

і

\(\sigma(n) = \sigma_1 (n) = \prod_{p|n} (1 + p + p^{2} + \cdot\cdot\cdot + p^{\alpha}) = \prod_{p|n} \dfrac{p^{\alpha + 1} - 1}{p - 1}\),

наприклад\(60 = 2^2 \cdot 3^1 \cdot 5^1\),

\(\tau(60) = (2 + 1)(1 + 1)(1 + 1) = 3 \cdot 2 \cdot 2 = 12\),

\(\sigma(60) = (1 + 2 + 2^2) ( 1+ 3) ( 1+ 5) = 7 \cdot 4 \cdot 6 = 168.\)

Ці формули розкривають мультиплікативний характер\(\sigma_k(n)\).

Для отримання явної формули використовується наступний добре відомий комбінаторний принцип.\(\varphi (n)\)

Принцип включення і виключення

Дані\(N\) об'єкти, кожен з яких може мати або не мати жодної з характеристик.

\(A_1, A_2, ... .\)

\(N(A_i, A_j, ...)\)Дозволяти кількість об'єктів, що мають характеристики\(A_i, A_j, ...\) і, можливо,. інші. Тоді кількість об'єктів, які не мають жодної з цих властивостей, дорівнює

\(N - \sum N(A_i) + \sum_{i < j} N(A_i, A_j) - \sum_{i < j < k} N(A_i, A_j, A_k) +\cdot\cdot\cdot,\)

де підсумовування поширюється на всі комбінації індексів 1, 2,...,\(n\) в групах по один, два, три і так далі, а знаки термінів чергуються.

Ціле число буде відносно простим і\(n\) тільки якщо воно не ділиться ні на один з простих множників\(n\). Нехай\(A_1, A_2 , ... , A_s\) позначають подільність\(p_1, p_2, ... , p_s\) відповідно. Потім за комбінаторним принципом, викладеному вище

\(\varphi(n) = n - \sum_i \dfrac{n}{p_i} + \sum_{i < j} \dfrac{n}{p_i p_j} - \sum_{i < j < k} \dfrac{n}{p_i p_j p_k} + \cdot\cdot\cdot\).

Цей вираз можна врахувати у вигляді

\(\varphi (n) = n \prod_{p|n} (1 - \dfrac{1}{p}),\)

напр

\(\varphi (60) = 60 (1 - \dfrac{1}{2}) (1 - \dfrac{1}{3}) (1 - \dfrac{1}{5}) = 60 \cdot \dfrac{1}{2} \cdot \dfrac{2}{3} \cdot \dfrac{4}{5}. = 16.\)

Аналогічний аргумент показує, що

\(\varphi_{k}(n) = n^{k} \prod_{p|n} ( 1- \dfrac{1}{p^{k}}).\)

Формулу для також\(\varphi(n)\) можна записати у вигляді

\(\varphi(n) = n \sum_{d |n} \dfrac{\mu (d)}{d},\)

де\(\mu (d)\) приймає значення 0, 1, −1. Дійсно,\(\mu (d) = 0\) якщо\(d\) має квадратний коефіцієнт\(\mu (1) = 1\), і\(\mu(p_1p_2 \cdot\cdot\cdot p_s) = (−1)^s\). Це дає певну мотивацію для визначення функції\(\mu(n)\) таким чином. Ця функція відіграє несподівано важливу роль в теорії чисел.

Наше визначення\(\mu(n)\) розкриває його мультиплікативну природу, але воно все ще здається досить штучним. Однак він має ряд дуже важливих властивостей, які можуть бути використані як альтернативні визначення. Ми доводимо найважливіше з них, а саме

\(\sum_{d | n} \mu(d) = \begin{cases} 1 & \text{if} n = 1,\\ 0 & \text{if} n \ne 1. \end{cases}\)

Оскільки\(\mu(d)= 0\) якщо\(d\) містить коефіцієнт у квадраті, досить припустити,\(n\) що такого фактора немає, тобто\(n = p_1p_2 \cdot\cdot\cdot p_s\). Для такого\(n > 1\)

\(\sum_{d | n} \mu(d) = 1 - {n \choose 1} + {n \choose 2} - \cdot\cdot\cdot = (1 - 1)^n = 0\).

За визначенням\(\mu(1) = 1\) так доведена теорема.

Якщо підсумувати цей результат\(n = 1, 2, ..., x\), отримаємо

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

що є ще одним визначальним співвідношенням.

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

\(M(x) = \sum_{d = 1}{x} \mu (d)\)

потім

\(\sum_{d = 1}^{x} M([\dfrac{x}{d}]) = 1.\)

Це, мабуть, найелегантніше визначення\(\mu\). Ще однією дуже важливою властивістю є те, що

\((\sum_{n = 1}^{\infty} \dfrac{1}{n^{s}}) (\sum_{n = 1}^{\infty} \dfrac{\mu(n)}{n^s} ) = 1.\)

Тепер звернемо увагу на множення Діріхле і ряд.

Розглянемо набір арифметичних функцій. Вони можуть бути об'єднані різними способами, щоб дати нові функції. Наприклад, ми могли б визначити\(f + g\)

\((f + g) (n) = f(n) + g(n)\)

і

\((f \cdot g)(n) = f(n) \cdot g(n)\)

Менш очевидний режим комбінації задається тим\(f \times g\), що визначається

\((f \times g) (n) = \sum_{d|n} f(d) g(\dfrac{n}{d}) = \sum_{dd' = n} f(d) g(d').\)

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

Ця мотивація для даного визначення полягає в наступному. Якщо

\(F(s) = \sum_{n = 1}^{\infty} f(n) n^{-s}\),\(F(s) = \sum_{n = 1}^{\infty} g(n) n^{-s}\), і\(F(s) \cdot G(s) = \sum_{n = 1}^{\infty} h(n) n^{-s},\)

то це легко перевіряється\(h = f \times g\). Таким чином, множення Діріхле арифметичних функцій відповідає звичайному множенню відповідного ряду Діріхле:

\(f \times g = g \times f\),\((f \times g) \times h = f \times (g \times h)\),

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

Давайте тепер визначимо функцію

\(\ell = \ell(n) : 1, 0, 0, ... .\)

Це легко помітити\(f \times \ell = f\). Таким чином, функція\(ell\) є єдністю нашого множення.

Можна без праці довести, що якщо\(f(1) \ne 0\), то\(f\) має зворотне по відношенню до\(ell\). Такі функції називаються регулярними. Таким чином регулярні функції утворюють групу щодо операції\(\times \).

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

Тепер ми введемо функції

\(I_k : 1^k, 2^k, 3^k, ... .\)

Цікаво, що, починаючи тільки з функцій\(\ell\) і\(I_k\), ми можемо побудувати багато арифметичних функцій і їх важливих властивостей.

Для початку ми можемо визначити\(\mu(n)\) по\(\mu = I_{0}^{-1}\). Це означає, звичайно, що\(\mu \times I_0 = \ell\) або

\(\sum_{d | n} \mu(d) = \ell (n)\).

і ми вже бачили, що це визначальна властивість\(\mu\) функції. Ми можемо визначити\(\sigma_{k}\) по

\(\sigma_k = I_0 \times I_k\).

Це означає, що

\(\sigma_k(n) = \sum_{d|n} (d^k \cdot 1),\)

що відповідає нашому більш ранньому визначенню. Особливими випадками є

\(\tau = I_0 \times I_0 = I_0^2\)і\(\sigma = I_0 \times I_1\)

Далі ми можемо визначити

\(\varphi_k = \mu \times I_k = I_0^{-1} \times I_k\).

Це означає, що

\(\varphi_k(n) = \sum_{d|n} \mu(d) (\dfrac{n}{d})^k,\)

які знову можна побачити, щоб відповідати нашому більш ранньому визначенню.

Особливий випадок інтересу тут

\(\varphi = \varphi_1 = \mu \times I_1.\)

Тепер, щоб отримати деякі важливі відносини між нашими функціями, відзначимо так звану формулу інверсії M\(\ddot{\text{o}}\) bius. З нашої точки зору це говорить про те, що

\(g = f \times I_0 \iff f = u \times g\)

Це, звичайно, досить прозоро. У виписаному повному обсязі зазначено, що

\(g(n) = \sum_{d|n} f(d) \iff f(n) = \sum_{d | n} \mu(d) g(\dfrac{n}{d}).\)

У такому вигляді вона значно менш очевидна.

Розглянемо тепер наступні програми. Перший

\(\sigma_k = I_0 \times I_k \iff I_k = \mu \times \sigma_k\).

Це означає, що

\(\sum_{d|n} \mu(d) \sigma_k(\dfrac{n}{d}) = n^k.\)

Важливими особливими випадками є

\(\sum_{d | n} \mu(d) \tau(\dfrac{n}{d}) = 1,\)

і

\(\sum_{d | n} \mu(d) \sigma(\dfrac{n}{d}) = 1.\)

Знову

\(\varphi_k = I_0^{-1} \times I_k \iff I_k = I_0 \times \varphi_k,\)

щоб

\(\sum_{d|n} \varphi_k (d) = n^k,\)

Ми можемо отримати ідентичності дещо іншого виду. Таким чином

\(\sigma_k \times \varphi_k = I_0 \times I_k \times I_0^{-1} \times I_k = I_k \times I_k,\)

і, отже,

\(\sum_{d|n} \sigma_k(d) \varphi_k (\dfrac{n}{d}) = \sum_{d|n}d^{k}(\dfrac{n}{d})^k = \sum_{d|n} n^k = \tau(n) n^k.\)

Особливий випадок інтересу тут

\(\sum_{d|n} \sigma(d) \varphi (\dfrac{n}{d}) = n \tau(n).\)

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

\(f'(n) = -f(n)\)журнал\(n\)

Мотивацію до цього визначення можна побачити з

\(\dfrac{d}{ds} (\sum \dfrac{f(n)}{n^s}) = -\sum \dfrac{(\text{log} n) f(n)}{n^s}.\)

Тепер визначимося

\(\Lambda(n) = \begin{cases} \text{log} p & \text{if} n = p^{\alpha}, \\ 0 & \text{if} n \ne p^{\alpha}. \end{cases}\)

Легко помітити, що

\(\sum_{d|n}\Lambda(d) = \text{log} n\)

У нашому позначенні множення Діріхле ми маємо

\(\Lambda \times I_0 = -I_0^{'},\)

щоб

\(\Lambda = I_0^{-1} \times ( -I_0^{'}) = \mu \times ( -I_0^{'})\)

або

\(\Lambda(n) = \sum_{d|n} \mu(d) \text{ log } (\dfrac{n}{d}) = - \sum_{d|n} \mu(d) \text{ log } d.\)

Давайте тепер інтерпретуємо деякі наші результати з точки зору ряду Діріхле. У нас листування

\(F(s) \leftrightarrow f(n)\)якщо\(F(s) = \sum \dfrac{f(n)}{n^s},\)

і ми знаємо, що множення Діріхле арифметичних функцій відповідає звичайному множенню для ряду Діріхле. Починаємо з

\(f \leftrightarrow F, 1 \leftrightarrow 1\), і\(I_0 \leftrightarrow \zeta(s).\)

Крім того

\(I_k \leftrightarrow \sum_{n = 1}^{\infty} \dfrac{n^k}{n^s} = \zeta (s - k).\)

Також

\(\mu \leftrightarrow \dfrac{1}{\zeta (s)}\)і\(I_0^{'} \leftrightarrow \sum \dfrac{-\text{ log }n}{n^s} = \zeta '(s).\)

Це дає

\(\sum \dfrac{\sigma_k(n)}{n^s} = \zeta (s) \zeta (s - k).\)

Особливими випадками є

\(\sum \dfrac{\tau (n)}{n^s} = \zeta^2 (s)\)

і

\(\sum \dfrac{\sigma (n)}{n^s} = \zeta(s) \zeta (s - 1).\)

Знову

\(\sum \dfrac{\mu(n){n^s) = \dfrac{1}{\zeta(s)}\)

і

\(\sum \dfrac{\varphi_k (n)}{n^s} = \dfrac{\zeta (s - k)}{\zeta (s)},\)

з особливим корпусом

\(\sum \dfrac{\varphi (n)}{n^s} = \dfrac{\zeta (s - 1)}{\zeta (s)}.\)

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

\(\begin{array} {rcl} {\sum \dfrac{\tau (n)}{n^2}} & = & {\zeta^2 (2) = \dfrac{\pi ^4}{36},} \\ {\sum \dfrac{\sigma_4 (n)}{n^2}} & = & {\zeta (2) \cdot \zeta (4) = \dfrac{\pi^2}{6} \cdot \dfrac{\pi^4}{90} = \dfrac{\pi^6}{540}.} \\ {\sum \dfrac{\mu (n)}{n^2}} & = & {\dfrac{6}{\pi^2}} \end{array}\)

Що стосується нашої\(\Lambda\) функції, то ми мали

\(\Lambda = I_{0}^{-1} \times I_0^{'};\)

це означає, що

\[\sum_{n -= 1}^{\infty} \dfrac{\Lambda (n)}{n^s} = \dfrac{-\zeta'(s)}{\zeta (s)}.\]

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

\(\Psi (x) = \sum_{n = 1}^{x} \Lambda(n).\)

Дійсно, ми хочемо показати це\(\Psi(x) \thicksim x\).

Будь-яка інтеграція контуру з правою стороною (1) передбачає, звичайно, необхідність знати, де\(\zeta (s)\) зникає. Це одна з центральних проблем теорії чисел.

Коротко обговоримо деякі інші серії Діріхле.

Якщо\(n = p_{1}^{\alpha_1} p_{2}^{\alpha_2} \cdot\cdot\cdot p_{s}^{\alpha_s} \) визначити

\(\lambda (n) = (-1)^{\alpha_1 + \alpha_2 + \cdot\cdot\cdot + \alpha_s}.\)

\(\lambda\)Функція має властивості, подібні до властивостей\(\mu\) функції. Ми залишаємо як вправу, щоб показати, що

\(\sum_{d|n} \lambda (d) = \begin{cases} 1 & \text{if } n = r^2. \\ 0 & \text{if } n \ne r^2.\end{cases}\)

Зараз

\(\zeta (2s) = \sum \dfrac{s(n)}{n^s}\)де\(s(n) = \begin{cases} 1 & \text{if } n = r^2. \\ 0 & \text{if } n \ne r^2.\end{cases}\)

Отже\(\lambda \times I_0 = s\), т. Е.

\(\sum \dfrac{\lambda (n)}{n^s} \cdot \zeta (s) = \zeta(2s)\)

або

\(\sum \dfrac{\lambda (n)}{n^s} = \dfrac{\zeta (2s)}{\zeta (s)}.\)

Наприклад

\(\sum \dfrac{\lambda (n)} {n^2} = \dfrac{\pi^4}{90} / \dfrac{\pi^2}{6} = \dfrac{\pi^2}{15}.\)

Завершимо короткий огляд іншого типу генеруючих серій, а саме серії Ламберта. Це серії типу

\(\sum \dfrac{f(n) x^n}{1 - x^n}.\)

Легко показано, що якщо\(F = f \times I_0\) тоді

\(\sum \dfrac{f(n)x^n}{1 - x^n} = \sum F(n) x^n.\)

Цікавими особливими випадками є

\(f = I_0, \sum \dfrac{x^n}{1 - x^n} = \sum \tau(n) x^n\);

\(f = \mu, \sum \mu(n) \dfrac{x^n}{1 - x^n} = x\);

\(f = \varphi, \sum \varphi (n) \dfrac{x^n}{1 - x^n} = \sum n x^n = \dfrac{x}{(1 - x)^2}.\)

Наприклад, взявши\(x = \dfrac{1}{10}\) в останньому рівність, отримуємо

\(\dfrac{\varphi(1)}{9} + \dfrac{\varphi(2)}{99} + \dfrac{\varphi(3)}{999} + \cdot\cdot\cdot = \dfrac{10}{81}.\)

Вправа\(\PageIndex{1}\)

Доведіть, що\(\sum_{n = 1}^{\infty} \dfrac{\mu(n) x^n}{1 + x^n} = x - 2x^2.\)

Доведіть, що\(\sum_{n = 1}^{\infty} \dfrac{\lambda(n) x^n}{1 - x^n} = \sum_{n = 1}^{\infty} x^{n^2}.\)

Відповідь

Додайте сюди тексти. Не видаляйте цей текст спочатку.