RECYCLING HARDY & WRIGHT

9 06 2012

AVERAGE ORDER OF DEDEKIND PSI FUNCTION


Dedekind psi function called my attention, when I was trying to find trivial properties and formulas related to Jordan’s totient functions, that are indeed just generalizations of Euler’s totient function. At that time I realize that values in range of psi had similarities to those of divisor sigma, because trivialy: \sigma_{1}(n) - \psi(n) \geq 0, (inequality that holds for squarefree numbers). So, It seems reasonable to look for an alternate inequality to Robin’s criterion but with Dedekind psi instead of divisor function.

Fortunately, this question was settled, before my discovery of gunpowder, by true mathematicians like Patrick Sole and Michel Planat ([3] and [4]).

Riemann Hypothesis (RH) is true if and only:

\psi(n) 30

After I found these papers on the internet, my interest on Dedekind psi function became huge, and then I begun to look for more and more information about this arithmetical function on my library. But the real thing is that psi is never given the importance on every Number Theory book that it deserves. This was good to me because it gave me the opportunity to populate The On-Line Encyclopedia of Integer Sequences with my trivialities related to this function. This the modest mission of this blog: to create math not in the books.

As I’m a copycat and Euler’s totient is first cousin of Dedekind psi, the idea is to turn \varphi formulas into \psi with a small retouch, for example if:

\frac{n}{\varphi(n)}=\sum_{d|n}{\frac{{\mu(d)}^2}{\varphi(d)}}

Then you can discover the unpublished:

\frac{n}{\psi(n)}=\sum_{d|n}{\frac{\mu(d)}{\psi(d)}}

The same thing can be done “recycling” the analytic theorems about the average order of number theoretical functions that came on the most cited book on the topic: Hardy and Wright’s An Introduction to the Theory of Numbers, particularly Theorem 330 on the average order of Euler’s Totient can be easily rewritten to get, the not so easy to find, average order of Dedekind psi, just implementing the following expressions along theorem development:

\psi(n)= n \cdot \prod_{p|n}{\left( 1 + \frac{1}{p} \right)}

\psi(n)= n \cdot \sum_{d|n}{ \frac{|\mu(d)|}{d} }

(Taken from [4])

\sum_{d=1}^{\infty}{\frac{|\mu(d)|}{d^{2}}} = \frac{15}{{\pi}^{2}}

(See [6])

Proof:
\Psi(n) = \sum_{m=1}^{n}{\psi(m)} = m \cdot \sum_{d|m}{ \frac{|\mu(d)|}{d}} = \sum_{d \cdot d^{\prime} \leq n}{d^{\prime} \cdot |\mu(d)|} = \sum_{d=1}^{n}{|\mu(d)| \cdot \sum_{d^{\prime}=1}^{\lfloor \frac{n}{d} \rfloor}{d^{\prime}} = \frac{1}{2} \sum_{d=1}^{n}{|\mu(d)| \bigg( \bigg\lfloor \frac{n}{d} \bigg\rfloor^{2} + \bigg\lfloor \frac{n}{d} \bigg\rfloor \bigg) =

\frac{1}{2} \sum_{d=1}^{n}{|\mu(d)| \bigg\{ \frac{n^{2}}{d^{2}} + O \bigg( \frac{n}{d} \bigg) \bigg\} } = \frac{n^2}{2} \sum_{d=1}^{n}{ \frac{|\mu(d)|}{d^2} + O \bigg( n \sum_{d=1}^{n}{ \frac{1}{d} \bigg) } = \frac{n^2}{2} \sum_{d=1}^{n}{ \frac{|\mu(d)|}{d^2} + O \bigg( n^{2} \sum_{n+1}^{\infty}{ \frac{1}{d^2} \bigg) + O(n \cdot \log{n}) =

\frac{15n^{2}}{2{\pi}^2} + O(n) + O(n \cdot \log{n}) = \frac{15n^{2}}{2{\pi}^2} + O(n \cdot \log{n})

\Psi(n) = \frac{15n^{2}}{2{\pi}^2} + O(n \cdot \log{n})

Then the average order of \psi(n) is \frac{2}{n} \cdot \frac{15n}{{\pi}^2} = \frac{15n}{\pi^2}


Archives:
[a]-JordanTotientFunction.m


References:
 [1]-Patrick Sole and Michel Planat, Extreme values of the Dedekind Psi function, to appear in Journal of Combinatorics and Number Theory, arXiv:1011.1825v2
[2]-Michel Planat, Riemann hypothesis from the Dedekind psi function, arXiv:1010.3239v2
[3]-G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1979, 5th Edition pp 268, Theorem 330.
[4]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. A001615: Dedekind psi function: n * Product_{p|n, p prime} (1 + 1/p)
[5]- Jonathan Vos Post, Feb 15 2010, The On-Line Encyclopedia of Integer Sequences. A173290: Partial sums of A001615.
[6]- N. J. A. Sloane, May 09 2003, The On-Line Encyclopedia of Integer Sequences. A082020: Decimal expansion of 15/Pi^2.





TOTIENT CARNIVAL

11 07 2010

Euler´s totient function: \phi(n) is defined as the number of positive integers less than or equal to n, that are coprime to n, and using Iverson bracket, \phi can be written as: (See reference [1])

\phi(n) =\sum_{i=1}^{n}{[gcd(i,n)=1]}

MULTIPLICATIVE BUT NOT COMPLETELY MULTIPLICATIVE FUNCTIONS:

The above summatory can be expressed with the aid of non completely multiplicative arithmetical funcions, using the fact that, some functions hold for inequalities similar to this one:

f(n \cdot m)  f(n) \cdot f(m); if gcd(n,m)\neq 1

And that also hold for the properties that any multiplicative function has:

f(n)> 0

f(n \cdot m) = f(n) \cdot f(m); if gcd(n,m)= 1

Then:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{ f(i \cdot n)}{ f(i)\cdot f(n)}\bigg\rfloor}

And applying this idea to arithmetical functions of common use, we can give, for the divisor sigma functions, the Piltz divisor functions and the squarefree kernel [4], respectively:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{\sigma_{k}(i \cdot n)}{\sigma_{k}(i)\cdot \sigma_{k}(n)}\bigg\rfloor}

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{\tau_{k}(i \cdot n)}{\tau_{k}(i)\cdot \tau_{k}(n)}\bigg\rfloor}

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{rad(i \cdot n)}{rad(i)\cdot rad(n)}\bigg\rfloor}

Or we can construct an implicit formula for the Totient function:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac {\phi(i)\cdot \phi(n)}{\phi(i \cdot n)}\bigg\rfloor}

But now we must take care that now:

f(n \cdot m) > f(n) \cdot f(m); if gcd(n,m)\neq 1

so we must invert the fraction inside the floor function.

ADDITIVE BUT NOT COMPLETELY ADDITIVE FUNCTIONS:

The same thing can be done with additive but not completely additive functions:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{\omega(i \cdot n)}{\omega(i) + \omega(n)}\bigg\rfloor} \; (n>1)

OTHER FORMULAS:

This way of constructing new formulas, seems to be trivial and useless, but this is only an excuse to show how works the characteristic or indicator functions, that are underneath the behaviour of the arithmetical functions, and thus the basic Set Theory inside Number Theory.

And of course we can extend this collection of formulas to other functions distinct than \phi, like for example \pi the Prime Counting Function:

\pi(n)=\sum_{i=2}^{n}{\bigg\lfloor \frac{i+1}{\sigma_{1}(i)}\bigg\rfloor} \; (n>1)

\pi(n)=\sum_{i=2}^{n}{\bigg\lfloor \frac{\phi(i)}{i-1}\bigg\rfloor} \; (n>1)

\pi(n)=\sum_{i=2}^{n}{\bigg\lfloor \frac{2}{\tau(i)}\bigg\rfloor}=\sum_{i=2}^{n}{\bigg\lfloor \frac{k}{\tau_{k}(i)}\bigg\rfloor} \; (n>1)


Archives:
[a]-071210-Totient Carnival.nb


References:

[1]-Peter Luschny – OEIS-Wiki: Sequences related to Euler’s totient function.
[2]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A000720: pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159…
[3]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A000010: Euler totient function phi(n): count numbers <= n and prime to n.
[4]- R. Muller, The On-Line Encyclopedia of Integer Sequences.
A007947: Largest squarefree number dividing n (the squarefree kernel of n)






SPLITTING FTA FUNCTIONS (III)

23 12 2009

PILTZ DIVISOR FUNCTIONS (2)


THEOREM-2:

\displaystyle\tau_{j+k}(n)=\sum_{d|n}^{}{\tau_{j}(d)\cdot\tau_{k}\left(\frac{n}{d}\right)}

Proof:

The Piltz Divisor functions are multiplicative, so it is only necessary to prove the case p^{\alpha}

In the previous post we saw how:

\displaystyle\tau_{k}(p^\alpha)=\binom{\alpha+k-1}{k-1}

And if we apply p^\alpha to second member of the problem identity, then:

\displaystyle f(p^\alpha)=\sum_{d|p^\alpha}{\tau_{j}(d)\cdot\tau_{k}\left(\frac{p^\alpha}{d}\right)}=\sum_{i=0}^{\alpha}{\tau_{j}(p^i)\cdot\tau_{k}(p^{\alpha-i})}

\displaystyle=\sum_{i=0}^{\alpha}{\binom{i+j-1}{j-1}\binom{\alpha-i+k-1}{k-1}}=\binom{\alpha+j+k-1}{j+k-1}=\tau_{j+k}(p^\alpha)

This proof seems easy except for the binomial identity step:

\displaystyle\sum_{i=0}^{\alpha}{\binom{i+j-1}{j-1}\binom{\alpha-i+k-1}{k-1}}=\binom{\alpha+j+k-1}{j+k-1}

After several unfruitful tries to prove it, due to my lack of mathematical skills, I resigned myself to look for information about this problem on the bibliography, this formula look very close to the one found on reference [1] or [2], but with an additional variable, and after many reviews, I was glad to find a combinatorial version of the proof into the book of Chuan Chong Chen and Khee-Meng Koh [3]

This proof solved the problem, but it let me very much unsatisfied, and I begun to rethink about this topic again.

This problem is about Number Theory and not Combinatorics, and I had to revise the first lesson about the properties of Dirichlet Product:

Dirichlet´s functional convolution is associative, so we can put the brackets wherever we want, so:

\tau_{j+k}(n)=(\underbrace{I_{0}(n)*...*I_{0}(n)}_{j}) *( \underbrace{I_{0}(n)*...*I_{0}(n)}_{k})=\tau_{j}(n)*\tau_{k}(n)

This simple line proves this trivial property of the Piltz functions that I pedanticly considered as a Theorem, and it proves, as a tip, the binomial formula. The readers of this blog (if any) may forgive me.

But after all of this mess, I´ve learned many interesting things:

1) Number Theory counts with powerful mathematical tools than can be used for many unexpected purposes, just to mention the relationship between the Piltz functions and the Jacobi polynomials.
2) The properties of arithmetical functions can be used to get elegant proofs for binomial identities. (This is the opposite way that the one I took).
3) In my effort to deal with binomial identities, I discovered some formulas for determinants of matrices with binomial coefficients. (Well, there´s many articles about this topic, but I worked without previous knowledge of them). Anyhow, I haven´t found this formula somewhere but here.


References:[1]-Matthew Hubbard and Tom Roby – Pascal’s Triangle From Top To Bottom -Catalog #: 31000005
[2]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 – Concrete Mathematics – Identity (5.26)
[3]-Chuan Chong Chen,Khee-Meng Koh – Principles and techniques in combinatorics page 88-Example 2.6.2-Shortest Routes in Rectangular Grid.


 





SPLITTING FTA FUNCTIONS (II)

21 12 2009

PILTZ DIVISOR FUNCTIONS (1)

INTRO:

If we look for an example of “Functions that depend only on coefficients”, our first idea should be the divisor function, \tau_{2}(n) because it is multiplicative with:

\tau_{2}(p^\alpha)=1+\alpha

Here, they only appear the coefficients but not the primes.

With the help of recursive Dirichlet Convolution of the unit, I_{0}(n)=1, it is possible to construct a sequence of arithmetical functions only dependent on the coefficients of the prime factors of any number, known as Piltz Divisor Functions, \tau_{k}(n), because they give the number of distinct solutions of the equation x_{1}x_{2} \cdots x_{k}=n, where x_{1},x_{2},\cdots,x_{k} run indepently through the set of positive integers) or, if preferred, they give the number of ordered factorizations of n as a product of k terms. (References [3],[4] and [11])

DEFINITION:

\displaystyle \tau_{1}(n)=I_{0}(n)=1

\tau_{k}(n)=\sum_{d|n}^{}{\tau_{k-1}(d)\cdot I_{0}(n/d)}=\sum_{d|n}^{}{\tau_{k-1}(d)}

This recursion can also be notated in terms of Dirichlet Product as:

(f*g)(n)=\sum_{d|n}{f(d)\cdot g(n/d)}

\tau_{k}(n)=\tau_{k-1}*I_{0}(n)


NOTES ON NOTATION:

The divisor function can be found on the literature as: d(n), \sigma_{0}(n), \tau(n), and in this post as \tau_{2}(n).
The “\sigma´s”, and “\tau´s” are two different series of arithmetical functions that share one element in common: The divisor function. With the help of this two notations, it is possible to remark what kind of series we are working with.

On the other hand the “d“, it is a simple notation that can be used for another purposes, were the belonging to this series of functions, does not matters.

Unfortunately, this happens not only with the divisor function, the mathematical notation on arithmetical functions related to Dirichlet convolution (or product) varies from one book to another, and not only distinct functions are named the same, but all cases of “non-biyectivity” between notations and functions can be found.

Hereinafter we are going to use:

I_{k}(n)=n^{k} ( like in Reference [3] but with I_{0}(n)=1 and I_{1}(n)=n)

The identity element for Dirichlet´s product (or unit function), using Kronecker´s delta notation, is:

\displaystyle \delta_{1n}= \bigg\lfloor \frac{1}{n} \bigg\rfloor (Reference [2])

\omega(n) means the number of distinct prime factors of n


PROPERTY:

\tau_{k}(n) is multiplicative because \tau_{k-1}(n), and \tau_{1}(n) are multiplicative.

This property can also be derived from the behavior of the Dirichlet Product, but we must note that although \tau_{1}(n)=I_{0}(n)=1 is a completely multiplicative function, its convolution: \tau_{2}(n) is multiplicative, but it is not completely multiplicative.

THEOREM: [1] and [4]

\displaystyle \tau_{k}(n)=\prod_{i=1}^{\omega(n)}{\prod_{j=1}^{k-1}\frac{\alpha_{i}+j}{j}}=\prod_{i=1}^{\omega(n)}{\binom{\alpha_{i}+k-1}{k-1}}; \; (k \ge 1)

Proof:

\displaystyle \tau_{k}(p^\alpha)=\sum_{d|p^\alpha}^{}{\tau_{k-1}(d)}=\tau_{k-1}(1)+\tau_{k-1}(p)+\tau_{k-1}(p^2)+ \cdots +\tau_{k-1}(p^\alpha)

\displaystyle \tau_{k}(p^\alpha)= \sum_{i=0}^{\alpha}{\tau_{k-1}(p^i)} =\sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}}=\binom{\alpha+k-1}{k-1}

Lemma:

\displaystyle \sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}}=\binom{\alpha+k-1}{k-1}

Proof:

From Parallel Summation Identity (References [6] and [8]):

\displaystyle \sum_{k=0}^{n}{\binom{k+r}{k}}=\binom{n+r+1}{n}

Substituing: \displaystyle n\rightarrow{\alpha} and \displaystyle k\rightarrow{i}

\displaystyle \sum_{i=0}^{\alpha}{\binom{i+r}{i}}=\binom{\alpha+r+1}{\alpha}

\displaystyle r\rightarrow{k-2} and with Pascal´s Symmetry Rule [7]:

\displaystyle \sum_{i=0}^{\alpha}{\binom{i+k-2}{i}}= \sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}}= \binom{\alpha+k-1}{\alpha}=\binom{\alpha+k-1}{k-1}


Corollary-1: Values of \tau_{k}(s), being s a squarefree number.

If s is squarefree then all coefficients of its factorization are \displaystyle \alpha_{i}(s)=1, then:

\displaystyle \tau_{k}(s)= \prod_{i=1}^{\omega(s)}{\binom{k}{k-1}}=k^{\omega(s)}

For a prime p, \displaystyle \omega(p)=1, and \displaystyle \tau_{k}(p)=k, and if s=1, then \displaystyle \omega(1)=0 and \tau_{k}(1)=1


Corollary-2:

\displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \tau_2(n)

Proof:

\displaystyle \tau_{k+1}(n)=\tau_{k}(n)\cdot \prod_{i=1}^{\omega(n)}{\frac{\alpha_{i}+k}{k}}

\displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n^k)}{\frac{\alpha_{i}+k}{k}}

Like \displaystyle \omega(n^k)=\omega(n), and \displaystyle \alpha_{i}(n^k)=k\cdot\alpha_{i}(n):

\displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n)}{\frac{k \cdot \alpha_i+k}{k}}=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n)}{(\alpha_i+1)}=\tau_{k}(n^k)\cdot \tau_2(n)


References:[1]-p.167-Exercise 5.b – Leveque, William J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover Publications. ISBN 9780486689067
[2]-T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pages 29 and 38
[3]-J. Sándor: On the Arithmetical Functions d_{k}(n) and d_{k}^{*}(n), Portugaliæ Mathematica 53, No. 1 (1996)
[4]-I.Vinogradov, Fundamentos de la Teoría de los Números, Editorial RUBIÑOS, ISBN 84-2222-210-8, Segunda Edición,chapter II, Exercise 11, page 44
[5]-J. Sándor, B. Crstici, Handbook of Number Theory (Vol II), Kluwer Academic Publishers, Springer, 2004 ISBN 1402025467, 9781402025464
[6]-Ken.J.Ward, Ken Ward’s Mathematics Pages, Parellel Summation-Formula 2.2.2
[7]-Matthew Hubbard and Tom Roby – Pascal’s Triangle From Top To Bottom -Catalog #: 1000001
[8]-Matthew Hubbard and Tom Roby – Pascal’s Triangle From Top To Bottom – Catalog #: 1100002
[9]-A000012-The simplest sequence of positive numbers: the all 1’s sequence. The On-Line Encyclopedia of Integer Sequences!
[10]-A000005-d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n. The On-Line Encyclopedia of Integer Sequences!
[11]-A007425-d_3(n), or tau_3(n), the number of ordered factorizations of n as n = rst. The On-Line Encyclopedia of Integer Sequences!


 





SPLITTING FTA FUNCTIONS (I)

28 08 2009

The Fundamental Theorem of Arithmetic (FTA) grants every natural number, n>1, a unique factorization of the form:

\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}...p_{\omega(n)}^{\alpha_{\omega(n)}} = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}

Where \omega(n) is the number of distinct prime factors of n.

The arithmetical functions can be evaluated once the factorization of n is known, (although there are many of them that can be calculated without factorization)

In fact, the only way to “express some arithmetical property of n” is that the function, must be dependant on the primes, p_i and (or) on the coefficients, \alpha_i

So the arithmetical functions can be classified, in a psychedelic and unorthodox way of course, in:

1) Functions that depend only on coefficients.

2) Functions that depend only on primes.

3) Functions that depend both on primes and coefficients.

This classification, mathematically speaking, seems to be useless, but it is only an alternative to the alphabetical order, when it comes to deal with this topic.


References:

[1]-D. Joyner, R. Kreminski, J. Turisco @ Applied Abstract Algebra The Fundamental Theorem of Arithmetic
[2]-Arithmetic Function @ Wikipedia Arithmetic Function
[3]-Prime Factor @ Wikipedia Prime Factor