13
$\begingroup$

Let $p$ and $q$ be distinct primes. By the ring of $pq$-adic integers I mean the ring $\mathbb{Z}_{pq} := \varprojlim \mathbb{Z}/(pq)^n\mathbb{Z}$ which is obviously isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_q$ by the Chinese remainder theorem; but the point of writing it as $\mathbb{Z}_{pq}$ is that we can consider the base $pq$ expansion of a $pq$-adic.

Apart from $0$ and $1$, the isomorphism in question shows that $\mathbb{Z}_{pq}$ has two other (=non-trivial) idempotents, $e$ and $1-e$ where $e$ is defined by the sequence of $e_n \in \mathbb{Z}/(pq)^n\mathbb{Z}$ such that $e_n \equiv 1\pmod{p^n}$ and $e_n \equiv 0\pmod{q^n}$. The approximations $e_n$ of $e$ are sometimes known, at least when $pq=10$, as "automorphic numbers" (a fairly silly terminology IMHO).

(Side note: a simple way to compute $e$ with arbitrary $pq$-adic precision is to start with $e_1$ and iterate the function $x \mapsto 3x^2 - 2x^3$, because the latter has $0$ and $1$ as superattractive fixed points so will converge very rapidly in $\mathbb{Z}_p$ and $\mathbb{Z}_q$; as an experiment with GMP, I was able to compute several million digits of the $10$-adic idempotent $\ldots 893380022607743740081787109376$ in a few minutes. Apparently this is just as fast as computing the inverse of $p^n$ mod $q^n$ and multiplying by $p^n$ mod $(pq)^n$.)

My question is: has the distribution of digits of these idempotents been studied? — and specifically, is it known whether they contain all finite sequences of $pq$-adic digits, or, even better, whether they are normal? (Experimentally, over a few million digits for $pq=10$, this seems to be the case.)

(One reason I ask is because this is related to a problem by Ulam on cellular automata, namely, whether there exists a cellular automaton which generates all finite patterns from a finite seed: a remarkably simple answer to this problem given by Jarkko Kari is to consider the automaton which computes multiplication by $q$ on the $pq$-adics (this is indeed given by a cellular automaton), whose $N$-th generation is $q^N$ written in base $pq$: see here for more about this. Now the sequence $q^{n!}$ (or even $q^{(p-1)p^n}$) converges to $e$ in the $pq$-adic sense. So if $e$ does indeed contain all finite sequences, this means that the automaton in question not only produces all finite sequences, but also produces them at arbitrarily divisble generation numbers.)

$\endgroup$
  • $\begingroup$ Out of curiosity, since you have the code to do this: does the distribution appear to be uniform for some of the other all small cases, when, say, pq = 6, or 14, or 15? $\endgroup$ – Michael Lugo Jan 31 '14 at 16:20
  • 1
    $\begingroup$ @MichaelLugo: I computed the first 5 million digits of the idempotent for bases 10, 6, 14 and 15, and ran a χ² distribution test on the subsequences of length 1 through 6 of all of them, and all remained within the 99% bound (which is reasonable considering there were 4×6=24 different tests). So yes, it appears to be quite uniform, at least from this (somewhat naïve) test. $\endgroup$ – Gro-Tsen Feb 3 '14 at 14:32

Your Answer

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

Browse other questions tagged or ask your own question.