SOLVED

If $A\subseteq \mathbb{N}$ is a multiset of integers such that
\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N\]
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?

A problem of Folkman. Folkman [Fo66] showed that this is true if
\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1+\epsilon}\]
for some $\epsilon>0$ and all $N$.

The original question was answered by Szemerédi and Vu [SzVu06] (who proved that the answer is yes).

This is best possible, since Folkman [Fo66] showed that for all $\epsilon>0$ there exists a multiset $A$ with \[\lvert A\cap \{1,\ldots,N\}\rvert\ll N^{1+\epsilon}\] for all $N$, such that $A$ is not subcomplete.

SOLVED

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?

Folkman proved this under the stronger assumption that
\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2+\epsilon}\]
for some $\epsilon>0$.

This is true, and was proved by Szemerédi and Vu [SzVu06]. 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].

OPEN

Let $A\subseteq \mathbb{N}$ be a complete sequence, and define the threshold of completeness $T(A)$ to be the least integer $m$ such that all $n\geq m$ are in
\[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\]
(the existence of $T(A)$ is guaranteed by completeness).

Is it true that there are infinitely many $k$ such that $T(n^k)>T(n^{k+1})$?

Erdős and Graham [ErGr80] remark that very little is known about $T(A)$ in general. It is known that
\[T(n)=1, T(n^2)=128, T(n^3)=12758,\]
\[T(n^4)=5134240,\textrm{ and }T(n^5)=67898771.\]
Erdős and Graham remark that a good candidate for the $n$ in the question are $k=2^t$ for large $t$, perhaps even $t=3$, because of the highly restricted values of $n^{2^t}$ modulo $2^{t+1}$.

OPEN

Let $A=\{a_1< a_2<\cdots\}$ be a set of integers such that

- $A\backslash B$ is complete for any finite subset $B$ and
- $A\backslash B$ is not complete for any infinite subset $B$.

Graham [Gr64d] has shown that the sequence $a_n=F_n-(-1)^{n}$, where $F_n$ is the $n$th Fibonacci number, has these properties. Erdős and Graham [ErGr80] remark that it is easy to see that if $a_{n+1}/a_n>\frac{1+\sqrt{5}}{2}$ then the second property is automatically satisfied, and that it is not hard to construct very irregular sequences satisfying both properties.

OPEN

For what values of $0\leq m<n$ is there a complete sequence $A=\{a_1\leq a_2\leq \cdots\}$ of integers such that

- $A$ remains complete after removing any $m$ elements, but
- $A$ is not complete after removing any $n$ elements?

The Fibonacci sequence $1,1,2,3,5,\ldots$ shows that $m=1$ and $n=2$ is possible. The sequence of powers of $2$ shows that $m=0$ and $n=1$ is possible. The case $m=2$ and $n=3$ is not known.

OPEN

For what values of $t,\alpha \in (0,\infty)$ is the sequence $\lfloor t\alpha^n\rfloor$ complete?

Even in the range $t\in (0,1)$ and $\alpha\in (1,2)$ the behaviour is surprisingly complex. For example, Graham [Gr64e] has shown that for any $k$ there exists some $t_k\in (0,1)$ such that the set of $\alpha$ such that the sequence is complete consists of at least $k$ disjoint line segments. It seems likely that the sequence is complete for all $t>0$ and all $1<\alpha < \frac{1+\sqrt{5}}{2}$. Proving this seems very difficult, since we do not even known whether $\lfloor (3/2)^n\rfloor$ is odd or even infinitely often.

OPEN

Let $p(x)\in \mathbb{Q}[x]$. Is it true that
\[A=\{ p(n)+1/n : n\in \mathbb{N}\}\]
is strongly complete, in the sense that, for any finite set $B$,
\[\left\{\sum_{n\in X}n : X\subseteq A\backslash B\textrm{ finite }\right\}\]
contains all sufficiently large rational numbers?

Graham [Gr64f] proved this is true when $p(n)=n$. Erdős and Graham also ask which rational functions $r(x)\in\mathbb{Z}[x]$ force $\{ r(n) : n\in\mathbb{N}\}$ to be complete?