How to get a good upper bound on $\sum_{1 \lt d, d|n} \phi(d)/\log d$?

Question

I'm actually interested in a slightly smaller quantity, but I'm willing to accept the following simplification, especially if there are small error terms.

Let's start with $ n \gt 1$, Euler's totient $\phi(n)$, and $$f(n) = \sum_{d \gt 1, d | n} \frac{\phi(d)}{\log d}.$$

I can use obvious estimates to get $n \gt f(n) \geq (n-1)/\log n$. I hope that indeed there is an absolute (independent of $n$) constant $C \lt 2$ so that also $f(n) \lt Cn/ \log n$. The first question then is if my hope can be realized.

Does such a $C \lt 2$ exist, and what is (a good estimate of) its value if it does?

Now for a fixed $n$ I am actually dealing with bounded quantities $b_d$ and other quantities $c_d$ ( which may also depend on $n$ but let's ignore that ) which I am willing to upper bound by $b$ and lower bound by $c \geq 1$ to get the next approximation

$$ g(n) = \sum_{ 1 \lt d, d | n} \frac{ \phi(d) + b }{\log ( cd + 1)} $$ where now if it is easier you can add a $d=1$ term with numerator $0$.

Do we have a good value of $C$ corresponding to $g(n) \lt Cn/ \log n$?

Something that would be really nice for my target function ( of which $g(n)$ can be a rough upper bound) is $g(n) \lt n/(\log n - B)$ for sufficiently large $n$ and some positive constant $B$. Is this possible?

It is tempting to use Moebius inversion to solve this. I am primarily interested in explicit bounds more than exact reformulation though. Is there a nice way to see how to use Mobius inversion here? (I am reading some of the posts on inversion, but am concerned about the size of the error. The usual examples do not have a log term, and I don't know yet how much that changes things.) While I want answers to the above questions, I am willing to accept an answer to the following meta-question:

How do I search on this site and others for terms like those used to define $f(n)$ and $g(n)$?

Gerhard "Hoping To Add Some Knowledge" Paseman, 2015.11.16

Answer 1

As usual, log is almost constant.

Let $\tau(n)$ denote the number of divisors of $n$. For 'small' values of $d$ we have $$\sum_{d|n,d\leq \frac{n}{\tau(n)\log^2 n}} \varphi(d)/\log d\leq \tau(n)\cdot \frac{n}{\tau(n)\log^2 n}=\frac{n}{\log^2 n}.$$ For 'large' $d> n/\tau(n)\log^2 n$ we have $$\log d> \log n-\log \tau(n)-2\log\log n=(1+o(1))\log n,$$ since $\tau(n)=o(n^c)$ for any $c>0$. That is, for such values of $d$ we have $$ \sum_{d|n,d> \frac{n}{\tau(n)\log^2 n}} \varphi(d)/\log d\sim (\log n)^{-1} \sum_{d|n,d> \frac{n}{\tau(n)\log^2 n}} \varphi(d)\sim \frac{n}{\log n}, $$ since $\sum_{d|n} \varphi(d)=n$ and $\sum_{d|n,d\leq \frac{n}{\tau(n)\log^2 n}} \varphi(d)\leq \frac{n}{\log^2 n}$.

Answer 2

As you observe $\sum_{d \leq n} \phi(d) =n$ (clear from looking at fractions) so that for $\alpha \in \mathbb R^{>1}$, the sum restricted to all $d$ with $d^\alpha \geq n$ is at most $\alpha n/\log n$.

To bound the number of $d$ with $d< n^{1/\alpha}$ we will apply the identity:

$$\sum_{d \leq n} (n/d) \phi(d)= \sum_{i=0}^{n-1} \gcd(i,n) = n \mathbb E \left[ \gcd(i,n)\right] $$

$$= n \prod_{p^k |n } \mathbb E [ \gcd(i, p^k) ] = n \prod_{p^k|n}(1-1/p) (k+1) \leq n \prod_{p^k|n} (k+1) $$

and the inequality $\prod_{p^k|n} (k+1) \leq C_\epsilon n^\epsilon$ for all $\epsilon > 0$, which is true as multiplying the left side by $p$ multiplies the right side by $1+1/(k+1)$, which is less than $p^\epsilon$ except for finitely many $p$ and finitely many values of $k$, which together multiply the right side by a bounded amount.

We get that number of $d$ with $d \leq n^{1/\alpha}$ is at most $C_\epsilon n^{1+ \epsilon} / (n /n^{1/k} ) = C_\epsilon n^{1/\alpha + \epsilon} $. Taking $\epsilon < 1 -1/\alpha$, we may bound this by a constant multiple of $n/\log n$, and taking $n$ sufficiently large the constant multiple goes to $0$.

Hence for all $C>1$ we can take $\alpha$ slightly less than $C$ and we have $\sum_{d \leq n} \phi(d)/\log d \leq C n/\log n$ for all $n$ sufficiently large.

Answer 3

I am grateful to Will Sawin and Fedor Petrov for the inspiration their answers provided me. Thanks also to Will Jagy for some bounds on the divisor function $\tau(n)$. Although I still need to show that $F(n) = \sum_{1 \lt d, d|n} \phi(d)/\log d \lt 1.95n/\log n$ holds for all $n \lt 10^{11}$, when I have that, I can use the argument below to show the inequality holds for all $n$. I will use $C$ and later set $C=1.95$.

Let's split the index set into divisors $d \leq d'=n^r$, and $d \gt d'$: $$F(n) = \sum_{1\lt d\leq d', d|n} \frac{\phi(d)}{\log d} + \sum_{d' \lt d, d|n} \frac{\phi(d)}{\log d} \leq \frac{\tau(n)d'}{\log d'} + \frac{n-d'}{\log d'}.$$ The bound of the first sum comes from overestimating the number of terms by $\tau(n)$ and each term by $d'/\log d'$. The bound of the second sum arises from replacing the denominator $\log d$ by $\log d'$ and using a property of $\phi$. For $r=1/2$, and writing $\log d'$ as $(\log n)/2$, we get an upper bound of $(\tau(n)\sqrt{n} + n - \sqrt{n})2/\log n$. As $\tau(n) \leq \sqrt{3n}$, so $F(n)\lt (2+2\sqrt{3}) n/\log n$ for all $n\gt 1$.

We can remove a $\sqrt{3}$ from the constant by observing that $\tau(n)$ can be replaced by the sharper count $(\tau(n)-1)/2$, and since $\tau(n)$ is eventually bounded by $n^s$ for any real $s \gt 0$ and $n$ sufficiently large, we get that the sum of interest is eventually bounded by $2n/\log n$. We can do better.

Let's increase $r$ slightly. Rewriting the right hand side, we get $$F(n) \lt \frac{(\tau(n)-3)n^r +n}{r\log n}.$$ Recounting the divisors (and excluding $1$ and $n$) shows there are at most $\tau(n) - 2$ many which are greater than $1$ and at most $d' \lt n$. For fixed $r$ and increasing $n$, we get that eventually $F(n) \lt n(1+ \epsilon)/r\log n$. Even though this can eventually approach $1$ by increasing $r$ and $n$, we want to do better, especially as $\tau(n)n^r$ stays close to or above $n$ for some moderately large $n$ and $r\gt 1/2$.

As $r$ gets larger, the estimate for the upper sum shrinks and approaches the true value of this sum, while the bound on the lower sum grows like $\tau(n)n^r/r\log n$. I need a better estimate of the lower sum if I want $F(n) \lt Cn/\log n$ for all $n$, not just sufficiently large $n$.

I thus assume $F(m) \lt Cm/\log m$ for all $m$ less than a bound $N$, and then use an improved estimate to get $F(n) \lt Cn/\log n$ for $n \geq N$. I use (assuming all $d|n$) $$\sum_{1\lt d \leq d'} \frac{\phi(d)}{\log d} \leq \sum_{d \in S} \frac{Cd}{\log d} \leq \frac{|S|Cd'}{\log d'}.$$ Here $S$ is a maximal irredundant set of covering divisors $d$ with $d \leq d'$. So for any divisor $f \leq d'$ of $n$, there is at least one $d \in S$ with $f|d$, and no two members of $S$ divide one another. Then every term $\phi(f)/\log f$ is incorporated into some term $Cd/\log d$ for one or more $d \in S$.

The improvement comes from seeing that $|S|\leq h(n)=\tau(n)/(1+a_e)$, with $a_e$ the largest exponent occuring in the prime factorization of $n$. (Proof of this will appear elsewhere, say in a comment.) I encourage study of the growth of $h$-champions, which seem to be more sparsely distributed than highly composite numbers.

I now choose $d'$ according to a tunable parameter $k$, so that I guarantee $|S|Cd'/\log d' \leq n/k\log n$, or in terms of $r=\log d'/\log n$, so that $|S|Ck \leq rn^{1-r}$. Then when $h(n)C/r \leq n^{1-r}/k$ and $1/k + 1/r \leq C$, we get the desired inequality.

We have $h(n) \leq \tau(n)/2$ for all $n$. This seems to tip the balance. When we pick $4/7$ or $5/9$ for $r$, and choose $k$ to be $4$ or $20/3$ respectively to get $(1/r + 1/k)=C=1.95$, computer simulation suggests $h(n)Ck \lt rn^{1-r}$ for all $n \gt 5$ times $10^8$. On the theory side, we compare $\tau(n)Ck/2r$ with $n^{1-r}$ using upper bounds on $\tau(n)$ like $1152(n/367567200)^{0.244651}$ to get that the bound holds for all $n\gt 1.3$ times $10^{10}$. So the bound $F(n) \lt 1.95n/\log n$ will be established for all $n$ once it is established for all the troublesome cases below $10^{11}$. Computer experimentation gives that $F(n)\log n/n$ achieves a maximum of less than $1.607$ when $n=60$ for integral $n \in [2,10^8)$, so I'm feeling pretty good that $C=1.95$ will work for all $n$.

Gerhard "Gentlemen, Start Your Processor Cores" Paseman, 2015.11.29

Answer 4

I am putting the final touches on a writeup (approximately 12 pages) which gives $f(n) \lt 1.607 n/\log n$ and a little more. Those who wish a copy may request one by email.

The general idea (with much detail omitted) is this: for every integer $m$ find where possible $n\lt m$ with $f(m)n\log m \lt f(n)m\log n$, by replacing a prime power factor of $m$ with a smaller one to get $n$. This mostly reduces the problem to showing the desired inequality holds for those $n$ all of whose prime factors are the first $j$ primes. Now use the set $S$ (divisor antichain) and check all special $n$ to see that they satisfy either the bound on $|S|$ ($|S| \lt (r - 1/C)n^{1-r}$ which implies $f(n) \lt Cn/\log n$) or else satisfy $f(n) \lt 1.607 n/\log n$. One can show by hand that the $|S|$ bound will be satisfied for $j \gt 14$ if either the $|S|$ or the $f$ bound is satisfied for $j\leq 14$. The $j \leq 14$ case comes with bounded exponents which lead to a feasible computer calculation which should take less than a day. The $|S|$ bound gives the result, as shown in the other post.

Gerhard "Anyway, That Is The Plan" Paseman, 2016.02.13.