Erdős Problems

1,217 source-owned questions · 604 with a formal statement · searchable by statement, number, topic and source status.

Add a contribution Collection details

Collection coverage

Source status, exact formal material, and reviewed Results are separate signals.

Open per source608
Resolved per source556
Other source status53

Exact formal statement available604 / 1,217

With Repository-reviewed evidence2 / 1,217

102 Problems

1/3

Number	Question	Source says	Formal	Result here
#1	If $A\subseteq\{1, ..., N\}$ with $\|A\| = n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then $N \gg 2 ^ n.$ openFormalized	open	In Lean	No Result decision
#3	If $A \subset \mathbb{N}$ has $\sum_{n \in A}\frac 1 n = \infty$ , then must A contain arbitrarily long arithmetic progressions?openFormalized	open	In Lean	No Result decision
#14	Let $A ⊆ \mathbb{N}$ . Let $B ⊆ \mathbb{N}$ be the set of integers which are representable in exactly one way as the sum of two elements from $A$ . Is it true that for all $\epsilon > 0$ and large $N$ , $\|\{1,\ldots,N\} \setminus B\| \gg_\epsilon N^{1/2 - \epsilon}$ ?openFormalized	open	In Lean	No Result decision
#30	Is it true that, for every $\varepsilon > 0$ , h(N) $= \sqrt N + O_{\varespilon}(N^\varespilon$ )openFormalized	open	In Lean	No Result decision
#36	For `n = 5` the best splitting of `{1, …, 10}` has maximum overlap `3`.openFormalized	open	In Lean	No Result decision
#37	No statement retained — open to read what the source holdsdisprovedNo formal declaration	disproved	No formal statement	No Result decision
#39	Is there an infinite Sidon set $A\subset \mathbb{N}$ such that $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ for all $\varepsilon > 0$ ?openFormalized	open	In Lean	No Result decision
#41	Let `A ⊆ ℕ` be an infinite set such that the triple sums `a + b + c` are all distinct for `a, b, c` in `A` (aside from the trivial coincidences). Is it true that `liminf n → ∞ \|A ∩ {1, …, N}\| / N^(1/3) = 0`?openFormalized	open	In Lean	No Result decision
#42	Erdős Problem 42: Let M ≥ 1 and N be sufficiently large in terms of M. Is it true that for every maximal Sidon set `A ⊆ {1,…,N}` there is another Sidon set `B ⊆ {1,…,N}` of size M such that `(A - A) ∩ (B - B) = {0}`?solved (Lean)Formalized	solved (Lean)	In Lean	No Result decision
#43	If $A$ and $B$ are Sidon sets in $\{1,\ldots,N\}$ with $(A-A)\cap(B-B)=\{0\}$ , is it true that $\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?$ disprovedFormalized	disproved	In Lean	No Result decision
#44	Erdős Problem 44: Let N ≥ 1 and `A ⊆ {1,…,N}` be a Sidon set. Is it true that, for any ε > 0, there exist M = M(ε) and `B ⊆ {N+1,…,M}` such that `A ∪ B ⊆ {1,…,M}` is a Sidon set of size at least `(1−ε)M^{1/2}`?openFormalized	open	In Lean	No Result decision
#52	Let $A$ be a finite set of integers. Is it true that for every $\epsilon>0$ $\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?$ openFormalized	open	In Lean	No Result decision
#53	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#109	Any $A\subseteq \mathbb{N}$ of positive upper density contains a sumset $B+C$ where both $B$ and $C$ are infinite.provedFormalized	proved	In Lean	No Result decision
#138	In [Er80] Erdős asks whether $\lim_{k \to \infty} (W(k))^{1/k} = \infty$ openFormalized	open	In Lean	No Result decision
#139	Erdős Problem 139: Let $r_k(N)$ be the size of the largest subset of ${1,...,N}$ which does not contain a non-trivial $k$ -term arithmetic progression. Prove that $r_k(N) = o(N)$ .provedFormalized	proved	In Lean	No Result decision
#140	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#141	Let $k≥3$ . Are there $k$ consecutive primes in arithmetic progression?openFormalized	open	In Lean	No Result decision
#142	Prove an asymptotic formula for $r_k(N)$ , the largest possible size of a subset of $\{1, \dots, N\}$ that does not contain any non-trivial $k$ -term arithmetic progression.openFormalized	open	In Lean	No Result decision
#155	Is it true that for every $k \geq 1$ we have $F(N + k) \leq F(N) + 1$ for all sufficiently large $N$ ?openFormalized	open	In Lean	No Result decision
#160	Estimate $h(n)$ by finding a better lower bound.openFormalized	open	In Lean	No Result decision
#168	Sanity check: if `S` is a maximal non ternary subset of `{1,..., N}` then `F N` is given by the cardinality of `S`openFormalized	open	In Lean	No Result decision
#169	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#170	The problem is to determine the limit of the sequence $\frac{F(N)}{\sqrt{N}}$ as $N \to \infty$ .openFormalized	open	In Lean	No Result decision
#171	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#172	Is it true that in any finite colouring of $\mathbb{N}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour?openFormalized	open	In Lean	No Result decision
#176	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#179	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#185	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#186	No statement retained — open to read what the source holdssolvedNo formal declaration	solved	No formal statement	No Result decision
#187	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#190	No statement retained — open to read what the source holdssolvedNo formal declaration	solved	No formal statement	No Result decision
#198	The statement for which Baumgartner actually writes a proof.disproved (Lean)Formalized	disproved (Lean)	In Lean	No Result decision
#201	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#219	Are there arbitrarily long arithmetic progressions of primes? Solution: yes. Ref: Green, Ben and Tao, Terence, _The primes contain arbitrarily long arithmetic progressions_provedFormalized	proved	In Lean	No Result decision
#241	Is it true that $f(N)\sim N^{1/3}$ ?openFormalized	open	In Lean	No Result decision
#245	Let $A\subseteq\mathbb{N}$ be an infinite set such that $\|A\cap \{1, ..., N\}\| = o(N)$ . Is it true that $\limsup_{N\to\infty}\frac{\|(A + A)\cap \{1, ..., N\}\|}{\|A \cap \{1, ..., N\}\|} \geq 3?$ provedFormalized	proved	In Lean	No Result decision
#271	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#272	Let $N\geq 1$ . What is the largest $t$ such that there are $A_1,\ldots,A_t\subseteq \{1,\ldots,N\}$ with $A_i\cap A_j$ a non-empty arithmetic progression for all $i\neq j$ ?openFormalized	open	In Lean	No Result decision
#328	Suppose $A\subseteq\mathbb{N}$ and $C>0$ is such that $1_A\ast 1_A(n)\leq C$ for all $n\in\mathbb{N}$ . Can $A$ be partitioned into $t$ many subsets $A_1,\ldots,A_t$ (where $t=t(C)$ depends only on $C$ ) such that $1_{A_i}\ast 1_{A_i}(n)<C$ for all $1\leq i\leq t$ and $n\in \mathbb{N}$ ?disproved (Lean)Formalized	disproved (Lean)	In Lean	No Result decision
#331	Let $A,B\subseteq \mathbb{N}$ such that for all large $N$ $\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}$ and $\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}.$ Is it true that there are infinitely many solutions to $a_1-a_2=b_1-b_2\neq 0$ with $a_1,a_2\in A$ and $b_1,b_2\in B$ ?disproved (Lean)Formalized	disproved (Lean)	In Lean	No Result decision
#335	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#337	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?$ disproved (Lean)Formalized	disproved (Lean)	In Lean	No Result decision
#340	Let $A = \{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, \ldots\}$ be the greedy Sidon sequence: we begin with $1$ and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions to $a + b = c + d$ ). What is the order of growth of $A$ ? Is it true that $\|A \cap \{1, \ldots, N\}\| \gg N^{1/2 - \varepsilon}$ for all $\varepsilon > 0$ and large $N$ ?openFormalized	open	In Lean	No Result decision
#350	Small sanity check: the two predicates are saying the same thing.proved (Lean)Formalized	proved (Lean)	In Lean	No Result decision
#475	No statement retained — open to read what the source holdsdecidableNo formal declaration	decidable	No formal statement	No Result decision
#476	Let $A\subseteq \mathbb{F}_p$ . Let $A\hat{+}A = \{ a+b : a\neq b \in A\}.$ Is it true that $\lvert A\hat{+}A\rvert \geq \min(2\lvert A\rvert-3,p)?$ proved (Lean)Formalized	proved (Lean)	In Lean	No Result decision
#483	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision

Problems

Search problems.science