Browsing by Autor "John Goodrick"

Now showing 1 - 5 of 5

A Characterization of Strongly Dependent Ordered Abelian Groups
(National University of Colombia, 2018) Alfred Dolich; John Goodrick
We characterize all ordered Abelian groups whose ﬁrst-order theory in the language {+, <, 0} is strongly dependent. The main result of this note was obtained independently by Halevi and Hasson [7] and Farré [5].
Amalgamation functors and boundary properties in simple theories
(Cornell University, 2010) John Goodrick; Byunghan Kim; Alexei Kolesnikov
This paper continues the study of generalized amalgamation properties. 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 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.
Bounding quantification in parametric expansions of Presburger arithmetic
(Springer Science+Business Media, 2017) John Goodrick
DISCRETE SETS DEFINABLE IN STRONG EXPANSIONS OF ORDERED ABELIAN GROUPS
(Cambridge University Press, 2024) Alfred Dolich; John Goodrick
Abstract We study the structure of infinite discrete sets D definable in expansions of ordered Abelian groups whose theories are strong and definably complete, with a particular emphasis on the set $D'$ comprised of differences between successive elements. In particular, if the burden of the structure is at most n , then the result of applying the operation $D \mapsto D'\ n$ times must be a finite set (Theorem 1.1). In the case when the structure is densely ordered and has burden $2$ , we show that any definable unary discrete set must be definable in some elementary extension of the structure $\langle \mathbb{R}; <, +, \mathbb{Z} \rangle $ (Theorem 1.3).
Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
(Diamond Open Access Journals, 2017) Kevin Woods; John Goodrick; Tristram Bogart
Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior, Discrete Analysis 2017:4, 34 pp. Let $T$ be a triangle with vertices $(0,0)$, $(0,1/3)$, and $(1,0)$, and let $t$ be a positive integer. Then it is not hard to check that there are three quadratics $q_1,q_2$ and $q_3$ such that the number of integer points in $tT$ is $q_i(t)$ if $t\equiv i$ mod 3. In a situation like this, we say that the number of integer points is _quasipolynomial_ with period 3. In 1962, Ehrhart proved that if $P$ is a polytope in $\mathbb Z^d$ defined by a finite set of linear inequalities of the form $a_i.x\leq b_i$, where each of the $a_i$ belong to $\mathbb Z^d$ and $b$ belongs to $\mathbb Z$, then the number of lattice points in $tP$ is quasipolynomial with period $m$, where $m$ is the smallest integer such that the vertices of $mP$ are all lattice points. Since then, the same conclusion has been established for other families of sets $S_t\subset \mathbb Z^d$ by Chen, Li and Sam, by Calegari and Walker, and by Roune and Woods. After these results, it was tempting to wonder whether _all_ families of sets, provided that they are sufficiently nice in some appropriate sense, exhibit this quasipolynomial behaviour. The constraints would have to be reasonably strong -- for example, the number of lattice points inside the unit sphere of radius $t$ is certainly not quasipolynomial (and indeed, estimating it is a famous problem) -- but one could still hope for a general theorem that would encompass the known results and give a number of further ones. It turns out that the right behaviour to look for in general is that the size of $S_t$ should be _eventually_ quasipolynomial -- that is, it should agree with a quasipolynomial for sufficiently large $t$. Woods conjectured that eventual quasipolynomial behaviour should occur whenever the family is definable in _parametric Presburger arithmetic_. Roughly what this means (for a more precise definition, see the paper) is that the family $S_t$ of subsets of $\mathbb Z^d$ can be defined using addition, inequalities, integer constants, Boolean operations, multiplication by $t$, and quantification over $\mathbb Z$. The polytopes discussed earlier are examples. For a somewhat different kind of example, let $S_t$ be the set of positive integers $n$ such that there do not exist non-negative integers $a,b,c$ with $n=at+b(t+1)+c(t+2)$. This example involves quantification over $\mathbb Z$, but again the number of points in $S_t$ turns out to be quasipolynomial: in fact, it is $\lfloor t^2/4 \rfloor$ (the paper also discusses a quasipolynomial formula for the maximum element of $S_t$). Note that it is crucial in this definition that multiplication, except by the parameter $t$, should not be allowed, since otherwise we would have the full power of Peano arithmetic, which is undecidable. The main result of this paper is a proof of this very appealing conjecture. The proof uses a series of reductions that make the family simpler and simpler until the result can be shown using previously developed methods. One of the reductions uses the well-known technique of quantifier elimination. However, this cannot be applied straightforwardly, owing to the multiplication-by-$t$ operation, which is not part of standard Presburger arithmetic (hence the word "parametric"). The paper also discusses the power of parametric Presburger arithmetic, which, considering the necessary restrictions, is greater than one might expect. Thus, it proves eventual quasipolynomial behaviour for an extremely wide class of families and is probably the most general result one could hope for along these lines. <sup><sub>[Image created by Georgios Barmparis, Georgios Kopidakis and Ioannis Remediakis](http://www.mdpi.com/1996-1944/9/4/301/htm)</sub></sup>