Gaussian Lower Bounds for Distinct Subset Sums in Higher Dimensions
In the authors' words
For sequences of nonnegative integer vectors in with distinct subset sums, we prove, for fixed , the uniform lower bound for the largest coordinate, where \[ C_k=\sqrt{\frac{2k}{\pi}} \frac{(k+1)^{(k-1)/(2k)}}{\sqrt{\lfloor (k+1)^2/4\rfloor}}. \] The proof compares a Gaussian-kernel expectation with a sum over a translated lattice, uniformly over the vector sequence. We optimise the resulting quadratic-form constant using a vertex second-moment certificate. We show that also exceeds the variance constant obtained by optimising an ellipsoidal geometry.
Main resultLimitation the authors admit
Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.