A proof of Pisot's dth root conjecture

We propose a function-field analog of Pisot's $d$-th root conjecture on linear recurrences, and prove it under some "non-triviality" assumption. Besides a recent result of Pasten-Wang on B{\"u}chi's $d$-th power problem, our main tool, which is also developed in this paper, is a function-field analog of an GCD estimate in a recent work of Levin and Levin-Wang. As an easy corollary of such GCD estimate, we also obtain an asymptotic result.

We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field $\mathbb{K}$. More precisely, given a precision $d$, and a polynomial $Q$ whose coefficients are power series in $x$, the algorithm computes a representation of all power series $f(x)$ such that $Q(f(x)) = 0 \bmod x^d$. The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails. Our main motivation comes from coding...

Let k be a number field. It is well known that the set of sequences composed by Taylor coefficients of rational functions over k is closed under component-wise operations, and so it can be equipped with a ring structure. A conjecture due to Pisot asks if (after enlarging the field) one can take d-th roots in this ring, provided d-th roots of coefficients can be taken in k. This was proved true in a preceding paper of the second author; in this article we generalize this resul...

Let $P(x):=a_d x^d+\cdots+a_0\in\mathbb{Q}[x]$, $a_d>0$, be a polynomial of degree $d\geq 2$. Let $(x_n)$ be a sequence of integers satisfying \begin{equation*} x_{n+1}=P(x_n)\mbox{for all}\quad n=0,1,2\ldots,\quad\mbox{and} \quad x_n\to\infty\quad\mbox{as}\quad n\to\infty. \end{equation*} Set $\alpha:=\lim_{n\to\infty} x^{d^{-n}}_n$. Then, under the assumption $a_d^{1/(d-1)}\in\mathbb{Q}$, in a recent result by Dubickas \cite{dubickas}, either $\alpha$ is transcendental, o...

About fifty years ago Mahler proved that if $\alpha>1$ is rational but not an integer and if $0<l<1$ then the fractional part of $\alpha^n$ is $>l^n$ apart from a finite set of integers $n$ depending on $\alpha$ and $l$. Answering completely a question of Mahler we show that the same conclusion holds for all algebraic numbers which are not $d$-th roots of Pisot numbers. By related methods, we also answer a question by Mendes France, characterizing completely the quadratic irr...

This paper presents two algorithms on certain computations about Pisot numbers. Firstly, we develop an algorithm that finds a Pisot number $\alpha$ such that $\Q[\alpha] = \F$ given a real Galois extension $\F$ of $\Q$ by its integral basis. This algorithm is based on the lattice reduction, and it runs in time polynomial in the size of the integral basis. Next, we show that for a fixed Pisot number $\alpha$, one can compute $ [\alpha^n] \pmod{m}$ in time polynomial in $(\log ...

We consider integer sequences that satisfy a recursion of the form $x_{n+1} = P(x_n)$ for some polynomial $P$ of degree $d > 1$. If such a sequence tends to infinity, then it satisfies an asymptotic formula of the form $x_n \sim A \alpha^{d^n}$, but little can be said about the constant $\alpha$. In this paper, we show that $\alpha$ is always irrational or an integer. In fact, we prove a stronger statement: if a sequence $G_n$ satisfies an asymptotic formula of the form $G_n ...

A sequence of functions {f_n(q)}_{n=1}^{\infty} satisfies the functional equation for multiplication of quantum integers if f_{mn}(q) = f_m(q)f_n(q^m) for all positive integers m and n. This paper describes the structure of all sequences of rational functions with rational coefficients that satisfy this functional equation.

We study rational numbers with purely periodic R\'enyi $\beta$-expansions. For bases $\beta$ satisfying $\beta^2=a\beta+b$ with $b$ dividing $a$, we give a necessary and sufficient condition for $\gamma(\beta)=1$, i.e., that all rational numbers $p/q\in[0,1)$ with $\gcd(q,b)=1$ have a purely periodic $\beta$-expansion. A simple algorithm for determining the value of $\gamma(\beta)$ for all quadratic Pisot numbers $\beta$ is described.

Let $F$ be a field and let $F(X_1,\dots,X_n)$ be the field of rational functions in $n$ variables $X_1,\dots,X_n$ over $F$. Let $T=X_1+\cdots+X_n\in F(X_1,\dots,X_n)$ and let $m$ be a positive integer such that $\text{char}\,F\nmid m$. Is it possible to express each $X_i$ as a rational function in $X_1^m\dots,X_n^m$ and $T$ over $F$? It is not difficult to prove that this can be done but it is another matter to show how this is done. We answer the above question affirmatively...