2
$\begingroup$

If the base-ten numerals of the nonnegative integers (or the prime numbers) are concatenated in their natural order, the resulting sequence of digits is known to be normal in base ten.

Question 1: Can concatenating the same set of numerals in some other order produce a non-normal digit sequence?

I haven't come up with any reordering of the numerals that gives a clearly non-normal digit sequence, but neither do I see how to prove that there are none.

More generally, for an arbitrary $S\subseteq\mathbb{N}\ $ and arbitrary integer base $b\ge 2$:

Question 2: Is it the case that either all permutations of $S$ produce concatenated digits that are normal in base $b$, else no permutation does so?

(A similar question replaces "normal in base $b$" with "absolutely normal".)

NB: The permutations above are with respect to the sequence of numerals to be concatenated, as distinct from directly rearranging the resulting digit sequence. Directly rearranging the digits, which are not all distinct, would not properly be called permutation; furthermore, normality -- absolute or otherwise -- is not preserved by freely rearranging all the digits, because any positive irrational could then be transformed into any positive real. E.g., if $d_1d_2d_3...$ are the fractional bits of any irrational and $d_1'd_2'd_3'...$ are the fractional bits of any real, then there is, trivially, a permutation of $\mathbb{N}_+$, say $(n_i)_{i\ge 1}$, such that $d_{n_1}d_{n_2}d_{n_3}...=d_1'd_2'd_3'...$.

$\endgroup$
  • $\begingroup$ I edited to remove a question about the meaning of "absolute normality is invariant under permutation of digits". I take it that this merely refers to "relabeling" the digits $(0,1,...,b-1)$ according to some permutation $(\pi_0,\pi_1,...,\pi_{b-1})$ of the same symbols; i.e., replace every appearance of digit $d$ with the corresponding element $\pi_d$ of the permutation. $\endgroup$ – r.e.s. May 10 '17 at 20:20
  • 2
    $\begingroup$ Let $A = \{1,11,111,1111,11111,\ldots\}$ be the repunits, and let $B$ be the rest of the integers (arranged in increasing order). Then the digit $0.12113111411115111116\ldots$ formed by alternating terms from $A$ and $B$ will certainly not be normal --- in fact, the digit $1$ occurs with density one and all other digits with density zero. $\endgroup$ – Gordon May 10 '17 at 20:51
  • $\begingroup$ @Gordon - Thanks, I don't know why I didn't think of that! $\endgroup$ – r.e.s. May 10 '17 at 21:10
3
$\begingroup$

The answer to the first question is yes. Normality is a statement about the limit density of every substring. So, consider the sequence $1, 11, 111, 1111, \dots$ interleaved with every other number to produce $1, 2, 11, 3, 111, 4, 1111, 5, 11111, \dots$.

I couldn't think of any obvious reason this should be true for primes. But I discovered there are infinitely many primes not containing the digit $1$. This lets us create an ordering where, after concatenating, the digit $1$ has limit density $0$.

As for conditions that preserve normality, consider the situation where we start with an algorithmically random sequence like the digits of Chaitin's constant which is absolutely normal. In that case every computable permutation will also be absolutely normal.

$\endgroup$
  • $\begingroup$ (+1) Thanks, I should have seen that! Now I'm curious about what restrictions on the permutations might force a negative answer. $\endgroup$ – r.e.s. May 10 '17 at 21:13

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.