Weighted densities with multiplicative structure

The upper density of a set {A\subset{\mathbb N}}, defined by

\displaystyle \bar d(A)=\limsup_{N\rightarrow\infty}\frac{\big|A\cap\{1,\dots,N\}\big|}N \ \ \ \ \ (1)

provides a useful way to measure subsets of {{\mathbb N}}. For instance, whenever {\bar d(A)>0}, {A} contains arbitrarily long arithmetic progressions, this is Szemerédi’s theorem. A fundamental property of the upper density {\bar d} is that it is invariant under (additive) shifts. More precisely, if we denote by {A-n} the set {\{x\in{\mathbb N}:x+n\in A\}} then {\bar d(A-1)=\bar d(A)} for any {A\subset{\mathbb N}} and {n\in{\mathbb N}}.
However the upper density is not invariant under multiplicative `shifts’. More precisely, if we let {A/n:=\{x\in{\mathbb N}:x\cdot n\in A\}}, then {\bar d(A/n)} is not, in general, the same as {\bar d(A)}. For instance, taking {A} to be the set of odd numbers and {n=2} we have {\bar d(A)=1/2} but {A/n} is the empty set, and as such {\bar d(A/n)=0}. In fact, as I explored in a previous post, there is very little multiplicative information contained in the upper density {\bar d} of a set. In particular, for any {\epsilon>0}, there are sets with upper density {\bar d(A)>1/2-\epsilon} but without any two numbers {x,y\in A} which divide each other; the first examples of such sets were constructed by Besicovitch in 1934.
We remark that it is an elementary (and well known) fact that if we take more than {n} elements out of {\{1,2,\dots,2n\}}, than there are two elements, one of them dividing the other (and the ratio can be taken to be a power of {2}). This implies that if {\bar d(A)>1/2}, then {A} contains {x,y} such that {x} divides {y}.

— 1. Sets with density {1}

One (of the very few) way(s) to get some multiplicative structure out of additive density is when the {\limsup} in (1) is actually a {\lim} and is equal to {1}. Then it follows from Proposition 8 of my earlier post that there are (many) pairs {x,y\in A} such that {x} is a multiple of {y}. In that post I asked if the same phenomenon in Proposition 8 occurs when we only assume that {\bar d(A)=1} (instead of requiring the limit to exist). It turns out that the answer is yes and can be deduced with a simple combinatorial argument:

Proposition 1 If {\bar d(A)=1} and {n\in{\mathbb N}}, then {\bar d\big(A\cap(A/n)\big)=1}.

Proof: In this proof we write {[1,x]} to denote the set {\{1,2,\dots,\lfloor x\rfloor\}}, where {\lfloor x\rfloor} is the largest integer no bigger than {x}.
Let {\epsilon>0} and find {N\in{\mathbb N}} such that

\displaystyle |A\cap[1,N]|>\left(1-\frac\epsilon{2n}\right)N=N-\frac{\epsilon N}{2n}

This implies that

\displaystyle |nA\cap[1,N]|=\bigg|A\cap\left[1,\tfrac Nn\right]\bigg|>\frac Nn-\frac{\epsilon N}{2n}

Using the general fact that {|X\cup Y|+|X\cap Y|=|X|+|Y|} we deduce that {nA\cap A\cap[1,N]=(nA\cap[1,N])\cap(A\cap[1,N])} has cardinality

\displaystyle \begin{array}{rcl} \displaystyle |nA\cap A\cap[1,N]|&=&\displaystyle |nA\cap[1,N]|+|A\cap[1,N]|-\Big|\big(nA\cap[1,N]\big)\cup\big(A\cap[1,N]\big)\Big|\\&\geq& \displaystyle \quad N-\frac{\epsilon N}{2n}\ \ +\ \ \frac Nn-\frac{\epsilon N}{2n}\ \ -\qquad N\\&=&\displaystyle \frac Nn(1-\epsilon) \end{array}

Dividing by {n} (and observing that every number in the intersection {nA\cap A\cap[1,N]} is divisible by {n}) we conclude that

\displaystyle |A\cap(A/n)\cap[1,N/n]|=|nA\cap A\cap[1,N]|\geq\frac Nn(1-\epsilon)

As {N} can be taken arbitrarily large we deduce that

\displaystyle \bar d\big(A\cap(A/n)\big)>1-\epsilon

and since {\epsilon>0} was arbitrary we get that

\displaystyle \bar d\big(A\cap(A/n)\big)=1


From this one can immediately deduce that the multiplicative upper Banach density of {A} is {1}. In other words, if {\bar d(A)=1} then {A} is multiplicatively thick.
Thus upper density equal {1} is enough to obtain very good multiplicative structure.

— 2. Weighted densities —

The next obvious question is what happens if we look instead to lower density, defined by

\displaystyle \underbar d(A)=\liminf_{N\rightarrow\infty}\frac{|A\cap[1,N]|}N

Is it true that {\underbar d(A)>0} implies the existence of {x,y\in A} with {x} a multiple of {y}? The answer turns out to be yes, but the first proofs (and to my knowledge the only proofs so far) use a different notion of density. I will give a quite general approach to weighted densities.

Definition 2 A non-negative function {w:{\mathbb N}\rightarrow{\mathbb R}^{\geq0}} is a weight if the sum {W(N):=\sum_{n=1}^Nw(n)} goes to infinity.

Given a weight {w} one can define the upper and lower density of a set {A\subset{\mathbb N}} with respect to {w}. The upper density is

\displaystyle \begin{array}{rcl} \displaystyle \bar d_w(A)&=&\displaystyle \limsup_{N\rightarrow\infty}\frac1{W(N)}\sum_{n=1}^Nw(n)1_A(n)\\&=& \displaystyle \limsup_{N\rightarrow\infty}\frac1{W(N)}\sum_{n\in A\cap[N]}w(n) \end{array}

Similarly we define the lower density by

\displaystyle \begin{array}{rcl} \displaystyle \underbar d_w(A)&=&\displaystyle \liminf_{N\rightarrow\infty}\frac1{W(N)}\sum_{n=1}^Nw(n)1_A(n)\\&=& \displaystyle \liminf_{N\rightarrow\infty}\frac1{W(N)}\sum_{n\in A\cap[N]}w(n) \end{array}

Example 1 When {w(n)=1} for every {n} we get the upper density (1).

Another example is the logarithmic density, with {w(n)=1/n}.
For a function {f:{\mathbb N}\rightarrow{\mathbb R}} we denote by {f'} the discrete derivative defined by {f'(n)=f(n+1)-f(n)}. For instance, for {W(N)} defined above we have {W'(n)=w(n+1)}.

Theorem 3 Let {w,v:{\mathbb N}\rightarrow{\mathbb R}^{\geq0}} be weights on {{\mathbb N}} and assume that {w/v} is a non-increasing function and

\displaystyle \lim_{n\rightarrow\infty}\frac{w(n)/W(n)}{v(n)/V(n)}=0\ \ \ \ \ (2)


\displaystyle \underbar d_v(A)\leq\underbar d_w(A)\leq\bar d_w(A)\leq\bar d_v(A)

Proof: Observe that the first inequality follows from the last, by replacing {A} with {{\mathbb N}\setminus A}. Also the middle inequality is trivial. Thus all that we need to prove is the last inequality.
Let {\delta=\bar d_v(A)} and let

\displaystyle \mu(m)=\sum_{n=1}^m1_A(n)v(n)\qquad \nu(m)=\sum_{n=1}^m1_A(n)w(n)

Let {\epsilon>0} be arbitrary and find {N_0\in{\mathbb N}} such that for any {N\geq N_0} we have {\mu(N)\leq(\delta+\epsilon)V(N)}. Let {M>N_0} be a very large integer (to be determined later). Consider the identity

\displaystyle \nu(M)=\frac{w(M)}{v(M)}\mu(M)+\sum_{m=1}^{M-1}\mu(m)\left(\frac{w(m)}{v(m)}-\frac{w(m+1)}{v(m+1)}\right)

which can be checked by induction on {M}. From this we get

\displaystyle \begin{array}{rcl} \displaystyle \nu(M)&\leq&\displaystyle \frac{w(M)}{v(M)}(\delta+\epsilon)V(M)+ \sum_{m=1}^{N_0-1}\mu(m)\left(\frac{w(m)}{v(m)}-\frac{w(m+1)}{v(m+1)}\right)\\&+&\displaystyle (\delta+\epsilon)\sum_{m=N_0}^{M}V(m)\left(\frac{w(m)}{v(m)}-\frac{w(m+1)}{v(m+1)}\right) \end{array}

The first term in the right hand side is {o\big(W(M)\big)} by (2). The second term is independent of {M}, so for large enough {M} we can think of it as {O(1)}, which gets absorbed into the {o\big(W(M)\big)}. Thus we get

\displaystyle \nu(M)\leq(\delta+\epsilon)\sum_{m=N_0}^{M}V(m)\left(\frac{w(m)}{v(m)}-\frac{w(m+1)}{v(m+1)}\right)+o\big(W(M)\big)

The sum can be rearranged using summation by parts:

\displaystyle \sum_{m=N_0}^Mf_m(g_{m+1}-g_m)=[f_{M+1}g_{M+1}-f_{N_0}g_{N_0}]-\sum_{m=N_0}^M(f_{m+1}-f_m)g_{m+1}

with {f_m=V(m)} and {g_m=-w(m)/v(m)}. Note that the term {f_{N_0}g_{N_0}} is independent of {M}, hence {O(1)}, and the term {f_{M+1}g_{M+1}=-V(M+1)w(M+1)/v(M+1)} is {o\big(W(M)\big)}, again by (2). Thus we get

\displaystyle \begin{array}{rcl} \displaystyle \nu(M)&\leq& \displaystyle(\delta+\epsilon)\left(\sum_{m=N_0}^M\big(V(m+1)-V(m)\big)\frac{w(m+1)}{v(m+1)}\right)+o\big(W(M)\big) \\&=&\displaystyle (\delta+\epsilon)\big(W(M+1)-W(N_0)\big)+o\big(W(M)\big)\\&\leq& \displaystyle\big(\delta+\epsilon+o(1)\big)W(M)\end{array}

Since {\epsilon>0} was arbitrary, we conclude that

\displaystyle \bar d_f(A)=\limsup_{M\rightarrow\infty}\frac{\nu(M)}{W(M)}\leq\delta

as desired.


Thus, if we denote the logarithmic (upper and lower) density of a set {A\subset{\mathbb N}} by {\underbar ld(A)} and {\bar ld(A)} respectively (these are the densities with weight {w(n)=1/n}), then we have

\displaystyle 0\leq\underbar d(A)\leq\underbar ld(A)\leq\bar ld(A)\leq\bar d(A)

In particular, if {\underbar d(A)>0}, then also {\underbar ld(A)>0}.
To get other examples of pairs of weights {(w,v)} which satisfy the conditions of Theorem 3, take any weight {v} and let {W(n)=\log\big(V(n)\big)} (so that {w(n)\simeq \frac{v(n)}{V(n)}}).
It turns out that the examples produced by Besicovitch of sets with positive upper density but without divisors all have {0} upper logarithmic density. In fact the following result is true:

Theorem 4 Let {A\subset{\mathbb N}} be such that {\bar ld(A)>0}. Then {A} contain {x,y\in A} such that {x} is a multiple of {y}.

This was first established by Behrend, and also follows from this paper.
Even more surprising, the following significant strengthening, obtained by Ahlswede, Khachatrian and Sárközy, also holds:

Theorem 5 Let {A\subset{\mathbb N}} be such that {\bar ld(A)>0}. Then there exists some {n\in{\mathbb N}} such that {\bar ld\big(A\cap(A/n)\big)>0}.

This implies that if {\bar ld(A)>0}, then {A} contains a (multiplicative) shift of an arbitrarily large finite (multiplicative) IP-set, in other words, all the initial products {a_1a_2\cdots a_n} of some sequence {(a_n)_{n\in{\mathbb N}}}.

This entry was posted in Combinatorics, Number Theory, Tool and tagged , , , . Bookmark the permalink.

1 Response to Weighted densities with multiplicative structure

  1. Pingback: Single and multiple recurrence along non-polynomial sequences | I Can't Believe It's Not Random!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s