2
$\begingroup$

I'm interested in quickly computing an embedding of the profinite integers $\widehat{\mathbb{Z}}$ into the unit interval $\left[0,1\right]$.

$\widehat{\mathbb{Z}}$ can be represented as compatible sequences $(a_1,a_2,a_3,\dots)$ where by compatible we mean $m|n \Rightarrow a_m \equiv a_n \mod m$. This is exactly the relation that holds when the sequences come from integers, i.e. $a_m=m$, and encodes facts like if $n$ is even, then $n \equiv 0,2 \mod 4$. In this way we have an embedding $\mathbb{Z} \subset \widehat{\mathbb{Z}}$ where $n \mapsto (n \mod 1, n \mod 2, n \mod 3,\dots)$.

One can imagine a tree with branching degree increasing by one each layer down. Each sequence corresponds to a path starting at the root of the tree. To place the leaves of the tree in the interval $[0,1]$ in a natural way, subdivide the interval into two pieces, those segments into three pieces, and so on all the way down. The map is then

$$n \mapsto \sum_{m=1}^{\infty} \frac{(n\mod m)}{m!}$$

This is simply using the fractional values in the mixed radix factorial number system, i.e. the sequence $(a_1, a_2, a_3,\dots)$ corresponds to $0.a_1 a_2 a_3 \dots$.

As the sequence $n \mod m$ is constant and equal to $n$ when $m>n$, we can compute the "remainder" $R_n$ quickly:

$$R_n = \sum_{m=n+1}^{\infty} \frac{n}{m!} = e\cdot n-\frac{e \Gamma(1+n,1)}{\Gamma(n)} = e\cdot n - \frac{\lfloor e\cdot n!\rfloor}{(n-1)!}$$

Let $\displaystyle S_n = \sum_{m=1}^n \frac{(n\mod m)}{m!}$ be the $n$-th partial sum of the series, a rational number.

Simply computing $n \% m$ for each $m$ and summing is $\mathcal{O}(n)$, so exponential in the number of digits. Is there a faster way to compute this?

$\endgroup$
3
  • 1
    $\begingroup$ Two trivial observations: it might be profitable to rewrite $S_n = \sum_{m=1}^n (\frac{n}{m} \mod 1) \cdot \frac{1}{(m-1)!}$, and plotting $S_n$ shows enough approximate periodicity to suggest that Fourier techniques might be of use. $\endgroup$ – Steve Huntsman Dec 23 '20 at 14:44
  • $\begingroup$ The two initial directions I had in mind were 1) factor $n$ and compute the residues modulo prime powers, $n \mod p^{r_i}$, use the divisibility criteria to reduce the number of summands, and the Chinese Remainder Theorem. 2) rewrite $n \mod m = n - m \lfloor \frac{n}{m} \rfloor$, and rewrite the floor using a Fourier series to get $n-m\left(\frac{n}{m}-1/2+\frac{1}{\pi}\sum_{k=1}^{\infty}\frac{\sin(2\pi kn/m)}{k}\right) = \frac{m}{2}-\frac{m}{\pi}\sum_{k=1}^{\infty}\frac{\sin(2\pi kn/m)}{k}$. Rearranging to get an exponential sum would be the next guess, but not confident w/o abs. conv. $\endgroup$ – J. G. Walters Dec 24 '20 at 2:49
  • $\begingroup$ It smells to me like Poisson summation might afford a foothold on your Fourier series $\endgroup$ – Steve Huntsman Dec 24 '20 at 3:03
1
$\begingroup$

Given that your denominators get up to $(n-1)$, which has $\approx n\log{n}$ digits, I don't see how you can possibly do better than $O(n)$.

That being said, let's look at your original map: \begin{equation} n \rightarrow f_n \equiv \sum_{m=1}^\infty \frac{(n \pmod{m})}{m!} \end{equation} Turn it into a generating function. \begin{equation} F(x) \equiv \sum_{n=1}^{\infty} f_n x^n \,. \end{equation} We then have the following recursion: \begin{equation} F(x) = \frac{(e-1)x}{1-x} + xF(x) - \sum_n \sum_{d|n} \frac{x^n}{(d-1)!} \\ = \frac{(e-1)x}{1-x} + xF(x) - \sum_d \sum_{k=1}^\infty \frac{x^{kd}}{(d-1)!} \\ = \frac{(e-1)x}{1-x} + xF(x) - \sum_d \frac{x^d}{(d-1)! (1-x^d)} \,. \end{equation} The first line comes from $(n+1 \pmod{m}) = (n \pmod{m}) + 1 - mI_{m|n}$, which gives a recursion on the $f_n$. I can't simplify the last line further, but maybe you can do something with that?

$\endgroup$
1
  • $\begingroup$ Thanks, that's helpful. This question got some more traction on SE (math.stackexchange.com/questions/3960138/…). As you say, it does seem to be the case that the output is large, though it's not obvious how to prove that the numerator doesn't cancel the denominator. As $1/m!$ is small, you really only need around 21 terms for an accurate 64-bit approximation, which is fine for what I was doing. $\endgroup$ – J. G. Walters Jan 26 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.