Why n(n+1)/2 is an integer

Why $n(n+1) / 2$ is an integer

Because either $n$ or $n + 1$ is even, hence $n(n+1)$ is always divisible by $2$.

So that settles it, then. Or does it? Let’s squint a bit and stretch what we mean by ‘integer’. Then a number theorist will inevitably find himself asking the following question: Let $K$ be a number field with ring of integers $\mathcal{O}_K$. Under what circumstances will the polynomial $f(x) = x(x+1) / 2$ preserve $\mathcal{O}_K$? The goal of this post will be to explore this question.

The only relevant prerequisite is a background in algebraic number theory, say at the level of the (fantastic) book A Classical Introduction to Modern Number Theory by Ireland–Rosen.

A curious quotient

Given $x \in \mathcal{O}_K$, the product $x(x+1)$ remains in $\mathcal{O}_K$, because $\mathcal{O}_K$ is a ring. The quotient $x(x+1) / 2$ is surely well-defined in $K$, but it is no longer clear whether it is in $\mathcal{O}_K$. Almost tautologically, this will be the case if and only if $x(x+1)$ is a multiple of $2$ in $\mathcal{O}_K$. Equivalently, what we’re saying is that $x(x+1)$ is equivalent to $0$ modulo $2$. This suggests we should take a look at $\mathcal{O}_K / (2)$. Which brings us to our first result:

Lemma 1. Let $K$ be a number field. Then $f(x) = x(x+1) / 2$ preserves algebraic integers if and only if $\mathcal{O}_K / (2)$ is isomorphic to a direct product $\mathbb{F}_2 \times \cdots \times \mathbb{F}_2$.

Proof: In order for $x(x+1) / 2$ to be an algebraic integer, $x(x + 1)$ must be equivalent to $0$ modulo $2$. Equivalently, the quotient ring $\mathcal{O}_K / (2)$ must satisfy the identity $x(x+1) = 0$ for every $x$. In other words, $\mathcal{O}_K / (2)$ must be a Boolean ring. Notice moreover that the ring must be finite, the order being equal to the norm $N_{K/\mathbb{Q}}(2)$.

I claim that the only finite Boolean rings are direct products $\mathbb{F}_2 \times \cdots \times \mathbb{F}_2$. In a Boolean ring, every element is idempotent. Idempotents correspond to splittings, in that if $e$ is an idempotent, then $R$ splits as $eR \oplus (1-e)R$. We can use this to inductively split up Boolean rings. But since our Boolean ring is finite, this process halts, at which point we reach the desired identification. ∎

Alright, so what ring is $\mathcal{O}_K / (2)$? For the purposes of future sections, we might as well ask this in a more general setting. Let $L / K$ be an extension of number fields, and let $\mathfrak{p}$ be a prime in $K$. What is the quotient $\mathcal{O}_L / \mathfrak{p}$?

The prime $\mathfrak{p}$, viewed as an ideal in $L$ splits as a product $\mathfrak{P}_1^{e_1} \cdots \mathfrak{P}_r^{e_r}$, where the $e_i$ are ramification indices. The Chinese remainder theorem lets us see that \[ \mathcal{O}_L / \mathfrak{p} \cong \prod_{i=1}^r \mathcal{O}_L / \mathfrak{P}_i^{e_i} \text{.} \] We may thus focus our attention to a single prime $\mathfrak{P}$ lying over $\mathfrak{p}$. Now, we know that $\mathfrak{O}_{L} / \mathfrak{P} \cong \mathbb{F}_{p^f}$ where $f$ is the inertia degree of $\mathfrak{P}$, so if $e = 1$, then we are done. But what if we have ramification?

Lemma 2. With the notation as above, we have \[\mathcal{O}_L / \mathfrak{P}^e \cong \mathbb{F}_{p^f}[\varepsilon] / (\varepsilon^e)\text{.}\]

Proof: If $\mathcal{O}_{\mathfrak{P}}$ is the ring of integers of the completion $L_{\mathfrak{P}}$, then \[ \mathcal{O}_{\mathfrak{P}} / \mathfrak{P}^e \cong \mathcal{O}_L / \mathfrak{P}^e \text{,} \] so we may as well work locally. Write $L'$ for the maximal unramified extension of $\mathbb{Q}_p$ inside $L$. Then $L = L'(\pi)$ for a prime $\pi$, and $\mathfrak{P} = (\pi)$. Denote by $\mathfrak{p}$ the unique prime in $L'$ below $\mathfrak{P}$. Since $L / L'$ is totally ramified, the minimal polynomial of $\pi$ is an Eisenstein polynomial $f(x) \in L'[x]$ of degree $e$.

Consider the evaluation map $\mathcal{O}_{L'}[x] \to \mathcal{O}_L$ sending $g$ to $g(\pi)$ and factor it into a map \[ \mathcal{O}_{L'}[x] / (f) \to \mathcal{O}_L / \mathfrak{P}^e \text{.} \] This map is surjective, and its kernel is $\mathfrak{p} \mathcal{O}_{L'}$, hence \[\begin{split} \mathcal{O}_{L} / \mathfrak{P}^e &\cong (\mathcal{O}_{L'} / \mathfrak{p})[x] / (f) \\ &\cong \mathbb{F}_{p^f}[x] / (f) \end{split}\] but now since $f$ was an Eisenstein polynomial, it is equivalent to $x^e$ mod $p$, hence we get the desired result. ∎

Corollary 3. Let $K$ be a number field. Then $f(x) = x(x+1)/2$ preserves algebraic integers in $K$ if and only if $(2)$ splits completely in $K$.

Proof: Combine Lemmas 1 and 2. ∎

Example 4. Consider a quadratic field $K = \mathbb{Q}(\sqrt{m})$ with $m$ squarefree. The prime $(2)$ splits completely if and only if $m \equiv 1$ mod $8$, in which case an integral basis of $\mathcal{O}_K$ is given by $\big\{1,(\sqrt{m}-1)/2\big\}$. Indeed it’s easily checked by hand that $f(x)$ preserves this basis.

An evident extension

Instead of looking at the product $x(x+1)$, let’s take a look at $x(x+1)(x+2)$. It’s easy to see that this product is divisible by $6$, and so $f(x) = x(x+1)(x+2) / 6$ is integer-valued. We can ask the same question as before, and by the same logic, we know that $f(x)$ preserves $\mathcal{O}_K$ if and only if $x(x+1)(x+2)$ is identically $0$ in the ring $\mathcal{O}_K / (6)$. Now, unlike before, it is no longer clear to me whether finite rings with this property can easily be classified — though I suspect that they can.

Luckily, we don’t need to find a general classification. By the Chinese remainder theorem, it suffices to look at the quotients $\mathcal{O}_K / \mathfrak{P}^e$ where $\mathfrak{P}$ is now a prime lying either over $2$ or over $3$, and where $e$ is the ramification index of $\mathfrak{P}$ over $p$. We have the following result:

Lemma 5. The polynomial $g_d(x) = x(x+1)(x+2)\cdots(x+d-1)$ is identically zero in the ring $\mathbb{F}_{p^f}[\varepsilon] / (\varepsilon^e)$ if and only if $f = 1$ and $e \leq d/p$.

Before formulating this lemma, I wrote up some rough Sage code to check if I could find any pattern. The script is quite slow, but we’ll improve it in a future iteration further down this post.

def is_zero(d, p, f, e):
    """Given a polynomial g_d(x) = x(x+1)...(x+d-1), test if g_d(x) vanishes everywhere on the ring Q = F_{p^f}[x] / (x^e)."""
    R = PolynomialRing(GF(p**f), 'x') #R = F_q[x]
    x = R.gen()
    Q = R.quotient(x**e) #The ring of interest
    g_d = 1 #Begin inductive construction of g_d(x)
    for i in range(d):
        g_d *= (x + i)
    for y in Q:
        if g_d(y) != 0:
            return False
    return True

def least_d(p, f, e):
    """Check if g_d(x) vanishes on Q = F_{p^f}[x] / (x^e) for d = 1,2,... until it does, and return that d. Cap at d = 50."""
    d = 1
    while d < 50:
        if is_zero(d, p, f, e):
            return d
        d += 1
    return -1

for p in [2, 3, 5]:
    l = [[least_d(p, f, e) for e in range(1, 10)] for f in range(1, 5)]
    print("p =", p)
    print(l)

As said, this code could surely be optimised drastically. For one, we could remember the output of $g_d(x)$ to easily compute $g_{d+1}(x)$. But more significantly, we are evaluating $g_d(x)$ at every $x$ in $\mathbb{F}_{p^f}[\varepsilon] / (\varepsilon^e)$, which as we’ll soon see is highly redundant. For now, though, this suffices. The results are simple enough:

p: 2
[[2, 4, 6, 8, 10, 12, 14, 16, 18], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1]]
p: 3
[[3, 6, 9, 12, 15, 18, 21, 24, 27], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1]]
p: 5
[[5, 10, 15, 20, 25, 30, 35, 40, 45],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1], 
 [-1, -1, -1, -1, -1, -1, -1, -1, -1]]

Let’s verify our findings. Denote by $Q_{e,f}$ or $Q$ the ring $\mathbb{F}_{p^f}[\varepsilon] / (\varepsilon^e)$ to avoid spelling it out.

Proof: We first claim that $g_d(x)$ never vanishes identically on $\mathbb{F}_{p^f}$ when $f > 1$. A fortiori, then, it doesn’t vanish on $Q_{e,f}$ either. To prove the claim, notice that if $x \in \mathbb{F}_{p^f} \setminus \mathbb{F}_p$, then $x + n$ isn’t in $\mathbb{F}_p$ either for any integer $n$. In particular, none of the $x + n$ are zero. Since $\mathbb{F}_{p^f}$ is a field, it has no zero divisors, so no such product can ever return zero.

Now consider the ring $Q = Q_{e,1} = \mathbb{F}_p[\varepsilon] / (\varepsilon^e)$. I claim that $g_{d}(x)$ vanishes identically precisely when $d \geq pe$. We first prove that this bound is sufficient, i.e. that $g_{pe}(x)$ vanishes identically on $Q$. Any element $x$ in $Q$ is of the form $\varepsilon x' + n$ for some $n \in \{0,\ldots,p-1\}$. Upon writing out the product $g_{pe}(x)$ for such an element, we see the term $\varepsilon x'$ appear at least $e$ times, hence the product must vanish. Notice that, when applied to $x = \varepsilon$, it in fact suffices to take $d = p(e-1) + 1$ — a fact we’ll use in a moment.

The bound $d \geq pe$ is moreover necessary. In fact, I claim that $g_{pe - 1}(\varepsilon + 1) \neq 0$. To prove this, define $\Delta g_d(x)$ as the difference $g_d(x + 1) - g_d(x)$. Then it’s easy to see that \[ \Delta g_d(x) = d g_{d-1}(x + 1) \text{.} \] Applied to $x = \varepsilon$, we use the vanishing of $g_d(\varepsilon)$ to find that \[ g_{pe - 1}(\varepsilon + 1) = -g_{pe - 2}(\varepsilon + 1) \text{.} \] Continue this process until we get to conclude that \[ g_{pe - 1}(\varepsilon + 1) = C g_{pe - p}(\varepsilon + 1) \] for some irrelevant but certainly nonzero constant $C$. Writing out the product, we find that \[ g_{pe - p}(\varepsilon + 1) = \prod_{n = 0}^{p - 1} (\varepsilon + n)^{e - 1} \text{.} \] Upon expanding this product, we find that almost all terms vanish, the only exception being the lowest-order term, which is $(p - 1)!\varepsilon$. As $p$ is a prime, $(p-1)!$ is nonzero modulo $p$. ∎

Theorem 6. The polynomial $f(x) = x(x+1)(x+2) / 6$ preserves $\mathcal{O}_K$ if and only if the primes $2$ and $3$ split completely in $K$.

Proof: $f(x)$ preserves $\mathcal{O}_K$ if and only if $x(x+1)(x+2)$ vanishes identically on $\mathcal{O}_K / (6)$. By the Chinese remainder theorem, this quotient splits as $\mathcal{O}_K / (2) \times \mathcal{O}_K / (3)$, which further splits into terms of the form $\mathcal{O}_K / (\mathfrak{P}^e)$. By Lemma 2 these terms are all of the form $\mathbb{F}_{p^f}[\varepsilon] / (\varepsilon^e)$ for $p = 2$ or $3$. By the result above, we always want $f = 1$ and $e \leq 3/p$, which just means $e = 1$ both when $p = 2$ or $p = 3$. ∎

Example 7. As in Example 4, consider a quadratic field $K = \mathbb{Q}(\sqrt{m})$, where $m$ is squarefree. The primes $2$ and $3$ split completely if and only if $m \equiv 1$ mod $24$, and it’s easy (but tedious) to check that $f(x)$ indeed preserves the ring of integers $\mathbb{Z}[(\sqrt{m} - 1)/2]$.

Example 8. Here’s a random cubic example. Let $K = \mathbb{Q}(\alpha)$ where $\alpha$ is a root of $x^3 + 35x - 60$. This is a degree-$3$ extension, not Galois, with discriminant $-5^2 \times 2687$ and class group $C_{27}$. The ring of integers $\mathcal{O}_K$ can be expressed as \[ \mathcal{O}_K \cong \mathbb{Z}[\alpha, \beta] \qquad \text{with} \qquad \beta = \frac{1}{2} \alpha^2 - \frac{1}{2} \alpha \text{.} \] The primes $(2)$ and $(3)$ split completely as \[ \begin{split} (2) &= (2,\alpha) \cdot (2, \beta + 1) \cdot (2, \alpha + \beta + 1) \\ (3) &= (3,\alpha) \cdot (3,\alpha + 1) \cdot (3,\alpha - 1) \end{split} \] The ring $\mathcal{O}_K$ is indeed closed under $f(x) = x(x+1)(x+2) / 6$; for instance, we can directly verify that \[ f(\alpha) = -5\alpha + \beta + 10 \] and \[ f(\beta) = -128\alpha + 31\beta + 190 \text{.} \] There are surely many other examples that we could cook up.

A further extension: where things go wrong

The next polynomial to consider is $f(x) = x(x+1)(x+2)(x+3) / 24$. Here, a phenomenon arises that we haven’t yet seen before: $24$ is no longer a product of distinct prime numbers, and so we find that \[ \mathcal{O}_K / (24) \cong \mathcal{O}_K / (2)^3 \times \mathcal{O}_K / (3) \text{.} \] The quotient ring $\mathcal{O}_K / (2)^3$ falls outside the realm of Lemma 2, and the ideas in the proof break down. What can we do?

At this point we might as well just go all out and consider the polynomial \[ f_d(x) = \frac{x(x+1)(x+2)\cdots(x+d-1)}{d!} = \frac{g_d(x)}{d!} \text{,} \] which obviously preserves integers for the same reason. To understand whether it preserves $\mathcal{O}_K$, we need to first understand the finite ring $\mathcal{O}_K / (p^N)$ for $N > 1$. Unfortunately for us, this turns out to be a hard question to answer directly: as it turns out, the local factors of a quotient such as $\mathcal{O}_K / (p^N)$ can be isomorphic to virtually every possible finite DVR of characteristic $p^N$, and there is no classification of such rings.

Let’s get the easy part out of the way. In the previous cases, we required all inertia to be trivial of the relevant prime numbers. I claim that this is still the case.

Lemma 9. In order for $f_d(x)$ to preserve the ring of integers $\mathcal{O}_K$, we at least want all primes lying over the prime numbers $p \leq d$ to have trivial inertia.

Proof: Observe that there is a surjective quotient map $\mathcal{O}_K / (p)^N \to \mathcal{O}_K / \mathfrak{P}$ for any prime $\mathfrak{P}$ lying over $(p)$. The target of this map is $\mathbb{F}_{p^f}$ where $f$ is the inertia degree of $\mathfrak{P}$. The quotient commutes with $g_d(x)$ and we had already seen that $g_d(x)$ never vanishes identically on $\mathbb{F}_{p^f}$ when $f > 1$. ∎

There is one case where we can decisively figure out what the quotient ring $\mathcal{O}_K / (p^N)$ is like, namely in the case when there’s no ramification either, i.e. when $(p)$ is totally split.

Lemma 10. If $p$ is totally split in $K$, then $\mathcal{O}_K / (p^N)$ will just be a product of copies of $\mathbb{Z}/p^N\mathbb{Z}$.

Proof: The proof uses a bit of algebraic geometry but it can probably be simplified quite a bit. Write $(p) = \mathfrak{P}_1 \cdots \mathfrak{P}_r$. By the Chinese remainder theorem it suffices to check that $\mathcal{O}_K / \mathfrak{P}^N \cong \mathbb{Z}/ p^N \mathbb{Z}$ where $\mathfrak{P}$ is one of the maximal ideals lying over $p$. We first claim that $\mathcal{O}_K / \mathfrak{P}^N$ has order $p^N$. Using the short exact sequence of abelian groups \[ 0 \to \mathfrak{P}^{n} / \mathfrak{P}^{n+1} \to \mathcal{O}_K / \mathfrak{P}^{n+1} \to \mathcal{O}_K / \mathfrak{P}^{n} \to 0 \] it suffices to know that $\mathfrak{P}^{n} / \mathfrak{P}^{n+1}$ has order $p$. Notice that this quotient carries the structure of an $\mathcal{O}_K / \mathfrak{P}$-vector space. Generally speaking, if $I$ is an ideal in $R$ generated by a regular sequence, then there’s an isomorphism $I^{n} / I^{n+1} \cong \operatorname{Sym}^n(I/I^2)$ which lets you deduce the dimension.^{Note 1} In our case, since $\operatorname{Spec} \mathcal{O}_K$ defines a smooth curve, $\mathfrak{P} / \mathfrak{P}^2$ must be $1$-dimensional, hence so is $\operatorname{Sym}^n(\mathfrak{P} / \mathfrak{P}^2)$ for every $n$.

It remains to show that $\mathcal{O}_K / \mathfrak{P}^N$ has characteristic $p^N$. This would finish up the proof as it would establish that the underlying abelian group is $\mathbb{Z}/p^N\mathbb{Z}$, which admits only one ring structure. But this becomes obvious upon passing to $\mathfrak{P}$-completion, as $p$ then acts as a uniformiser for $\mathfrak{P}$. ∎

If there is ramification involved, then it is no longer clear what the residues modulo prime powers will be like. Nonetheless, we might attain some insights by restricting to a specific class of rings. Looking at Lemmas 2 and 10, there’s one obvious family of rings that can surely arise as a quotient, namely the rings \[ Q_{e,N} = (\mathbb{Z}/p^N \mathbb{Z})[\varepsilon] / (\varepsilon^e) \text{.} \] It should be easy enough to figure out the vanishing behaviour of $g_d(x)$ on these rings. If $N = 1$, then we already know from Lemma 5 that $d$ needs to be at least $pe$ for $g_d(x)$ to vanish identically. But what about larger $N$?

I decided to take the Sage code written up earlier, and alter the base ring from $\mathbb{F}_{p^f}$ into $\mathbb{Z}/p^N \mathbb{Z}$, to see what would happen. But before doing so, let’s first optimise the code using the following two improvements, which I’ll state as lemmas.

Lemma 11. If $g_d(x)$ vanishes identically on $Q_{e,N}$, then $d$ needs to be at least $pe$.

Proof: The proof is analogous to that of Lemma 9: simply observe that there’s a projection $Q_{e,N} \to \mathbb{F}_p[\varepsilon] / (\varepsilon^e)$, and we know from Lemma 5 that $g_{d}(x)$ vanishes on the target only for $d \geq pe$. ∎

Lemma 12. If $g_d(\varepsilon + n) = 0$ for $n = 0,\ldots,d$, then $g_d(x)$ vanishes on all of $Q_{e,N}$.

Proof: I claim that $g_d(x),g_d(x+1),\ldots,g_d(x+d+1)$ are $\mathbb{Z}$-linearly dependent, hence if the first $d + 1$ polynomials vanish, then so does the $(d + 2)$-nd. By induction, then, all $g_d(x + n)$ for $n > d$ will vanish. To prove our claim, we induct on $d$. Recall the difference formula \[ \Delta g_d(x + n) = dg_d(x + n + 1) \] and apply the inductive hypothesis to find that $\Delta g_d(x),\ldots,\Delta g_d(x + d)$ are $\mathbb{Z}$-linearly dependent. Writing out the dependence, this proves the result.

We note that it’s unlikely that you can test $g_d(x)$ for significantly fewer $x$. For instance, if we take the ring $(\mathbb{Z}/4\mathbb{Z})[\varepsilon] / (\varepsilon^3)$, then one can check that $g_7(x + n) = 0$ for $n = 0,1,2,4,5,6,7$, yet \[ g_7(x + 3) = 2\varepsilon^2 \text{.} \] Numerical evidence does, however, suggest that it suffices to check $g_d(x + n)$ for $n = 0,\ldots,\lfloor d / 2\rfloor$. There may well be a hidden symmetry that we haven’t yet exploited.

There’s a potential additional improvement, which increases performance by a factor $p$. For any $Q_{e,N}$, the minimum $d$ for which $g_d(x)$ vanishes always appears to be a multiple of $p$, so in our numerical analysis, we might as well skip all other values of $d$. However, I’m unable to prove formally that this is the case, so we will not make use of it.

Here’s the code that we’ll make use of.

def is_zero(d, p, N, e):
    """Given a polynomial g_d(x) = x(x+1)...(x+d-1), test if g_d(x) vanishes everywhere on the ring Z_{p^N}[x] / (x^e)."""
    R = PolynomialRing(IntegerModRing(p**N), 'x')
    x = R.gen()
    Q = R.quotient(x**e) #The ring of interest
    a = Q.gen()
    g_d = 1
    for i in range(d):
        g_d *= (x + i) #Construct g_d
	check_range = min([p**N, d + 2])
    for n in range(check_range):
        y = a + n #We cannot write 'y = x + n' because Sage won't understand that we're evaluating f_d(y) in Q rather than in R
        if g_d(y) != 0:
            return False
    return True

def least_d(p, N, e):
    """Check if g_d(x) vanishes on Z_{p^N}[x] / (x^e) for d = 1,2,... until it does, and return that d. We've removed the cap as it's no longer needed."""
    d = p*e
    while True:
        if is_zero(d, p, N, e):
            return d
        d += 1 #You can probably change this to 'd += p'

for p in [2, 3, 5, 7]:
    print("p =", p)
    l = [[least_d(p, N, e) for e in range(1, 13)] for N in range(1, 9)]
    print(l)

The outcome is incredible:

p = 2
[[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24], 
 [4, 6, 8, 8, 12, 14, 16, 16, 20, 22, 24, 24], 
 [4, 8, 10, 12, 14, 16, 16, 16, 20, 24, 26, 28], 
 [6, 8, 12, 14, 16, 16, 18, 20, 22, 24, 28, 30], 
 [8, 10, 12, 16, 18, 20, 22, 24, 26, 28, 30, 32],
 [8, 12, 14, 16, 20, 22, 24, 24, 28, 30, 32, 32], 
 [8, 12, 14, 16, 20, 24, 26, 28, 30, 32, 32, 32], 
 [10, 14, 16, 18, 22, 24, 28, 30, 32, 32, 32, 32]]
p = 3
[[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36], 
 [6, 9, 9, 15, 18, 18, 24, 27, 27, 33, 36, 36], 
 [9, 12, 15, 18, 21, 24, 27, 27, 27, 36, 39, 42], 
 [9, 15, 18, 18, 24, 27, 27, 30, 33, 36, 42, 45], 
 [12, 18, 21, 24, 27, 27, 27, 33, 36, 39, 45, 48], 
 [15, 18, 24, 27, 27, 30, 33, 36, 39, 42, 45, 51], 
 [18, 21, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54], 
 [18, 21, 27, 33, 36, 36, 42, 45, 45, 51, 54, 54]]
p = 5
[[5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60], 
 [10, 15, 20, 25, 25, 35, 40, 45, 50, 50, 60, 65], 
 [15, 20, 25, 25, 30, 40, 45, 50, 50, 55, 65, 70], 
 [20, 25, 25, 30, 35, 45, 50, 50, 55, 60, 70, 75], 
 [25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80], 
 [25, 35, 40, 45, 50, 50, 60, 65, 70, 75, 75, 85], 
 [30, 40, 45, 50, 50, 55, 65, 70, 75, 75, 80, 90], 
 [35, 45, 50, 50, 55, 60, 70, 75, 75, 80, 85, 95]]
p = 7
[[7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84], 
 [14, 21, 28, 35, 42, 49, 49, 63, 70, 77, 84, 91], 
 [21, 28, 35, 42, 49, 49, 56, 70, 77, 84, 91, 98], 
 [28, 35, 42, 49, 49, 56, 63, 77, 84, 91, 98, 98], 
 [35, 42, 49, 49, 49, 63, 70, 84, 91, 98, 98, 98], 
 [42, 49, 49, 56, 63, 70, 77, 91, 98, 98, 105, 112],
 [49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126], 
 [49, 63, 70, 77, 84, 91, 98, 98, 112, 119, 126, 133]]

We see what appears to be a linear increase in $e$ and $N$. The increase isn’t perfect, however; there seem to be all sorts of little irregularities, which aren’t easily explained. What’s more is that the dependence on $e$ and $N$ is in fact not linear. This cannot be seen in the range outputted above, but it becomes obvious if we increase the range. The slopes in $e$ and $N$ slowly increase. How slow exactly? Logarithmic, perhaps? I was unable to tell.

Looking only at the first vertical line (i.e. $e = 1$), we see an obvious pattern: as we increase $N$, the minimal $d$ increases in steps of $p$, but at the $p^k$-th such increase, there’s a $k$-fold repetition of $d = p^k$. This pattern indeed continues without irregularity:

Lemma 13. The minimal $d$ for which $g_d(x)$ vanishes on $\mathbb{Z}/p^N\mathbb{Z}$ equals the minimal $d$ for which $p^N$ divides $d!$.

Proof: Notice that $g_d(1) = d!$ so we need $p^N$ to divide $d!$ in order for $g_d(1)$ to evaluate to $0$. The first such $d$ at which this happens will be divisible by $p$, since otherwise, the $p$-adic valuation of $(d-1)!$ and $d!$ would be the same, contradicting minimality.^{Note 2} In fact, this specific $g_d(x)$ will be uniformly zero on $\mathbb{Z} / p^N\mathbb{Z}$. To see this, expand the product $g_d(n)$ for $n > 1$ and consider its residue modulo $p$. ∎

Corollary 14. Let $K$ be a number field. Write $d! = p_1^{N_1} \cdots p_r^{N_r}$. In the hypothetical scenario that the local summands of the $\mathcal{O}_K / p_i^{N_i}$ are all isomorphic to some $Q_{e,N_i}$, then $f_d(x)$ will be well-defined on $\mathcal{O}_K$ if and only if all $p \leq d$ are totally split.

Proof: Obviously, the $p_i^{N_i}$ divide $d!$, so by Lemma 13, we know that $g_d(x)$ vanishes on $Q_{N,1} = \mathbb{Z}/p^N \mathbb{Z}$. However, I claim that it will not vanish on at least some $Q_{N,2}$. This can be seen by noting that $g_d(\varepsilon) = (d-1)! \varepsilon$, which is nonzero on some factor $Q_{N,2}$ for a $p$ dividing $d$. ∎

It’s tempting to say that this result holds regardless of the precise algebraic nature of the relevant quotient rings. As such we wind up with the following conjecture:

Conjecture 15. The polynomial $f_d(x)$ preserves $\mathcal{O}_K$ if and only if all primes less than or equal to $d$ split completely in $K$.

Notice that if this conjecture is true then the minimal $d$ for which $f_d(x)$ preserves $\mathcal{O}_K$ will always be a prime number.

I have attempted to find counterexamples to Conjecture 15 using brute-force computations in Sage, but I have been unable to find any. Nonetheless, I would hesitate to say for sure that the conjecture is true. One evidence in the opposite direction is that if, instead of $f_d(x)$, we consider an integer multiple of $f_d(x)$, then one can find counterexamples to the conjecture.

Example 16. If we take the field $K = \mathbb{Q}(\alpha)$ with $\alpha^3 + 567\alpha + 168 = 0$ then the polynomial $f_5(x)$ doesn’t preserve $\mathcal{O}_K$, but $3 f_5(x)$ does. In fact, in this field, the prime $(3)$ is totally ramified, splitting as a cube $(3,\alpha)^3$.

Example 17. Consider the polynomial $g_d(x) / \prod_{p \leq d} p$. Then the arguments of Theorem 6 extend readily to imply that $f_d(x)$ preserves $\mathcal{O}_K$ if and only if every prime $\mathfrak{P}$ lying over a prime number $p \leq d$ has trivial inertia and has ramification index $e \leq d/p$.

Aside on integer-valued polynomials

We started out this post with the question whether $x(x+1) / 2$ preserves rings of integers in a given number field. After answering this question, we observed that the product can be extended, so that we can ask the same question for the integer-valued polynomial \[ f_d(x) = \frac{x(x+1)\cdots(x+d-1)}{d!} \text{.} \] At that point, it is obvious that we can ask this question for any rational polynomial that preserves $\mathbb{Z}$. This, in turn, raises the question whether we can classify such polynomials.

Lemma 18. Let $f(x)$ be a rational polynomial which preserves integers. Then $f(x)$ is an integer linear combination of the $f_d(x)$ defined above.

Proof: The proof method resembles that of Lemma 12. We induct on the degree $n$ of the polynomial $f(x)$. If $f(x)$ is a polynomial of degree $n$, then define $\Delta f(x) = f(x+1) - f(x)$. Notice that this is a polynomial of degree $n - 1$. Notice moreover that $\Delta$ is almost injective, in that if $\Delta f(x) = \Delta g(x)$, then $f(x)$ and $g(x)$ differ by a constant.

If $f(x)$ preserves integers, then so does $\Delta f(x)$. Moreover, note that \[ \begin{split} \Delta f_d(x) &= f_{d-1}(x+1) \\ &= f_{d-1}(x) + f_{d-2}(x) + \cdots + f_1(x) + 1 \end{split} \] The induction hypothesis shows that this map yields a surjection onto the space of integer-preserving polynomials of degree $n - 1$, so we are done. ∎

Another obvious question to ask is whether rings of integers admit any exotic rational integer-valued polynomials. That is, given a number field $K$, are there any polynomials $f(x) \in K[x]$ preserving $\mathcal{O}_K$ that do not come from any of the $f_d(x)$ defined above?

Example 19. Consider the field $K = \mathbb{Q}(i)$. The prime $2$ is ramified, splitting as $(2) = (1 + i)^2$. From Corollary 3 we know that $x(x+1) / 2$ doesn’t preserve $\mathcal{O}_K$, but from $x(x+1) / (1 + i)$ does.

In fact, this example readily extends to any number field $K$ for which $\mathcal{O}_K$ is a PID. However, all polynomials obtained in this way are still morally close to the $f_d(x)$: they are a still an ‘integer’ multiple of the $f_d(x)$ — it’s just that the integers are in $\mathcal{O}_K$ instead of $\mathbb{Z}$. This is to be expected:

Lemma 20. Let $K$ be a number field, and let $f(x) \in K[x]$ preserve $\mathcal{O}_K$. Then $f(x)$ is an $\mathcal{O}_K$-linear combination of the $f_d(x)$.

Proof: We claim that, upon multiplying $f(x)$ by a suitable scalar in $\mathcal{O}_K$, it will land in $\mathbb{Q}[x]$, after which the result follows by Lemma 18. First multiply by a scalar to clear the denominators of the coefficient of $f(x)$. Next, I claim that for every coefficient $c \in \mathcal{O}_K$ of $f(x)$, one can find a scalar $c' \in \mathcal{O}_K$ such that $c \cdot c' \in \mathbb{Z}$. If $K$ is a Galois field, one can take $c'$ to be the product of the Galois conjugates of $c$. In other cases, $c$ can be written as the root of some monic polynomial $x^n + a_{n-1} x^{n-1} + \cdots + a_0$. Rewrite this into \[ c \cdot (c^{n-1} + a_{n-1}c^{n-2} + a_{n-2} c^{n-3} + \cdots + a_1 c) = -a_0 \text{,} \] so that we can put \[ c' = a_{n-1} + a_{n-2} c^{n-2} + + \cdots + a_1 c \text{.} \] This proves the desired result. ∎

Remark on the literature

While writing up this post, I came to find out that much of this has been studied on some form or other. In fact, there’s an entire book on this particular subject, aptly titled Integer-Valued Polynomials, by Cahen–Chabert.

Although I haven’t read the book, it contains a historical introduction which is available online. The results therein overlap substantially with what I’ve written in this post. Notably, Lemma 18 dates all the way back to a 1915 paper of George Pólya, titled Über ganzwertige ganze Funktionen.

The table of contents of the book suggests many other interesting avenues to study: the ring structure on the set of integer-valued polynomials; integer-valued rational functions; and multivariate integer-valued polynomials. So if the reader wants to learn more, he now knows where to look.

Footnotes

In such generality, this is a hard theorem, but I would expect that there’s an easy proof when restricting attention to curves, which is all we need.
Presumably, a comparable argument can be made to show that the minimal $d$ for which $g_d(x)$ vanishes on $Q_{e,N}$ is divisible by $p$. This would allow for a roughly $p$-fold speedup in the algorithm I described.