Algebraic Digit Extraction ideas

This is a solution to a special case of a problem discussed at the 2025 research workshop for version $p$ and the most significant digit.

Solution

The polynomial $f(x) = x - p^{n-1}\binom{x}{p^{n-1}}$ solves the problem for $e = n-1$. By Lucas's Theorem, $\binom{x}{p^{n-1}}\pmod{p}$ is the coefficient of $p^{n-1}$ in the base-$p$ representation of $x$. Hence, $f(x)$ is the remainder of $x\pmod{p^{n-1}}$.

There are a two important points to note when computing $\binom{x}{p^{n-1}}$:

• If we multiplied out the entire numerator of $\binom{x}{p^{n-1}}$ before any divisions, we would lose all information about $x$. Instead, we break the numerator into $p^{n-2}$ blocks of $p$ values, multiply each block together, divide each block by $p$, and induct down.

• The circuit does not permit division by nonzero numbers, which is necessary to compute $\binom{x}{p^{n-1}}$. Instead, we observe that $\prod_{k=1}^{p^{n-1}} kp^{-\nu_p(k)}\equiv -1\pmod{p}$, so we can replate the entire denominator by $-p^{\nu_p (p^{n-1}!)}$.

The bottleneck of computing $f(x)$ is computing $\binom{x}{p^{n-1}}$, which takes multiplictive depth $O(n\log p)$.

To extend this strategy to all $e$, we can instead use $f_e(x) = x - p^k\binom{x}{p^k}$, which eliminates the $p^k$ term in the base-$p$ representation of $x$. If we chain these in order from $k=e$ to $k=n-1$, we can solve the general problem with multiplicative depth $O(n(n-e)\log p)$.