Periodic behavior in families of numerical and affine semigroups via parametric Presburger arithmetic

Semigroup Forum - Let $$f_1(n), \ldots , f_k(n)$$ be polynomial functions of n. For fixed $$n\in \mathbb {N}$$ , let $$S_n\subseteq \mathbb {N}$$ be the numerical semigroup generated by...     

The Schröder-Bernstein property for weakly minimal theories

For a countable, weakly minimal theory T, we show that the Schröder-Bernstein property (any two elementarily bi-embeddable models are isomorphic) is equivalent to each of the following:

1. 1.
   For any U-rank-1 type q ∈ S(acl ^eq (?)) and any automorphism f of the monster model C, there is some n < ω such that f ⁿ (q) is not almost orthogonal to q ? f(q) ? … ? f ^n?1(q)
    
2. 2.
   T has no infinite collection of models which are pairwise elementarily bi-embeddable but pairwise nonisomorphic.
    

We conclude that for countable, weakly minimal theories, the Schröder-Bernstein property is absolute between transitve models of ZFC.     

Topological properties of definable sets in ordered Abelian groups of burden 2

We obtain some new results on the topology of unary definable sets in expansions of densely ordered Abelian groups of burden 2. In the special case in which the structure has dp-rank 2, we show that the existence of an infinite definable discrete set precludes the definability of a set which is dense and codense in an interval, or of a set which is topologically like the Cantor middle-third set (Theorem 2.9). If it has burden 2 and both an infinite discrete set D and a dense-codense set X are definable, then translates of X must witness the Independence Property (Theorem 2.26). In the last section, an explicit example of an ordered Abelian group of burden 2 is given in which both an infinite discrete set and a dense-codense set are definable.     

Parametric Presburger arithmetic: complexity of counting and quantifier elimination

We consider an expansion of Presburger arithmetic which allows multiplication by k parameters $t_1,\dots ,t_k$. A formula in this language defines a parametric set $S_{\mathbf{t}}?{\mathbb{Z}}^d$ as $\mathbf{t}$ varies in ${\mathbb{Z}}^k$, and we examine the counting function $|S_{\mathbf{t}}|$ as a function of t . For a single parameter, it is known that $|S_t|$ can be expressed as an eventual quasi‐polynomial (there is a period m such that, for sufficiently large t, the function is polynomial on each of the residue classes mod m). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming $\mathbf{P}\ne \mathbf{NP}$) we construct a parametric set $S_{t_1,t_2}$ such that $|S_{t_1,t_2}|$ is not even polynomial‐time computable on input $(t_1,t_2)$. In contrast, for parametric sets $S_{\mathbf{t}}?{\mathbb{Z}}^d$ with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that $|S_{\mathbf{t}}|$ is always polynomial‐time computable in the size of t , and in fact can be represented using the gcd and similar functions.     

Bounding quantification in parametric expansions of Presburger arithmetic

Generalizing Cooper’s method of quantifier elimination for Presburger arithmetic, we give a new proof that all parametric Presburger families \(\{S_t : t \in \mathbb {N}\}\) [as defined by Woods (Electron J Comb 21:P21, 2014)] are definable by formulas with polynomially bounded quantifiers in an expanded language with predicates for divisibility by f(t) for every polynomial \(f \in \mathbb {Z}[t]\). In fact, this quantifier bounding method works more generally in expansions of Presburger arithmetic by multiplication by scalars \(\{\alpha (t): \alpha \in R, t \in X\}\) where R is any ring of functions from X into \(\mathbb {Z}\).     

Amalgamation functors and boundary properties in simple theories

This paper continues the study of generalized amalgamation properties begun in [1], [2], [3], [5] and [6]. Part of the paper provides a finer analysis of the groupoids that arise from failure of 3-uniqueness in a stable theory. We show that such groupoids must be abelian and we link the binding group of the groupoids to a certain automorphism group of the monster model, showing that the group must be abelian as well. We also study connections between n-existence and n-uniqueness properties for various “dimensions” n in the wider context of simple theories. We introduce a family of weaker existence and uniqueness properties. Many of these properties did appear in the literature before; we give a category-theoretic formulation and study them systematically. Finally, we give examples of first-order simple unstable theories showing, in particular, that there is no straightforward generalization of the groupoid construction in an unstable context.