Problem 441

Let $N\geq 1$ . What is the size of the largest $A\subset \{1,\ldots,N\}$ such that $[a,b]\leq N$ for all $a,b\in A$ , where $[a,b]$ is the least common multiple of $a$ and $b$ ?

Is it attained by choosing all integers in $[1,(N/2)^{1/2}]$ together with all even integers in $[(N/2)^{1/2},(2N)^{1/2}]$ ?

Source: erdosproblems.com/441

Number theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

DISPROVED, the site's label, which attaches to the second question. The problem lists two parts, the size of the largest set (the first question) and the optimality of the construction (the second), and its standing derives from the accepted partial claims that settle them. The construction part: Chen and Dai's Theorem 1(ii) (Acta Arith. 128 (2007)) gives $g(N)\ge|B_N|+\mathrm{loc}\,N-2$ for infinitely many $N$ , where $\mathrm{loc}\,N$ is the number of iterated logarithms needed to bring $N$ below $1$ , so the construction is not a largest set for infinitely many $N$ and its excess over $|B_N|$ is unbounded. The Statement asks the question for each $N\ge1$ , so the explicit $N=336$ (below; the OEIS entry's comment of 2012 and AxiomProver's file) already answers it no, trivially, and the theorem answers no as well the variant asking about all large $N$ . The size part: Chen's Theorem (Acta Arith. 84 (1998)), $g(N)\sim(9N/8)^{1/2}$ , determines the size asymptotically, the form in which Erdős conjectured it ([Er73], quoted under Formulation), and Dai and Chen's Theorem (Acta Arith. 124 (2006)) sharpens it to $-2\le g(N)-(9N/8)^{1/2}\le45(N/\log N)^{1/2}\log\log N$ for large $N$ ; the exact value of $g(N)$ is not known in general, and Dai and Chen conjecture that the remainder tends to infinity. The three papers are refereed articles of Acta Arithmetica. The claim pages: Chen's asymptotic (accepted, partial: the size part, settled as a determination; refereed), Chen and Dai's theorem (accepted, partial: the construction part, refuted; refereed, and credited by the site's curator for its label) and AxiomProver's Lean disproof at $N=336$ (claimed, partial: the construction part; not built or audited here). The two accepted claims settle one part each with different values, so the derived standing is solved, answered, rather than the label's disproved, which covers only the second question. Dai and Chen's 2006 theorem has no claim page of its own: it sharpens the answer recorded on Chen's page and settles nothing further.

Ch98: Chen, Y.-G., Sequences with bounded l.c.m. of each pair of terms. Acta Arith. 84 (1998), no. 1, 71--95, DOI 10.4064/aa-84-1-71-95. The Theorem, p. 71. Library home: Chen 1998.
DaCh06: Dai, L.-X. and Chen, Y.-G., Sequences with bounded l.c.m. of each pair of terms II. Acta Arith. 124 (2006), no. 4, 315--326, DOI 10.4064/aa124-4-2. The Theorem, pp. 315--316. Library home: Dai 2006.
ChDa07: Chen, Y.-G. and Dai, L.-X., Sequences with bounded l.c.m. of each pair of terms, III. Acta Arith. 128 (2007), no. 2, 125--133, DOI 10.4064/aa128-2-3. Theorem 1 and Corollary 1, p. 126. Library home: Chen 2007.
Ch72b: Choi, S. L. G., The largest subset in $[1,n]$ whose integers have pairwise l.c.m. not exceeding $n$ . Mathematika 19 (1972), no. 2, 221--230, DOI 10.1112/S0025579300005684 (Crossref record accessed). The Theorem, printed p. 221: $g(n)<(1+\lambda-\lambda^*)n^{1/2}+o(n^{1/2})$ with $\lambda$ , $\lambda^*$ two explicit series and the paper's numerical values $0.6368<\lambda-\lambda^*<0.6380$ , the source of the bound $1.638\sqrt n$ quoted by [Ch98], [Gu04] and [OEIS]; the estimate (6), printed p. 222, $g(n)<(1+\lambda)n^{1/2}+o(n^{1/2})$ with $\lambda<0.87$ . The bound $1.43\sqrt n$ of its sequel (Acta Arith. 29 (1976), 105--111, not read) is quoted from [Ch98], p. 71. Library home: Choi 1972.
Er51b: Erdős, P., Problem. Mat. Lapok 2 (1951), 233 (the volume and page per [Ch98]'s reference [3]). Not read: the Rényi archive's bibliography, lists fourteen 1951 papers and no Mat. Lapok problem entry; no other open copy was located. The bound $g(N)\le(4N)^{1/2}+O(1)$ the site attributes to it is quoted from the site and from [Ch98], p. 71, which refers to [Er65] for a proof.
Er62: Erdős, P., Számelméleti megjegyzések IV. Mat. Lapok 13 (1962), 228--255; problem 15, printed p. 238. Not cited by the site for this problem. Library home: Erdős 1962.
Er65: Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math. VIII (1965), 181--189; item 4, printed p. 183. Library home: Erdos 1965.
Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (1973), 117--138; printed pp. 134--135. Library home: Erdos 1973.
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980), printed p. 87. Library home: Erdős and Graham 1980.
Er98: Erdős, P., Some of my new and almost new problems and results in combinatorial number theory. Number theory (Eger, 1996) (1998), 169--180. Not read (a paywalled de Gruyter chapter).
Gu04: Guy, R. K., Unsolved problems in number theory, 3rd ed. Problem Books in Mathematics, Springer (2004), xviii+437 pp. B26 "Densest set with no $l$ pairwise coprime", printed p. 125, and E2 "Density of a sequence with l.c.m. of each pair less than $x$ ", printed p. 312: B26 states $\frac3{2\sqrt2}n^{1/2}-2<g(n)\le2n^{1/2}$ as Erdős's, with the construction, and Choi's $1.638n^{1/2}$ ; E2 states $(9x/8)^{1/2}\le\max A(x)\le(4x)^{1/2}$ with the same construction; no proofs. Library home: Guy 2004.
OEIS: Nomoto, N., Sequence A068509, The On-Line Encyclopedia of Integer Sequences (2002; entry last modified 30 May 2026, server time): $g(N)$ for $N\le87$ with a table to $1000$ by W. R. Marshall.

Problem 441

Status

Proof claims

Discussion