# How can we pave the multiplicative semigroup $(\mathbb N,\cdot)$?

Let $(S,\cdot)$ be a semigroup and $W\subseteq S$ be a subset. Let me call $W$ "tile" if the following property is satisfied: there exist $s_1,...s_k\in S$ such that the sets $s_i\cdot W$ are pairwise disjoint and cover $S$. For instance, tiles for the semigroup $(\mathbb N,+)$ are given by the multiples of some fixed natural number. Here is my question: is there any explicit example of tile for the semigroup $(\mathbb N,\cdot)$?

A literature remark: I do not know if the notion of "tile" is already defined/used somewhere. I know the existence of "syndetic sets" that are pretty similar but different. I hope you like the name "tile"!

If someone of you wants to know more specifically my problem: Let $(S,\cdot)$ be a countable amenable semigroup and let $W\subset S$ be a subset. Let me denote by $\chi_W$ the characteristic function of $W$ and define the following numbers $$W^-=\inf [f(\chi_W),f \text{ bi-invariant mean}]$$ $$W^+=\sup[f(\chi_W), f \text{ bi-invariant mean}]$$ I am first of all interested in the case $W^-=W^+$ (this is why I'm interested in tiles). That would be the case when one can define some notion of intrinsic probability of the set $W$. Then it would be nice to find some description for the number $W^+-W^-$ and hopefully finding how the numbers $f(\chi_W)$ are distributed into the interval $[W^-,W^+]$.

-
Since you ask, a note regarding terminology: problems of this type (in particular for the integers but also other groups) can be found under the name 'cover' or 'covering system'. This is not exactly your 'tile', but I believe an 'exact covering' or 'exact 1-cover' would be; (exact) m-covers are also studied for other values of m. See, e.g., en.wikipedia.org/wiki/Covering_system – user9072 Mar 23 '11 at 17:30
So if there are $k$ integers $s_1,\dots,s_k \in \mathbb{N}$ so that the sets $s_i\ \cdot W$ are disjoint and cover $\mathbb{N}$, does that mean that $f(\chi_W)=\frac{1}{k}$? – Aaron Meyerowitz Mar 26 '11 at 4:02
Yes, if $f$ is an invariant mean.. – Valerio Capraro Apr 2 '11 at 16:02

Prime factorization provides an isomorphism between the semigroup $(\mathbb N,\cdot)$ and an infinite direct sum of copies of $(\mathbb N,+)$. So you can reduce your problem to the case that you already know how to solve.

Warning: my first $\mathbb N$ does not contain the element zero, whereas my second $\mathbb N$ does!

Concretely, here is an example of a tile of $(\mathbb N,\cdot)$: the set of all $n\in\mathbb N$ whose $p$-valuation is a multiple of $k$, where $p$ is a prime number, and $k$ is arbitrary.

-

Consider $W$ consisting of those natural numbers in which a given prime $p$ occurs in the prime factorization with exponent divisible by some constant $k$. For example, if $W$ is numbers in which the exponent of 2 is even, then $W \cap 2W = \emptyset$ and $W \cup 2W = \mathbb{N}$.

-
Thanks a lot. You know if there are any others? You're a statistic and so you might understand what I have in mind: sets such that $W^+=W^-$ have some kind of intrinsic probability. They should be the analogue of Haar-measurable subset of a compact group. It would be great to find a description of them. – Valerio Capraro Mar 24 '11 at 11:20

For each $b \gt 1$ there is a (unique) solutions to $\lbrace 1,b\rbrace W=W \cup bW=\mathbb{N}.$ So far the case of a prime power $b=p^k$ (particularly $b=2$) has been mentioned. The cases $b=6$ and $b=12$ are worth a look. I will call these 2-dimensional.

In a factorization $\mathbb{N}=VW,$ either of $V$ and $W$ uniquely determines the other. The 1-dimensional cases $V=\lbrace 1,p,p^2,p^3\rbrace$ , $V=\lbrace 1,p^{6},p^{12}\rbrace$ , $V=\lbrace 1,p,p^{10},p^{11},p^{20},p^{21}\rbrace$ hint at the most general 1-dimensional case.

The problem asks when we can factor the positive integers into two subsets $V,W$ so that each $n \in \mathbb{N}$ can be uniquely expressed as $n=vw$ i.e. $\mathbb{N}=VW$ where $V$ is finite. Since either set determines the other, it is sometimes easier to consider $V$ . Define the dimension of the factorization to be the number $d$ of primes dividing the members of $V$. Then factorizations correspond to tilings by translation (additive tilings) of ${(\mathbb{N}_{0})}^d$.

Here $W$ is thought of as the tile and $V$ as a finite set of placements or dilations. Some reflection shows that $V \cap W=\lbrace 1 \rbrace$. In particular $W=XY$ where $Y$ is the set of integers relatively prime to all the (prime divisors of) members of $V$ and $VX$ is the set of integers whose prime factors are divisors of members of $V$.

So $VW=\mathbb{N}$ is a factorization which we have refined to $VXY=\mathbb{N}$. It is worthwhile to consider factorizations of $\mathbb{N}$ into several (or even infinitely many) parts.

The one dimensional case was completely described by N. G. DeBruijn. Each coreesponds to a sequence of integers (exponents) each dividing the next (alternately, a mixed radix numeral system). An example will suffice to illustrate: Replace $b$ by $p$ to remember that we have a prime. and consider $1 \mid 2 \mid 10 \mid 30 \mid 90 \mid 180$ From this we build

$V=\lbrace 1,p \rbrace \lbrace 1,p^{10},p^{20} \rbrace\lbrace 1,p^{90} \rbrace=\lbrace 1,p,{p}^{10},{p}^{11},{p}^{20},{p}^{21},{p}^{90},{p}^{91},{p} ^{100},{p}^{101},{p}^{110},{p}^{111} \rbrace$ Then $VU$ is all the powers of $p$ from $p^0$ up to $p^{179}$ where $$U=\lbrace1,p^2,{p}^{4},{p}^{6},{p}^{8}\rbrace \lbrace 1,p^{30},p^{60} \rbrace=\lbrace 1,{p}^{2},{p}^{4},{p}^{6},{p}^{8},{p}^{30},{p}^{32},{p}^{34}, {p}^{36},{p}^{38},{p}^{60},{p}^{62},{p}^{64},{p}^{66},{p}^{68} \rbrace$$

• This could be sumarized as $$\frac{1-p^2}{1-p}\frac{1-p^{10}}{1-p^2}\frac{1-p^{30}}{1-p^{10}}\frac{1-p^{90}}{1-p^{30}}\frac{1-p^{180}}{1-p^{90}}\frac{1}{1-p^{180}}=\frac{1}{1-p}$$.
• This views things as working with polynomials (later in several variables) with integer $0,1$ coeffcients. Since things depend on the prime factorization of the exponents and later we have several variables corresponding to different prime bases, that notation seems too confusing.
• Additively, we have a 12 tile $\lbrace 0,1,10,11,20,21,90,91,100,101,110,111 \rbrace$ and 15 translations of it make an interval of length $180$. We could as well consider that 12 translations of the 15-tile $\lbrace 0,2,4,6,8,30,32,34,36,38,60,62,64,66,68 \rbrace$ make the same interval.

For dimension $d=2$ there are more cases. The article below by I. Niven classifies them all. The example above with $V=\lbrace 1,6 \rbrace$ relates to the factorization $$\lbrace 1,pq,p^2q^2,\cdots\rbrace \lbrace1,p,p^2,p^3,\cdots,q,q^2,q^3,\cdots \rbrace=\lbrace p^iq^j \mid i,j,\ge 0 \rbrace$$

The following references are from the excellent article Closed factors of normal Z-semimodules by Daniel A Marcus which classifies the most general case.and has some very worthwhile examples.

References

N. G. DeBruijn, On bases for the set of integers, Publ. Math., (Debrecen) 1 (1950), 232-242.

N. G. DeBruijn, On number systems, Nieuw Arch. Wisk., 4 (1956), 15-17.

N. G. DeBruijn, Some direct decompositions of the set of integers, Math. Comp., 18 (1964), 537-546.

R. T. Hansen, Complementing pairs of subsets of the plane, Duke Math. J., 36 (1969), 441-449.

C. T. Long, Addition theorems for sets of integers, Pacific J. Math., 23 (1967), 107-112.

I. Niven, A characterization of complementing sets of pairs of integers, Duke Math. J., 38 (1971)

S. K. Stein, Algebraic tiling, Amer. Math. Monthly, 81 (1974), 445-462.

S. K. Stein, Factors of some direct products, Duke Math. J., 41 (1974), 537-539.

C. Swenson, Direct sum subset decompositions of Z, Pacific J. Math., 53 (1974), 629-632.

-