Logo
FAQ Tags Prizes Definitions Links
All Problems Random Solved Random Open
7 solved out of 16 shown
$100
Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?
Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'.

Indeed, the answer is yes, as proved by Banks, Freiberg, and Turnage-Butterbaugh [BFT15] with an application of the Maynard-Tao machinery concerning bounded gaps between primes [Ma15]. They in fact prove that, for any $m\geq 1$, there are infinitely many $n$ such that \[d_n<d_{n+1}<\cdots <d_{n+m}\] and infinitely many $n$ such that \[d_n> d_{n+1}>\cdots >d_{n+m}.\]

Additional thanks to: Mehtaab Sawhney
$100
Let $A\subseteq \{1,\ldots,N\}$ be such that there are no $a<b<c\in A$ such that $a\mid(b+c)$. Is it true that $\lvert A\rvert\leq N/3+O(1)$?
Asked by Erdős and Sárközy, who observed that $[2N/3,N]\cap \mathbb{N}$ is such a set. The answer is yes, as proved by Bedert [Be23].
$100
An $\epsilon$-almost covering system is a set of congruences $a_i\pmod{n_i}$ for distinct moduli $n_1<\ldots<n_k$ such that the density of those integers which satisfy none of them is $\leq \epsilon$. Is there a constant $C>1$ such that for every $\epsilon>0$ and $N\geq 1$ there is an $\epsilon$-almost covering system with $N\leq n_1$ and $n_k\leq Cn_1$?
By a simple averaging argument the set of moduli $[m_1,m_2]\cap \mathbb{N}$ has a choice of residue classes which form an $\epsilon(m_1,m_2)$-almost covering system with \[\epsilon(m_1,m_2)=\prod_{m_1\leq m\leq m_2}(1-1/m).\] A $0$-covering system is just a covering system, and so by Hough [Ho15] these only exist for $n_1<10^{18}$. [NOTE: This is my best attempt at recovering problem 5 from [Er95], which doesn't make sense as written.]
$100
Is there an explicit construction of a set $A\subseteq \mathbb{N}$ such that $A+A=\mathbb{N}$ but $1_A\ast 1_A(n)=o(n^\epsilon)$ for every $\epsilon>0$?
The existence of such a set was asked by Sidon to Erdős in 1932. Erdős (eventually) proved the existence of such a set using probabilistic methods. This problem asks for a constructive solution.
$100
If $A,B\subset \{1,\ldots,N\}$ are two Sidon sets such that $(A-A)\cap(B-B)=\{0\}$ then is it true that \[ \binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1),\] where $f(N)$ is the maximum possible size of a Sidon set in $\{1,\ldots,N\}$? If $\lvert A\rvert=\lvert B\rvert$ then can this bound be improved to \[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq (1-c)\binom{f(N)}{2}\] for some constant $c>0$?
$100
If $\delta>0$ and $N$ is sufficiently large in terms of $\delta$, and $A\subseteq\{1,\ldots,N\}$ is such that $\sum_{a\in A}\frac{1}{a}>\delta \log N$ then must there exist $S\subseteq A$ such that $\sum_{n\in S}\frac{1}{n}=1$?
Solved by Bloom [Bl21], who showed that the quantitative threshold \[\sum_{n\in A}\frac{1}{n}\gg \frac{\log\log\log N}{\log\log N}\log N\] is sufficient. Erdős further speculates that perhaps even $\gg (\log\log N)^2$ might be sufficient. (A construction of Pomerance, as discussed in the appendix of [Bl21], shows that this would be best possible.)
$100
A set of integers $A$ is Ramsey $2$-complete if, whenever $A$ is $2$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. It is known that it cannot be true that \[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^2\] for all large $N$ and that there exists a Ramsey $2$-complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert < (2\log_2N)^3.\] Improve either of these bounds.
The stated bounds are due to Burr and Erdős [BuEr85].
$100
Is there a set $A\subset \mathbb{N}$ of density $0$ and a constant $c>0$ such that every graph on sufficiently many vertices with average degree $\geq c$ contains a cycle whose length is in $A$?
Bollobás proved that such a $c$ does exist if $A$ is an infinite arithmetic progression containing even numbers. Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although conjectures that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.

Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.

Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.

Additional thanks to: Richard Montgomery
$100
Give a constructive proof that $R(k)>C^k$ for some constant $C>1$.
Erdős gave a simple probabilistic proof that $R(k) \gg k2^{k/2}$. Equivalently, this question asks for an explicit construction of a graph on $n$ vertices which does not contain any clique or independent set of size $\geq c\log n$ for some constant $c>0$. Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size \[\geq 2^{(\log\log n)^{C}}\] for some constant $C>0$. Li [Li23b] has recently improved this to \[\geq (\log n)^{C}\] for some constant $C>0$.
Additional thanks to: Jesse Goodman, Mehtaab Sawhney
$100
Is it true that every subgraph of the $n$-dimensional cube with \[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\] many edges contains a $C_4$?
The best known result is due to Balogh, Hu, Lidicky, and Liu [BHLL14], who proved that $0.6068 n2^{n-1}$ edges suffice.
Additional thanks to: Casey Tompkins
$100
For any $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ such that if $G$ is a graph on $n$ vertices with no independent set or clique of size $\geq \epsilon\log n$ then $G$ contains an induced subgraph with $m$ edges for all $m\leq \delta n^2$.
Conjectured by Erdős and McKay, who proved it with $\delta n^2$ replaced by $\delta (\log n)^2$. Solved by Kwan, Sah, Sauermann, and Sawhney [KSSS22]. Erdős' original formulation also had the condition that $G$ has $\gg n^2$ edges, but an old result of Erdős and Szemerédi says that this follows from the other condition anyway.
Additional thanks to: Zachary Hunter and Mehtaab Sawhney
$100
Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with minimum distance equal to 1, chosen to minimise the diameter of $A$. If $n$ is sufficiently large then must there be three points in $A$ which form an equilateral triangle of size 1?
In fact Erdős believes such a set must have very large intersection with the triangular lattice. This is false for $n=4$, for example a square. The behaviour of such sets for small $n$ is explored by Bezdek and Fodor [BeFo99].
Additional thanks to: Boris Alexeev and Dustin Mixon
$100
Given $n$ points in $\mathbb{R}^2$, no five of which are on a line, then the number of lines containing four points is $o(n^2)$.
An example of Grünbaum shows that there could be $\gg n^{3/2}$ such lines. This may be the correct order of magnitude.
$100
Let $z_i$ be an infinite sequence of complex numbers such that $\lvert z_i\rvert=1$ for all $i\geq 1$, and for $n\geq 1$ let \[p_n(z)=\prod_{i\leq n} (z-z_i).\] Let $M_n=\max_{\lvert z\rvert=1}\lvert p_n(z)\rvert$. Is it true that $\limsup M_n=\infty$? Is it true that there exists $c>0$ such that for infinitely many $n$ we have $M_n > n^c$, or even that for all $n$ \[\sum_{k\leq n}M_k > n^{1+c}?\]
The weaker conjecture that $\limsup M_n=\infty$ was proved by Wagner, who show that there is some $c>0$ with $M_n>(\log n)^c$ infinitely often.

This was solved by Beck [Be91], who proved that there exists some $c>0$ such that \[\max_{n\leq N} M_n > N^c.\]

Additional thanks to: Winston Heap
$100
Let $A\subseteq\mathbb{R}$ be an infinite set. Must there be a set $E\subset \mathbb{R}$ of positive measure which does not contain any set of the shape $aA+b$ for some $a,b\in\mathbb{R}$ and $a\neq 0$?
#120: \cte{Er81b}[Er83d][Er90]
The Erdős similarity problem.

This is true if $A$ is unbounded or dense in some interval. It therefore suffices to prove this when $A=\{a_1>a_2>\cdots\}$ is a countable strictly monotone sequence which converges to $0$.

Steinhaus [St20] has proved this is false whenever $A$ is a finite set.

This conjecture is known in many special cases (but, for example, it is is open when $A=\{1,1/2,1/4,\ldots\}$. For an overview of progress we recommend a nice survey by Svetic [Sv00] on this problem.

Additional thanks to: Vjeksolav Kovac
$100
Let $1\leq k<n$. Given $n$ points in $\mathbb{R}^2$, at most $n-k$ on any line, the number of distinct lines formed joining two points is $\gg kn$.
In particular, given any $2n$ points with at most $n$ on a line there are $\gg n^2$ many lines formed by the points. Solved by Beck [Be83].