Multiplicative functions and almost division

A function f(n) with range in the integers is said to be multiplicative if f(ab)=f(a)f(b) whenever a and b are relatively prime. A function is said to be completely multiplicative if this applies for all a and b whether or not a and b are relatively prime. Some of my prior posts have discussed multiplicative functions (e.g. this post on Mersenne primes and perfect numbers). An important thing to note is that a multiplicative function is determined by its values at prime powers, while a completely multiplicative function is determined by its values at primes.

Let f and g be two functions from the positive integers to the integers. Let K(f,g)(x) be the number of n less than x such that f(n) does not divide g(n). We say that f almost always divides g if f(n) divides g(n) for almost all n if K(f,g)(x) = o(x) (or to put it another way, the set of exceptions has density zero). Obviously, almost divisibility is weaker than divisibility. Almost divisibility shares many of the properties of divisibility; it is a transitive relation. One important difference between divisibility and almost divisibility is that among positive functions, divisibility is an anti-symmetric relation (that is, if fg, and gf then f=g). This is not true for almost divisibility, but is true for almost divisibility if we restrict our attention to multiplicative functions.

Are there interesting examples of non-trivial almost divisibility where one doesn't have divisibility? Yes. Let σ(n) be the sum of the positive divisors of n, and let τ(n) be the number of positive divisors of n. Erdos showed that τ almost divides σ and showed through similar logic that τ almost divides the Euler φ function.

Why am I thinking about these functions? I noticed that some multiplicative functions divide a positive completely multiplicative function. Thus, for example φ divides the completely multiplicative f such that for any prime p, f(p)=p(p-1). However, other cases don't have such examples. It isn't too hard to show that there's no such completely multiplicative function for τ or σ. But, the situation changes drastically in the case of almost divisibility. We in fact have that for any function f from the natural number to the natural numbers, there is a completely multiplicative function g such that f almost divides g. We shall call such a g, a "completely multiplicative almost multiple" (or CMAM) Moreover, we can construct such a function explicitly.

Proposition: Let f(n) be a function from N to N, and let g(n) be the completely multiplicative function defined by g(p) = is the least common multiple of f(1),f(2),f(3)...f(2^p). Then g is a completely multiplicative almost multiple of f.

In order to prove this result, we need another notion, that of normal order. Often, to describe the behavior of a poorly behaved function, number theorists like to show that it asymptotic to a well behaved function in the sense that the limit of their ratios is 1. Thus, for example, the prime number theorem says that the poorly behaved function π(n) that counts the number of primes that are at most n is asymptotic to n/log n. But for many functions we care about this sort of statement is much too strong. Let ω(n) be the number of distinct prime divisors of n, and let Ω(n) be the total number of prime factors. Then these functions hit 1 infinitely often and so clearly are not asymptotic to any nice functions. However, ω and Ω possess a normal order, in the sense that for any ε > 0, we have that excepting a set of density 0, (1-ε) log log n < ω(n) < (1+ε) log log n and the same holds for Ω(n). (More refined estimates exist but we don't need them for these remarks.) An important heuristic that stems from this result is that most numbers look very close to square free in the sense that they have a lot of prime factors and very few of the prime factors occur more than once.

Now, to prove our result, we observe that excepting a set of density zero, we have Ω(n) < 2 log log n . So ignoring a set of density zero, the largest prime factor of n, call it p, is at least n^(1/(2 log log n)), and so f(n) appears as a term in g(p).

Obviously, for any f, the constructed CMAM grows very fast. However, this doesn't need to be the case, and it might be that in specific contexts one can substantially reduce this growth rate. So, this leaves me with three questions, one broad and two specific:

1) How much can we improve on reducing the growth rate of the CMAM for a function f? There are obvious steps to take in the construction but they still make it grow very quickly.

2) Let g(n) be a CMAM for σ. Does it follow that g(n) is not O(n^k) for any k? I strongly suspect this is true but don't see how to prove it.

3) One can through more careful work show that there is a CMAM for τ that is 0(x). What is the best possible growth rate for such a function?

While I've seen individual papers that have discussed specific functions being almost divisible by each other, I'm not aware any substantial work on their general structure. I don't know if this is due to my ignorance of the literature, the fault of almost divisibility being too weak a property to be interesting, or some other cause.