For k,N∈N, call a finite set A⊆1,…,N k-weakly divisible if every k+1 elements of A are not pairwise relatively prime. Let M_k(N) be the largest cardinality of a k-weakly divisible subset of 1,…,N. Let P_k(N) be the set of integers in 1,…,N divisible by at least one of the first k primes. Is it true that, for every k>0 and every N≥ p_k, where p_k is the kth prime, M_k(N)=|P_k(N)|?

Erdős Problem #56 — Largest Weakly Divisible Sets

About 64 years old · traced to 1962

For $k,N\in\mathbb{N}$ , call a finite set $A\subseteq\{1,\dots,N\}$ $k$ -weakly divisible if every $k+1$ elements of $A$ are not pairwise relatively prime. Let $M_k(N)$ be the largest cardinality of a $k$ -weakly divisible subset of $\{1,\dots,N\}$ . Let $P_k(N)$ be the set of integers in $\{1,\dots,N\}$ divisible by at least one of the first $k$ primes. Is it true that, for every $k>0$ and every $N\geq p_k$ , where $p_k$ is the $k$ th prime,

M_k(N)=|P_k(N)|?

References

Primary source

The Formal Conjectures Authors, Formal Conjectures (2025); independently edited from the pinned source file.

Additional references

Pinned Formal Conjectures source, Apache-2.0.

intersecting-family number-theory

InErdős Problems

Posted 1 month ago · edited 2 weeks ago

Progress summary

Refreshed 1 month ago

Claimed solved

The proposed universal bound is false, with counterexamples for some values of $k$ , although it becomes correct for each fixed $k$ once $N$ is sufficiently large.

This is the Erdős conjecture from 1962 asserting that the largest such set is the integers divisible by one of the first $k$ primes.

Known results

The conjecture is trivial for $k=1,2$ and was proved for $k=3$ by S. L. G. Choi in 1973.
Ahlswede and Kachatrian disproved it for $k=212$ in 1994.
For $k=4$ and $N\geq49$ , Chen and Zhou proved the conjectured extremal set is uniquely optimal.
For every fixed $k$ , equality eventually holds for all sufficiently large $N$ , with a unique optimal set (Ahlswede–Kachatrian).

2017 strengthening

A later paper proved that the conjecture fails for infinitely many $k$ and that the excess over the proposed bound is unbounded in the limsup sense; it also records a counterexample for $k=211$ due to Chen and Zhou.

Current status (as of June 2026): The universal assertion is settled false; fixed small cases and eventual validity for each fixed $k$ are known, but the full finite- $N$ extremal classification remains open.

Sources

No solutions have been posted yet.