The upper density of a set , defined by

provides a useful way to measure subsets of . For instance, whenever , contains arbitrarily long arithmetic progressions, this is Szemerédi’s theorem. A fundamental property of the upper density is that it is invariant under (additive) shifts. More precisely, if we denote by the set then for any and .

However the upper density is not invariant under multiplicative `shifts’. More precisely, if we let , then is not, in general, the same as . For instance, taking to be the set of odd numbers and we have but is the empty set, and as such . In fact, as I explored in a previous post, there is very little multiplicative information contained in the upper density of a set. In particular, for any , there are sets with upper density but without any two numbers 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 elements out of , than there are two elements, one of them dividing the other (and the ratio can be taken to be a power of ). This implies that if , then contains such that divides .

** — 1. Sets with density — **

One (of the very few) way(s) to get some multiplicative structure out of additive density is when the in (1) is actually a and is equal to . Then it follows from Proposition 8 of my earlier post that there are (many) pairs such that is a multiple of . In that post I asked if the same phenomenon in Proposition 8 occurs when we only assume that (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 1If and , then .

*Proof:* In this proof we write to denote the set , where is the largest integer no bigger than .

Let and find such that

This implies that

Using the general fact that we deduce that has cardinality

Dividing by (and observing that every number in the intersection is divisible by ) we conclude that

As can be taken arbitrarily large we deduce that

and since was arbitrary we get that

From this one can immediately deduce that the multiplicative upper Banach density of is . In other words, if then is multiplicatively thick.

Thus upper density equal 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

Is it true that implies the existence of with a multiple of ? 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 2A non-negative function is aweightif the sum goes to infinity.

Given a weight one can define the upper and lower density of a set with respect to . The upper density is

Similarly we define the lower density by

Example 1When for every we get the upper density (1).

Another example is the logarithmic density, with .

For a function we denote by the discrete derivative defined by . For instance, for defined above we have .

Theorem 3Let be weights on and assume that is a non-increasing function andThen

*Proof:* Observe that the first inequality follows from the last, by replacing with . Also the middle inequality is trivial. Thus all that we need to prove is the last inequality.

Let and let

Let be arbitrary and find such that for any we have . Let be a very large integer (to be determined later). Consider the identity

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

The first term in the right hand side is by (2). The second term is independent of , so for large enough we can think of it as , which gets absorbed into the . Thus we get

The sum can be rearranged using summation by parts:

with and . Note that the term is independent of , hence , and the term is , again by (2). Thus we get

Since was arbitrary, we conclude that

as desired.

Thus, if we denote the logarithmic (upper and lower) density of a set by and respectively (these are the densities with weight ), then we have

In particular, if , then also .

To get other examples of pairs of weights which satisfy the conditions of Theorem 3, take any weight and let (so that ).

It turns out that the examples produced by Besicovitch of sets with positive upper density but without divisors all have upper logarithmic density. In fact the following result is true:

Theorem 4Let be such that . Then contain such that is a multiple of .

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 5Let be such that . Then there exists some such that .

This implies that if , then contains a (multiplicative) shift of an arbitrarily large finite (multiplicative) IP-set, in other words, all the initial products of some sequence .

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