Büchi's problem in any power for finite fields
Page 1 Next
Hector Pasten (2011)
Acta Arithmetica
Alexis Bès, Ivan Korec (1998)
Fundamenta Mathematicae
Let Sq denote the set of squares, and let be the squaring function restricted to powers of n; let ⊥ denote the coprimeness relation. Let . For every integer n ≥ 2 addition and multiplication are definable in the structures ⟨ℕ; Bn,⊥⟩ and ⟨ℕ; Bn,Sq⟩; thus their elementary theories are undecidable. On the other hand, for every prime p the elementary theory of ⟨ℕ; Bp,SQp⟩ is decidable.
Jean Berstel, Maurice Mignotte (1976)
Bulletin de la Société Mathématique de France
James Jones (1979)
Acta Arithmetica
Christoph Baxa (2000)
Mathematica Slovaca
Thanases Pheidas (2004)
Fundamenta Mathematicae
We prove that the positive-existential theory of addition and divisibility in a ring of polynomials in two variables A[t₁,t₂] over an integral domain A is undecidable and that the universal-existential theory of A[t₁] is undecidable.
Laurent Moret-Bailly, Alexandra Shlapentokh (2009)
Annales de l’institut Fourier
Let be a one-variable function field over a field of constants of characteristic 0. Let be a holomorphy subring of , not equal to . We prove the following undecidability results for : if is recursive, then Hilbert’s Tenth Problem is undecidable in . In general, there exist such that there is no algorithm to tell whether a polynomial equation with coefficients in has solutions in .
Gunther Cornelissen, Thanases Pheidas, Karim Zahidi (2005)
Journal de Théorie des Nombres de Bordeaux
We prove that Hilbert’s Tenth Problem for a ring of integers in a number field has a negative answer if satisfies two arithmetical conditions (existence of a so-called division-ample set of integers and of an elliptic curve of rank one over ). We relate division-ample sets to arithmetic of abelian varieties.
Bjorn Poonen (2009)
Journal of the European Mathematical Society
Thanases Pheidas, Xavier Vidaux (2005)
Fundamenta Mathematicae
We generalize a question of Büchi: Let R be an integral domain, C a subring and k ≥ 2 an integer. Is there an algorithm to decide the solvability in R of any given system of polynomial equations, each of which is linear in the kth powers of the unknowns, with coefficients in C? We state a number-theoretical problem, depending on k, a positive answer to which would imply a negative answer to the question for R = C = ℤ. We reduce a negative answer for k = 2 and for...
Thanases Pheidas (1991)
Inventiones mathematicae
Havel, Ivan M. (1973)
Pokroky matematiky, fyziky a astronomie
Yuri Matijasevič, Julia Robinson (1975)
Acta Arithmetica
Ivan Korec (1994)
Mathematica Slovaca
Juha Honkala (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We show that it is decidable whether or not a given Q-rational series in several noncommutative variables has a cyclic image. By definition, a series r has a cyclic image if there is a rational number q such that all nonzero coefficients of r are integer powers of q.
Juha Honkala (2012)
RAIRO - Theoretical Informatics and Applications
We show that it is decidable whether or not a given Q-rational series in several noncommutative variables has a cyclic image. By definition, a series r has a cyclic image if there is a rational number q such that all nonzero coefficients of r are integer powers of q.
Robert Rumely (2015)
Acta Arithmetica
Let K be a complete, algebraically closed nonarchimedean valued field, and let φ(z) ∈ K(z) have degree d ≥ 2. We study how the resultant of φ varies under changes of coordinates. For γ ∈ GL₂(K), we show that the map factors through a function on the Berkovich projective line, which is piecewise affine and convex up. The minimal resultant is achieved either at a single point in , or on a segment, and the minimal resultant locus is contained in the tree in spanned by the fixed points and poles...
Pinthira Tangsupphathawat, Narong Punnim, Vichian Laohakosol (2012)
Colloquium Mathematicae
The problem whether each element of a sequence satisfying a fourth order linear recurrence with integer coefficients is nonnegative, referred to as the Positivity Problem for fourth order linear recurrence sequence, is shown to be decidable.
Josef Mlček (1976)
Commentationes Mathematicae Universitatis Carolinae
Ю.В. Матиясевич (1968)
Zapiski naucnych seminarov Leningradskogo
Page 1 Next