Просте омега функције

У теорији бројева, просте омега функције ${\displaystyle \omega (n)}$ и ${\displaystyle \Omega (n)}$ броје просте факторе природног броја ${\displaystyle n.}$ Број различитих простих фактора додељује се функцији ${\displaystyle \omega (n)}$ (мала омега), док ${\displaystyle \Omega (n)}$ (велика омега) броји укупан број простих фактора са вишеструкошћу (погледати аритметичка функција). То јест, ако имамо просту факторизацију броја ${\displaystyle n}$ у облику ${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$ за различите просте бројеве ${\displaystyle p_{i}}$ (${\displaystyle 1\leq i\leq k}$), онда су просте омега функције дате са ${\displaystyle \omega (n)=k}$ и ${\displaystyle \Omega (n)=\alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}}$. Ове функције за бројање простих фактора имају многе важне релације у теорији бројева.

Особине и релације

Функција ${\displaystyle \omega (n)}$ је адитивна, а ${\displaystyle \Omega (n)}$ је потпуно адитивна. Мала омега има формулу

${\displaystyle \omega (n)=\sum _{p\mid n}1,}$

где нотација p|n означава да се сума узима преко свих простих бројева p који деле n, без вишеструкости. На пример, ${\displaystyle \omega (12)=\omega (2^{2}\cdot 3)=2}$.

Велика омега има формуле

${\displaystyle \Omega (n)=\sum _{p^{\alpha }\mid n}1=\sum _{p^{\alpha }\parallel n}\alpha .}$

Нотација p^α|n означава да се сума узима преко свих степена простих бројева p^α који деле n, док p^α||n означава да се сума узима преко свих степена простих бројева p^α који деле n тако да је n / p^α узајамно прост са p^α. На пример, ${\displaystyle \Omega (12)=\Omega (2^{2}\cdot 3^{1})=3}$.

Омега функције су повезане неједнакостима ω(n) ≤ Ω(n) и 2^ω(n) ≤ d(n) ≤ 2^Ω(n), где је d(n) функција броја делитеља.^[1] Ако је Ω(n) = ω(n), онда је n безквадратни број и повезан је са Мебијусовом функцијом преко

${\displaystyle \mu (n)=(-1)^{\omega (n)}=(-1)^{\Omega (n)}.}$

Ако је ${\displaystyle \omega (n)=1}$, онда је ${\displaystyle n}$ степен простог броја, а ако је ${\displaystyle \Omega (n)=1}$, онда је ${\displaystyle n}$ прост број.

Асимптотски ред за просечан ред функције ${\displaystyle \omega (n)}$ је ^[2]

${\displaystyle {\frac {1}{n}}\sum \limits _{k=1}^{n}\omega (k)\sim \log \log n+B_{1}+\sum _{k\geq 1}\left(\sum _{j=0}^{k-1}{\frac {\gamma _{j}}{j!}}-1\right){\frac {(k-1)!}{(\log n)^{k}}},}$

где је ${\displaystyle B_{1}\approx 0.26149721}$ Мертенсова константа, а ${\displaystyle \gamma _{j}}$ су Стилтјесове константе.

Функција ${\displaystyle \omega (n)}$ је повезана са сумама делитеља преко Мебијусове функције и делитељске функције, укључујући:^[3]

${\displaystyle \sum _{d\mid n}|\mu (d)|=2^{\omega (n)}}$ је број унитарних делитеља. (секвенца A034444 у )

${\displaystyle \sum _{d\mid n}|\mu (d)|k^{\omega (d)}=(k+1)^{\omega (n)}}$

${\displaystyle \sum _{r\mid n}2^{\omega (r)}=d(n^{2})}$

${\displaystyle \sum _{r\mid n}2^{\omega (r)}d\left({\frac {n}{r}}\right)=d^{2}(n)}$

${\displaystyle \sum _{d\mid n}(-1)^{\omega (d)}=\prod \limits _{p^{\alpha }||n}(1-\alpha )}$

${\displaystyle \sum _{\stackrel {1\leq k\leq m}{(k,m)=1}}\gcd(k^{2}-1,m_{1})\gcd(k^{2}-1,m_{2})=\varphi (n)\sum _{\stackrel {d_{1}\mid m_{1}}{d_{2}\mid m_{2}}}\varphi (\gcd(d_{1},d_{2}))2^{\omega (\operatorname {lcm} (d_{1},d_{2}))},\ m_{1},m_{2}{\text{ непарни}},m=\operatorname {lcm} (m_{1},m_{2})}$

${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\operatorname {gcd} (k,m)=1}}\!\!\!\!1=n{\frac {\varphi (m)}{m}}+O\left(2^{\omega (m)}\right)}$

Карактеристична функција простих бројева може се изразити конволуцијом са Мебијусовом функцијом:^[4]

${\displaystyle \chi _{\mathbb {P} }(n)=(\mu \ast \omega )(n)=\sum _{d|n}\omega (d)\mu (n/d).}$

Тачан идентитет за ${\displaystyle \omega (n)}$ повезан са партицијама дат је са ^[5]

${\displaystyle \omega (n)=\log _{2}\left[\sum _{k=1}^{n}\sum _{j=1}^{k}\left(\sum _{d\mid k}\sum _{i=1}^{d}p(d-ji)\right)s_{n,k}\cdot |\mu (j)|\right],}$

где је ${\displaystyle p(n)}$ партициона функција, ${\displaystyle \mu (n)}$ је Мебијусова функција, а троугаони низ ${\displaystyle s_{n,k}}$ се проширује као

${\displaystyle s_{n,k}=[q^{n}](q;q)_{\infty }{\frac {q^{k}}{1-q^{k}}}=s_{o}(n,k)-s_{e}(n,k),}$

у терминима бесконачног q-Покхамеровог симбола и ограничених партиционих функција ${\displaystyle s_{o/e}(n,k)}$ које респективно означавају број појављивања броја ${\displaystyle k}$ у свим партицијама броја ${\displaystyle n}$ на непаран (паран) број различитих делова.^[6]

Наставак на комплексну раван

Пронађен је наставак функције ${\displaystyle \omega (n)}$, иако није аналитичан свуда.^[7] Имајте на уму да се користи нормализована ${\displaystyle \operatorname {sinc} }$ функција ${\displaystyle \operatorname {sinc} (x)={\frac {\sin(\pi x)}{\pi x}}}$.

${\displaystyle \omega (z)=\log _{2}\left(\sum _{n=1}^{\lceil Re(z)\rceil }\operatorname {sinc} \left(\prod _{m=1}^{\lceil Re(z)\rceil +1}\left(n^{2}+n-mz\right)\right)\right)}$

Ово је блиско повезано са следећим партиционим идентитетом. Размотримо партиције облика

${\displaystyle a={\frac {2}{c}}+{\frac {4}{c}}+\ldots +{\frac {2(b-1)}{c}}+{\frac {2b}{c}}}$

где су ${\displaystyle a}$, ${\displaystyle b}$, и ${\displaystyle c}$ позитивни цели бројеви, и ${\displaystyle a>b>c}$. Број партиција је тада дат са ${\displaystyle 2^{\omega (a)}-2}$. ^[8]

Просечан ред и суматорне функције

Просечан ред и функције ${\displaystyle \omega (n)}$ и ${\displaystyle \Omega (n)}$ је ${\displaystyle \log \log n}$. Када је ${\displaystyle n}$ прост број, доња граница вредности функције је ${\displaystyle \omega (n)=1}$. Слично томе, ако је ${\displaystyle n}$ приморијал, функција је велика као

${\displaystyle \omega (n)\sim {\frac {\log n}{\log \log n}}}$

у просечном реду. Када је ${\displaystyle n}$ степен двојке, онда је ${\displaystyle \Omega (n)=\log _{2}(n).}$^[9]

Асимптотике за суматорне функције над ${\displaystyle \omega (n)}$, ${\displaystyle \Omega (n)}$, и степенима ${\displaystyle \omega (n)}$ су респективно^[10][11]

${\displaystyle {\begin{aligned}\sum _{n\leq x}\omega (n)&=x\log \log x+B_{1}x+o(x)\\\sum _{n\leq x}\Omega (n)&=x\log \log x+B_{2}x+o(x)\\\sum _{n\leq x}\omega (n)^{2}&=x(\log \log x)^{2}+O(x\log \log x)\\\sum _{n\leq x}\omega (n)^{k}&=x(\log \log x)^{k}+O(x(\log \log x)^{k-1}),k\in \mathbb {Z} ^{+},\end{aligned}}}$

где је ${\displaystyle B_{1}\approx 0.2614972128}$ Мертенсова константа, а константа ${\displaystyle B_{2}}$ је дефинисана са

${\displaystyle B_{2}=B_{1}+\sum _{p{\text{ прост}}}{\frac {1}{p(p-1)}}\approx 1.0345061758.}$

Сума броја унитарних делитеља је

${\displaystyle \sum _{n\leq x}2^{\omega (n)}=(x\log x)/\zeta (2)+O(x)}$^[12] (секвенца A064608 у )

Друге суме које повезују две варијанте простих омега функција укључују ^[13]

${\displaystyle \sum _{n\leq x}\left\{\Omega (n)-\omega (n)\right\}=O(x),}$

и

${\displaystyle \#\left\{n\leq x:\Omega (n)-\omega (n)>{\sqrt {\log \log x}}\right\}=O\left({\frac {x}{(\log \log x)^{1/2}}}\right).}$

Пример I: Модификована суматорна функција

У овом примеру предлажемо варијанту суматорних функција ${\displaystyle S_{\omega }(x):=\sum _{n\leq x}\omega (n)}$ процењених у горенаведеним резултатима за довољно велико ${\displaystyle x}$. Затим доказујемо асимптотску формулу за раст ове модификоване суматорне функције изведену из асимптотске процене ${\displaystyle S_{\omega }(x)}$ дате у формулама у главном под-одељку овог чланка.^[14]

Да будемо потпуно прецизни, нека је суматорна функција са непарним индексима дефинисана као

${\displaystyle S_{\operatorname {odd} }(x):=\sum _{n\leq x}\omega (n)[n{\text{ је непаран}}],}$

где ${\displaystyle [\cdot ]}$ означава Ајверсонову заграду. Тада имамо да је

${\displaystyle S_{\operatorname {odd} }(x)={\frac {x}{2}}\log \log x+{\frac {(2B_{1}-1)x}{4}}+\left\{{\frac {x}{4}}\right\}-\left[x\equiv 2,3{\bmod {4}}\right]+O\left({\frac {x}{\log x}}\right).}$

Доказ овог резултата следи прво из запажања да

${\displaystyle \omega (2n)={\begin{cases}\omega (n)+1,&{\text{ако је }}n{\text{ непаран; }}\\\omega (n),&{\text{ако је }}n{\text{ паран,}}\end{cases}}}$

а затим применом асимптотског резултата из Хардија и Рајта за суматорну функцију над ${\displaystyle \omega (n)}$, означену са ${\displaystyle S_{\omega }(x):=\sum _{n\leq x}\omega (n)}$, у следећем облику:

${\displaystyle {\begin{aligned}S_{\omega }(x)&=S_{\operatorname {odd} }(x)+\sum _{n\leq \left\lfloor {\frac {x}{2}}\right\rfloor }\omega (2n)\\&=S_{\operatorname {odd} }(x)+\sum _{n\leq \left\lfloor {\frac {x}{4}}\right\rfloor }\left(\omega (4n)+\omega (4n+2)\right)\\&=S_{\operatorname {odd} }(x)+\sum _{n\leq \left\lfloor {\frac {x}{4}}\right\rfloor }\left(\omega (2n)+\omega (2n+1)+1\right)\\&=S_{\operatorname {odd} }(x)+S_{\omega }\left(\left\lfloor {\frac {x}{2}}\right\rfloor \right)+\left\lfloor {\frac {x}{4}}\right\rfloor .\end{aligned}}}$

Пример II: Суматорне функције за факторијелске моменте функције ω(n)

Прорачуни проширени у поглављу 22.11 Хардија и Рајта дају асимптотске процене за суматорну функцију

${\displaystyle \omega (n)\left\{\omega (n)-1\right\},}$

процењујући производ ове две компонентне омега функције као

${\displaystyle \omega (n)\left\{\omega (n)-1\right\}=\sum _{\stackrel {pq\mid n}{\stackrel {p\neq q}{p,q{\text{ прости}}}}}1=\sum _{\stackrel {pq\mid n}{p,q{\text{ прости}}}}1-\sum _{\stackrel {p^{2}\mid n}{p{\text{ прост}}}}1.}$

Слично можемо израчунати асимптотске формуле у општијем случају за повезане суматорне функције над такозваним факторијелским моментима функције ${\displaystyle \omega (n)}$.

Дирихлеови редови

Познат Дирихлеов ред који укључује ${\displaystyle \omega (n)}$ и Риманову зета-функцију дат је са^[15]

${\displaystyle \sum _{n\geq 1}{\frac {2^{\omega (n)}}{n^{s}}}={\frac {\zeta ^{2}(s)}{\zeta (2s)}},\ \Re (s)>1.}$

Такође можемо видети да је

${\displaystyle \sum _{n\geq 1}{\frac {z^{\omega (n)}}{n^{s}}}=\prod _{p}\left(1+{\frac {z}{p^{s}-1}}\right),|z|<2,\Re (s)>1,}$

${\displaystyle \sum _{n\geq 1}{\frac {z^{\Omega (n)}}{n^{s}}}=\prod _{p}\left(1-{\frac {z}{p^{s}}}\right)^{-1},|z|<2,\Re (s)>1,}$

Функција ${\displaystyle \Omega (n)}$ је потпуно адитивна, док је ${\displaystyle \omega (n)}$ строго адитивна (адитивна). Сада можемо доказати кратку лему у следећем облику, која имплицира тачне формуле за развоје Дирихлеових редова над ${\displaystyle \omega (n)}$ и ${\displaystyle \Omega (n)}$:

Лема. Претпоставимо да је ${\displaystyle f}$ строго адитивна аритметичка функција дефинисана тако да су њене вредности на степенима простих бројева дате са ${\displaystyle f(p^{\alpha }):=f_{0}(p,\alpha )}$, тј. ${\displaystyle f(p_{1}^{\alpha _{1}}\cdots p_{k}^{\alpha _{k}})=f_{0}(p_{1},\alpha _{1})+\cdots +f_{0}(p_{k},\alpha _{k})}$ за различите просте бројеве ${\displaystyle p_{i}}$ и експоненте ${\displaystyle \alpha _{i}\geq 1}$. Дирихлеов ред функције ${\displaystyle f}$ се развија као

${\displaystyle \sum _{n\geq 1}{\frac {f(n)}{n^{s}}}=\zeta (s)\times \sum _{p{\text{ прост}}}(1-p^{-s})\cdot \sum _{n\geq 1}f_{0}(p,n)p^{-ns},\Re (s)>\min(1,\sigma _{f}).}$

Доказ. Можемо видети да је

${\displaystyle \sum _{n\geq 1}{\frac {u^{f(n)}}{n^{s}}}=\prod _{p{\text{ прост}}}\left(1+\sum _{n\geq 1}u^{f_{0}(p,n)}p^{-ns}\right).}$

Ово имплицира да је

${\displaystyle {\begin{aligned}\sum _{n\geq 1}{\frac {f(n)}{n^{s}}}&={\frac {d}{du}}\left[\prod _{p{\text{ прост}}}\left(1+\sum _{n\geq 1}u^{f_{0}(p,n)}p^{-ns}\right)\right]{\Biggr |}_{u=1}=\prod _{p}\left(1+\sum _{n\geq 1}p^{-ns}\right)\times \sum _{p}{\frac {\sum _{n\geq 1}f_{0}(p,n)p^{-ns}}{1+\sum _{n\geq 1}p^{-ns}}}\\&=\zeta (s)\times \sum _{p{\text{ прост}}}(1-p^{-s})\cdot \sum _{n\geq 1}f_{0}(p,n)p^{-ns},\end{aligned}}}$

где год одговарајући редови и производи конвергирају. У последњој једначини, користили смо Ојлеров производ за Риманову зета-функцију.

Лема имплицира да за ${\displaystyle \Re (s)>1}$,

${\displaystyle {\begin{aligned}D_{\omega }(s)&:=\sum _{n\geq 1}{\frac {\omega (n)}{n^{s}}}=\zeta (s)P(s)\\&\ =\zeta (s)\times \sum _{n\geq 1}{\frac {\mu (n)}{n}}\log \zeta (ns)\\D_{\Omega }(s)&:=\sum _{n\geq 1}{\frac {\Omega (n)}{n^{s}}}=\zeta (s)\times \sum _{n\geq 1}P(ns)\\&\ =\zeta (s)\times \sum _{n\geq 1}{\frac {\phi (n)}{n}}\log \zeta (ns)\\D_{h}(s)&:=\sum _{n\geq 1}{\frac {h(n)}{n^{s}}}=\zeta (s)\log \zeta (s)\\&\ =\zeta (s)\times \sum _{n\geq 1}{\frac {\varepsilon (n)}{n}}\log \zeta (ns),\end{aligned}}}$

где је ${\displaystyle P(s)}$ проста зета-функција, ${\displaystyle h(n)=\sum _{p^{k}|n}{\frac {1}{k}}=\sum _{p^{k}||n}{H_{k}}}$ где је ${\displaystyle H_{k}}$ ${\displaystyle k}$-ти хармонијски број, а ${\displaystyle \varepsilon }$ је идентитет за Дирихлеову конволуцију, ${\displaystyle \varepsilon (n)=\lfloor {\frac {1}{n}}\rfloor }$.

Расподела разлике простих омега функција

Расподела различитих целобројних вредности разлика ${\displaystyle \Omega (n)-\omega (n)}$ је регуларна у поређењу са полу-случајним својствима компонентних функција. За ${\displaystyle k\geq 0}$, дефинишимо

${\displaystyle N_{k}(x):=\#(\{n\in \mathbb {Z} ^{+}:\Omega (n)-\omega (n)=k\}\cap [1,x]).}$

Ове кардиналности имају одговарајући низ граничних густина ${\displaystyle d_{k}}$ тако да за ${\displaystyle x\geq 2}$

${\displaystyle N_{k}(x)=d_{k}\cdot x+O\left(\left({\frac {3}{4}}\right)^{k}{\sqrt {x}}(\log x)^{\frac {4}{3}}\right).}$

Ове густине су генерисане производима над простим бројевима

${\displaystyle \sum _{k\geq 0}d_{k}\cdot z^{k}=\prod _{p}\left(1-{\frac {1}{p}}\right)\left(1+{\frac {1}{p-z}}\right).}$

Са апсолутном константом ${\displaystyle {\hat {c}}:={\frac {1}{4}}\times \prod _{p>2}\left(1-{\frac {1}{(p-1)^{2}}}\right)^{-1}}$, густине ${\displaystyle d_{k}}$ задовољавају

${\displaystyle d_{k}={\hat {c}}\cdot 2^{-k}+O(5^{-k}).}$

Упоредити са дефиницијом производа над простим бројевима дефинисаном у последњем одељку ^[16] у вези са Ердеш-Кацовом теоремом.

Види још

• Адитивна функција
• Аритметичка функција
• Ердеш-Кацова теорема
• Омега функција (вишезначна одредница)
• Прост број
• Безквадратни цео број