Search

A theorem of Cobham says that if $k$ and $\ell$ are two multiplicatively independent natural numbers then a subset of the natural numbers that is both $k$- and $\ell$-automatic is eventually periodic. A multidimensional extension was later given by Semenov. In this paper, we give a quantitative version of the Cobham-Semenov theorem for sparse automatic sets, showing that the intersection of a sparse $k$-automatic subset of $\mathbb{N}^d$ and a sparse $\ell$-automatic subset of $\mathbb{N}^d$ is finite with size that can be explicitly bounded in terms of data from the automata that accept these sets., 14 pages

We prove a result that can be seen as an analogue of the Pólya-Carlson theorem for multivariate D-finite power series with coefficients in $\bar{\mathbb{Q}}$. In the special case that the coefficients are algebraic integers, our main result says that if $$F(x_1,\ldots ,x_m)=\sum f(n_1,\ldots ,n_m)x_1^{n_1}\cdots x_m^{n_m}$$ is a D-finite power series in $m$ variables with algebraic integer coefficients and if the logarithmic Weil height of $f(n_1,\ldots ,n_m)$ is $o(n_1+\cdots +n_m)$, then $F$ is a rational function and, up to scalar multiplication, every irreducible factor of the denominator of $F$ has the form $1-ζx_1^{q_1}\cdots x_m^{q_m}$ where $ζ$ is a root of unity and $q_1,\ldots ,q_m$ are nonnegative integers, not all of which are zero.

We improve known estimates for the number of points of bounded height in semigroup orbits of polarized dynamical systems. In particular, we give exact asymptotics for generic semigroups acting on the projective line. The main new ingredient is the Wiener-Ikehara Tauberian theorem, which we use to count functions in semigroups of bounded degree.

Let $G$ be a semiabelian variety defined over an algebraically closed field $K$ of characteristic $0$. Let $\Phi\colon G\dashrightarrow G$ be a dominant rational self-map. Assume that an iterate $\Phi^m \colon G \to G$ is regular for some $m \geqslant 1$ and that there exists no non-constant homomorphism $\tau: G\to G_0$ of semiabelian varieties such that $\tau\circ \Phi^{m k}=\tau$ for some $k \geqslant 1$. We show that under these assumptions $\Phi$ itself must be a regular. We also prove a variant of this assertion in prime characteristic and present examples showing that our results are sharp., Comment: 15 pages

We consider D-finite power series $f(z)=\sum a_n z^n$ with coefficients in a number field $K$. We show that there is a dichotomy governing the behaviour of $h(a_n)$ as a function of $n$, where $h$ is the absolute logarithmic Weil height. As an immediate consequence of our results, we have that either $f(z)$ is rational or $h(a_n)>[K:\mathbb{Q}]^{-1}\cdot \log(n)+O(1)$ for $n$ in a set of positive upper density and this is best possible when $K=\mathbb{Q}$., Minor change in the proof of Proposition 4.1

We study an open question at the interplay between the classical and the dynamical Mordell-Lang conjectures in positive characteristic. Let $K$ be an algebraically closed field of positive characteristic, let $G$ be a finitely generated subgroup of the multiplicative group of $K$, and let $X$ be a (irreducible) quasiprojective variety defined over $K$. We consider $K$-valued sequences of the form $a_n:=f(\varphi^n(x_0))$, where $\varphi\colon X\rightarrow X$ and $f\colon X\rightarrow\mathbb{P}^1$ are rational maps defined over $K$ and $x_0\in X$ is a point whose forward orbit avoids the indeterminacy loci of $\varphi$ and $f$. We show that the set of $n$ for which $a_n\in G$ is a finite union of arithmetic progressions along with a set of upper Banach density zero. In addition, we show that if $a_n\in G$ for every $n$ and the $\varphi$ orbit of $x$ is Zariski dense in $X$ then {there is} a multiplicative torus $\mathbb{G}_m^d$ and maps $\Psi:\mathbb{G}_m^d \to \mathbb{G}_m^d$ and $g:\mathbb{G}_m^d \to \mathbb{G}_m$ such that $a_n = g\circ \Psi^n(y)$ for some $y\in \mathbb{G}_m^d$. We then describe various applications of our results., Comment: 13 pages. arXiv admin note: text overlap with arXiv:2005.04281

Let $L$ be a field of characteristic zero, let $h:\mathbb{P}^1\to \mathbb{P}^1$ be a rational map defined over $L$, and let $c\in \mathbb{P}^1(L)$. We show that there exists a finitely generated subfield $K$ of $L$ over which both $c$ and $h$ are defined along with an infinite set of inequivalent non-archimedean completions $K_{\mathfrak{p}}$ for which there exists a positive integer $a=a(\mathfrak{p})$ with the property that for $i\in \{0,\ldots ,a-1\}$ there exists a power series $g_i(t)\in K_{\mathfrak{p}}[[t]]$ that converges on the closed unit disc of $K_{\mathfrak{p}}$ such that $h^{an+i}(c)=g_i(n)$ for all sufficiently large $n$. As a consequence we show that the dynamical Mordell-Lang conjecture holds for split self-maps $(h,g)$ of $\mathbb{P}^1 \times X$ with $g$ \'etale., Comment: 12 pages

Let $G$ be a semiabelian variety defined over an algebraically closed field $K$, endowed with a rational self-map $\Phi$. Let $\alpha\in G(K)$ and let $\Gamma\subseteq G(K)$ be a finitely generated subgroup. We show that the set $\{n\in\mathbb{N}\colon \Phi^n(\alpha)\in \Gamma\}$ is a union of finitely many arithmetic progressions along with a set of Banach density equal to $0$. In addition, assuming $\Phi$ is regular, we prove that the set $S$ must be finite., Comment: 12 pages

We disprove a 2002 conjecture of Dombi from additive number theory. More precisely, we find examples of sets $A \subset \mathbb{N}$ with the property that $\mathbb{N} \setminus A$ is infinite, but the sequence $n \rightarrow |\{ (a,b,c) \, : \, n=a+b+c \text{ and } a,b,c \in A \}|$, counting the number of $3$-compositions using elements of $A$ only, is strictly increasing., Comment: additional author added; largely rewritten with different example

We prove a general criterion for an irrational power series $f(z)=\displaystyle\sum_{n=0}^{\infty}a_nz^n$ with coefficients in a number field $K$ to admit the unit circle as a natural boundary. As an application, let $F$ be a finite field, let $d$ be a positive integer, let $A\in M_d(F[t])$ be a $d\times d$-matrix with entries in $F[t]$, and let $ζ_A(z)$ be the Artin-Mazur zeta function associated to the multiplication-by-$A$ map on the compact abelian group $F((1/t))^d/F[t]^d$. We provide a complete characterization of when $ζ_A(z)$ is algebraic and prove that it admits the circle of convergence as a natural boundary in the transcendence case. This is in stark contrast to the case of linear endomorphisms on $\mathbb{R}^d/\mathbb{Z}^d$ in which Baake, Lau, and Paskunas prove that the zeta function is always rational. Some connections to earlier work of Bell, Byszewski, Cornelissen, Miles, Royals, and Ward are discussed. Our method uses a similar technique in recent work of Bell, Nguyen, and Zannier together with certain patching arguments involving linear recurrence sequences.

We give a formula for the cyclotomic valuation of $q$-Pochhammer symbols in terms of (generalized) Dwork maps. We also obtain a criterion for the $q$-integrality of basic hypergeometric series in terms of certain step functions, which generalize Christol step functions. This provides suitable $q$-analogs of two results proved by Christol: a formula for the $p$-adic valuation of Pochhammer symbols and a criterion for the $N$-integrality of hypergeometric series.

We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number [Formula: see text] is the sum of at most three natural numbers whose base-[Formula: see text] representation has an equal number of [Formula: see text]’s and [Formula: see text]’s.

We prove an analog of the Tits alternative for rational functions. In particular, we show that if $S$ is a finitely generated semigroup of rational functions over the complex numbers, then either $S$ has polynomially bounded growth or $S$ contains a nonabelian free semigroup. We also show that if f and g are polarizable maps over any field that do not have the same set of preperiodic points, then the semigroup generated by f and g contains a nonabelian free semigroup., Comment: 16 pages

Let $X$ be a projective variety and let $f$ be a dominant endomorphism of $X$, both of which are defined over a number field $K$. We consider a question of the second author, Meng, Shibata, and Zhang, which asks whether the tower of $K$-points $Y(K)\subseteq (f^{-1}(Y))(K)\subseteq (f^{-2}(Y))(K)\subseteq \cdots$ eventually stabilizes, where $Y\subset X$ is a subvariety invariant under $f$. We show this question has an affirmative answer when the map $f$ is \'etale. We also look at a related problem of showing that there is some integer $s_0$, depending only on $X$ and $K$, such that whenever $x, y \in X(K)$ have the property that $f^{s}(x) = f^{s}(y)$ for some $s \geq 0$, we necessarily have $f^{s_{0}}(x) = f^{s_{0}}(y)$. We prove this holds for \'etale morphisms of projective varieties, as well as self-morphisms of smooth projective curves. We also prove a more general cancellation theorem for polynomial maps on $\mathbb{P}^1$ where we allow for composition by multiple different maps $f_1,\dots,f_r$., Comment: 27 pages

Let $q$ a prime power and ${\mathbb F}_q$ the finite field of $q$ elements. We study the analogues of Mahler's and Koksma's classifications of complex numbers for power series in ${\mathbb F}_q((T^{-1}))$. Among other results, we establish that both classifications coincide, thereby answering a question of Ooto.

The isotrivial Mordell-Lang theorem of Moosa and Scanlon describes the set $X\cap\Gamma$ when $X$ is a subvariety of a semiabelian variety $G$ over a finite field $\mathbb{F}_q$ and $\Gamma$ is a finitely generated subgroup of $G$ that is invariant under the $q$-power Frobenius endomorphism $F$. That description is here made effective, and extended to arbitrary commutative algebraic groups $G$ and arbitrary finitely generated $\mathbb{Z}[F]$-submodules $\Gamma$. The approach is to use finite automata to give a concrete description of $X\cap \Gamma$. These methods and results have new applications even when specialised to the case when $G$ is an abelian variety over a finite field, $X\subseteq G$ a subvariety defined over a function field $K$, and $\Gamma=G(K)$. As an application of the automata-theoretic approach, a dichotomy theorem is established for the growth of the number of points in $X(K)$ of bounded height. As an application of the effective description of $X\cap\Gamma$, decision procedures are given for the following three diophantine problems: Is $X(K)$ nonempty? Is it infinite? Does it contain an infinite coset?

In previous work, the first author, Ghioca, and the third author introduced a broad dynamical framework giving rise to many classical sequences from number theory and algebraic combinatorics. Specifically, these are sequences of the form $f(\Phi^n(x))$, where $\Phi\colon X\to X$ and $f\colon X\to\mathbb{P}^1$ are rational maps defined over $\overline{\mathbb{Q}}$ and $x\in X(\overline{\mathbb{Q}})$ is a point whose forward orbit avoids the indeterminacy loci of $\Phi$ and $f$. They conjectured that if the sequence is infinite, then $\limsup \frac{h(f(\Phi^n(x)))}{\log n} > 0$. They also made a corresponding conjecture for $\liminf$ and showed that it implies the Dynamical Mordell-Lang Conjecture. In this paper, we prove the $\limsup$ conjecture as well as the $\liminf$ conjecture away from a set of density $0$. As applications, we prove results concerning the growth rate of coefficients of $D$-finite power series as well as the Dynamical Mordell-Lang Conjecture up to a set of density $0$.

A famous result of Christol gives that a power series $F(t)=\sum_{n\ge 0} f(n)t^n$ with coefficients in a finite field $\mathbb{F}_q$ of characteristic $p$ is algebraic over the field of rational functions in $t$ if and only if there is a finite-state automaton accepting the base-$p$ digits of $n$ as input and giving $f(n)$ as output for every $n\ge 0$. An extension of Christol's theorem, giving a complete description of the algebraic closure of $\mathbb{F}_q(t)$, was later given by Kedlaya. When one looks at the support of an algebraic power series, that is the set of $n$ for which $f(n)\neq 0$, a well-known dichotomy for sets generated by finite-state automata shows that the support set is either sparse---with the number of $n\le x$ for which $f(n)\neq 0$ bounded by a polynomial in $\log(x)$---or it is reasonably large in the sense that the number of $n\le x$ with $f(n)\neq 0$ grows faster than $x^{\alpha}$ for some positive $\alpha$. The collection of algebraic power series with sparse supports forms a ring and we give a purely algebraic characterization of this ring in terms of Artin-Schreier extensions and we extend this to the context of Kedlaya's work on generalized power series., Comment: 21 pages; statement of main theorem updated slightly

A (noncommutative) P��lya series over a field $K$ is a formal power series whose nonzero coefficients are contained in a finitely generated subgroup of $K^\times$. We show that rational P��lya series are unambiguous rational series, proving a 40 year old conjecture of Reutenauer. The proof combines methods from noncommutative algebra, automata theory, and number theory (specifically, unit equations). As a corollary, a rational series is a P��lya series if and only if it is Hadamard sub-invertible. Phrased differently, we show that every weighted finite automaton taking values in a finitely generated subgroup of a field (and zero) is equivalent to an unambiguous weighted finite automaton., 35 pages; added several examples

Using methods of p-adic analysis, along with the powerful result of Medvedev-Scanlon (Annals of Mathematics, 2014) for the classification of periodic subvarieties of (P^1)^n, we bound the length of the orbit of a periodic subvariety Y of (P^1)^n under the action of a dominant endomorphism.

The classical notion of a k-automatic subset of the natural numbers is here extended to that of an F-automatic subset of an arbitrary finitely generated abelian group $\Gamma$ equipped with an arbitrary endomorphism F. This is applied to the isotrivial positive characteristic Mordell-Lang context where F is the Frobenius action on a commutative algebraic group G over a finite field, and $\Gamma$ is a finitely generated F-invariant subgroup of G. It is shown that the F-subsets of $\Gamma$ introduced by the second author and Scanlon are F-automatic. It follows that when G is semiabelian and X is a closed subvariety then X intersect $\Gamma$ is F-automatic. Derksen's notion of a k-normal subset of the natural numbers is also here extended to the above abstract setting, and it is shown that F-subsets are F-normal. In particular, the X intersect $\Gamma$ appearing in the Mordell-Lang problem are F-normal. This generalises Derksen's Skolem-Mahler-Lech theorem to the Mordell-Lang context., Comment: The final section is revised following an error discovered by Christopher Hawthorne; it is no longer claimed that an F-normal subset has a finite symmetric difference with an F-subset. The main theorems of the paper remain unchanged

We prove congruence relations modulo cyclotomic polynomials for multisums of $q$-factorial ratios, therefore generalizing many well-known $p$-Lucas congruences. Such congruences connect various classical generating series to their $q$-analogs. Using this, we prove a propagation phenomenon: when these generating series are algebraically independent, this is also the case for their $q$-analogs., Extended abstract submitted to FPSAC 2017

Motivated by work of Zhang from the early `90s, Medvedev and Scanlon formulated the following conjecture. Let $K$ be an algebraically closed field of characteristic $0$ and let $X$ be a quasiprojective variety defined over $K$ endowed with a dominant rational self-map $\Phi$. Then there exists a point $\alpha\in X(K)$ with Zariski dense orbit under $\Phi$ if and only if $\Phi$ preserves no nontrivial rational fibration, i.e., there exists no non-constant rational function $f\in K(X)$ such that $\Phi^*(f)=f$. The Medvedev-Scanlon conjecture holds when $K$ is uncountable. The case where $K$ is countable (e.g., $K=\overline{\mathbb{Q}}$) is much more difficult; here the conjecture has only been proved in a small number of special cases. In this paper we show that the Medvedev-Scanlon conjecture holds for all varieties of positive Kodaira dimension, and explore the case of Kodaira dimension $0$. Our results are most complete in dimension $3$., Comment: Minor changes limited to the Introduction concerning past work on the conjecture

We develop a new method for proving algebraic independence of $G$-functions. Our approach rests on the following observation: $G$-functions do not always come with a single linear differential equation, but also sometimes with an infinite family of linear difference equations associated with the Frobenius that are obtained by reduction modulo prime ideals. When these linear difference equations have order one, the coefficients of the $G$-function satisfy congruences reminiscent of a classical theorem of Lucas on binomial coefficients. We use this to derive a Kolchin-like algebraic independence criterion. We show the relevance of this criterion by proving, using p-adic tools, that many classical families of $G$-functions turn out to satisfy congruences "�� la Lucas".

We study how well Fekete polynomials $$ F_p(X) = \sum_{n=0}^{p-1} \left(\frac{n}{p}\right) X^n \in {\mathbb Z}[X] $$ with the coefficients given by Legendre symbols modulo a prime $p$, can be approximated by power series representing algebraic functions of a given degree. We also obtain some explicit results describing polynomial recurrence relations which are satisfied by the coefficients of such algebraic functions.

The Skolem-Mahler-Lech theorem states that if $f(n)$ is a sequence given by a linear recurrence over a field of characteristic 0,then the set of $m$ such that $f(m)$ is equal to 0 is the union of a finite number of arithmetic progressions in $m\ge 0$ and a finite set. We prove that if $X$ is a subvariety of an affine variety $Y$ over a field of characteristic 0 and ${\bf q}$ is a point in $Y$, and $\sigma$ is an automorphism of $Y$, then the set of $m$ such that $\sigma^m({\bf q})$ lies in $X$ is a union of a finite number of complete doubly-infinite arithmetic progressions and a finite set. We show that this is a generalization of the Skolem-Mahler-Lech theorem., Comment: 23 pages

We determine a lower gap property for the growth of an unbounded \(\mathbb{Z}\)-valued \(k\)-regular sequence. In particular, if \(f:\mathbb{N}\to\mathbb{Z}\) is an unbounded \(k\)-regular sequence, we show that there is a constant \(c>0\) such that \(|f(n)|>c\log n\) infinitely often. We end our paper by answering a question of Borwein, Choi, and Coons on the sums of completely multiplicative automatic functions., 8 pages

Let $K$ be a field of characteristic zero and $k$ and $l$ be two multiplicatively independent positive integers. We prove the following result that was conjectured by Loxton and van der Poorten during the Eighties: a power series $F(z)\in K[[z]]$ satisfies both a $k$- and a $l$-Mahler type functional equation if and only if it is a rational function., Comment: 52 pages

In this paper, we give a new proof of a result due to Bezivin that a D-finite Mahler function is necessarily rational. This also gives a new proof of the rational-transcendental dichotomy of Mahler functions due to Nishioka. Using our method of proof, we also provide a new proof of a Polya-Carlson type result for Mahler functions due to Rande; that is, a Mahler function which is meromorphic in the unit disk is either rational or has the unit circle as a natural boundary., Comment: 10 pages, 1 figure; added reference to Bezivin's paper

Let $K$ be a field of characteristic 0, $f:\mathbb{N}\to K$ be a multiplicative function, and $F(z)=\sum_{n\geq 1} f(n)z^n\in K[[z]]$ be algebraic over $K(z)$. Then either there is a natural number $k$ and a periodic multiplicative function $\chi(n)$ such that $f(n)=n^k \chi(n)$ for all $n$, or $f(n)$ is eventually zero. In particular, the generating function of a multiplicative function $f:\mathbb{N}\to K$ is either transcendental or rational., Comment: This paper has been withdrawn and replaced with a more current version; see arXiv:1003.2221

We prove a dynamical version of the Mordell-Lang conjecture for etale endomorphisms of quasiprojective varieties. We use p-adic methods inspired by the work of Skolem, Mahler, and Lech, combined with methods from algebraic geometry. As special cases of our result we obtain a new proof of the classical Mordell-Lang conjecture for cyclic subgroups of a semiabelian variety, and we also answer positively a question of Keeler/Rogalski/Stafford for critically dense sequences of closed points of a Noetherian integral scheme., Comment: 19 pages

We study certain step functions whose nonnegativity is related to the integrality of sequences of ratios of factorial products. In particular, we obtain a lower bound for the mean square of such step functions which allows us to give a restriction on when such a factorial ratio sequence can be integral. Additionally, we note that this work has applications to the classification of cyclic quotient singularities., Comment: 11 Pages; argument improved and simplified; references added

We consider real sequences $(f_n)$ that satisfy a linear recurrence with constant coefficients. We show that the density of the positivity set of such a sequence always exists. In the special case where the sequence has no positive dominating characteristic root, we establish that the density is positive. Furthermore, we determine the values that can occur as density of such a positivity set, both for the special case just mentioned and in general.