REVIEW 2 major objections 3 minor 13 references
Cyclic deletion rigidity and Macaulay shadows in the Tu--Deng problem
T0 review · 2 major / 3 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read The paper proves that the Tu–Deng bound $|S_{t,k}| \le 2^{k-1}$ is attained exactly when every cyclic zero-gap in the k-bit word of $t$ has length at least $Z-1$, and quantifies the deficit away from equality.
desk verdict The paper likely settles the Tu-Deng equality classification with genuinely new structural machinery, but its main theorem rests entirely on an unrefereed carry identity from [10] that is quoted, not proved. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument runs through three interlocking objects. First, the finite language $L(v)=\mathrm{Sub}(v)\cup\{u\in\partial_1\mathrm{Sub}(v): u<_{\mathrm{lex}} v\}$ attached to a rotation $W=10v$ of the cyclic word, whose bivariate weight enumerator $J_v(X,Y)$ carries the fixed-content counts; the proof inherits the identity $C_v(X,Y)=1+(X+Y-1)J_v(X,Y)+X^ZY^R$ expressing the cyclic-carry enumerator through this language. Second, the fixed-content defects $\Delta_\ell(v)=2j_{\ell,\ell-1}(v)-j_{\ell,\ell}(v)$, which are nonnegative by marked-deletion counting and decompose the Tu–Deng deficit through $2^{k-1}-|S_{t,k}|=\sum_{\ell\ge1}2^{k-2\ell-1}\Delta_\ell(v)$ plus an indicator term. Third, an explicit matrix conjugation identifies the coefficient polynomial $H_W$ of the other complete proof with $J_v$, and a rooted coarsening model represents balanced slices as bounded gap-constrained monomial families; Macaulay shadow theory then yields the exact deletion-flux identity $\Delta_m(L)=2|\partial F_m|-|F_m|+2o_m$ and, at the top level, the inclusion–exclusion Macaulay–Möbius formula for $\Delta_m(W)$.
What would settle it
Compute $|S_{t,k}|$ by direct enumeration for all $1\le t<2^k-1$ with $k\le 10$ and test the classification: any $t$ whose cyclic word has some gap shorter than $Z-1$ while $|S_{t,k}|=2^{k-1}$ would refute Theorem 7.5. In the $R\ge Z$ range, search for a non-equality word with deficit strictly between $1$ and $2^{R-Z+1}-1$, or with exactly one gap of length $Z-3$ and all others large, and compare the deficit with the Macaulay–Möbius prediction; a mismatch would refute the first stability gap.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is the complete equality classification for the Tu–Deng bound. Writing $R$ and $Z$ for the numbers of ones and zeros in the $k$-bit cyclic word of $t$, and $g_1,\ldots,g_Z$ for the cyclic numbers of ones between successive zeros, the theorem states that $|S_{t,k}|=2^{k-1}$ if and only if $g_i\ge Z-1$ for every $i$. This establishes the converse direction of the separated-zero family conjecture stated in the 2010 literature, and the paper also enumerates the equality parameters: for exactly $Z$ zeros, the count is $\frac{k}{Z}\binom{k-Z^2+Z-1}{Z-1}$ when $Z\le\lfloor\sqrt{k}\rfloor$, and zero otherwise. Away from equality, when $R\ge Z$ the deficit satisfies $2^{k-1}-|S_{t,k}|\ge 2^{R-Z+1}$, with two explicitly described extremal families attaining equality in that bound; when $R<Z$ the deficit is $2^{Z-R}M_-(W)-1$ for a positive integer $M_-(W)$, forcing $|S_{t,k}|\equiv 1\pmod{2^{Z-R}}$ and making equality impossible.
Load-bearing premise
The load-bearing premise is the quoted cyclic-carry enumerator description of $S_{t,k}$ from the recent preprint literature, specifically the identity $C_v(X,Y)=1+(X+Y-1)J_v(X,Y)+X^ZY^R$ and the evaluation $|S_{t,k}|/2^k=\Phi^-(C_v)$; this description is not re-derived here, and if it or the one-sided deletion closure of $L(v)$ contained an error, the defect decomposition and all subsequent classifications would lose their foundation.
Editorial extensions
If this is right
- The separated-zero equality family is exhaustive: equality in the Tu–Deng bound holds exactly when every zero-to-zero gap contains at least $Z-1$ ones.
- For $R\ge Z$, every non-equality parameter is at least $2^{R-Z+1}$ away from the bound, and the closest words are completely classified: exactly one gap of length $Z-2$ with all others at least $Z-1$, plus one extra family when $Z=3$.
- For $R<Z$, equality is impossible, the deficit always has the exact form $2^{Z-R}M_-(W)-1$, and the congruence $|S_{t,k}|\equiv1\pmod{2^{Z-R}}$ holds.
- The coefficient polynomial of one complete proof and the language enumerator of the other are the same object, so the coefficient inequalities in the two proofs are identical statements.
- All equality parameters are enumerated: for $Z$ zeros there are $\frac{k}{Z}\binom{k-Z^2+Z-1}{Z-1}$ of them, and none once $Z^2>k$.
Reading between the lines
- A natural next step, which the paper explicitly leaves open, is to determine the sharp minimum of $M_-(W)$ for fixed $R<Z$; the coarsening model reduces this to a finite multi-level optimization over the defects $\Delta_1,\ldots,\Delta_R$.
- The Macaulay–Möbius formula suggests a broader principle: any deletion-closed language whose balanced slices are bounded monomial families should have defects controlled by Macaulay barriers, so analogues of the first stability gap may hold for other subsequence-counting problems.
- Because the equality condition depends only on the cyclic gap lengths, the classification could be converted into a sampling statement: for random $t$, the probability of hitting the bound equals the probability that a random $k$-bit word with $Z$ zeros has all gaps at least $Z-1$, which could sharpen the known almost-sure result into an exact asymptotic rate.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the Tu–Deng bound |S_{t,k}|≤2^{k−1}. Its main result (Theorem 7.5) is a complete equality classification: for the k-bit cyclic word of t with R ones, Z zeros, and cyclic one-gap lengths g_1,...,g_Z, equality holds if and only if g_i≥Z−1 for every i. This proves Conjecture 3.20 of Flori–Randriambololona–Cohen–Mesnager. The paper also enumerates the equality parameters (Corollary 7.7), proves a sharp first stability gap when R≥Z (Theorem 7.8), and obtains a quantized deficit with a run-sensitive lower bound when R<Z (Theorem 7.2). Structurally, it proves an explicit matrix conjugation identifying Cusick's H_W with the Liu–Luo–Xie enumerator J_v (Theorem 3.3), develops a rooted coarsening model for the coefficients, proves one-sided deletion rigidity (Theorem 4.3), and derives an exact Macaulay–Möbius formula at the top cyclic level (Theorem 6.3).
Significance. Subject to the validity of the quoted carry-enumerator identities, this is a substantial and coherent contribution. The equality classification is the natural completion of the Tu–Deng conjecture, and the enumeration formula is explicit and testable. The proof machinery is original and elegant: the matrix-conjugation bridge between the two 2026 proofs, the deletion-rigidity classification, and the Macaulay-flux identity are likely to be reusable. The paper is careful to state its external dependency on Proposition 2.1 from the unrefereed preprint [10], and the internal derivations (marked-deletion double count, bounded-simplex formula, inclusion–exclusion) are consistent. The main theorems give falsifiable predictions, and the stability bound in Theorem 7.8 is sharp with a complete extremal family. The principal weakness is not internal inconsistency but the unproven external foundation.
major comments (2)
- [§2.1, Proposition 2.1] The entire defect decomposition (2.3), and therefore the central equality classification (Theorem 7.5), the quantization in Theorem 7.2, and the stability gap in Theorem 7.8, rest on identities (2.1) and (2.2) quoted from the unrefereed preprint [10]. The paper does not re-derive these identities, and the bridge theorem (Theorem 3.3) is not used to supply them. If [10] is not yet accepted, the main results are conditional on an external verification. The authors should either provide a self-contained proof of Proposition 2.1 in this paper, or explicitly state that the results are conditional on the correctness of [10] and update the exposition once [10] has a published version.
- [Theorem 7.2(ii), proof of (7.4)] The formula (7.4) is obtained by applying Theorem 6.1 to the complemented word W, but this application is outside the stated hypotheses of Theorem 6.1, which assumes R≥Z≥2. For W the roles are reversed: R(W)=Z and Z(W)=R, and (7.4) is being proved exactly in the complementary range R<Z. The argument inside the proof of Theorem 6.1 only appears to require q<R (where R is the number of ones of the word to which it is applied), but this weaker hypothesis is not stated. Please state and prove a generalized top-level bounded-simplex lemma covering q<R for arbitrary cyclic words, or otherwise justify (7.4).
minor comments (3)
- [§7.2, after (7.4)] In the proof of Theorem 7.2, the same symbols R and Z are reused for the complemented word W immediately after being used for the original word W; this is understandable but could confuse readers. Consider writing R' and Z' for the complemented word.
- [Corollary 4.5, proof] The sentence 'contrary to the assumed range of s' would be clearer if it explicitly noted that the 1-deletion down-set generated by a nonempty balanced family automatically has nonempty content level (m,m−1), so the only way for Δ_m(L) to vanish is for both levels to be full.
- [§3, Theorem 3.3] After subtracting the two expressions for tr M_W(Y,X) and C_v(X,Y), the cancellation of X+Y−1 is valid because Z[X,Y] is an integral domain; a brief remark to this effect would make the argument fully explicit.
Circularity Check
No circular derivation: the equality classification is derived from independent defect and shadow arguments; reliance on the external Liu–Luo–Xie enumerator is an unverified dependency, not a self-referential reduction.
full rationale
Theorem 7.5 is not assumed as an input. It is proved by combining Proposition 2.2's defect decomposition, Theorem 4.3's rigidity classification, and Theorem 6.1's bounded-simplex description; each step is derived from explicit coefficient identities rather than from the equality statement itself. The only heavily loaded external premise is Proposition 2.1, quoted from Liu, Luo and Xie [10], but those authors are not the present author and the proposition states coefficient identities for the cyclic-carry enumerator, not the equality classification. Cusick's polynomial definition in (2.5) is also external but is a definition. The author's self-citations [1] and [2] are motivational or historical and do not supply any premise for Theorem 7.5. No fitted parameter is renamed as a prediction: the quantities in the classification are exact combinatorial counts. The external dependence on an unrefereed preprint is a correctness risk, not a circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption The Liu-Luo-Xie cyclic-carry enumerator satisfies C_v(X,Y)=1+(X+Y-1)J_v(X,Y)+X^Z Y^R and |S_{t,k}|/2^k=Phi^-(C_v) (Proposition 2.1), and L(v) is closed under deletion of a 1.
- standard math Clements-Lindstrom lower-shadow bound |∂F| >= ∂_m(|F|) for degree-m monomial families and the strict positivity of Phi_m in the interior.
- standard math Products of polynomials 1+y+...+y^a have symmetric unimodal coefficient sequences.
Cite this review
Pith. "Pith review of Cyclic deletion rigidity and Macaulay shadows in the Tu--Deng problem." pith.science (2026). https://pith.science/paper/746QMNCD
@misc{pith2026260822451,
author = {Pith},
title = {Pith review of: Cyclic deletion rigidity and Macaulay shadows in the Tu--Deng problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/746QMNCD}},
note = {Machine review of arXiv:2608.22451}
}
abstract
We determine all equality cases in the Tu--Deng bound $|S_{t,k}|\le 2^{k-1}$. If the $k$-bit cyclic word of $t$ has $R$ ones, $Z$ zeros, and cyclic one-gap lengths $g_1,\ldots,g_Z$, then equality holds if and only if $g_i\ge Z-1$ for every $i$. This resolves Conjecture~3.20 of Flori, Randriambololona, Cohen and Mesnager, and we also enumerate all equality parameters. For $R\ge Z$ we determine the sharp first stability gap and all extremal words, while for $R<Z$ we obtain an exact quantization of the deficit and an explicit run-sensitive lower bound. The proofs are structural: an explicit matrix conjugation identifies the auxiliary enumerators in the two recent complete proofs of the Tu--Deng conjecture. We then develop a rooted coarsening model for all coefficients, prove one-sided deletion rigidity and an exact Macaulay-flux identity, and derive a Macaulay--M\"obius formula from the bounded simplex at the highest cyclic level.
Reference graph
Works this paper leans on
-
[10]
R. Liu, H. Luo and T. Xie, A complete proof for Tu–Deng conjecture, arXiv:2608.05187, 2026
work page Pith review arXiv 2026
-
[1]
A first-exit proof of Cusick's sum-of-digits conjecture
K. Cheng, A first-exit proof of Cusick’s sum-of-digits conjecture, arXiv:2606.23398, 2026
work page Pith review arXiv 2026
-
[2]
K. Cheng, S. Hong and Y. Zhong, A note on the Tu–Deng conjecture,J. Syst. Sci. Complex.28 (2015), no. 3, 702–724, DOI 10.1007/s11424-015-2240-3
-
[3]
Y. Chen, L. Lin and C. Wei, About the Tu–Deng conjecture forw(t) less than or equal to 10,IACR Cryptol. ePrint Arch.2020, Paper No. 227
work page 2020
-
[4]
G. F. Clements, More on the generalized Macaulay theorem,Discrete Math.1(1971), no. 3, 247– 255
work page 1971
-
[5]
G. F. Clements and B. Lindstr¨ om, A generalization of a combinatorial theorem of Macaulay,J. Combinatorial Theory7(1969), no. 3, 230–238
work page 1969
-
[6]
T. W. Cusick, Proof of the Tu–Deng conjecture, arXiv:2608.14821, 2026
work page Pith review arXiv 2026
-
[7]
T. W. Cusick, Y. Li and P. St˘ anic˘ a, On a combinatorial conjecture,Integers11(2011), Paper No. A17
work page 2011
Show all 13 references
-
[8]
Deng and P
G. Deng and P. Yuan, On a combinatorial conjecture of Tu and Deng,Integers12(2012), Paper No. A48
2012
-
[9]
Flori, H
J.-P. Flori, H. Randriambololona, G. Cohen and S. Mesnager, On a conjecture about binary strings distribution, in:Sequences and Their Applications–SETA 2010, Lecture Notes in Comput. Sci. 6338, Springer, Berlin, 2010, pp. 346–358, DOI 10.1007/978-3-642-15874-2 30
2010 doi
-
[11]
F. S. Macaulay, Some properties of enumeration in the theory of modular systems,Proc. London Math. Soc.(2)26(1927), 531–555
1927
-
[12]
Spiegelhofer and M
L. Spiegelhofer and M. Wallner, The Tu–Deng conjecture holds almost surely,Electron. J. Combin. 26(2019), no. 1, Paper No. P1.28
2019
-
[13]
Tu and Y
Z. Tu and Y. Deng, A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity,Des. Codes Cryptogr.60(2011), no. 1, 1–14. School of Mathematical Sciences, China West Normal University, Nanchong 637002, P. R. China Em...
2011
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.