Deficit bounds and equality cases in the Tu--Deng problem

Abstract

Let N=2^k−1, and let S_t,k consist of the pairs 0≤ a,b<N such that a+b≡ tpmod N and wt(a)+wt(b)<k. The Tu--Deng bound |S_t,k|≤ 2^k−1 has recently been proved. In this paper, we give a combinatorial proof of the equality criterion. If the k-bit cyclic word of t has Z zeros and g₁,…,g_Z are the numbers of ones between successive zeros, then |S_t,k|=2^k−1 Longleftrightarrow g_i≥ Z−1 (1≤ i≤ Z). Moreover, we recover the resulting enumeration of the equality parameters. Beyond equality, if R≥ Z≥2, where R is the number of ones, then every nonequality parameter satisfies 2^k−1−|S_t,k|≥ 2^R−Z+1, and we classify all cases in which this bound is attained. For R<Z we obtain a congruence for |S_t,k| and a lower bound for the deficit in terms of the number of cyclic runs of ones.

Equality Cases in the Tu-Deng Conjecture Bound
Thomas W. Cusick
arXiv8 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
A new proof of equality cases of the Brunn-Minkowski inequality on manifolds
Osama Farooqui
arXiv15 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Stack Constructions and Equality Cases for Laffey's Bound for Maximal Commutative Matrix Algebras
Małgorzata Nowak-Kępczyk
arXiv23 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Equality cases for matrix spaces with bounded-rank commutators
Zhi-Lin Zhang
arXiv1 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs
Hao Hu
arXiv30 Aug 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{cheng2026deficit,
  title = {{Deficit bounds and equality cases in the Tu--Deng problem}},
  author = {Kaimin Cheng},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.22451},
  eprint = {2608.22451},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.22451},
}

RIS

TY  - UNPB
TI  - Deficit bounds and equality cases in the Tu--Deng problem
AU  - Kaimin Cheng
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2608.22451
UR  - https://arxiv.org/abs/2608.22451
AB  - Let N=2^k−1, and let S_t,k consist of the pairs 0≤ a,b<N such that a+b≡ tpmod N and wt(a)+wt(b)<k. The Tu--Deng bound |S_t,k|≤ 2^k−1 has recently been proved. In this paper, we give a combinatorial proof of the equality criterion. If the k-bit cyclic word of t has Z zeros and g_1,…,g_Z are the numbers of ones between successive zeros, then |S_t,k|=2^k−1 Longleftrightarrow g_i≥ Z−1 (1≤ i≤ Z). Moreover, we recover the resulting enumeration of the equality parameters. Beyond equality, if R≥ Z≥2, where R is the number of ones, then every nonequality parameter satisfies 2^k−1−|S_t,k|≥ 2^R−Z+1, and we classify all cases in which this bound is attained. For R<Z we obtain a congruence for |S_t,k| and a lower bound for the deficit in terms of the number of cyclic runs of ones.
ER  -

Abstract

Related

Cite