DISPROVED (LEAN)
This has been solved in the negative and the proof verified in Lean.
Is it true that if $A=\{a_1<\cdots <a_t\}\subseteq \{1,\ldots,N\}$ has no solutions to\[a_i+a_{i+1}+\cdots+a_j\in A\]then\[\lvert A\rvert \leq \frac{N}{2}+O(1)?\]
A finitary version of
[839]. Taking $A=(N/2,N]\cap \mathbb{N}$ shows $\lvert A\rvert \geq N/2-O(1)$ is possible.
Adenwalla has observed that\[\lvert A\rvert \leq (\tfrac{2}{3}+o(1))N.\]Indeed, if $\lvert A\cap [x,2x]\rvert=t$ then there are $t-1$ distinct sums of consecutive pairs of elements in $(2x,4x]$, all of which are not in $A$ by assumption. It follows that\[\lvert A\cap [x,4x]\rvert \leq t+(2x-(t-1))=2x+1.\]It follows that\[\lvert A\rvert \leq \sum_{i\geq 1}\lvert A\cap [4^{-i}n, 4^{1-i}n]\rvert \leq \frac{2}{3}n+O(\log n).\]In fact this problem is false. Freud
[Fr93] constructed a sequence with density $\geq 19/36$. The current best bounds are due to Coppersmith and Phillips
[CoPh96], who prove that the maximal size of such an $A$ satisfies\[\frac{13}{24}N -O(1)\leq \lvert A\rvert \leq \left(\frac{2}{3}-\frac{1}{512}\right)N+\log N.\]
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
PietroMonticone
|
|
I am working on formalising the results on this problem
|
PietroMonticone
|
Additional thanks to: Sarosh Adenwalla, Boris Alexeev, and Desmond Weisenberg
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #867, https://www.erdosproblems.com/867, accessed 2026-04-11
