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

102 Problems

2/3

NumberQuestionOpen
#484Prove that there exists an absolute constant c>0c>0 such that, whenever {1,…,N}\{1,\ldots,N\} is kk-coloured (and NN is large enough depending on kk) then there are at least cNcN many integers in {1,…,N}\{1,\ldots,N\} which are representable as a monochromatic sum (that is, a+ba+b where a,b∈{1,…,N}a,b\in \{1,\ldots,N\} are in the same colour class and a≠ba\neq b).proved (Lean)Formalized
#494Selfridge and Straus [SeSt58] proved that AA is determined by AkA_k if ∣A∣|A| is divisible by a prime greater than kk.provedFormalized
#645If ℕ is 22-coloured then there must exist a monochromatic three-term arithmetic progression x,x+d,x+2dx,x+d,x+2d such that d>xd>x.proved (Lean)Formalized
#656No statement retained — open to read what the source holdsprovedNo formal declaration
#658No statement retained — open to read what the source holdsproved (Lean)No formal declaration
#707Erdős Problem 707: It is false that any finite Sidon set can be embedded in a perfect different set modulo some nn.disproved (Lean)Formalized
#721No statement retained — open to read what the source holdssolvedNo formal declaration
#741Let A⊆NA\subseteq \mathbb{N} be such that A+AA+A has positive upper density. Can one always decompose A=A1⊔A2A=A_1\sqcup A_2 such that A1+A1A_1+A_1 and A2+A2A_2+A_2 both have positive upper density?solved (Lean)Formalized
#749Let ϵ>0\epsilon>0. Does there exist A⊆NA\subseteq \mathbb{N} such that the lower density of A+AA+A is at least 1−ϵ1-\epsilon and yet 1A∗1A(n)≪ϵ11_A\ast 1_A(n) \ll_\epsilon 1 for all nn?openFormalized
#763No statement retained — open to read what the source holdsdisprovedNo formal declaration
#764No statement retained — open to read what the source holdsdisprovedNo formal declaration
#772No statement retained — open to read what the source holdsprovedNo formal declaration
#781No statement retained — open to read what the source holdsdisprovedNo formal declaration
#785Let A,B⊆NA,B\subseteq \mathbb{N} be infinite sets such that A+BA+B contains all large integers. Let A(x)=∣A∩[1,x]∣A(x)=\lvert A\cap [1,x]\rvert and similarly for B(x)B(x). Is it true that if A(x)B(x)∼xA(x)B(x)\sim x then A(x)B(x)−x→∞A(x)B(x)-x\to \infty as x→∞x\to \infty?proved (Lean)Formalized
#787No statement retained — open to read what the source holdsopenNo formal declaration
#788No statement retained — open to read what the source holdsopenNo formal declaration
#789Let h(n)h(n) be maximal such that if A⊆ZA\subseteq \mathbb{Z} with ∣A∣=n\lvert A\rvert=n then there is B⊆AB\subseteq A with ∣B∣≥h(n)\lvert B\rvert \geq h(n) such that if a1+⋯+ar=b1+⋯+bsa_1+\cdots+a_r=b_1+\cdots+b_s with ai,bi∈Ba_i,b_i\in B then r=sr=s.openFormalized
#790No statement retained — open to read what the source holdsopenNo formal declaration
#791No statement retained — open to read what the source holdsopenNo formal declaration
#792No statement retained — open to read what the source holdsopenNo formal declaration
#806No statement retained — open to read what the source holdsprovedNo formal declaration
#808No statement retained — open to read what the source holdsdisprovedNo formal declaration
#817Let k≥3k \geq 3. Define gk(n)g_k(n) to be the minimal NN such that {1,...,N}\{1, ..., N\} contains some AA of size ∣A∣=n|A| = n such that ⟨A⟩={∑a∈Aϵaa:ϵa∈{0,1}} \langle A\rangle = \left\{\sum_{a \in A} \epsilon_a a : \epsilon_a \in\{0, 1\}\right\} contains no non-trivial kk-term arithmetic progression. Estimate gk(n)g_k(n). In particular, is it true that g3(n)≫3n g_3(n) \gg 3^n openFormalized
#818Let AA be a finite set of integers such that ∣A+A∣≪∣A∣\lvert A+A\rvert \ll \lvert A\rvert. Is it true that ∣AA∣≫∣A∣2(log⁡∣A∣)C\lvert AA\rvert \gg \frac{\lvert A\rvert^2}{(\log \lvert A\rvert)^C} for some constant C>0C>0?proved (Lean)Formalized
#819No statement retained — open to read what the source holdsopenNo formal declaration
#840No statement retained — open to read what the source holdsopenNo formal declaration
#847Let A⊂NA \subset \mathbb{N} be an infinite set for which there exists some ϵ>0\epsilon > 0 such that in any subset of AA of size nn there is a subset of size at least ϵn\epsilon n which contains no three-term arithmetic progression.disprovedFormalized
#863No statement retained — open to read what the source holdsprovedNo formal declaration
#864No statement retained — open to read what the source holdsopenNo formal declaration
#865There exists a constant C>0C>0 such that, for all large NN, if A⊆{1,…,N}A\subseteq \{1,\ldots,N\} has size at least 58N+C\frac{5}{8}N+C then there are distinct a,b,c∈Aa,b,c\in A such that a+b,a+c,b+c∈Aa+b,a+c,b+c\in A.proved (Lean)Formalized
#866No statement retained — open to read what the source holdsopenNo formal declaration
#867Is it true that if A={a1<⋯<at}⊆{1,…,N}A=\{a_1<\cdots <a_t\}\subseteq \{1,\ldots,N\} has no solutions to ai+ai+1+⋯+aj∈Aa_i+a_{i+1}+\cdots+a_j\in A then ∣A∣≤N2+O(1)?\lvert A\rvert \leq \frac{N}{2}+O(1)?disproved (Lean)Formalized
#874No statement retained — open to read what the source holdsprovedNo formal declaration
#875No statement retained — open to read what the source holdsopenNo formal declaration
#876No statement retained — open to read what the source holdsopenNo formal declaration
#877No statement retained — open to read what the source holdsprovedNo formal declaration
#895No statement retained — open to read what the source holdsprovedNo formal declaration
#899Let 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}∣=∞? \limsup_{N\to\infty}\frac{|(A - A)\cap \{1, ..., N\}|}{|A \cap \{1, ..., N\}|} = \infty? provedFormalized
#966Let k,r≥2k,r\geq 2. Does there exist a set A⊆NA\subseteq \mathbb{N} that contains no non-trivial arithmetic progression of length k+1k+1, yet in any rr-colouring of AA there must exist a monochromatic non-trivial arithmetic progression of length kk?proved (Lean)Formalized
#984No statement retained — open to read what the source holdsprovedNo formal declaration
#1097The main conjecture: for any finite set of integers AA with ∣A∣=n|A| = n, the number of distinct common differences in three-term arithmetic progressions is O(n3/2)O(n^{3/2}).openFormalized
#1112No statement retained — open to read what the source holdsopen (Lean)No formal declaration
#1145Let A={1≤a1<a2<⋯ }A=\{1\leq a_1 < a_2 < \cdots\} and B={1≤b1<b2<⋯ }B=\{1\leq b_1 < b_2 < \cdots\} be sets of integers with an/bn→1a_n/b_n\to 1.openFormalized
#1179No statement retained — open to read what the source holdsprovedNo formal declaration
#1185No statement retained — open to read what the source holdssolvedNo formal declaration
#1186No statement retained — open to read what the source holdsopenNo formal declaration
#1187No statement retained — open to read what the source holdssolvedNo formal declaration
#1191No statement retained — open to read what the source holdsopenNo formal declaration

Search problems.science

Find a Problem, Result, source, or page