Study reveals when weighted sums keep unique representations stable
Rényi stability of $B_h$ sets: a two-order phase diagram and sharp deletion principles
Information Theory
Summary
The paper looks at special sets of numbers where sums of a certain size have only one way to be made, like unique sums of pairs. The authors explore how much you need to remove from a weighted list to keep this uniqueness if there's only a little bit of mixing or overlap, measured by a special entropy concept. They find exact conditions and rates on when this stability happens and when it fails, providing sharp boundaries to understand this behavior. Their results come from new mathematical inequalities and constructions that perfectly match the limits they describe.
What this means in practice
- •For cryptographic engineers: Design cryptographic protocols relying on unique sum properties with guaranteed stability under noisy or weighted inputs.
- •For error-correcting code designers: Develop codes that maintain unique decodings by understanding how weighted signal overlaps affect stability and require minimal corrections.
A theory result. No direct application yet.
Authors
Jae Oh Woo
Abstract
A set $B$ in an abelian group is a $B_h$ set if every $h$-term sum has a unique representation up to permutation; for $h=2$ these are the Sidon sets. We study a weighted removal problem for this collision-free property: if the $h$-fold sum map has small Rényi entropy loss, how much probability mass must be deleted to leave a $B_h$ support? Two Rényi orders naturally arise: a collision order $α$, measuring the entropy loss, and a budget order $β$, controlling how spread out the weighting may be. Existing one-order formulations tie the two together on the diagonal $β=α$. We determine the resulting stability problem on the full $(α,β)$-plane. Stability holds exactly when $β\le1$ and $α\geβ$. Inside this region the optimal deletion rate is polynomial for $β<1$ and logarithmic on the boundary $β=1$, where the leading constant is exact; outside it, stability fails through two distinct mechanisms: a supercritical budget and dilution by light atoms. In each case the limiting defect is computed exactly. The upper bounds follow from a sharp list-coarsening inequality with optimal constant, which also yields an entropy-free removal theorem, a finite combinatorial consequence for moments of the representation function, and extensions to $B_h[g]$ sets. Matching constructions show that the phase boundaries and rates are sharp.