Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


The claim. For every tt and ε>0\varepsilon>0 there is n0(t,ε)n_0(t,\varepsilon) such that for n>n0n>n_0

2ctlog⁡n/log⁡log⁡n<ft(n)<n3/4+ε.2^{c_t\log n/\log\log n}<f_t(n)<n^{3/4+\varepsilon}.

This is the Theorem, display (4), on p. 644 of P. Erdős, On a problem in elementary number theory and a combinatorial problem, Math. Comp. 18 (1964), no. 88, 644--646 (received 20 March 1964), paged as the theorem page of Erdős (1964). Erdős's ft(n)f_t(n), the least size that forces tt integers with pairwise the same greatest common divisor, is one more than the site's fr(N)f_r(N) of Problem 535. The upper bound comes from the Erdős–Rado sunflower bound applied to squarefree parts, the lower bound from an explicit product construction on the first 3k3k primes (p. 645). The page is named by the date the paper was received.

Covers. For every fixed r≥3r\ge3, fr(N)<N3/4+εf_r(N)<N^{3/4+\varepsilon} for large NN and fr(N)>Ncr/log⁡log⁡Nf_r(N)>N^{c_r/\log\log N}; the order of fr(N)f_r(N) is not determined.

Acceptance. Refereed: the journal publication. The site's commentary credits the result on a problem it labels OPEN, which is not acceptance.

Depends on. Nothing in this wiki: the theorem and its proof are contained in the cited paper, whose card is linked above.