Statement of the criterion
Write N={1,2,…} and N0={0,1,2,…}. For A⊆N, let
MA={n∈N:a∣n for some a∈A}.(1)
For B⊆N, its lower natural density is
d(B)=x→∞liminfx∣B∩[1,x]∣.
When the corresponding limit exists, it is denoted by d(B). A set A is called a Behrend sequence when d(MA)=1. Erdős asked for a necessary and sufficient condition for this property [2 p. 77].
Let p1<p2<⋯ be the primes, and let vp(n) denote the exponent of p in n. For ℓ∈N0, define the prime-prefix projection
πℓ(n)=i≤ℓ∏pivpi(n).(2)
For integers 0≤r≤s, put
Hr,s={n∈N:vpi(n)=0 whenever i∈/(r,s]},Qr,s=r<i≤s∏(1−pi1).(3)
Empty products equal one, so π0(n)=1, Hr,r={1}, and Qr,r=1. A set S⊆N is divisor closed if n∈S and d∣n imply d∈S.
Theorem 1.1. For every A⊆N, the following are equivalent.
(i) The set MA has natural density one.
(ii) For every admissible family (ℓk,Sk)k≥0 in Definition 1.2,
A∩k≥0⋃Sk=∅.(4)
Definition 1.2. An admissible family consists of integers
0≤ℓ0<ℓ1<ℓ2<⋯ and finite sets Sk⊆N, k∈N0, satisfying S0={1} and the following conditions for every k≥1.
(i) Sk is divisor closed and Sk⊆Hℓ0,ℓk.
(ii) πℓk−1(Sk)⊆Sk−1.
(iii) For every m∈Sk−1, the finite set
Fk(m)={n∈Hℓk−1,ℓk:mn∈Sk}(5) satisfies
Qℓk−1,ℓkn∈Fk(m)∑n1≥1−2−k−2.(6) The definition of an admissible family is independent of A. Each condition at a fixed level involves finite sets, prime factorization, and finite reciprocal sums. The multiplier 1 is permitted in (1.5). The fibers may depend on the parent m.
Lemma 1.3. Every admissible family satisfies Sk−1⊆Sk for k≥1. Each fiber Fk(m) is nonempty and divisor closed. If m′,m∈Sk−1 and m′∣m, then Fk(m)⊆Fk(m′).
Proof. The right-hand side of (1.6) is positive, so Fk(m) is nonempty. If n∈Fk(m) and d∣n, then md∣mn. Divisor closure of Sk gives md∈Sk, and d has the required prime support. Thus d∈Fk(m). In particular 1∈Fk(m), so m∈Sk. Finally, if m′∣m and n∈Fk(m), then m′n∣mn, giving n∈Fk(m′). □
Prime valuations and the density transfer
Let V1,V2,… be independent random variables with
P(Vi=e)=(1−pi1)pi−e,e∈N0.(7)
We work on the product probability space Ω=N0N with these coordinate laws. For a∈N, write a∣V when vpi(a)≤Vi for every i. This event depends on finitely many coordinates. Define
C=CA={V:a∤V for every a∈A}.(8)
The event C is measurable and is downward closed in the coordinatewise order on Ω.
For ℓ∈N0 and 0≤r≤s, let
Xℓ=i≤ℓ∏piVi,Yr,s=r<i≤s∏piVi.
Independence gives the exact distributions
P(Xℓ=m)=mQ0,ℓ(m∈H0,ℓ),P(Yr,s=n)=nQr,s(n∈Hr,s).(9)
In particular, every finite-prefix cylinder has positive probability. We denote the second probability in (2.3) by νr,s(n). Then
n∈Hr,s∑νr,s(n)=1.(10)
Lemma 2.1. For every finite F⊆N,
P(a∣V for some a∈F)=d(MF).(11)
Proof. For e∈N0, summing (7) gives P(Vi≥e)=pi−e. Consequently, for every nonempty finite J⊆N,
P(a∣V for every a∈J)=i∏pi−vpi(lcm(J))=lcm(J)1.
The positive integers divisible by every member of J are precisely the multiples of lcm(J), and their density is the same quantity. Applying finite inclusion-exclusion to both sides gives
P(a∣V for some a∈F)=∅=J⊆F∑lcm(J)(−1)∣J∣+1=d(MF).
The assertion for F=∅ is immediate. □
We use the classical finite-approximation theorem of Davenport and Erdős [1].
Theorem 2.2 (Davenport–Erdős). For every A⊆N, with At=A∩{1,…,t},
d(MA)=t→∞limd(MAt).(12)
Corollary 2.3. For every A⊆N,
P(CA)=1−d(MA).(13) In particular,
d(MA)=1⟺P(CA)=0.(14)
Proof. The events {V:a∣V for some a∈At} increase to CA. Continuity from below, Lemma 2.1, and Theorem 2.2 give (13). A subset of N with lower natural density one has natural density one, because its upper natural density is at most one. This proves (14). □
Positive avoidance from an admissible family
Proposition 3.1. Suppose (ℓk,Sk)k≥0 is admissible and A∩Sk=∅ for every k. Then
P(CA)≥43Q0,ℓ0>0.(15)
Proof. Set Ek={V:Xℓk∈Sk}. Since S0={1}, we have P(E0)=Q0,ℓ0. The projection condition in Definition 1.2 gives Ek⊆Ek−1. For each m∈Sk−1, the new block Yℓk−1,ℓk is independent of Xℓk−1. Equations (9) and (6) therefore give
P(Ek)=m∈Sk−1∑P(Xℓk−1=m)n∈Fk(m)∑νℓk−1,ℓk(n)≥(1−2−k−2)P(Ek−1).(16)
For uj∈[0,1], induction gives ∏j=1k(1−uj)≥1−∑j=1kuj. Hence
P(Ek)≥Q0,ℓ0j=1∏k(1−2−j−2)≥43Q0,ℓ0.
Continuity from above yields
P(k≥0⋂Ek)≥43Q0,ℓ0.(17)
We claim that ⋂k≥0Ek⊆CA. Indeed, let V belong to this intersection and suppose a∈A divides V. The integer a has finitely many prime divisors, and ℓk→∞. Thus a∣Xℓk for all sufficiently large k. Since Xℓk∈Sk and Sk is divisor closed, it follows that a∈Sk. This contradicts A∩Sk=∅. The claim and (17) prove (15). □
Finite-prefix extraction
For m∈H0,ℓ, define
hℓ(m)=P(CA∣Xℓ=m).(18)
The conditioning is legitimate by (9). Equivalently, fix the first ℓ prime exponents to those of m and sample the remaining coordinates according to (7). Let
Cℓ={V:a∤Xℓ for every a∈A}.(19)
Then Cℓ↓CA. Indeed, any integer dividing V divides Xℓ once the prefix contains all of its prime divisors.
Lemma 4.1. For every ℓ∈N0,
(i) 0≤hℓ(m)≤1 for m∈H0,ℓ.
(ii) If m′,m∈H0,ℓ and m′∣m, then hℓ(m′)≥hℓ(m).
(iii) If some a∈A divides m, then hℓ(m)=0.
(iv) E[hℓ(Xℓ)]=P(CA).
Proof. The first assertion follows from the definition as a conditional probability. For the second, use the same future prime exponents with prefixes m′ and m. The first complete valuation vector is coordinatewise no larger than the second. Downward closure of CA shows that survival for the second implies survival for the first. For the third, every completion of the prefix m remains divisible by a. The last assertion is the law of total probability applied to the countable partition {Xℓ=m}. □
Lemma 4.2. If c=P(CA)>0, then hℓ(1)→1 as ℓ→∞.
Proof. By Lemma 4.1, the function hℓ is at most hℓ(1) and vanishes on prefixes outside Cℓ. Consequently,
c=E[hℓ(Xℓ)]≤hℓ(1)P(Cℓ).
Since P(Cℓ)↓c>0,
1≥hℓ(1)≥P(Cℓ)c⟶1.
□
Lemma 4.3. Let r∈N0, let G⊆H0,r be finite, and let 0<δ<1. There exist ℓ>r and, for each m∈G, a finite set Nm⊆Hr,ℓ such that
hℓ(mn)≥1−δ(n∈Nm)(20) n∈Nm∑νr,ℓ(n)>hr(m)−2δ.(21) The cutoff ℓ is common to all m∈G.
Proof. Fix m∈G and write Pm and Em for probability and expectation conditional on Xr=m. For ℓ≥r, we have Xr=πr(Xℓ). The tower property and Lemma 4.1(iii) give
Dℓ(m):=Em[(1−hℓ(Xℓ))1Cℓ]=Pm(Cℓ)−hr(m).(22)
Indeed, hℓ(Xℓ) vanishes off Cℓ and has conditional expectation hr(m) under Pm. Continuity from above gives Pm(Cℓ)↓Pm(CA)=hr(m), and therefore Dℓ(m)→0. Since G is finite, choose a common ℓ>r such that
Dℓ(m)<δ2(m∈G).(23)
On Cℓ∩{hℓ(Xℓ)<1−δ}, the integrand in (22) is greater than δ. It follows that
Pm(Cℓ∩{hℓ(Xℓ)<1−δ})<δ.
The event {hℓ(Xℓ)≥1−δ} is contained in Cℓ, because δ<1 and hℓ vanishes on unsafe prefixes. Thus
Pm(hℓ(Xℓ)≥1−δ)>Pm(Cℓ)−δ≥hr(m)−δ.(24)
Under Pm, the new multiplier Yr,ℓ has the law νr,ℓ, and Xℓ=mYr,ℓ. Consequently, the probability on the left of (24) is the sum of νr,ℓ(n) over
{n∈Hr,ℓ:hℓ(mn)≥1−δ}.
This is a convergent series of nonnegative terms. Choose a finite subset Nm whose sum is greater than that series minus δ. Equations (20) and (21) follow. □
Construction of an avoiding family
Proposition 5.1. If P(CA)>0, then there exists an admissible family (ℓk,Sk)k≥0 such that A∩Sk=∅ for every $k.
Proof. Set
δk=2−k−5(k≥0).(25)
By Lemma 4.2, choose ℓ0 with hℓ0(1)≥1−δ0, and put S0={1}. Lemma 4.1(iii) gives A∩S0=∅. We construct the family inductively, maintaining
hℓk(s)≥1−δk(s∈Sk).(26)
Suppose that ℓk−1 and the finite divisor-closed set Sk−1⊆Hℓ0,ℓk−1 have been chosen. Apply Lemma 4.3 with
r=ℓk−1,G=Sk−1,δ=δk.
It gives ℓk>ℓk−1 and finite sets Nm⊆Hℓk−1,ℓk for m∈Sk−1. Let
Tk=m∈Sk−1⋃{mn:n∈Nm},Sk=Div(Tk)={d∈N:d∣t for some t∈Tk}.(27)
The set Sk is finite and divisor closed, and its elements use only primes in (ℓ0,ℓk]. If d∣mn with m∈Sk−1 and n∈Nm, then πℓk−1(d)∣m, because n uses only primes with indices greater than ℓk−1. Divisor closure of Sk−1 therefore gives
πℓk−1(d)∈Sk−1.
This verifies the projection condition. Moreover, Lemma 4.1(ii) and (20) imply
hℓk(d)≥hℓk(mn)≥1−δk.
Thus (26) holds at level k. Since $1-\delta_k>0$, Lemma 4.1(iii) shows that no element of Sk has a divisor in A. In particular $A\cap S_k=\varnothing. For every m∈Sk−1, the inclusion mNm⊆Sk gives Nm⊆Fk(m). Using (21) and the induction hypothesis, we obtain
Qℓk−1,ℓkn∈Fk(m)∑n1≥n∈Nm∑νℓk−1,ℓk(n)>hℓk−1(m)−2δk≥1−δk−1−2δk=1−2−k−3≥1−2−k−2.(28)
The lower bound is positive, so every Nm is nonempty. All conditions of Definition 1.2 have now been verified, completing the induction. □
Proof of Theorem 1.1. Suppose d(MA)=1. By Corollary 2.3, P(CA)=0. If an admissible family were disjoint from A at every level, Proposition 3.1 would give P(CA)>0. Hence every admissible family meets A.
Conversely, suppose A meets every admissible family. If MA failed to have natural density one, Corollary 2.3 would give P(CA)>0. Proposition 5.1 would then produce an admissible family disjoint from A at every level, a contradiction. Therefore d(MA)=1. □
Acknowledgments
Artificial-intelligence tools provided by OpenAI assisted with mathematical exploration, checking arguments, and preparation of the manuscript.