Logo
All Random Solved Random Open
3 solved out of 10 shown (show only solved or open)
OPEN
Let $A$ be an infinite set such that there are no distinct $a,b,c\in A$ such that $a\mid (b+c)$ and $b,c>a$. Is there such an $A$ with \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>0?\] Does there exist some absolute constant $c>0$ such that there are always infinitely many $N$ with \[\lvert A\cap\{1,\ldots,N\}\rvert<N^{1-c}?\]

Is it true that \[\sum_{n\in A}\frac{1}{n}<\infty?\]

Asked by Erdős and Sárközy [ErSa70], who proved that $A$ must have density $0$. They also prove that this is essentially best possible, in that given any function $f(x)\to \infty$ as $x\to \infty$ there exists a set $A$ with this property and infinitely many $N$ such that \[\lvert A\cap\{1,\ldots,N\}\rvert>\frac{N}{f(N)}.\] (Their example is given by all integers in $(y_i,\frac{3}{2}y_i)$ congruent to $1$ modulo $(2y_{i-1})!$, where $y_i$ is some sufficiently quickly growing sequence.)

An example of an $A$ with this property where \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\log N>0\] is given by the set of $p^2$, where $p\equiv 3\pmod{4}$ is prime.

For the finite version see [13].

SOLVED - $100
Let $A\subseteq \{1,\ldots,N\}$ be such that there are no $a,b,c\in A$ such that $a\mid(b+c)$ and $a<\min(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].

For the infinite version see [12].

Additional thanks to: Zachary Chase
SOLVED
Let $A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}$ be such that $\phi(a_1)<\cdots<\phi(a_t)$. The primes are such an example. Are they the largest possible? Can one show that $\lvert A\rvert<(1+o(1))\pi(N)$ or even $\lvert A\rvert=o(N)$?
Erdős remarks that the last conjecture is probably easy, and that similar questions can be asked about $\sigma(n)$.

Solved by Tao [Ta23b], who proved that \[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]

In [Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.

OPEN - $250
Let $f(n)$ be maximal such that if $A\subseteq\mathbb{N}$ has $\lvert A\rvert=n$ then $\prod_{a\neq b\in A}(a+b)$ has at least $f(n)$ distinct prime factors. Is it true that $f(n)/\log n\to\infty$?
Investigated by Erdős and Turán [ErTu34] (prompted by a question of Lázár and Grünwald) in their first joint paper, where they proved that \[\log n \ll f(n) \ll n/\log n\] (the upper bound is trivial, taking $A=\{1,\ldots,n\}$). Erdős says that $f(n)=o(n/\log n)$ has never been proved, but perhaps never seriously attacked.
OPEN
Let $\omega(n)$ count the number of distinct primes dividing $n$. Are there infinitely many $n$ such that, for all $m<n$, we have $m+\omega(m) \leq n$?

Can one show that there exists an $\epsilon>0$ such that there are infinitely many $n$ where $m+\epsilon \omega(m)\leq n$ for all $m<n$?

In [Er79] Erdős calls such an $n$ a 'barrier' for $\omega$. Some other natural number theoretic functions (such as $\phi$ and $\sigma$) have no barriers because they increase too rapidly. Erdős believed that $\omega$ should have infinitely many barriers. In [Er79d] he proves that $F(n)=\prod k_i$, where $n=\prod p_i^{k_i}$, has infinitely many barriers (in fact the set of barriers has positive density in the integers).

Erdős also believed that $\Omega$, the count of the number of prime factors with multiplicity), should have infinitely many barriers. Selfridge found the largest barrier for $\Omega$ which is $<10^5$ is $99840$.

In [ErGr80] this problem is suggested as a way of showing that the iterated behaviour of $n\mapsto n+\omega(n)$ eventually settles into a single sequence, regardless of the starting value of $n$ (see also [412] and [414]).

Erdős and Graham report it could be attacked by sieve methods, but 'at present these methods are not strong enough'.

See also [647] and [679].

SOLVED
If $\mathbb{N}$ is 2-coloured then must there exist a monochromatic three-term arithmetic progression $x,x+d,x+2d$ such that $d>x$?
Erdös writes 'perhaps this is easy or false'. It is not true for four-term arithmetic progressions: colour the integers in $[3^{2k},3^{2k+1})$ red and all others blue.

Ryan Alweiss has provided the following simple argument showing that the answer is yes: suppose we have some red/blue colouring without this property. Without loss of generality, suppose $1$ is coloured red, and then either $3$ or $5$ must be blue.

Suppose first that $3$ is blue. If $n\geq 6$ is red then (considering $1,n,2n-1$) we deduce $2n-1$ is blue, and then (considering $3,n+1,2n-1$) we deduce that $n+1$ is red. In particular the colouring must be eventually constant, and we are done.

Now suppose that $5$ is blue. Arguing similarly (considering $1,n,2n-1$ and $5,n+2,2n-1$) we deduce that if $n\geq 8$ is red then $n+2$ is also red, and we are similarly done, since the colouring must be eventually constant on some congruence class modulo $2$.

Additional thanks to: Ryan Alweiss
OPEN
Let $\tau(n)$ count the number of divisors of $n$. Is there some $n>24$ such that \[\max_{m<n}(m+\tau(m))\leq n+2?\]
A problem of Erdős and Selfridge. This is true for $n=24$. The $n+2$ is best possible here since \[\max(\tau(n-1)+n-1,\tau(n-2)+n-2)\geq n+2.\]

In [Er79] Erdős says 'it is extremely doubtful' that there are infinitely many such $n$, and in fact suggets that \[\lim_{n\to \infty}\max_{m<n}(\tau(m)+m-n)=\infty.\]

In [Er79d] Erdős says it 'seems certain' that for every $k$ there are infinitely many $n$ for which \[\max_{n-k<m<n}(m+\tau(m))\leq n+2,\] but 'this is hopeless with our present methods', although it follows from Schinzel's Hypothesis H.

See also [413].

OPEN
Let $g(n)$ denote the largest $t$ such that there exist integers $2\leq a_1<a_2<\cdots <a_t <n$ such that \[P(a_1)>P(a_2)>\cdots >P(a_t)\] where $P(m)$ is the greatest prime factor of $m$. Estimate $g(n)$.
OPEN
Is it true that, for any two (odd) primes $p,q$, there exists some integer $n$ such that the largest prime factor of $n$ is $p$ and the largest prime factor of $n+1$ is $q$?
Erdős writes 'it is probably hopelessly difficult to decide about the truth of this conjecture'. The number of solutions is finite for any fixed $p,q$ since the largest prime factor of $n(n+1)$ tends to $\infty$ (Mahler [Ma35] showed that this is $\gg \log\log n$, see [368]).

Sampaio has observed that the answer to this question is no if one of the primes can be $2$ - for example this is false with $p=19$ and $q=2$, since if $n+1=2^k$ and $19\mid n$ then (since $2$ is a primitive root modulo $19$) we must have $18\mid k$, and hence $73\mid 2^{18}-1\mid n$. A similar argument works with $19$ replaced by any prime $p>13$ for which $2$ is a primitive root, using a result of Rotkiewicz [Ro64b] that for every prime $p>13$ there is a prime $q>p$ which divides $2^{p-1}-1$.

It is unclear whether Erdős was aware of this obstacle; certainly in [Er95c] he asks for any two primes, but may have intended to rule out such small prime obstacles.

More generally, one can ask about whether for any primes $p_1,\ldots,p_k$ there exists some $n$ such that the largest prime factor of $n+i$ is $p_i$. Erdős writes this is 'clearly impossible' if the $p_i$ are the first $k$ primes and $k$ is sufficiently large, but does not know what happens if all of the primes are sufficiently large compared to $k$.

Additional thanks to: Euro Vidal Sampaio
OPEN
Let $f(m)$ be such that if $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert=m$ then every interval in $[1,\infty)$ of length $2N$ contains $\geq f(m)$ many distinct integers $b_1,\ldots,b_r$ where each $b_i$ is divisible by some $a_i\in A$, where $a_1,\ldots,a_r$ are distinct.

Estimate $f(m)$. In particular is it true that $f(m)\ll m^{1/2}$?

Erdős and Sarányi [ErSa59] proved that $f(m)\gg m^{1/2}$.