Erdős · problems
OEIS index →← the campaignThe Erdős problems.
62 of 1217 · 34 sealed
#155Let $F(N)$ be the size of the largest Sidon subset of $\{1,\ldots,N\}$. Is it true that for every $k\geq 1$ we have\[F(N+k)\leq F(N)+1\]for all sufficiently large $N$?additive combinatorics · 4 Vela attempts (improved bound) · AI tried (unverified) · A143824,A227590,A003022#272Let $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$?additive combinatorics · 1 Vela attempt (honest null) · AI tried (unverified) · possible#141Let $k\geq 3$. Are there $k$ consecutive primes in arithmetic progression?additive combinatorics · AI tried (unverified) · A006560#142Let $r_k(N)$ be the largest possible size of a subset of $\{1,\ldots,N\}$ that does not contain any non-trivial $k$-term arithmetic progression. Prove an asymptotic formula for $r_k(N)$.additive combinatorics · AI tried (unverified) · A003002,A003003,A003004,A003005#160Let $h(N)$ be the smallest $k$ such that $\{1,\ldots,N\}$ can be coloured with $k$ colours so that every four-term arithmetic progression must contain at least three distinct colours. Estimate $h(N)$.additive combinatorics · AI tried (unverified) · possible#168Let $F(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain any set of the form $\{n,2n,3n\}$. What is\[ \lim_{N\to \infty}\frac{F(N)}{N}?\]Is this limit irrational?additive combinatorics · AI tried (unverified) · A004059,A057561,A094708,A386439#170Let $F(N)$ be the smallest possible size of $A\subset \{0,1,\ldots,N\}$ such that $\{0,1,\ldots,N\}\subset A-A$. Find the value of\[\lim_{N\to \infty}\frac{F(N)}{N^{1/2}}.\]sparse ruler problem · additive combinatorics · AI tried (unverified) · A046693#172Is 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?additive combinatorics · AI tried (unverified) · N/A#241Let $f(N)$ be the maximum size of $A\subseteq \{1,\ldots,N\}$ such that the sums $a+b+c$ with $a,b,c\in A$ are all distinct (aside from the trivial coincidences). Is it true that\[ f(N)\sim N^{1/3}?\]additive combinatorics · AI tried (unverified) · A387704#749Let $\epsilon>0$. Does there exist $A\subseteq \mathbb{N}$ such that the lower density of $A+A$ is at least $1-\epsilon$ and yet $1_A\ast 1_A(n) \ll_\epsilon 1$ for all $n$?additive combinatorics · AI tried (unverified) · N/A#789Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b…additive combinatorics · AI tried (unverified) · possible#817Let $k\geq 3$ and define $g_k(n)$ to be the minimal $N$ such that $\{1,\ldots,N\}$ contains some $A$ of size $\lvert A\rvert=n$ such that\[\langle A\rangle = \left\{\sum_{a\in A}\epsilon_aa: \epsilon_…additive combinatorics · AI tried (unverified) · possible#847Let $A\subset \mathbb{N}$ be an infinite set for which there exists some $\epsilon>0$ such that in any subset of $A$ of size $n$ there is a subset of size at least $\epsilon n$ which contains no t…additive combinatorics · solved · AI tried (unverified) · N/A#169Let $k\geq 3$ and $f(k)$ be the supremum of $\sum_{n\in A}\frac{1}{n}$ as $A$ ranges over all sets of positive integers which do not contain a $k$-term arithmetic progression. Estimate $f(k)$. Is\[\li…additive combinatorics · AI tried (unverified) · A005346#176Let $N(k,\ell)$ be the minimal $N$ such that for any $f:\{1,\ldots,N\}\to\{-1,1\}$ there must exist a $k$-term arithmetic progression $P$ such that\[ \left\lvert \sum_{n\in P}f(n)\right\rvert\geq \ell…additive combinatorics · AI tried (unverified) · possible#187Find the best function $f(d)$ such that, in any 2-colouring of the integers, at least one colour class contains an arithmetic progression with common difference $d$ of length $f(d)$ for infinitely man…additive combinatorics · AI tried (unverified) · N/A#190Let $H(k)$ be the smallest $N$ such that in any finite colouring of $\{1,\ldots,N\}$ (into any number of colours) there is always either a monochromatic $k$-term arithmetic progression or a rainbow ar…additive combinatorics · solved · AI tried (unverified) · possible#201Let $G_k(N)$ be such that any set of $N$ integers contains a subset of size at least $G_k(N)$ which does not contain a $k$-term arithmetic progression. Determine the size of $G_k(N)$. How does it rela…additive combinatorics · AI tried (unverified) · A003002,A003003,A003004,A003005,possible#271Let $A(n)=\{a_0<a_1<\cdots\}$ be the sequence defined by $a_0=0$ and $a_1=n$, and for $k\geq 1$ define $a_{k+1}$ as the least positive integer such that there is no three-term arithmetic progr…Stanley sequences · additive combinatorics · AI tried (unverified) · A005487#787Let $g(n)$ be maximal such that given any set $A\subset \mathbb{R}$ with $\lvert A\rvert=n$ there exists some $B\subseteq A$ of size $\lvert B\rvert\geq g(n)$ such that $b_1+b_2\not\in A$ for all $b_1…additive combinatorics · AI tried (unverified) · possible#788Let $f(n)$ be maximal such that if $B\subset (2n,4n)\cap \mathbb{N}$ there exists some $C\subset (n,2n)\cap \mathbb{N}$ such that $c_1+c_2\not\in B$ for all $c_1\neq c_2\in C$ and $\lvert C\rvert+\lve…additive combinatorics · AI tried (unverified) · possible#790Let $l(n)$ be maximal such that if $A\subset\mathbb{Z}$ with $\lvert A\rvert=n$ then there exists a sum-free $B\subseteq A$ with $\lvert B\rvert \geq l(n)$ - that is, $B$ is such that there are no sol…additive combinatorics · AI tried (unverified) · possible#791Let $g(n)$ be minimal such that there exists $A\subseteq \{0,\ldots,n\}$ of size $g(n)$ with $\{0,\ldots,n\}\subseteq A+A$. Estimate $g(n)$. In particular is it true that $g(n)\sim 2n^{1/2}$?additive combinatorics · AI tried (unverified) · A066063#792Let $f(n)$ be maximal such that in any $A\subset \mathbb{Z}$ with $\lvert A\rvert=n$ there exists some sum-free subset $B\subseteq A$ with $\lvert B\rvert \geq f(n)$, so that there are no solutions to…additive combinatorics · AI tried (unverified) · possible#819Let $f(N)$ be maximal such that there exists $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=\lfloor N^{1/2}\rfloor$ such that $\lvert (A+A)\cap [1,N]\rvert=f(N)$. Estimate $f(N)$.additive combinatorics · AI tried (unverified) · possible#840Let $f(N)$ be the size of the largest quasi-Sidon subset $A\subset\{1,\ldots,N\}$, where we say that $A$ is quasi-Sidon if\[\lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2}.\]How does $f(N)$ grow?additive combinatorics · AI tried (unverified) · N/A#875Let $A=\{a_1<a_2<\cdots\}\subset \mathbb{N}$ be an infinite set such that the sets\[S_r = \{ a_1+\cdots +a_r : a_1<\cdots<a_r\in A\}\]are disjoint for distinct $r\geq 1$. How fast can …additive combinatorics · AI tried (unverified) · N/A#876Let $A=\{a_1<a_2<\cdots\}\subset \mathbb{N}$ be an infinite sum-free set - that is, there are no solutions to\[a=b_1+\cdots+b_r\]with $b_1<\cdots<b_r<a\in A$. How small can $a_{n+1…additive combinatorics · AI tried (unverified) · N/A#1112Let $1\leq d_1<d_2$ and $k\geq 3$. Does there exist an integer $r$ such that if $B=\{b_1<\cdots\}$ is a lacunary sequence of positive integers with $b_{i+1}\geq rb_i$ then there exists a seque…additive combinatorics · AI tried (unverified) · N/A#109Any $A\subseteq \mathbb{N}$ of positive upper density contains a sumset $B+C$ where both $B$ and $C$ are infinite.Erdős sumset conjecture · additive combinatorics · solved · N/A#138Let the van der Waerden number $W(k)$ be such that whenever $N\geq W(k)$ and $\{1,\ldots,N\}$ is $2$-coloured there must exist a monochromatic $k$-term arithmetic progression. Improve the bounds for $…additive combinatorics · AI machine-verified · A005346#139Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(N)$.Szemerédi's theorem · additive combinatorics · solved · A003002,A003003,A003004,A003005#198If $A\subset \mathbb{N}$ is a Sidon set then must the complement of $A$ contain an infinite arithmetic progression?additive combinatorics · solved · N/A#245Let $A\subseteq \mathbb{N}$ be an infinite set such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that\[\limsup_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\…additive combinatorics · solved · N/A#707Let $A\subset \mathbb{N}$ be a finite Sidon set. Is there some set $B$ with $A\subseteq B$ which is perfect difference set modulo $p^2+p+1$ for some prime $p$?additive combinatorics · solved · N/A#741Let $A\subseteq \mathbb{N}$ be such that $A+A$ has positive (upper) density. Can one always decompose $A=A_1\sqcup A_2$ such that $A_1+A_1$ and $A_2+A_2$ both have positive (upper) density?Is there a …additive combinatorics · solved · AI machine-verified · N/A#899Let $A\subseteq \mathbb{N}$ be an infinite set such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that\[\limsup_{N\to \infty}\frac{\lvert (A-A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\…additive combinatorics · solved · N/A#1145Let $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 th…additive combinatorics · N/A#1199Is it true that in any $2$-colouring of $\mathbb{N}$ there exists an infinite set $A$ such that all elements of $A+A$ are the same colour?additive combinatorics · possible#140Let $r_3(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $3$-term arithmetic progression. Prove that $r_3(N)\ll N/(\log N)^C$ for every $C>0$.additive combinatorics · solved · A003002#171Is it true that for every $\epsilon>0$ and integer $t\geq 1$, if $N$ is sufficiently large and $A$ is a subset of $[t]^N$ of size at least $\epsilon t^N$ then $A$ must contain a combinatorial line…density Hales-Jewett · additive combinatorics · solved · A156989#179Let $1\leq k<\ell$ be integers and define $F_k(N,\ell)$ to be minimal such that every set $A\subset \mathbb{N}$ of size $N$ which contains at least $F_k(N,\ell)$ many $k$-term arithmetic progressions …additive combinatorics · solved · possible#185Let $f_3(n)$ be the maximal size of a subset of $\{0,1,2\}^n$ which contains no three points on a line. Is it true that $f_3(n)=o(3^n)$?additive combinatorics · solved · A003142#186Let $F(N)$ be the maximal size of $A\subseteq \{1,\ldots,N\}$ which is 'non-averaging', so that no $n\in A$ is the arithmetic mean of at least two elements in $A$. What is the order of growth of $F(N)…additive combinatorics · solved · A389784#658Let $\delta>0$ and $N$ be sufficiently large depending on $\delta$. Is it true that if $A\subseteq \{1,\ldots,N\}^2$ has $\lvert A\rvert \geq \delta N^2$ then $A$ must contain the vertices of a sq…additive combinatorics · solved · possible#781Let $f(k)$ be the minimal $n$ such that any $2$-colouring of $\{1,\ldots,n\}$ contains a monochromatic $k$-term descending wave: a sequence $x_1<\cdots <x_k$ such that, for $1<j<k$,\[x…additive combinatorics · solved · possible#785Let $A,B\subseteq \mathbb{N}$ be infinite sets such that $A+B$ contains all large integers. Let $A(x)=\lvert A\cap [1,x]\rvert$ and similarly for $B(x)$. Is it true that if $A(x)B(x)\sim x$ then\[A(x)…exact additive complements · additive combinatorics · solved · N/A#806Let $A\subseteq \{1,\ldots,n\}$ with $\lvert A\rvert \leq n^{1/2}$. Must there exist some $B\subset\mathbb{Z}$ with $\lvert B\rvert=o(n^{1/2})$ such that $A\subseteq B+B$?additive combinatorics · solved · possible#808Let $c,\epsilon>0$ and $n$ be sufficiently large. If $A\subset \mathbb{N}$ has $\lvert A\rvert=n$ and $G$ is any graph on $A$ with at least $n^{1+c}$ edges then\[\max(\lvert A+_GA\rvert,\lvert A\c…additive combinatorics · solved · N/A#818Let $A$ be a finite set of integers such that $\lvert A+A\rvert \ll \lvert A\rvert$. Is it true that\[\lvert AA\rvert \gg \frac{\lvert A\rvert^2}{(\log \lvert A\rvert)^C}\]for some constant $C>0$?additive combinatorics · solved · N/A#867Is it true that if $A=\{a_1<\cdots <a_t\}\subseteq \{1,\ldots,N\}$ has no solutions to\[a_i+a_{i+1}+\cdots+a_j\in A\]then\[\lvert A\rvert \leq \frac{N}{2}+O(1)?\]additive combinatorics · solved · possible#877Let $f_m(n)$ count the number of maximal sum-free subsets $A\subseteq\{1,\ldots,n\}$ - that is, there are no solutions to $a=b+c$ in $A$ and $A$ is maximal with this property. Estimate $f(n)$ - is it …additive combinatorics · solved · possible#895Is it true that, for all sufficiently large $n$, if $G$ is a triangle-free graph on $\{1,\ldots,n\}$ then there must exist three independent points $a,b,a+b$?additive combinatorics · solved · N/A#1179Let $0<\epsilon<1$ and let $g_\epsilon(N)$ be the minimal $k$ such that if $G$ is an abelian group of size $N$ and $A\subseteq G$ is a uniformly random subset of size $k$, and\[F_A(g) = \#\left\{ S\su…additive combinatorics · solved · N/A#1185Let $\delta>0$ and $k\geq 3$. Is it true that there exists $m\geq 1$ (depending only on $\delta$ and $k$) such that, for all large $N$, if $A,B\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert \geq \…additive combinatorics · solved · N/A#1186Let $\delta_k$ be such that in any $2$-colouring of $\{1,\ldots,n\}$ there exist at least $(\delta_k+o(1))n^2$ many monochromatic $k$-term arithmetic progressions. Give reasonable bounds (or even an a…additive combinatorics · possible#1191Let $A\subset\mathbb{N}$ be an infinite Sidon set. Is it true that\[\liminf_{x\to \infty} \frac{\lvert A\cap [1,x]\rvert}{x^{1/2}}(\log x)^{1/2}=0?\]Does there exist an infinite Sidon set $A$ such tha…additive combinatorics · possible#1192For $A\subset \mathbb{N}$ let $f_r(n)$ count the number of solutions to $n=a_1+\cdots+a_r$ with $a_i\in A$.Does there exist, for all $r\geq 2$, a basis $A$ of order $r$ (so that $f_r(n)>0$ for all…additive combinatorics · possible#1193Let $A\subset \mathbb{N}$ and let $g(n)$ be a non-decreasing function of $n$ which is always $>0$. Is the lower density of\[\{ n : 1_A\ast 1_A(n)=g(n)\}\]always $0$? Is the upper density always $&…additive combinatorics · solved · N/A#1194Let $A\subset\mathbb{N}$ be such that every integer $n\geq 1$ can be written uniquely as $a_n-b_n$ for some $a_n,b_n\in A$. How fast must $a_n/n$ increase?additive combinatorics · possible#1198If $\mathbb{N}$ is $2$-coloured then must there exist an infinite set $A=\{a_1<\cdots\}$ such that all expressions of the shape\[\prod_{i\in S_1}a_i+\cdots+\prod_{i\in S_k}a_i,\]for disjoint $S_1,…additive combinatorics · solved · N/A#1213Let $a,K\geq 1$. Does there exist $f(a,K)$ such that if\[a=a_1<\cdots <a_s\]is a sequence of integers with $a_s> f(a,K)$ and with bounded gaps $a_{i+1}-a_i\leq K$ then there are two distinct intervals…additive combinatorics · solved · possible