Polylogarithmic List Replicability of Sign Matrices: Entropy Tilting, Hanner Lower Bounds, Combinatorial Bridges, and the Remaining Logarithm
BHHLT26 conjectured that every $N\times M$ sign matrix has list replicability number $O(\log N\log M)$. For $N,M\ge2$, we prove $\operatorname{lr}(B)\le 2^{31}\ln^2(2N)\ln(2M)$. The proof combines a nonlinear power-map encoding with a relative-entropy tilt that transports bounded-overlap covers without a boosting factor. The corresponding topological bound is $\operatorname{Ind}S(B)+1\le 2^{31}\ln(2N)\ln(2M)\min\{\ln(2N),\ln(2M)\}$. Hanner matrices give $\Omega(\log N\log M)$ lower bounds, a quantitative consequence of existing Hanner geometry and the index-list-replicability bridge. We also establish an unbounded restricted-output/improper separation, exact values for anchored cubes and Hadamard matrices, and exact learning-theoretic values for projective-plane classes. The binary-cube value is due to BHH+26c; the threshold value is due to CMY23. A combinatorial bridge gives $\operatorname{lr}(C_B,\varepsilon)\le\chi^*(B)\le h_+^*(B)\le h(B)\le r_2(B)+1$, while a two-piece equivariant join construction gives the sharp bound $\operatorname{Ind}S(C)\le 2s+2$ under bounded error intersections. Power-map, affine-sketch, static-label, and average-stability obstructions identify limitations of the available methods. For Paley matrices, inversion mixing reduces the residual-emptiness approach to bounding switchable monochromatic squares. The conjecture remains open, with one logarithmic factor separating the general upper bound from the Hanner lower bound in the square case.
Authors
- Guangjian Zhang (ORCID: https://orcid.org/0000-0002-4540-8179)
Institutions
- UNSW Sydney (AU)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-10
- DOI
- https://doi.org/10.5281/zenodo.22683774
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint