Logo
All Random Solved Random Open
7 solved out of 27 shown (show only solved or open)
OPEN
Let $A$ be the set of all integers not of the form $p+2^{k}+2^l$ (where $k,l\geq 0$ and $p$ is prime). Is the upper density of $A$ positive?
Crocker [Cr71] has proved there are are $\gg\log\log N$ such integers in $\{1,\ldots,N\}$. Pan [Pa11] improved this to $\gg_\epsilon N^{1-\epsilon}$ for any $\epsilon>0$. Erdős believed this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.

The sequence of such numbers is A006286 in the OEIS.

See also [10], [11], and [16].

Additional thanks to: Ralf Stephan
OPEN
Is there some $k$ such that every integer is the sum of a prime and at most $k$ powers of 2?
Erdős described this as 'probably unattackable'. In [ErGr80] Erdős and Graham suggest that no such $k$ exists. Gallagher [Ga75] has shown that for any $\epsilon>0$ there exists $k(\epsilon)$ such that the set of integers which are the sum of a prime and at most $k(\epsilon)$ many powers of 2 has lower density at least $1-\epsilon$.

Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of 2 suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers. (The restriction to odd integers is important here - for example, Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ (see [9]) suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).

See also [9], [11], and [16].

Additional thanks to: Bogdan Grechuk
OPEN
Is every odd $n$ the sum of a squarefree number and a power of 2?
Odlyzko has checked this up to $10^7$. Hercher [He24b] has verified this is true for all odd integers up to $2^{50}\approx 1.12\times 10^{15}$.

Granville and Soundararajan [GrSo98] have proved that this is very related to the problem of finding primes $p$ for which $2^p\equiv 2\pmod{p^2}$ (for example this conjecture implies there are infinitely many such $p$).

Erdős often asked this under the weaker assumption that $n$ is not divisible by $4$. Erdős thought that proving this with two powers of 2 is perhaps easy, and could prove that it is true (with a single power of two) for almost all $n$.

See also [9], [10], and [16].

Additional thanks to: Milos
SOLVED
Is the set of odd integers not of the form $2^k+p$ the union of an infinite arithmetic progression and a set of density $0$?
Erdős called this conjecture 'rather silly'. Using covering congruences Erdős [Er50] proved that the set of such odd integers contains an infinite arithmetic progression.

Chen [Ch23] has proved the answer is no.

See also [9], [10], and [11].

OPEN - $500
If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.
Conjectured by Erdős and Turán. They also suggest the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$.

Another stronger conjecture would be that the hypothesis $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ suffices.

Erdős and Sárközy conjectured the stronger version that if $A=\{a_1<a_2<\cdots\}$ and $B=\{b_1<b_2<\cdots\}$ with $a_n/b_n\to 1$ are such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.

See also [40].

SOLVED - $100
Is there an explicit construction of a set $A\subseteq \mathbb{N}$ such that $A+A=\mathbb{N}$ but $1_A\ast 1_A(n)=o(n^\epsilon)$ for every $\epsilon>0$?
The existence of such a set was asked by Sidon to Erdős in 1932. Erdős (eventually) proved the existence of such a set using probabilistic methods. This problem asks for a constructive solution.

An explicit construction was given by Jain, Pham, Sawhney, and Zakharov [JPSZ24].

SOLVED
Given any infinite set $A\subset \mathbb{N}$ there is a set $B$ of density $0$ such that $A+B$ contains all except finitely many integers.
Conjectured by Erdős and Straus. Proved by Lorentz [Lo54].
OPEN
Is there a set $A\subset\mathbb{N}$ such that \[\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)\] and such that every large integer can be written as $p+a$ for some prime $p$ and $a\in A$?

Can the bound $O(\log N)$ be achieved? Must such an $A$ satisfy \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?\]

Such a set is called an additive complement to the primes.

Erdős [Er54] proved that such a set $A$ exists with $\lvert A\cap\{1,\ldots,N\}\rvert\ll (\log N)^2$ (improving a previous result of Lorentz [Lo54] who achieved $\ll (\log N)^3$). Wolke [Wo96] has shown that such a bound is almost true, in that we can achieve $\ll (\log N)^{1+o(1)}$ if we only ask for almost all integers to be representable.

The answer to the third question is yes: Ruzsa [Ru98c] has shown that we must have \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}\geq e^\gamma\approx 1.781.\]

OPEN
Let $A\subset\mathbb{N}$ be such that every large integer can be written as $n^2+a$ for some $a\in A$ and $n\geq 0$. What is the smallest possible value of \[\limsup \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}?\]
Erdős observed that this value is finite and $>1$.
Additional thanks to: Timothy Gowers
SOLVED
Let $B\subseteq\mathbb{N}$ be an additive basis of order $k$ with $0\in B$. Is it true that for every $A\subseteq\mathbb{N}$ we have \[d_s(A+B)\geq \alpha+\frac{\alpha(1-\alpha)}{k},\] where $\alpha=d_s(A)$ and \[d_s(A) = \inf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N}\] is the Schnirelmann density?
Erdős [Er36c] proved this is true with $k$ replaced by $2k$ in the denominator (in a stronger form that only considers $A\cup (A+b)$ for some $b\in B$, see [38]).

Ruzsa has observed that this follows immediately from the stronger fact proved by Plünnecke [Pl70] that (under the same assumptions) \[d_S(A+B)\geq \alpha^{1-1/k}.\]

Additional thanks to: Imre Ruzsa
OPEN - $500
For what functions $g(N)\to \infty$ is it true that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}g(N)\] implies $\limsup 1_A\ast 1_A(n)=\infty$?
It is possible that this is true even with $g(N)=O(1)$, from which the Erdős-Turán conjecture [28] would follow.
OPEN - $500
Is there $A\subseteq \mathbb{N}$ such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is $\neq 0$?
A suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set. Erdős believed the answer should be no. Erdős and Sárkzözy proved that \[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\] is impossible. Erdős suggests it may even be true that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ are always separated by some absolute constant.
SOLVED
Is there a set $A\subset\mathbb{N}$ such that, for all large $N$, \[\lvert A\cap\{1,\ldots,N\}\rvert \ll N/\log N\] and such that every large integer can be written as $2^k+a$ for some $k\geq 0$ and $a\in A$?
Lorentz [Lo54] proved there is such a set with, for all large $N$, \[\lvert A\cap\{1,\ldots,N\}\rvert \ll \frac{\log\log N}{\log N}N\] The answer is yes, proved by Ruzsa [Ru72]. Ruzsa's construction is ingeniously simple: \[A = \{ 5^nm : m\geq 1\textrm{ and }5^n\geq C\log m\}+\{0,1\}\] for some large absolute constant $C>0$. That every large integer is of the form $2^k+a$ for some $a\in A$ is a consequence of the fact that $2$ is a primitive root of $5^n$ for all $n\geq 1$.

In [Ru01] Ruzsa constructs an asymptotically best possible answer to this question (a so-called 'exact additive complement'); that is, there is such a set $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert \sim \frac{N}{\log_2N}\] as $N\to \infty$.

OPEN
Let $A\subset \mathbb{N}$ be an additive basis of order $2$. Must there exist $B=\{b_1<b_2<\cdots\}\subseteq A$ which is also a basis such that \[\lim_{k\to \infty}\frac{b_k}{k^2}\] does not exist?
Erdős originally asked whether this was true with $A=B$, but this was disproved by Cassels [Ca57].
OPEN
Suppose $A\subset\mathbb{N}$ is a minimal basis with positive density. Is it true that, for any $n\in A$, the (upper) density of integers which cannot be represented without using $n$ is positive?
Asked by Erdős and Nathanson.
OPEN
Let $A\subseteq \mathbb{N}$ be a set of density zero. Does there exist a basis $B$ such that $A\subseteq B+B$ and \[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\] for all large $N$?
Erdős and Newman [ErNe77] have proved this is true when $A$ is the set of squares.

See also [806].

OPEN
For $r\geq 2$ let $h(r)$ be the maximal finite $k$ such that there exists a basis $A\subseteq \mathbb{N}$ of order $r$ (so every large integer is the sum of at most $r$ integers from $A$) and exact order $k$ (i.e. $k$ is minimal such that every large integer is the sum of exactly $k$ integers from $A$). Find the value of \[\lim_r \frac{h(r)}{r^2}.\]
Erdős and Graham [ErGr80b] have shown that a basis $A$ has an exact order if and only if $a_2-a_1,a_3-a_2,a_4-a_3,\ldots$ are coprime. They also prove that \[\frac{1}{4}\leq \lim_r \frac{h(r)}{r^2}\leq \frac{5}{4}.\] It is known that $h(2)=4$, but even $h(3)$ is unknown (it is $\geq 7$).
Additional thanks to: Zachary Hunter
SOLVED
Let $A\subseteq \mathbb{N}$ be an additive basis (of any finite order) such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that \[\lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty?\]
The answer is no, and a counterexample was provided by Turjányi [Tu84]. This was generalised (to the replacement of $A+A$ by the $h$-fold sumset $hA$ for any $h\geq 2$) by Ruzsa and Turjányi [RT85]. Ruzsa and Turjányi do prove (under the same hypotheses) that \[\lim_{N\to \infty}\frac{\lvert (A+A+A)\cap \{1,\ldots,3N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty,\] and conjecture that the same should be true with $(A+A)\cap \{1,\ldots,2N\}$ in the numerator.
Additional thanks to: Zachary Chase, Zach Hunter
OPEN
The restricted order of a basis is the least integer $t$ (if it exists) such that every large integer is the sum of at most $t$ distinct summands from $A$. What are necessary and sufficient conditions that this exists? Can it be bounded (when it exists) in terms of the order of the basis? What are necessary and sufficient conditions that this is equal to the order of the basis?
Bateman has observed that for $h\geq 3$ there is a basis of order $h$ with no restricted order, taking \[A=\{1\}\cup \{x>0 : h\mid x\}.\] Kelly [Ke57] has shown that any basis of order $2$ has restricted order at most $4$ and conjectured it always has restricted order at most $3$ (which he proved under the additional assumption that the basis has positive lower density). Kelly's conjecture was disproved by Hennecart [He05], who constructed a basis of order $2$ with restricted order $4$.

The set of squares has order $4$ and restricted order $5$ (see [Pa33]) and the set of triangular numbers has order $3$ and restricted order $3$ (see [Sc54]).

Is it true that if $A\backslash F$ is a basis for all finite sets $F$ then $A$ must have a restricted order? What if they are all bases of the same order?

Hegyvári, Hennecart, and Plagne [HHP07] have shown that for all $k\geq2$ there exists a basis of order $k$ which has restricted order at least \[2^{k-2}+k-1.\]

Additional thanks to: Euro Sampaio
OPEN
Let $A\subseteq \mathbb{N}$ be a basis of order $r$. Must the set of integers representable as the sum of exactly $r$ distinct elements from $A$ have positive density?
OPEN
Is there a sequence $A=\{1\leq a_1<a_2<\cdots\}$ such that every large integer is the sum of at least two consecutive elements of $A$? Can the number of representations of $n$ in this form tend to infinity with $n$?
Erdős and Moser [Mo63] considered the case when $A$ is the set of primes, and conjectured that the $\limsup$ of the number of such representations in this case is infinite. They could not even prove that the upper density of the set of integers representable in this form is positive.

In [ErGr80] this was asked without the 'at least two' restriction, but otherwise the answer is trivially yes, as observed by Egami, since one can take $a_n=n$.

Additional thanks to: Stijn Cambie and Hayato Egami
OPEN
If $A$ is an additive basis order $2$, and $1_A\ast 1_A(n)\to \infty$ as $n\to \infty$, then must $A$ contain a minimal additive basis of order $2$? (i.e. such that deleting any element creates infinitely many $n\not\in A+A$)

What if $1_A\ast 1_A(n) >\epsilon \log n$ (for all large $n$, for arbitrary fixed $\epsilon>0$)?

A question of Erdős and Nathanson [ErNa79], who proved that this is true if $1_A\ast 1_A(n) > (\log \frac{4}{3})^{-1}\log n$ for all large $n$.

Härtter [Ha56] and Nathanson [Na74] proved that there exist additive bases which do not contain any minimal additive bases.

See also [870].

OPEN
If $A_1,A_2$ are disjoint additive bases of order $2$ (i.e. $A_i+A_i$ contains all large integers) then must $A=A_1\cup A_2$ contain a minimal additive basis of order $2$ (one such that deleting any element creates infinitely many $n\not\in A+A$)?
A question of Erdős and Nathanson [ErNa88].

Härtter [Ha56] and Nathanson [Na74] proved that there exist additive bases which do not contain any minimal additive bases.

OPEN
Let $k\geq 3$ and $A$ be an additive basis of order $k$. Does there exist a constant $c=c(k)>0$ such that if $r(n)\geq c\log n$ for all large $n$ then $A$ must contain a minimal basis of order $k$? (Here $r(n)$ counts the number of representations of $n$ as the sum of at most $k$ elements from $A$.)
A question of Erdős and Nathanson [ErNa79], who proved that this is true for $k=2$ if $1_A\ast 1_A(n) > (\log \frac{4}{3})^{-1}\log n$ for all large $n$.

Härtter [Ha56] and Nathanson [Na74] proved that there exist additive bases which do not contain any minimal additive bases.

See also [868].

OPEN
Let $A$ be an additive basis of order $2$, and suppose $1_A\ast 1_A(n)\to \infty$ as $n\to \infty$. Can $A$ be partitioned into two disjoint additive bases of order $2$?
A question of Erdős and Nathanson [ErNa88], who proved this is true if $1_A\ast 1_A(n) > (\log\frac{4}{3})^{-1}\log n$ (for all large $n$).
SOLVED
Let $A\subset\mathbb{N}$ be an additive basis of order $k$. Let $B=\{b_1<b_2<\cdots\}$ be the set of integers which are the sum of $k$ or fewer distinct $a\in A$. Is it true that $b_{n+1}-b_n=O(1)$? (Where the implied constant may depend on both $A$ and $k$.)
A problem of Burr and Erdős.

Hegyvári, Hennecart, and Plagne [HHP07] showed the answer is yes for $k=2$ (in fact with $b_{n+1}-b_n\leq 2$ for large $n$) but no for $k\geq 3$.

The proof that $b_{n+1}-b_n\leq 2$ for $k=2$ is trivial, since clearly all odd numbers in $A+A$ must be the sum of two distinct elements from $A$.

Additional thanks to: Euro Sampaio
OPEN
Let $A\subset\mathbb{N}$ be an additive basis of order $k$ which is minimal, in the sense that if $B\subset A$ is any infinite set then $A\backslash B$ is not a basis of order $k$.

Must there exist an infinite $B\subset A$ such that $A\backslash B$ is a basis of order $k+1$?