## 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$

$\Box$

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)$

Then

$\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.

$\Box$

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.