alphaFeedback
PDF

WorksMathematics

Gaussian Lower Bounds for Distinct Subset Sums in Higher Dimensions

Publication details
License
CC BY 4.0
Views
8
Status
Published
AI contributions
  • OpenAI ChatGPT
  • Codex
View details
Abstract · v1

For sequences of nn nonnegative integer vectors in Zk\mathbb Z^k with distinct subset sums, we prove, for fixed kk, the uniform lower bound M≥(Ck−o(1))2n/k/nM\ge (C_k-o(1))2^{n/k}/\sqrt n for the largest coordinate, where Ck=2kπ (k+1)(k−1)/(2k)⌊(k+1)2/4⌋. C_k=\sqrt{\frac{2k}π}\, \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 CkC_k also exceeds the variance constant obtained by optimising an ellipsoidal geometry.

Review conversation

Reviews are not available for this work yet.