Number of primitive $n$th roots with positive versus negative real parts

Question

Does anyone know a reference to the following results, which I can prove, but I suspect may be known. Let $R(n)$ denote the number of primitive $n$th roots of unity with positive real part, and $L(n)$ the number of primitive $n$th roots of unity with negative real part. Then $\varphi(n)=R(n)+L(n)$ for $n\ne 4$. I am particularly interested in (references to) an explicit formula for the difference function $D(n):=R(n)-L(n)$. I was surprised to observe (and then prove) that the values of $D(n)$ are zero, or plus or minus a power of 2. For example, $$ D(3)=-2,\quad D(6)=2,\quad D(8)=0,\quad D(21)=4,\quad D(42)=-4. $$ Three applications of the formula are: $\limsup_{n\to\infty} D(n)=\infty$, $\lim_{n\to\infty}D(n)/\varphi(n)=0$, and $\frac{\varphi(n)}{3}\leqslant L(n)\leqslant\frac{2\varphi(n)}{3}$ for $n>6$.

Answer 1

As Gerhard Paseman has commented, more general problems were studied by D.H. Lehmer in his paper The distribution of totatives. In particular, see section 5 of the paper. From his work it follows that $D(n)$ is a multiplicative function defined on prime powers as follows: $D(p^k)=0$ if $p\equiv 1\pmod 4$ for all $k\ge 1$; $D(p^k)=(-1)^k\times 2$ if $p\equiv 3\pmod 4$ and for all $k\ge 1$; and finally $D(2)=-1$, and $D(2^k)=0$ for all $k\ge 2$. The proofs are based on the simple sieve of Eratosthenes, and clearly this formula establishes that all $D(n)$ are zero or a power of $2$ in magnitude; the other assertions in the problem also follow easily.

Answer 2

I am not sure if this is the explicit formula you refer to, but the Erastothenes-Legendre sieve gives $$D(n)=\sum_{d\mid P_n}\mu(d)\left(2\left\lfloor \frac{n}{4d}\right\rfloor+\left\lfloor \frac{n}{d}\right\rfloor-2\left\lfloor \frac{3n}{4d}\right\rfloor\right),$$ where $P_n$ is the product of the prime divisors of $n$.

Since $L(n)$ counts those roots $e^{\frac{2\pi i k}{n}}$ for which $gcd(k,n)=1$ and $\frac{n}{4}<k<\frac{3n}{4}$, one sees by applying the Erastothenes-Legendre sieve similarly that $$L(n)=\frac{n}{2}\prod_{p\mid n }\left(1-\frac{1}{p}\right)+O(2^{\omega(n)})=\frac{\varphi(n)}{2}+O(2^{\omega(n)}),$$ where $\omega(n)$ is the number of distinct prime factors and the constant in the big $O$ notation can be taken to be $1$. Since $\omega(n)$ is almost always at most $\frac{4}{3}\log \log n$, say, the error is almost always $O(\log n)$. Even in the worst case, we have $\omega(n)\leq \frac{2\log n}{\log \log n}$ for large $n$, so the error is $n^{\frac{2\log 2}{\log \log n}}$, which is small. This proves your third application, but the problem is that the sieve gives the exact same formula for $R(n)$, so this gives only $D(n)=O(2^{\omega(n)})$, which is however enough to prove your second application, as it is well known that $\varphi(n)\gg \frac{n}{\log n}$.

Answer 3

There are (at least) two explicit formulas. First, $D(n)$ can be shown to be a multiplicative function (this means $\gcd(m,n)=1$ implies $D(mn)=D(m)D(n)$), and the values of $D(p^k)$ for all primes $p$ and positive integers $k$ are described in D.H. Lehmer's paper and Lucia's answer. Second, there is a formula similar to, but simpler than Joni's formula, namely $$D(n)=\sum_{d\mid n}\mu(d)\left(4\left\lfloor\frac n{4d}\right\rfloor-\frac nd\right)=\sum_{d\mid n}\mu(\frac nd)\left(4\left\lfloor\frac d4\right\rfloor-d\right).$$ I used this formula to prove that $D$ is multiplicative. Note that the Dirichlet convolution $(f\,*\,g)(n)=\sum_{d\mid n}f(d)g(\frac nd)$ of two multiplicative functions $f$ and $g$ is necessarily multiplicative, but this fact can not be used to show that $D=\mu\,*\,g$ multiplicative as $g(n)=4\left\lfloor\frac n4\right\rfloor-n$ is not multiplicative.