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
Collection coverage

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

1,217 Problems · 2 with reviewed evidence

1/26

NumberQuestionOpen
#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. openFormalized
#2No statement retained — open to read what the source holdsdisprovedNo formal declaration
#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?openFormalized
#4Is it true that, for any C>0C > 0, there infinitely many nn such that: pn+1−pn>Clog⁡log⁡nlog⁡log⁡log⁡log⁡n(log⁡log⁡log⁡n)2log⁡n p_{n + 1} - p_n > C \frac{\log\log n\log\log\log\log n}{(\log\log\log n) ^ 2}\log n provedFormalized
#5No statement retained — open to read what the source holdsopenNo formal declaration
#6There are infinitely many nn such that dn<dn+1<dn+2d_n < d_{n+1} < d_{n+2}, where dd denotes the prime gap function.provedFormalized
#7Is there a covering system all of whose moduli are odd (and greater than 1)?verifiableFormalized
#8No statement retained — open to read what the source holdsdisprovedNo formal declaration
#9Is the upper density of the set of odd numbers that cannot be expressed as a prime plus two powers of 2 positive?openFormalized
#10Is there some kk such that every integer is the sum of a prime and at most kk powers of 22?openFormalized
#11Is every odd n>1n > 1 the sum of a squarefree number and a power of 2?openFormalized
#12The set of p2p ^ 2 where p≅3mod  4p \cong 3 \mod 4 is prime is an example of a good set. Formal proof provided by AlphaProofopenFormalized
#13If A⊆{1,...,N}A \subseteq \{1, ..., N\} is a set with no a,b,c∈Aa, b, c \in A such that a∣(b+c)a | (b+c) and a<min⁡(b,c)a < \min(b,c), then ∣A∣≤N/3+O(1)|A| \le N/3 + O(1). This has been solved by Bedert [Be23].provedFormalized
#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}?openFormalized
#15Is it true that ∑n=1∞(−1)nnpn\sum_{n=1}^\infty(-1)^n\frac{n}{p_n} converges, where pnp_n is the sequence of primes?openFormalized
#16Is the set of odd integers not of the form 2k+p2^k+p the union of an infinite arithmetic progression and a set of density 00?disproved (Lean)Formalized
#17Erdős Problem 17. Are there infinitely many cluster primes?openFormalized
#18Erdős's Theorem. Erdős proved that h(n!)<nh(n!) < n for all n≥1n \ge 1.openFormalized
#19No statement retained — open to read what the source holdsdecidableNo formal declaration
#20Is it true that f(n,k)<cknf(n,k) < c_k^n for some constant ck>0c_k>0 and for all n>0n > 0?openFormalized
#21No statement retained — open to read what the source holdsprovedNo formal declaration
#22Let ϵ>0\epsilon > 0 and let nn be sufficiently large depending on ϵ\epsilon. Is there a graph on nn vertices with at least n2/8n^2/8 many edges which contains no K4K_4, such that the largest independent set has size at most ϵn\epsilon n?provedFormalized
#23The blow-up of C5C_5 shows that the bound n2n^2 in Erdős Problem 23 is tight: any bipartite subgraph must omit at least n2n^2 edges.falsifiableFormalized
#24Does every triangle-free graph on 5n5n vertices contain at most n5n^5 copies of C5C_5?proved (Lean)Formalized
#25Let n1<n2<…n_1 < n_2 < \dots be an arbitrary sequence of integers, each with an associated residue class ai(modni)a_i \pmod{n_i}. Let AA be the set of integers nn such that for every ii either n<nin < n_i or n≢ai(modni)n \not\equiv a_i \pmod{n_i}. Must the logarithmic density of AA exist?openFormalized
#26Let A⊂NA\subset\mathbb{N} be infinite such that ∑a∈A1a=∞\sum_{a \in A} \frac{1}{a} = \infty. Must there exist some k≥1k\geq 1 such that almost all integers have a divisor of the form a+ka+k for some a∈Aa\in A?disproved (Lean)Formalized
#27No statement retained — open to read what the source holdsdisprovedNo formal declaration
#28If A⊆NA ⊆ \mathbb{N} is such that A+AA + A contains all but finitely many integers then lim sup⁡1A∗1A(n)=∞\limsup 1_A ∗ 1_A(n) = \infty.openFormalized
#29No statement retained — open to read what the source holdsprovedNo formal declaration
#30Is it true that, for every ε>0\varepsilon > 0, h(N) =N+O\varespilon(N\varespilon= \sqrt N + O_{\varespilon}(N^\varespilon)openFormalized
#31Given any infinite set A⊂NA\subset \mathbb{N} there is a set BB of density 00 such that A+BA+B contains all except finitely many integers.proved (Lean)Formalized
#32Does there exist a set A⊆NA \subseteq \mathbb{N} such that ∣A∩{1,…,N}∣=o((log⁡N)2)|A \cap \{1, \ldots, N\}| = o((\log N)^2) and every sufficiently large integer can be written as p+ap + a for some prime pp and a∈Aa \in A?openFormalized
#33Let A ⊆ ℕ be a set such that every integer can be written as n^2 + a for some a in A and n ≥ 0. What is the smallest possible value of lim sup n → ∞ |A ∩ {1, …, N}| / N^(1/2)?openFormalized
#34For any permutation π∈Sn\pi\in S_n of {1,…,n}\{1,\ldots,n\} let S(π)S(\pi) count the number of distinct consecutive sums, that is, sums of the shape ∑u≤i≤vπ(i)\sum_{u\leq i\leq v}\pi(i). Is it true that S(π)=o(n2) S(\pi) = o(n^2) for all π∈Sn\pi\in S_n?disproved (Lean)Formalized
#35No statement retained — open to read what the source holdsprovedNo formal declaration
#36For n = 5 the best splitting of {1, …, 10} has maximum overlap 3.openFormalized
#37No statement retained — open to read what the source holdsdisprovedNo formal declaration
#38Does there exist B⊂NB \subset \mathbb{N} which is not an additive basis, but is such that for every set A⊆NA \subseteq \mathbb{N} of Schnirelmann density α\alpha and every NN there exists b∈Bb \in B such that ∣(A∪(A+b))∩{1,…,N}∣≥(α+f(α))N \lvert (A \cup (A+b)) \cap \{1, \ldots, N\} \rvert \geq (\alpha + f(\alpha)) N where f(α)>0f(\alpha) > 0 for 0<α<10 < \alpha < 1?proved (Lean)Formalized
#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?openFormalized
#40For what functions g(N)→∞g(N) → \infty is it true that ∣A∩{1,…,N}∣≫N1/2g(N)\lvert A\cap \{1,\ldots,N\}\rvert \gg \frac{N^{1/2}}{g(N)} implies lim sup⁡1A∗1A(n)=∞\limsup 1_A\ast 1_A(n)=\infty?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?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}?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)?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}?openFormalized
#45Let k≥2k\geq 2. Is there an integer nkn_k such that, if D={1<d<nk:d∣nk}D=\{ 1<d<n_k : d\mid n_k\}, then for any kk-colouring of DD there is a monochromatic subset D′⊆DD'\subseteq D such that ∑d∈D′1d=1\sum_{d\in D'}\frac{1}{d}=1?proved (Lean)Formalized
#46Does every finite colouring of the integers have a monochromatic solution to 1=∑1ni1=\sum \frac{1}{n_i} with 2≤n1<⋯<nk2\leq n_1<\cdots <n_k?proved (Lean)Formalized
#47If δ>0\delta>0 and NN is sufficiently large in terms of δ\delta, and A⊆{1,…,N}A\subseteq\{1,\ldots,N\} is such that ∑a∈A1a>δlog⁡N\sum_{a\in A}\frac{1}{a}>\delta \log N then must there exist S⊆AS\subseteq A such that ∑n∈S1n=1\sum_{n\in S}\frac{1}{n}=1?proved (Lean)Formalized
#48Are there infinitely many integers n,mn, m such that ϕ(n)=σ(m)ϕ(n) = σ(m)?provedFormalized

Search problems.science

Find a Problem, Result, source, or page