2
$\begingroup$

I am working on a problem where it has become important to count (or at least bound from above and below) the number of elements of ${\bf Z}/n{\bf Z}$ that have order less than a given $k$, where $2\leq k\leq n$. In the absence of deeper insights, I proceeded to write this as the sum $$\sum_{j=1}^{k-1} [j\backslash n] \varphi(j),$$ where $[j\backslash n]$ is $1$ if $j$ divides $n$ and $0$ otherwise. If $n$ is prime, then this sum equals $1$ for any $2\leq k\leq n$, and when $k=n$, the sum equals $n-\varphi(n)$. But besides these special cases, I haven't been able to get anything more out of this sum.

There are formulas $$\sum_{j\backslash n} \varphi(j) = n\quad\hbox{and}\quad \sum_{j=1}^{n} \varphi(j) = {3\over \pi^2}n^2 + O\big(n(\log n)^{2/3}(\log\log n)^{4/3}\big),$$ but I'm not too sure how to combine them to tackle my summation. I am not too familiar with the totient function, so perhaps this has been studied before. A reference to an asymptotic result like the one on the right above would be an amazing help. Bounds that work for all $n$ and $k$ would be nice, but it would also be okay if $k$ is not allowed to be too big (e.g. $k\sim\log n$).

The number of elements in a group with order less than a given $k$ seems to be a natural question in group theory, so I might be barking up the wrong tree with this sum. Have any other methods been devised to count it?

$\endgroup$
2
  • $\begingroup$ The upper bound $kn^\varepsilon$ is easy; would you be happy with it? It is probably close to what one can prove, anyway. $\endgroup$
    – Seva
    Dec 4, 2020 at 7:39
  • $\begingroup$ @Seva I just came to the realisation that for my problem specifically, I only need very loose bounds, so that would definitely work. However, this is an interesting question in general (perhaps even replacing ${\bf Z}/n{\bf Z}$ with an arbitrary abelian group), and I'd be happy to hear anything that sheds light on it! $\endgroup$ Dec 4, 2020 at 18:39

0

Your Answer

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