Back to search
2504.00184

(Don’t) Mind the Gap Complexity of Gapped Digit Substitutions

Natalie Priebe Frank, May Mei, Kitty Yang

wronghigh confidenceCounterexample detected
Category
math.DS
Journal tier
Note/Short/Other
Processed
Sep 28, 2025, 12:56 AM

Audit review

The paper’s Theorem 6 states p_S(n)=2,4, 6n+14 (n=3,4,5), and 8n+12 (n≥6). That implies p_S(3)=32 and p_S(5)=44, which is impossible for a binary sequence (where p(3)≤8 and p(5)≤32). Moreover, the paper’s own earlier computational table (Figure 5, row S(a)=b,a,b; S(b)=a,b,a) lists p(n) for n=2..10 as (4,8,14,20,28,36,44,52,60), matching the model’s formula p(3)=8, p(4)=14, p(5)=20, and p(n)=8n−20 for n≥6. The paper’s proof sketch via higher-block recoding and a right-special tree is conceptually sound, but the final constants (+14 and +12) in Theorem 6 are wrong—likely from misapplying the higher-block shift or (binary-only) Proposition 2 after recoding to an 8-letter alphabet. The model’s derivation (3-adic parent recursion, finite right-special base, and stabilization with 8 right-special factors for n≥5) is consistent with the paper’s own computational evidence and yields the correct piecewise complexity.

Referee report (LaTeX)

\textbf{Recommendation:} major revisions

\textbf{Journal Tier:} note/short/other

\textbf{Justification:}

The overall approach—recode the gapped substitution to constant length, compute a right-special tree, and translate back—is sound and pedagogically useful. However, the main theorem’s numerical constants are incorrect and contradict both binary bounds and the paper’s own earlier computations for the very same substitution. The paper needs a careful correction of Theorem 6 and a clearer explanation of how right-special counts in the recoded system are transferred back to the original (binary) complexity.