3
$\begingroup$

Let $\mathbb{N}$ denote the set of non-negative integers. We say that a sequence $f:\mathbb{N}\to \{0,1\}$ is normal if every finite $\{0,1\}$-sequence appears in $f$.

Let the swapping operation $\sigma:\mathbb{N}\to \mathbb{N}$ be defined by swapping each even integer with its successor - that is, $\sigma(2n) = 2n+1$ and $\sigma(2n+1) = 2n$ for all $n\in \mathbb{N}$.

Question. Is there a normal binary sequence $f:\mathbb{N} \to \{0,1\}$ such that $f \circ \sigma$ is not normal?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ To clarify: in the definition of normality, do you want every finite sequence to appear in $f$ as a subsequence or a consecutive subsequence? $\endgroup$
    – Sam Hopkins
    Commented Jan 29, 2022 at 21:43
  • 2
    $\begingroup$ @SamHopkins, as a non-consecutive subsequence, normalcy would be equivalent to not being eventually constant, which isn't a very interesting property. $\endgroup$
    – Peter Taylor
    Commented Jan 29, 2022 at 22:48
  • $\begingroup$ @PeterTaylor: of course, silly me. $\endgroup$
    – Sam Hopkins
    Commented Jan 29, 2022 at 22:53
  • 4
    $\begingroup$ Apparently, such sequences are called disjunctive. The usual definition of normal sequences asks for an even distribution of all the subsequences of given length. $\endgroup$
    – Pierre PC
    Commented Jan 30, 2022 at 0:20

1 Answer 1

Reset to default
9
$\begingroup$

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

(Thanks to Alessandro Della Corte for corrections in the comments below!)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string of even length. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string $S$ of even length appears consecutively in $f$ starting from even position, it's also the case that $S \circ \sigma$ appears consecutively in $f$ starting from an even position. So every string $S$ of even length appears consecutively in $f \circ \sigma$ (starting from even position). As every string is a consecutive substring of a string of even length, it follows that every string appears consecutively in $f \circ \sigma$.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Looks like you're assuming that $S$ has an even length... in the other case instead of $S0S$ you should use $SS$. $\endgroup$
    – Alessandro Della Corte
    Commented Jan 29, 2022 at 23:03
  • 1
    $\begingroup$ @AlessandroDellaCorte Ah, nice catch, thanks. Alternatively, note that every string $S$ appears consecutively in $f$ if and only if every string $S$ of even length appears consecutively in $f$ to reduce to this case. In fact, I think the next part of the argument also assumes that $S$ has even length, and would require some ad hoc modification for the odd-length case. $\endgroup$
    – Tim Campion
    Commented Jan 29, 2022 at 23:05
  • $\begingroup$ But I still can't follow the argument. It seems to me that to get $S=s_1s_2\dots s_{2k}$ in $f\circ\sigma$ you need something like $s_2s_1s_4s_3\dots s_{2k}s_{2k-1}$ in $f$. $\endgroup$
    – Alessandro Della Corte
    Commented Jan 29, 2022 at 23:11
  • $\begingroup$ Right, that's the string I'm abusively calling $S \circ \sigma$. $\endgroup$
    – Tim Campion
    Commented Jan 29, 2022 at 23:11
  • 1
    $\begingroup$ Right, that's taken care of in the last sentence -- simply pad your odd-length string and now it's even length, reducing to the previous case :) $\endgroup$
    – Tim Campion
    Commented Jan 29, 2022 at 23:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .