No label defined (Q4526796)

This book treats the problem of counting certain structures. These are very varied on the surface: permutations of a finite set, partitions of a positive integer, or a finite Abelian group. These share the following common traits: (i) They admit a natural measure of ``size'', which is a nonnegative integer; (ii) they have a natural operation (like a permutation on a disjoint union, the direct product of groups), and the size is either added or multiplied; (iii) under this operation a structure has a unique decomposition into irreducible elements (a cycle for a permutation, a prime-power order cyclic group for Abelian groups), that is, the operation in (ii) turns them into a free commutative semigroup. If we now forget the origin of the object and just see this semigroup, we have what the author calls, corresponding to the cases in (ii), an additive or multiplicative number system. Important quantities related to such a number system \(\mathcal A\) are \(a(n)\), the number of elements of size \(n\), \(A(x)=\sum _{n\leq x} a(n)\), the number of elements of size \(\leq x\), and the generating function \({\mathbf A(x)}\), which is the power series \(\sum a(n)x^n \) in the additive case and the Dirichlet series \(\sum a(n) n^{-x}\) in the multiplicative case. The focus of the book is not in finding estimates for these quantities in concrete cases---in fact, such results are barely mentioned---but rather comparing them for subsystems and finding densities, or in other words, finding the probability of certain properties (say, that an Abelian group has an element of order 2). If \(B\) is a subset of \(\mathcal A\), then---with the natural choice of notation---the above counting functions induce the local asymptotic density \( \lim b(n)/a(n)\), the global asymptotic density \( \lim B(n)/A(n)\), and the Dirichlet density \( \lim {\mathbf B (x)}/ {\mathbf A(x)}\). In the last limit, \(x\) tends to the radius \(\varrho \) or abscissa \(\alpha \) of convergence. It is assumed that \(\varrho >0\) or \(\alpha <\infty \), which excludes very fast growing counting functions. If there are infinitely many irreducibles, then \(\varrho \leq 1\), \(\alpha \geq 0\) (the case of finitely many irreducibles is also discussed, it is quite easy and of limited interest). The aim of the book is to exhibit classes of systems for which the existence of such a density can be proved, and cases when a 0-1 law holds. The book is divided into two parts of closely parallel structure, Part 1 is devoted to the additive case and Part 2 to the multiplicative one. Often the results in the multiplicative case are weaker and the proofs more difficult, which is no surprise. Indeed, there is a natural correspondence between additive systems and multiplicative systems with the property that every norm is a power of a fixed integer; the author calls these ``discrete'', and the rest ``strictly multiplicative''. An important case which is fairly well understood is the so called \textit{partition sets}. These are obtained by splitting the set of irreducibles into finitely many classes, say \(P_1, ..., P_k\), taking integers \(m_1, ..., m_k\) imposing for each \(1\leq i\leq k\) a condition that the number of factors taken from \(P_i\) is either at most \(m_i\), or at least \(m_i\), or exactly \(m_i\). The generating function of a partition set is rather simple, and one can prove that they always possess a Dirichlet density. Furthermore, in the extremal cases \(\varrho =1\) or \(\alpha =0\) this density is always 0 or 1. To pass from Dirichlet to global or local density, one needs Tauberian theorems of varying difficulty. In the additive case, when \(\varrho =1\), then \(a(n-1)/a(n)\rightarrow 1\) is a necessary and sufficient condition for every partition set to have local density (a beautiful sufficient condition for this is that the norms of primes are all distinct, by an old result of Bateman and Erdős), and similarly \(A(n-1)/A(n)\rightarrow 1\) is the necessary and sufficient condition for global density. In the multiplicative case the analogous condition reads \(A(tx)/A(t)\rightarrow 1\) as \(t\rightarrow \infty \), for every fixed value of \(x\). This is, in the case \(\alpha =0\), the necessary and sufficient condition for every partition set to possess global density. For \(\varrho <1\) or \(\alpha >0\) there are similar but more involved sufficient conditions, but no necessary and sufficient condition is known. It often happens that under analogous conditions one can establish a local law in the additive case and a global one for multiplicative systems. The book ends with stating as the main problem to explain why this parallel behavior happens. There are three conjectures in Part~2, based on the assumption that the parallelism would hold. All three have now been proven correct. Both parts of the book end with a chapter where it is shown that finite unions of pairwise disjoint partition sets include many naturally arising classes, and hence (under appropriate assumptions) these have a density; this accounts for the second part of the title. We start with a language \(L\) to construct a first-order logic; this language is, in the additive case, restricted to purely relational type (no functions, no constant symbols---as an important example, a graph is a single binary relation). These restrictions are needed in order to form disjoint unions of structures. However, in the multiplicative case there are no such restrictions. A class of finite \(L\)-structures is \textit{adequate}, if it is closed under disjoint union (additive case) or direct product (multiplicative case), and this operation turns it into a free semigroup (isomorphic structures identified). The main result sounds as follows. Consider an adequate class of finite \(L\) structures. Then the subclass of structures satisfying \(\phi \), where \(\phi \) is any monadic second-order sentence in the additive case, (``monadic'' means that the formula may involve subsets [= unary relations] that can be quantified), and any first-order sentence in the multiplicative case, is always a finite union of pairwise disjoint partition sets. Hence if we assume that all partition sets have local (global) asymptotic density, then so do the sets defined via \(\phi \). This is a rather new subject. The results in the additive case are due mainly to K. J. Compton from the 80s, the analogs for the multiplicative case mainly to the author of the book with different coauthors. It shows an exciting connection between combinatorics, number theory and logic, and certainly deserves to be more widely known. The book gives a very clear account of it and it is easily readable -- somewhat too detailed to my taste in routine analytic arguments. The book lists some open problems, quite a few of which have since been solved. (See the author's web page \texttt{www.thoralf.uwaterloo.ca} for the announcements and references to new results).