Primitive sets (antichains in the divisibility poset: no element divides another)

Statement

A set $A\subset\mathbb N_{>1}$ is primitive (equivalently: a divisor-antichain, equivalently: an antichain in the divisibility poset $(\mathbb N,\mid)$) if no element of $A$ divides another: for all $a,b\in A$ with $a\mid b$, necessarily $a=b$.

- Canonical examples: the primes $\mathcal P$; $\mathbb N_k:=\{n:\Omega(n)=k\}$, the integers with exactly $k$ prime factors counted with multiplicity, for any fixed $k\ge0$ (so $\mathbb N_1=\mathcal P$); any dyadic-type interval $(x,2x]\cap\mathbb Z$ (no element can divide another since the ratio of any two distinct elements is $<2$); the perfect numbers; and, historically first, the *primitive abundant numbers* (abundant numbers none of whose proper divisors are themselves abundant). - Erdős's foundational 1935 theorem: for the weight $\nu_0(a):=1/(a\log a)$, the sum $f(A):=\sum_{a\in A}\nu_0(a)$ is uniformly bounded over all primitive sets $A$: $\sup_A f(A)<\infty$. This is not obvious — a primitive set can have positive upper density and even be infinite while staying "spread out" only in the divisibility sense, not in the ordinary integer-density sense — and it is the fact that makes "primitive sets" a coherent extremal-combinatorics object in the first place (source: Lichtman, arXiv:2202.02384, §1, quoting/restating Erdős 1935). - Erdős primitive set conjecture (1986, in print since ≥1974): is $f(A)$ maximized, over all primitive sets $A$, by $A=\mathcal P$, i.e. does $f(A)\le f(\mathcal P)=\sum_p 1/(p\log p)\approx1.6366$ hold for every primitive $A$? — Proved YES by Lichtman 2022/2023 (arXiv:2202.02384) and reproved with a shorter, unifying argument by Alexeev–Barreto–Li–Lichtman–Price–Shah–Tang–Tao 2026 (arXiv:2605.00301). Full detail: Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n). - Chain/antichain duality (the general mechanism underlying essentially every primitive-set extremal result): a *divisibility chain* is a sequence $1<d_1<d_2<\cdots$ with $d_j\mid d_{j+1}$ for all $j$ — the dual object to a primitive set. Because a primitive set is by definition an antichain, any single divisibility chain meets any given primitive set in at most one point. This one fact is the entire combinatorial content of "primitive," and it converts every "bound a weighted sum over an arbitrary primitive set" question into a dual question about chains/random walks on the divisibility poset (see Technique).

Facts

- Historical origin: the notion traces to the 1930s study of *abundant numbers* (integers whose proper-divisor sum exceeds the integer). Davenport (1933) proved by heavy analytic (density) methods that the abundant numbers have positive asymptotic density; Erdős found an elementary proof by restricting to the *primitive* abundant numbers (abundant numbers with no abundant proper divisor) — automatically an antichain under divisibility — and this restriction-to-an-antichain trick is what motivated defining "primitive set" as an abstract object worth studying in its own right (arXiv:2202.02384, §1). - Behrend/Erdős 1935 density fact: the lower asymptotic (natural) density of any primitive set is always $0$ — an infinite primitive set can never be "dense" in the ordinary sense, only in weighted/logarithmic senses. - Behrend's inequality (the classical bound on the harmonic-type sum, as opposed to the doubly-logarithmic $f(A)$): for primitive $A$, $\frac1{\log N}\sum_{n\in A,n\le N}\frac1n \ll \frac1{\sqrt{\log\log N}}\to0$, witnessed extremally by $A=\{$integers in $[\sqrt N,N]$ divisible by some prime $>\sqrt N\}$ (cited in wiki/problems/858.md's Facts, sourced to erdosproblems.com/858 remark text quoting Behrend [Be35]). - History of bounds on $f(A)$ before the conjecture was settled: trivial $e^\gamma\approx1.781$-type bound implicit in Erdős's 1935 method $\to$ Erdős–Zhang (1993): $f(A)<1.84$ for all primitive $A$ $\to$ Lichtman–Pomerance (2019, arXiv:1806.02250, *Proc. AMS Ser. B*): $f(A)<e^\gamma\approx1.781$ (also connected there to prime-counting-function "prime races" $\pi(x)$ vs. $\mathrm{li}(x)$) $\to$ Lichtman (2022/2023, arXiv:2202.02384): $f(A)\le f(\mathcal P)\approx1.6366$, matching the conjectured exact extremal value. - Davenport–Erdős theorem (1937): if $A\subset\mathbb N$ has positive upper *logarithmic* density, then $A$ contains an infinite divisibility chain. Erdős–Sárközy–Szemerédi (1966) quantified this: any such chain $D$ can be found growing no faster than $\sum_{d\in D,d\le y}1/d\gg\sqrt{\log\log y}$ along a subsequence, and this rate is best possible (WebSearch-sourced, not independently primary-verified this pass). - **Erdős–Sárközy–Szemerédi "large numbers" tail refinement (1966/1970, Erdős–Sárközy–Szemerédi (1966/1970) — primitive sets of large numbers: the tail Erdős-sum bound $\sum_{a\in A,\,a>x}1/(a\log a) < 1+o(1)$): for primitive $A\subset[x,\infty)$, is $\sum_{a\in A,a>x}1/(a\log a)<1+o(1)$ as $x\to\infty$ (the $x=1$ case recovering the #164 conjecture, threshold $1$ replacing $f(\mathcal P)$)? — Proved YES**, sharp form $1+O(1/\log x)$, first solved by an autonomous run of GPT-5.4 Pro (prompted by co-author Liam Price), written up in Alexeev et al., arXiv:2605.00301 (2026). Full detail: Erdős–Sárközy–Szemerédi (1966/1970) — primitive sets of large numbers: the tail Erdős-sum bound $\sum_{a\in A,\,a>x}1/(a\log a) < 1+o(1)$. - Companion resolved problems in the same 2026 paper: Erdős #1217 (a divisibility-chains conjecture), a revised Banks–Martin "master conjecture," and "$2$ is Erdős-strong" (every odd prime, and $2$, individually maximizes $f$ restricted to primitive sets with that least prime factor) — all cracked by the *same* von Mangoldt-chain machine (arXiv:2605.00301, per wiki/problems/164.md). - Weakenings and generalizations, still partly open: Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — Erdős's real-valued "integer dilation approximation" generalization ($|kx-y|\ge1$ for all distinct $x,y\in A$, $k\in\mathbb N$) — partially resolved: one of two sub-questions proved in full generality by Koukoulopoulos–Lamzouri–Lichtman (arXiv:2502.09539, 2025) via *GCD-graph* machinery imported from the Koukoulopoulos–Maynard proof of the Duffin–Schaeffer conjecture; the other sub-question and the "is $A$ sparse" umbrella question remain open. Erdős #858 — max Erdős-sum over sets avoiding \"a·t=b, spf(t)>a\" chains — a strictly *weaker* chain-avoidance condition than primitivity ("no $a,b\in A$ with $b=at$, $\mathrm{spf}(t)>a$") — solved, extremal constant $c\approx0.6187712111\ldots$ (vs. Behrend's decay-to-$0$ for genuine primitivity), by Chojecki + GPT-5.4 Pro (2026) via a flow-network/discrete-divergence-theorem argument built on the #1196 von Mangoldt-chain technique. - Extremal combinatorics of finite primitive sets (structure, not sums): the maximum-size primitive subset of $\{1,\dots,2n\}$ has size (at least) $n$, witnessed by the interval $(n,2n]$ (no element of a set with max/min ratio $<2$ can divide another). The Cameron–Erdős conjecture on *counting* primitive sets — that $f(n):=$ the number of primitive subsets of $\{1,\dots,n\}$ satisfies $\lim_{n\to\infty}f(n)^{1/n}$ exists — was proved by Rodrigo Angelo, arXiv:1711.08107. Liu–Pach–Palincza (per WebSearch snippet of an IBS preprint, not independently fetched) have results on the *number* of maximum-size primitive subsets of $[1,2n]$. - Do not confuse "primitive set" (this divisibility-antichain sense) with: "primitive root," "primitive polynomial," "primitive sequence" (OEIS/combinatorics-on-words usage), or "Sidon set" (a different antichain-flavored but additively-defined extremal object; see Sidon sets / B_2 sets / Golomb rulers) — none of these share the divisibility-poset structure that is the entire content of this concept.

Technique

WHEN it applies: any problem that quantifies over "all sets of integers with no element dividing another" (or a stated weakening/strengthening of that condition) and asks for an extremal bound on a weighted sum, a density, a counting function, or a structural property (chain length, sparsity). This includes essentially the entire Erdős-sum family (#164, #1196, #1217, #858, #143, Banks–Martin) and any future divisibility-antichain question in the same style.

WHY it works (the mechanism — chain/antichain duality): the divisibility relation $\mid$ makes $\mathbb N$ a poset. A primitive set is an antichain in this poset; the dual structures are divisibility chains $n_0\mid n_1\mid n_2\mid\cdots$. The single structural fact that makes everything work is:

> A chain meets any given antichain in at most one point.

This is trivial to prove (two elements of the same chain are comparable, so at most one can survive membership in an antichain) but has enormous leverage: it means that *any* process that distributes "mass" along divisibility chains — deterministically or via a random walk/Markov chain — can never have two units of mass simultaneously "belong to" a fixed primitive set $A$ along the same trajectory. Summing a weighted indicator of $A$-membership over all chain-trajectories therefore telescopes into a single global upper bound, converting "bound a sum over an adversarially-chosen antichain in an unbounded combinatorial family" (hard, extremal-combinatorics-flavored) into "bound the total mass pushed through one fixed, explicitly constructible stochastic process" (an ordinary, if sometimes delicate, analytic/Dirichlet-series computation). This is a special case of a more general LP/Farkas'-lemma-style duality between weighted antichain bounds and probability distributions over chains (a Stanley chain-polytope argument), stated explicitly as the transferable engine in wiki/problems/164.md's Related section as concept/chain-antichain-duality.

HOW to use it to prove things (recombination steps, following the 2026 von Mangoldt-chain paradigm): 1. Identify the target weight $\nu$ on $\mathbb N$ — usually the summand of whatever Erdős-sum-type quantity is being bounded (e.g. $\nu_0(n)=1/(n\log n)$ for #164/#1196; $1/n$ for #858). 2. Construct a Markov chain on $\mathbb N$ (or the relevant sub-poset) that only ever moves along divisibility relations — e.g. the von Mangoldt downward chain: from $n$, move to $n/q$ with probability $\Lambda(q)/\log n$ for each divisor $q\mid n$ (a valid distribution exactly because $\sum_{q\mid n}\Lambda(q)=\log n$, the identity $\Lambda*1=\log$). Every sample path is a strictly decreasing divisibility chain, so step-1's duality fact applies to it directly. 3. Show the target weight is invariant or sub-invariant under the chain (a "downward hitting mass" $h_{b\downarrow}(n)$ construction): choose an initial mass distribution $b$ so that $h_{b\downarrow}(n)=\nu(n)$ exactly (or $\ge$), typically via a divisor-sum correction and an inductive/telescoping identity. 4. Conclude $\sum_{n\in A}\nu(n)\le\sum_{n_0}b(n_0)$ for every primitive (or antichain-respecting) $A$ simultaneously — the extremal bound falls out as a single computation on the fixed chain, no case analysis over choices of $A$ needed. 5. Re-plumb the same chain for related problems: absorbing at a different set (primes instead of $1$), reversing to the *adjoint upward chain*, or restricting the allowed divisors $q$ (e.g. prime-only steps with reweighted probabilities $\beta_p=p/(p-2)$ for Banks–Martin) turns *one* chain construction into a "master key" solving an entire cluster of related extremal problems at once — this is exactly what arXiv:2605.00301 does across #164, #1196, #1217, and Banks–Martin in a single paper. 6. For weaker-than-primitive conditions (e.g. #858's chain-avoidance, not full divisibility-antichain), the same duality survives if the "chain" relation is re-defined to match the weaker condition exactly (a canonical unique-factorization/"first-violation" rule replacing plain divisibility) — the resulting flow is a *functional graph* (out-degree $1$ everywhere), and the discrete divergence theorem plays the role of step 4's telescoping sum. 7. For genuinely different (non-Erdős-sum) primitive-set questions — e.g. bounding the *size* or *count* of finite primitive subsets of $\{1,\dots,n\}$, as opposed to a weighted infinite sum — the relevant tool is instead direct extremal combinatorics (the dyadic-interval construction $(n,2n]$ for size; generating-function/counting arguments à la Angelo's Cameron–Erdős proof for enumeration), not the Markov-chain duality above; match the tool to whether the question is "bound a weighted sum over antichains" (chain duality) or "bound the size/count of antichains" (direct extremal combinatorics).

Portable lesson: whenever a problem quantifies over "all antichains under a partial order" (divisibility is the classical case, but the recipe is order-agnostic) and asks for an extremal weighted-sum bound, check first whether the order admits a natural random walk/flow that visits each antichain-respecting object at most once per trajectory. If so, the entire extremal problem collapses from "control an adversarial combinatorial family" to "compute one potential/hitting-mass integral for a single fixed process" — this is the reusable move that, per the authors of arXiv:2605.00301, had been "overlooked by the prior literature since Erdős's seminal 1935 paper" until an LLM (GPT-5.4 Pro) suggested trying it.

Related

- Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) — the original Erdős primitive set conjecture: primes maximize $f(A)=\sum1/(a\log a)$ over all primitive sets. Proved (Lichtman 2022/2023; reproved shorter via the von Mangoldt-chain method, 2026). The canonical worked example of the Technique above. - Erdős–Sárközy–Szemerédi (1966/1970) — primitive sets of large numbers: the tail Erdős-sum bound $\sum_{a\in A,\,a>x}1/(a\log a) < 1+o(1)$ — Erdős–Sárközy–Szemerédi tail-sum refinement of #164 for primitive sets of large numbers. Proved, sharp form, first solved autonomously by GPT-5.4 Pro. The page where the von Mangoldt-chain technique is documented in full mechanical detail (transition rule, sub-invariance, hitting-mass inequality). - Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — real-valued "integer dilation approximation" generalization of primitivity. Partially resolved via a *different* toolkit (GCD graphs, imported from the Duffin–Schaeffer-conjecture proof), useful contrast for when chain-duality does vs. doesn't directly transplant. - Erdős #858 — max Erdős-sum over sets avoiding \"a·t=b, spf(t)>a\" chains — a strictly weaker-than-primitive chain-avoidance condition. Solved via a flow-network/discrete-divergence-theorem variant of the same duality idea, extremal constant $c\approx0.6187712111$. - concept/chain-antichain-duality — the general Stanley chain-polytope / LP-duality principle behind step 1 of the Technique above (referenced from wiki/problems/164.md; not yet its own page in this wiki). - concept/von-mangoldt-markov-chain — the specific downward chain $\mathbb P(n\downarrow n/q)=\Lambda(q)/\log n$ and its sub-invariance argument (referenced from wiki/problems/164.md and wiki/problems/1196.md; not yet its own page in this wiki). - GCD graphs (Koukoulopoulos–Maynard graph-theoretic sieve) — the Koukoulopoulos–Maynard/Duffin–Schaeffer-derived graph technique used for the still-open first sub-question of Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?; the toolkit to reach for when chain-duality does *not* directly apply. - Dilworth's theorem (chain/antichain decomposition of a poset) and its dual, Mirsky's theorem — the finite-poset chain/antichain *decomposition* theorem (width = min chain cover); a structurally related but logically distinct fact about posets in general (Dilworth decomposes a whole finite poset into chains realizing the max antichain size, whereas the primitive-set duality bounds a *weighted sum* over one arbitrary infinite antichain via a probabilistic chain construction) — worth distinguishing explicitly since both are "chain vs. antichain" results on posets but solve different kinds of problems. - Sidon sets / B_2 sets / Golomb rulers — a different, additively-defined (not divisibility-defined) extremal antichain-flavored object; not to be confused with primitive sets despite superficial "no bad pairwise relation" similarity.