Newton polygons part 3

20 Jan, 2025

The past two posts (1, 2) have covered Newton polygons, as a tool for understanding and computing valuations of algebraic numbers, and as a tool for investigating factorization of polynomials with rational coefficients. This post is a short (non-)example of using Newton polygons, in dialogue with some existing math on the web.

A better algorithm for exponentiation

The starting point for this post is Kevin Ventullo's post 2-adic Logarithms and Fast Exponentiation. In that post Kevin proposes an efficient algorithm for computing $x^{y} \mod 2^{n}$ for $n$ -bit integers $x, y$ . Here "efficiency" measures the number of $n$ -bit integer multiplications necessary, since these will be the dominant term in a full runtime analysis.

Computing $x^{y} \mod 2^{n}$ directly requires $O (y)$ multiplications, but the technique of repeated squaring gets things down to $O (n) = O ({log}_{2} (y))$ many multiplications: compute $x, x^{2}, x^{4}, \dots$ and then multiply an appropriate subset of those based on the binary expansion of $y$ . Ventullo's algorithm does better: it achieves $O (\sqrt{n})$ many multiplications, with the major restriction being that it only computes the answer mod $2^{n}$ . In principle repeated squaring can be used to compute the full $x^{y}$ if working with arbitrary precision integers. Since the int type in many languages is effectively $ℤ / 2^{64} ℤ$ , working mod $2^{n}$ is not a massive restriction. Ventullo's algorithm in practice shows runtime improvements even for $n = 64$ , as is shown in his post.

2-adic numbers

In a search for algorithms for exponentiation, you might remember that logarithms exist. The key property of the logarithm function is that it converts multiplication into addition

log (a b) = log (a) + log (b) .

Since exponentiation is just repeated multiplication, this same principle extends to convert exponentiation into multiplication

log (a^{b}) = b log (a) .

Remembering that the exponential function $exp$ is the inverse to $log$ we've got a candidate algorithm: compute $x^{y}$ by computing

x^{y} = exp (y log (x)) .

We've broken up our exponentiation into one multiplication operation and two function applications. There's a couple of problems with this:

How do we compute $exp$ and $log$ on a computer?
What data type do we work with?

Since $exp$ and $log$ are defined by power series with rational coefficients, we can approximate them with polynomial computations by computing truncations of those power series. The coefficients of those truncated power series are rational numbers (reciprocals of integers in fact), and so we need a data type supporting those coefficients. The natural realm for working with $exp$ and $log$ is the real numbers, which are typically approximated on computers by floating-point arithmetic. This is a whole can of worms that we don't want to get into.

Ventullo's key insight is to interpret these functions in the $2$ -adic numbers rather than real numbers: the same power series converge in appropriate discs, and they share the same properties. Moreover $2$ -adics are a natural fit for computers, since $2$ -adic integers are approximated by $ℤ / 2^{n} ℤ$ which is the natural domain for integer arithmetic on a computer. Ventullo's algorithm is thus to compute $x^{y}$ using the $2$ -adic exponential and logarithm functions, which are just the usual power series interpreted $2$ -adically. Tracking the required precision and with a couple of optimizations around using pre-computed values to reduce the number of necessary term in the (truncated) power series, we get an algorithm that requires only $O (\sqrt{n})$ many multiplications to compute $x^{y} \mod 2^{n}$ .

Complexity of truncated exponential and logarithmic power series

Computing the truncated power series for the exponential function

E_{k} (x) = 1 + x + \frac{x^{2}}{2!} + \dots + \frac{x^{k}}{k!}

and logarithm function

L_{k} (1 + x) = x - \frac{x^{2}}{2} + \frac{x^{3}}{3} + \dots + \frac{(- 1)^{k + 1} x^{k}}{k}

is at the heart of this algorithm, and much of the tension in the algorithm is in the choice of $k$ .

Using a larger value of $k$ is good in that it gives an output which is more ( $2$ -adically) accurate, i.e. the correct value of $x^{y}$ modulo a higher power of $2$ . Of course the trade-off is that more computation is necessary in order to compute a larger truncation $k$ ; this computation is basically done directly. The power of needed to achieve a certain level of precision can be reduced by transforming the input to one which is more divisible by $2$ , at the cost of some more multiplications. The $O (\sqrt{n})$ from Ventullo's algorithm comes from striking the optimal balance between the work necessary to compute a certain truncation and the work done in reducing to a lower truncation.

Can we do better than direct computation in determining $E_{k} (x)$ ? First off we note that though it is not obvious, all of the terms will actually be computed with integer arithmetic mod $2^{n}$ rather than needing to involve rational numbers: the inputs to $E_{k} (x)$ will all be divisible by $2$ , and ${val}_{2} (x^{k} / k!) \geq 0$ so we can get by with computing powers of $x$ , bit shifts to handle the divisions by $2$ (while remaining integral), and multiplication by a known constant (the odd part of $\frac{1}{k!}$ has a multiplicative inverse mod $2^{n}$ ).

Computing a power series truncated to the $k$ -th term doesn't necessarily require $O (k)$ computations. The classic example is computing a truncation of

\frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \dots .

If we truncate at $2^{ℓ} - 1$ for some $ℓ$ , then there is a factorization:

1 + x + x^{2} + \dots + x^{2^{ℓ} - 1} = (1 + x) (1 + x^{2}) (1 + x^{4}) \dots (1 + x^{2^{ℓ - 1}}) .

With this factorization and $k = 2^{ℓ} - 1$ we can do the computation with just $O ({log}_{2} (k)) = O (ℓ)$ many multiplications, thanks to repeated squaring.

Can we do anything similar to speed up the computation of the truncations $E_{k} (x)$ and $L_{k} (x)$ that we care about for Ventullo's algorithm?

Newton polygons (not) to the rescue!

Last time we saw that $E_{k} (x)$ is irreducible using Newton polygons. But that was irreducibility over the rational numbers. In the course of our proof we actually showed that $E_{k} (x)$ is often reducible over the $2$ -adic numbers, accepting that we haven't proved that Newton polygons determine $p$ -adic factorization.

The $2$ -adic Newton polygon of $E_{k} (x)$ has one segment for each non-zero bit in the binary expansion of $k$ . If the $ℓ$ -th bit is non-zero, there is a segment of width $2^{ℓ}$ and slope $\frac{1 - 2^{ℓ}}{2^{ℓ}}$ ; this segment is necessarily irreducible by an Eisenstein-like argument.

To get the most possible factorization we should set $k = 2^{ℓ} - 1$ , so that there are segments of lengths $1, 2, 4, \dots, 2^{ℓ - 1}$ in the $2$ -adic Newton polygon of $E_{k} (x)$ . This seems like good news, but unlike the case of $\frac{1}{1 - x}$ above, factoring the truncation isn't enough. With some quick sage computations it looks like the factored pieces of $E_{k} (x)$ (which are now irreducible) are "full" in the sense that a degree $2^{ℓ}$ piece has most-to-all of its possible coefficients non-zero, so that $O (2^{ℓ}$ ) are necessary to compute it. Adding up over all the factored pieces this means that we're still doing at least $O (k)$ many multiplications, for example to compute all the powers of $x$ up to $x^{k / 2}$ .

So while we can in some sense completely understand the $2$ -adic factorization of $E_{k} (x)$ , it doesn't appear that this helps us improve the complexity of computing it. I think there is a lot more to be investigated here in understanding these factored pieces; a more combinatorial description rather than simply the existence we've established here with Newton polygons would help. It is still possible that there's some value from a computational perspective in understanding this factorization.

A similar story plays out for $L_{k} (1 + x)$ . Again one can completely determine the Newton polygon just based on $k$ . The $k$ with the most factoring are again one less than a power of $2$ . Here there's a single segment of width $1$ and infinite slope coming from the fact that $L_{k} (1 + x)$ is divisible by $x$ . The other segments come in pairs and have lengths $1, 2, 4, \dots, 2^{ℓ - 2}$ ; the segments of length $2^{a}$ have slopes $\pm \frac{1}{2^{a}}$ . And again, some quick experimentation with sage doesn't reveal any obvious simplicities in these factored polynomials; it appears they are "full" in the sense of having most-to-all of their coefficients be non-zero.

Wrap up

Newton polygons were exactly the tool we needed to start tackling this problem: in a search for more efficient ways of computing $E_{k} (x)$ and $L_{k} (1 + x)$ the first thing we want to do is factor them 2-adically, and the Newton polygons let us quickly figure out the exact shape of the factorizations.

In this case unfortunately it doesn't seem as though this factorization alone lends itself to simplifying the computation at all, but there is definitely more to explore!

I think that is all that I'll be writing about Newton polygons for the time being. More coming soon, likely a non-math interlude before I dive into writing a new math series of posts!