ERDŐS/DAILY ▸

← back to the ledger

ERDőS #892 · PARTIAL

Erdős problem #892 — wave w021

Date: 2026-07-28 UTC

Claim labels

Step 0: mandatory live-page gate

I fetched the authoritative live page and its discussion thread through the Bright Data browser on 2026-07-28. Direct datacenter HTTP was not used for the gate.

Live state:

Thus the mandatory stop condition did not fire.

Verbatim current statement

Is there a necessary and sufficient condition for a sequence of integers \(b_1<b_2<\cdots\) that ensures there exists a primitive sequence \(a_1<a_2<\cdots\) (i.e. no element divides another) with \(a_n\ll b_n\) for all \(n\)?

In particular, is this always possible if there are no non-trivial solutions to \((b_i,b_j)=b_k\)?

Similarly, find necessary and sufficient conditions on a sequence \(n_1<n_2<\cdots\) that ensure there exists a primitive set \(A\) such that \[ > \lvert A\cap[1,2^{n_i}]\rvert\gg 2^{n_i} > \] for every \(i\).

The page attributes the problem to Erdős, Sárközi, and Szemerédi and lists the following known necessary conditions:

\[ \sum_n\frac1{b_n\log b_n}<\infty \tag{P1} \]

and

\[ \sum_{b_n<x}\frac1{b_n} =o\!\left(\frac{\log x}{\sqrt{\log\log x}}\right). \tag{P2} \]

It says that (P1) is due to Erdős (1935), (P2) to Erdős–Sárközy–Szemerédi (1967), mentions the analogous real-number question as problem #143, and records Erdős’s 1980 view that the first question is “difficult and perhaps has no reasonable solution” while the final question may be more reasonable.

The two live comments are:

  1. “By a trivial solution to \((b_i,b_j)=b_k\), what exactly is meant?”
  2. “I would imagine it is when \(i=j=k\).”

The page itself warns that comments are unverified. This particular ambiguity matters; see “The gcd wording” below.

Primary-source audit and literature search

I verified the following sources rather than relying on titles or search snippets.

  1. Erdős (1935). Note on sequences of integers no one of which is divisible by any other, J. London Math. Soc. 10 (1935), 126–128. Its displayed theorem is that \(\sum 1/(a\log a)\) converges for every primitive sequence; it proves a uniform stronger weighted inequality. This verifies (P1).
  1. Erdős–Sárközy–Szemerédi (1967). On a theorem of Behrend, J. Austral. Math. Soc. 7 (1967), 9–16. Theorem 1 states

\[ \sum_{\substack{a\in A\\a<x}}\frac1a =o\!\left(\frac{\log x}{\sqrt{\log\log x}}\right) \] for every infinite primitive sequence \(A\). This verifies (P2).

  1. The live page’s [ESS68] entry. Erdős–Sárközy–Szemerédi, On the solvability of certain equations in sequences of positive upper logarithmic density, J. London Math. Soc. 43 (1968), 71–78, DOI 10.1112/jlms/s1-43.1.71. I verified the paper and its theorem about infinite gcd/lcm-closed subsequences in a set of positive upper logarithmic density.
  1. Historical formulation and the gcd convention. Erdős–Sárközy–Szemerédi, On divisibility properties of sequences of integers, Number Theory (Debrecen, 1968), Colloq. Math. Soc. János Bolyai 2 (published 1970), 35–49. Page 37 prints the general \(b_n\) question; page 42 prints the gcd-free special question. On page 41 the authors explicitly say that when writing \((a_i,a_j)=a_r\), they henceforth assume \(a_i\nmid a_j\) and \(a_j\nmid a_i\). Martin–Pomerance also cite this conference paper as the source of the favorite problem.
  1. Erdős (1980). A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89–115. Page 101 contains both the general \(b_n\) question and the final \(2^{n_i}\)-scale question essentially as on the live page.
  1. Ahlswede–Khachatrian–Sárközy (1999). On the counting function of primitive sets of integers, J. Number Theory 79 (1999), 330–344. It constructs consistently large primitive counting functions in one near-boundary iterated-log regime.
  1. Martin–Pomerance (2011). Primitive sets with large counting functions, Publ. Math. Debrecen 79 (2011), 521–530, DOI 10.5486/PMD.2011.5051. Its introduction explicitly identifies this Erdős problem and says its principal result answers it affirmatively for smoothly growing sequences. Theorem 1 and Proposition 6 are used below.
  1. McNew (2020). Primitive and geometric-progression-free sets without large gaps, Acta Arith. 192 (2020), 95–104. This gives a different probabilistic construction controlling individual gaps, but it does not give a criterion for arbitrary \(b_n\) or for arbitrary prescribed density scales.

Exact-phrase searches for the \(b_n\) question, its gcd-free special case, and the \(2^{n_i}\) formulation, together with the citation chain above, found no primary source claiming a full necessary-and-sufficient condition. This is a search result, not proof that no uncatalogued result exists. The important positive miss from the live page is Martin–Pomerance (2011), which gives a substantial partial answer.

Result 1: the gcd wording

(a) If “no non-trivial solutions” is interpreted literally as the second live commenter suggests—every solution must have \(i=j=k\)—then the special question is immediate. If \(b_i\mid b_j\) for distinct \(i,j\), then

\[ (b_i,b_j)=b_i \]

is a solution with indices not all equal. Therefore no distinct \(b_i,b_j\) divide one another, \(B=\{b_i\}\) is already primitive, and one may take \(a_i=b_i\).

This does not resolve the intended historical question. The original convention excludes comparable input pairs before asking whether their gcd is another sequence member. Under that convention the hypothesis is genuinely weaker than primitivity. All discussion of the open gcd-free case below uses this historically explicit convention. The live statement should ideally define “non-trivial.”

Result 2: a sharp iff theorem for a broad smooth family

Write \(\log_j x\) for the \(j\)-fold iterated natural logarithm when \(x\) is large. Finite initial terms can be defined arbitrarily and do not affect \(\ll\).

Theorem

Let \(L:[2,\infty)\to(0,\infty)\) be nondecreasing and satisfy

\[ \frac{L(2t)}{L(t)}\longrightarrow1. \tag{1} \]

Define, for all sufficiently large \(n\),

\[ D_L(n)=\log_2n\,\log_3n\,L(\log_2n), \qquad b_n=\left\lceil nD_L(n)\right\rceil, \tag{2} \]

and extend \(b_n\) to a strictly increasing integer sequence in any way over the finitely many omitted indices. Then

\[ \boxed{\ \exists\hbox{ primitive }a_1<a_2<\cdots\text{ with }a_n\ll b_n \quad\Longleftrightarrow\quad \int_2^\infty\frac{dt}{t\log t\,L(t)}<\infty . \ } \tag{3} \]

The necessity is (a) modulo Erdős’s classical primitive-sum theorem, and the sufficiency is (b) modulo Martin–Pomerance Theorem 1.

Proof of necessity

Condition (1) and monotonicity imply \(L(t)\ll_\varepsilon t^\varepsilon\) for every \(\varepsilon>0\): eventually \(L(2t)\le 2^\varepsilon L(t)\), and iteration over dyadic intervals gives the bound. Hence

\[ \log D_L(n)=o(\log n),\qquad \log b_n\sim\log n. \tag{4} \]

If \(a_n\le Cb_n\), then for all sufficiently large \(n\),

\[ \frac1{b_n\log b_n}\ll_C\frac1{a_n\log a_n}. \]

Erdős’s 1935 theorem therefore forces \(\sum1/(b_n\log b_n)<\infty\).

Using (2), (4), monotonicity, and the integral test, that series converges exactly when

\[ \int^\infty \frac{dx} {x\log x\,\log_2x\,\log_3x\,L(\log_2x)} <\infty. \tag{5} \]

Put \(u=\log x\), then \(t=\log u=\log_2x\). Integral (5) becomes

\[ \int^\infty\frac{dt}{t\log t\,L(t)}, \]

which proves the necessary direction.

Proof of sufficiency

Assume the integral in (3) converges. Martin–Pomerance Theorem 1 supplies a primitive set \(S\) with

\[ S(x)\asymp \frac{x}{\log_2x\,\log_3x\,L(\log_2x)} =\frac{x}{D_L(x)} \tag{6} \]

for all sufficiently large \(x\).

Let \(a_n\) enumerate \(S\). From (1), monotonicity, and (4),

\[ D_L\!\bigl(nD_L(n)\bigr)\sim D_L(n). \tag{7} \]

Choose a sufficiently large constant \(K\). Equations (6)–(7) give

\[ S\!\bigl(KnD_L(n)\bigr)\ge n \]

for all large \(n\), so

\[ a_n\le KnD_L(n)\ll b_n. \]

The reverse comparison follows similarly from the upper half of (6), so in fact \(a_n\asymp b_n\).

Concrete sharp boundary

(b) Taking \(L(t)=(\log t)^\varepsilon\) gives, for every fixed \(\varepsilon>0\),

\[ b_n\asymp n\log_2n\,(\log_3n)^{1+\varepsilon} \quad\Longrightarrow\quad \exists\text{ primitive }a_n\asymp b_n. \tag{8} \]

(a) At the boundary \(L(t)=1\),

\[ b_n\asymp n\log_2n\,\log_3n, \tag{9} \]

the integral is \(\int dt/(t\log t)=\infty\), so no primitive sequence can satisfy \(a_n\ll b_n\). Thus (8) versus (9) is a genuine iff threshold inside this smooth family, not merely a one-sided construction.

This does not characterize irregular \(b_n\): arbitrarily tall or long counting-function spikes are precisely what the slow-variation hypothesis removes.

Result 3: an explicit computable primitive sequence

This specializes (8) to \(\varepsilon=1\) and makes the Martin–Pomerance marker construction completely explicit.

For \(k\ge1\), put

\[ f(k)=10k\log^2(k+1),\qquad p_0=1, \]

and define

\[ p_k=\text{the least prime strictly larger than }\max\{p_{k-1},f(k)\}. \tag{10} \]

For \(\Omega(m)\), the number of prime factors counted with multiplicity, let

\[ S_k= \left\{ m\ge2: \Omega(m)=k,\quad p_k\mid m,\quad p_j\nmid m\ (1\le j<k) \right\}, \qquad S=\bigcup_{k\ge1}S_k. \tag{11} \]

Marker facts

(a) The reciprocal-marker hypothesis used by Martin–Pomerance holds with room to spare. Since \(p_k>10k\log^2(k+1)\),

\[ \begin{aligned} \sum_{k\ge1}\frac1{p_k} &< \frac1{10}\sum_{k\ge1}\frac1{k\log^2(k+1)}\\ &< \frac1{10} \left( \frac1{\log^22} +\frac1{2\log^22} +\int_2^\infty\frac{dx}{x\log^2x} \right)\\ &= \frac1{10} \left( \frac{3}{2\log^22}+\frac1{\log2} \right) =0.4564748512\ldots<\frac12. \end{aligned} \tag{12} \]

(b: prime number theorem) We also have

\[ p_k\sim10k\log^2k. \tag{13} \]

Indeed, if \(r_k=\pi(p_k)\), recurrence (10) gives

\[ r_k=\max\{r_{k-1}+1,\ \pi(f(k))+1\}. \]

Consequently

\[ \pi(f(k))+1\le r_k\le\pi(f(k))+k. \]

The prime number theorem gives \(\pi(f(k))\sim10k\log k\), so the additive \(k\) is \(o(\pi(f(k)))\); applying the prime number theorem again yields (13). In particular \(p_k\ll k^2\).

Elementary global primitivity

(a) The infinite set \(S\) in (11) is primitive. Suppose distinct \(m\in S_j\) and \(n\in S_k\) satisfy \(m\mid n\). Then \(\Omega(m)<\Omega(n)\), so \(j<k\). But \(p_j\mid m\mid n\), while membership of \(n\) in \(S_k\) says \(p_j\nmid n\), a contradiction.

Asymptotic enumeration

(b: Sathe–Selberg through Martin–Pomerance Proposition 6) Their proposition applies because of (12), (13), and \(p_k\ll k^2\), and gives

\[ S(x)\asymp\frac{x}{p_{\lfloor c\log_2x\rfloor}} \asymp \frac{x}{\log_2x\,(\log_3x)^2}, \tag{14} \]

where the two sides of their bound use \(c=1/2\) and \(c=3/2\). Hence, if \(a_n\) enumerates this explicit \(S\),

\[ \boxed{\ a_n\asymp n\log_2n\,(\log_3n)^2.\ } \tag{15} \]

Equation (15) is not inferred from the finite data below; its analytic dependency is explicitly Sathe–Selberg.

Result 4: a necessary condition for the final \(2^{n_i}\)-scale question

Theorem

(a) If a primitive set \(A\) and a constant \(c>0\) satisfy

\[ \lvert A\cap[1,2^{n_i}]\rvert\ge c\,2^{n_i} \quad\text{for every }i, \tag{16} \]

then necessarily

\[ \boxed{\ \sum_{i=1}^{\infty}\frac1{n_i}<\infty.\ } \tag{17} \]

Proof

We may assume \(0<c\le1\). Put \(X_i=2^{n_i}\) and \(\delta=c/2\). For all sufficiently large \(i\),

\[ \begin{aligned} \left|A\cap(\delta X_i,X_i]\right| &\ge A(X_i)-\lfloor\delta X_i\rfloor\\ &\ge \frac{c}{3}X_i. \end{aligned} \tag{18} \]

Every \(a\) in this slice has

\[ \frac1{a\log a}\ge\frac1{X_i\log X_i}, \]

so (18) charges at least

\[ \sum_{a\in A\cap(\delta X_i,X_i]}\frac1{a\log a} \ge \frac{c}{3\log X_i} =\frac{c}{3(\log2)n_i} \tag{19} \]

to that slice.

Choose an integer \(r\) with \(\delta2^r>1\). Since the \(n_i\) are strictly increasing integers,

\[ X_{i+r}\ge2^rX_i, \]

and therefore the intervals

\[ (\delta X_i,X_i],\quad (\delta X_{i+r},X_{i+r}],\quad (\delta X_{i+2r},X_{i+2r}],\ldots \]

are pairwise disjoint.

If \(\sum_i1/n_i\) diverged, at least one of its \(r\) residue-class subseries would diverge. Summing (19) over that residue class would then force

\[ \sum_{a\in A}\frac1{a\log a}=\infty, \]

contrary to Erdős’s 1935 theorem. This proves (17).

For example, (17) rules out \(n_i=i\), \(n_i=i\log i\), and every other sequence with divergent reciprocal sum. It does not rule out \(n_i=i^{1+\varepsilon}\) or \(n_i=2^i\). No sufficiency claim is made.

Exact compactness reductions and the remaining wall

General and gcd-free \(b_n\)

For a fixed increasing \(b=(b_i)\), define the finite dilation number

\[ C_N(b)= \min_{\substack{2\le a_1<\cdots<a_N\\ \{a_1,\ldots,a_N\}\ {\rm primitive}}} \max_{1\le i\le N}\frac{a_i}{b_i}. \tag{20} \]

(a) There exists an infinite primitive sequence with \(a_i\le Cb_i\) for every \(i\) if and only if \(C_N(b)\le C\) for every \(N\). The forward implication is immediate. For the reverse implication, form the finitely branching tree of all feasible primitive prefixes with the fixed deadlines \(a_i\le Cb_i\). It has a vertex at every depth; König’s infinity lemma supplies an infinite branch.

Thus the historically intended gcd-free special case is exactly the assertion

\[ \sup_N C_N(b)<\infty \tag{21} \]

for every \(b\) having no gcd solution from an incomparable input pair.

The cited gcd theorems give the weighted thinness condition (P2), but they do not control the deadline-respecting antichains in (20). The missing lemma is precisely a uniform bound in (21), not another finite-\(N\) construction.

Final scale question

Fix \(c>0\), \(X_i=2^{n_i}\), and \(m\). Consider the finite feasibility problem

\[ \begin{cases} A_m\subseteq[1,X_m]\text{ is primitive},\\ |A_m\cap[1,X_i]|\ge cX_i,&1\le i\le m. \end{cases} \tag{22} \]

(a) There is an infinite primitive \(A\) satisfying all the scale constraints for this \(c\) if and only if (22) is feasible for every \(m\). This is again König compactness, now using restriction from \([1,X_m]\) to \([1,X_{m-1}]\).

Condition (17) is a genuine analytic obstruction to (22) being feasible uniformly in \(m\). What remains is a construction, or another obstruction, for reciprocal-summable but irregular scale sequences.

Why the available machinery stops

These are the exact finiteness/uniformity gaps; nothing here claims the full problem closed.

From-scratch computation

The standalone checker is erdos892_wavew021_verify.py. It uses only the Python standard library and, independently:

  1. computes \(\Omega(n)\) through a prime-power sieve;
  2. recomputes every \(\Omega(n)\) through smallest-prime-factor recursion and compares all entries;
  3. constructs the marker primes and trial-divides each marker independently;
  4. evaluates membership in (11) for every \(n\le10^6\);
  5. scans every multiple of every selected member to detect any divisibility conflict;
  6. recomputes the infinite reciprocal upper certificate (12);
  7. hashes both the membership bit-vector and the element list.

Run:

python3 runs/erdos892_wavew021_verify.py

Exact output at the default limit includes:

limit=1000000
markers=p_1=5,p_2=29,p_3=59,p_4=107,p_5=163,p_6=229,p_7=307,
        p_8=389,p_9=479,p_10=577,p_11=683,p_12=797,p_13=907,
        p_14=1031,p_15=1163,p_16=1289,p_17=1423,p_18=1567,p_19=1709
partial_marker_reciprocal_sum=0.289281277743
infinite_marker_reciprocal_upper_certificate=0.456474851240
set_size=10204
multiples_tested_for_primitivity=324042
membership_sha256=b2cc061bd93dee18e2dadbb6ab0a90d94bc88d0a9cdd7cfa8c70ef575f966ca2
elements_csv_sha256=a9c22796f4fec00e41ec24d92eda0f34bbb678076b04c4a3ee32fbd120a71249
ALL_CHECKS_PASSED

Selected exact counting values are:

| \(x\) | \(S(x)\) | \(S(x)\log_2x(\log_3x)^2/x\) | |---:|---:|---:| | \(10^3\) | 16 | 0.030922315743 | | \(10^4\) | 131 | 0.029086281163 | | \(10^5\) | 1129 | 0.027586780338 | | \(10^6\) | 10204 | 0.026793580695 |

These rows and hashes are (d). They verify the implementation and the finite primitive set, not the asymptotic estimate (14). At these small logarithmic scales the iterated-log convention \(\log_1x=\max\{1,\log x\}\) also clips \(\log_3x\), so the table should not be read as numerical evidence for a limiting constant.

Verified outcome

The full arbitrary-sequence problem, the historically intended gcd-free special case, and sufficiency for the final scale question remain open. The verified progress is:

  1. (a) the live gcd wording has two inequivalent readings; the literal comment reading is trivial, while the original source uses incomparable inputs;
  2. (b) an iff criterion is proved for the broad smooth family (2), giving the sharp concrete boundary (8)–(9);
  3. (a)+(b) an explicit infinite marker-prime construction is given, elementary-primitivity checked from scratch, with \(a_n\asymp n\log_2n(\log_3n)^2\);
  4. (a) every sequence in the final question must satisfy the additional explicit obstruction \(\sum_i1/n_i<\infty\);
  5. (a) compactness reductions isolate the exact uniform finite-antichain lemmas still missing.

PARTIAL: Proved the necessary condition \(\sum_i1/n_i<\infty\) for the final scale question and an iff theorem for \(b_n\asymp n\log_2n\log_3n\,L(\log_2n)\), with an explicit independently checked primitive construction; the arbitrary and intended gcd-free cases remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger