Средний порядок арифметической функции - Average order of an arithmetic function

В теория чисел, средний порядок арифметической функции - это некоторая более простая или лучше понятная функция, которая "в среднем" принимает те же значения.

Позволять ${displaystyle f}$ быть арифметическая функция. Мы говорим, что средний заказ из ${displaystyle f}$ является ${displaystyle g}$ если

${displaystyle sum _{nleq x}f(n)sim sum _{nleq x}g(n)}$

в качестве ${displaystyle x}$ стремится к бесконечности.

Обычно выбирают аппроксимирующую функцию ${displaystyle g}$ то есть непрерывный и монотонный. Но даже в этом случае средний заказ, конечно, не уникален.

В случаях, когда лимит

${displaystyle lim _{Nightarrow infty }{frac {1}{N}}sum _{nleq N}f(n)=c}$

существует, говорят, что ${displaystyle f}$ имеет среднее значение (Средняя стоимость) ${displaystyle c}$.

Примеры

• Средний порядок d(п), то количество делителей из п, является бревно п;
• Средний порядок σ(п), то сумма делителей из п, является пπ² / 6;
• Средний порядок φ(п), Функция Эйлера из п, является 6п / π²;
• Средний порядок р(п), количество способов выражения п в виде суммы двух квадратов π;
• Средний порядок представления натурального числа в виде суммы трех квадратов равен 4πп / 3;
• Среднее количество разложений натурального числа в сумму одного или нескольких последовательных простых чисел равно п log2;
• Средний порядок ω(п), то количество различных простых множителей из п, является журнал п;
• Средний порядок Ω (п), то количество простых факторов из п, является журнал п;
• В теорема о простых числах эквивалентно утверждению, что функция фон Мангольдта Λ (п) имеет средний порядок 1;
• Средний порядок μ(п), то Функция Мёбиуса, равно нулю; это снова эквивалентно теорема о простых числах.

Расчет средних значений с использованием ряда Дирихле

В случае ${displaystyle F}$ имеет форму

${displaystyle F(n)=sum _{dmid n}f(d),}$

для некоторой арифметической функции ${displaystyle f(n)}$, надо,

${displaystyle sum _{nleq x}F(n)=sum _{dleq x}f(d)sum _{nleq x,dmid n}1=sum _{dleq x}f(d)[x/d]=xsum _{dleq x}{frac {f(d)}{d}}{ ext{ }}+O(sum _{dleq x}|f(d)|).qquad qquad (1)}$

Найдены обобщения предыдущего тождества. здесь. Это тождество часто обеспечивает практический способ вычисления среднего значения с точки зрения Дзета-функция Римана. Это показано в следующем примере.

Плотность k-й степени свободных целых чисел в N

Для целого числа ${displaystyle kgeq 1}$ набор ${displaystyle Q_{k}}$ из k-th-power-свободный целые числа

${displaystyle Q_{k}:={nin mathbb {Z} mid n{ ext{ is not divisible by }}d^{k}{ ext{ for any integer }}dgeq 2}.}$

Мы рассчитываем естественная плотность из этих чисел в N, то есть среднее значение ${displaystyle 1_{Q_{k}}}$, обозначаемый ${displaystyle delta (n)}$, с точки зрения дзета-функция.

Функция ${displaystyle delta }$ мультипликативен, и, поскольку он ограничен 1, его Серия Дирихле абсолютно сходится в полуплоскости ${displaystyle mathrm {Re} (s)>1}$, и есть Произведение Эйлера

${displaystyle sum _{Q_{k}}n^{-s}=sum _{n}delta (n)n^{-s}=prod _{p}(1+p^{-s}+cdots +p^{-s(k-1)})=prod _{p}left({frac {1-p^{-sk}}{1-p^{-s}}}ight)={frac {zeta (s)}{zeta (sk)}}.}$

Посредством Инверсия Мёбиуса формула, получаем

${displaystyle {frac {1}{zeta (ks)}}=sum _{n}mu (n)n^{-ks},}$

куда ${displaystyle mu }$ стоит за Функция Мёбиуса. Эквивалентно

${displaystyle {frac {1}{zeta (ks)}}=sum _{n}f(n)n^{-s},}$

куда ${displaystyle f(n)={egin{cases};;,mu (d)&n=d^{k};;,0&{ ext{otherwise}},end{cases}}}$

и поэтому,

${displaystyle {frac {zeta (s)}{zeta (sk)}}=sum _{n}(sum _{dmid n}f(d))n^{-s}.}$

Сравнивая коэффициенты, получаем

${displaystyle delta (n)=sum _{dmid n}f(d)n^{-s}.}$

Используя (1), получаем

${displaystyle sum _{dleq x}delta (d)=xsum _{dleq x}(f(d)/d)+O(x^{1/k}).}$

Мы заключаем, что,

${displaystyle sum _{nin Q_{k},nleq x}1={frac {x}{zeta (k)}}+O(x^{1/k}),}$

где для этого использовалось соотношение

${displaystyle sum _{n}(f(n)/n)=sum _{n}f(n^{k})n^{-k}=sum _{n}mu (n)n^{-k}={frac {1}{zeta (k)}},}$

которое следует из формулы обращения Мёбиуса.

В частности, плотность целые числа без квадратов является ${displaystyle zeta (2)^{-1}={frac {6}{pi ^{2}}}}$.

Видимость точек решетки

Мы говорим, что две точки решетки видны одна из другой, если на соединяющем их открытом отрезке нет точки решетки.

Теперь, если gcd (а, б) = d > 1, тогда запись а = да², б = db² можно заметить, что точка (а², б²) находится на отрезке, который соединяет (0,0) с (а, б) и поэтому (а, б) не видно из исходной точки. Таким образом (а, б) видна из начала координат, следует, что (а, б) = 1. Обратно, также легко увидеть, что gcd (а, б) = 1 означает, что на отрезке, соединяющем (0,0) с (а,б).Таким образом, (а, б) виден из (0,0) тогда и только тогда, когда gcd (а, б) = 1.

Заметь ${displaystyle {frac {varphi (n)}{n}}}$ вероятность случайной точки на квадрате ${displaystyle {(r,s)in mathbb {N} :max(|r|,|s|)=n}}$ быть видимым из исходной точки.

Таким образом, можно показать, что естественная плотность точек, видимых из начала координат, определяется средним значением,

${displaystyle lim _{Nightarrow infty }{frac {1}{N}}sum _{nleq N}{frac {varphi (n)}{n}}={frac {6}{pi ^{2}}}={frac {1}{zeta (2)}}.}$

${displaystyle {frac {1}{zeta (2)}}}$ также является естественной плотностью бесквадратных чисел в N. На самом деле это не совпадение. Рассмотрим k-мерная решетка, ${displaystyle mathbb {Z} ^{k}}$. Естественная плотность точек, видимых из начала координат, равна ${displaystyle {frac {1}{zeta (k)}}}$, которая также является естественной плотностью k-ые свободные целые числа в N.

Функции делителя

Рассмотрим обобщение ${displaystyle d(n)}$:

${displaystyle sigma _{alpha }(n)=sum _{dmid n}d^{alpha }.}$

Верно следующее:

${displaystyle sum _{nleq x}sigma _{alpha }(n)={egin{cases};;sum _{nleq x}sigma _{alpha }(n)={frac {zeta (alpha +1)}{alpha +1}}x^{alpha +1}+O(x^{eta })&{ ext{if }}alpha >0,;;sum _{nleq x}sigma _{-1}(n)=zeta (2)x+O(log x)&{ ext{if }}alpha =-1,;;sum _{nleq x}sigma _{alpha }(n)=zeta (-alpha +1)x+O(x^{max(0,1+alpha )})&{ ext{otherwise.}}end{cases}}}$

куда ${displaystyle eta =max(1,alpha )}$.

Лучше средний заказ

Это понятие лучше всего пояснить на примере. Из

${displaystyle sum _{nleq x}d(n)=xlog x+(2gamma -1)x+o(x)}$

(${displaystyle gamma }$ это Константа Эйлера – Маскерони ) и

${displaystyle sum _{nleq x}log n=xlog x-x+O(log x),}$

имеем асимптотическое соотношение

${displaystyle sum _{nleq x}(d(n)-(log n+2gamma ))=o(x)quad (xightarrow infty ),}$

что предполагает, что функция ${displaystyle log n+2gamma }$ лучший выбор среднего заказа для ${displaystyle d(n)}$ чем просто ${displaystyle log n}$.

Средние значения более F_q[Икс]

Определение

Позволять час(Икс) - функция на множестве монические полиномы над F_q. За ${displaystyle ngeq 1}$ мы определяем

${displaystyle { ext{Ave}}_{n}(h)={frac {1}{q^{n}}}sum _{f{ ext{ monic}},deg(f)=n}h(f).}$

Это среднее значение (среднее значение) час на множестве монических многочленов степени п. Мы говорим что грамм(п) является средний заказ из час если

${displaystyle { ext{Ave}}_{n}(h)sim g(n)}$

в качестве п стремится к бесконечности.

В случаях, когда лимит,

${displaystyle lim _{nightarrow infty }{ ext{Ave}}_{n}(h)=c}$

существует, говорят, что час имеет среднее значение (Средняя стоимость) c.

Дзета-функция и ряд Дирихле в F_q[ИКС]

Позволять F_q[ИКС]=А быть кольцо многочленов над конечное поле F_q.

Позволять час быть полиномиальной арифметической функцией (т.е. функцией на множестве монических многочленов над А). Соответствующий ему ряд Дирихле определяется как

${displaystyle D_{h}(s)=sum _{f{ ext{ monic}}}h(f)|f|^{-s},}$

где для ${displaystyle gin A}$, набор ${displaystyle |g|=q^{deg(g)}}$ если ${displaystyle geq 0}$, и ${displaystyle |g|=0}$ иначе.

Тогда полиномиальная дзета-функция будет

${displaystyle zeta _{A}(s)=sum _{f{ ext{ monic}}}|f|^{-s}.}$

Аналогично ситуации в N, каждая серия Дирихле мультипликативная функция час имеет товарное представление (произведение Эйлера):

${displaystyle D_{h}(s)=prod _{P}(sum _{nmathop {=} 0}^{infty }h(P^{n})|P|^{-sn}),}$

Где произведение пробегает все монические неприводимые многочлены п.

Например, представление продукта дзета-функции такое же, как для целых чисел: ${displaystyle zeta _{A}(s)=prod _{P}(1-|P|^{-s})^{-1}}$.

В отличие от классического дзета-функция, ${displaystyle zeta _{A}(s)}$ простая рациональная функция:

${displaystyle zeta _{A}(s)=sum _{f}(|f|^{-s})=sum _{n}sum _{ ext{deg(f)=n}}q^{-sn}=sum _{n}(q^{n-sn})=(1-q^{1-s})^{-1}.}$

Аналогично, если ƒ и грамм две полиномиальные арифметические функции, одна определяет ƒ * грамм, то Свертка Дирихле из ƒ и грамм, к

${displaystyle {egin{aligned}(f*g)(m)&=sum _{d,mid ,m}f(m)gleft({frac {m}{d}}ight)&=sum _{ab,=,m}f(a)g(b)end{aligned}}}$

где сумма распространяется на все монические делители d изм, или эквивалентно по всем парам (а, б) монических многочленов, произведение которых равно м. Личность ${displaystyle D_{h}D_{g}=D_{h*g}}$ все еще держится. Таким образом, как и в элементарной теории, полиномиальный ряд Дирихле и дзета-функция связаны с понятием средних значений в контексте полиномов. Следующие примеры иллюстрируют это.

Примеры

Плотность k-й степени свободные многочлены от F_q[ИКС]

Определять ${displaystyle delta (f)}$ быть 1, если ${displaystyle f}$ является k-я степень бесплатно и 0 в противном случае.

Рассчитываем среднее значение ${displaystyle delta }$, которая представляет собой плотность k-й степени свободные многочлены от F_q[ИКС]таким же образом, как и в целых числах.

По мультипликативности ${displaystyle delta }$:

${displaystyle sum _{f}{frac {delta (f)}{|f|^{s}}}=prod _{P}(sum _{jmathop {=} 0}^{k-1}(|P|^{-js}))=prod _{P}{frac {1-|P|^{-sk}}{1-|P|^{-s}}}={frac {zeta _{A}(s)}{zeta _{A}(sk)}}={frac {1-q^{1-ks}}{1-q^{1-s}}}={frac {zeta _{A}(s)}{zeta _{A}(ks)}}}$

Обозначить ${displaystyle b_{n}}$ количество kУнитарные многочлены степени п, мы получили

${displaystyle sum _{f}{frac {delta (f)}{|f|^{s}}}=sum _{n}sum _{{ ext{def}}f=n}delta (f)|f|^{-s}=sum _{n}b_{n}q^{-sn}.}$

Делаем замену ${displaystyle u=q^{-s}}$ мы получили:

${displaystyle {frac {1-qu^{k}}{1-qu}}=sum _{nmathop {=} 0}^{infty }b_{n}u^{n}.}$

Наконец, разверните левую часть в геометрический ряд и сравните коэффициенты на ${displaystyle u^{n}}$ с обеих сторон, чтобы сделать вывод, что

${displaystyle b_{n}={egin{cases};;,q^{n}&nleq k-1;;,q^{n}(1-q^{1-k})&{ ext{otherwise}}end{cases}}}$

Следовательно,

${displaystyle { ext{Ave}}_{n}(delta )=1-q^{1-k}={frac {1}{zeta _{A}(k)}}}$

И поскольку это не зависит от п это также среднее значение ${displaystyle delta (f)}$.

Функции полиномиального делителя

В F_q[ИКС], мы определяем

${displaystyle sigma _{k}(m)=sum _{f|m,{ ext{ monic}}}|f|^{k}.}$

Мы вычислим ${displaystyle { ext{Ave}}_{n}(sigma _{k})}$ за ${displaystyle kgeq 1}$.

Во-первых, обратите внимание, что

${displaystyle sigma _{k}(m)=h*mathbb {I} (m)}$

куда ${displaystyle h(f)=|f|^{k}}$ и ${displaystyle ;mathbb {I} (f)=1;;forall {f}}$.

Следовательно,

${displaystyle sum _{m}sigma _{k}(m)|m|^{-s}=zeta _{A}(s)sum _{m}h(m)|m|^{-s}.}$

Заменять ${displaystyle q^{-s}=u}$ мы получили,

${displaystyle { ext{LHS}}=sum _{n}(sum _{deg(m)=n}sigma _{k}(m))u^{n}}$, и по Продукт Коши мы получили,

${displaystyle {egin{aligned}{ ext{RHS}}&=sum _{n}q^{n(1-s)}sum _{n}(sum _{deg(m)=n}h(m))u^{n}&=sum _{n}q^{n}u^{n}sum _{l}q^{l}q^{lk}u^{l}&=sum _{n}(sum _{jmathop {=} 0}^{n}q^{n-j}q^{jk+j})&=sum _{n}(q^{n}({frac {1-q^{k(n+1)}}{1-q^{k}}}))u^{n}.end{aligned}}}$

Наконец мы получаем это,

${displaystyle { ext{Ave}}_{n}sigma _{k}={frac {1-q^{k(n+1)}}{1-q^{k}}}.}$

Заметь

${displaystyle q^{n}{ ext{Ave}}_{n}sigma _{k}=q^{n(k+1)}({frac {1-q^{-k(n+1)}}{1-q^{-k}}})=q^{n(k+1)}({frac {zeta (k+1)}{zeta (kn+k+1)}})}$

Таким образом, если положить ${displaystyle x=q^{n}}$ тогда результат выше читается

${displaystyle sum _{deg(m)=n,m{ ext{ monic}}}sigma _{k}(m)=x^{k+1}({frac {zeta (k+1)}{zeta (kn+k+1)}})}$

что напоминает аналогичный результат для целых чисел:

${displaystyle sum _{nleq x}sigma _{k}(n)={frac {zeta (k+1)}{k+1}}x^{k+1}+O(x^{k})}$

Количество делителей

Позволять ${displaystyle d(f)}$ быть числом монических делителей числа ж и разреши ${displaystyle D(n)}$ быть суммой ${displaystyle d(f)}$ по всем моникам степени n.

${displaystyle zeta _{A}(s)^{2}=(sum _{h}|h|^{-s})(sum _{g}|g|^{-s})=sum _{f}(sum _{hg=f}1)|f|^{-s}=sum _{f}d(f)|f|^{-s}=D_{d}(s)=sum _{nmathop {=} 0}^{infty }D(n)u^{n}}$

куда ${displaystyle u=q^{-s}}$.

Раскладывая правую часть в степенной ряд, получаем

${displaystyle D(n)=(n+1)q^{n}.}$

Заменять ${displaystyle x=q^{n}}$ приведенное выше уравнение становится:

${displaystyle D(n)=xlog _{q}(x)+x}$ что очень похоже на аналогичный результат для целых чисел ${displaystyle sum _{kmathop {=} 1}^{n}d(k)=xlog x+(2gamma -1)x+O({sqrt {x}})}$, куда ${displaystyle gamma }$ является Постоянная Эйлера.

О члене ошибки для целых чисел известно немного, в то время как в случае полиномов члена ошибки нет! Это связано с очень простой природой дзета-функции. ${displaystyle zeta _{A}(s)}$, и что в нем НЕТ нулей.

Полиномиальная функция фон Мангольдта

Полином функция фон Мангольдта определяется:${displaystyle Lambda _{A}(f)={egin{cases}log |P|&{mbox{if }}f=|P|^{k}{ ext{ for some prime monic}}P{ ext{ and integer }}kgeq 1,�&{mbox{otherwise.}}end{cases}}}$

Где логарифм берется на основе q.

Предложение. Среднее значение ${displaystyle Lambda _{A}}$ точно 1.

Доказательство.Позволять м - монический многочлен, и пусть ${displaystyle m=prod _{imathop {=} 1}^{l}P_{i}^{e_{i}}}$ - разложение m на простые числа.

У нас есть,

${displaystyle {egin{aligned}sum _{f|m}Lambda _{A}(f)&=sum _{(i_{1},ldots ,i_{l})|0leq i_{j}leq e_{j}}Lambda _{A}(prod _{jmathop {=} 1}^{l}P_{j}^{i_{j}})=sum _{jmathop {=} 1}^{l}sum _{imathop {=} 1}^{e_{i}}Lambda _{A}(P_{j}^{i})=sum _{jmathop {=} 1}^{l}sum _{imathop {=} 1}^{e_{i}}log |P_{j}|&=sum _{jmathop {=} 1}^{l}e_{j}log |P_{j}|=sum _{jmathop {=} 1}^{l}log |P_{j}|^{e_{j}}=log |(prod _{imathop {=} 1}^{l}P_{i}^{e_{i}})|&=log(m)end{aligned}}}$

Следовательно,

${displaystyle mathbb {I} cdot Lambda _{A}(m)=log |m|}$

и мы получаем это,

${displaystyle zeta _{A}(s)D_{Lambda _{A}}(s)=sum _{m}log|m||m|^{-s}.}$

Сейчас же,

${displaystyle sum _{m}|m|^{s}=sum _{n}sum _{deg m=n}u^{n}=sum _{n}q^{n}u^{n}=sum _{n}q^{n(1-s)}.}$

Таким образом,

${displaystyle {frac {d}{ds}}sum _{m}|m|^{s}=-sum _{n}log(q^{n})q^{n(1-s)}=-sum _{n}sum _{deg(f)=n}log(q^{n})q^{-ns}=-sum _{f}log |f||f|^{-s}.}$

Мы получили это:

${displaystyle D_{Lambda _{A}}(s)={frac {-zeta '_{A}(s)}{zeta _{A}(s)}}}$

Сейчас же,

${displaystyle sum _{m}Lambda _{A}(m)|m|^{-s}=sum _{n}(sum _{deg(m)=n}Lambda _{A}(m)q^{-sm})=sum _{n}(sum _{deg(m)=n}Lambda _{A}(m))u^{n}={frac {-zeta '_{A}(s)}{zeta _{A}(s)}}={frac {q^{1-s}log(q)}{1-q^{1-s}}}=log(q)sum _{nmathop {=} 1}^{infty }q^{n}u^{n}}$

Следовательно,

${displaystyle sum _{deg(m)=n}Lambda _{A}(m)=q^{n}log(q),}$

и разделив на ${displaystyle q^{n}}$ мы получаем это,

${displaystyle { ext{Ave}}_{n}Lambda _{A}(m)=log(q)=1.}$

Полиномиальная функция Эйлера

Определять Функция Эйлера полиномиальный аналог, ${displaystyle Phi }$, чтобы быть количеством элементов в группе ${displaystyle (A/fA)^{*}}$. У нас есть,

${displaystyle sum _{deg f=n,f{ ext{ monic}}}Phi (f)=q^{2n}(1-q^{-1}).}$

Смотрите также

• Сумматорная функция делителя
• Нормальный порядок арифметической функции
• Экстремальные порядки арифметической функции
• Тождества суммы делителей

Рекомендации

• Харди, Г.; Райт, Э.М. (2008) [1938]. Введение в теорию чисел. Отредактировано Д. Р. Хит-Браун и Дж. Х. Сильверман. Предисловие Эндрю Уайлс. (6-е изд.). Оксфорд: Oxford University Press. ISBN  978-0-19-921986-5. МИСТЕР  2445243. Zbl  1159.11001. Стр. 347–360
• Джеральд Тененбаум (1995). Введение в аналитическую и вероятностную теорию чисел. Кембриджские исследования по высшей математике. 46. Издательство Кембриджского университета. С. 36–55. ISBN  0-521-41261-7. Zbl  0831.11001.
• Том М. Апостол (1976), Введение в аналитическую теорию чисел, Springer Тексты для бакалавриата по математике, ISBN  0-387-90163-9
• Майкл Розен (2000), Теория чисел в функциональных полях, Тексты для выпускников Springer по математике, ISBN  0-387-95335-3
• Хью Л. Монтгомери; Роберт К. Воан (2006), Теория мультипликативных чисел, Издательство Кембриджского университета, ISBN  978-0521849036
• Майкл Баакеа; Роберт В. Мудиб; Питер А. Pleasantsc (2000), Дифракция от видимых точек решетки и целые числа без k-й степени, Дискретная математика - Журнал