Source author record

Alexandra Shlapentokh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO math.NT math.AG math.CT

Catalog footprint

Research overview

12works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On existential definitions of C.E. subsets of rings of functions of characteristic 0

We extend results of Denef, Zahidi, Demeyer and the second author to show the following. (1) Rational integers have a single-fold Diophantine definition over the ring of integral functions of any function field of characteristic 0. (2) Every c.e. set of integers has a finite-fold Diophantine definition over the ring of integral functions of any function field of characteristic $0$ . (3) All c.e. subsets of polynomial rings over totally real number fields have finite-fold Diophantine definitions. (These are the first examples of infinite rings with this property.) (4) If $k$ is algebraic over $\Q$ and is embeddable into a finite extension of $\Q_p$ for odd $p$ , and $K$ is a one-variable function field over $k$ , then the valuation ring of any function field valuation of $K$ has a Diophantine definition over $K$ . (5) If $k$ is algebraic over $\Q$ and is embeddable into $\R$ , and $K$ is a function field over $k$ , then "almost" all function field valuations of $K$ have a valuation ring Diophantine over $K$ . (6) Let $K$ be a one-variable function field over a number field and let $S$ be a finite set of its primes. Then all c.e. subsets of $O_{K,S}$ are existentially definable. (Here $O_{K,S}$ is the ring of $S$ -integers or a ring of integral functions.)

preprint2015arXiv

A Computable Functor From Graphs to Fields

We construct a fully faithful functor from the category of graphs to the category of fields. Using this functor, we resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure S, there exists a countable field F with the same essential computable-model-theoretic properties as S. Along the way, we develop a new "computable category theory," and prove that our functor and its partially-defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors.

preprint2015arXiv

On decidable algebraic fields

We prove the following propositions. Theorem 1: Let $M$ be a subfield of a fixed algebraic closure $\tilde \Q$ of $\Q$ whose existential elementary theory is decidable (resp. primitively decidable). Then, M is conjugate to a recursive (resp. primitive recursive) subfield $L \subset \tilde \Q$. Theorem 2: For each positive integer $e$ there are infinitely many $e$ -tuples $\boldsymbol σ\in \Gal(\Q)^e$ such that the field $\tilde \Q( {\boldsymbol σ})$ -- the fixed field of $\boldsymbol σ$ , is recursive in $\tilde\Q$ and its elementary theory is decidable. Moreover, $\tilde \Q(\boldsymbol σ)$ is PAC and $\Gal(\tilde\Q(\boldsymbol σ))$ is isomorphic to the free profinite group on $e$ generators.

preprint2015arXiv

On definitions of polynomials over function fields of positive characteristi

We consider the problem of defining polynomials over function fields of positive characteristic. Among other results, we show that the following assertions are true. 1. Let $\G_p$ be an algebraic extension of a field of $p$ elements and assume $\G_p$ is not algebraically closed. Let $t$ be transcendental over $\G_p$, and let $K$ be a finite extension of $\G_p(t)$. In this case $\G_p[t]$ has a definition (with parameters) over $K$ of the form $\forall \exists \ldots \exists P$ with only one variable in the range of the universal quantifier and $P$ being a polynomial over $K$ . 2. For any $q$ , for all $p \not=q$ and all function fields $K$ as above with $\G_p$ having an extension of degree $q$ and a primitive $q$ -th root of unity, there is a uniform in $p$ and $K$ definition (with parameters) of $\G_p[t]$, of the form $\exists \ldots \exists \forall \forall \exists \ldots \exists P$ with only two variables in the range of universal quantifiers and $P$ being a finite collection of disjunction and conjunction of polynomial equations over $\Z/p$ . Further, for any finite collection $\calS_K$ of primes of $K$ of fixed size $m$ , there is a uniform in $K$ and $p$ definition of the ring of $\calS_K$-integers of the form $\forall\forall\exists \ldots \exists P$ with the range of universal quantifiers and $P$ as above. 3. Let $M$ be a function field of positive characteristic in one variable $t$ over an arbitrary constant field $H,$ and let $\G_p$ be the algebraic closure of a finite field in $H$ . Assume $\G_p$ is not algebraically closed. In this case $\G_p[t]$ is first-order definable over $M$ .

preprint2014arXiv

First Order Decidability and Definability of Integers in Infinite Algebraic Extensions of Rational Numbers

We extend results of Videla and Fukuzaki to define algebraic integers in large classes of infinite algebraic extensions of Q and use these definitions for some of the fields to show the first-order undecidability. We also obtain a structural sufficient condition for definability of the ring of integers over its field of fractions. In particular, we show that the following propositions hold. (1) For any rational prime $q$ and any positive rational integer $m$ , algebraic integers are definable in any Galois extension of Q where the degree of any finite subextension is not divisible by $q^{m}$ . (2) Given a prime $q$ , and an integer $m>0$ , algebraic integers are definable in a cyclotomic extension (and any of its subfields) generated by any set $\{ξ_{p^{\ell}}| \ell \in \Z_{>0}, p \not=q {is any prime such that} q^{m +1}\not | (p-1)\}$ . (3) The first-order theory of any abelian extension of Q with finitely many ramified rational primes is undecidable. We also show that under a condition on the splitting of one rational prime in an infinite algebraic extension of Q, the existence of a finitely generated elliptic curve over the field in question is enough to have a definition of Z and to show that the field is indecidable.

preprint2013arXiv

Hilbert's Tenth Problem over Function Fields of Positive Characteristic Not Containing the Algebraic Closure of a Finite Field

We prove that the existential theory of any function field $K$ of characteristic $p> 0$ is undecidable in the language of rings provided that the constant field does not contain the algebraic closure of a finite field. We also extend the undecidability proof for function fields of higher transcendence degree to characteristic 2 and show that the first-order theory of {\bf any} function field of positive characteristic is undecidable in the language of rings without parameters.

preprint2011arXiv

Definability and Decidability in Infinite Algebraic Extensions

We use a generalization of a construction by Ziegler to show that for any field $F$ and any countable collection of countable subsets $A_i \subseteq F, i \in \calI \subset \Z_{>0}$ there exist infinitely many fields $K$ of arbitrary positive transcendence degree over $F$ and of infinite algebraic degree such that each $A_i$ is first-order definable over $K$ . We also use the construction to show that many infinitely axiomatizable theories of fields which are not compatible with the theory of algebraically closed fields are finitely hereditarily undecidable.

preprint2011arXiv

Hilbert's Tenth Problem and Mazur's Conjectures in Complementary Subrings of Number Fields

We show that Hilbert's Tenth Problem is undecidable for complementary subrings of number fields and that the p-adic and archimedean ring versions of Mazur's conjectures do not hold in these rings. More specifically, given a number field K, a positive integer t>1, and t nonnegative computable real numbers delta_1,..., delta_t whose sum is one, we prove that the nonarchimedean primes of K can be partitioned into t disjoint recursive subsets S_1,..., S_t of densities delta_1,..., delta_t, respectively such that Hilbert's Tenth Problem is undecidable for each corresponding ring O_{K,S_i}. We also show that we can find a partition as above such that each ring O_{K,S_i} possesses an infinite Diophantine set which is discrete in every topology of the field. The only assumption on K we need is that there is an elliptic curve of rank one defined over K.

preprint2011arXiv

Turing degrees of isomorphism types of geometric objects

We initiate the computability-theoretic study of ringed spaces and schemes. In particular, we show that any Turing degree may occur as the least degree of an isomorphic copy of a structure of these kinds. We also show that these structures may fail to have a least degree.

preprint2011arXiv

Using Indices of Points on an Elliptic Curve to Construct A Diophantine Model of $\Z$ and Define $\Z$ Using One Universal Quantifier in Very Large Subrings of Number Fields, Including $\Q$

Let $K$ be a number field and let $E$ be an elliptic curve defined and of rank one over $K$ . For a set $\calW_K$ of primes of $K$ , let $O_{K,\calW_K}=\{x\in K: \ord_{\pp}x \geq 0, \forall \pp \not \in \calW_K\}$. Let $P \in E(K)$ be a generator of $E(K)$ modulo the torsion subgroup. Let $(x_n(P),y_n(P))$ be the affine coordinates of $[n]P$ with respect to a fixed Weierstrass equation of $E$ . We show that there exists a set $\calW_K$ of primes of $K$ of natural density one such that in $O_{K,\calW_K}$ multiplication of indices (with respect to some fixed multiple of $P$ ) is existentially definable and therefore these indices can be used to construct a Diophantine model of $\Z$ . We also show that $\Z$ is definable over $O_{K,\calW_K}$ using just one universal quantifier. Both, the construction of a Diophantine model using the indices and the first-order definition of $\Z$ can be lifted to the integral closure of $O_{K,\calW_K}$ in any infinite extension $K_{\infty}$ of $K$ as long as $E(K_{\infty})$ is finitely generated and of rank one.

preprint2010arXiv

Defining Integers

We survey the recent developments in the area that grew out of attempts to extend an analog of Hilbert's Tenth Problem to the field of rational numbers and rings of integers of number fields. The paper is based on a plenary talk the author gave at the North American Annual ASL meeting at the University of Notre Dame in May of 2009.

preprint2010arXiv

The analogue of Büchi's problem for function fields

Büchi's $n$ Squares Problem asks for an integer $M$ such that any sequence $(x_0,...,x_{M-1})$ , whose second difference of squares is the constant sequence $(2)$ (i.e. $x^2_n-2x^2_{n-1}+x_{n-2}^2=2$ for all $n$ ), satisfies $x_n^2=(x+n)^2$ for some integer $x$ . Hensley's problem for $r$ -th powers (where $r$ is an integer $\geq2$ ) is a generalization of Büchi's problem asking for an integer $M$ such that, given integers $ν$ and $a$ , the quantity $(ν+n)^r-a$ cannot be an $r$ -th power for $M$ or more values of the integer $n$ , unless $a=0$ . The analogues of these problems for rings of functions consider only sequences with at least one non-constant term. Let $K$ be a function field of a curve of genus $g$ . We prove that Hensley's problem for $r$ -th powers has a positive answer for any $r$ if $K$ has characteristic zero, improving results by Pasten and Vojta. In positive characteristic $p$ we obtain a weaker result, but which is enough to prove that Büchi's problem has a positive answer if $p\geq 312g+169$ (improving results by Pheidas and the second author).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Alexandra Shlapentokh

Research overview

Is this your work?

12 publications

On existential definitions of C.E. subsets of rings of functions of characteristic 0

A Computable Functor From Graphs to Fields

On decidable algebraic fields

On definitions of polynomials over function fields of positive characteristi

First Order Decidability and Definability of Integers in Infinite Algebraic Extensions of Rational Numbers

Hilbert's Tenth Problem over Function Fields of Positive Characteristic Not Containing the Algebraic Closure of a Finite Field

Definability and Decidability in Infinite Algebraic Extensions

Hilbert's Tenth Problem and Mazur's Conjectures in Complementary Subrings of Number Fields

Turing degrees of isomorphism types of geometric objects

Using Indices of Points on an Elliptic Curve to Construct A Diophantine Model of $\Z$ and Define $\Z$ Using One Universal Quantifier in Very Large Subrings of Number Fields, Including $\Q$

Defining Integers

The analogue of Büchi's problem for function fields

See the researcher in context

Building this map preview

Alexandra Shlapentokh

Research overview

Is this your work?

12 publications

On existential definitions of C.E. subsets of rings of functions of characteristic 0

A Computable Functor From Graphs to Fields

On decidable algebraic fields

On definitions of polynomials over function fields of positive characteristi

First Order Decidability and Definability of Integers in Infinite Algebraic Extensions of Rational Numbers

Hilbert's Tenth Problem over Function Fields of Positive Characteristic Not Containing the Algebraic Closure of a Finite Field

Definability and Decidability in Infinite Algebraic Extensions

Hilbert's Tenth Problem and Mazur's Conjectures in Complementary Subrings of Number Fields

Turing degrees of isomorphism types of geometric objects

Using Indices of Points on an Elliptic Curve to Construct A Diophantine Model of Z\ZZ and Define Z\ZZ Using One Universal Quantifier in Very Large Subrings of Number Fields, Including $\Q$

Defining Integers

The analogue of Büchi's problem for function fields

See the researcher in context

Building this map preview

Using Indices of Points on an Elliptic Curve to Construct A Diophantine Model of $\Z$ and Define $\Z$ Using One Universal Quantifier in Very Large Subrings of Number Fields, Including $\Q$