✦ LIBER ✦

Arithmetical definability over finite structures

✍ Scribed by Troy Lee

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 134 KB
Volume: 49
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.200310041

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Arithmetical definability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical definability over finite structures, motivated by the correspondence between uniform AC^0^ and FO(PLUS, TIMES). We prove finite analogs of three classic results in arithmetical definability, namely that < and TIMES can first‐order define PLUS, that < and DIVIDES can first‐order define TIMES, and that < and COPRIME can first‐order define TIMES. The first result sharpens the equivalence FO(PLUS, TIMES) =FO(BIT) to FO(<, TIMES) = FO(BIT), answering a question raised by Barrington et al. about the Crane Beach Conjecture. Together with previous results on the Crane Beach Conjecture, our results imply that FO(PLUS) is strictly less expressive than FO(<, TIMES) = FO(<, DIVIDES) = FO(<,COPRIME). In more colorful language, one could say that, for parallel computation, multiplication is harder than addition.

📜 SIMILAR VOLUMES

Finite Groups over Arithmetical Rings an

Finite Groups over Arithmetical Rings and Globally Irreducible Representations

✍ F. Van Oystaeyen; A.E. Zalesski ĭ 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 142 KB

Given the ring of integers R of an algebraic number field K, for which natural Ž . number n is there a finite group G ; GL n, R such that RG, the R-span of G, Ž . Ž . Ž . coincides with M n, R , the ring of n = n -matrices over R? Given G ; GL n, R Ž . we show that RG s M n, R if and only if the Bra

A Companion to Philosophical Logic || Lo

A Companion to Philosophical Logic || Logic in Finite Structures: Definability, Complexity, and Randomness

✍ Jacquette, Dale 📂 Article 📅 2006 🏛 Blackwell Publishing Ltd 🌐 English ⚖ 132 KB

Edited By Dale Jacquette. Includes Bibliographical References And Index.

Order counting of elliptic curves define

Order counting of elliptic curves defined over finite fields of characteristic 2

✍ Tetsuya Izu; Jun Kogure; Masayuki Noro; Kazuhiro Yokoyama 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

Zeros of a Pair of Quadratic Forms Defin

Zeros of a Pair of Quadratic Forms Defined over a Finite Field

✍ David B. Leep; Laura Mann Schueller 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 155 KB

Let N be the number of affine zeros of a pair of quadratic forms in n#1 variables defined over a finite field F O . We give upper and lower bounds for N and show that these bounds are optimal. One result states that if n#1510 and every quadratic form in the pencil has order at least three, then "N!q

Group Structure of Elliptic Curves over

Group Structure of Elliptic Curves over Finite Fields

✍ Christian Wittmann 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 123 KB

Let A be a finite abelian group such that there is an elliptic curve defined over a finite field F q with E(F q )$A. We will determine the possible group structures E(F q k) as E varies over all elliptic curves defined over F q with E(F q )$A.

Group Structures of Elementary Supersing

Group Structures of Elementary Supersingular Abelian Varieties over Finite Fields

✍ Hui June Zhu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 176 KB

Let A be a supersingular abelian variety over a finite field k which is k-isogenous to a power of a simple abelian variety over k. Write the characteristic polynomial of the Frobenius endomorphism of A relative to k as f = g e for a monic irreducible polynomial g and a positive integer e. We show th