1
$\begingroup$

Given a prime $N$ and integer $g$, where $g$ is able to generate the multiplicative subgroup $(\mathbb{Z}/N^2\mathbb{Z})^*$, I am interested in any results simplifying or evaluating $f\in (\mathbb{Z}/N^2\mathbb{Z})[x]$ where

$$f(x) := \prod_{k=0}^{N-2} (x-g^k)$$

I know that this polynomial in $\mathbb{Z}/N\mathbb{Z}[x]$ is equivalent to $(x^N-1)$ because they are both monic polynomials of the same degree with the same roots.

Similarly in $\mathbb{Z}/N^2\mathbb{Z}[x]$, $$\prod_{k=0}^{N(N-1)-1} (x-g^k)=(x^{N(N-1)}-1)$$

I have tried generating a few small examples of this product but have not seen an obvious pattern emerge. This polynomial also seems different from cyclomatic polynomials because the roots are close to each other rather than separated by by a gcd relation.

Ideally, I want to evaluate $f(x)$, but I am also curious what research has been done on these partial products. My preliminary searches have failed to find a name for this polynomial much less any results, so any information would be informative.

Note: This equation and question are very similar to the second quantity asked about in https://math.stackexchange.com/questions/3398653/polynomial-whose-roots-are-some-of-the-nth-roots-of-unity. But not much by way of follow up has been given for possible ways to evaluate or simplify the polynomial

$\endgroup$
4
  • $\begingroup$ When you say "evaluating $f$", do you mean computing the coefficients of $f$, or computing $f(\alpha)$ for $\alpha$ in $\mathbb{Z}/N^2\mathbb{Z}$ (or some $\mathbb{Z}/N^2\mathbb{Z}$-algebra)? $\endgroup$
    – Ben Smith
    Commented Aug 7, 2020 at 12:03
  • $\begingroup$ The latter, computing $f(\alpha)$. $\endgroup$
    – Richard G.
    Commented Aug 7, 2020 at 22:21
  • $\begingroup$ Pollard has an algorithm which can be used to evaluate $f(x)$ in $O(\sqrt{N})$ operations in $\mathbb{Z}/N^2\mathbb{Z}$. Pollard's paper ("Theorems on factorization and primality testing") is not available freely online, but there's a convenient description of the algorithm in Section 2.1 of Bostan's "Computing the N-th Term of a q-Holonomic Sequence". $\endgroup$
    – Ben Smith
    Commented Aug 10, 2020 at 10:08
  • $\begingroup$ Thank you. That is a noticeable improvement over just calculating all the terms! $\endgroup$
    – Richard G.
    Commented Aug 11, 2020 at 23:16

0

You must log in to answer this question.