Jordan's totient function (original) (raw)

From Wikipedia, the free encyclopedia

Arithmetical function

In number theory, Jordan's totient function, denoted as J k ( n ) {\displaystyle J_{k}(n)} $J_{k}(n)$ , where k {\displaystyle k} $k$ is a positive integer, is a function of a positive integer, n {\displaystyle n} $n$ , that equals the number of k {\displaystyle k} $k$ -tuples of positive integers that are less than or equal to n {\displaystyle n} $n$ and that together with n {\displaystyle n} $n$ form a coprime set of k + 1 {\displaystyle k+1} $k+1$ integers.

Jordan's totient function is a generalization of Euler's totient function, which is the same as J 1 ( n ) {\displaystyle J_{1}(n)} $J_{1}(n)$ . The function is named after Camille Jordan.

For each positive integer k {\displaystyle k} $k$ , Jordan's totient function J k {\displaystyle J_{k}} $J_{k}$ is multiplicative and may be evaluated as

J k ( n ) = n k ∏ p | n ( 1 − 1 p k ) {\displaystyle J_{k}(n)=n^{k}\prod _{p|n}\left(1-{\frac {1}{p^{k}}}\right)\,} $J_{k}(n)=n^{k}\prod _{p|n}\left(1-{\frac {1}{p^{k}}}\right)\,$ , where p {\displaystyle p} $p$ ranges through the prime divisors of n {\displaystyle n} $n$ .

∑ d | n J k ( d ) = n k . {\displaystyle \sum _{d|n}J_{k}(d)=n^{k}.\,} $\sum _{d|n}J_{k}(d)=n^{k}.\,$

which may be written in the language of Dirichlet convolutions as[1]

J k ( n ) ⋆ 1 = n k {\displaystyle J_{k}(n)\star 1=n^{k}\,} $J_{k}(n)\star 1=n^{k}\,$

and via Möbius inversion as

J k ( n ) = μ ( n ) ⋆ n k {\displaystyle J_{k}(n)=\mu (n)\star n^{k}} $J_{k}(n)=\mu (n)\star n^{k}$ .

Since the Dirichlet generating function of μ {\displaystyle \mu } $\mu$ is 1 / ζ ( s ) {\displaystyle 1/\zeta (s)} $1/\zeta (s)$ and the Dirichlet generating function of n k {\displaystyle n^{k}} $n^{k}$ is ζ ( s − k ) {\displaystyle \zeta (s-k)} $\zeta (s-k)$ , the series for J k {\displaystyle J_{k}} $J_{k}$ becomes

∑ n ≥ 1 J k ( n ) n s = ζ ( s − k ) ζ ( s ) {\displaystyle \sum _{n\geq 1}{\frac {J_{k}(n)}{n^{s}}}={\frac {\zeta (s-k)}{\zeta (s)}}} $\sum _{n\geq 1}{\frac {J_{k}(n)}{n^{s}}}={\frac {\zeta (s-k)}{\zeta (s)}}$ .

An average order of J k ( n ) {\displaystyle J_{k}(n)} $J_{k}(n)$ is

J k ( n ) ∼ n k ζ ( k + 1 ) {\displaystyle J_{k}(n)\sim {\frac {n^{k}}{\zeta (k+1)}}} $J_{k}(n)\sim {\frac {n^{k}}{\zeta (k+1)}}$ .

The Dedekind psi function is

ψ ( n ) = J 2 ( n ) J 1 ( n ) {\displaystyle \psi (n)={\frac {J_{2}(n)}{J_{1}(n)}}} $\psi (n)={\frac {J_{2}(n)}{J_{1}(n)}}$ ,

and by inspection of the definition (recognizing that each factor in the product over the primes is a cyclotomic polynomial of p − k {\displaystyle p^{-k}} $p^{-k}$ ), the arithmetic functions defined by J k ( n ) J 1 ( n ) {\displaystyle {\frac {J_{k}(n)}{J_{1}(n)}}} ${\frac {J_{k}(n)}{J_{1}(n)}}$ or J 2 k ( n ) J k ( n ) {\displaystyle {\frac {J_{2k}(n)}{J_{k}(n)}}} ${\frac {J_{2k}(n)}{J_{k}(n)}}$ can also be shown to be integer-valued multiplicative functions.

∑ δ ∣ n δ s J r ( δ ) J s ( n δ ) = J r + s ( n ) {\displaystyle \sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)} $\sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)$ .[2]

Order of matrix groups

[edit]

| GL ⁡ ( m , Z / n ) | = n m ( m − 1 ) 2 ∏ k = 1 m J k ( n ) . {\displaystyle |\operatorname {GL} (m,\mathbf {Z} /n)|=n^{\frac {m(m-1)}{2}}\prod _{k=1}^{m}J_{k}(n).} $|\operatorname {GL} (m,\mathbf {Z} /n)|=n^{\frac {m(m-1)}{2}}\prod _{k=1}^{m}J_{k}(n).$

| SL ⁡ ( m , Z / n ) | = n m ( m − 1 ) 2 ∏ k = 2 m J k ( n ) . {\displaystyle |\operatorname {SL} (m,\mathbf {Z} /n)|=n^{\frac {m(m-1)}{2}}\prod _{k=2}^{m}J_{k}(n).} $|\operatorname {SL} (m,\mathbf {Z} /n)|=n^{\frac {m(m-1)}{2}}\prod _{k=2}^{m}J_{k}(n).$

| Sp ⁡ ( 2 m , Z / n ) | = n m 2 ∏ k = 1 m J 2 k ( n ) . {\displaystyle |\operatorname {Sp} (2m,\mathbf {Z} /n)|=n^{m^{2}}\prod _{k=1}^{m}J_{2k}(n).} $|\operatorname {Sp} (2m,\mathbf {Z} /n)|=n^{m^{2}}\prod _{k=1}^{m}J_{2k}(n).$

The first two formulas were discovered by Jordan.

Explicit lists in the OEIS are J2 in OEIS: A007434, J3 in OEIS: A059376, J4 in OEIS: A059377, J5 in OEIS: A059378, J6 up to J10 in OEIS: A069091 up to OEIS: A069095.
Multiplicative functions defined by ratios are J2(n)/J1(n) in OEIS: A001615, J3(n)/J1(n) in OEIS: A160889, J4(n)/J1(n) in OEIS: A160891, J5(n)/J1(n) in OEIS: A160893, J6(n)/J1(n) in OEIS: A160895, J7(n)/J1(n) in OEIS: A160897, J8(n)/J1(n) in OEIS: A160908, J9(n)/J1(n) in OEIS: A160953, J10(n)/J1(n) in OEIS: A160957, J11(n)/J1(n) in OEIS: A160960.
Examples of the ratios J2k(n)/Jk(n) are J4(n)/J2(n) in OEIS: A065958, J6(n)/J3(n) in OEIS: A065959, and J8(n)/J4(n) in OEIS: A065960.

^ Sándor & Crstici (2004) p.106
^ Holden et al in external links. The formula is Gegenbauer's.
^ All of these formulas are from Andrica and Piticari in #External links.

L. E. Dickson (1971) [1919]. History of the Theory of Numbers, Vol. I. Chelsea Publishing. p. 147. ISBN 0-8284-0086-5. JFM 47.0100.04.
M. Ram Murty (2001). Problems in Analytic Number Theory. Graduate Texts in Mathematics. Vol. 206. Springer-Verlag. p. 11. ISBN 0-387-95143-1. Zbl 0971.11001.
Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36. ISBN 1-4020-2546-7. Zbl 1079.11001.
Andrica, Dorin; Piticari, Mihai (2004). "On some extensions of Jordan's arithmetic functions". Acta Universitatis Apulensis. 7: 13–22. MR 2157944.
Holden, Matthew; Orrison, Michael; Vrable, Michael. "Yet Another Generalization of Euler's Totient Function" (PDF). Archived from the original (PDF) on 2016-03-05. Retrieved 2011-12-21.