NTIC Making New Functions

Section 23.3 Making New Functions

Subsection 23.3.1 First new functions

In order to see what good this does, let's see what happens when we mess around and make Dirichlet products with functions we know. We already know two of these functions, and I give you a third.

🔗

Definition 23.3.1.

We define a new simple arithmetic function to go along with those from Definition 19.2.9.

$u (n) = 1$ for all $n$
$N (n) = n$ for all $n$
$I (n) = {\begin{cases} 1 & n = 1 \\ 0 & n > 1 \end{cases}$

🔗

In the next computational cell, we define these using Sage (recall Sage note 11.1.1), as well as a Dirichlet product function.

xxxxxxxxxx
 
def u(n): return 1
def N(n): return n
def I(n): return floor(1/n)
def DirichletProduct(f,g,n): return sum(f(d)*g(n/d) for d in divisors(n))

🔗

Now let's see what we get! For instance, what happens if we look for the inverse of

N ?

(You can try it by hand too, of course.)

xxxxxxxxxx
 
@interact
def _(n=10):
    H = [['$i$',r'$(N\star \mu)(i)$']]
    T = [(i,DirichletProduct(N,moebius,i)) for i in [1..n]]
    pretty_print(html(table(H+T, header_row=True, frame=True )))

🔗

Maybe this is a surprise! But this makes sense, if you remember Example 23.2.4 just previously about

N = ϕ ⋆ u .

Let's confirm that fact numerically as well.

xxxxxxxxxx
 
@interact
def _(n=10):
    H = [['$i$',r'$(\phi\star u)(i)$']]
    T = [(i,DirichletProduct(u,euler_phi,i)) for i in [1..n]]
    pretty_print(html(table(H+T, header_row=True, frame=True )))

🔗

We summarize these explanations as follows.

🔗

Fact 23.3.2.

We may identify the following Dirichlet products as known functions.

$ϕ ⋆ u = N$
$N ⋆ μ = ϕ$

🔗

Both parts of Fact 23.3.2 can be connected to work from much earlier. The first part is another proof of Fact 9.5.4, while the second part gives an alternate proof for our formula for

ϕ

from Exercise 9.6.11:

ϕ (n) = (N ⋆ μ) (n) = \sum_{d ∣ n} N (d) μ (\frac{n}{d}) =

\sum_{e ∣ n} N (\frac{n}{e}) μ (e) = n \sum_{e ∣ n} \frac{μ (e)}{e} = n \prod_{p ∣ n} (1 - \frac{1}{p}) .

🔗

The middle step follows if we let

e = n / d,

since that sum will also go through all divisors of

n .

The last step follows from our initial definition of

μ

in Definition 23.1.1.

🔗

Subsection 23.3.2 More new functions

🔗

Next, please try computing the Moebius inversions of our old friends,

σ

and

τ,

by hand for several values. (Hint: try primes and perfect powers first, as they don't have many divisors!)

🔗

You can try something out here in Sage as well.

xxxxxxxxxx
 
​

🔗

If you are online, in the next few cells one can try this interactively. (If you get an error, you'll need to evaluate the earlier cell after Definition 23.3.1.)

xxxxxxxxxx
 
@interact
def _(n=10):
    H = [['$i$',r'$(\tau\star \mu)(i)$']]
    T = [(i,DirichletProduct(lambda y: sigma(y,0),moebius,i)) for i in [1..n]]
    pretty_print(html(table(H+T, header_row=True, frame=True )))

xxxxxxxxxx
 
@interact
def _(n=10):
    H = [['$i$',r'$(\sigma\star \mu)(i)$']]
    T = [(i,DirichletProduct(sigma,moebius,i)) for i in [1..n]]
    pretty_print(html(table(H+T, header_row=True, frame=True )))

🔗

There is a load of fun to be had here. We could try to see what

μ ⋆ μ

is, or

u ⋆ u .

Could there be a formula for

| μ |,

or could we calculate

| μ | ⋆ u ?

xxxxxxxxxx
 
@interact
def _(n=10):
    H = [['$i$',r'$(\mu\star \mu)(i)$']]
    T = [(i,DirichletProduct(moebius,moebius,i)) for i in [1..n]]
    pretty_print(html(table(H+T, header_row=True, frame=True )))

xxxxxxxxxx
 
@interact
def _(n=10):
    H = [['$i$',r'$(u\star u)(i)$']]
    T = [(i,DirichletProduct(u,u,i)) for i in [1..n]]
    pretty_print(html(table(H+T, header_row=True, frame=True )))

🔗

It turns out you can define all kinds of other functions. We already saw the first of these informally in our discussion of the Moebius function in Proposition 23.1.5.

🔗

Definition 23.3.3.

n = \prod_{i = 1}^{k} p_{i}^{e_{i}}

then we can give the name $ω (n) = k$ to the number of unique prime divisors of an integer. (This is sometimes called $ν (n)$ in the literature.)

🔗

Definition 23.3.4.

If $n = \prod_{i = 1}^{k} p_{i}^{e_{i}},$ we summarize the parity of the total powers of primes dividing a number as

λ (n) = (- 1)^{e_{1} + e_{2} + \dots + e_{k}} .

This is called Liouville's function.

🔗

In both cases, you might want to try a few values to see what these functions look like. See Exercise 23.5.1, or pursue these ideas:

What is the value for primes?
What is the $⋆$ product of this with something – say, $u ?$

🔗

Finally, we provide some Sage cells to try things out; the first one defines our functions, and the interact lets you explore. Then again, you should try them not just with Sage, but also by hand; this is part of the allure of number theory. The sky's the limit. Enjoy!

xxxxxxxxxx
 
def u(n): return 1
def N(n): return n
def I(n): return floor(1/n)
def omega(n): return len(n.prime_divisors())
def liouville(n): return (-1)^sum([z[1] for z in n.factor()])
def DirichletProduct(f,g,n): return sum(f(d)*g(Integer(n/d)) for d in divisors(n))

xxxxxxxxxx
 
@interact
def _(n=10,f=[liouville,u,N,moebius,omega,I], g=[liouville,u,N,moebius,omega,I]):
    H = [['$i$',r'$(%s\star %s)(i)$'%(f,g)]]
    T = [(i,DirichletProduct(f,g,i)) for i in [1..n]]
    pretty_print(html(table(H+T, header_row=True, frame=True )))