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

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

• This is related to distribution of totatives of n. Canadian Journal of Math. in 1955 has an article by D.H. Lehmer of a similar title where he looks at how the distribution varies from the average in the interval (qn/k, (q+1)n/k) for various small k including your case of k=4. You should find this and later articles (e.g. Codeca and Nair) helpful for your D(n). MathOverflow questions 88777 and 37679 are favorites of mine, which partly address your question and show related material. Gerhard "I'm Also Finding It Useful" Paseman, 2014.06.20 – Gerhard Paseman Jun 21 '14 at 2:59
• If I remember Lehmer's notation, your D(n) is some multiple (maybe even 1) of 2(E(4,0,n) - E(4,1,n)). Remember the multiplicative factor he introduces, which threw me for a little bit. Gerhard "Carefully Reading Between The Ticks" Paseman, 2014.06.20 – Gerhard Paseman Jun 21 '14 at 3:06

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.
• Thanks Gerhard and Lucia. I think you want $D(p^k)=(-1)^k2$ for $p\equiv 3\pmod 4$. D.H. Lehmer's paper is nice: my proofs are simpler but less general too. – Glasby Jun 23 '14 at 8:01
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}$.
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.