MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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"!

Thanks in advance, Valerio

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^+]$.

share|cite|improve this question
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., – 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
up vote 5 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
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.


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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.