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

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

• It seems I am interested in bounding from above sum of $(\phi(d)\log n)/(n\log d)$ over all divisors d of n which are greater than 1. This might be in the literature; I am hoping someone will recognize it and provide a reference. Gerhard "So Imagine A Reference-Request Tag" Paseman, 2015.11.16 – Gerhard Paseman Nov 16 '15 at 21:31

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}$.

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.

• The $\ll n \log n$ step is not correct. You can bound it by $n 2^{\omega(n)}$, but this may not be bounded by $n\log n$ since $2^{\omega(n)}$ can be as large as $2^{\log n/\log \log n}$. Of course the spirit of your proof is fine! – Lucia Nov 16 '15 at 22:06
• Great! Just so it is agonizingly clear, I can take $k$ in your argument to be a real parameter which approaches 1 from above arbitrarily closely? Also, if I look at max (f(n)log n)/n, that seems to be achieved for n=60 with a value of less than 1.607 (assuming my code is correct). Do the numerics look good also? Gerhard "Also Accepts Slightly Annoying Clarity" Paseman, 2015.11.16 – Gerhard Paseman Nov 16 '15 at 22:07
• @LuciaI Good point! But I don't think that's quite right either as $\omega(n)$ only gives the number of distinct prime factors, but this grows arbitrarily large with only a single prime factor. – Will Sawin Nov 16 '15 at 23:02
• @GerhardPaseman Yes, precisely that. I have no idea about the numerics but this method can certainly be made effective. – Will Sawin Nov 16 '15 at 23:15
• I have trouble following your estimate from the second displayed line on down. I think it is easier to just use $n^{1/\alpha}$ to bound the number of $d \lt n^{1/\alpha}$ and then tune $\alpha$ to get a nice $C$. Thank you for the answer. If you have more information about explicit values, I invite you to add it. Gerhard "Likes Seeing Real Number Estimates" Paseman, 2015.11.17 – Gerhard Paseman Nov 17 '15 at 15:45

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

• $S$ is a special antichain in the divisibility lattice of $n$. Here are hints for three separate proofs that its size is bounded by $\tau(n)/(1 + a_e)$: 1) Induction: for a chain ($n$ a prime power), $h(n)$ is 1. Now multiply $n$ by a smaller prime power. 2) Pigeonhole: Write elements of $S$ as mp^k where prime p occurs the most in factorizing n. No two incomparable elements can have the same $m$. 3) Carpentry: Visualize the lattice as a long two-by-four balanced on a tip. Consider $S$ below a horizontal cut. Gerhard "Likes Proofs Using Saw Cuts" Paseman, 2015.11.29 – Gerhard Paseman Nov 30 '15 at 0:49

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.