Problem 1134

Let $A\subseteq \mathbb{N}$ be the smallest set which contains $1$ and is closed under the operations

x\mapsto 2x+1,

x\mapsto 3x+1,

and

x\mapsto 6x+1.

Does $A$ have positive lower density?

Source: erdosproblems.com/1134

Number theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN). Crampin and Hilton answered the question in the negative in 1972 without publishing; Lagarias's Theorem 6 ([La16], refereed) is the published reconstruction, giving $|A\cap[1,T]|\le C(\epsilon)T^{\tau_1+\epsilon}$ with $\tau_1\approx0.900526<1$ , so $A$ has density zero. The site's curator, Thomas Bloom, records this as the resolution. The claim page Lagarias 2016 records the acceptance. The site's (LEAN) suffix is its catalog label; the outside Lean files it rests on are described under Formalization and on the claim pages, none of them built by this corpus.

Gu04: Guy, Richard K., Unsolved problems in number theory. Third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp. Section E36 "Klarner--Rado sequences", printed p. 361: the sequence 1, 2, 4, 5, 8, 9, 10, 14, ... that "is the thinnest which contains 1, and whenever it contains $x$ , also contains $2x$ , $3x+2$ and $6x+3$ . Does it have positive density?"; the printed generators differ from the statement's $2x+1$ , $3x+1$ , $6x+1$ , and no equivalence is claimed here; [La16] pp. 771--772 identifies Guy's generators as Klarner's free semigroup $\mathcal S_2$ (its Theorem 11), a corrected variant of Erdős's problem posed by Klarner in 1982, and reports its density question unanswered, so the two problems are distinct. Library home: Guy 2004.
Gu83b: Guy, Richard K., Unsolved Problems: Don't Try to Solve These Problems. Amer. Math. Monthly (1983), 35-38+39-41.
Kl82: Klarner, David A., A sufficient condition for certain semigroups to be free. J. Algebra (1982), 140-148.
KlRa74: Klarner, D. A. and Rado, R., Arithmetic properties of certain recursively defined sets. Pacific J. Math. 53 (1974), no. 2, 445--463, doi:10.2140/pjm.1974.53.445.
La16: Lagarias, Jeffrey C., Erdős, Klarner, and the $3x+1$ problem. Amer. Math. Monthly 123 (2016), no. 8, 753--776, doi:10.4169/amer.math.monthly.123.08.753 as printed (JSTOR's stable identifier is 10.4169/amer.math.monthly.123.8.753). Section 7, printed p. 766, poses the statement's question as the "Erdős Positive Density Problem", for which Erdős offered a prize in 1972, and reports that Crampin and Hilton answered it in the negative soon afterwards without publishing; Theorem 6 (p. 767) is the paper's reconstructed proof that the set has at most $C(\epsilon)T^{\tau_1+\epsilon}$ elements up to $T$ with $\tau_1\approx0.900526$ , so density zero. Sections 3--5 (pp. 755--761) give the history and Erdős's orbit-size bound (Theorem 3, p. 759), which makes the two-generator set $\langle2x+1,3x+1:1\rangle$ of density zero but gives nothing for the three generators since $1/2+1/3+1/6=1$ . Library home: Lagarias 2016; result pages Theorem 6 and Theorem 3.

Problem 1134

Status

Proof claims

Discussion