A quantifier elimination for the theory of \(p\)-adic numbers
type: Item
instance of: scholarly article
title: A quantifier elimination for the theory of \(p\)-adic numbers
zbMATH Open document ID: 0922.11108
author: Lavinia Egidi
published in: Computational Complexity
publication date: 1999-07-20T00:00:00Z
review text: A lower bound for the decision problem in the first order theory of \(p\)-adic numbers has been known for a long time. As for the upper bound, the best algorithm known so far is that of \textit{P. J. Cohen} [Decision procedures for real and \(p\)-adic fields, Commun. Pure Appl. Math. 22, 131-151 (1969; Zbl 0167.01502)]; it is primitive recursive but not elementary. The analysed formula is expanded dramatically each time a quantifier is eliminated. A similar problem was faced before in the context of the first order theory of the reals \textit{Th} \(\mathbb R\). Consider, for instance, Cohen's real counterpart of his own algorithm for \textit{Th} \(\mathbb Q_p\). It treats the quantified variables one at a time and suffers from exponential growth at each step of the recursion. Consider the solution proposed in the real case by \textit{G. E. Collins} [Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Lect. Notes Comput. Sci. 33, 134-183 (1975; Zbl 0318.02051)]. Every atomic formula in the language of \textit{Th} \(\mathbb R\) is a polynomial inequality, in other words, it states that some polynomial is a square. Collins' procedure partitions a space into a finite number of sets (Cells), in each of which every polynomial that appears in the sentence to be decided has constant sign. Then a point is chosen from each cell \(C\) to determine the sign that each of the polynomials involved has in \(C\). Now each existential (resp. universal) quantifier can be replaced by a finite disjunction (resp. conjunction) of the polynomial inequalities evaluated in the sample points. So, a block of quantifiers is eliminated in a single step. The decomposition of the space into cells can be done efficiently. Some analogies between the real field and the \(p\)-adic field \(\mathbb Q_p\) suggest that it is reasonable to expect that an elementary algorithm could be obtained by using Collins' method on the \(p\)-adics. In [\textit{P. Scowcroft} and \texti…
Mathematics Subject Classification ID: 11U05
Mathematics Subject Classification ID: 03C60
Mathematics Subject Classification ID: 03C10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1247753
zbMATH Keywords: complexity
zbMATH Keywords: quantifier elimination
zbMATH Keywords: \(p\)-adic numbers
zbMATH Keywords: upper bound for decision problem
MaRDI profile type: Publication
full work available at URL: s000370050011
OpenAlex ID: W2006885630
DOI: 10.1007/S000370050011
description: scientific article; zbMATH DE number 1247753