Skip to content

Erdős Problems

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

Add a contributionCollection details
Full distribution

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
More filters

Coverage is source-observation coverage, not Problem completeness. Inspect coverage

Problems

102 Problems

1/3

SelectNumberQuestionOpen
#1If A⊆{1,...,N}A\subseteq\{1, ..., N\} with ∣A∣=n|A| = n is such that the subset sums ∑a∈Sa\sum_{a\in S}a are distinct for all S⊆AS\subseteq A then N≫2n. N \gg 2 ^ n. Source says openFormalized
#3If A⊂NA \subset \mathbb{N} has ∑n∈A1n=∞\sum_{n \in A}\frac 1 n = \infty, then must A contain arbitrarily long arithmetic progressions?Source says openFormalized
#14Let A⊆NA ⊆ \mathbb{N}. Let B⊆NB ⊆ \mathbb{N} be the set of integers which are representable in exactly one way as the sum of two elements from AA. Is it true that for all ϵ>0\epsilon > 0 and large NN, ∣{1,…,N}∖B∣≫ϵN1/2−ϵ|\{1,\ldots,N\} \setminus B| \gg_\epsilon N^{1/2 - \epsilon}?Source says openFormalized
#30Is it true that, for every ε>0\varepsilon > 0, h(N) Unparsed notation: = \sqrt N + O_{\varespilon}(N^\varespilon)Source says openFormalized
#36For n = 5 the best splitting of {1, …, 10} has maximum overlap 3.Source says openFormalized
#37No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#39Is there an infinite Sidon set A⊂NA\subset \mathbb{N} such that ∣A∩{1…,N}∣≫ϵN1/2−ϵ\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon} for all ε>0\varepsilon > 0?Source says openFormalized
#41Let 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?Source says openFormalized
#42Erdő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}?Source says solved (Lean)Formalized
#43If AA and BB are Sidon sets in {1,…,N}\{1,\ldots,N\} with (A−A)∩(B−B)={0}(A-A)\cap(B-B)=\{0\}, is it true that (∣A∣2)+(∣B∣2)≤(f(N)2)+O(1)?\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?Source says disprovedFormalized
#44Erdő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}?Source says openFormalized
#52Let AA be a finite set of integers. Is it true that for every ϵ>0\epsilon>0 max⁡(∣A+A∣,∣AA∣)≫ϵ∣A∣2−ϵ?\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?Source says openFormalized
#53No statement retained — open to read what the source holdsSource says provedNo formal declaration
#109Any A⊆NA\subseteq \mathbb{N} of positive upper density contains a sumset B+CB+C where both BB and CC are infinite.Source says provedFormalized
#138In [Er80] Erdős asks whether lim⁡k→∞(W(k))1/k=∞ \lim_{k \to \infty} (W(k))^{1/k} = \infty Source says openFormalized
#139Erdős Problem 139: Let rk(N)r_k(N) be the size of the largest subset of 1,...,N{1,...,N} which does not contain a non-trivial kk-term arithmetic progression. Prove that rk(N)=o(N)r_k(N) = o(N).Source says provedFormalized
#140No statement retained — open to read what the source holdsSource says provedNo formal declaration
#141Let k≥3k≥3. Are there kk consecutive primes in arithmetic progression?Source says openFormalized
#142Prove an asymptotic formula for rk(N)r_k(N), the largest possible size of a subset of {1,…,N}\{1, \dots, N\} that does not contain any non-trivial kk-term arithmetic progression.Source says openFormalized
#155Is it true that for every k≥1k \geq 1 we have F(N+k)≤F(N)+1 F(N + k) \leq F(N) + 1 for all sufficiently large NN?Source says openFormalized
#160Estimate h(n)h(n) by finding a better lower bound.Source says openFormalized
#168Sanity check: if S is a maximal non ternary subset of {1,..., N} then F N is given by the cardinality of SSource says openFormalized
#169No statement retained — open to read what the source holdsSource says openNo formal declaration
#170The problem is to determine the limit of the sequence F(N)N\frac{F(N)}{\sqrt{N}} as N→∞N \to \infty.Source says openFormalized
#171No statement retained — open to read what the source holdsSource says provedNo formal declaration
#172Is it true that in any finite colouring of N\mathbb{N} there exist arbitrarily large finite AA such that all sums and products of distinct elements in AA are the same colour?Source says openFormalized
#176No statement retained — open to read what the source holdsSource says openNo formal declaration
#179No statement retained — open to read what the source holdsSource says provedNo formal declaration
#185No statement retained — open to read what the source holdsSource says provedNo formal declaration
#186No statement retained — open to read what the source holdsSource says solvedNo formal declaration
#187No statement retained — open to read what the source holdsSource says openNo formal declaration
#190No statement retained — open to read what the source holdsSource says solvedNo formal declaration
#198The statement for which Baumgartner actually writes a proof.Source says disproved (Lean)Formalized
#201No statement retained — open to read what the source holdsSource says openNo formal declaration
#219Are there arbitrarily long arithmetic progressions of primes? Solution: yes. Ref: Green, Ben and Tao, Terence, _The primes contain arbitrarily long arithmetic progressions_Source says provedFormalized
#241Is it true that f(N)∼N1/3f(N)\sim N^{1/3}?Source says openFormalized
#245Let A⊆NA\subseteq\mathbb{N} be an infinite set such that ∣A∩{1,...,N}∣=o(N)|A\cap \{1, ..., N\}| = o(N). Is it true that lim sup⁡N→∞∣(A+A)∩{1,...,N}∣∣A∩{1,...,N}∣≥3? \limsup_{N\to\infty}\frac{|(A + A)\cap \{1, ..., N\}|}{|A \cap \{1, ..., N\}|} \geq 3? Source says provedFormalized
#271No statement retained — open to read what the source holdsSource says openNo formal declaration
#272Let N≥1N\geq 1. What is the largest tt such that there are A1,…,At⊆{1,…,N}A_1,\ldots,A_t\subseteq \{1,\ldots,N\} with Ai∩AjA_i\cap A_j a non-empty arithmetic progression for all i≠ji\neq j?Source says openFormalized
#328Suppose A⊆NA\subseteq\mathbb{N} and C>0C>0 is such that 1A∗1A(n)≤C1_A\ast 1_A(n)\leq C for all n∈Nn\in\mathbb{N}. Can AA be partitioned into tt many subsets A1,…,AtA_1,\ldots,A_t (where t=t(C)t=t(C) depends only on CC) such that 1Ai∗1Ai(n)<C1_{A_i}\ast 1_{A_i}(n)<C for all 1≤i≤t1\leq i\leq t and n∈Nn\in \mathbb{N}?Source says disproved (Lean)Formalized
#331Let A,B⊆NA,B\subseteq \mathbb{N} such that for all large NN∣A∩{1,…,N}∣≫N1/2\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}and∣B∩{1,…,N}∣≫N1/2.\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}. Is it true that there are infinitely many solutions to a1−a2=b1−b2≠0a_1-a_2=b_1-b_2\neq 0 with a1,a2∈Aa_1,a_2\in A and b1,b2∈Bb_1,b_2\in B?Source says disproved (Lean)Formalized
#335No statement retained — open to read what the source holdsSource says openNo formal declaration
#337Let A⊆NA\subseteq \mathbb{N} be an additive basis (of any finite order) such that ∣A∩{1,…,N}∣=o(N)\lvert A\cap \{1,\ldots,N\}\rvert=o(N). Is it true that lim⁡N→∞∣(A+A)∩{1,…,N}∣∣A∩{1,…,N}∣=∞? \lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert} {\lvert A\cap \{1,\ldots,N\}\rvert}=\infty? Source says disproved (Lean)Formalized
#340Let A={1,2,4,8,13,21,31,45,66,81,97,…}A = \{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, \ldots\} be the greedy Sidon sequence: we begin with 11 and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions to a+b=c+da + b = c + d). What is the order of growth of AA? Is it true that ∣A∩{1,…,N}∣≫N1/2−ε|A \cap \{1, \ldots, N\}| \gg N^{1/2 - \varepsilon} for all ε>0\varepsilon > 0 and large NN?Source says openFormalized
#350Small sanity check: the two predicates are saying the same thing.Source says proved (Lean)Formalized
#475No statement retained — open to read what the source holdsSource says decidableNo formal declaration
#476Let A⊆FpA\subseteq \mathbb{F}_p. Let A+^A={a+b:a≠b∈A}. A\hat{+}A = \{ a+b : a\neq b \in A\}. Is it true that ∣A+^A∣≥min⁡(2∣A∣−3,p)? \lvert A\hat{+}A\rvert \geq \min(2\lvert A\rvert-3,p)? Source says proved (Lean)Formalized
#483No statement retained — open to read what the source holdsSource says openNo formal declaration