Special binary string

Question

Imagine a binary string of increasing length, up to infinity.

What makes it so special? Well, just a simple "rule":

for any given length (odd or even), if one folds the string in half, there is at least one couple of ones that overlaps.

The question is now about the distribution of ones (zeros), as a function of string length. What are its properties? Are there any?

A trivial example that follow the rule is the string $111010101010....$.

Answer 1

We can view the string as a subset $A\subseteq \mathbb N_0$ (positions of $1$s). The bit string has the folding property if and only if each $n\in \mathbb N_\color{red}0$ can be written as the sum of two $\color{red}{\text{(not necessarily distinct)}}$ elements of $A$.

The lexically first string is almost the one you gave: $1\overline{10} $. If one redundantly replaces the first $0$ with a $1$ and then tries to stay lexically low again, one obtains $11\overline{100}$ and so on.

EDIT: I changed two places to accomodate a different interpretation of "overlap" in case of odd substrings. Without these red changes, the lexically first string is $111\overline{010}$.

Answer 2

For any string that satisfies the rule, you can change any $0$'s to $1$'s and get a new one that satisfies the rule. So I think you should look for the lowest density string. One way is the greedy algorithm. I assume you don't count the bit on the fold, if there is one, but you are satisfied with one position of overlap. Using Hagen von Eitzen's characterization of the set, The positions of the $1$'s by this rule are $1,2,3,5,8,11,14,\ldots,3k+2$ We can see the $1,2,3,5,8,11,14$ by inspection. If the pattern continues up to $3k+2$, we can make $3k+3, 3k+4, 3k+5$ but cannot make $3k+6$ because the only number that is $1 \pmod 3$ is $1$. So we have to add $3k+5=3(k+1)+2$ to the list and the induction continues. I didn't find the sequence in OEIS.

Added: with the clarification that a $1$ on the fold counts, the greedy series becomes $1,2,4,6,8,\ldots 2k$ and the proof is the same as the previous one. This is a higher density that the previous one, so the greedy algorithm will not give the minimum. We can make the limiting density arbitrarily low by starting with $n\ 1$'s, then putting $n-1\ 0$'s and a $1$ repeatedly.