Additive vs multiplicative densities

It is basic fact of measure theory that there is no uniform measure on a countable set such as the set {{\mathbb N}} of all natural numbers. However, there are many ways to measure size of subsets of {{\mathbb N}}. For instance, the set of even numbers {2{\mathbb N}} should have {1/2} of all the measure. With this philosophy, the precise definition of natural density appeared:

Definition 1 (Natural density) Let {A\subset{\mathbb N}}. Define the natural density of {A} to be the number {\displaystyle\lim_{n\rightarrow\infty}\frac{|[n]\cap A|}n}, when the limit exists (and is undefined when the limit does not exist).

Among other good properties of the natural density, we quickly realize that {d(A+n)=d(A)} for any {n\in{\mathbb Z}} (where {A+n:=\{x\in{\mathbb N}:x-n\in A\}}). Thus {A} is an additively invariant density over {{\mathbb N}}.
For some purposes, it turns out that it is convenient to have a density which is invariant under multiplication, thus the sets {A} and {rA} should have the same density for every {r\in{\mathbb Q}} (where {rA:=\{x\in{\mathbb N}:x/r\in A\}}). We will see that such a density also exists. However, no density can be both invariant under addition and multiplication simultaneously (I say a little about this after Theorem 1 in my previous post).
A question raised by these observations is whether additively “large” sets must be multiplicatively “large” or vice versa. In this post we give some partial answers to this question (spoiler alert: the answer is usually no). In particular we will exhibit examples of sets in {{\mathbb N}} that have opposite “size” regarding additive and multiplicative density.

— 1. Definitions and notation —

We start by making more precise definitions. As usual, for {M\in{\mathbb N}} we denote {[M]:=\{1,2,...,M\}}. If {x\in{\mathbb N}} and {F\subset{\mathbb N}} we define {xF:=\{xn:n\in F\}} and {x+F:=\{x+n:n\in F\}}.
We have the following

Definition 2 (Følner sequence)

  • An additive Følner sequence is a sequence {(F_n)} of finite subsets of {{\mathbb N}} such that for all {x\in{\mathbb N}} we have {|(x+F_n)\cap F_n|/|F_n|\rightarrow1}.
  • A multiplicative Følner sequence is a sequence {(F_n)} of finite subsets of {{\mathbb N}} such that for all {x\in{\mathbb N}} we have {|(xF_n)\cap F_n|/|F_n|\rightarrow1}.

As an example of additive Følner sequence take {F_n=[n]}. A more general example if {F_n=[a_n,a_n+n]} for any sequence {(a_n)} in {{\mathbb N}} . An example of a multiplicative Følner sequence is the following:

\displaystyle F_n=\big\{p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}\mid 0\leq e_1,e_2,\dots,e_n\leq n\big\}

where {p_1,p_2,\dots} are the prime numbers (we can take any arbitrary ordering of the prime numbers, as long as every prime appears in the sequence).
The following lemma (which follows easily from the definitions) gives more examples of Følner sequences.

Lemma 2 Let {(F_n)} be a Følner sequence and let {(x_n)} be a sequence taking values on {{\mathbb N}}. If {(F_n)} is an additive Følner sequence, then {(x_n+F_n)} is still an additive Følner sequence and if {(F_n)} is a multiplicative Følner sequence, then {(x_nF_n)} is still a multiplicative Følner sequence.

We can now define densities. It turns out that the family of sets for which the natural density is defined does not behave well with respect to set theoretical operators. Thus it is convenient to broaden the definition to allow any subset of {{\mathbb N}}. To do so, we simply take the {\limsup} instead of the {\lim}.

Definition 3 (Density)

  • Given a Følner sequence {(F_n)} (additive or multiplicative) and a set {A\subset{\mathbb N}}, the upper density of {A} with respect to {(F_n)} is the number {\displaystyle\limsup_{n\rightarrow\infty}\frac{|F_n\cap A|}{|F_n|}}.
  • The additive (resp. multiplicative) upper Banach density of a set {A\subset{\mathbb N}} is the supremum over all additive (resp. multiplicative) Følner sequences of the upper density of {A}.
  • Given a Følner sequence {(F_n)} (additive or multiplicative) and a set {A\subset{\mathbb N}}, the lower density of {A} with respect to {(F_n)} is the number {\displaystyle\liminf_{n\rightarrow\infty}\frac{|F_n\cap A|}{|F_n|}}.

The following result follows from the fact that {|F_n|\rightarrow\infty} as {n\rightarrow\infty} for any Følner sequence.

Lemma 3 Let {A\subset{\mathbb N}}, let {F\subset A} be a finite set and let {B=A\setminus F}. Then the density of {B} is the same as the density of {A} (upper or lower density with respect to a (additive or multiplicative) Følner sequence, natural density and upper Banach density).

While Følner sequences for a general class of semigroups were introduced by Følner, the multiplicatively invariant density on {{\mathbb N}} was maybe studied for the first time by Bergelson in this paper.

— 2. Independence between additive and multiplicative densities —

In this section we answer (mostly in the negative) some precise reformulations of the question in the introduction, regarding the relation between the additive and multiplicative densities.
We start with an example that suggests a certain independence between the two notions.

Proposition 4 There exists a set {A\subset{\mathbb N}} whose additive Banach upper density is {0} and the lower density with respect to some multiplicative Følner sequence is {1}.

Proof: Let {(F_n)} be some multiplicative Føner sequence and let {M_n=\max F_n} so that {F_n\subset[M_n]}. Define the sequence {(a_n)} of natural numbers by {a_1=1} and for {n>1} let {a_n=2a_{n-1}M_n}. Let {\displaystyle A=\bigcup_{n=1}^\infty a_n[M_n]}, we claim that it satisfies the proposition. Since {(a_nF_n)} is a multiplicative Følner sequence by Lemma 2 and {|A\cap a_nF_n|=|a_nF_n|=|F_n|} we conclude that the lower density of {A} with respect to {(a_nF_n)} is {1}.
Now for each {N\in{\mathbb N}} let {\displaystyle A_N=\bigcup_{n=N}^\infty a_n[M_n]}. Note that {A_N} is obtained from {A} by removing a finite set, so by Lemma 3 the additive Banach upper density of {A} is the same as that of {A_N}. On the other hand, the sets {\{A_N-i,i=1,...,a_N\}} are pairwise disjoint, so for any additive Følner sequence we get that the upper density of {A_N} is at most {1/a_N}. Since {N} was arbitrary we conclude that the Banach upper density of {A} is {0} as desired. \Box
For the next result we need a lemma:

Lemma 5 Let {P} be a set with {0} additive upper density with respect to some fixed arbitrary Følner sequence. Then for every {n\in{\mathbb N}} there exists some {a\in{\mathbb N}} such that the interval {[a,a+n]} is disjoint from {P}.

Proof: For each {i\in[n]}, the set {P-i} has {0} density, hence the finite union

\displaystyle \bigcup_{i=0}^n(P-i)

still has {0} density and hence is not all of {{\mathbb N}}. Let {a} be a number not in that union. Then for each {i\in\{0,\dots,n\}} we have {a\notin(P-i)} which is equivalent to {a+i\notin P}. We conclude that {[a,a+n]} is disjoint from {P} as desired. \Box

The next result is in some sense complementary to Proposition 4.

Proposition 6 There exists a set {A\subset{\mathbb N}} such that {A} has multiplicative Banach upper density {0} but for some additive Følner sequence, the lower density of {A} is {1}.

Proof: We define the sequences {(a_n)} of natural numbers and {(A_n)} of finite sets of {{\mathbb N}}, recursively by {a_1=1}, {A_1=\{1\}} and for {n>1} we let {a_n>a_{n-1}} be such that {[a_n,a_n+n]} is disjoint from {\displaystyle \bigcup_{k=1}^\infty 2^kA_{n-1}} and we let {A_n=A_{n-1}\cup [a_n,a_n+n]}.
Observe that we can always choose such {a_n} because the set {\displaystyle \bigcup_{k=1}^\infty 2^kA_{n-1}} can be rewritten as {\displaystyle \bigcup_{x\in A_{n-1}}xP} where {P=\{2^k:k\in{\mathbb N}\}} has natural density {0}. Hence each of the sets {xP} has natural density {0} and thus also the finite union over {A_{n-1}} has natural density {0}. By Lemma 5 we can choose {a_n} as desired.
Let {A=\bigcup A_n}. It has lower density {1} with respect to the additive Følner sequence {([a_n,a_n+n])}. Also note that the multiplicative shifts {\{2^kA,k\in{\mathbb N}\}} are all disjoint, so {A} has zero multiplicative density with respect to every multiplicative Følner sequence. \Box
Since the natural density implies more regularity to a set than just upper density, it is natural to wonder if the previous result still holds with the upper density with respect to some Følner sequence replaced with natural density. As an indication in this direction is the following:

Proposition 7 For every {\epsilon>0} there is a set {A\subset{\mathbb N}} of natural density at least {1-\epsilon} and such that {A} has multiplicative Banach upper density {0}.

Proof: Let {k\in{\mathbb N}} and take {A:={\mathbb N}\setminus\bigcup_{i=1}^\infty i^k{\mathbb N}} to be the set of {k}-th power free numbers. It is a classical fact that the natural density of {A} is {1/\zeta(k)} where {\zeta} is the Riemann zeta function. On the other hand, the sets {\{p^kA: p\text{ is prime}\}} are pairwise disjoint, therefore the upper density of {A} with respect to any multiplicative Følner sequence is {0} \Box
The next proposition is in the opposite flavor of the previous ones, in the sense that it establishes some relation between additive and multiplicative structure.

Proposition 8 If {A\subset{\mathbb N}} is such that the natural density of {A} is {1}, then there exists some multiplicative Følner sequence {(F_n)} such that the upper density of {A} with respect to {(F_n)} is also {1}.

Proof: Note that for each {k\in{\mathbb N}}, the set {A/k:=\{x\in{\mathbb N}:kx\in A\}} still has natural density {1}. Moreover, any finite collection of sets of natural density {1} has non-empty intersection.
Let {(G_n)} be an arbitrary multiplicative Følner sequence. For each {n\in{\mathbb N}} let {x_n} be in the intersection {\bigcap_{k\in G_n}A/k}. Then {F_n:=x_nG_n\subset A}. Since by lemma 2 {(F_n)} is a multiplicative Følner sequence we are done. \Box
Observe that a set {A\subset{\mathbb N}} has natural density {1} if and only if its lower density with respect to the Følner sequence {([n])} is {1}. Thus it is natural to try to weaken the hypothesis of the previous proposition, and also the conclusion. I don’t know the answer to the following question:

Question 9 Is it true that if {A\subset{\mathbb N}} has upper density {1} with respect to the additive Følner sequence {F_n=[n]}, then {A} has positive upper density with respect to some multiplicative Følner sequence?

Another intriguing question is whether there exists a set {A\subset{\mathbb N}} which has natural density strictly between {0} and {1} and multiplicative upper density also strictly between {0} and {1} for some Følner sequence. While there seems to be no reason why such set shouldn’t exist, I could not find an example.

Advertisements

About Joel Moreira

PhD Student at OSU in Mathematics. I'm portuguese.
This entry was posted in Combinatorics and tagged , , , , . Bookmark the permalink.

One Response to Additive vs multiplicative densities

  1. Pingback: Weighted densities with multiplicative structure | 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s