Dyck Numbers, IV. Nested patterns in OEIS A036991

NEW

Problem: Reconstructed statement: let $D_n$ be the $n$-th level of OEIS A036991, i.e. the integers whose $n$-bit binary expansion has every suffix with at least as many $1$'s as $0$'s. Let $M_k=2^k-1$. For even $n$, the $n$-core is the initial segment

$$\mu_n=D_n\cap (M_{n-1},\,M_{n-1}+2^{n-3}],$$

whose senior term is

$$A_n=M_{n-1}+2^{n-3}.$$

Writing $\mu_n^{(4)}$ for the top fourth subsegment of $\mu_n$, i.e.

$$\mu_n^{(4)}=D_n\cap(A_n-2^{n-5},A_n],$$

Conjecture 18 says that for even $n\ge 12$,

$$\mu_n^{(4)} = \mu_{n-4}(A_n-3\cdot 2^{n-7}) \oplus \bigl(\mu_{n-2}^{(4)}(A_n)\bigr)^3 .$$

Here $X(B)$ means the copy of the pattern $X$ shifted so that its senior term is $B$, and $Y(B)^3$ means the three adjacent copies of $Y$ with senior terms $B-2\ell,B-\ell,B$, where $\ell$ is the interval length of $Y$. The notation in the prompt $\mu_{n/4}$ and $\mu_{(n-2)/4}$ is interpreted from the paper’s examples as $\mu_n^{(4)}$ and $\mu_{n-2}^{(4)}$, not as arithmetic division of the index.

Result: The conjecture is true.

Let a binary word be admissible if every suffix has nonnegative balance $\#1-\#0$. Then:

• $\mu_n$ consists exactly of admissible $n$-bit words beginning with $100$;
• $\mu_n^{(4)}$ consists exactly of admissible $n$-bit words beginning with $10011$.

Put $P=10011$. An element of $\mu_n^{(4)}$ has form

$$Pqr,\qquad q\in\{00,01,10,11\},\quad |r|=n-7.$$

Case $q=00$. Then

$$P00r=1001100r=1001(100r).$$

The word $1001100r$ is admissible iff $100r$ is admissible: one direction is immediate because $100r$ is a suffix; conversely, prefixing an even-length admissible word $x=100r$ by $1001$ preserves admissibility since $\operatorname{bal}(x)\ge2$. Thus the $q=00$ block is exactly a copy of $\mu_{n-4}$, with senior word $1001100\,1^{n-7}$, i.e. senior term $A_n-3\cdot2^{n-7}$.

Cases $q=01,10,11$. For $x=Pr$, the word $Pqr$ is admissible iff $Pr$ is admissible. Indeed, suffixes inside $r$ are unchanged; suffixes beginning in $P$ gain $\operatorname{bal}(q)\ge0$; and the only delicate case is $q=10$, where the suffix $0r$ requires $\operatorname{bal}(r)\ge1$, which holds because $|r|$ is odd and $r$ is an admissible suffix. Conversely, if $Pqr$ is admissible then $r$ is admissible, and every suffix of $P$ has nonnegative balance, so $Pr$ is admissible.

Therefore the $q=01,10,11$ blocks are precisely three adjacent copies of $\mu_{n-2}^{(4)}$, with senior terms

$$A_n-2\cdot2^{n-7},\quad A_n-2^{n-7},\quad A_n.$$

Combining the four ordered blocks gives exactly

$$\mu_n^{(4)} = \mu_{n-4}(A_n-3\cdot2^{n-7}) \oplus \bigl(\mu_{n-2}^{(4)}(A_n)\bigr)^3 .$$

Audit: the proof uses only the standard suffix-balance definition of A036991 and the paper’s definitions of core, subsegment, senior term, copy, and ordered concatenation. No stronger hypothesis than even $n\ge12$ is introduced.

Citation: No known published resolution found. Conjecture and notation are from G. Eremin, “Dyck Numbers, IV. Nested patterns in OEIS A036991,” arXiv:2306.10318, Conjecture 18.