Erdős Problem #1

Erdős Problem #1 --- Round 3: Reduction to Hypercube Bandwidth

1) ROUND-3 OBJECTIVE

We interpret the placeholder prompt as requesting Round 3, continuing from the completed Round-2 output.

Path (A): proof attempt via a stronger universal lower bound. The most promising direction after Round 2 is to exploit the full ordering of the $2^n$ subset sums, rather than a single threshold family. Round 2 already converted the problem into a labeling problem on the hypercube $Q_n$; the new idea is to replace the actual subset-sum values by their ranks. This leads directly to the bandwidth of $Q_n$, and yields a lower bound strictly stronger than the Round-2 bound \[ N\ge \binom{n}{\lfloor n/2\rfloor}. \]

2) Round-2 FOUNDATION USED

We use the following Round-2 ingredients.

1. The hypercube model: identify each subset $S\subseteq [n]$ with a vertex of $Q_n$, and define the subset-sum map \[ f(S)=\sum_{i\in S} a_i. \] This map is injective because all subset sums are distinct.
2. For adjacent vertices $S,T$ of $Q_n$ (that is, $T=S\triangle\{i\}$ for some $i$), one has \[ |f(T)-f(S)|=a_i\le N. \]
3. The Round-2 lower bound \[ N\ge \binom{n}{\lfloor n/2\rfloor}. \]
4. The Round-1 exact computations for small $n$: \[ 1,2,4,7,13,24 \] for the minimal feasible values of $N$ when $n=1,2,3,4,5,6$.

3) NEW INSIGHT / TOOL (ROUND-3)

New insight: rank-compress the subset-sum labeling and compare with the bandwidth of $Q_n$.

Let $r(S)$ denote the rank of $f(S)$ among the $2^n$ distinct subset sums. Since passing from actual values to ranks can only decrease differences, every edge of $Q_n$ has rank gap at most its actual subset-sum gap, hence at most $N$. Therefore $r$ is a numbering of $Q_n$ with bandwidth at most $N$. This gives \[ N\ge \operatorname{bw}(Q_n). \] Using the classical exact formula for the hypercube bandwidth, \[ \operatorname{bw}(Q_n)=\sum_{j=0}^{n-1}\binom{j}{\lfloor j/2\rfloor}, \] we obtain a strictly stronger general lower bound than in Round 2.

4) ATTACK PLAN (ROUND-3)

The exact gap after Round 2 is that the argument only used a single threshold family \[ F_t=\{S: f(S)\le t\}, \] and therefore only extracted one boundary estimate. To go beyond that, we now use the entire total order of the subset sums.

The precise claims to prove are:

1. The rank map $r$ is a bijection from $V(Q_n)$ to $\{1,\dots,2^n\}$.
2. For every edge $ST$ of $Q_n$, \[ |r(S)-r(T)|\le |f(S)-f(T)|\le N. \]
3. Hence $N\ge \operatorname{bw}(Q_n)$.
4. Invoking the exact bandwidth formula for $Q_n$ yields \[ N\ge \sum_{j=0}^{n-1}\binom{j}{\lfloor j/2\rfloor}. \]

This overcomes the Round-2 obstacle because it uses all thresholds simultaneously, encoded by the rank order.

5) WORK (ROUND-3)

Let \[ A=\{a_1,\dots,a_n\}\subseteq \{1,\dots,N\} \] with all subset sums distinct. As in Round 2, identify each subset $S\subseteq [n]$ with a vertex of $Q_n$, and define \[ f(S):=\sum_{i\in S} a_i. \] By hypothesis, $f$ is injective.

Lemma 5.1 (rank labeling)

Define \[ r(S):=1+\#\{T\subseteq [n]: f(T)<f(S)\}. \] Then $r$ is a bijection from $\mathcal P([n])$ onto $\{1,2,\dots,2^n\}$.

Proof. Because $f$ is injective, the $2^n$ values $f(S)$ are distinct integers and can therefore be totally ordered. The formula above assigns to each subset the position of its subset sum in that strict increasing order. Hence the values of $r$ are exactly $1,2,\dots,2^n$, each occurring once. $\square$

Lemma 5.2 (rank gap is bounded by value gap)

If $S,T\subseteq [n]$ satisfy $f(S)<f(T)$, then \[ r(T)-r(S)\le f(T)-f(S). \]

Proof. Between the two integers $f(S)$ and $f(T)$ there are exactly \[ f(T)-f(S)-1 \] integers. On the other hand, since $r(S)$ and $r(T)$ are the ranks of $f(S)$ and $f(T)$ in the ordered list of all subset sums, there are exactly \[ r(T)-r(S)-1 \] subset sums strictly between them. These are distinct integers lying strictly between $f(S)$ and $f(T)$, so \[ r(T)-r(S)-1\le f(T)-f(S)-1. \] Therefore \[ r(T)-r(S)\le f(T)-f(S), \] as claimed. $\square$

Corollary 5.3 (edge rank gaps are at most $N$)

If $S$ and $T$ are adjacent vertices of $Q_n$, then \[ |r(T)-r(S)|\le N. \]

Proof. Adjacency in $Q_n$ means that $T=S\triangle\{i\}$ for some $i\in[n]$. Therefore \[ |f(T)-f(S)|=a_i\le N. \] Applying Lemma 5.2 to the smaller and larger of $f(S),f(T)$ gives \[ |r(T)-r(S)|\le |f(T)-f(S)|=a_i\le N. \] $\square$

Theorem 5.4 (bandwidth lower bound)

For every sum-distinct set $A\subseteq \{1,\dots,N\}$ of size $n$, \[ N\ge \operatorname{bw}(Q_n). \]

Proof. By Lemma 5.1, $r$ is a numbering of the vertices of $Q_n$ by $1,2,\dots,2^n$. By Corollary 5.3, every edge of $Q_n$ has rank gap at most $N$ under this numbering. By the definition of graph bandwidth, \[ \operatorname{bw}(Q_n):=\min_{\eta:V(Q_n)\overset{\sim}{\to}\{1,\dots,2^n\}}\ \max_{uv\in E(Q_n)} |\eta(u)-\eta(v)|, \] we conclude that \[ \operatorname{bw}(Q_n)\le N. \] Equivalently, \[ N\ge \operatorname{bw}(Q_n). \] $\square$

Theorem 5.5 (explicit strengthened bound)

For every sum-distinct set $A\subseteq \{1,\dots,N\}$ of size $n$, \[ N\ge \sum_{j=0}^{n-1}\binom{j}{\lfloor j/2\rfloor}. \]

Proof. By Theorem 5.4 it suffices to invoke the classical exact formula for the bandwidth of the hypercube: \[ \operatorname{bw}(Q_n)=\sum_{j=0}^{n-1}\binom{j}{\lfloor j/2\rfloor}. \] Substituting into Theorem 5.4 yields the claim. $\square$

Thus the new lower bound sequence begins \[ 1,2,4,7,13,23,43,78,148,\dots \] for $n=1,2,3,4,5,6,7,8,9,\dots$.

Compared with the Round-2 bound \[ \binom{n}{\lfloor n/2\rfloor}=1,2,3,6,10,20,35,70,126,\dots, \] this is already a strict improvement for the displayed values $n=3,4,5,6,7,8,9$.

Combined with the Round-1 exact computations for the minimal feasible $N$ at $n\le 6$, we obtain the comparison \[ \begin{array}{c|cccccc} n & 1 & 2 & 3 & 4 & 5 & 6\\ \hline \text{Round-3 lower bound} & 1 & 2 & 4 & 7 & 13 & 23\\ \text{actual minimum from Round 1} & 1 & 2 & 4 & 7 & 13 & 24 \end{array} \] so the new theorem is exact for $n\le 5$ and misses the $n=6$ optimum by only $1$.

6) ADVERSARIAL VERIFICATION

We now stress-test the new argument.

1. Does the rank map really give a numbering? Yes. Injectivity of the subset-sum map implies a strict total order on the $2^n$ subset sums, so the ranks are exactly $1,\dots,2^n$.

2. Could rank differences ever exceed value differences? No. The proof of Lemma 5.2 uses only the fact that the subset sums are distinct integers. This integrality is essential and is satisfied here.

3. Are edge differences really one of the $a_i$? Yes. Adjacent vertices of $Q_n$ differ by toggling exactly one coordinate $i$, so their subset sums differ by exactly $a_i$ in absolute value.

4. Is positivity used? Yes, but only indirectly: the original problem has $a_i\in\{1,\dots,N\}$, so each $a_i$ is a positive integer and in particular at most $N$.

5. Does the bandwidth theorem apply to the correct graph? Yes. The graph whose vertices are subsets of $[n]$ and whose edges correspond to toggling one element is exactly the $n$-dimensional hypercube $Q_n$.

6. Interaction with Round 2. There is no conflict. Round 2 produced the weaker bound $N\ge \binom{n}{\lfloor n/2\rfloor}$ via one threshold and vertex isoperimetry. Round 3 sharpens this by compressing the entire labeling into ranks and invoking bandwidth.

No hidden assumption was found that invalidates the proof.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED)

Round 3 proves the stronger universal lower bound \[ N\ge \operatorname{bw}(Q_n)=\sum_{j=0}^{n-1}\binom{j}{\lfloor j/2\rfloor}. \] This strictly strengthens the Round-2 bound \[ N\ge \binom{n}{\lfloor n/2\rfloor}. \] It does not settle the conjecture $N\gg 2^n$; it supplies a stronger explicit lower bound, but still not one of the form $c\,2^n$ with an absolute constant $c>0$.

A useful reformulation emerging from this round is the following: the original problem asks for a very special kind of integer labeling of the hypercube---a separable labeling of the form $f(S)=\sum_{i\in S} a_i$---and Round 3 shows that every such labeling must have maximum edge difference at least the ordinary bandwidth of $Q_n$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 78%

9) REFERENCES

References

• [Bloom1] T. F. Bloom, Erdős Problem #1, online problem page.
• [Harper] L. H. Harper, Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory 1 $1966$, 385--393.
• [WWD] X. Wang, X. Wu, and S. Dumitrescu, On explicit formulas for bandwidth and antibandwidth of hypercubes, Discrete Applied Mathematics 157 $2009$, 1947--1952.
• [OEISA036256] OEIS A036256, Partial sums of central binomial coefficients; equivalently, shifted by one index, the bandwidth sequence of the hypercube graph.

10) OUTPUT FORMAT

The Erdős problem number here is $x=1$, so this continuation has been exported as 1_solutions.tex.

FORMAL RESTATEMENT

Erdős #1; reconstruction of the known counterexample, 2026-09-23. A finite set $A$ of positive integers is dissociated if its subset sums are all distinct. The conjecture asks whether an absolute $c>0$ satisfies $\max A\geq c2^{|A|}$ for every such $A$. We prove the negative answer: for every $\epsilon>0$ there are arbitrarily large $n$ and dissociated $n$-element sets with $\max A<\epsilon2^n$. The covering-system question is problem #2, not this problem.

QUICK LITERATURE AND CONTEXT CHECK

The live problem page labels this conjecture disproved and reports a Lean verification. Its exposition by Thomas Bloom, edited 2026-09-03, attributes the counterexample to GPT-6 Astra. The lattice construction below is a reconstruction of that already reported result; no novelty is claimed. I have not independently run the referenced Lean development. The earlier local attempts concern the correct distinct-sums problem but do not contain this counterexample.

The source exposition leaves its primitive-lattice approximation step in a sketch form. We give an explicit integer-matrix argument for precisely the rational lattices used here. The only standard algebraic input is Smith normal form for an integer matrix: integral row and column operations with determinant $\pm1$ reduce a full-column-rank matrix to a diagonal matrix followed by zero rows. This follows by the Euclidean algorithm on the entries. No equidistribution theorem is used.

OBJECTIVE AND ATTACK PLAN

Construct rational lattices in the sum-zero hyperplane that avoid the open unit cube and have a small normalized covolume. Approximate a slight dilation by primitive integer lattices using Smith normal form. Their positive normal vectors give integer weights without short relations; binary expansion converts these weights into ordinary dissociated sets. The slight dilation and the dyadic choice of the relation bound are both essential bookkeeping steps in this argument.

WORK

1. An odd-cycle building block

Write $V_d=\{x\in\mathbb R^d:\sum_i x_i=0\}$. A pair $(\Lambda,v)$ is admissible if $\Lambda\subset V_d$ is a lattice of rank $d-1$, $h:=\sum_i v_i>0$, and \[ \Lambda\cap(-1,1)^d=\{0\},\qquad (\Lambda+t v)\cap(-1,1)^d\ne\varnothing\ \Longrightarrow\ |t|<1. \tag{1} \] Take an odd integer $b\geq3$, number coordinates modulo $b$, and set \[ (Tz)_i=z_i+\tfrac12z_{i-1},\quad \Lambda_1=T(V_b\cap\mathbb Z^b),\quad v_1=Te_0. \] Then $h_1=3/2$. The eigenvalue calculation, or expansion of the cyclic determinant, gives $\det T=1+2^{-b}>0$. In particular, $T$ is invertible.

We check both assertions in $1$. Whenever $\|Tz\|_\infty<1$, putting $M=\|z\|_\infty$ gives $M<1+M/2$, hence $M<2$. If $z$ is integral, its coordinates belong to $\{-1,0,1\}$. A coordinate equal to $1$ forces its predecessor to be $-1$, and a coordinate $-1$ forces its predecessor to be $1$. Any nonzero coordinate would therefore force alternating signs around an odd cycle, an impossibility. Thus $z=0$, proving the first assertion even for the larger lattice $T\mathbb Z^b$.

For the second assertion let $z=z'+t e_0$, where $z'\in V_b\cap\mathbb Z^b$, and suppose $\|Tz\|_\infty<1$. The coordinates $z_1,\ldots,z_{b-1}$ are integral, and $t=\sum_i z_i$. The nonzero entries among these integral coordinates must form an initial alternating segment: a nonzero entry forces the preceding entry to have the opposite sign, while a zero cannot be followed by a nonzero entry. If the entire segment is zero, $|z_0|<1$ and $t=z_0$. Otherwise change all signs so that $z_1=1$. The inequality $|1+z_0/2|<1$ implies $z_0<0$. If $z_{b-1}=0$, the coordinate-zero inequality gives $-1<z_0<0$; the sum of the integral segment is either $0$ or $1$, so $|t|<1$. If the segment reaches $b-1$, it has even length, has sum zero, and ends in $-1$. Consequently $|z_0-1/2|<1$ and $z_0<0$ give $-1/2<t=z_0<0$. This proves $1$.

For any admissible pair put $\Gamma=\Lambda+\mathbb Zv$. Taking a basis of $\Lambda$ and appending $v$ shows \[ \operatorname{covol}(\Gamma) =\frac{h}{\sqrt d}\operatorname{covol}(\Lambda),\qquad \Delta(\Lambda):=\frac{\operatorname{covol}(\Lambda)}{\sqrt d} =\frac{\operatorname{covol}(\Gamma)}h. \tag{2} \] Here $h/\sqrt d$ is the perpendicular component of $v$ relative to $V_d$. In the building block $\Gamma_1=T\mathbb Z^b$, since $(V_b\cap\mathbb Z^b)+\mathbb Ze_0=\mathbb Z^b$. Thus $\operatorname{covol}(\Gamma_1)=1+2^{-b}$.

2. Iteration makes the normalized covolume arbitrarily small

Given an admissible rational pair $(\Lambda_s,v_s)$ in dimension $d$, set \[ \Lambda_{s+1}=\left\{(\lambda_j+\beta_jv_s)_{j=0}^{b-1}: \lambda_j\in\Lambda_s,\ \beta\in\Lambda_1\right\}, \qquad v_{s+1}=((v_1)_jv_s)_{j=0}^{b-1}. \tag{3} \] All these vectors are rational. The sum of block $j$ is $h_s\beta_j$, so the parametrization is injective, its image lies in $V_{bd}$, and its rank is $b(d-1)+(b-1)=bd-1$. It is a lattice, as the image of a product lattice under an injective linear map.

If a vector of $\Lambda_{s+1}$ lies in the open unit cube, the second part of $1$, applied block by block, gives $|\beta_j|<1$. Then $\beta\in\Lambda_1$ and the first part of $1$ imply $\beta=0$. The remaining $\lambda_j$ vanish by the same first part for $\Lambda_s$. More generally a vector of $\Lambda_{s+1}+t v_{s+1}$ in the cube has block coefficients $\gamma=\beta+t v_1$. Their absolute values are less than one by block admissibility. Admissibility of the building block then gives $|t|<1$. The new pair is therefore admissible, and $h_{s+1}=(3/2)h_s$.

To compute volumes, choose a basis $B_s$ of $\Lambda_s$ and use the block coordinate maps $(x_j,\alpha_j)\mapsto B_sx_j+\alpha_jv_s$. Each map has determinant of absolute value $\operatorname{covol}(\Gamma_s)$. The allowed coefficient lattice for the full-rank lattice $\Gamma_{s+1}$ is $(\mathbb Z^{d-1})^b\times\Gamma_1$. Hence \[ \operatorname{covol}(\Gamma_{s+1}) =(1+2^{-b})\operatorname{covol}(\Gamma_s)^b. \] In dimension $d=b^s$, $2$ consequently gives \[ \Delta_s= \frac{(1+2^{-b})^{1+b+\cdots+b^{s-1}}}{(3/2)^s}. \tag{4} \] Fix $s$ first. As odd $b\to\infty$, the logarithm of the numerator is at most $(1+b+\cdots+b^{s-1})2^{-b}\to0$. Therefore $\Delta_s\to(2/3)^s$. Choosing $s$ and then $b$ makes $\Delta_s$ as small as desired. This order of parameter choices matters.

3. Explicit primitive approximation, including dyadic scales

Let $B$ be a rational $d$ by $m$ basis matrix for one of these lattices, where $m=d-1$, and let $\Delta=\operatorname{covol}(B\mathbb Z^m)/\sqrt d$. Choose a positive integer $r$ with $C=rB$ integral. Smith normal form provides unimodular integer matrices $U,W$ such that \[ UCW=D=\begin{pmatrix}\operatorname{diag}(s_1,\ldots,s_m)\\0\end{pmatrix}, \qquad s_i>0. \] Let $E_t$ be the $d$ by $m$ matrix with entries $t s_i$ in position $(i,i)$, entries $1$ in position $(i+1,i)$, and zero elsewhere. Define \[ A_t=U^{-1}E_tW^{-1}. \] These are integer matrices and $A_t/t\to C$. The last $m$ rows of $E_t$ form a triangular matrix with diagonal entries $1$. Thus its columns generate a saturated integer lattice: if an integer vector lies in their real span, its coefficients are integral, as can be read from these last $m$ coordinates. Unimodular transformations preserve this property. The signed maximal minors of $A_t$ therefore give a primitive integral normal vector $u_t$, with \[ A_t\mathbb Z^m=u_t^\perp\cap\mathbb Z^d. \tag{5} \] Equivalently, the minor equal to $1$ before the transformations ensures that the greatest common divisor of all maximal minors is $1$.

Because the columns of $C$ span $V_d$, its signed-minor vector is $r^m\Delta(1,\ldots,1)$ after choosing its overall sign. Continuity of the minors gives \[ \frac{u_t}{t^m}\longrightarrow r^m\Delta(1,\ldots,1). \tag{6} \] In particular all coordinates of $u_t$ are positive for large $t$.

Fix $\delta>0$. For each dyadic $Q=2^\ell$, choose $t=\lceil(1+\delta)Q/r\rceil$. Then $A_t/Q\to(1+\delta)B$. For all sufficiently large such $Q$, \[ (A_t\mathbb Z^m)\cap(-Q,Q)^d=\{0\}. \tag{7} \] Indeed, if this failed along an infinite sequence, write a nonzero short vector as $A_t z_t$. Uniformly bounded left inverses of $A_t/Q$ show that the integer vectors $z_t$ remain bounded. Passing to a subsequence makes them a fixed nonzero $z$. Taking limits yields $\|(1+\delta)Bz\|_\infty\leq1$, whereas cube avoidance for $B\mathbb Z^m$ gives $\|Bz\|_\infty\geq1$, a contradiction. This also explains why the positive dilation cannot simply be omitted.

It follows from $5$--$7$ that the coordinates $u_1,\ldots,u_d$ of $u_t$ are positive integers satisfying \[ \sum_i c_i u_i=0,\quad c_i\in\mathbb Z,\quad |c_i|<Q \quad\Longrightarrow\quad c_i=0\text{ for every }i, \qquad \frac{\max_i u_i}{Q^{d-1}}\longrightarrow(1+\delta)^{d-1}\Delta. \tag{8} \] This is the required $Q$-dissociation statement at actual powers of two.

4. Binary expansion finishes the counterexample

For the weights in $8$, form \[ A_Q=\{2^j u_i:1\leq i\leq d,\ 0\leq j<\ell\}. \] An equality of two subset sums gives $\sum_i c_i u_i=0$, where $c_i=\sum_j\eta_{ij}2^j$, $\eta_{ij}\in\{-1,0,1\}$, and $|c_i|\leq2^\ell-1=Q-1$. By $8$, every $c_i$ vanishes; uniqueness of binary expansions then says that the two subsets used exactly the same powers for each $i$. In particular all the displayed elements are distinct and $A_Q$ is dissociated, with $n=d\ell$. Moreover \[ \frac{\max A_Q}{2^n} =\frac{(Q/2)\max_i u_i}{Q^d} \longrightarrow\frac{(1+\delta)^{d-1}\Delta}{2}. \tag{9} \] Given $\epsilon>0$, use $4$ to choose a lattice with $\Delta<\epsilon$. Then choose $\delta>0$ so small that $(1+\delta)^{d-1}<2$. The limit in $9$ is strictly less than $\epsilon$, and all sufficiently large $\ell$ give $\max A_Q<\epsilon2^{|A_Q|}$. Their cardinalities $d\ell$ tend to infinity. This disproves the conjectured uniform positive constant. $\square$

ADVERSARIAL VERIFICATION

The accompanying exact-arithmetic script checks the building block's integer and single-real-coordinate assertions for $b=3,5,7,9$. For the latter it intersects the strict rational intervals allowed for $z_0$, so it checks every possible real value rather than a grid sample. The proof above handles all odd $b$.

As a concrete check of the primitive approximation when $b=3$, a basis matrix after clearing denominators is \[ C=\begin{pmatrix}1&-1\\1&2\\-2&-1\end{pmatrix}. \] The procedure gives \[ A_t=\begin{pmatrix}t&-t\\t+1&2t-1\\-2t-1&2-t\end{pmatrix}, \qquad u_t=(3t^2+t+1,\ 3t^2-t,\ 3t^2). \] The script verifies the normal-vector identities and primitivity, then checks $8$ by exhaustive short-relation searches for $Q=2,4,8,16,32,64,128$ and $t=\lceil3Q/5\rceil$. These finite checks support the formulas; the limiting argument supplies the theorem for arbitrary dimension and sufficiently large scales. The script also demonstrates the failure of the odd-cycle argument for even cycle length.

FINAL STATUS AND REMAINING WORK

SOLVED (reproduction of the known negative answer). The argument establishes arbitrarily small $\max A/2^{|A|}$ with arbitrarily large $|A|$. Its input construction is credited to the current proof exposition. The matrix approximation, boundary argument, volume computation, and conversion to subsets have been checked here. There is no remaining mathematical gap identified in this reconstruction; the standard Smith normal form theorem is explicitly invoked. The published formal verification has not been audited here, and this write-up does not provide an efficient numerical construction at large dimension or improve the known asymptotic result.

SOURCES AND REPRODUCIBILITY

T. F. Bloom, problem #1 and its proof exposition, https://www.erdosproblems.com/1, accessed 2026-09-23. The source records the attribution of the construction and the current problem status. Exact checks for this reconstruction are in verification/solved_1_checks.py and their saved results in verification/solved_1_checks.json.

The estimate concerns completion of this mathematical reconstruction, not a claim of novelty, a new formal proof, or an improved quantitative bound.

COMPLETION ESTIMATE

COMPLETION: 100%

Round 2: Hypercube isoperimetry and a sharp general lower bound

1) Round-2 Objective

Path (A): proof attempt toward the conjectured bound $N\gg 2^n$. Building on the Round-1 gap---to prove or disprove the existence of an absolute $c>0$ such that $N\ge c\,2^n$ for all $n$---the most concrete promising route is an anti-concentration argument for subset sums. In this round we implement a sharp anti-concentration mechanism via the vertex-isoperimetric inequality on the hypercube, obtaining the best-known general lower bound \[ N\ge \binom{n}{\lfloor n/2\rfloor}. \] This still falls short of $N\gg 2^n$ by a factor $\Theta(\sqrt n)$, so the original conjecture remains unresolved.

2) Round-1 Foundation Used

We use the following Round-1 foundations.

1. The global hypothesis: $A\subseteq\{1,\dots,N\}$, $|A|=n$, and the subset-sum map $S\mapsto \sigma(S)$ is injective on $\mathcal P(A)$.
2. The standard identification of subsets with vertices of the hypercube $\{0,1\}^n$ and the fact that injectivity implies the $2^n$ values are distinct integers.

(We do not use Round-1 Lemmas 2--3 in this round.)

3) New Insight / Tool (Round-2)

New tool: hypercube vertex-isoperimetry (Harper) + a Lipschitz property.

Let $f:\{0,1\}^n\to\mathbb Z$ be the subset-sum function $f(x)=\sum_{i=1}^n x_i a_i$. If $x$ and $y$ differ in exactly one coordinate $i$, then $|f(x)-f(y)|=a_i\le N$, so $f$ is $N$-Lipschitz on the hypercube graph. Harper's theorem lower-bounds the vertex boundary of any family of size $2^{n-1}$ by $\binom{n}{\lfloor n/2\rfloor}$. Combining these forces at least $\binom{n}{\lfloor n/2\rfloor}$ distinct subset sums into an interval of length $N$, yielding $N\ge \binom{n}{\lfloor n/2\rfloor}$.

4) Attack Plan (Round-2)

Gap after Round-1: prove/disprove an absolute-constant bound $N\ge c\,2^n$.

Round-2 target claim: prove the strongest general lower bound accessible from a clean anti-concentration argument: \[ N\ge \binom{n}{\lfloor n/2\rfloor}. \]

Plan. Choose a median threshold among the $2^n$ distinct subset sums and take the corresponding "lower half" family $\mathcal F$ of vertices. Points in the external vertex boundary $\partial\mathcal F$ must have subset sums within $N$ of the median threshold (Lipschitz). Thus $|\partial\mathcal F|\le N$. Harper gives $|\partial\mathcal F|\ge \binom{n}{\lfloor n/2\rfloor}$, forcing the desired bound.

5) Work (Round-2)

5.1 Setup

Let $A=\{a_1,\dots,a_n\}\subseteq\{1,\dots,N\}$, and assume all subset sums are distinct. Identify each subset with its indicator vector $x\in\{0,1\}^n$ and define \[ f(x):=\sum_{i=1}^n x_i a_i\in\mathbb Z. \] Injectivity of subset sums is equivalent to $f$ being injective on $\{0,1\}^n$.

Let $Q_n$ be the hypercube graph on vertex set $\{0,1\}^n$, with $x\sim y$ if they differ in exactly one coordinate. For $\mathcal F\subseteq\{0,1\}^n$ define the external vertex boundary \[ \partial\mathcal F:=\{y\in\{0,1\}^n\setminus \mathcal F: \exists x\in\mathcal F\text{ with }x\sim y\}. \]

5.2 Lipschitz property

If $x\sim y$ and they differ in coordinate $i$, then \[ |f(x)-f(y)|=a_i\le N. \] Hence $f$ is $N$-Lipschitz on $Q_n$.

5.3 Harper's vertex-isoperimetric inequality (special case)

We use the following standard statement.

Harper (special case). If $\mathcal F\subseteq\{0,1\}^n$ has size $|\mathcal F|=2^{n-1}$, then \[ |\partial\mathcal F|\ge \binom{n}{\lfloor n/2\rfloor}. \]

5.4 Median split and localization of the boundary

Since $f$ is injective, its values on $\{0,1\}^n$ are $2^n$ distinct integers. List them in increasing order: \[ s_0<s_1<\cdots<s_{2^n-1}. \] Let \[ t:=s_{2^{n-1}-1}. \] Define the "lower half" family \[ \mathcal F:=\{x\in\{0,1\}^n: f(x)\le t\}. \] By definition of $t$ we have $|\mathcal F|=2^{n-1}$.

Now let $y\in\partial\mathcal F$. Then $y\notin\mathcal F$, so $f(y)>t$, and there exists $x\in\mathcal F$ with $x\sim y$. By the Lipschitz property, \[ f(y)-f(x)=a_i\le N \] for the flipped coordinate $i$. Since $f(x)\le t$ and $f(y)>t$, we obtain \[ t< f(y)\le t+N. \] As $f(y)$ is an integer, this implies \[ f(y)\in \{t+1,t+2,\dots,t+N\}, \] an interval containing exactly $N$ integers.

Because $f$ is injective, distinct $y\in\partial\mathcal F$ give distinct values $f(y)$. Therefore \[ |\partial\mathcal F|\le N. \]

5.5 Conclusion: the sharp general lower bound

By Harper's inequality applied to $\mathcal F$ (which has size $2^{n-1}$), \[ |\partial\mathcal F|\ge \binom{n}{\lfloor n/2\rfloor}. \] Combined with $|\partial\mathcal F|\le N$, we conclude \[ N\ge \binom{n}{\lfloor n/2\rfloor}. \]

5.6 Asymptotic form (optional corollary)

By Stirling's approximation, \[ \binom{n}{\lfloor n/2\rfloor}=\left(\sqrt{\frac{2}{\pi}}+o(1)\right)\frac{2^n}{\sqrt n}, \] so the bound implies \[ N\ge \left(\sqrt{\frac{2}{\pi}}+o(1)\right)\frac{2^n}{\sqrt n}. \]

6) Adversarial Verification

1. Small $n$ checks. For $n=1$, the bound gives $N\ge 1$; for $n=2$, it gives $N\ge 2$; for $n=3$, it gives $N\ge 3$. All are consistent with known minima and with Round-1 computations.
2. Boundary notion. The argument uses the external vertex boundary. The localization step crucially uses $y\notin\mathcal F$ (hence $f(y)>t$) and adjacency to an $x\in\mathcal F$ (hence $f(y)\le f(x)+N\le t+N$). This matches the standard formulation of Harper used here.
3. Quantifier/tie issues at the median. Injectivity of $f$ guarantees strict ordering $s_0<\cdots<s_{2^n-1}$ and ensures $|\mathcal F|=2^{n-1}$ with no ties.
4. Off-by-one in interval length. The set $\{t+1,\dots,t+N\}$ has exactly $N$ integers. Since $f$ is injective, $|\partial\mathcal F|\le N$ is correct.

7) Final Status (exactly one)

UNRESOLVED (but strictly advanced).

We proved the sharp general lower bound \[ N\ge \binom{n}{\lfloor n/2\rfloor}=\left(\sqrt{\frac{2}{\pi}}+o(1)\right)\frac{2^n}{\sqrt n}, \] via a median-splitting argument on the hypercube combined with Harper's vertex-isoperimetric inequality and the $N$-Lipschitz property of the subset-sum map. This strengthens the Round-1 lower bounds $N\ge (2^n-1)/n$ and $N\ge \binom{n}{2}+1$, but still does not prove the conjectured $N\gg 2^n$.

8) Completion Estimate

COMPLETION: 70%

9) References

References

• [BloomErdos1] T. F. Bloom, Erdős Problem #1: Distinct subset sums (online problem page).
• [DFX] Q. Dubroff, J. Fox, and M. W. Xu, A note on the Erdős distinct subset sums problem, arXiv:2006.12988.