pipette
ESEspañol

Gaussian Lower Bounds for Distinct Subset Sums in Higher Dimensions

Zijie Gu

Preprint

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.