1
$\begingroup$

When thinking about an unrelated problem, I wanted to sum

$$\sum_{k\in[\sqrt n,2\sqrt n]}\#\{j\leq k/5:\gcd(k,j)=1\}$$ and I wanted this sum to be $\Theta(n)$. From the wikipedia I can see that if we take away the restriction of $\leq n/5$ we do have our result. A natural definition to consider given this is the following

$$\varphi(n,\varepsilon):=\#\{k\leq\varepsilon n:\gcd(k,n)=1\}$$

My question is the following

Question. Can we prove that for every fixed $\varepsilon\in(0,1)$ we have $\varphi(n,\varepsilon)=\Theta(\varphi(n))$?

I've been trying to do an averaging argument to prove that it holds true for almost every $n$ (which at least would've been enough for my original application), but I'm not too well-versed in number theory so I haven't been succesful

$\endgroup$
2
  • $\begingroup$ I don't know (yet?) about $\varphi(n,\varepsilon)$, but I can prove that your sum is $\Theta(n)$ for arbitrary values of $\frac{1}{5}$. Would you consider that an answer? $\endgroup$ Commented Nov 20 at 20:26
  • $\begingroup$ @DermotCraddock sure! $\endgroup$ Commented Nov 20 at 20:37

1 Answer 1

Reset to default
5
$\begingroup$

The answer is yes. Almost surely there's an answer already on this site, but since I couldn't find it after searching, I'll provide a complete proof—the general method is important to remember.

The key idea is to apply the fundamental identity $$ \sum_{d\mid m} \mu(d) = \begin{cases} 1, &\text{if } m=1, \\ 0, &\text{if } m>1\end{cases} $$ with $m=\gcd(j,n)$. For any real numbers $x<y$, we obtain \begin{align*} \#\{ x < j \le y\colon \gcd(j,n)=1\} &= \sum_{x<j\le y} \sum_{d\mid\gcd(j,n)} \mu(d) \\ &= \sum_{d\mid n} \mu(d) \sum_{\substack{x<j\le y \\ d\mid j}} 1 \\ &= \sum_{d\mid n} \mu(d) \biggl( \Bigl\lfloor \frac yd\Bigr\rfloor - \Bigl\lfloor \frac xd\Bigr\rfloor \biggr) \\ &= \sum_{d\mid n} \mu(d) \biggl( \frac{y-x}d + O(1) \biggr) \\ &= (y-x) \sum_{d\mid n} \frac{\mu(d)}d + O\biggl( \sum_{d\mid n} |\mu(d)| \biggr) \\ &= (y-x)\frac{\phi(n)}n + O(2^{\omega(n)}), \end{align*} where $\omega(n)$ is the number of distinct prime factors of $n$.

In particular, $\phi(n) \gg_\delta n^{1-\delta}$ and $2^{\omega(n)} \ll_\delta n^\delta$ for every $\delta>0$, so the above provides an asymptotic formula as soon as the interval $(x,y]$ has length greater than $n^\delta$. In particular, taking $(x,y] = (0,\varepsilon n]$ handles the question in the OP.

$\endgroup$
3
  • 1
    $\begingroup$ There's a typo in the last equality, it should be $\phi(n)/n$, right? $\endgroup$ Commented Nov 20 at 20:48
  • $\begingroup$ Right, @BrunoAndrades, $\sum_{d \mid n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$. $\endgroup$ Commented Nov 20 at 21:13
  • $\begingroup$ Thanks for the answer! That's a nice trick to know $\endgroup$ Commented Nov 20 at 22:15

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.