Results about Multiplicative functions

I will be regularly updating this post with results, along with my proofs of them, that I encounter about multiplicative functions, in particular involving the Dirichlet product.

A multiplicative function f is such that for (m,n) = 1, f(mn)=f(m)f(n), where m,n \in\mathbb{Z}. The Dirichlet product of two arithmetical functions (functions that take operate in the integer domain) f,g is f*g = \sum\limits_{d| n}f(d)g(\frac{n}{d}).

Result 1:  \frac{n}{\varphi(n)} = \sum\limits_{d|n}\frac{\mu^2(d)}{\varphi(d)}

Proof: We will make extensive use of the fact that \varphi(p_ip_j) = \varphi(p_i)\varphi(p_j).

Since, \varphi(n) = n\prod (1-\frac{1}{p_i}), the left side of the equality simplifies to \frac{1}{\prod (1- \frac{1}{p_i})} = \frac{p_1\dots p_r}{\varphi(p_1 \dots p_r)}. Assigning N = p_1\dots p_r, the left side finally becomes \frac{N}{\varphi(N)} .

Now, the right side is the sum over all the divisors of n that are square-free (if d is not square-free then \mu(d) = 0. Also since, \mu(d) = \pm 1\mu^2(d) = 1, the sum can be split up as:

1 + \sum \frac{1}{\varphi(p_i)} + \sum \frac{1}{\varphi(p_ip_j)} + \dots + \frac{1}{\varphi(p_1\dots p_r)}.

Taking the lcm which is equal to \varphi(p_1\dots p_r) = \varphi(N), we get:

\frac{\varphi(N) + \sum\varphi(p_1\dots p_{i-1}p_{i+1}\dots p_r)+\dots +1}{\varphi(N)}

Note that the numerator contains all the same terms as the product \prod\limits_{i=1}^{r}(1 + \varphi(p_i)). This further simplifies the right-hand side to:

\frac{\prod\limits_{i=1}^{r}(1 + \varphi(p_i))}{\varphi(N)}

Using the fact that \varphi(p_i) = p_i-1, we are left with:

\frac{\prod\limits_{i=1}^{r}p_i}{\varphi(N)} = \frac{N}{\varphi(N)}.

\square

Result 2: Define v(1) = 0, and for n > 0 let v(n) be the number of distinct prime factors of n. Let f = \mu *v then prove that f(n) is either 0 or 1.

Proof:  Since f = \mu * v, it follows that f(n) = \sum \limits_{d|n} \mu(d)v(\frac{n}{d}).

Then f(n) = \mu(1)v(\frac{n}{1}) + \sum \limits_{i} \mu(p_i)\frac{n}{p_i}+\sum \limits_{i,j} \mu(p_ip_j)v(\frac{n}{p_ip_j})\dots+ \mu(p_1p_2\dots p_k)v(\frac{n}{p_1p_2\dots p_k})

The other terms in the sum will become 0, because they will contain a square factor for which the möbius function will be zero.

Now if n = p_1^{a_1}\dots p_k ^{a_k}, define c_i = 1 if a_i = 1 else 0.

\therefore f(n) = k - \sum \limits_i (k-c_i) + \sum\limits_{i,j} (k-c_i-c_j) + \dots + (-1)^k(k-\sum\limits_i c_i)

Collecting terms:

f(n) = k(1 - \binom{k}{1} + \binom{k}{2}- \dots (-1)^k) + \sum\limits_i c_i(1 - \binom{k-1}{1} + \binom{k-1}{2} - \dots + (-1)^{k-1})

or, f(n) = k(1-1)^k + \sum\limits_i c_i(1-1)^{k-1} when k > 1 .

Thus, f(n) = 0, when k>1.

Let’s consider the case when k=1. This means that n = p, where p is prime. Then, f(n) = f(p) = \mu(1)v(\frac{p}{1}) + \mu(p)v(\frac{p}{p}) = 1 + 0 = 1.

Therefore f(n) = 0 or 1.

\square

Result 3: \varphi(n) > \frac{n}{6} for all n with at most 8 distinct prime factors.

This is actually much simpler than it looks. I tried a variety of approaches finally giving up and writing to Dr. Shailesh Shirali (yes, the problem totally tormented me). He too first thought it would be challenging but the next day he came up with a proof, that I reproduce here:

The problem asks you to prove that \frac{\varphi(n)}{n} > \frac{1}{6}, so let us see how small we can make \frac{\varphi(n)}{n} . Since we want to make it as small as possible, it is in our interest to use smaller primes in place of larger primes. Using the given information, the product has at most 8 terms. Therefore, the minimum possible value of \frac{\varphi(n)}{n} using at most 8 terms is going to be the product of 1 - \frac{1}{p} over the first 8 primes.
Evaluating this, we find that the product is  0.171 which exceeds \frac{1}{6}.
Hence the result.

 

Yeah, I was banging my head when I read the proof! Sometimes things can be so deceptive.

 

Advertisements

One thought on “Results about Multiplicative functions

  1. Pingback: Results about Finite-Dimensional Linear Spaces | Math In Operation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s