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 1 If 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 2 A non-negative function is a weight if 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 1 When 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 .
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
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 4 Let be such that . Then contain such that is a multiple of .
Theorem 5 Let 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 .