/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
[ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number
theory. Monographies de L'Enseignement Mathematique (1980).
[Er61b] Erdős, P., On the representation of large integers as sums of distinct summands
taken from a fixed set. Acta Arith. (1961/62), 345-354.
[Fo66] Folkman, J., On the representation of integers as sums of distinct terms from a
fixed sequence. Canadian J. Math. 18 (1966), 643-655.
[SzVu06] Szemerédi, E. and Vu, V., Long arithmetic progressions in sumsets: thresholds and
bounds. J. Amer. Math. Soc. 19 (2006), 119-169.
[SzVu06b] Szemerédi, E. and Vu, V., Finite and infinite arithmetic progressions in sumsets.
Ann. of Math. 163 (2006), 1-35.
@[expose]publicsectionopenFilternamespaceErdos344
If $A\subseteq \mathbb{N}$ is a set of integers such that
$$\lvert A\cap {1,\ldots,N}\rvert\gg N^{1/2}$$
for all $N$ then must $A$ be subcomplete? That is, must
$$P(A) = \left{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right}$$
contain an infinite arithmetic progression?
This is true, and was proved by Szemerédi and Vu [SzVu06].
The implied constant is absolute, as in [SzVu06b, Corollary 1.4].
The stronger conjecture that this is true under
$$\lvert A\cap {1,\ldots,N}\rvert\geq (2N)^{1/2}$$
seems to be still open (this would be best possible as shown by [Er61b]).
The bound is required for all sufficiently large $N$: at $N=1$, it is impossible since
$\lvert A\cap{1}\rvert\leq 1<\sqrt{2}$.