Erdős Problem #361

Round 2 continuation for Erdős problems #319, #359, #361

This file is written as a continuation of the Round-1 write-up. I explicitly indicate below whenever I use a Round-1 result as a black box.

---

Problem #361

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. Round 1 completely solved the case $c\ge 1$, but left the whole range $0<c<1$ open. The most promising Round-2 direction is therefore to give genuinely new rigorous constructions for $c<1$, especially constructions that explain why arithmetic properties of $n$ should matter.

I will prove two new lower-bound mechanisms:

• an interval construction valid for all $c<1$;
• a new hybrid modular/large-element construction for $1/2<c<1$.

The hybrid construction depends explicitly on the smallest integer $q>1$ not dividing $n$, and this gives a rigorous arithmetic obstruction that was absent from Round 1.

2) ROUND-1 FOUNDATION USED

I use one Round-1 theorem as a black box.

• Round 1 proved that if $m\ge n$, then the maximum size of $A\subseteq \{1,\dots,m\}$ with $n\notin \Sigma(A)$ is exactly \[ m-\left\lceil \frac n2\right\rceil. \] In particular, for fixed $c\ge 1$ and $m=\lfloor cn\rfloor$, \[ G_c(n)=\lfloor cn\rfloor-\left\lceil \frac n2\right\rceil = \left(c-\frac12\right)n+O(1). \]

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is that, when $m<n$, two different obstructions can be superimposed:

• size obstruction: if all chosen elements lie in a short interval $(n/b,m]$, then any $(b-1)$-term sum is too small and any $b$-term sum is too large;
• modular obstruction plus one-large-element principle: if all elements above $n/2$ avoid the residue class $n \pmod q$, while all elements at most $n/2$ are multiples of $q$, then any subset summing to $n$ is impossible.

The second point is genuinely new in this write-up and produces a clean arithmetic lower bound depending on the smallest $q>1$ with $q\nmid n$.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was the complete absence of rigorous theorems for $c<1$.

I will now prove:

• (i) a general interval-construction lower bound for $m<n$;
• (ii) a new hybrid lower bound for $m>n/2$;
• (iii) the asymptotic form of the hybrid lower bound \[ G_c(n)\ge \left(c-\frac12+\frac{1-c}{q(n)}\right)n+O(1), \] where $q(n)$ is the smallest integer $>1$ not dividing $n$.

This does not settle the problem for $c<1$, but it gives a sharply formulated obstruction: below $c=1$, the extremal behaviour already depends on the arithmetic of $n$ at the level of explicit linear constructions.

5) WORK (ROUND-2)

For this section write \[ G(n,m):=\max\{|A|:\ A\subseteq \{1,\dots,m\},\ n\notin \Sigma(A)\}. \] Thus $G_c(n)=G(n,\lfloor cn\rfloor)$.

Proposition 361.1 (interval construction).

Let $b\ge 2$ be an integer and suppose \[ m<\frac{n}{b-1}. \] Define \[ A_b:=\left\{\left\lfloor \frac nb\right\rfloor+1,\ \left\lfloor \frac nb\right\rfloor+2,\ \dots,\ m\right\}. \] Then $n\notin \Sigma(A_b)$. Consequently, \[ G(n,m)\ge \max\!\left(0,\ m-\left\lfloor \frac nb\right\rfloor\right). \]

Proof.

Every element of $A_b$ is strictly larger than $n/b$. Therefore any sum of $b$ elements of $A_b$ is strictly larger than $n$.

On the other hand, every element of $A_b$ is at most $m$, and by assumption \[ (b-1)m<n. \] So any sum of at most $b-1$ elements of $A_b$ is strictly smaller than $n$.

Hence no subset of $A_b$ can sum to $n$. The cardinality statement is immediate. $\square$

Remark.

If $1/b\le c<1/(b-1)$ and $m=\lfloor cn\rfloor$, Proposition 361.1 gives \[ G_c(n)\ge \left(c-\frac1b\right)n+O(1). \]

Proposition 361.2 (hybrid modular/large-element construction).

Assume \[ \frac n2 < m < n. \] Let $q>1$ be any integer with $q\nmid n$, and define \[ A_q(n,m):= \{a\in \{1,\dots,\lfloor n/2\rfloor\}: q\mid a\} \ \cup\ \{a\in \{\lfloor n/2\rfloor+1,\dots,m\}: a\not\equiv n \pmod q\}. \] Then \[ n\notin \Sigma(A_q(n,m)). \]

Proof.

Let $S\subseteq A_q(n,m)$ be any subset.

Case 1: $S$ contains no element greater than $n/2$. Then every element of $S$ is divisible by $q$, so \[ \sum_{a\in S} a \equiv 0 \pmod q. \] Since $q\nmid n$, we have $n\not\equiv 0\pmod q$, so $\sum_{a\in S}\neq n$.

Case 2: $S$ contains at least two elements greater than $n/2$. Then \[ \sum_{a\in S} a > \frac n2 + \frac n2 = n, \] so again $\sum_{a\in S}\neq n$.

Case 3: $S$ contains exactly one element $y>n/2$. Every other element of $S$ is divisible by $q$, so \[ \sum_{a\in S} a \equiv y \pmod q. \] But by construction $y\not\equiv n\pmod q$. Hence $\sum_{a\in S}\neq n$.

These three cases exhaust all possibilities, so indeed $n\notin \Sigma(A_q(n,m))$. $\square$

Corollary 361.3.

Let $q(n)$ denote the smallest integer $>1$ that does not divide $n$. If $1/2<c<1$ and $m=\lfloor cn\rfloor$, then \[ G_c(n)\ge \left(c-\frac12+\frac{1-c}{q(n)}\right)n+O(1). \]

Proof.

Apply Proposition 361.2 with $q=q(n)$. The size of the constructed set is \[ |A_{q(n)}(n,m)| = \#\{a\le \lfloor n/2\rfloor:\ q(n)\mid a\} + \#\{\lfloor n/2\rfloor<a\le m:\ a\not\equiv n\pmod{q(n)}\}. \] The first term is \[ \frac{n}{2q(n)}+O(1), \] and the second term is \[ \left(m-\frac n2\right)\left(1-\frac1{q(n)}\right)+O(1) = \left(c-\frac12\right)\left(1-\frac1{q(n)}\right)n+O(1). \] Adding, \[ |A_{q(n)}(n,m)| = \left(c-\frac12+\frac{1-c}{q(n)}\right)n+O(1). \] Therefore \[ G_c(n)\ge \left(c-\frac12+\frac{1-c}{q(n)}\right)n+O(1). \] $\square$

Examples when $c=3/4$.

The new lower bound gives the following explicit infinite families.

• If $n$ is odd, then $q(n)=2$, so \[ G_{3/4}(n)\ge \frac{3}{8}n+O(1). \] This is exactly the "all even numbers" construction.

• If $n$ is even and $3\nmid n$, then $q(n)=3$, so \[ G_{3/4}(n)\ge \frac13 n+O(1). \]

• If $6\mid n$ but $4\nmid n$, then $q(n)=4$, so \[ G_{3/4}(n)\ge \frac{5}{16}n+O(1). \]

Thus, already at the level of clean explicit constructions, the lower-bound constant changes with the divisibility pattern of $n$.

6) ADVERSARIAL VERIFICATION

I check both new constructions carefully.

• Interval construction: The strict inequalities are essential. I used $m<n/(b-1)$ to force every $(b-1)$-term sum to be $<n$, and I used the lower endpoint $\lfloor n/b\rfloor+1$ to force every $b$-term sum to be $>n$. No boundary case has been glossed over.

• Hybrid construction: The only subtle point is possible overlap between the "lower multiples of $q$" and the upper interval. I avoided this by defining the two pieces on disjoint ranges: \[ [1,\lfloor n/2\rfloor] \quad\text{and}\quad [\lfloor n/2\rfloor+1,m]. \] So the case distinction by number of upper elements is exact.

• Could one upper element plus lower multiples of $q$ still sum to $n$? No. Modulo $q$, such a sum would be congruent to the upper element itself, and by construction every upper element avoids the residue class $n \pmod q$.

• Does the new lower bound really interpolate correctly between known constructions? Yes. When $q(n)=2$ (for odd $n$), the hybrid set is exactly the set of even numbers, giving the parity construction. When $q(n)$ is large, the gain over the pure interval construction becomes small, as expected.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 adds genuine new mathematics below the previously solved threshold $c=1$:

• a general interval lower bound for all $c<1$;
• a new hybrid modular/large-element construction for $1/2<c<1$;
• an explicit arithmetic lower bound \[ G_c(n)\ge \left(c-\frac12+\frac{1-c}{q(n)}\right)n+O(1), \] where $q(n)$ is the smallest integer $>1$ not dividing $n$.

So the Round-1 exact formula for $c\ge 1$ does not extend below $1$ by any naive uniform mechanism: already the best explicit constructions for $c<1$ depend on the arithmetic of $n$.

8) COMPLETION ESTIMATE

COMPLETION: 78%

9) REFERENCES

• T. F. Bloom, Erdős Problem #361, erdosproblems.com/361 (checked in this round).
• T. F. Bloom, Discussion thread for Erdős Problem #361, erdosproblems.com/forum/thread/361 (checked in this round; used only as motivation, not as a proof source).
• P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographie de L'Enseignement Mathématique 28, Geneva, 1980.

OBJECTIVE AND SOURCE REVIEW

Erdős #361; independent attempt, 2026-09-23. Determine the largest subset of $[1,\lfloor cn\rfloor]$ having no subset sum $n$, including its dependence on $n$. I read all of 361.tex, which gives interval and modular lower constructions. Here I add a verified second-order size construction; differing lower bounds alone must not be mistaken for a proof of irregularity of the optimum.

WORK: A SMALL BLOCK PLUS A LARGE BLOCK

Let $n/2<m<n$. Choose $t\le\lfloor n/2\rfloor$ with $t(t+1)/2<n-m$, and put \[ A=[1,t]\cup[\lfloor n/2\rfloor+1,m]. \] A subset with at least two members of the upper block has sum greater than $n$. One with at most one such member has sum at most $m+t(t+1)/2<n$. Thus $n$ is not a subset sum, and \[ G(n,m)\ge m-\lfloor n/2\rfloor+t. \] For fixed $1/2<c<1$ and $m=\lfloor cn\rfloor$, the maximal admissible $t$ satisfies $t=\sqrt{2(1-c)n}+O(1)$. Therefore \[ G_c(n)\ge(c-1/2)n+\sqrt{2(1-c)n}+O(1). \] Taking the larger of this and the supplied modular construction gives two complementary lower bounds: the small block supplies a square-root correction uniformly, whereas small nondivisors of $n$ can supply a linear gain. This construction is also discussed in the official comments and is not claimed as new.

ADVERSARIAL VERIFICATION AND REMAINING GAP

The inequality on $t$ is strict; equality could create a forbidden sum using $m$. The two blocks are disjoint by the imposed upper bound on $t$, automatic for sufficiently large $n$ at fixed $c$. These are existence bounds, not matching upper bounds. In particular, a dependence of a chosen construction on $q(n)$ does not prove the true optimum has that dependence. The general extremal value for $c<1$ remains undetermined.

SOURCES CHECKED

Complete local source gpt_pro_5.4/361.tex; official statement and construction comments checked at https://www.erdosproblems.com/forum/thread/361, 2026-09-23.

FINAL

UNRESOLVED. A uniform square-root correction is verified, with no proof that the construction is optimal.

COMPLETION ESTIMATE

Conservative subjective progress toward the complete extremal function. COMPLETION: 12%

Problem #361

1) FORMAL RESTATEMENT

Fix a real constant $c>0$. For each integer $n\ge 1$ let $m=\lfloor cn\rfloor$ and define \[ G_c(n):=\max\left\{|A|:\ A\subseteq\{1,2,\dots,m\}\ \text{and}\ n\notin \Sigma(A)\right\}, \] where $\Sigma(A)=\{\sum_{a\in S} a:\ S\subseteq A\}$ is the set of all subset sums. The problem asks for the size/asymptotics of $G_c(n)$ as $n\to\infty$ and whether $G_c(n)$ depends irregularly on $n$.

2) CONTEXT AND DEFINITIONS

Key observation: if $m\ge n$ and all elements are positive, then elements $>n$ cannot participate in a subset sum equal to $n$. Hence for $m\ge n$ the problem splits: \[ n\notin \Sigma(A)\quad\Longleftrightarrow\quad n\notin \Sigma(A\cap\{1,\dots,n\}). \]

3) QUICK LITERATURE/CONTEXT CHECK

The Erdős Problems forum thread for #361 reports computer checks for $c=3/4$ showing irregular dependence on $n$ (e.g. for $100\le n\le 104$ the maximum sizes are $34,37,32,38,35$), and also notes the "trivial" exact answer when $c\ge 1$.

4) ATTACK PLAN

I will give a complete proof of the exact optimum in the regime $m\ge n$ (in particular, for every fixed $c>1$ and all sufficiently large $n$): \[ G_c(n)=\lfloor cn\rfloor-\left\lceil\frac n2\right\rceil. \] This resolves the "$c\ge 1$" case and shows that in this range the dependence on $n$ is simple (only parity effects via $\lceil n/2\rceil$). For $c<1$ the general problem appears more delicate and (per the forum computations) can be irregular.

5) DETAILED WORK

It suffices to prove the following finite statement.

Theorem 361.1. Let $n,m\in\mathbb{N}$ with $m\ge n$. Then the maximum size of a set $A\subseteq\{1,\dots,m\}$ such that $n\notin\Sigma(A)$ is \[ m-\left\lceil\frac n2\right\rceil. \]

Consequence for fixed $c>1$.

If $c>1$ is fixed and $m=\lfloor cn\rfloor$, then for all large $n$ one has $m\ge n$, hence \[ G_c(n)=\lfloor cn\rfloor-\left\lceil\frac n2\right\rceil = \left(c-\frac12\right)n + O(1). \] So in this range there is no "irregular" dependence beyond parity.

6) VERIFICATION AND EDGE CASES

• For $c=1$ this gives $G_1(n)=\lfloor n/2\rfloor$, matching small-$n$ checks.
• The proof uses only the two-element obstruction $x+(n-x)=n$ and the single-element obstruction $\{n\}$; this is enough to cap the size, while the explicit $B_0$ avoids all subset sums $n$ because its elements are so large that any two already exceed $n$.

7) FINAL

UNRESOLVED (for the full range $c>0$), but with a complete solution for $c\ge 1$.

• (i) Strongest proved partial result: if $c\ge 1$ and $m=\lfloor cn\rfloor$, then \[ G_c(n)=m-\left\lceil\frac n2\right\rceil = \left(c-\frac12\right)n + O(1), \] with the explicit extremal set $A=\{\lceil n/2\rceil,\dots,n-1\}\cup\{n+1,\dots,m\}$.
• (ii) First remaining gap: determine $G_c(n)$ (or even its correct order of magnitude) for fixed $0<c<1$; explain/prove the reported irregular dependence on $n$ in that regime.
• (iii) Next moves: for $c<1$, combine "pairing" constraints with modular constructions (e.g. taking multiples of the smallest prime not dividing $n$) and optimize; try to prove matching upper bounds.
• (iv) Minimal counterexample search: for fixed $c<1$, compute/estimate $G_c(n)$ across residue classes and prime factorizations of $n$ to identify the correct extremal templates.

COMPLETION: 70%