betaFeedback

WorksMathematics

A divisor-closed criterion for Behrend sequences

Abstract

We give a necessary and sufficient condition for a set of positive integers to be a Behrend sequence. The condition quantifies over sequences of finite divisor-closed sets supported on consecutive prime blocks. For each element at one level, its permitted extensions at the next level retain a prescribed reciprocal mass. We prove that the set of multiples of AA has natural density one if and only if AA meets every such family. The proof combines the classical Davenport–Erdős finite-approximation theorem with a finite pruning argument for independent geometric prime valuations.

Statement of the criterion

Write N={1,2,…}\mathbb{N} = \{1,2,\ldots\} and N0={0,1,2,…}\mathbb{N}_0 = \{0,1,2,\ldots\}. For A⊆NA \subseteq\mathbb{N}, let

MA={n∈N:a∣n for some a∈A}.(1)M_A = \{n \in\mathbb{N} : a \mid n \text{ for some } a \in A\}. \tag*{(1)}

For B⊆NB \subseteq\mathbb{N}, its lower natural density is

d(B)=lim inf⁡x→∞∣B∩[1,x]∣x.d(B) = \liminf_{x\to\infty} \frac{|B \cap[1,x]|}{x}.

When the corresponding limit exists, it is denoted by d(B)d(B). A set AA is called a Behrend sequence when d(MA)=1d(M_A) = 1. Erdős asked for a necessary and sufficient condition for this property [2 p. 77].

Let p1<p2<⋯p_1 < p_2 < \cdots be the primes, and let vp(n)v_p(n) denote the exponent of pp in nn. For ℓ∈N0\ell\in\mathbb{N}_0, define the prime-prefix projection

πℓ(n)=∏i≤ℓpivpi(n).(2)\pi_\ell(n) = \prod_{i\leq\ell} p_i^{v_{p_i}(n)}. \tag*{(2)}

For integers 0≤r≤s0 \leq r \leq s, put

Hr,s={n∈N:vpi(n)=0 whenever i∉(r,s]},Qr,s=∏r<i≤s(1−1pi).(3)H_{r,s} = \{n \in\mathbb{N} : v_{p_i}(n) = 0\text{ whenever }i \notin(r,s]\}, \qquad Q_{r,s} = \prod_{r<i\leq s}\left(1-\frac{1}{p_i}\right). \tag*{(3)}

Empty products equal one, so π0(n)=1\pi_0(n) = 1, Hr,r={1}H_{r,r} = \{1\}, and Qr,r=1Q_{r,r} = 1. A set S⊆NS \subseteq\mathbb{N} is divisor closed if n∈Sn \in S and d∣nd \mid n imply d∈Sd \in S.

Theorem 1.1. For every A⊆NA \subseteq\mathbb{N}, the following are equivalent.

(i) The set MAM_A has natural density one.

(ii) For every admissible family (ℓk,Sk)k≥0(\ell_k,S_k)_{k\geq0} in Definition 1.2,

A∩⋃k≥0Sk≠∅.(4)A \cap\bigcup_{k\geq0} S_k \ne\varnothing. \tag*{(4)}

Definition 1.2. An admissible family consists of integers

0≤ℓ0<ℓ1<ℓ2<⋯0 \le\ell_0 < \ell_1 < \ell_2 < \cdots

and finite sets Sk⊆NS_k \subseteq\mathbb{N}, k∈N0k \in\mathbb{N}_0, satisfying S0={1}S_0 = \{1\} and the following conditions for every k≥1k \ge1.

(i) SkS_k is divisor closed and Sk⊆Hℓ0,ℓkS_k \subseteq\mathcal{H}_{\ell_0,\ell_k}.

(ii) πℓk−1(Sk)⊆Sk−1\pi_{\ell_{k-1}}(S_k) \subseteq S_{k-1}.

(iii) For every m∈Sk−1m \in S_{k-1}, the finite set

Fk(m)={n∈Hℓk−1,ℓk:mn∈Sk}(5)F_k(m) = \{n \in\mathcal{H}_{\ell_{k-1},\ell_k} : mn \in S_k\} \tag*{(5)}

satisfies

Qℓk−1,ℓk∑n∈Fk(m)1n≥1−2−k−2.(6)Q_{\ell_{k-1},\ell_k} \sum_{n \in F_k(m)} \frac{1}{n} \ge1 - 2^{-k-2}. \tag*{(6)}

The definition of an admissible family is independent of AA. Each condition at a fixed level involves finite sets, prime factorization, and finite reciprocal sums. The multiplier 11 is permitted in (1.5). The fibers may depend on the parent mm.

Lemma 1.3. Every admissible family satisfies Sk−1⊆SkS_{k-1} \subseteq S_k for k≥1k \ge1. Each fiber Fk(m)F_k(m) is nonempty and divisor closed. If m′,m∈Sk−1m',m \in S_{k-1} and m′∣mm' \mid m, then Fk(m)⊆Fk(m′)F_k(m) \subseteq F_k(m').

Proof. The right-hand side of (1.6) is positive, so Fk(m)F_k(m) is nonempty. If n∈Fk(m)n \in F_k(m) and d∣nd \mid n, then md∣mnmd \mid mn. Divisor closure of SkS_k gives md∈Skmd \in S_k, and dd has the required prime support. Thus d∈Fk(m)d \in F_k(m). In particular 1∈Fk(m)1 \in F_k(m), so m∈Skm \in S_k. Finally, if m′∣mm' \mid m and n∈Fk(m)n \in F_k(m), then m′n∣mnm'n \mid mn, giving n∈Fk(m′)n \in F_k(m'). □

Prime valuations and the density transfer

Let V1,V2,…V_1,V_2,\ldots be independent random variables with

P(Vi=e)=(1−1pi)pi−e,e∈N0.(7)\mathbb{P}(V_i=e)=\left(1-\frac{1}{p_i}\right)p_i^{-e}, \qquad e \in\mathbb{N}_0. \tag*{(7)}

We work on the product probability space Ω=N0N\Omega= \mathbb{N}_0^{\mathbb{N}} with these coordinate laws. For a∈Na \in\mathbb{N}, write a∣Va \mid V when vpi(a)≤Viv_{p_i}(a) \le V_i for every ii. This event depends on finitely many coordinates. Define

C=CA={V:a∤V for every a∈A}.(8)C=C_A=\{V:a\nmid V\text{ for every }a\in A\}. \tag*{(8)}

The event CC is measurable and is downward closed in the coordinatewise order on Ω\Omega.

For ℓ∈N0\ell\in\mathbb{N}_0 and 0≤r≤s0 \le r \le s, let

Xℓ=∏i≤ℓpiVi,Yr,s=∏r<i≤spiVi.X_\ell=\prod_{i\le\ell}p_i^{V_i}, \qquad Y_{r,s}=\prod_{r<i\le s}p_i^{V_i}.

Independence gives the exact distributions

P(Xℓ=m)=Q0,ℓm(m∈H0,ℓ),P(Yr,s=n)=Qr,sn(n∈Hr,s).(9)\mathbb{P}(X_\ell=m)=\frac{Q_{0,\ell}}{m}\quad(m\in\mathcal{H}_{0,\ell}), \qquad \mathbb{P}(Y_{r,s}=n)=\frac{Q_{r,s}}{n}\quad(n\in\mathcal{H}_{r,s}). \tag*{(9)}

In particular, every finite-prefix cylinder has positive probability. We denote the second probability in (2.3) by νr,s(n)\nu_{r,s}(n). Then

∑n∈Hr,sνr,s(n)=1.(10)\sum_{n\in\mathcal{H}_{r,s}}\nu_{r,s}(n)=1. \tag*{(10)}

Lemma 2.1. For every finite F⊆NF \subseteq\mathbb{N},

P(a∣V for some a∈F)=d(MF).(11)\mathbb{P}(a \mid V\text{ for some }a \in F)=d(M_F). \tag*{(11)}

Proof. For e∈N0e \in\mathbb{N}_0, summing (7) gives P(Vi≥e)=pi−e\mathbb{P}(V_i \ge e)=p_i^{-e}. Consequently, for every nonempty finite J⊆NJ \subseteq\mathbb{N},

P(a∣V for every a∈J)=∏ipi−vpi(lcm⁡(J))=1lcm⁡(J).\mathbb{P}(a \mid V\text{ for every }a \in J)=\prod_i p_i^{-v_{p_i}(\operatorname{lcm}(J))}=\frac{1}{\operatorname{lcm}(J)}.

The positive integers divisible by every member of JJ are precisely the multiples of lcm⁡(J)\operatorname{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(−1)∣J∣+1lcm⁡(J)=d(MF).\mathbb{P}(a \mid V\text{ for some }a \in F)=\sum_{\varnothing\ne J\subseteq F}\frac{(-1)^{|J|+1}}{\operatorname{lcm}(J)}=d(M_F).

The assertion for F=∅F=\varnothing is immediate. □

We use the classical finite-approximation theorem of Davenport and Erdős [1].

Theorem 2.2 (Davenport–Erdős). For every A⊆NA \subseteq\mathbb{N}, with At=A∩{1,…,t}A_t=A\cap\{1,\ldots,t\},

d(MA)=lim⁡t→∞d(MAt).(12)d(M_A)=\lim_{t\to\infty}d(M_{A_t}). \tag*{(12)}

Corollary 2.3. For every A⊆NA \subseteq\mathbb{N},

P(CA)=1−d(MA).(13)\mathbb{P}(C_A)=1-d(M_A). \tag*{(13)}

In particular,

d(MA)=1⟺P(CA)=0.(14)d(M_A)=1\Longleftrightarrow\mathbb{P}(C_A)=0. \tag*{(14)}

Proof. The events {V:a∣V for some a∈At}\{V:a\mid V\text{ for some }a\in A_t\} increase to CAC_A. Continuity from below, Lemma 2.1, and Theorem 2.2 give (13). A subset of N\mathbb{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(\ell_k,S_k)_{k\ge0} is admissible and A∩Sk=∅A\cap S_k=\varnothing for every kk. Then

P(CA)≥34Q0,ℓ0>0.(15)\mathbb{P}(C_A)\ge\frac{3}{4}Q_{0,\ell_0}>0. \tag*{(15)}

Proof. Set Ek={V:Xℓk∈Sk}E_k=\{V:X_{\ell_k}\in S_k\}. Since S0={1}S_0=\{1\}, we have P(E0)=Q0,ℓ0\mathbb{P}(E_0)=Q_{0,\ell_0}. The projection condition in Definition 1.2 gives Ek⊆Ek−1E_k\subseteq E_{k-1}. For each m∈Sk−1m\in S_{k-1}, the new block Yℓk−1,ℓkY_{\ell_{k-1},\ell_k} is independent of Xℓk−1X_{\ell_{k-1}}. Equations (9) and (6) therefore give

P(Ek)=∑m∈Sk−1P(Xℓk−1=m)∑n∈Fk(m)νℓk−1,ℓk(n)≥(1−2−k−2)P(Ek−1).(16)\begin{aligned} \mathbb{P}(E_k)=\sum_{m\in S_{k-1}}\mathbb{P}(X_{\ell_{k-1}}=m)\sum_{n\in F_k(m)}\nu_{\ell_{k-1},\ell_k}(n) \\ &\ge(1-2^{-k-2})\mathbb{P}(E_{k-1}). \tag*{(16)} \end{aligned}

For uj∈[0,1]u_j\in[0,1], induction gives ∏j=1k(1−uj)≥1−∑j=1kuj\prod_{j=1}^k(1-u_j)\ge1-\sum_{j=1}^k u_j. Hence

P(Ek)≥Q0,ℓ0∏j=1k(1−2−j−2)≥34Q0,ℓ0.\mathbb{P}(E_k)\ge Q_{0,\ell_0}\prod_{j=1}^k(1-2^{-j-2})\ge\frac{3}{4}Q_{0,\ell_0}.

Continuity from above yields

P(⋂k≥0Ek)≥34Q0,ℓ0.(17)\mathbb{P}\left(\bigcap_{k\ge0}E_k\right)\ge\frac{3}{4}Q_{0,\ell_0}. \tag*{(17)}

We claim that ⋂k≥0Ek⊆CA\bigcap_{k\ge0} E_k \subseteq C_A. Indeed, let VV belong to this intersection and suppose a∈Aa \in A divides VV. The integer aa has finitely many prime divisors, and ℓk→∞\ell_k \to\infty. Thus a∣Xℓka \mid X_{\ell_k} for all sufficiently large kk. Since Xℓk∈SkX_{\ell_k} \in S_k and SkS_k is divisor closed, it follows that a∈Ska \in S_k. This contradicts A∩Sk=∅A \cap S_k = \varnothing. The claim and (17) prove (15). □\square

Finite-prefix extraction

For m∈H0,ℓm \in\mathcal{H}_{0,\ell}, define

hℓ(m)=P(CA∣Xℓ=m).(18)h_\ell(m) = \mathbf{P}(C_A \mid X_\ell= m). \tag*{(18)}

The conditioning is legitimate by (9). Equivalently, fix the first ℓ\ell prime exponents to those of mm and sample the remaining coordinates according to (7). Let

Cℓ={V:a∤Xℓ for every a∈A}.(19)C_\ell= \{V : a \nmid X_\ell\text{ for every } a \in A\}. \tag*{(19)}

Then Cℓ↓CAC_\ell\downarrow C_A. Indeed, any integer dividing VV divides XℓX_\ell once the prefix contains all of its prime divisors.

Lemma 4.1. For every ℓ∈N0\ell\in\mathbb{N}_0,

(i) 0≤hℓ(m)≤10 \le h_\ell(m) \le1 for m∈H0,ℓm \in\mathcal{H}_{0,\ell}.

(ii) If m′,m∈H0,ℓm',m \in\mathcal{H}_{0,\ell} and m′∣mm' \mid m, then hℓ(m′)≥hℓ(m)h_\ell(m') \ge h_\ell(m).

(iii) If some a∈Aa \in A divides mm, then hℓ(m)=0h_\ell(m) = 0.

(iv) E[hℓ(Xℓ)]=P(CA)\mathbf{E}[h_\ell(X_\ell)] = \mathbf{P}(C_A).

Proof. The first assertion follows from the definition as a conditional probability. For the second, use the same future prime exponents with prefixes m′m' and mm. The first complete valuation vector is coordinatewise no larger than the second. Downward closure of CAC_A shows that survival for the second implies survival for the first. For the third, every completion of the prefix mm remains divisible by aa. The last assertion is the law of total probability applied to the countable partition {Xℓ=m}\{X_\ell= m\}. □\square

Lemma 4.2. If c=P(CA)>0c = \mathbf{P}(C_A) > 0, then hℓ(1)→1h_\ell(1) \to1 as ℓ→∞\ell\to\infty.

Proof. By Lemma 4.1, the function hℓh_\ell is at most hℓ(1)h_\ell(1) and vanishes on prefixes outside CℓC_\ell. Consequently,

c=E[hℓ(Xℓ)]≤hℓ(1)P(Cℓ).c = \mathbf{E}[h_\ell(X_\ell)] \le h_\ell(1)\mathbf{P}(C_\ell).

Since P(Cℓ)↓c>0\mathbf{P}(C_\ell) \downarrow c > 0,

1≥hℓ(1)≥cP(Cℓ)⟶1.1 \ge h_\ell(1) \ge\frac{c}{\mathbf{P}(C_\ell)} \longrightarrow1.

□\square

Lemma 4.3. Let r∈N0r \in\mathbb{N}_0, let G⊆H0,rG \subseteq\mathcal{H}_{0,r} be finite, and let 0<δ<10 < \delta< 1. There exist ℓ>r\ell> r and, for each m∈Gm \in G, a finite set Nm⊆Hr,ℓN_m \subseteq\mathcal{H}_{r,\ell} such that

hℓ(mn)≥1−δ(n∈Nm)(20)h_\ell(mn) \ge1-\delta\qquad(n \in N_m) \tag*{(20)}
∑n∈Nmνr,ℓ(n)>hr(m)−2δ.(21)\sum_{n\in N_m} \nu_{r,\ell}(n) > h_r(m)-2\delta. \tag*{(21)}

The cutoff ℓ\ell is common to all m∈Gm \in G.

Proof. Fix m∈Gm \in G and write Pm\mathbf{P}_m and Em\mathbf{E}_m for probability and expectation conditional on Xr=mX_r = m. For ℓ≥r\ell\ge r, we have Xr=πr(Xℓ)X_r = \pi_r(X_\ell). The tower property and Lemma 4.1(iii) give

Dℓ(m):=Em[(1−hℓ(Xℓ))1Cℓ]=Pm(Cℓ)−hr(m).(22)D_\ell(m) := \mathbf{E}_m\left[(1-h_\ell(X_\ell))1_{C_\ell}\right] = \mathbf{P}_m(C_\ell)-h_r(m). \tag*{(22)}

Indeed, hℓ(Xℓ)h_{\ell}(X_{\ell}) vanishes off CℓC_{\ell} and has conditional expectation hr(m)h_r(m) under Pm\mathbf{P}_m. Continuity from above gives Pm(Cℓ)↓Pm(CA)=hr(m)\mathbf{P}_m(C_{\ell}) \downarrow\mathbf{P}_m(C_A) = h_r(m), and therefore Dℓ(m)→0D_{\ell}(m) \to0. Since GG is finite, choose a common ℓ>r\ell> r such that

Dℓ(m)<δ2(m∈G).(23)D_{\ell}(m) < \delta^2 \qquad(m \in G). \tag*{(23)}

On Cℓ∩{hℓ(Xℓ)<1−δ}C_{\ell} \cap\{h_{\ell}(X_{\ell}) < 1-\delta\}, the integrand in (22) is greater than δ\delta. It follows that

Pm(Cℓ∩{hℓ(Xℓ)<1−δ})<δ.\mathbf{P}_m(C_{\ell} \cap\{h_{\ell}(X_{\ell}) < 1-\delta\}) < \delta.

The event {hℓ(Xℓ)≥1−δ}\{h_{\ell}(X_{\ell}) \ge1-\delta\} is contained in CℓC_{\ell}, because δ<1\delta< 1 and hℓh_{\ell} vanishes on unsafe prefixes. Thus

Pm(hℓ(Xℓ)≥1−δ)>Pm(Cℓ)−δ≥hr(m)−δ.(24)\mathbf{P}_m(h_{\ell}(X_{\ell}) \ge1-\delta) > \mathbf{P}_m(C_{\ell})-\delta\ge h_r(m)-\delta. \tag*{(24)}

Under Pm\mathbf{P}_m, the new multiplier Yr,ℓY_{r,\ell} has the law νr,ℓ\nu_{r,\ell}, and Xℓ=mYr,ℓX_{\ell}=mY_{r,\ell}. Consequently, the probability on the left of (24) is the sum of νr,ℓ(n)\nu_{r,\ell}(n) over

{n∈Hr,ℓ:hℓ(mn)≥1−δ}.\{n \in H_{r,\ell}: h_{\ell}(mn) \ge1-\delta\}.

This is a convergent series of nonnegative terms. Choose a finite subset NmN_m whose sum is greater than that series minus δ\delta. Equations (20) and (21) follow. □\square

Construction of an avoiding family

Proposition 5.1. If P(CA)>0\mathbf{P}(C_A)>0, then there exists an admissible family (ℓk,Sk)k≥0(\ell_k,S_k)_{k\ge0} such that A∩Sk=∅A \cap S_k=\varnothing for every $k.

Proof. Set

δk=2−k−5(k≥0).(25)\delta_k = 2^{-k-5} \qquad(k \ge0). \tag*{(25)}

By Lemma 4.2, choose ℓ0\ell_0 with hℓ0(1)≥1−δ0h_{\ell_0}(1) \ge1-\delta_0, and put S0={1}S_0=\{1\}. Lemma 4.1(iii) gives A∩S0=∅A \cap S_0=\varnothing. We construct the family inductively, maintaining

hℓk(s)≥1−δk(s∈Sk).(26)h_{\ell_k}(s) \ge1-\delta_k \qquad(s \in S_k). \tag*{(26)}

Suppose that ℓk−1\ell_{k-1} and the finite divisor-closed set Sk−1⊆Hℓ0,ℓk−1S_{k-1} \subseteq H_{\ell_0,\ell_{k-1}} have been chosen. Apply Lemma 4.3 with

r=ℓk−1,G=Sk−1,δ=δk.r=\ell_{k-1}, \qquad G=S_{k-1}, \qquad\delta=\delta_k.

It gives ℓk>ℓk−1\ell_k>\ell_{k-1} and finite sets Nm⊆Hℓk−1,ℓkN_m \subseteq H_{\ell_{k-1},\ell_k} for m∈Sk−1m \in S_{k-1}. Let

Tk=⋃m∈Sk−1{mn:n∈Nm},Sk=Div⁡(Tk)={d∈N:d∣t for some t∈Tk}.(27)T_k=\bigcup_{m\in S_{k-1}}\{mn:n\in N_m\}, \qquad S_k=\operatorname{Div}(T_k)=\{d\in\mathbb{N}:d\mid t\text{ for some }t\in T_k\}. \tag*{(27)}

The set SkS_k is finite and divisor closed, and its elements use only primes in (ℓ0,ℓk](\ell_0,\ell_k]. If d∣mnd\mid mn with m∈Sk−1m\in S_{k-1} and n∈Nmn\in N_m, then πℓk−1(d)∣m\pi_{\ell_{k-1}}(d)\mid m, because nn uses only primes with indices greater than ℓk−1\ell_{k-1}. Divisor closure of Sk−1S_{k-1} therefore gives

πℓk−1(d)∈Sk−1.\pi_{\ell_{k-1}}(d)\in S_{k-1}.

This verifies the projection condition. Moreover, Lemma 4.1(ii) and (20) imply

hℓk(d)≥hℓk(mn)≥1−δk.h_{\ell_k}(d)\ge h_{\ell_k}(mn)\ge1-\delta_k.

Thus (26) holds at level kk. Since $1-\delta_k>0$, Lemma 4.1(iii) shows that no element of SkS_k has a divisor in AA. In particular $A\cap S_k=\varnothing. For every m∈Sk−1m \in S_{k-1}, the inclusion mNm⊆SkmN_m \subseteq S_k gives Nm⊆Fk(m)N_m \subseteq F_k(m). Using (21) and the induction hypothesis, we obtain

Qℓk−1,ℓk∑n∈Fk(m)1n≥∑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)\begin{aligned} Q_{\ell_{k-1},\ell_k}\sum_{n\in F_k(m)}\frac{1}{n} &\ge\sum_{n\in N_m}\nu_{\ell_{k-1},\ell_k}(n)\\ &>h_{\ell_{k-1}}(m)-2\delta_k\\ &\ge1-\delta_{k-1}-2\delta_k=1-2^{-k-3}\ge1-2^{-k-2}. \tag*{(28)} \end{aligned}

The lower bound is positive, so every NmN_m is nonempty. All conditions of Definition 1.2 have now been verified, completing the induction. □\square

Proof of Theorem 1.1. Suppose d(MA)=1d(M_A)=1. By Corollary 2.3, P(CA)=0P(C_A)=0. If an admissible family were disjoint from AA at every level, Proposition 3.1 would give P(CA)>0P(C_A)>0. Hence every admissible family meets AA.

Conversely, suppose AA meets every admissible family. If MAM_A failed to have natural density one, Corollary 2.3 would give P(CA)>0P(C_A)>0. Proposition 5.1 would then produce an admissible family disjoint from AA at every level, a contradiction. Therefore d(MA)=1d(M_A)=1. □\square

Acknowledgments

Artificial-intelligence tools provided by OpenAI assisted with mathematical exploration, checking arguments, and preparation of the manuscript.

References

  1. [1]H. Davenport and P. Erdős, On sequences of positive integers, Acta Arithmetica 2 (1936), 147–151.
  2. [2]P. Erdős, Some unconventional problems in number theory, Astérisque 61 (1979), 73–82.

Paper details

vlnc:W_z4jnk6uk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents