Gaussian Lower Bounds for Distinct Subset Sums in Higher Dimensions

Introduction

This paper seeks lower bounds for the largest coordinate of a sequence of nonnegative integer vectors whose subset sums are all distinct. In dimension one, this is the Erdős distinct subset sums problem. For a positive integer $n$ and positive integers $0<a_1<\cdots<a_n$, the condition is

The variance method gives the classical Erdős–Moser bound $a_n\ge2^n/(4\sqrt{n})$, as recalled in the opening discussion of Dubroff, Fox, and Xu [4]. In the same note [4 Theorem 1], they give two proofs of the stronger asymptotic bound

The first bound holds for every $n\ge1$; the second is asymptotic as $n\to\infty$. Dubroff, Fox, and Xu explicitly record that the latter constant had already been obtained in unpublished work of Elkies and Gleason. These scalar results apply to our setting when $k=1$, after ordering the entries increasingly.

In 2026, Costa and Della Fiore [3, Theorem 1.1 and Corollary 5.3] prove the finite scalar bound

For $n\ge3$, this improves the bound obtained in the second proof of Dubroff, Fox, and Xu, while retaining the leading constant $\sqrt{2/\pi}$.

For $n\ge1$, let $m_1(n)$ denote the minimum attainable largest entry $a_n$ among the $n$-term strictly increasing positive integer sequences with distinct subset sums described above.

In dimension one, the classical Erdős conjecture asks whether $m_1(n) \ge c2^n$ for a positive absolute constant $c$. In September of 2026, Tom Adamczewski and Thomas F. Bloom report a disproof in FrontierMath Erdős, [1 Appendix B.1, Theorem 1]. More precisely, they report that for every real $\varepsilon> 0$ and every integer $L \ge1$, there exist integers $n \ge L$ and $N > 1$ and a set $A \subset\{1, \ldots, N\}$ with $|A| = n$ and all subset sums distinct, such that $N \le\varepsilon2^n$. Conditional on this reported theorem, no positive absolute $c$ satisfies the classical conjecture.

Steinerberger [7 Theorem 1 and Corollary 2] obtains the same scalar asymptotic constant through a Fourier integral involving a product of squared cosines. He also compares a smoothed signed-sum distribution with a Gaussian density, under an additional bound on the largest summand [7 Theorem 2]. This is a methodological predecessor to the present argument.

For the vector problem, we use the following conventions. Throughout, $k$ and $n$ are positive integers, with $k$ fixed as $n \to\infty$.

The minimum exists for every $k, n \ge1$. Distribute the $n$ vectors as evenly as possible among the $k$ coordinate axes, taking $e_j, 2e_j, 4e_j, \ldots$ on each used axis, where $e_j$ is the $j$th standard basis vector. Uniqueness of binary representation makes the subset sums distinct, so the set defining $m_k(n)$ is nonempty. Its integer values therefore have an attained minimum, and the construction gives

This also applies when $n < k$, with some axes unused.

For each fixed positive integer $k$, Costa, Dalai, and Della Fiore [2 arXiv:2107.07885v3, Theorem 2.5] obtain the following asymptotic bound for every admissible sequence. We take $\lambda= 1$ in their theorem: their family $\mathcal{F}_{1,n}$ is the full power set, and their $M$-bounded integer vectors lie in $[0, M]^k$, exactly as in Definition 1.1. With $\Gamma$ denoting Euler’s gamma function, their bound is

The author’s earlier preprint [5] studied the same vector problem using first- and third-moment methods.

We use a Gaussian kernel in place of a moment and prove the estimate directly for bounded vector arrays, uniformly even when their covariance matrices vary with $n$ or are singular. The coordinate bound and the distinctness condition give, respectively, lower and upper bounds on the same expectation. A suitable quadratic form then gives a single constant for every fixed dimension.

For example,

Thus the one-dimensional constant agrees with the scalar bound above. For every fixed $k$, the strict inequality $C_k>D_{k,2}$ improves the vector variance benchmark (1).

Theorem 3.3 then proves that the chosen quadratic form maximises the explicit formula $C(A)$ defined in Proposition 3.1. Its vertex certificate also describes a minimum-volume enclosing ellipsoid of a classical projected cube, as explained in Appendix § 6; the theorem does not determine the optimal constant for $m_k(n)$.

To separate the effect of the quadratic form from that of the Gaussian kernel, Proposition 4.3 also establishes the optimised variance constant

Gaussian Comparison Framework

Bounded coefficients give a lower bound for a Gaussian-kernel expectation; distinctness and integrality give an upper bound via a translated lattice. For fixed kernel parameters, these estimates are uniform over admissible sequences, including those with singular covariance matrices, and together bound the largest coordinate from below.

Centred Subset Sums and Normalisation

Let $\Sigma=(a_1,\ldots,a_n)$ be admissible as in Definition 1.1, with $M=M(\Sigma)$. Let $r_1,\ldots,r_n$ be independent and uniformly distributed on $\{-1,1\}$, and set

If $S=\{i:r_i=1\}$, then

Consequently, $X$ has $2^n$ distinct values, each with probability $2^{-n}$. All values lie in the same translate of $\mathbb{Z}^k$. The coordinates of $X$ need not be independent: they use the same random signs. Our arguments require independence of the signs only.

To apply the bounded-array Gaussian estimate and track the lattice spacing, define

Then $u_i\in[0,1]^k$, and the values of $Y$ lie in

for some $\theta\in\mathbb{R}^k$ depending on the sequence.

For this normalised vector $Y$, fix a real symmetric positive definite $k\times k$ matrix $A$ and a parameter $t>0$, both independent of $n$. We compare two bounds on

A Gaussian-Kernel Lower Bound for Bounded Random Sums

Proof. Let $G$ be a standard Gaussian vector in $\mathbb{R}^k$, independent of the signs. For every fixed $x\in\mathbb{R}^k$,

The one-dimensional Gaussian characteristic function and independence of the Gaussian coordinates give this identity. Applying (7) to each value of $Z$, we may interchange the sign and Gaussian expectations because the cosine integrand is bounded. Conditional on $G$, independence and symmetry of the signs factor the cosine average, giving

Define the positive semidefinite matrix

Taking traces and using the assumed norm bound gives

The function $\log\cos x$ is smooth on $[-1/2,1/2]$, with bounded fourth derivative. Taylor’s theorem therefore gives an absolute constant $c>0$ such that

To put all cosine arguments within this Taylor interval, define the event in the probability space of the auxiliary Gaussian vector $G$ by

Cauchy–Schwarz and $\lVert z_i\rVert_2\le\sqrt{b}$ give, on $E_n$, for every $i$,

Thus the Taylor estimate applies simultaneously to every factor in (8). Moreover,

Exponentiating the sum of the Taylor bounds gives, on $E_n$,

Use $e^{-x}\ge1-x$ for $x\ge0$. Since $T\succeq0$, we also have $0<e^{-tG^{\mathsf{T}}TG}\le1$, so the multiplicative error gives the additive bound

Outside $E_n$, the cosine product lies in $[-1,1]$ and the Gaussian term lies in $(0,1]$, so their difference is at least $-2$. Since $\mathbb{E}\lVert G\rVert_2^2=k(k+2)$, Markov’s inequality gives

Taking expectations over $E_n$ and its complement therefore gives the explicit estimate

Both error terms depend only on $k,b,t,n$, proving uniformity over the vectors. In particular,

Let $\lambda_1,\ldots,\lambda_k\ge0$ be the eigenvalues of $T$. Orthogonal diagonalisation and Gaussian integration give

Every factor $1+2t\lambda_j$ is positive, including when $\lambda_j=0$. The first inequality below is the arithmetic–geometric mean inequality for these factors; the second uses $\operatorname{tr}T\le b$:

Taking reciprocal square roots reverses this inequality, so the Gaussian expectation is at least $(1+2tb/k)^{-k/2}$. Combining this with (9) proves the lemma, without requiring $T$ to be invertible. □

A Uniform Upper Bound for Gaussian Lattice Sums

We need a lattice-sum estimate uniform in the translation. We average over a cube centred at each lattice point; symmetry removes the linear term in the quadratic form.

Proof. Write $f(x)=e^{-t x^{\mathsf{T}}Ax}$. For each lattice point $\xi\in h(\mathbb{Z}^{k}+\theta)$, let

These cubes partition $\mathbb{R}^{k}$ and each has volume $h^{k}$. Let $U$ be uniform on $[-h/2,h/2)^{k}$. Its coordinates are independent, with

Consequently,

Applying Jensen’s inequality to the convex scalar function $s\mapsto e^{-ts}$ and using the $\xi$-independent correction in (2.9) gives

Thus

Summing over the partition, using nonnegativity, yields

The substitution $y=\sqrt{t}A^{1/2}x$ gives

This proves (2.8); its factor and all preceding estimates are independent of the translation. □

For an admissible sequence, let $y_{1},\ldots,y_{2^{n}}$ be the distinct, equiprobable values of $Y$ in (2.3). Since the Gaussian weights are nonnegative,

Lemma 2.2, with $h=2/(M\sqrt{n})$, gives

The bound (13) holds for every $n \ge1$, every symmetric positive definite $A$, and every $t > 0$. For fixed $A$, $t$, the exponential factor is $1 + O_{A,t}(n^{-1})$, uniformly over the sequence, because $M \ge1$.

Main Results

Proposition 3.1 gives the bound for a general quadratic form; evaluating a particular form then proves Theorem 1.2. Subsection 3.3 separately certifies optimality within the quadratic-form formula.

The Bound Associated with a General Quadratic Form

Proof. Use $u_i,Y$ from (4) and set $z_i=A^{1/2}u_i$. Positive definiteness gives $b_A \ge e_1^\mathsf{T}Ae_1 > 0$, while $\lVert z_i\rVert_2^2 = u_i^\mathsf{T}Au_i \le b_A$. Also,

Lemma 2.1 therefore gives, for fixed $t > 0$,

Combining this with (13) and writing $R_n=M\sqrt{n}/2^{n/k}$ yields

The leading term on the left is positive for fixed $t$. Thus there are constants $\alpha_t,\beta_t \ge0$, depending only on $A,k,t$, such that, for all sufficiently large $n$ and every admissible sequence,

The numerator is positive for all sufficiently large $n$, with a threshold independent of the sequence. Moreover,

To obtain the constant $C(A)$ while retaining the fixed-$t$ error estimate, let $\delta> 0$. First choose a finite $t=t(A,k,\delta)$ such that $F_A(t)\ge C(A)-\delta/2$. Keep this $t$ fixed and choose $n_0=n_0(A,k,\delta)$ so that the factor in the finite-$n$ bound changes $F_A(t)$ by at most $\delta/2$ whenever $n\ge n_0$. Then

for every admissible sequence and every $n\ge n_0$.

This proves the asserted uniform error. □

The finite-$n$ Gaussian and lattice estimates above are used with fixed $A,t$; no uniformity for arbitrary choices $A=A_n$ or $t=t_n$ is asserted.

Choice of Quadratic Form and Proof of the Main Theorem

Proposition 3.1 reduces the choice of the leading constant to maximising $(\det A)^{1/(2k)}/\sqrt{b_A}$. A useful candidate is invariant under coordinate permutations and scales the all-ones direction differently from its orthogonal complement. Let $I_k$ denote the identity matrix, let $\mathbf{1}=(1,\ldots,1)^{\mathsf{T}}$, and take

Proof. The matrix $\mathbf{1}\mathbf{1}^{\mathsf{T}}$ has eigenvalue $k$ in the $\mathbf{1}$ direction and eigenvalue $0$ on its orthogonal complement. Thus the eigenvalues of $H$ are $1/(k+1),1,\ldots,1$, proving positive definiteness and the determinant formula.

The quadratic form

is convex in each coordinate separately. Holding the other coordinates fixed, a maximum on $[0,1]$ can be attained at an endpoint. Repeating this for every coordinate shows that the maximum on the cube is attained at a vertex. At a vertex with $r$ coordinates equal to $1,

The maximum of $r(k+1-r)$ over integers $0\le r\le k$ is $\lfloor(k+1)^2/4\rfloor$, giving the formula for $b_H$. □

Proof of Theorem 1.2. Take $A=H$ in Proposition 3.1. Using Proposition 3.2,

This proves (1.2). □

Optimality of the Quadratic-Form Formula

Proof. For $k=1$, $A$ is a positive scalar and $b_A=A$, so $C(A)=\sqrt{2/\pi}=C_1$. Suppose henceforth that $k\ge2$. Recall from Proposition 3.2 that

We construct a random cube vertex $V \in\{0,1\}^{k}$ whose uncentred second moment is proportional to $H^{-1}$. This choice will make the averaging and matrix inequalities below sharp at $A=H$. Specifically, we require

First choose the number $R$ of coordinates equal to 1, and then choose uniformly among the vertices with that number of ones. If $k$ is odd, set $R=(k+1)/2$. Here $b_H=(k+1)/4$, and

If $k=2m$ is even, set

Since $b_H=m(m+1)/(2m+1)$, direct calculation gives

Coordinate symmetry now gives, for $j\ne\ell$,

This proves (16).

The matrix $S$ is positive definite and satisfies

For every positive definite $A$, the support of $V$ lies in $[0,1]^k$, so averaging its quadratic-form values gives the first inequality below. For the second, apply the arithmetic–geometric mean inequality to the positive eigenvalues of the symmetric positive definite matrix $A^{1/2}SA^{1/2}$. Its trace is $\operatorname{tr}(AS)$ and its determinant is $\det A\det S$; no commutativity of $A$ and $S$ is needed. Thus

Consequently,

By Proposition 3.2 and $S=(b_H/k)H^{-1}$,

Substitution gives

The chosen values of $R$ all maximise $R(k+1-R)$, so $V^{\mathsf T}HV=b_H$ throughout the support of $V$. Also, $H^{1/2}SH^{1/2}=(b_H/k)I_k$. Thus both inequalities in $b_H\geq\operatorname{tr}(HS)\geq k(\det H\det S)^{1/k}$ are equalities, and $H$ attains the upper bound $C_k$. □

The geometric interpretation of this certificate is given in Appendix § 6, Remark A.1.

Optimised Variance Comparison

The variance bound $(1.1)$ uses the Euclidean geometry of the original lattice. To distinguish the effect of the quadratic form from that of the kernel, we apply the second-moment comparison after a linear change of coordinates, using transformed unit cubes and the ball second moment in the centred model. The relation to the quadratic-form constant, together with Theorem 3.3 and Proposition 4.2, yields the optimisation and comparison. The transformed-variance proof does not use the Gaussian probability estimate.

Euclidean Prerequisites

For a positive integer $k$ and $R \ge0$, write

Proof. First let $v=\operatorname{vol}(B_{k,2}(1))$ be the unevaluated unit-ball volume. The inclusions

give $0<v<\infty$. Homogeneity of the norm gives $B_{k,2}(r)=rB_{k,2}(1)$ for $r>0$, so its volume is $vr^{k}$. At $r=0$, the ball is a singleton of volume zero since $k\ge1$.

Thus the image of Lebesgue measure under $x\mapsto\lVert x\rVert_{2}$ assigns mass $vr^{k}$ to $[0,r]$, and has density $kvr^{k-1}$ for $r>0$. For every nonnegative Borel function $f$, this gives the radial integration formula

The substitution $s=x^{2}$ on the positive half-line gives

Since the integrand below is a nonnegative product, Tonelli’s theorem gives

Applying the radial formula with $f(r)=e^{-r^{2}}$ and substituting $s=r^{2}$ gives

Since $k\ge1$, the gamma integrals are finite, and the two evaluations give

Finally, apply the radial formula with $f(r)=r^{2}\mathbf{1}_{[0,R]}(r)$, where $\mathbf{1}_{E}$ denotes the indicator of a set $E$:

This also holds at $R=0$, when both sides vanish. □

Proof. Let $Q=[-1,1]^k$ and $B=B_{k,2}(\rho)$, where

By Proposition 4.1, $\operatorname{vol}(B)=\operatorname{vol}(Q)=2^k$. The sets $Q\setminus B$ and $B\setminus Q$ have equal volume. The function $\lVert x\rVert_2^2$ is at least $\rho^2$ on the first set and at most $\rho^2$ on the second. Subtracting the two integrals, which are finite, therefore gives

The ball moment formula (17) and integration of each coordinate over the cube yield

Dividing by $k>0$ and taking positive square roots gives

Here $D_{k,2}$ is defined in (1), and $\Gamma(3/2)=\sqrt{\pi}/2$ gives the displayed scalar value. Since $\pi<4$, we have $1/\sqrt{3}<\sqrt{2/\pi}$. Finally, $b_{I_k}=k$ and $\det I_k=1$, so the definition of $C(A)$ gives $C(I_k)=\sqrt{2/\pi}$. Theorem 3.3 then gives $C_k\ge C(I_k)=C_1$, completing (4.2). □

The Variance Bound on a Transformed Lattice

For a real symmetric positive definite $k\times k$ matrix $A$, define

For fixed $k,A$, this gives $M\ge(V_k(A)-o(1))2^{n/k}/\sqrt{n}$, with an error depending only on $k,A,n$, uniformly over admissible sequences. Moreover,

The first inequality is an equality for $k=1$ and is strict for $k\ge2$.

Proof of Proposition 4.3. Let $s_1,\ldots,s_N$ be the values of $X$ from Subsection 2.1, where $N=2^n$. They are distinct points in one translate of $\mathbb{Z}^k$, each with probability $1/N$. Let $U$ be independent of $X$ and uniform on $[-1/2,1/2)^k$. The sets

are disjoint and each has volume $\sqrt{\det A}$. Hence $A^{1/2}(X+U)$ is uniform on their union $E$, of volume $N\sqrt{\det A}$. Put $R = (N\sqrt{\det A}/v_{k,2})^{1/k}$. The sets $E \setminus B_{k,2}(R)$ and $B_{k,2}(R) \setminus E$ have equal volume. The function $\lVert x\rVert_2^2$ is at least $R^2$ on the first and at most $R^2$ on the second. All the integrals are finite because the sets are bounded. The ball moment formula in Proposition 4.1 therefore gives

The cube averages satisfy $\mathbb{E}U=0$ and $\mathbb{E}[UU^{\mathsf T}]=I_k/12$. Independence of $X$ and $U$ eliminates the mixed term, so

For the signs defining $X$, independence and symmetry give $\mathbb{E}[r_i r_j]=0$ for $i\ne j$ and $\mathbb{E}[r_i^2]=1$. Since $a_i/M\in[0,1]^k$,

Combining these estimates yields

Using $v_{k,2}=\pi^{k/2}/\Gamma(1+k/2)$, dividing by $2^{2n/k}b_A/4>0$, and then taking nonnegative square roots gives (4.3). For fixed $k$, $A$, its right side tends to $V_k(A)>0$ and depends only on $k$, $A$, $n$, proving uniformity. No invertibility of the covariance matrix of $X$ is required.

The identity $V_k(A)=D_{k,2}C(A)/C_1$ and Theorem 3.3 give the supremum in (4.4). Proposition 4.2 gives $D_{k,2}<C_1\le C_k$, hence $D_{k,2}\le V_k<C_k$.

For $k=1$, $C_k=C_1$. For $k\ge2$, the second moment matrix $S$ in (3.3) has the distinct eigenvalues $b_H/k$ and $(k+1)b_H/k$. Thus the matrix arithmetic–geometric mean inequality in the proof of Theorem 3.3 is strict at $A=I_k$, giving $C_1<C_k$ and therefore $D_{k,2}<V_k$. □

The ratio $V_k/D_{k,2}=C_k/C_1$ records the improvement obtained by optimising the quadratic form in the variance argument. For the same quadratic form, the Gaussian constant exceeds the variance constant by the factor below, which equals $C_k/V_k$ at $A=H$:

Concluding Remarks

For fixed $k$, combining Theorem 1.2 with the construction following Definition 1.1 gives, as $n\to\infty$,

These bounds do not determine the precise asymptotics of $m_k(n)$.

A possible refinement is to retain the covariance matrix rather than pass immediately to the trace bound. In the application of Lemma 2.1, for fixed $A\succ0$ we have

Equation (2.7) retains the factor $\det(I_k+2tT)^{-1/2}$, with an error uniform over the sequence for fixed $k$, $A$, $t$, even when $T$ is singular. The present argument does not determine whether admissibility constrains $T$ or the subset-sum locations sufficiently to improve the uniform leading constant.

Theorem 3.3 rules out such an improvement by optimising the formula $C(A)$ alone; it does not rule out sharper finite-$n$ errors or refinements before the trace estimate.

Geometric Interpretation of the Quadratic-Form Certificate

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

OpenAI ChatGPT and Codex were used for literature and bibliographic assistance, manuscript editing and organisation.

The author independently verified the mathematical arguments and takes full responsibility for the content of the manuscript.