Distribution Of Divisor Sums Modulo 32

Consider the polynomial $p_n (x) = \prod_{k=2}^{n} \left(\sum_{d\vert n} x^d \right) = (x+x^2)(x+x^3)(x+x^2+x^4) \cdots$ Let $\omega$ be a primitive $32$ nd root of unity. Then, a roots of unity filter gives $P(n) = \frac{1}{32 p_n (1)}\sum_{i=0}^{31} p_n (\omega^i).$ Now, note that for each $i$ , by Dirichlet's theorem , we can find a prime $p$ of the form $2^{i+1} m + 2^i + 1 = 2^i (2m+1)+1$ so that $x^{2^i} + 1$ divides $x^p + x$ . In particular, there exists $n_0$ such that for all $n\ge n_0$ , $(x^{16} + 1)(x^{8} + 1)(x^4 + 1)(x^2 + 1)(x+1) \, \big\vert \, p_n (x)$ and hence $p_n (\omega) = p_n (\omega^2) = \cdots p_n (\omega^{31}) = 0$ . Accordingly, for $n\ge n_0$ , the value of $P(n)$ is exactly $1/32$ .

Let $q_k (x) = \sum_{d\vert k} x^d$ . To compute $n_0$ , for each $0\le i\le 4$ we must find the smallest $k$ such that $x^{2^i} + 1$ divides $q_k (x)$ . The above argument shows that some such $k$ exists for all $i$ , but the prime produced by Dirichlet's theorem is not necessarily the minimal such $k$ . From here, we factor $q_k$ for small values of $k$ and find the minimal $k$ for each $i$ : $x+1 \, \big\vert \, q_2 (x)$ $x^2 + 1 \big\vert \, q_3 (x)$ $x^4 + 1 \big\vert \, q_5 (x)$ $x^8 + 1 \big\vert \, q_{27} (x)$ $x^{16} + 1 \big\vert \, q_{17} (x)$ Taking the maximum of these indices, we conclude $n_0 = 27$ .