We have that $\phi(n)$ is the number of positive integers less than $n$ and relatively prime to $n$.

I tried to extend this definition by working with $\phi_x(n)$, which is the number of positive integer less than $x$ and relatively prime to $n$. I wonder if there was a research about this extension before, because I found a very interesting inequality. (haven't proved yet, but I checked for some value of $m,n$)

Let $m,n$ be positive integers. Then we have:

$\phi(1)+\phi(2)+\cdots+\phi(m)+\phi_n(1)+\phi_n(2)+\cdots+\phi_n(m) \geq \phi(n+1)+\phi(n+2)+\cdots+\phi(n+m)$

Does anyone have any hint for this or any resources related to $\phi_x(n)$? Thank you in advance.


I don't really understand the practicality of $\phi_x(n)$. What's your purpose for studying it?

In any case, note that $\phi_n(m) = \phi(m)$ if $n \geq m$. This allows us to show that your inequality is false in certain ranges. Namely, if $n \geq m$, then \[\sum_{k \leq m} (\phi(k) + \phi_n(k)) = 2 \sum_{k \leq m} \phi(k) = \frac{6}{\pi^2} m^2 + O(m \log m),\] while \[\sum_{n + 1 \leq k \leq n + m} \phi(k) = \frac{3}{\pi^2} (n + m)^2 + O((n + m) \log (n + m)) - \frac{3}{\pi^2} (n + 1)^2 + O((n + 1) \log (n + 1)),\] which is \[\frac{3}{\pi^2} m(2n + m) + O(n \log n).\] It follows that \[\sum_{n + 1 \leq k \leq n + m} \phi(k) - \sum_{k \leq m} (\phi(k) + \phi_n(k)) = \frac{3}{\pi^2} m(2n - m) + O(n \log n).\] So if $(\log n)^2 \ll m \leq n$, say, then the right-hand side is positive for all sufficiently large $n$, contradicting your inequality.

  • $\begingroup$ why is $\phi_n(m) = \phi(m)$ for $n \ge m$? consider $n = 2m$. The number of integers less than $2m$ and relatively prime to $m$ is not the same as number of integers less than $m$ and relatively prime to $m$. $\endgroup$
    – sku
    Jun 22 '17 at 14:48
  • $\begingroup$ Ah, I misread.. $\endgroup$ Jun 22 '17 at 15:24

$\phi(x,n) = \sum\limits_{k \le x} \left[\frac{1}{(n,k)}\right] = \sum\limits_{k \le x} \sum\limits_{d \mid (n,k)} \mu(d) = \sum\limits_{k \le x} \sum\limits_{d \mid n, d\mid k} \mu(d)$

For a fixed divisor $d$ of $n$, we sum over all $k$ in the range $1 \le k \le x$ which are multiples of $d$. We can write $k = qd$, then $1 \le k \le n$ only if $1 \le q \le \left[\frac{x}{d}\right]$

Hence $\phi(x,n) = \sum\limits_{d \mid n} \sum\limits_{q = 1}^{[x/d]} \mu(d) =\sum\limits_{d \mid n} \mu(d) \sum\limits_{q = 1}^{[x/d]} 1 = \sum\limits_{d \mid n} \mu(d) \left[\frac{x}{d}\right]$

This looks correct as $\phi(n,n) = \sum\limits_{d \mid n} \mu(d) \left[\frac{n}{d}\right] = \sum\limits_{d \mid n} \mu(d) \frac{n}{d} = \phi(n)$

  • $\begingroup$ The formula is indeed correct since this is exactly the exercise 9 of chapter 2 of Apostol's Introduction to Analytic Number Theory $\endgroup$
    – TravorLZH
    Sep 10 '20 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.