For which $n$ does $p_n(x)=\sum\limits_{{k=1,(k,n)=1}}^n o(k) x^k $ have exactly two real roots?

Question

Let $n\in\mathbb{N}$ be fixed and denote by $o(k)$ the multiplicative order of $k$ modulo $n$. Define $$p_n(x)=\sum_{\substack{k=1 \\ (k,n)=1}}^n o(k) x^k ;$$here the sum is taken over $k$ that are coprime to $n$, so $o(k)$ is well-defined. Here are two simple observations:

• If $n$ is even, $p_n(x)$ is odd. Further, in this case it only has one real root.
• If $n$ is odd, aside from $n=1$ it seems that $n$ has an even number of real roots. Here is a picture of the number of roots for $1\le n \le 1000$ and $n$ odd.

I checked OEIS and it didn't return any matches. Perhaps this problem is very difficult, as I don't know how easy it is to compute $o(k)$ for arbitrary $n$. If we denote $R(n)$ as the number of real roots of $p_n(x)$ for odd $n$, here are some questions I think are worth pursuing about $R(n$):

1. Is there an estimate or asymptotic for $R(n)$? Is there an upper bound for $R(n)$?
2. When does $R(n)=2$? For $1\le n\le 1000$, this occured when $n=\{3, 5, 7, 11, 31, 89, 127, 257, 331, 635\}$; OEIS didn't recognize this sequence either.
3. As a follow-up, does $R(n)=2$ infinitely often?

Answer 1

$\deg(p_n) = n-1$.

$p_n$ has $2d_n$ non-real roots thus $n-1-2d_n$ real roots counted with multiplicity, maybe you just didn't find the rare cases where it has some double real roots.

For $n$ even then $p_n$ is odd and it is $> 0$ on $(0,\infty)$ thus its only one real root is at $0$.

The same holds when replacing $order(k\bmod n)$ by any non-negative function such that $f(n-1)>0$.

Not convinced that we can say anything about $R(n)$, do more simulations and see if some non-random estimate pops up.

Answer 2

Decomposition of $p_n$

Let $n$ be odd. Then we have $$ (n,2k)=1 \wedge 2k<n \Leftrightarrow (n,k)=1 \wedge k<n/2. $$ Thus, the terms with even exponents can be written as $$ \sum_{\ell<\frac n2} o(2\ell) x^{2\ell}. $$ The remaining odd numbers can be written as $n-2\ell$. Thus, we can write $p_n$ as $$ p_n(x)=\sum_{\ell<\frac n2} o(2\ell) x^{2\ell} + \sum_{\ell<\frac n2} o(-2\ell) x^{n-2\ell} \ \ \ (1) $$ so that the first sum gives even exponents, the second sum gives odd exponents.

Obviously, there are no positive real roots. As observed in comments, $x=0$ is a real root. Aside from $x=0$, all real roots must be negative. Then $-x\leq 0$ is a real root if and only if the following holds. $$ \sum_{\ell<\frac n2} o(2\ell) x^{2\ell} = \sum_{\ell < \frac n2} o(-2\ell) x^{n-2\ell}. \ \ \ (2) $$

For any $k$ with $(n,k)=1$, there is a relation between $o(k)$ and $o(-k)$. Explicitly, this is $$ o(-k)=\begin{cases} \frac{o(k)}2 &\mbox{ if }o(k) \mbox{ is even and } \frac{o(k)}2 \mbox{ is odd}\\ o(k) &\mbox{ if } o(k) \mbox{ is even and }\frac{o(k)}2 \mbox{ is even}\\ 2o(k) &\mbox{ if } o(k) \mbox{ is odd.} \end{cases} \ \ \ (3) $$ This shows that we only need to compute $o(k)$ when $k<\frac n2$. Then $o(-k)$ is obtained as above. This might help reducing the computing time.

An upper bound of $R(n)$

By Descartes' rule of signs, we have $$ R(n)\leq \phi(n). $$

Zero-free intervals

Let $\lambda(n)$ be the exponent of the group $(\mathbb{Z}/n\mathbb{Z})^*$ (Carmichael's function). The LHS of (2) is $2x^{n-1} + \sum_{2\ell<n-1} o(2\ell)x^{2\ell}$, the RHS of (2) is $x+\sum_{2\ell<n-1}o(-2\ell)x^{n-2\ell}$.

First, we use $o(2\ell)\geq 0$ on LHS of (2), and $o(-2\ell)\leq \lambda(n)$ on RHS of (2). By the geometric series partial sum formula, $$ x + \lambda(n) \frac{x^3-x^n}{1-x^2} \geq \text{RHS} . $$ On the other hand, $$ \text{LHS}\geq 2x^{n-1}. $$ After some manipulation, we have $\lambda(n) x^n + 2x^{n-1} < 2x^{n+1} + x + (\lambda(n)-1) x^3$ when $x \geq \tau=\frac{\lambda(n)}4+\sqrt{1+\frac{\lambda(n)^2}{16}}$. This gives $$ \text{LHS}\geq 2x^{n-1} > x + \lambda(n) \frac{x^3-x^n}{1-x^2} \geq \text{RHS}. $$ Thus, there is no real root of (2) when $x\geq \tau$.

Next, we use $o(2\ell)\leq \lambda(n)$ on LHS of (2), and $o(-2\ell)\geq 0$ on RHS of (2). By the geometric series partial sum formula, $$ \text{LHS}\leq 2x^{n-1} +\lambda(n) \frac{x^2-x^{n-1}}{1-x^2}. $$ On the other hand, $$ \text{RHS}\geq x. $$ After some manipulation, we have $\lambda(n) x^2 + x^3 < 2x^{n+1} + (\lambda(n)-2)x^{n-1} + x$ when $0<x\leq \mu=-\frac{\lambda(n)}2+\sqrt{1+\frac{\lambda(n)^2}4}$. This gives $$ \text{LHS}\leq 2x^{n-1} +\lambda(n) \frac{x^2-x^{n-1}}{1-x^2}<x\leq \text{RHS}. $$ Thus, there is no real root of (2) when $0<x\leq \mu$.

Hence, the equation (1) does not have any real root when $$ x\in \left(-\infty, -\left(\frac{\lambda(n)}4+\sqrt{1+\frac{\lambda(n)^2}{16}}\right)\right] \cup \left[-\left(-\frac{\lambda(n)}2+\sqrt{1+\frac{\lambda(n)^2}4}\right), 0\right). $$ By Intermediate Value Theorem, there is at least one real root of (2) in the interval $(\mu,\tau)$. Therefore, there is at least one real root of (1) in the interval $(-\tau,-\mu)$ for any odd $n$.

Fermat prime case

Let $n=2^{2^m}+1$ be Fermat prime. Then by (3), we have $$ o(-2\ell)=o(2\ell) \ \textrm{ if } 2\ell < n-1. $$ Thus, we obtain $$ \textrm{LHS} = 2x^{n-1} + \sum_{2\ell < n-1} o(2\ell) x^{2\ell}, $$ $$ \textrm{RHS} = x + \sum_{2\ell < n-1} o(2\ell) x^{n-2\ell}. $$

For $x=1$, we see that $$ \textrm{LHS}=2+\sum_{2\ell < n-1} o(2\ell), $$ $$ \textrm{RHS} = 1 + \sum_{2\ell < n-1} o(2\ell). $$ This gives $\textrm{LHS} = \textrm{RHS}+1 > \textrm{RHS}$ at $x=1$.

Previously, we have seen that $\textrm{LHS}<\textrm{RHS}$ if $0<x\leq \mu$. Since $\mu<1$, we obtain that there is at least one root of (2) in the interval $(\mu, 1)$. Hence, for $n=3,5,17,257,65537$, there is a real root of (1) in the interval $(-1,-\mu)$.

Currently, we do not know whether there are infinitely many Fermat primes.

Answer 3

With the admission that this isn't an answer per se but an interesting bit of data, this wasn't going to fit in just a comment.

I noticed that a lot of values of $n$ had a root very close to $x=-1$. Like, very, very close. I thought "Hey, what if we calculate the function's value at $x=-1$ and see what we get."

I got a lot of $1$s. A bunch of other numbers as well, of course, but too many $1$s. If we treat $\text{ord}_n(0)$ as something that is defined, and set it to $\text{ord}_n(0) = -1$, here's the list of values of $n < 5000$ that have a root at exactly $x = -1$:

$$n = \{3, 5, 9, 15, 17, 25, 27, 29, 33, 35, 45, 51, 65, 69, 75, 81, 85, 87, 99, 115, 125, 135, 141, 143, 145, 153, 165, 177, 185, 195, 221, 225, 243, 247, 249, 255, 257, 289, 321, 357, 365, 375, 405, 423, 425, 445, 455, 459, 477, 481, 485, 501, 535, 537, 561, 565, 575, 585, 625, 641, 675, 679, 681, 705, 729, 765, 771, 789, 825, 841, 845, 867, 915, 935, 951, 965, 1041, 1059, 1071, 1077, 1105, 1109, 1125, 1149, 1173, 1215, 1275, 1285, 1287, 1345, 1377, 1401, 1411, 1435, 1437, 1445, 1479, 1509, 1513, 1515, 1547, 1565, 1605, 1689, 1735, 1755, 1761, 1765, 1799, 1815, 1819, 1875, 1923, 1945, 1955, 1977, 2025, 2037, 2115, 2125, 2157, 2187, 2235, 2245, 2255, 2295, 2313, 2329, 2415, 2425, 2509, 2517, 2535, 2589, 2601, 2661, 2675, 2787, 2805, 2827, 2845, 2873, 2875, 2895, 2949, 3009, 3057, 3125, 3185, 3205, 3237, 3315, 3349, 3375, 3435, 3561, 3617, 3645, 3825, 3849, 3855, 3921, 3957, 3961, 3995, 4101, 4125, 4131, 4199, 4205, 4277, 4315, 4317, 4335, 4369, 4461, 4569, 4575, 4589, 4675, 4857, 4913, 4947, 4981\}$$

I have no clue how to interpret this, or whether it can be usefully interpreted. While these get sparser as you go up the number line, they keep appearing. The smallest above $100000$ is $n = 100041$; I haven't yet found one above $n = 10^6$.