Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
Is the upper density of the set of odd numbers that cannot be expressed as a prime plus two powers of 2 positive?
Is there some \(k\) such that every large integer is the sum of a prime and at most \(k\) powers of \(2\)?
Is every large odd integer \(n\) the sum of a squarefree number and a power of 2?
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". Chen [Ch23] has proved the answer is no. This was formalized in…
If \(A ⊆ \mathbb{N}\) is such that \(A + A\) contains all but finitely many integers then \(\limsup 1_A ∗ 1_A(n) = \infty\).
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…
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].
Does there exist a set \(A \subseteq \mathbb{N}\) such that \(|A \cap \{1, \ldots, N\}| = o((\log N)^2)\) and every sufficiently large integer can be written as \(p + a\) for some prime \(p\) and \(a \in A\)?
Let A ⊆ ℕ be a set such that every integer can be written as n^2 + a for some a in A and n ≥ 0. -/ -- Formalisation note: Changed 'every large integer' to 'every integer' as for the statement these -- conditions are equivalent. Also, this…
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…
For what functions \(g(N) → \infty\) is it true that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg \frac{N^{1/2}}{g(N)}\] implies \(\limsup 1_A\ast 1_A(n)=\infty\)?
Is there and \(A \subset \mathbb{N}\) is such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is \(\ne 0\)?
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]…
Does there exist \(A = \{a_1 < a_2 < \cdots\} \subset \mathbb{N}\) which is a minimal basis of order \(2\) (i.e. every large integer is the sum of \(2\) elements from \(A\), and no proper subset of \(A\) has this property), such that…
Does there exist a minimal basis \(A \subset \mathbb{N}\) with positive density such that, for any \(n \in A\), the (upper) density of integers which cannot be represented without using \(n\) is positive? Neither set is asked to have a…
Let \(A\subseteq \mathbb{N}\) be a set of density zero. Does there exist a \(B\) such that \(A\subseteq B+B\) and \[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\] for all large \(N\)? The answer is no. Erdős and Newman [ErNe77] have…
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…
The restricted order of a basis \(A\) 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? A…
Let \(A=\{a_1 < \cdots\}\) be an infinite sequence of integers. Let \(f(n)\) count the number of solutions to \[n=\sum_{u\leq i\leq v}a_i.\] Is there such an \(A\) for which \(f(n)\to \infty\) as \(n\to \infty\)? Tao [Ta26] constructed…
Let \(A\) be an additive basis of order \(2\), let \(f(n)\) denote the number of ways in which \(n\) can be written as the sum of two elements from \(A\). If \(f(n) \to \infty\) as \(n \to \infty\), then must \(A\) contain a minimal…
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…
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…
Let A ⊂ ℕ be an additive basis of order k which is minimal in the sense that if B ⊂ A is any infinite set, then A \ B is not a basis of order k. Must there exist an infinite B ⊂ A such that A \ B is an additive basis of order k + 1?
Let \(A=\{1\leq a_1 < a_2 < \cdots\}\) and \(B=\{1\leq b_1 < b_2 < \cdots\}\) be sets of integers with \(a_n/b_n\to 1\). If \(A+B\) contains all sufficiently large positive integers then is it true that \(\limsup 1_A\ast 1_B(n)=\infty\)? A…
Let \(\alpha>0\) be an irrational number. Is the set \[A=\left\{ n\geq 1: \| \alpha n^2\| < \frac{1}{\log n}\right\},\] where \(\|\cdot\|\) denotes the distance to the nearest integer, an additive basis of order \(2\)? This was disproved…
Does there exist, for all \(r\geq 2\), a basis \(A\) of order \(r\) (so that \(f_r(n)>0\) for all large \(n\)) such that \[\sum_{n\leq x}f_r(n)^2 \ll x\] for all \(x\)?