1
$\begingroup$

Given, $f$ and $g$ as functions with domain and range in the integers, we will write $S(f,g)$ to be the set of $n$ such that $f(n)|g(n)$. We will write $f^2$ to just be $f(n)^2$

We will say that $f$ almost divides $g$, which we will write as $f|_A g$ if $S(f,g)$ has natural density 1. For example, due to a result of Bateman, Erdos, Pomerance and Straus, that $\tau(n) |_A \sigma(n)$, but that it is not true that $\tau(n)^2 |_A \sigma(n)$. Here $\tau(n)$ is the number of divisors of $n$, and $\sigma(n)$ is the sum of the divisors of $n$. (They do not use this language, and in fact show the stronger result the set of $n$ where $\tau^2(n)|\sigma(n)$ has density $\frac{1}{2}$).

Let $F$ be the set of multiplicative functions from $\mathbb{Z}^+$ to $\mathbb{Z}^+$. Then almost division is a partial order on $F$

Proof: Reflexivity and transitivity are easy The only difficulty is to show that if $f |_A g$ and $g |_A f$ then $f=g.$ To see this, note that this means that on a set of density 1, $f(n)|g(n)$ and on a set of density 1, $g(n)|f(n)$. So on a set of density one, $f(n)=g(n)$. So if $f \neq g$, then there is some prime power $p^a$ such that $f(p^a) \neq g(p^a)$. But then for any $m$, where $f(m)=g(m)$, on a set of and $(m,p)=1$, we have $f(mp^a)=f(m)f(p^a) \neq g(m)g(p^a) = g(mp^a)$, and $m$ satisfying this have density $\frac{p-1}{p}$, which is a contradiction.

We also have that for any function $f$ with domain and range in the non-zero integers, there is a completely multiplicative function $c$ such that $f |_A c$. To see this, note that almost all positive integers have a prime factor which is at least $n^\frac{1}{2\log \log n}$. (Tighter bounds come immediately from the Hardy-Ramanujan theorem for $\omega(n)$ but we do not need them here.) So let $c(n)$ be defined by being completely multiplicative and for any given prime $p$, set $c(p) = f(1)f(2)... f(\lceil e^{e^p} \rceil)$.

We'll say that a function $f$ strongly fails to divide $g$, if the set of $n$, where $f(n)|g(n)$ has density zero. This is in some sense the opposite of being almost divisible. Examples here are how $n$ strongly fails to divide $\sigma(n)$, and $\phi$ strongly fails to divide $n$.

We'll say that a multiplicative function $f(n)$ is polynomial-controlled if for any $a$ there is a polynomial $Q_a(x)$ such that for all primes $p$, $f(p^a)=Q_a(p)$. Notice that the choice of polynomial is allowed to depend on $a$, but is then otherwise the same. Most classical multiplicative functions are polynomial-controlled, including $\tau$, $\sigma$, $\mu$, $\phi$, and $\psi$. We'll say that a positive multiplicative function is positively polynomial-controlled if it is polynomial-controlled and for any $a$, the coefficients of the corresponding $Q_a(x)$ are non-negative. For example, $\sigma(n)$ is positively polynomial controlled because $\sigma(p^a) = 1+p+p^2 \cdots + p^a$. But $\phi(n)$ is not positively polynomial controlled because $\phi(p^a)= p^a - p^{a-1}$.

Let $\beta(n)$ be the multiplicative function given by $\beta(p^a) = p-1$ for all $a$ and primes $p$. Notice that $\beta$ is polynomial-controlled but not positively polynomial controlled.

Question Is it true that if $f$ is a multiplicative function which is positively polynomial-controlled, then $\beta$ strongly fails to divide $f$?

$\endgroup$
1
  • $\begingroup$ If $p=2$ and $a=1$, then $\beta(p^a) = \beta(2^1) = \beta(2) = 2 - 1 = 1$ and $\sigma(p^a) = \sigma(2^1) = \sigma(2) = 2 + 1 = 3$. (Note that $1 \mid 3$ holds.) $\endgroup$ Jan 12, 2023 at 22:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.