On the complexity of algebraic numbers,and the bit-complexity of straight-line programs 1

Abstract

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform ${TC}^{0}$ circuits for division, matrix powering, and related problems, where the improvement is in terms of “majority depth” (initially studied by Maciel and Thérien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy, and we answer a question posed by Yap.

Keywords

Threshold circuits counting hierarchy algebraic numbers

1. Introduction

In this article, we consider formal languages that are subsets of ${0, 1}^{*} = {s_{0}, s_{1}, \dots}$ (where $s_{0} = λ$ (the empty string), $s_{1} = 0, s_{2} = 1, s_{3} = 00$ etc. in the standard order on ${0, 1}^{*}$ , where short strings precede long strings, and strings of the same length are placed in lexicographic order. Any such language A can be identified with its characteristic sequence $χ_{A} = b_{0} b_{1} b_{2} \dots$ where $b_{i} = 1$ if $s_{i} \in A$ and $b_{i} = 0$ otherwise. The sequence $χ_{A}$ is also the binary representation of a real number in the interval $[0, 1]$ . Thus, it is not uncommon to equate languages with real numbers. (The computability literature contains many investigations of this sort; see, for example, [27,50,53,75].)

Viewed in this light, the finite and co-finite languages correspond exactly to dyadic rational numbers. For instance, the sequences $1000 \dots$ and $0111 \dots$ (corresponding to the languages ${λ}$ and ${x : x \neq λ}$ , respectively) both denote the number $\frac{1}{2} = \sum_{i = 2}^{\infty} 2^{- i}$ . Any real number in $[0, 1]$ that is not a dyadic rational has exactly one binary representation, and hence corresponds to exactly one language. The literature in computability theory (dating back to Turing’s original work [68]) has tended to focus on the placement of various classes of reals in the hierarchy of (non-)computability classes. (See, for example, [27,50,53,75].)

In contrast, the literature in computational complexity theory has tended to focus on the more “practical” questions of either computing approximations of various real numbers to a desired accuracy, or of obtaining all of the first n bits of their binary representations. For example, the original investigations of Hartmanis and Stearns [35], which can be said to have given birth to the field of computational complexity theory, focused on the question of classifying the complexity of various real numbers, in terms of computing the first n bits of their binary representations. Most other papers that have dealt with the complexity of real numbers (such as [3,39,42,52,74]) have continued in a related vein (focusing more often on approximations), as has most of the significant work formalizing the notions of computability and complexity of real functions (e.g., [20,43,71]). We do not dispute the motivations for defining the “complexity” of a real number in this way. After all, there are many applications that require knowing the bits of $\sqrt{2}$ to desired accuracy, whereas we struggle to conceive of a practical application that requires us to take a large string x as input (such as $x = 10^{100}$ ) and return the $x^{th}$ bit of $\sqrt{2}$ .

Nonetheless, there are important theoretical considerations that argue in favor of precisely this sort of investigation. Freivalds [32] provides a very compelling survey of the history of mathematical considerations that have led investigators over the centuries to study “normal” reals and “automatic” reals. (Briefly, a real number corresponding to a language A is automatic if and only if A is regular. For more on this topic, we refer the reader to the book by Allouche and Shallit [11].) It was viewed as a very significant achievement when Adamczewski, Bugeaud, and Luca proved that no irrational algebraic number is automatic [1,2]. (It is an easy exercise to see that every rational number corresponds to a regular language, and hence is automatic.)

In this paper, we give an upper bound on the complexity of languages corresponding to algebraic real numbers. We show that all such languages2

²
It is mistakenly claimed in [25] that these languages lie in ${PH}^{{CH}_{2}}$ . We do not know how to obtain that stronger upper bound.

lie in

{CH}_{5}

: the fifth level of the “counting hierarchy”, whose levels are defined as follows.

${CH}_{1} = PP$

${CH}_{k + 1} = {PP}^{{CH}_{k}}$ .

A real number is algebraic if it is a root of some (non-zero) univariate polynomial with integer coefficients. Jeřábek [39] showed that, for any given constant d, there is a uniform family of ${TC}^{0}$ circuits that will take as input a degree d univariate polynomial p (represented by its sequence of integer coefficients), along with $1^{n}$ , and produce as output the first n bits of the binary representation of each of the roots of p. Because of well-known connections between ${TC}^{0}$ and the counting hierarchy (see Proposition 2), this easily implies that every algebraic number lies in the counting hierarchy. However, Jeřábek’s techniques yield threshold circuits whose depth depends on the degree of the polynomial p, and consequently his approach does not provide any constant k such that every algebraic real would lie3

A referee points out that the argument of [39] requires depth related to the degree d primarily because it is finding all of the roots of a polynomial p. The referee asserts that the algorithm in [39] can be modified, by hardwiring information related to a specific root of p, to show that every algebraic number lies in ${PH}^{{CH}_{4}}$ , not quite matching the bound that we present.

{CH}_{k}

; we show that this does hold, for

k = 5

. (We actually prove a better upper bound:

{PH}^{{CH}_{3}}

, which (by Toda’s theorem [67]) is contained in

P^{{CH}_{4}} \subseteq {CH}_{5}

.) It is fair to ask how tight this upper bound is. Thus we also consider lower bounds, although the lower bounds we present are quite weak. For every prime modulus m, we show that there are algebraic numbers (in fact, rational numbers) that lie outside of

{AC}^{0} [m]

). For rational numbers, this lower bound is rather tight; the language corresponding to any rational number lies in

{ACC}^{0}

(and hence lies in

{AC}^{0} [m]

for some

m \in N

). Although it seems reasonable to conjecture that irrational algebraic numbers are even more difficult than rational ones, we currently do not know of any irrational algebraic number that lies outside of

{AC}^{0}

; nor do we know of any irrational algebraic number that lies in

{AC}^{0}

. Our upper bound of

{PH}^{{CH}_{3}}

is the best upper bound that we know of, for any irrational algebraic number.

Our techniques also apply to certain transcendental numbers, such as π. Yap [73] showed that there is a logspace-computable function that, on input $1^{n}$ , will output the first n bits of π. (This theorem is also discussed by Lipton in [47, Chapter 31].) Thus the language corresponding to π lies in $PSPACE$ . We improve this, to show that $π \in {PH}^{{CH}_{3}}$ (and we show that the first n bits of π can be computed in uniform ${TC}^{0}$ ). We also answer a question posed by Yap, by showing that, for any base b, the first n digits of π expressed in base b can be produced in ${TC}^{0}$ , and hence in logspace.

The main technical contribution of our work consists of improved algorithms for integer division and related problems. The chain that connects integer division and the complexity of algebraic numbers consists of the following links:

Our ${PH}^{{CH}_{3}}$ upper bound on algebraic numbers relies on an improved upper bound on the problem of computing a given bit of a number represented by an arithmetic circuit (or straight-line program). This problem, known as $BitSLP$ was introduced in [8], where it was shown to be hard for $#P$ [8], and was also shown to lie in the counting hierarchy.4

⁴

This connection between numerical computation and arithmetic circuits has also been exploited in other work, such as [23,46,54,55].

The best previously-known upper bound for the complexity of

BitSLP

is the bound mentioned in [8] and credited there to [10]:

{PH}^{{CH}_{4}}

That bound of ${PH}^{{CH}_{4}}$ follows via a straightforward translation of a uniform ${TC}^{0}$ algorithm for division and for conversion to and from Chinese Remainder Representation, which was presented in [37]. The algorithms presented in [37] also play a central role in the ${TC}^{0}$ root-finding algorithm of [39]. We give improved uniform ${TC}^{0}$ algorithms for these problems, which in turn yield a ${PH}^{{CH}_{3}}$ upper bound on $BitSLP$ , and on algebraic reals.

The rest of the paper is organized as follows. In Section 2 we present the necessary background and definitions for our theorems that deal with (arithmetic and Boolean) circuits. In Section 3 we give improved algorithms for a variety of problems, including integer division, iterated product, and matrix powering, and we show how these algorithms yield improved upper bounds in the Counting Hierarchy for some fundamental problems about arithmetic circuits. In Section 4 we review background material about algebraic numbers and root-finding algorithms. Then in Section 4.2 we present our upper bound on the complexity of languages A whose characteristic sequence $χ_{A}$ is an algebraic number, and we also present related results about certain transcendental numbers (including π). We conclude with a discussion of open problems in Section 5.

2. Arithmetic and Boolean circuits

The algorithms that we present depend on Chinese Remainder Representation (CRR). Let us fix the notation that we will use. Given a list of primes $Π = (p_{1}, \dots, p_{m})$ and a number $X \in N$ , the ${CRR}_{Π}$ representation of X is the list $(X mod p_{1}, \dots, X mod p_{m})$ . We omit the subscript Π when it is clear from context.

We need to refer (repeatedly) to the binary expansion of a rational number. Furthermore, we want to avoid possible confusion caused by the fact that some numbers have more than one binary expansion (e.g. $1 = \sum_{i = 1}^{\infty} 2^{- i}$ ). Thus the following definition fixes a unique binary representation for every rational number.

Definition 1.
The binary expansion of a nonnegative rational number $X / Y$ is the unique expression $X / Y = \sum_{i = - \infty}^{\infty} a_{i} 2^{i}$ , where each $a_{i} \in {0, 1}$ , and where the binary expansion of any integer multiple of $2^{j}$ has $a_{i} = 0$ for all $i < j$ .

The binary expansion of $X / Y$ correct to m places is the sequence of bits representing $\sum_{i = - m}^{⌊ log (X / Y) ⌋} a_{i} 2^{i}$ .

A circuit is a directed acyclic graph, whose nodes are called gates and whose edges are called wires. Gates with indegree zero are input gates. We usually restrict attention to circuits with exactly one gate of outdegree zero; this gate is called the output gate. In this paper, all input gates will be connected either to constants or to input variables, which can be assigned values in ${0, 1}$ .

In an arithmetic circuit, all gates other than input gates are labeled with an operation in ${+, \times}$ , and the constants that we will allow are ${0, 1, - 1}$ . Thus each wire leading from gate g to gate h will “carry” the integer value that is computed at g to be fed into gate h.

Arithmetic circuits of polynomial size can produce numbers that require exponentially-many bits to represent in binary. The problem5
⁵
“SLP” stands for “straight-line program”; which is a model equivalent to arithmetic circuits. Throughout the rest of the paper, we will stick with the arithmetic circuit formalism.

known as $BitSLP$ is the problem of determining a given bit of this binary representation. Formally, $BitSLP$ is $\begin{array}{l} BitSLP = {(C, i, b) : the i -th bit of the number represented by arithmetic circuit C is b} . \end{array}$ A related problem, $\begin{array}{l} PosSLP = {C : the number represented by arithmetic circuit C is > 0}) \end{array}$ and a host of other problems on inferring properties of succinctly represented numbers were introduced in an article by Allender, Bürgisser, Kjeldgaard-Pedersen and Miltersen [8]. The main goal of [8] was to provide a complexity-theoretic framework to study problems arising in numerical analysis. It is shown in [8] that $BitSLP$ is hard for $#P$ , and it also conjectured there that $PosSLP \notin P / poly$ .

It is important to note that the arithmetic circuits considered in $PosSLP$ and $BitSLP$ do not have any input variables. Let us emphasize this point: In this paper, we focus on arithmetic circuits without input variables. Thus an arithmetic circuit is a (possibly very compact) representation of an integer.

The Boolean circuits that we will consider will have gates (other than input gates) labeled with an operation in {NOT, AND, OR, MAJORITY}. These gates (which have unbounded fan-in, except for NOT gates, which have fan-in 1) produce as output the logical NOT, AND, OR, and MAJORITY of their inputs, respectively (where MAJORITY $(x_{1}, \dots, x_{n})$ evaluates to 1 iff strictly more than $n / 2$ of the input bits are 1).

The depth of a circuit is the length of the longest path from an input gate to the output gate. A circuit family is a set ${C_{n} : n \in N}$ where each $C_{n}$ has n input gates. A circuit family is dlogtime-uniform if there is a Turing machine takes an input string $(n, g, h)$ of length m and determines in time $O (m)$ the labels of g and h in $C_{n}$ and also reports if there is a wire in $C_{n}$ from g to h. A circuit family is said to be nonuniform if no uniformity condition is imposed. ${TC}^{0}$ is the set of languages that are recognized by dlogtime-uniform circuit families of polynomial size and depth $O (1)$ . ${AC}^{0}$ is the set of languages that are recognized by such circuit families that have no MAJORITY gates.

We also need to refer to functions computable in circuit classes. The function f is said to be in $C$ (such as $C = {AC}^{0}$ or ${TC}^{0}$ ) if the length of $f (x)$ is polynomial in the length of x, and the language { $(x, i, b)$ : the $i^{th}$ bit of $f (x)$ is b} is in $C$ .

For more on circuit complexity classes such as ${AC}^{0}$ and ${TC}^{0}$ , as well as a discussion of dlogtime uniformity, see [69]. For background on other standard complexity classes such as $PP, #P, NP, P$ etc., consult a standard text such as [12].

There are several possible variants of “depth” that one could choose to study. For instance, several papers have studied circuits consisting only of MAJORITY gates, and tight bounds are known for the depth required for several problems, in that model. (See, for instance [34,61,63,70] and other work referenced there.) Since our motivation comes largely from the desire to understand the complexity of problems in the counting hierarchy, it turns out that it is much more relevant to consider the notion of majority depth that was considered by Maciel and Thérien [48]. The class ${\hat{TC}}_{d}^{0}$ consists of functions computable by families of threshold circuits of polynomial size and constant depth such that no path from an input to an output gate encounters more than d MAJORITY gates. Thus the class of functions with majority depth zero, ${\hat{TC}}_{0}^{0}$ , is precisely ${AC}^{0}$ . In order to explain the connection between ${\hat{TC}}_{d}^{0}$ and the counting hierarchy, recall how the levels of the counting hierarchy are defined: $\begin{matrix} {CH}_{1} = PP, and {CH}_{k + 1} = {PP}^{{CH}_{k}} . \end{matrix}$ The counting hierarchy is analogous in some ways to the polynomial hierarchy $PH = NP \cup {NP}^{NP} \cup \dots .$ The following proposition can be interpreted as saying that ${PH}^{{CH}_{d}}$ is an exponential analog of ${\hat{TC}}_{d}^{0}$ .
Proposition 2 (Implicit in [8, Theorem 4.1].).

Let A be a set such that, for some k, some polynomial-time computable function f and for some dlogtime-uniform ${\hat{TC}}_{d}^{0}$ circuit family $C_{n}$ , it holds that $x \in A$ if and only if $C_{| x | + 2^{| x |^{k}}} (x, f (x, 1) f (x, 2) \dots f (x, 2^{| x |^{k}}))$ accepts. Then $A \in {PH}^{{CH}_{d}}$ .

(One important part of the proof of Proposition 2 is the fact that, by Toda’s theorem [67], for every oracle A, ${PP}^{{PH}^{A}} \subseteq P^{{PP}^{A}}$ . Thus all of the ${AC}^{0}$ circuitry inside the ${\hat{TC}}_{d}^{0}$ circuit can be swallowed up by the $PH$ part of the simulation.)

Note that the dlogtime-uniformity condition is crucial for Proposition 2. Thus, for the remainder of this paper, all references to ${\hat{TC}}_{d}^{0}$ will refer to the dlogtime-uniform version of this class, unless we specifically refer to nonuniform circuits.

3. Overview of the new algorithmic results

In this section, we present new uniform ${TC}^{0}$ algorithms for integer division, converting from CRR to binary, computing a power of a given integer, and computing a power of a given matrix (of bounded dimension). Table 1 compares the complexity bounds that Maciel and Thérien obtained in the nonuniform setting with the bounds that we are able to obtain in the uniform setting. (Maciel and Thérien also considered several problems for which they gave uniform circuit bounds; the problems listed in Table 1 were not known to lie in dlogtime-uniform ${TC}^{0}$ until the subsequent work of [37].) All previously-known dlogtime-uniform ${TC}^{0}$ algorithms for these problems rely on the CRR-to-binary algorithm of [37], and thus have at least majority-depth 4 (as analyzed by [10]); no other depth analysis beyond $O (1)$ was attempted.

Table 1
Prior bounds and new bounds on majority-depth for various problems

Problem Nonuniform Majority–Depth [48] Uniform Majority–Depth [This Paper]

Iterated multiplication 3 3

Division 2 3

Powering 2 3

CRR-to-binary 1 3

Matrix powering O(1) [37,49] 3

Problem	Nonuniform Majority–Depth [48]	Uniform Majority–Depth [This Paper]
Iterated multiplication	3	3
Division	2	3
Powering	2	3
CRR-to-binary	1	3
Matrix powering	O(1) [37,49]	3

In all of the cases where our uniform majority-depth bounds are worse than the nonuniform bounds given by [48], our algorithms also give rise to nonuniform algorithms that match the bounds of [48] (by hardwiring in some information that depends only on the length), although in all cases the algorithms differ in several respects from those of [48].

The most efficient previously-known ${TC}^{0}$ algorithms for the problems considered in this paper all make use of clever decompositions of the problem at hand, in terms of partial evaluations or approximations. The technical innovations in our improved algorithms rely on introducing yet another approximation, as discussed in Lemmas 7 and 10.

Table 1 also lists one problem that was not considered by Maciel and Thérien: the problem of taking as input $1^{m}$ and a $k \times k$ matrix A, and producing $A^{m}$ . For any fixed k, this problem was shown to be in nonuniform ${TC}^{0}$ by Mereghetti and Palano6

⁶

The reader should be cautioned that it is stated in [49] that iterated matrix product of $k \times k$ integer matrices is computable in ${NC}^{1}$ . In fact, the best known upper bound is ${GapNC}^{1}$ [21].

[49]; it follows from [37] that their algorithm can be implemented in dlogtime-uniform

{TC}^{0}

. The corresponding problem of computing large powers of a

k \times k

matrix (i.e., when m is given in binary) has been discussed recently [33,54]. We show that this version of matrix powering is in

{PH}^{{CH}_{3}}

, by making use of the improved algorithm for CRR-to-binary, which plays an important role in our

{PH}^{{CH}_{3}}

algorithm for

BitSLP

In addition to $BitSLP$ , there has also been interest in the related problem $PosSLP$ [29,41,44,45]. $PosSLP \in {PH}^{{CH}_{2}}$ , and is not known to be in $PH$ [8], but in contrast to $BitSLP$ , it is not known (or believed [29]) to be $NP$ -hard. Our theorems do not imply any new bounds on the complexity of $PosSLP$ , but we do conjecture that $BitSLP$ and $PosSLP$ both lie in ${PH}^{PP}$ . This conjecture is based mainly on the heuristic that says that, for problems of interest, if a nonuniform circuit is known, then corresponding dlogtime-uniform circuits usually also exist. Converting from CRR to binary can be done nonuniformly in majority-depth one, and there is no reason to believe that this is not possible uniformly – although it seems clear that a different approach will be needed, to reach this goal.

The well-studied Sum-of-Square-Roots problem reduces to $PosSLP$ [8], which in turn reduces to $BitSLP$ . But the relationship between $PosSLP$ and the matrix powering problem (given a matrix A and an n-bit integers $(k, j)$ , output the $k^{th}$ bit of a given entry of $A^{j}$ ) is unclear, since matrix powering corresponds to evaluating very restricted arithmetic circuits. Note that some types of arithmetic involving large numbers can be done in $P$ ; see [33,38]. Might matrix powering also lie in $PH$ ?

In Section 3.6, we provide a very weak “hardness” result for the problem of computing the bits of large powers of 2-by-2 matrices, to shed some dim light on this question. We show that the Sum-of-Square-Roots problem reduces to matrix powering via ${PH}^{PP}$ -Turing reductions.

3.1. Improved uniform circuits for division

Our new algorithm for division makes use of several useful subroutines that are computable in ${AC}^{0}$ and ${\hat{TC}}_{1}^{0}$ . These are summarized in the following lemma:

Lemma 3.
Let $x, y, i, j, k, x_{j}$ be numbers in the interval $(0, n^{c})$ (where $c ⩾ 3$ is a constant). Let $X, X_{j} \in [0, 2^{n})$ and let $p < n^{c}$ be prime. Then the following operations have the indicated complexities:
$p \mapsto first n^{c} bits of 1 / p$ is in ${\hat{TC}}_{0}^{0} = {AC}^{0}$ .

$p, k, X_{1} \dots, X_{k} \mapsto \sum_{j = 1}^{k} X_{j} mod p$ is in ${\hat{TC}}_{1}^{0}$ .

$x \mapsto x^{i} mod p$ is in ${\hat{TC}}_{0}^{0} = {AC}^{0}$ .

$p \mapsto g_{p}$ is in ${\hat{TC}}_{0}^{0} = {AC}^{0}$ where $g_{p}$ is a generator of the multiplicative group modulo p.

$X \mapsto X mod p$ is in ${\hat{TC}}_{1}^{0}$ .

$x, y \mapsto x y mod p$ is in ${\hat{TC}}_{0}^{0} = {AC}^{0}$ .

$(x_{1}, \dots, x_{k}) \mapsto \prod_{j = 1}^{k} x_{j} mod p$ is in ${\hat{TC}}_{1}^{0}$ .

Proof.
We list the proofs of items in the Lemma above:
Follows from Lemma 4.2 and Corollary 6.2 in [37]. In Section 4.3, we will also need the fact that the base-β representation of $1 / p$ is also computable in ${AC}^{0}$ . (See also Note 12.) Thus we present the details here.

Claim 4.
The language { $(1^{n}, p, σ) : p ⩽ n^{c}$ and the $n^{th}$ symbol in the base-β representation of $1 / p$ is σ} is in ${AC}^{0}$ .

Proof.
Let a and b be such that $β^{n} = a p + b$ with $b = β^{n} mod p$ . The $n^{th}$ digit of the base-β expansion of the rational number $1 / p$ is equal to the low-order digit of a. Since $a p + b$ is congruent to zero modulo β, it follows that the low-order digit of a is equal to $- p^{- 1} b mod β$ , where $p^{- 1}$ is the multiplicative inverse of $p mod β$ . The result now follows from the fact that computing $β^{n} mod p$ is in ${AC}^{0}$ [37], and that $p^{- 1} mod β$ can be computed in ${AC}^{0}$ . □

Follows from Corollary 3.4.2 in [48].

Follows from Corollary 6.2 in [37].

Follows from testing each integer $x \in [1, n - 1]$ for being a generator by checking if $\forall i ⩽ \frac{p - 1}{2} x^{i} ≢ 1 mod p$ and reporting the first successful x (implicit in [8,37]).

Follows from (the proof of) Lemma 4.1 in [37].

Follows from Proposition 3.7 in [48] and the fact that two $log n$ -bit integers can be multiplied in ${AC}^{0}$ .

Follows from the reduction of multiplication to addition of discrete logs and the previous parts.
□

3.2. A new division algorithm

We now give a construction of efficient threshold circuits for division.

Theorem 5.
The function taking as input $X \in [0, 2^{n}), Y \in [1, 2^{n})$ , and $0^{m}$ and producing as output the binary expansion of $X / Y$ correct to m places is in ${\hat{TC}}_{3}^{0}$ .
Proof.
This task is trivial if $Y = 1$ ; thus in the rest of this argument assume that $Y ⩾ 2$ .

Computing the binary expansion of $Z / Y$ correct to m places is equivalent to computing $⌊ 2^{m} Z / Y ⌋$ . Thus we will focus on the task of computing $⌊ X / Y ⌋$ , given integers X and Y.

The basic structure of all known ${TC}^{0}$ algorithms for division (reducing the problem to iterated product, and computing iterated product via a reduction to iterated addition, via conversion to and from Chinese Remainder Representation) has remained unchanged since the pioneering work of [17]. Subsequent improvements [22,37,48,63] have focused on finding more efficient implementations of these various tasks.

Our approach will be to compute $\tilde{V} (X, Y)$ , a strict underestimate of $X / Y$ , such that $X / Y - \tilde{V} (X, Y) < 1 / Y$ . Since $Y > 1$ , we have that $⌊ X / Y ⌋ \neq ⌊ (X + 1) / Y ⌋$ if and only if $(X + 1) / Y = ⌊ X / Y ⌋ + 1$ . It follows that in all cases $⌊ X / Y ⌋ = ⌊ \tilde{V} (X + 1, Y) ⌋$ , since $\begin{array}{l} ⌊ \frac{X}{Y} ⌋ ⩽ \frac{X}{Y} = \frac{X + 1}{Y} - \frac{1}{Y} < \tilde{V} (X + 1, Y) < \frac{X + 1}{Y} . \end{array}$ Note that, in order to compute $⌊ \frac{X}{Y} ⌋$ , we actually compute an approximation to $(X + 1) / Y$ .

The approximation $\tilde{V} (X, Y)$ is actually defined in terms of another rational approximation $W (X, Y)$ , which will have the property that $\tilde{V} (X, Y) ⩽ W (X, Y) < X / Y$ . ( $W (X, Y)$ is easier to compute, which is why we introduce it.) We postpone the definition of $\tilde{V} (X, Y)$ , and focus for now on $W (X, Y)$ , an under approximation of $\frac{X}{Y}$ with error at most $2^{- (n + 1)}$ .

Using ${AC}^{0}$ circuitry, we can compute a value $t ⩾ 2$ such that7
⁷
In Section 4.3, we will need to consider a variant algorithm, where, in this first step, a value t is computed such that $β^{t - 1} ⩽ Y < β^{t}$ . Observe that this is easy to do, if Y is expressed in base-β notation. Also, in this case, if we set $u = 1 - β^{- t} Y$ . Then $u \in (0, \frac{β - 1}{β}]$ , and $Y^{- 1} = β^{- t} {(1 - u)}^{- 1}$ . This will also involve changing the definition of W and $W_{j}$ , so that $W_{j} (X, Y)$ is $X {(β^{t} - Y)}^{j} (β^{(2 n + 1 - j) t})$ , and hence $W (X, Y) = \frac{1}{β^{2 (n + 1) t}} \sum_{j = 0}^{2 n + 1} W_{j} (X, Y)$ . We will refer to this variant of the algorithm as the β-variant. The analysis of the β-variant differs from that of the binary version in only trivial respects.

$2^{t - 1} ⩽ Y < 2^{t}$ .

Let $u = 1 - 2^{- t} Y$ . Then $u \in (0, \frac{1}{2}]$ . Thus, $Y^{- 1} = 2^{- t} {(1 - u)}^{- 1} = 2^{- t} (1 + u + u^{2} + \dots)$ . Set $Y^{'} = 2^{- t} (1 + u + u^{2} + \dots + u^{2 n + 1})$ , then $\begin{array}{l} 0 < Y^{- 1} - Y^{'} ⩽ 2^{- t} \sum_{j > 2 n + 1} 2^{- j} < 2^{- (2 n + 1)} \end{array}$ Define $W (X, Y)$ to be $X Y^{'}$ . Hence, $0 < \frac{X}{Y} - W (X, Y) < 2^{- (n + 1)}$ .

We find it useful to use this equivalent expression for $W (X, Y)$ : $\begin{array}{l} W (X, Y) = \frac{X}{2^{t}} \sum_{j = 0}^{2 n + 1} {(1 - \frac{Y}{2^{t}})}^{j} = \frac{1}{2^{2 (n + 1) t}} \sum_{j = 0}^{2 n + 1} X {(2^{t} - Y)}^{j} 2^{(2 n + 1 - j) t} . \end{array}$

Define $W_{j} (X, Y)$ to be $X {(2^{t} - Y)}^{j} (2^{(2 n + 1 - j) t})$ . Thus $W (X, Y) = \frac{1}{2^{2 (n + 1) t}} \sum_{j = 0}^{2 n + 1} W_{j} (X, Y)$ . Lemma 6.
Let Π be any set of primes such that the product M of these primes lies in $(2^{n^{c}}, 2^{n^{d}})$ for some $d > c ⩾ 3$ . Then, given $X, Y, Π$ we can compute the ${CRR}_{Π}$ representations of the $2 (n + 1)$ numbers $W_{j} (X, Y)$ (for $j \in {0, \dots, 2 n + 1}$ ) in ${\hat{TC}}_{1}^{0}$ .
Proof.
With the aid of Lemma 3, we see that using ${AC}^{0}$ circuitry, we can compute
$2^{t} - Y$

$2^{j} mod p$ for each prime $p \in Π$ and various powers j, and

a generator mod p for each prime $p \in Π$ .
In ${\hat{TC}}_{1}^{0}$ we can compute $X mod p$ and $(2^{t} - Y) mod p$ (each of which has $O (log n)$ bits). Using those results, with ${AC}^{0}$ circuitry we can compute the powers ${(2^{t} - Y)}^{j} mod p$ and then do additional arithmetic on numbers of $O (log n)$ bits to obtain the product $X {(2^{t} - Y)}^{j} (2^{(2 n + 1 - j) t}) mod p$ for each $p \in Π$ . (The condition that $c ⩾ 3$ ensures that the numbers that we are representing are all less than M.) □

Having the ${CRR}_{Π}$ representation of the number $W_{j} (X, Y)$ , our goal might be to convert the $W_{j} (X, Y)$ to binary, and take their sum. In order to do this efficiently, we instead first show how to obtain an approximation (in binary) to $W (X, Y) / M$ where $M = \prod_{p \in Π} p$ , and then in Lemma 10 we build on this to compute our approximation $\tilde{V} (X, Y)$ to $W (X, Y)$ .

Recall that $W (X, Y) = \frac{1}{2^{2 (n + 1) t}} \sum_{j = 0}^{2 n + 1} W_{j} (X, Y)$ . Thus the number $2^{2 (n + 1) t} W (X, Y)$ is an integer with the same significant bits as $W (X, Y)$ . Lemma 7.
Let Π be any set of primes such that the product M of these primes lies in $(2^{n^{c}}, 2^{n^{d}})$ for a fixed constant $d > c ⩾ 3$ , and let b be any natural number. Then, given $X, Y, Π$ we can compute the binary representation of a good approximation to $\frac{2^{2 (n + 1) t} W (X, Y)}{M}$ in ${\hat{TC}}_{2}^{0}$ (where by good we mean that it under-estimates the correct value by at most an additive term of $1 / 2^{n^{b}}$ ).
Proof.
Let $h_{p}^{Π} = {(M / p)}^{- 1} mod p$ for each prime $p \in Π$ .

If we were to first compute a good approximation ${\tilde{A}}_{Π}$ to the fractional part of: $\begin{array}{l} A_{Π} = \sum_{p \in Π} \frac{(2^{2 (n + 1) t} W (X, Y) mod p) h_{p}^{Π}}{p} \end{array}$ i.e. if ${\tilde{A}}_{Π}$ were a good approximation to $A_{Π} - ⌊ A_{Π} ⌋$ , then $\tilde{A_{Π}} M$ would be a good approximation to $2^{2 (n + 1) t} W (X, Y)$ . This follows from observing that the fractional part of $A_{Π}$ is exactly $\frac{2^{2 (n + 1) t} W (X, Y)}{M}$ (as in [37, Lemma 4.3] and [8, Theorem 4.2]).

Instead of working with $A_{Π}$ , we will work with $\begin{array}{l} A_{Π}^{'} = \sum_{p \in Π} \sum_{j = 0}^{2 n + 1} \frac{(W_{j} (X, Y) mod p) h_{p}^{Π}}{p} . \end{array}$ Note that the exact magnitudes of the two quantities $A_{Π}, A_{Π}^{'}$ are not the same but their fractional parts will be the same. Thus we will compute ${\tilde{A}}_{Π}$ as a good approximation to the fractional part of $A_{Π}^{'}$ . Since we are adding up $2 (n + 1) | Π |$ approximate quantities it suffices to compute each of them to $b_{n, b, Π} = 2 n^{b} + 2 (n + 1) | Π |$ bits of accuracy to ensure: $\begin{array}{l} 0 ⩽ \frac{2^{2 (n + 1) t} W (X, Y)}{M} - {\tilde{A}}_{Π} < \frac{1}{2^{n^{b}}} . \end{array}$

Now we analyze the complexity. By Lemma 6, we obtain in ${\hat{TC}}_{1}^{0}$ the ${CRR}_{Π}$ representation of $W_{j} (X, Y) \in [0, 2^{n})$ for $j \in {0, \dots, O (n)}$ . Also, by Lemma 3, each $h_{p}^{Π}$ can be computed in ${\hat{TC}}_{1}^{0}$ , and polynomially-many bits of the binary expansion of $1 / p$ can be obtained in ${AC}^{0}$ .

Using ${AC}^{0}$ circuitry we can multiply together the $O (log n)$ -bit numbers $W_{j} (X, Y) mod p$ and $h_{p}^{Π}$ , and then obtain the binary expansion of $((W_{j} (X, Y) mod p) h_{p}^{Π}) \cdot (1 / p)$ (since multiplying an n-bit number by a $log n$ bit number can be done in ${AC}^{0}$ ).

Thus, with one more layer of majority gates, we can compute a good approximation to $\begin{array}{l} A_{Π}^{'} = \sum_{p \in Π} \sum_{j = 0}^{2 n + 1} \frac{(W_{j} (X, Y) mod p) h_{p}^{Π}}{p} \end{array}$ and strip off the integer part, to obtain the desired approximation ${\tilde{A}}_{Π}$ . □
Corollary 8.
Let Π be any set of primes such that the product M of these primes lies in $(2^{n^{c}}, 2^{n^{d}})$ for a fixed constant $d > c ⩾ 3$ . Then, given Z in ${CRR}_{Π}$ representation and the numbers $h_{p}^{Π}$ for each $p \in Π$ , we can compute the binary representation of a good approximation to $\frac{Z}{M}$ in ${\hat{TC}}_{1}^{0}$ .
Proof.
This follows from the analysis presented in the proof of Lemma 7, in the special case when $W_{1} = Z$ and $W_{j} = 0$ for all $j > 1$ . □

Before presenting our approximation $\tilde{V} (X, Y)$ , first we present a claim, which helps motivate the definition. In the claim, and in the subsequent discussion, let $Π_{i}$ for $i \in {1, \dots, n^{ℓ}}$ be $n^{ℓ}$ pairwise disjoint sets of primes such that $M_{i} = \prod_{p \in Π_{i}} p \in (2^{n^{c}}, 2^{n^{d}})$ (for some constants $c, d : 3 ⩽ ℓ ⩽ c < d$ ). Let $Π = ⋃_{i = 1}^{n^{ℓ}} Π_{i}$ . Claim 9.
For any value A, it holds that $\begin{array}{l} A (1 - \frac{n^{ℓ}}{2^{n^{ℓ}}}) < \frac{A \prod_{i = 1}^{n^{ℓ}} (M_{i} - 1)}{\prod_{i = 1}^{n^{ℓ}} M_{i}} < A . \end{array}$
Proof.
It suffices to show that $\begin{array}{l} (1 - \frac{n^{ℓ}}{2^{n^{ℓ}}}) < \frac{\prod_{i = 1}^{n^{ℓ}} (M_{i} - 1)}{\prod_{i = 1}^{n^{ℓ}} M_{i}} < 1 \end{array}$ where the final inequality is trivial. Let $m = n^{ℓ}$ and let $x = 2^{n^{ℓ}}$ . Then $(1 - \frac{n^{ℓ}}{2^{n^{ℓ}}}) = 1 - \frac{m}{x}$ and ${(1 - \frac{1}{x})}^{m} ⩽ \frac{\prod_{i = 1}^{n^{ℓ}} (M_{i} - 1)}{\prod_{i = 1}^{n^{ℓ}} M_{i}}$ . Thus the claim holds if we show that, for all $x > 1$ and for all integers $m > 1$ , $\begin{array}{l} 1 - \frac{m}{x} < {(1 - \frac{1}{x})}^{m} . \end{array}$ This holds by induction. Assume that $1 - m / x ⩽ {(1 - 1 / x)}^{m}$ . (This holds for $m = 1$ .) Then $1 - (m + 1) / x = 1 - m / x + m / x - (m + 1) / x < {(1 - 1 / x)}^{m} - 1 / x < {(1 - 1 / x)}^{m} - {(1 - 1 / x)}^{m} 1 / x = {(1 - 1 / x)}^{m} (1 - 1 / x)$ . This completes the induction, and the proof of the claim. □

Now, finally, we present our desired approximation. $\tilde{V} (X, Y)$ is $2^{n^{ℓ}} \cdot V^{'} (X, Y)$ , where $V^{'} (X, Y)$ is an approximation (within $1 / 2^{n^{2 ℓ}}$ ) of $\begin{array}{l} V (X, Y) = \frac{W (X, Y) \prod_{i = 1}^{n^{ℓ}} (M_{i} - 1) / 2}{\prod_{i = 1}^{n^{ℓ}} M_{i}} . \end{array}$

Note that $\begin{array}{l} W (X, Y) - 2^{n^{ℓ}} V (X, Y) & = W (X, Y) - 2^{n^{ℓ}} \frac{W (X, Y) \prod_{i = 1}^{n^{ℓ}} (M_{i} - 1) / 2}{\prod_{i = 1}^{n^{ℓ}} M_{i}} \\ = W (X, Y) - \frac{W (X, Y) \prod_{i = 1}^{n^{ℓ}} (M_{i} - 1)}{\prod_{i = 1}^{n^{ℓ}} M_{i}} \\ < W (X, Y) \frac{n^{ℓ}}{2^{n^{ℓ}}} < \frac{2^{2 n} n^{ℓ}}{2^{n^{ℓ}}} \end{array}$ and $\begin{array}{l} 2^{n^{ℓ}} V (X, Y) - \tilde{V} (X, Y) & = 2^{n^{ℓ}} V (X, Y) - 2^{n^{ℓ}} V^{'} (X, Y) \\ = 2^{n^{ℓ}} (V (X, Y) - V^{'} (X, Y)) \\ ⩽ 2^{n^{ℓ}} (\frac{1}{2^{n^{2 ℓ}}}) \\ = \frac{2^{n^{ℓ}}}{2^{n^{2 ℓ}}} . \end{array}$

Thus $X / Y - \tilde{V} (X, Y)$ is equal to $\begin{array}{l} (X / Y - W (X, Y)) + (W (X, Y) - 2^{n^{ℓ}} V (X, Y)) + (2^{n^{ℓ}} V (X, Y) - \tilde{V} (X, Y)) \end{array}$ and hence $\begin{array}{l} X / Y - \tilde{V} (X, Y) & < 2^{- (n + 1)} + \frac{n^{ℓ} 2^{2 n}}{2^{n^{ℓ}}} + \frac{2^{n^{ℓ}}}{2^{n^{2 ℓ}}} \\ < 1 / Y, \end{array}$ for all $n ⩾ 2$ . Lemma 10.
Let $Π_{i}$ for $i \in {1, \dots, n^{ℓ}}$ be $n^{ℓ}$ pairwise disjoint sets of odd primes such that $M_{i} = \prod_{p \in Π_{i}} p \in (2^{n^{c}}, 2^{n^{d}})$ (for some constants $c, d : 3 ⩽ c < d$ ). Let $Π = ⋃_{i = 1}^{n^{ℓ}} Π_{i}$ . Then, given $X, Y$ and the $Π_{i}$ , we can compute $\tilde{V} (X, Y)$ in ${\hat{TC}}_{3}^{0}$ .
Proof.
Via Lemma 3, in ${\hat{TC}}_{1}^{0}$ we can compute the ${CRR}_{Π}$ representation of each $M_{i}$ , as well as the numbers $W_{j} mod p$ (using Lemma 6). Also, as in Lemma 7, we can compute the values $h_{p}^{Π}$ for each prime p.

Then, via Lemma 3, with one more layer of majority gates we can compute the CRR representation of $\prod_{i} (M_{i} - 1) / 2$ , as well as the CRR representation of $2^{2 (n + 1) t} W (X, Y) = \sum_{j = 0}^{2 n + 1} W_{j} (X, Y)$ . The CRR representation of the product $2^{2 (n + 1) t} W (X, Y) \cdot \prod_{i} (M_{i} - 1) / 2$ can then be computed with ${AC}^{0}$ circuitry to obtain the CRR representation of the numerator of the expression for $V (X, Y)$ . (It is important to note that $2^{2 (n + 1) t} W (X, Y) \cdot \prod_{i} (M_{i} - 1) / 2 < \prod_{i} M_{i}$ , so that it is appropriate to talk about this CRR representation. Indeed, that is the reason why we divide each factor $M_{i} - 1$ by two.)

This value can then be converted to binary with one additional layer of majority gates, via Corollary 8, to obtain $\tilde{V} (X, Y)$ . □

This completes the proof of Theorem 5. □
Corollary 11.
Let Π be any set of primes that is the union of pairwise disjoint sets $Π_{i}$ , such that, for all i, $M_{i} = \prod_{p \in Π_{i}} p$ lies in $(2^{n^{c}}, 2^{n^{d}})$ for fixed constants $d > c ⩾ 3$ . Then, given Z in ${CRR}_{Π}$ representation, the binary representation of Z can be computed in ${\hat{TC}}_{3}^{0}$ .
Proof.
Recall from the proof of Theorem 5 that, in order to compute the bits of $Z / 2$ , our circuit actually computes an approximation to $(Z + 1) / 2$ . Although, of course, it is trivial to compute $Z / 2$ if Z is given to us in binary, let us consider how to modify the circuit described in the proof of Lemma 10, if we were computing $\tilde{V} (Z + 1, 2)$ , where we are given Z in CRR representation.

With one layer of majority gates, we can compute the ${CRR}_{Π}$ representation of each $M_{i}$ and the values $h_{p}^{Π}$ for each prime p. (We will not need the numbers $W_{j} mod p$ .)

Then, with one more layer of majority gates we can compute the CRR representation of $\prod_{i} (M_{i} - 1) / 2$ . In place of the gates that store the value of the CRR representation of $2^{2 (n + 1) t} W (X, Y)$ , we insert the CRR representation of Z (which is given to us as input) and using ${AC}^{0}$ circuitry store the value of $Z + 1$ . The CRR representation of the product $(Z + 1) \cdot \prod_{i} (M_{i} - 1) / 2$ can then be computed with ${AC}^{0}$ circuitry to obtain the CRR representation of the numerator of the expression for $V (Z + 1, 2)$ .

Then this value can be converted to binary with one additional layer of majority gates, from which the bits of Z can be read off. □
Note 12.
Although we have stated our results in terms of converting from CRR to binary notation, there is nothing special about base 2. As observed in [6,37], the approach from Lemma 10 (and in Lemma 7) carries over with only trivial adjustments, to convert from CRR to base ten or to representation in any other base. The only “new” ingredient that is required is that the base-β expansion of $1 / p$ can be computed to a polynomial number of bits of accuracy in ${AC}^{0}$ . (See Claim 4.8
⁸
It should be mentioned that the β-variant of the division algorithm is not required, for conversion from CRR to base-β. The β-variant is introduced for other considerations that arise in Section 4.3.

)

It is rather frustrating to observe that the input values Z are not used until quite late in the ${\hat{TC}}_{3}^{0}$ computation (when just one layer of majority gates remains). However, we see no simpler uniform algorithm to convert CRR to binary.

For our application regarding problems in the counting hierarchy, it is useful to consider the analog to Theorem 5 where the values X and Y are presented in CRR notation.
Theorem 13.
The function taking as input $X \in [0, 2^{n}), Y \in [1, 2^{n})$ (in CRR) as well as $0^{m}$ , and producing as output the binary expansion of $X / Y$ correct to m places is in ${\hat{TC}}_{3}^{0}$ .
Proof.
We assume that the CRR basis consists of pairwise disjoint sets of primes $M_{i}$ , as in Lemma 10.

The algorithm is much the same as in Theorem 5, but there are some important differences that require comment. The first step is to determine if $Y = 1$ , which can be done using ${AC}^{0}$ circuitry (since the CRR of 1 is easy to recognize). The next step is to determine a value t such that $2^{t - 1} ⩽ Y < 2^{t}$ . Although this is trivial when the input is presented in binary, when the input is given in CRR it requires the following lemma: Lemma 14 (Adapted from [4,8,26]).

Let X be an integer from $(- 2^{n}, 2^{n})$ specified by its residues modulo each $p \in Π_{n}$ . Then, the predicate $X > 0$ is in ${\hat{TC}}_{2}^{0}$

Since we are able to determine inequalities in majority-depth two, we will carry out the initial part of the algorithm from Theorem 5 using all possible values of t, and then select the correct value between the second and third levels of MAJORITY gates.

Thus, for each t, and for each j, we compute the values $W_{j, t} (X + 1, Y) = (X + 1) {(2^{t} - Y)}^{j} (2^{(2 n + 1 - j) t})$ in CRR, along with the desired number of bits of accuracy of $1 / p$ for each p in our CRR basis.

With this information available, as in Lemma 10, in majority-depth one we can compute $h_{p}^{Π}$ , as well as the CRR representation of each $M_{i}$ , and thus with ${AC}^{0}$ circuitry we obtain $(W_{j, t} (X + 1, Y)$ and the CRR for each $(M_{i} - 1) / 2$ .

Next, with our second layer of majority gates we sum the values $W_{j, t} (X + 1, Y)$ (over all j), and at this point we also will have been able to determine which is the correct value of t, so that we can take the correct sum, to obtain $2^{2 (n + 1) t} W (X + 1, Y)$ .

Thus, after majority-depth two, we have obtained the same partial results as in the proof of Lemma 10, and the rest of the algorithm is thus identical. □

The following generalization of Theorem 13 will be useful for us in Section 4.3.

Theorem 15.
There is a function computable in ${\hat{TC}}_{3}^{0}$ that takes as input the CRR representation of a sequence $X_{1}, Y_{1}, X_{2}, Y_{2}, \dots, X_{r}, Y_{r}$ , as well as $0^{m}$ and $1^{t}$ with the property that, for each i, $2^{t - 1} ⩽ Y_{i} < 2^{t}$ , and produces as output the binary expansion of $\sum_{i = 1}^{r} \frac{X_{i}}{Y_{i}}$ correct to m places.
Proof.
The naïve approach, of simply taking the sum of the circuits that result from Theorem 13, would be too expensive in terms of majority-depth. Thus we dive deeper into the details of how each quotient is computed.

Recall the definition of $W_{j} (X, Y)$ (immediately before Lemma 6), and recall also that $\frac{X}{Y}$ is approximated by $W (X + 1, Y) = \frac{1}{2^{2 (n + 1) t}} \sum_{j = 0}^{2 n + 1} W_{j} (X + 1, Y)$ .

Thus $\sum_{i = 1}^{r} \frac{X_{i}}{Y_{i}} \approx \sum_{i = 1}^{r} \frac{1}{2^{2 (n + 1) t}} \sum_{j = 0}^{2 n + 1} W_{j} (X_{i} + 1, Y_{i})$ , where the approximation is a correct underapproximation to $n^{O (1)}$ bits

As in the proof of Theorem 13, after one level of majority gates, we can have computed the values of $W_{j} (X_{i} + 1, Y_{i})$ (in CRR notation), and with another level of majority gates, we can compute the CRR of $\sum_{i = 1}^{r} \frac{1}{2^{2 (n + 1) t}} \sum_{j = 0}^{2 n + 1} W_{j} (X_{i} + 1, Y_{i})$ , and (as in the proof of Theorem 13) with one more level of majority gates, we obtain the binary encoding of the desired result. □
Proposition 16.
Iterated product is in uniform ${\hat{TC}}_{3}^{0}$ .
Proof.
The overall algorithm is identical to the algorithm outlined in [48], although the implementation of the basic building blocks is different. In majority-depth one, we convert the input from binary to CRR. With one more level of majority gates, we compute the CRR of the product.

Simultaneously, in majority-depth two we compute the bottom two levels of our circuit that converts from CRR to binary, as in Corollary 11.

Thus, with one final level of majority gates, we are able to convert the answer from CRR to binary. □

3.3. Consequences for the counting hierarchy

Corollary 17.
$BitSLP \in {PH}^{{CH}_{3}}$ .
Proof.
This is immediate from Proposition 2 and Corollary 11.

Let f be the function that takes as input a tuple $(C, (p, j))$ and if p is a prime, evaluates the arithmetic circuit C mod p and outputs the j-th bit of the result. This function f, taken together with the ${\hat{TC}}_{3}^{0}$ circuit family promised by Corollary 11, satisfies the hypothesis of Proposition 2. (There is a minor subtlety, regarding how to partition the set of primes into the groupings $M_{i}$ , but this is easily handled by merely using all of the primes of a given length, at most polynomially-larger than $| C |$ .) □

Via essentially identical methods, using Theorem 13, we obtain: Corollary 18.
{ $(C_{X}, C_{Y}, N)$ : the Nth bit of the quotient $X / Y$ , where X and Y are represented by arithmetic circuits $C_{X}$ and $C_{Y}$ , respectively} is in ${PH}^{{CH}_{3}}$ .
Proof.
We will appeal to Proposition 2 and Theorem 13. Let f be the polynomial-time-computable function that, on input $(x, y) = ((C_{X}, C_{Y}, N), (b, p))$ outputs “p not prime” if p is not prime, and otherwise outputs the value of $C_{X} mod p$ if $b = 0$ , and outputs the value of $C_{Y} mod p$ if $b = 1$ . Note that the string $(x, f (x, 1) f (x, 2) \dots f (x, 2^{| x |^{k}}))$ can be viewed as providing the CRR representation of the numbers represented by $C_{X}$ and $C_{Y}$ . (Technically, in order to directly appeal to Proposition 2 and Theorem 13, the definition of f will need to be modified slightly, so that $(x, f (x, 1) f (x, 2) \dots f (x, 2^{| x |^{k}}))$ also ends in a sequence of exponentially-many zeros. This is conceptually quite easy – by only considering numbers p whose length, in bits, is polynomially-related to the length of N, and making some minor formatting changes. In order to avoid introducing distracting technicalities, we leave these minor details to the interested reader.)

Now, let A be the language in ${\hat{TC}}_{3}^{0}$ that takes the CRR representation of X and Y as input, along with the number $0^{N}$ , and outputs the $N^{th}$ bit of $X / Y$ , as follows from Theorem 13. The theorem now follows from Proposition 2. □

3.4. Integer powering

In this section, we continue presenting our algorithmic results, concentrating on the problem of computing powers of integer matrices.

We begin by presenting an alternative algorithm for integer powering, which serves to illustrate our approach for matrix powering. (Note that the upper bound of ${\hat{TC}}_{3}^{0}$ already follows from our algorithm for iterated integer multiplication. Here, we are merely presenting an alternative algorithm as a warm-up for matrix powering.)

Theorem 19.
The function taking as input $X \in [0, 2^{n})$ , $1^{m}$ and $1^{i}$ (where $i \in [1, n m]$ ) and producing as output the i-th bit of $X^{m}$ is in ${\hat{TC}}_{3}^{0}$ .
Proof.
Our algorithm is as follows:
Convert X to CRR. Let $X \equiv X_{j} mod p_{j}$ for $j \in [k]$ . This is implementable in ${\hat{TC}}_{1}^{0}$ by item 5 in Lemma 3. In parallel, compute the first two phases of our uniform algorithm to convert CRR to binary (Corollary 11). (Note that these first two stages depend only on the moduli Π, and do not depend on X)

Compute $X^{m}$ by appealing to Fermat’s little theorem. More precisely: Since $X^{p - 1} \equiv 1 mod p$ for any prime p, we can compute $X_{j}^{m_{j}} mod p_{j}$ where $m = q_{j} (p_{j} - 1) + m_{j}$ for $j \in [k]$ . This step is in ${AC}^{0}$ via item 3 in Lemma 3.

At this stage, we have the answer encoded in CRR, and we invoke the final layer of the circuit from Corollary 11, convert the answer to binary.
Putting these three together, we have integer powering in ${\hat{TC}}_{3}^{0}$ . □

3.5. Integer matrix powering

Theorem 20.
The function $MPOW (A, m, p, q, i)$ taking as input a $(d \times d)$ integer matrix $A \in {0, 1}^{d^{2} n}$ , $p, q$ , $1^{i}$ , where $p, q \in [d]$ , $i \in [O (n)]$ and producing as output the i-th bit of the $(p, q)$ -th entry of $A^{m}$ is in ${\hat{TC}}_{3}^{0}$ .

For a $(d \times d)$ matrix A, the characteristic polynomial $χ_{A} (x) : Z \to Z$ is a univariate polynomial of degree at most d. Let $q, r : Z \to Z$ be univariate polynomials of degree at most $(m - d)$ and $(d - 1)$ such that $x^{m} = q (x) χ_{A} (x) + r (x)$ . By the Cayley–Hamilton theorem, we have that $χ_{A} (A) = 0$ . So, in order to compute $A^{m}$ , it suffices to compute $r (A)$ .
Lemma 21.
Given a $(d \times d)$ matrix A with entries that are n-bit integers, the coefficients of the characteristic polynomial of A in CRR can be computed in ${\hat{TC}}_{1}^{0}$ .
Proof.
We convert the entries of A to CRR and compute the determinant of $(x I - A)$ . This involves an iterated sum of $O (2^{d} d!)$ integers each of which is an iterated product of d n-bit integers. The conversion to CRR is in ${\hat{TC}}_{1}^{0}$ by item 5 in Lemma 3. Since addition, multiplication, and powering of $O (1)$ numbers of $O (log n)$ bits is computable in ${AC}^{0}$ (by Lemma 3, items $3, 4$ and 6), it follows that the coefficients of the characteristic polynomial can be computed in ${\hat{TC}}_{1}^{0}$ . □
Lemma 22.
Given the coefficients of the polynomial r, in CRR, and given A in CRR, we can compute $A^{m}$ in CRR using ${AC}^{0}$ circuitry.
Proof.
Recall that $A^{m} = r (A)$ . Let $r (x) = r_{0} + r_{1} x + \dots + r_{d - 1} x^{d - 1}$ . Computing any entry of $r (A)$ in CRR involves an iterated sum of $O (1)$ many numbers which are themselves an iterated product of $O (1)$ many $O (log n)$ -bit integers. The claim follows by appeal to Lemma 3. □
Lemma 23 (Adapted from [36]).

Let p be a prime of magnitude $poly (m)$ . Let $g (x)$ of degree m and $f (x)$ of degree d be monic univariate polynomials over $G F_{p}$ , such that $g (x) = q (x) f (x) + r (x)$ for some polynomials $q (x)$ of degree $(m - d)$ and $r (x)$ of degree $(d - 1)$ . Then, given the coefficients of g and f, the coefficients of r can be computed in ${\hat{TC}}_{1}^{0}$ .

Proof.
Following [36], let $f (x) = \sum_{i = 0}^{d} a_{i} x^{i}$ , $g (x) = \sum_{i = 0}^{m} b_{i} x^{i}$ , $r (x) = \sum_{i = 0}^{d - 1} r_{i} x^{i}$ and $q (x) = \sum_{i = 0}^{m - d} q_{i} x^{i}$ . Since $f, g$ are monic, we have $a_{d} = b_{m} = 1$ . Denote by $f_{R} (x), g_{R} (x), r_{R} (x)$ and $q_{R} (x)$ respectively the polynomial with the i-th coefficient $a_{d - i}, b_{m - i}, r_{d - i - 1}$ and $q_{m - d - i}$ respectively. Then note that $x^{d} f (1 / x) = f_{R} (x)$ , $x^{m} g (1 / x) = g_{R} (x)$ , $x^{m - d} q (1 / x) = q_{R} (x)$ and $x^{d - 1} r (1 / x) = r_{R} (x)$ .

We use the Kung–Sieveking algorithm (as implemented in [36]). The algorithm is as follows:
Compute ${\tilde{f}}_{R} (x) = \sum_{i = 0}^{m - d} {(1 - f_{R} (x))}^{i}$ via interpolation modulo p.

Compute $h (x) = {\tilde{f}}_{R} (x) g_{R} (x) = c_{0} + c_{1} x + \dots + c_{d (m - d) + m} x^{d (m - d) + m}$ . from which the coefficients of $q (x)$ can be obtained as $q_{i} = c_{d (m - d) + m - i}$ .

Compute $r (x) = g (x) - q (x) f (x)$ .

To prove the correctness of our algorithm, note that we have $g (1 / x) = q (1 / x) f (1 / x) + r (1 / x)$ . Scaling the whole equation by $x^{m}$ , we get $g_{R} (x) = q_{R} (x) f_{R} (x) + x^{m - d + 1} r_{R} (x)$ . Hence when we compute $h (x) = {\tilde{f}}_{R} (x) g_{R} (x)$ in step 2 of our algorithm, we get $\begin{array}{l} h (x) = {\tilde{f}}_{R} (x) g_{R} (x) = {\tilde{f}}_{R} (x) q_{R} (x) f_{R} (x) + x^{m - d + 1} {\tilde{f}}_{R} (x) r_{R} (x) . \end{array}$

Note that ${\tilde{f}}_{R} (x) f_{R} (x) = {\tilde{f}}_{R} (x) (1 - (1 - f_{R} (x))) = \sum_{i = 0}^{m - d} {(1 - f_{R} (x))}^{i} - \sum_{i = 0}^{m - d} {(1 - f_{R} (x))}^{i + 1} = 1 - {(1 - f_{R} (x))}^{m - d + 1}$ (a telescoping sum). Since f is monic, $f_{R}$ has a constant term which is 1 and hence ${(1 - f_{R} (x))}^{m - d + 1}$ does not contain a monomial of degree less than $(m - d + 1)$ . This is also the case with $x^{m - d + 1} {\tilde{f}}_{R} (x) r_{R} (x)$ , and hence all the monomials of degree less than $(m - d + 1)$ belong to $q_{R} (x)$ .

Now we justify why the algorithm above is amenable to a ${\hat{TC}}_{1}^{0}$ implementation: Firstly, note that given $f (x)$ and $g (x)$ , the coefficients of $f_{R} (x)$ and $g_{R} (x)$ can be computed in ${NC}^{0}$ . To compute the coefficients of ${\tilde{f}}_{R} (x)$ , we use interpolation via the discrete Fourier transform (DFT) using arithmetic modulo p. Find a generator w of the multiplicative group modulo p and substitute $x = {w^{1}, w^{2}, \dots, w^{p - 1}}$ to obtain a system of linear equations in the coefficients F of ${\tilde{f}}_{R} (x) : V \cdot F = Y$ , where Y is the vector consisting of ${\tilde{f}}_{R} (w^{i})$ evaluated at the various powers of w. Since the underlying linear transformation $V (w)$ is a DFT, it is invertible; the inverse DFT $V^{- 1} (w)$ is equal to $V (w^{- 1}) \cdot {(p - 1)}^{- 1}$ , which is equivalent to $- V (w^{- 1}) mod p$ . We can find each coefficient of ${\tilde{f}}_{R} (x)$ by evaluating $V^{- 1} Y$ , i.e., by an inner product of a row of the inverse DFT-matrix with the vector formed by evaluating $\sum_{i = 1}^{(m - d + 1)} {(1 - f_{R} (x))}^{i - 1}$ at various powers of w and dividing by $p - 1$ . The terms in this sum can be computed in ${AC}^{0}$ , and then the sum can be computed in majority-depth one, to obtain the coefficients of ${\tilde{f}}_{R} (x)$ . The coefficients of $h (x)$ in step 2 can be obtained by iterated addition of the product of certain coefficients of ${\tilde{f}}_{R}$ and $g_{R}$ , but since the coefficients of ${\tilde{f}}_{R}$ are themselves obtained by iterated addition of certain terms t, we roll steps 1 and 2 together by multiplying these terms t by the appropriate coefficients of $g_{R}$ . Thus steps 1 and 2 can be accomplished in majority-depth 1. Then step 3 can be computed using ${AC}^{0}$ circuitry. □
Proof of Theorem 20.
Our ${\hat{TC}}_{3}^{0}$ circuit C that implements the ideas above is the following:
At the input, we have the $d^{2}$ entries $A_{i j}$ , $i, j \in [d]$ of A, a set Π of short primes (such that Π can be partitioned into $n^{c}$ sets $Π_{i}$ that are pairwise disjoint, i.e., $Π = ⋃_{i = 1}^{n^{c}} Π_{i}$ ), and the numbers $I = {1, 2, \dots, (m - d + 1)}$ .

In majority-depth one, we obtain (1) $A_{i j} mod p$ for each prime p in our basis, and (2) $M_{i} = \prod_{p \in Π_{i}} p$ for each of the $n^{c}$ sets $Π_{i}$ that constitute Π, and (3) the CRR of the characteristic polynomial of A (via appeal to Lemma 21).

In the next layer of threshold gates, we compute (1) $\prod_{i}^{n^{c}} (M_{i} - 1) / 2$ in CRR, and (2) the coefficients of the polynomial r in CRR, by appeal to Lemma 23.

At this point, by Lemma 22, ${AC}^{0}$ circuitry can obtain $r (A) = A^{m}$ in CRR, and with one more layer of MAJORITY gates we can convert to binary, by appeal to Corollary 11.
□

Now we consider the “succinct” versions of the problems of computing powers of integers and matrices (i.e., where the power is given in binary, instead of in unary notation), and show that these problems reduce to $BitSLP$ . (We do not consider taking powers of integers as a separate problem; an integer can be viewed as a 1-by-1 matrix.) Define: $\begin{array}{l} Bit - k - MatPow = {(A, N, p, q, I) : the I^{th} bit of entry (p, q) of the (k \times k) matrix A^{N} is 1} \end{array}$ (Here, the matrix A is represented by $k^{2}$ arithmetic circuits, with one circuit for each entry.) Theorem 24.
For every $k \in N$ , Bit-k-MatPow polynomial time reduces to $BitSLP$ .
Proof.
It is sufficient to produce arithmetic circuits computing $A^{N}$ . This is easily obtained via repeated squaring:

Since M is a $(k \times k)$ matrix with entries that are represented as arithmetic circuits, we can again compute $A^{N}$ using $n^{O (1)}$ additional arithmetic gates, by repeated squaring (where N is an n-bit number). Again, it is easy to construct this circuit, in polynomial time. □

3.6. Reducing sum-of-square-roots to matrix powering

In this section, we digress slightly from our presentation of efficient algorithms (in ${TC}^{0}$ or in $CH$ ), in order to address the question of whether the problems that we have shown to lie in $CH$ might have much more efficient algorithms. Evidence for the intractability of $PosSLP$ and $BitSLP$ is presented in [8]. But there is much less evidence that matrix powering is difficult. Here, we show that if one could power 2-by-2 matrices in $PH$ , then it would yield an improved upper bound on the well-known Sum-of-Square-Roots problem. More formally, we present a reduction, showing that the Sum-of-Square-Roots problem is reducible to the problem of computing large powers of 2-by-2 integer matrices, where the power of the reduction lies low in $CH$ .

Definition 25 (The Sum-of-Square-Roots Problem).

Let $a = (a_{1}, \dots, a_{n})$ be a list of n-bit positive integers, and let $σ = (σ_{1}, \dots, σ_{n}) \in {- 1, + 1}^{n}$ . Define $SSQRT (a, σ)$ to be the problem of determining if: $\begin{array}{l} \sum_{i = 1}^{n} σ_{i} \sqrt{a_{i}} > 0 \end{array}$

Theorem 26.
$SSQRT \in {PH}^{{PP}^{Bit - 2 - MatPow}}$ .

Our proof makes use of Linear Fractional Transformations (LFTs), which in turn correspond directly to 2-by-2 matrices. We introduce LFTs in the next subsection.
3.7. Linear fractional transformations (LFTs)

Here we give a brief introduction to LFTs based on the expositions in [28,56,57], concentrating only on the aspects required in this paper.

A linear fractional transformation is a function mapping $y \mapsto \frac{a y + c}{b y + d}$ for reals (and preferably integers) $a, b, c, d$ ; we associate the matrix $(\begin{matrix} a & c \\ b & d \end{matrix})$ to this mapping. The interesting thing about LFTs is that the matrix corresponding to the composition of two LFTs is the usual product of the matrices corresponding to the two LFTs. In other words, if the matrix corresponding to $ϕ_{i} (y)$ is $(\begin{matrix} a_{i} & c_{i} \\ b_{i} & d_{i} \end{matrix})$ (for $i = 1, 2$ ), then a matrix corresponding to $ϕ_{1} ϕ_{2} (y)$ (which abbreviates $ϕ_{1} (ϕ_{2} (y))$ ) is $(\begin{matrix} a_{1} & c_{1} \\ b_{1} & d_{1} \end{matrix}) (\begin{matrix} a_{2} & c_{2} \\ b_{2} & d_{2} \end{matrix})$ , as can be easily verified. In this paper we deal only with nonsingular LFTs (i.e., LFTs whose matrices have non-zero determinant). An LFT is said to be positive if all four entries in its matrix have the same sign.

Let ϕ be an LFT and let $M = (\begin{matrix} a & c \\ b & d \end{matrix})$ be its matrix. Then ϕ acts as a bijection between any interval $[p, q]$ and a subset of the extended reals $R \cup {\infty}$ . Further, this subset is also an interval (possibly including ∞): either $[ϕ (p), ϕ (q)]$ or $[ϕ (q), ϕ (p)]$ . Notice that we do not claim that there is a linear order on the reals augmented with ∞. Instead, we refer to these sets as “intervals” in the same sense that connected subsets of the unit circle can be called intervals.

For a concrete example, $ϕ [0, \infty]$ is the interval $[\frac{a}{b}, \frac{c}{d}]$ if $det (M) < 0$ and the interval $[\frac{c}{d}, \frac{a}{b}]$ if $det (M) > 0$ . Notice that $ϕ (\infty)$ is taken to be ${lim}_{y \to \infty} ϕ (y) = \frac{a}{b}$ . Notice also that $(- 1 / x) [- 1, 1]$ is the interval $[1, - 1]$ containing ∞.

An LFT is said to be refining for an interval $[p, q]$ if $ϕ [p, q] \subseteq [p, q]$ . We will need the following two propositions from [56]:

Proposition 27.
Given two non-trivial intervals $[p, q]$ and $[r, s]$ with $p \neq q$ and $r \neq s$ , there exists an LFT ϕ with $ϕ [p, q] = [r, s]$ .
Proposition 28.
For LFTs ϕ and ψ we have $ϕ [0, \infty] \supseteq ψ [0, \infty]$ iff $ψ = ϕ γ$ for a positive LFT γ.

Thus for any sequence of nested intervals $[p_{0}, q_{0}] \supseteq [p_{1}, q_{1}] \supseteq \dots \supseteq [p_{n}, q_{n}] \supseteq \dots$ we have $[p_{n}, q_{n}] = ϕ_{0} ϕ_{1} \dots ϕ_{n} [0, \infty]$ where $ϕ_{0}$ is an LFT and all other $ϕ_{i}$ ’s are positive LFTs.9
⁹
We call $[p_{n}, q_{n}]$ , the $n^{th}$ convergent of the LFT sequence ϕ.

Thus if a sequence of nested intervals converges to a real number r, then the corresponding infinite sequence of LFTs or the corresponding infinite product of matrices represents r; and the initial finite subsequence of LFTs applied to the interval $[0, \infty]$ yields increasingly finer approximations to r.

LFTs are closely related to continued fractions; in fact, the continued fraction $\begin{array}{l} a_{0} + \frac{b_{0}}{a_{1} + \frac{b_{1}}{⋱}} \end{array}$ corresponds to the LFT $(\begin{matrix} a_{0} & b_{0} \\ 1 & 0 \end{matrix}) (\begin{matrix} a_{1} & b_{1} \\ 1 & 0 \end{matrix}) \dots .$

An LFT for the square root function is: $\begin{array}{l} \sqrt{x} \equiv \prod_{n = 0}^{\infty} (\begin{matrix} x & x \\ 1 & x \end{matrix}) \end{array}$ for $x \in [1, \infty]$ . This differs slightly from the LFT specified in [56,57]. We establish its correctness below.

To see that this LFT ϕ is an LFT for the square root function, we first establish a bound on the length of the $n^{th}$ convergent. We use the following notation: $‖ [p, q] ‖ = q - p$ denotes the length of the interval $[p, q]$ . The following two subsections show that $‖ ϕ^{n} [0, \infty] ‖ \to 0$ as $n \to \infty$ .
3.8. Length of the $n^{th}$ convergent

Let $M_{i} = (\begin{matrix} a_{i} & c_{i} \\ b_{i} & d_{i} \end{matrix})$ and $P_{i} = \prod_{j = 0}^{i - 1} M_{j} = (\begin{matrix} A_{i} & C_{i} \\ B_{i} & D_{i} \end{matrix})$ . Then the length of the interval $[p_{n}, q_{n}] = \prod_{i = 0}^{n} M_{i} [0, \infty] = P_{n} M_{n} [0, \infty]$ is given by: $\begin{array}{l} ‖ P_{n} M_{n} [0, \infty] ‖ & = ‖(\begin{matrix} A_{n} & C_{n} \\ B_{n} & D_{n} \end{matrix}) (\begin{matrix} a_{n} & c_{n} \\ b_{n} & d_{n} \end{matrix}) ([0, \infty])‖ \\ = ‖(\begin{matrix} A_{n} a_{n} + C_{n} b_{n} & A_{n} c_{n} + C_{n} d_{n} \\ B_{n} a_{n} + D_{n} b_{n} & B_{n} c_{n} + D_{n} d_{n} \end{matrix}) ([0, \infty])‖ \\ = | \frac{A_{n} a_{n} + C_{n} b_{n}}{B_{n} a_{n} + D_{n} b_{n}} - \frac{A_{n} c_{n} + C_{n} d_{n}}{B_{n} c_{n} + D_{n} d_{n}} | \\ = | \frac{(A_{n} D_{n} - B_{n} C_{n}) (a_{n} d_{n} - b_{n} c_{n})}{(B_{n} a_{n} + D_{n} b_{n}) (B_{n} c_{n} + D_{n} d_{n})} | \end{array}$

3.9. Length of the $n^{th}$ convergent for the square root

Using the notation above with $M_{i} = (\begin{matrix} x & x \\ 1 & x \end{matrix})$ , we get $\begin{array}{l} ‖ [p_{n}, q_{n}] ‖ & = | \frac{(A_{n} D_{n} - B_{n} C_{n}) (x^{2} - x)}{(x B_{n} + D_{n}) (x B_{n} + x D_{n})} | \\ < | \frac{(A_{n} D_{n} - B_{n} C_{n}) (x^{2} - x)}{(x B_{n}) (x D_{n})} | \\ = | (\frac{A_{n}}{B_{n}} - \frac{C_{n}}{D_{n}}) (1 - \frac{1}{x}) | \\ = | (q_{n - 1} - p_{n - 1}) (1 - \frac{1}{x}) | \end{array}$ Thus, inductively, $q_{n} - p_{n} < | (q_{0} - p_{0}) {(1 - \frac{1}{x})}^{n} |$ .

Thus $ϕ^{n} (y) \to y_{0}$ for some $y_{0}$ and all $y \in [0, \infty]$ . In particular, $ϕ^{n} (y_{0}) \to y_{0}$ and thus $ϕ^{n + 1} (y) \to ϕ (y_{0})$ as $n \to \infty$ . Thus, $ϕ (y_{0}) = y_{0}$ , so that $\begin{array}{l} \frac{x y_{0} + x}{y_{0} + x} = y_{0} \end{array}$ Hence $x = y_{0}^{2}$ .

This establishes that ϕ is a LFT for the square root function.

Lemma 29.
If $[p_{n} (a), q_{n} (a)]$ denotes the $n^{th}$ convergent for the matrix sequence $M_{1}, M_{2}, \dots$ where each $M_{i} = L (a) = (\begin{matrix} a & a \\ 1 & a \end{matrix})$ , then $q_{n} (a) - p_{n} (a) < a {(1 - \frac{1}{a})}^{n + 1}$ . Thus if $a \in [1, 2]$ , then $0 ⩽ q_{n} (a) - p_{n} (a) < 2^{- n}$ , and for all $n, \sqrt{a} \in [p_{n} (a), q_{n} (a)]$ . Furthermore, $p_{n} (a) = {(L {(a)}^{n})}_{1, 2} / {(L {(a)}^{n})}_{2, 2}$ .
Proof.
From the foregoing, we have that $q_{n} (x) - p_{n} (x) < | (q_{0} (x) - p_{0} (x)) {(1 - \frac{1}{x})}^{n} |$ . But $[p_{0} (x), q_{0} (x)] = (\begin{matrix} x & x \\ 1 & x \end{matrix}) [0, \infty] = [1, x]$ . This yields $q_{n} (x) - p_{n} (x) < (x - 1) {(1 - \frac{1}{x})}^{n} ⩽ x (1 - \frac{1}{x}) {(1 - \frac{1}{x})}^{n} = {(1 - \frac{1}{x})}^{n + 1}$ .

The other parts of the lemma follow immediately. □
Proof of Theorem 26.
Let $(a, σ)$ be an input instance for $SSQRT$ . Let $α_{i}$ be a positive integer satisfying $2^{α_{i}} < a_{i} ⩽ 2^{α_{i} + 1}$ . Further, let $a_{i}^{'} = a_{i} / 2^{α_{i}}$ be a rational in $(1, 2]$ . Hence, by an application of Lemma 29, any number, say $p_{M} (a_{i}^{'})$ in the $M^{th}$ convergent interval of $L (a_{i})$ approximates $\sqrt{a_{i}^{'}}$ with an error of at most $2^{- M}$ . To obtain an approximation of $\sqrt{a_{i}}$ from this we need to multiply $p_{M} (a_{i}^{'})$ by $2^{⌊ \frac{α_{i}}{2} ⌋}$ (and if $α_{i}$ is odd then we must also multiply this by an approximation to $\sqrt{2}$ – which can also be approximated in this way by setting $a = 2$ and $α = 0$ ).

How good an approximation is needed? That is, how large must M be? Tiwari has shown [66] that if a sum of n square roots $\pm \sqrt{a_{i}}$ is not zero, where each $a_{i}$ has binary representation of length at most s, then the sum is bounded from below by $\begin{array}{l} 2^{- (s + 1) 2^{n}} \end{array}$ Thus taking $M = 2 (log n) (s + 1) 2^{n}$ and obtaining an approximation of each $\sqrt{a_{i}}$ to within $2^{- M}$ provides enough accuracy to determine the sign of the result. By Lemma 29, a suitable approximation is provided by ${(L {(a_{i})}^{M})}_{1, 2} / {(L {(a_{i})}^{M})}_{2, 2}$ (or – if $α_{i}$ is odd – by the expression ${(L {(a_{i})}^{M})}_{1, 2} {(L {(2)}^{M})}_{1, 2} / {(L {(a_{i})}^{M})}_{2, 2} {(L {(2)}^{M})}_{2, 2}$ ). Denote this fraction by $C_{i} / D_{i}$ . (Note that each $D_{i} > 0$ .)

Note that $\begin{array}{l} \sum_{i = 1}^{n} σ_{i} \sqrt{a_{i}} > 0 & \Leftrightarrow \sum_{i = 1}^{n} σ_{i} \frac{C_{i}}{D_{i}} > 0 \\ \Leftrightarrow \sum_{i = 1}^{n} σ_{i} C_{i} \prod_{j \neq i} D_{j} > 0 \end{array}$

We will need to re-write the expression $\sum_{i = 1}^{n} σ_{i} C_{i} \prod_{j \neq i} D_{j}$ in order to make it easier to evaluate. First, note that this expression is of the form $\sum_{i = 1}^{n} \prod_{j = 1}^{n} Z_{i, j}$ for integers $Z_{i, j}$ whose binary representation is of length less than $2^{n^{2}}$ . Thus this expression can written in the form $\sum_{i = 1}^{n} \prod_{j = 1}^{n} \sum_{k = 1}^{2^{n^{2}}} b_{i, j, k} 2^{k}$ where each $b_{i, j, k} \in {- 1, 0, 1}$ is easily computable from the input and from the oracle $Bit - 2 - MatPow$ . Via the distributive law, this can be rewritten as $\sum_{i = 1}^{n} \sum_{(k_{1}, k_{2}, \dots, k_{n}) \in {[2^{n^{2}}]}^{n}} \prod_{j = 1}^{n} b_{i, j, k_{j}} 2^{k_{j}}$ .

Thus there is a function f computable in polynomial time with an oracle for $Bit - 2 - MatPow$ that, on input $(a, σ, i, k_{1}, k_{2}, \dots, k_{n}, j, ℓ)$ outputs the $ℓ^{th}$ bit of the number $\prod_{j = 1}^{n} b_{i, j, k_{j}} 2^{k_{j}}$ . (Namely, the algorithm queries the n oracle bits corresponding to $b_{i, j, k_{j}}$ and combines this information with $σ$ to obtain the sign $\in {- 1, 0, 1}$ , and computes the value of the exponent $\sum_{j} k_{j}$ , and from this easily determines the value of bit ℓ of the binary representation.)

Since addition of m numbers, each consisting of m bits is computable in ${\hat{TC}}_{1}^{0}$ , it is now immediate that the bits of this expression are computable in ${PH}^{PP}$ . Thus in $PH$ , using the bits of this expression as an oracle, one can determine if the number represented in this manner is positive or not. (Namely, is there some bit that is non-zero, and is the sign bit positive?) □

4. Computing bits of algebraic numbers

In this section, we use the tools developed in the previous section to derive upper bounds on the problem of computing bits of algebraic numbers.

4.1. Mathematical preliminaries

Definition 30 (Algebraic number, Minimal Polynomial, Degree).

A real number α is called algebraic if there is a univariate polynomial p with rational (or – equivalently – integer) coefficients such that $p (α) = 0$ . There is a unique monic10

¹⁰
A univariate polynomial $p (x) = \sum_{i = 0}^{d} a_{i} x^{i}$ is monic if $a_{d} = 1$ .

univariate polynomial of minimal degree (and rational coefficients)

p_{α} (x)

such that

p_{α} (α) = 0

;

p_{α}

is said to be the defining polynomial or the minimal polynomial of the algebraic number α. The degree of α is the degree of

p_{α}

. The roots of

p_{α}

are called the Galois conjugates of α.

The minimal polynomial $p_{α}$ is irreducible; all of the Galois conjugates of α have the same degree d. In particular, no root of $p = p_{α}$ is also a root of the first derivatives of p (denoted $p^{'}$ ).

The Newton–Raphson method is a well-known algorithm for computing an approximation to a root of a univariate polynomial. For background, the reader can consult a textbook that explains the method, such as [31,65].

Definition 31 (Newton–Raphson).

Given a polynomial p and a starting point $x_{0}$ , recursively define: $\begin{array}{l} x_{i + 1} = x_{i} - \frac{p (x_{i})}{p^{'} (x_{i})}, \end{array}$ whenever $x_{i}$ is defined and $p^{'} (x_{i})$ is non-zero.

Note that if p is an irreducible polynomial (such as the minimal polynomial $p_{α}$ for an algebraic number α), then there is an interval $I = [α - β, α + β]$ around α such that $p^{'}$ has no roots in I, since $p^{'} (α) \neq 0$ and $p^{'}$ has only finitely-many roots. In fact, it is known that if β is small enough, then for any starting point $x_{0}$ in I, the sequence $x_{0}, x_{1}, \dots$ not only is infinite (because $p^{'} (x_{i}) \neq 0$ ), but it converges “rapidly” to α. Let us make precise the notion of “rapid” convergence.

Let $ϵ_{i}$ denote the error in the ith iteration of Newton–Raphson: $ϵ_{i} = | x_{i} - α |$ . We say that the Newton–Raphson sequence (with starting point $x_{0}$ ) converges quadratically (with parameter $M > 0$ ) if, for all $i ⩾ 0$ , $ϵ_{i + 1} ⩽ M ϵ_{i}^{2}$ . Note that we can assume (pessimistically) that $M ⩾ 1$ .

Much more is known about sufficient conditions on the size of the interval $I = [α - β, α + β]$ that are sufficient to guarantee quadratic convergence (for every choice of $x_{0} \in I$ , for the same parameter M), but for our purposes it is sufficient to know that this interval exists, and hence there is a rational number $x_{0}$ that we can use as the starting point for a Newton–Raphson sequence that converges quadratically to α. The constant $x_{0}$ will be hard-wired into our algorithm. We will impose some additional requirements on $x_{0}$ ; in particular, we will pick $x_{0}$ so that $ϵ_{0} = | x_{0} - α | < min (\frac{1}{4}, \frac{1}{2 M})$ . With this restriction on $x_{0}$ , a simple induction shows that, for all $i > 0$ , $ϵ_{i} ⩽ \frac{1}{2^{2^{i}} M} ⩽ \frac{1}{2^{2^{i}}}$ .

Since the Newton–Raphson sequence converges quadratically, this means that the number of bits of accuracy is doubling with each iteration (so that, after a polynomial number of iterations, the approximation is accurate to an exponential number of bits). But if the $i^{th}$ bit of $x_{n^{c}}$ is 0 (for example), do we really know that the $i^{th}$ bit of α is 0? If the next 100 bits of $x_{n^{c}}$ are all 1, it could still be possible that in our next underestimate $x_{n^{c} + 1}$ , the i-th bit would be 1, followed by 100 0’s and then a 1. How far do we need to “look ahead”, in order to be confident about the value of the $i^{th}$ bit of α?

The answer is provided by Liouville’s Theorem, which provides useful bounds on approximating algebraic numbers by rational numbers (see e.g. Shidlovskii [62] or Yap [72]).

Fact 32 (Liouville’s Theorem).

If α is a real algebraic number of degree $d ⩾ 1$ , then there exists a constant $c = c (α) > 0$ such that the following inequality holds for any $γ \in Z$ and $β \in N$ , $γ / β \neq α$ : $\begin{array}{l} | α - \frac{γ}{β} | > \frac{c}{β^{d}} \end{array}$

Roth’s theorem sharpens the inequality in Liouville’s theorem:

Fact 33 (Roth’s Theorem [60]).

If α is a real irrational algebraic number then there exists a constant $c = c (α, ϵ) > 0$ such that the following inequality holds for any $γ \in Z$ and $β \in N$ , $\begin{array}{l} | α - \frac{γ}{β} | > \frac{c (α, ϵ)}{β^{2 + ϵ}} \end{array}$

Roth’s theorem is optimal, in some ways: the number 2 in the exponent cannot be decreased.

The rest of this subsection is an adaptation of the corresponding material in [73], which gives a logspace algorithm to compute the digits of π. In contrast to the development in [73], we choose to utilize Liouville’s Theorem for algebraic numbers, instead of the advanced arguments required for bounding the irrationality measure of π. We could throughout replace the use of Liouville’s theorem by the much stronger and deeper Roth’s theorem, but we prefer not to do so, in order to retain the elementary nature of the arguments. We now introduce some terminology and notation that we will be using (some of which is standard, and some of which was introduced in [73]).

Definition 34.
Let α be a real number. Let ${α} = α - ⌊ α ⌋$ be the fractional part of α. Further, let ${α}_{n} = {2^{n} α}$ and let $α_{n}$ be the n-th bit after the binary point.

It is clear that $α_{n} = 1$ iff ${α}_{n - 1} ⩾ \frac{1}{2}$ . For algebraic numbers we can sharpen this:
Lemma 35 (Adapted from [73]).

Let α be an irrational algebraic number of degree d, and let $c = c (α)$ be the constant guaranteed by Liouville’s theorem. Let $δ_{n} = \frac{c}{2^{(d - 1) n + 1}}$ . Then we have:

$α_{n} = 1$ iff ${α}_{n - 1} > \frac{1}{2} + δ_{n}$ .

$α_{n} = 0$ iff ${α}_{n - 1} < \frac{1}{2} - δ_{n}$ .

Proof.
Taking $β = 2^{n}$ , and letting $γ \in N$ be the number whose binary representation corresponds to the first n bits in the binary representation of α, Liouville’s theorem implies that $| α - 2^{- n} γ | > \frac{c}{2^{d n}}$ , so $| 2^{n} α - γ | > \frac{c}{2^{(d - 1) n}} = 2 δ_{n}$ . Also, we have that $γ = 2 γ^{'} + α_{n}$ , where $γ^{'}$ is the first $n - 1$ bits of the binary representation of α.

Thus ${α}_{n - 1} = {2^{n - 1} α} = 2^{n - 1} α - γ^{'} = \frac{1}{2} (2^{n} α - γ) + \frac{α_{n}}{2}$ . This is greater than $\frac{1}{2} + δ_{n}$ if $α_{n} = 1$ . A similar calculation establishes the claim also in the case when $α_{n} = 0$ . □

As a consequence of Lemma 35, in order to be confident that our approximation to α is giving us the correct value for the $i^{th}$ bit of α, it is sufficient to have an approximation with error at most $\frac{1}{2^{O (i)}}$ . In other words, there is a constant b such that, if the $i^{th}$ bit of α is 1, then the binary representation of α will have another 1 appearing no later than position number $d i + b$ ; there is a bound on how many consecutive 1’s can appear in the binary representation of α. (And similarly, if the $i^{th}$ bit of α is 0, there will be another 0 that appears not too much later.) More specifically, recalling that our starting point $x_{0}$ is in the interval I where Newton–Raphson converges quadratically to α, and where $ϵ_{0} = | x_{0} - α | < min (\frac{1}{4}, \frac{1}{2 M})$ , this means that there is a constant $c \in N$ such that, given an n-bit number N, the $N^{th}$ bit of α is equal to the $N^{th}$ bit of $x_{c n}$ .
4.2. Algebraic numbers in ${CH}_{5}$

In this section, we prove our main result concerning algebraic numbers.

Theorem 36.
Let $α = \sum_{i = 0}^{\infty} a_{i} 2^{- (i + 1)}$ be an algebraic number, where each $a_{i} \in {0, 1}$ . Then the language $A_{α} = {j : a_{j} = 1}$ is in ${PH}^{{CH}_{3}}$ .
Proof.
Let $x_{0}$ be the starting point for the Newton–Raphson method as described in Section 4.1. Since $x_{0}$ is rational, let $x_{0} = \frac{a}{b}$ for integers a and b. Let p be the minimal polynomial for α. Recall that the Newton–Raphson sequence is defined as $x_{i + 1} = f (x_{i}) = x_{i} - \frac{p (x_{i})}{p^{'} (x_{i})} = \frac{x_{i} p^{'} (x_{i}) - p (x_{i})}{p^{'} (x_{i})}$ for all i. Thus $x_{2} = f (f (x_{0}))$ and more generally $x_{i} = f^{[i]} (x_{0})$ , where $f^{[i]}$ denotes the i-fold composition of f.

Consider an input string j of length n. As discussed in Section 4, $j \in A_{α}$ if and only bit j of $x_{c n}$ is equal to 1 (for some constant c). Our algorithm will create arithmetic circuits N and D (in polynomial time) so that the rational number $x_{c n}$ is equal to $\frac{N (a, b)}{D (a, b)}$ . Then we will use our ${PH}^{{CH}_{3}}$ algorithm from Corollary 18, to obtain the $j^{th}$ bit of $x_{c n} = f^{[c n]} (a / b)$ .

First, note that any polynomial $q (x) = \sum_{i = 0}^{d} a_{i} x^{i}$ , with rational coefficients, when applied to a rational input $x = \frac{y}{z}$ , (where $z \neq 0$ ) can be written as the quotient of two bivariate integer polynomials $n_{q} (y, z)$ and $d_{q} (z)$ : $\begin{array}{l} q (\frac{y}{z}) = \sum_{i = 0}^{d} a_{i} \frac{y^{i}}{z^{i}} \cdot \frac{z^{d - i}}{z^{d - i}} = \frac{\sum_{i = 0}^{d} L a_{i} y^{i} z^{d - i}}{L z^{d}} = \frac{n_{q} (y, z)}{d_{q} (z)}, \end{array}$ where L is the least common multiple of the denominators of the rational coefficients $a_{i}$ .

We are especially interested in the polynomials $n_{p}, d_{p}, n_{p^{'}}$ and $d_{p^{'}}$ . Thus $\begin{array}{l} f (y / z) & = \frac{(y / z) p^{'} (y / z) - p (y / z)}{p^{'} (y / z)} \\ = \frac{\frac{y n_{p^{'}} (y, z)}{z d_{p^{'}} (z)} - \frac{n_{p} (y, z)}{d_{p} (z)}}{\frac{n_{p^{'}} (y, z)}{d_{p^{'}} (z)}} \\ = \frac{\frac{y n_{p^{'}} (y, z) d_{p} (z) - z d_{p^{'}} (z) n_{p} (y, z)}{z d_{p^{'}} (z) d_{p} (z)}}{\frac{n_{p^{'}} (y, z)}{d_{p^{'}} (z)}} \\ = \frac{(y n_{p^{'}} (y, z) d_{p} (z) - z d_{p^{'}} (z) n_{p} (y, z)) d_{p^{'}} (z)}{z d_{p^{'}} (z) d_{p} (z) n_{p^{'}} (y, z)} \\ = \frac{F (y, z)}{G (y, z)}, \end{array}$ for integer bivariate polynomials F and G. Definition 37.
For a positive integer t, let the t-bicomposition of $(F, G)$ be the pair of bivariate polynomials $(F^{[t]}, G^{[t]})$ defined as follows: $\begin{array}{l} F^{[1]} (y, z) = F (y, z), G^{[1]} (y, z) = G (y, z), \end{array}$ and, $\begin{array}{l} F^{[t + 1]} (y, z) = F (F^{[t]} (y, z), G^{[t]} (y, z)), \\ G^{[t + 1]} (y, z) = G (F^{[t]} (y, z), G^{[t]} (y, z)) . \end{array}$

A straightforward induction shows that $f^{[t]} (y / z) = \frac{F^{[t]} (y, z)}{G^{[t]} (y, z)}$ .

Recall that p is the minimal polynomial for α, and it does not depend on the input j to $A_{α}$ . Similarly, the starting point $x_{0} = \frac{a}{b}$ is a fixed constant. Thus there are arithmetic circuits $N_{1} (a, b)$ and $D_{1} (a, b)$ of size $O (1)$ computing $F (a, b)$ , and $G (a, b)$ , respectively. For each $t > 1$ , the circuit $N_{t} (a, b)$ computing $F^{[t]} (a, b)$ can be constructed by running wires from the output gates of $N_{t - 1}$ and $D_{t - 1}$ to the $a, b$ input gates, respectively, of a copy of the circuit for $N_{1} (a, b)$ . The circuit for $D_{t} (a, b)$ is constructed similarly.

In this way, we construct in polynomial time the circuits $N (a, b) = N_{c n} (a, b)$ and $D (a, b) = D_{c n} (a, b)$ so that the rational number $x_{c n}$ is equal to $\frac{N (a, b)}{D (a, b)}$ , as desired. This completes the proof. □

4.3. Certain transcendentals in ${CH}_{5}$

Our results on algebraic numbers made use of Liouville’s Theorem, which shows that algebraic numbers can not be “too close” to rational numbers with small denominators. A similar property holds for several important transcendental numbers. This motivates the following definition:

Definition 38.
The irrationality measure of a transcendental number α is the infimum of $\begin{array}{l} {k : for all but finitely many (γ, β) \in Z \times N | α - \frac{γ}{β} | > \frac{1}{β^{k}}} \end{array}$

The irrationality measure of π is no more than 7.10321 [76]. The irrationality measure of e is equal to 2 (see [19]).

Yap took as his starting point a remarkable expression for π, discovered by Borwein, Borwein, and Plouffe [13]: $\begin{array}{l} π = \sum_{k = 0}^{\infty} \frac{120 k^{2} + 151 k + 47}{{(16)}^{k} (2^{9} k^{4} + 2^{10} k^{3} + 712 k^{2} + 194 k + 15)} \end{array}$

Borwein, Borwein, and Plouffe exhibited similar series for other transcendental numbers, such as ${log}_{10} 2$ and $π^{2}$ . Yap defined a series $\sum_{k = 0}^{\infty} t_{k}$ to be BBP-like if there are integer polynomials p and q and an integer c so that $t_{k} = \frac{p (k)}{2^{c k} q (k)}$ .

With these definitions in hand, we can state Yap’s theorem:
Theorem 39 ([73]).

If $α = a_{0} a_{1} a_{2} \dots$ is a transcendental real number that

has finite irrationality measure, and

can be expressed as a BBP-like series,

then there is a logspace-computable function

f_{α}

such that

f_{α} (1^{n}) = a_{o} a_{1} \dots a_{n}

We note that some of the motivation for the algorithms presented in [13], as well as some of the exposition in [73], comes from the ability to compute individual bits, without having to compute all of the earlier bits. In spite of this, the algorithm presented in [73] does yield a logspace algorithm computing all of the first n bits.

We improve on Theorem 39, by placing the function $f_{α}$ in the (seemingly) smaller complexity class ${TC}^{0}$ . (We discuss additional improvements to Theorem 39 later in this section.)

Theorem 40.
If $α = a_{0} a_{1} a_{2} \dots$ is a transcendental real number that
has finite irrationality measure, and

can be expressed as a BBP-like series,
then there is a ${TC}^{0}$ -computable function $f_{α}$ such that $f_{α} (1^{n}) = a_{o} a_{1} \dots a_{n}$ .
Proof.
Yap showed in [73] that the finite irrationality measure condition on α implies that, in order to compute $a_{0} a_{1} \dots a_{n}$ , it is sufficient to compute $\sum_{k = 0}^{n^{c^{'}}} t_{k} = \sum_{k = 0}^{n^{c^{'}}} \frac{p (k)}{2^{c k} q (k)}$ (for some constant $c^{'}$ ) to $n^{c^{'}}$ bits of accuracy, and then output the first $n + 1$ bits.

Let $T_{k} = \prod_{{i ⩽ n, i \neq k}} 2^{c k} q (k)$ . Then $\sum_{k = 0}^{n^{c^{'}}} t_{k} = \frac{\sum_{k = 0}^{n^{c^{'}}} T_{k} p (k)}{\prod_{k = 0}^{n^{c^{'}}} 2^{c k} q (k)}$ .

The numerator and denominator are both computable in ${TC}^{0}$ . Thus the theorem follows immediately by an application of Theorem 5. □

Both [73] and [13] explicitly ask if the algorithms that they present for π and similar numbers hold only for the binary representation, or if they can be modified to yield algorithms for the base-b representations for other bases b. But, as observed in Note 12, our techniques work equally well for base 10 or any other base.

Similarly, our proof of Theorem 40 applies not only to series that satisfy Yap’s BBP-like criterion, but for any series $\sum_{k = 0}^{\infty} t_{k}$ that converges rapidly to a transcendental number with bounded irrationality measure, if $t_{k} = \frac{n (k)}{d (k)}$ and the functions n and d are computable by ${TC}^{0}$ circuits of size polynomial in n. They do not need to be polynomials (or polynomials multiplied by $b^{c k}$ ). For example, to the best of our knowledge, no BBP-like series is known to converge to Euler’s constant e, but since $e = \sum_{k = 0}^{\infty} \frac{1}{k!}$ where the error term $ϵ_{n} = e - \sum_{k = 0}^{n} \frac{1}{k!} < \frac{1}{n!}$ , and where the numerator $n (k) = 1$ and denominator $d (k) = k!$ are easily computable by ${TC}^{0}$ circuits of size polynomial in n if $k = n^{O (1)}$ , this shows that the bits of e can also be computed in ${TC}^{0}$ . (This can also be derived from the earlier work of Reif and Tate [59], who showed that various numerical computations can be performed in P-uniform ${TC}^{0}$ ; their algorithms can be made dlogtime-uniform by appeal to [37].)

Much of the motivation in [13] (and, to a lesser extent, in [73]) comes from efficient implementations of programs to compute various constants. We do not claim that the algorithms presented here lend themselves to efficient implementation. They merely show that certain computations can be performed in ${TC}^{0}$ .

We now wish to prove a result that is analogous to Theorem 36, for various important transcendental numbers. However, in Theorem 36 we equate the characteristic sequence of a language with a real number in $[0, 1]$ , whereas the constants such as π and e that we consider lie outside of this interval. Thus, when we say “ $π \in {CH}_{k}$ ” and “ $e \in {CH}_{k}$ ”, we mean that the languages corresponding to the fractional parts of π and e ( ${π}$ and ${e}$ , respectively, using the notation introduced above) lie in ${CH}_{k}$ .

First, we show that the transcendental numbers that Yap studied in [73] all lie in ${PH}^{{CH}_{3}}$ .
Theorem 41.
Let $α = \sum_{k = 0}^{\infty} t_{k}$ be a transcendental real number having finite irrationality measure and a BBP-like series. Then $α \in {PH}^{{CH}_{3}}$ .
Proof.
We follow the same basic strategy as in the proof of Theorem 36, but we make use of the ${TC}^{0}$ circuits constructed in Theorem 15.

Given an input string j of length n, our goal is to compute the $j^{th}$ bit of the fractional part of α. As in Theorem 40, because of bounded irrationality measure and the rapid convergence of our series $\begin{array}{l} α = \sum_{k = 0}^{\infty} t_{k} = \sum_{k = 0}^{\infty} \frac{p (k)}{2^{c k} q (k)}, \end{array}$ (for integer polynomials p and q), it suffices to compute the $j^{th}$ bit of $\sum_{k = 0}^{2^{c^{'} n}} t_{k}$ , for some constant $c^{'}$ . As in the proof of Corollary 18, we first make use of some polynomial-time computation (in this case, it will be $PH$ computation), to prepare the CRR-representation of an exponentially-large input instance for a ${TC}^{0}$ circuit.

First, let us assume that $t_{k} > 0$ for all k. (This is true for the series for π.) Then we will modify the algorithm for more general BBP-like series.

The input instances for Theorem 15 need to be of the form $\sum_{i = 1}^{r} \frac{X_{i}}{Y_{i}}$ , where there is a natural number t such that $2^{t - 1} ⩽ Y_{i} < 2^{t}$ for all i. Using $PH$ computation, we can compute $B = max {2^{c k} q (k) : 1 ⩽ k ⩽ 2^{c^{'} n}}$ . To see this, note that the number $2^{c k} q (k)$ will require an exponential number of bits to write in binary for k at the high end of this range. However, the number $c k$ requires only $n^{O (1)}$ bits, and similarly $q (k)$ requires only $n^{O (1)}$ bits. Thus each such number $2^{c k} q (k)$ can be expressed exactly as $2^{c k} q (k) = x_{k} \cdot 2^{e_{k}}$ , for values $(x_{k}, e_{k})$ that are easy to compute, given k, and furthermore, it is easy to determine, given $(x_{k}, e_{k})$ and $(x_{k^{'}}, e_{k^{'}})$ , if $2^{c k} q (k) ⩾ 2^{c k^{'}} q (k^{'})$ . Thus, with a $PH$ oracle, a polynomial-time machine can find k such that, for all $k^{'}$ , it holds that $2^{c k} q (k) ⩾ 2^{c k^{'}} q (k^{'})$ . This determines B. Then, with B in hand, we can compute t such that $2^{t - 1} ⩽ B < 2^{t}$ .

Given k, we can compute $p (k)$ and $q (k)$ such that $t_{k} = \frac{p (k)}{2^{c k} q (k)}$ , and can compute a number $b_{k}$ such that $2^{b_{k} - 1} ⩽ 2^{c k} q (k) < 2^{b_{k}}$ . Let $e_{k} = t - b_{k}$ . Note that $t_{k} = \frac{2^{e_{k}} p (k)}{2^{e_{k}} 2^{c k} q (k)}$ , and for every $k, 2^{t - 1} ⩽ 2^{e_{k}} 2^{c k} q (k) < 2^{t}$ .

Now, similar to the proof of Corollary 18, we can let f be the function that, on input $(x, y) = ((j, t), (k, b, p))$ outputs “p is not prime” if p is not prime, and otherwise outputs $2^{e_{k}} p (k) mod p$ if $b = 0$ and outputs $2^{e_{k}} 2^{c k} q (k) mod p$ if $b = 1$ . Thus, we now have the CRR representation that satisfies the input requirements of Theorem 15, and we can appeal to Proposition 2.

This completes the argument, in the case when $t_{k} > 0$ for all k. Now we consider the more general case.

Since p and q are polynomials, they each tend to either ∞ or $- \infty$ for large k. If they are both positive or both negative for large k, then $t_{k} > 0$ for all large k, and the analysis is very similar to what appears above. Namely, let $t_{k} > 0$ for all $k > K$ Let $Q = \sum_{k = 0}^{K} t_{k}$ . Then we can compute an approximation to $\sum_{k = K + 1}^{\infty} t_{k}$ as above, and then simply add Q to the result.

In the remaining case, $t_{k} < 0$ for all large k. In that case, we can compute Q as above, and compute our underestimate A to $\sum_{k = K + 1}^{\infty} | t_{k} |$ as above, and then the desired answer is $Q - \sum_{k = K + 1}^{\infty} | t_{k} |$ – but note that $Q - A$ is an overestimate to α, which means that, if the $j^{th}$ bit of $Q - A$ is 1, it is still possible that the $j^{th}$ bit of α is 0. However, here we can once again appeal to the bounded irrationality measure of α. If we increase the accuracy of our approximation A (by summing up to $k = 2^{n^{c^{″}}}$ for some $c^{″} > c$ ), we are guaranteed to obtain an approximation that yields the correct bit for j. □
Corollary 42.
$π \in {PH}^{{CH}_{3}}$ .

There has been considerable progress using the BBP framework since the original paper [13] appeared. An extensive list can be found in [14]. Many of the “BBP-like” series presented in [14] do not actually fit Yap’s definition of “BBP-like”; the definition in [73] requires that $t_{k}$ be of the form $\frac{p (k)}{2^{c k} q (k)}$ , whereas many of the series presented in [14] have $t_{k}$ of the form $\frac{p (k)}{β^{k} q (k)}$ for some integer β where $β \neq 2$ . With some minor adjustments, we can accommodate this broader definition, too.
Corollary 43.
Let $α = \sum_{k = 0}^{\infty} t_{k}$ be a transcendental real number having finite irrationality measure, where there are integer polynomials p and q and integer β with $| β | ⩾ 2$ , and $t_{k} = \frac{p (k)}{β^{k} q (k)}$ . Then $α \in {PH}^{{CH}_{3}}$ .
Proof.
First we deal with the case when $β > 0$ .

As above, given an input string j of length n, our goal is to compute the $j^{th}$ bit of the fractional part of α, and once again it suffices to compute the $j^{th}$ bit of $\sum_{k = 0}^{2^{n^{c^{'}}}} t_{k}$ , for some constant $c^{'}$ , and once again we begin with a $PH$ computation, to prepare the CRR-representation of an exponentially-large input instance for a ${TC}^{0}$ circuit.

Now, however, we will compute $p (k)$ and $q (k)$ in β-ary notation, and begin by computing $B = max {β^{k} q (k) : 1 ⩽ k ⩽ 2^{n^{c^{'}}}}$ , and then find t such that $β^{t - 1} ⩽ B < β^{t}$ , and let f be the function that, on input $(x, y) = ((j, t), (k, b, p))$ outputs “p is not prime” if p is not prime, and otherwise outputs $β^{e_{k}} p (k) mod p$ if $b = 0$ and outputs $β^{e_{k}} q (k) mod p$ if $b = 1$ . Instead of the circuits that were presented in the proof of Theorem 15, we make use of the β-variant of those circuits (as defined in the footnotes to the proof of Theorem 5). This is because determining if a number B is less than $β^{t}$ is easy in base β, but less easy in base 2. Note that these β-variant circuits still produce the final answer in binary; it is merely the case that some of the intermediate computations take place using powers of β rather than powers of 2.

The analysis proceeds precisely as in the preceding theorem.

Now, we consider the case where $β < 0$ . In this case, note that $α = \sum_{k = 0}^{\infty} t_{k} = \sum_{ℓ = 0}^{\infty} (t_{2 ℓ)} + t_{2 ℓ + 1}) = \sum_{ℓ = 0}^{\infty} (\frac{p (2 ℓ)}{β^{2 ℓ} q (2 ℓ)} + \frac{p (2 ℓ + 1)}{β^{2 ℓ + 1} q (2 ℓ + 1)}) = \sum_{ℓ = 0}^{\infty} (\frac{p (2 ℓ) q (2 ℓ + 1) + p (2 ℓ + 1) β q (2 ℓ)}{β^{2 ℓ + 1} q (2 ℓ) q (2 ℓ + 1)}) = \sum_{ℓ = 0} \frac{r (ℓ)}{γ^{ℓ} s (ℓ)}$ for $γ = β^{2} > 0$ and integer polynomials r and s. Thus this case reduces to the previous case. □

We can, in principle, handle even more general terms $t_{k}$ . Our proof requires only that $t_{k} = \frac{n (k)}{d (k)}$ for numerator and denominator functions n and d, such that $β^{t} n (k) mod p$ and $β^{t} d (k) mod p$ be “easy” to compute (in $PH$ ), and also that it be possible (in $PH$ ) to find t such that $β^{t - 1} ⩽ d (k) < β^{t}$ . We have no examples at hand, to show that this generalization is useful for transcendental reals of interest. In particular, we do not see how to give a ${PH}^{{CH}_{3}}$ upper bound for e.

It is clear from the discussion after Theorem 40 that $e \in CH$ . The “naïve approach” mentioned at the start of the proof of Theorem 15 leads to a proof that $e \in {PH}^{{CH}_{4}}$ .
4.4. Lower bound

In this section, we complement our upper bounds on algebraic numbers by giving (rather weak) lower bounds for certain algebraic numbers. We emphasize that our lower bounds are only for rational numbers; we do not have any lower bounds at all for irrational algebraic numbers. Our lower bounds for rational numbers are fairly tight; we observe that all such numbers lie in ${ACC}^{0} = ⋃_{m} {AC}^{0} [m]$ , and for any prime m there is a rational number that lies outside ${AC}^{0} [m]$ .

First, we show membership in ${ACC}^{0}$ . The binary expansion of any rational number $α \in [0, 1]$ is ultimately periodic, meaning that it has the form $α = \sum_{i = 0}^{\infty} a_{i} 2^{- (i + 1)}$ where the sequence $a_{0}, a_{1}, a_{2}, \dots$ has the property that there is some k and some N such that, for all $j ⩾ N, a_{j} = a_{j + k}$ . Let $S = {ℓ : N ⩽ ℓ < N + k, a_{ℓ} = 1} = {ℓ_{1}, ℓ_{2}, \dots ℓ_{r}}$ for some $r < k$ . Thus the language $A_{α} = {x : a_{x} = 1}$ is equal to $F \cup L_{1} \cup \dots \cup L_{r}$ , where F is a finite set (of some strings that lexicographically precede N) and $L_{i} = {ℓ_{i} + c k : c \in N}$ . Each $L_{i}$ is therefore a linear set, and A is a semi-linear set (defined as the union of linear sets). Barrington and Corbett [16] showed that all semi-linear sets lie in ${ACC}^{0}$ . Thus we have shown:

Theorem 44 ([16]).

Let α be a rational number in $[0, 1]$ . Then the language $A_{α} \in {ACC}^{0}$ .

Now we turn to a lower bound.

Lemma 45.
For a given odd modulus m, there is a rational number $α_{m}$ whose language $A_{α_{m}}$ is hard for ${AC}^{0} [m]$ under ${AC}^{0}$ -Turing reductions. More precisely, the ${MOD}_{m}$ function reduces to $A_{α_{m}}$ under Dlogtime-uniform projections.
Proof.
Let m be an odd number, $m > 1$ , and let $α_{m}$ be the rational corresponding to the language $A_{α_{m}} = {c m : c \in N}$ .

The well-known Carmichael function $λ (m)$ from number theory has the property that, for any odd $m > 1$ , $λ (m) > 1$ and $2^{λ (m)} \equiv 1 (mod m)$ .

The ${MOD}_{m}$ function is defined so that ${MOD}_{m} (x) = 1$ if the number of 1’s in x is a multiple of m, and ${MOD}_{m} (x) = 0$ otherwise. Thus our goal is to take x as input and produce as output a number $f (x)$ that is a multiple of m if and only if the number of 1’s in x is a multiple of m. We make use of a construction that was used earlier in [9,18]. If $x = x_{0} x_{1} \dots x_{n}$ , let $f (x)$ be the number with binary representation $\begin{array}{l} x_{n} 0^{d} x_{n - 1} 0^{d} x_{n - 2} \dots x_{2} 0^{d} x_{1} 0^{d} x_{0} \end{array}$ where $d + 1 = λ (m)$ . Thus $f (x) = \sum_{i = 0}^{n} 2^{i λ (m)} x_{i}$ , which is equivalent to $\sum_{i = 0}^{n} x_{i}$ mod m. It is clear that f is easy to compute via a Dlogtime-uniform projection. The lemma follows, since the ${MOD}_{m}$ language is complete for ${AC}^{0} [m]$ under ${AC}^{0}$ -Turing reductions. □
Corollary 46.
For every prime m, there is a rational number $β_{m}$ such that $A_{β_{m}} \notin {AC}^{0} [m]$ .
Proof.
Let p be any prime other than m. If the language $A_{α_{p}}$ from Lemma 45 were in ${AC}^{0} [m]$ , then the ${MOD}_{p}$ language would also be in ${AC}^{0} [m]$ , contrary to the lower bounds of [58,64]. □

The restriction to prime moduli in Corollary 46 is essential, given the current state of lower bound techniques. It is still not known whether $NP = {AC}^{0} [6]$ . The best lower bounds against ${AC}^{0} [m]$ for composite m are those of [5,51].

It should perhaps be mentioned that there are rationals in ${AC}^{0}$ , other than dyadic rationals. For instance, $\frac{1}{3} = 010101 \dots$ corresponds to the set given by the regular expression ${(0 \cup 1)}^{*} 1$ , which is clearly in ${AC}^{0}$ . Since every rational number corresponds to a regular language, and since there are nice characterizations of the regular languages in ${AC}^{0}$ [15,24], there is probably a very crisp characterization of the rational numbers in ${AC}^{0}$ .
5. Open questions and discussion

Is conversion from CRR to binary in dlogtime-uniform ${\hat{TC}}_{1}^{0}$ ? This problem has been known to be in $P$ -uniform ${\hat{TC}}_{1}^{0}$ starting with the seminal work of Beame, Cook, and Hoover [17], but the subsequent improvements on the uniformity condition [22,37] introduced additional complexity that translated into increased depth. We have been able to reduce the majority-depth (relative to the construction in [37]) by rearranging the algorithmic components introduced in this line of research, but it appears to us that a fresh approach will be needed, in order to decrease the depth further.

Is $BitSLP$ in ${PH}^{PP}$ ? An affirmative answer to the first question implies an affirmative answer to the second, and this would pin down the complexity of $BitSLP$ between $P^{#P}$ and ${PH}^{PP}$ . We have not attempted to determine a small value of k such that $BitSLP \in {(Σ_{k}^{p})}^{A}$ for some set $A \in {CH}_{3}$ , because we suspect that $BitSLP$ does reside lower in $CH$ , and any improvement in majority-depth will be more significant than optimizing the depth of ${AC}^{0}$ circuitry, since $PH \subseteq P^{PP}$ .

Is $PosSLP$ in $PH$ ? Some interesting observations related to this problem were announced recently [30,40].

Is it easy to compute bits of large powers of small matrices? We remark in this regard, that there are some surprising things that one can compute, regarding large powers of integers [38] and the most significant bits of $2 \times 2$ matrices [33].

Does every transcendental real with a BBP-like series have finite irrationality measure?

Is $e \in {PH}^{{CH}_{3}}$ ? Is there any fundamental reason why e should be more complex than π in this sense?

Is any irrational algebraic number in $PH$ ? Is every irrational algebraic number in ${AC}^{0}$ ? We strongly conjecture that the answer to the second question is “no”, and we suspect that the answer to the first question is also “no”, although there is absolutely no evidence to support either conjecture. We think that it would be very instructive see an example of an irrational algebraic number that is outside of ${AC}^{0}$ . It would be remarkable and important, if it should turn out that irrational algebraic numbers reside in ${PH}^{{CH}_{3}} - PH$ .

Footnotes

Acknowledgements

The first author acknowledges the support of NSF grants CCF-1909216 and CCF-1909683. The second and the third authors were partially funded by a grant from Infosys Foundation. We would like to thank anonymous referees for help in improving the presentation of the paper, and we thank Howard Straubing and Bruno Grenet for helpful comments.

References

Adamczewski and

Bugeaud, On the complexity of algebraic numbers I. Expansions in integer bases, Annals of Mathematics (2007), 547–565. doi:10.4007/annals.2007.165.547.

Adamczewski,

Bugeaud and

Luca, Sur la complexité des nombres algébriques, Comptes Rendus Mathematique 339(1) (2004), 11–14. doi:10.1016/j.crma.2004.04.012.

Adamczewski,

Cassaigne and

Le Gonidec, On the computational complexity of algebraic numbers: The Hartmanis–Stearns problem revisited, Transactions of the American Mathematical Society 373(5) (2020), 3085–3115. doi:10.1090/tran/7915.

Agrawal,

Allender and

Datta, On TC⁰, AC⁰, and arithmetic circuits, Journal of Computer and System Sciences 60(2) (2000), 395–421. doi:10.1006/jcss.1999.1675.

Allender, The permanent requires large uniform threshold circuits, Chicago J. Theor. Comput. Sci. 1999 (1999). doi:10.4086/cjtcs.1999.007.

Allender, The division breakthroughs, in: Current Trends in Theoretical Computer Science, the Challenge of the New Century, Vol. 1: Algorithms and Complexity,

Paun,

Rozenberg and

Salomaa, eds, World Scientific, 2004, pp. 147–164. doi:10.1142/9789812562494_0011.

Allender,

Balaji and

Datta, Low-depth uniform threshold circuits and the bit-complexity of straight line programs, in: Mathematical Foundations of Computer Science (MFCS), Vol. 8635, Springer, 2014, pp. 13–24.

Allender,

Bürgisser,

Kjeldgaard-Pedersen and

P.B.

Miltersen, On the complexity of numerical analysis, SIAM J. Comput. 38(5) (2009), 1987–2006. doi:10.1137/070697926.

Allender,

M.E.

Saks and

I.E.

Shparlinski, A lower bound for primality, Journal of Computer and System Sciences 62(2) (2001), 356–366. doi:10.1006/jcss.2000.1725.

10.

Allender and

Schnorr, The complexity of the BitSLP problem, 2005, Unpublished Manuscript.

11.

J.-P.

Allouche and

Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003. ISBN 0521823323.

12.

Arora and

Barak, Computational Complexity: A Modern Approach, Vol. 1, Cambridge University Press, 2009.

13.

Bailey,

Borwein and

Plouffe, On the rapid computation of various polylogarithmic constants, Mathematics of Computation 66(218) (1997), 903–913. doi:10.1090/S0025-5718-97-00856-9.

14.

D.H.

Bailey, A Compendium of BBP-Type Formulas for Mathematical Constants, Report, Lawrence, Berkeley National Laboratory, Berkeley, CA, USA, 2017.

15.

D.A.M.

Barrington,

K.J.

Compton,

Straubing and

Thérien, Regular languages in NC1, Journal of Computer and System Sciences 44(3) (1992), 478–499. doi:10.1016/0022-0000(92)90014-A.

16.

D.A.M.

Barrington and

J.C.

Corbett, A note on some languages in uniform ACC⁰, Theor. Comput. Sci. 78(2) (1991), 357–362. doi:10.1016/0304-3975(91)90357-8.

17.

P.W.

Beame,

S.A.

Cook and

H.J.

Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing 15 (1986), 994–1003. doi:10.1137/0215070.

18.

R.B.

Boppana and

J.C.

Lagarias, One-way functions and circuit complexity, Information and Computation 74(3) (1987), 226–240. doi:10.1016/0890-5401(87)90022-8.

19.

J.M.

Borwein and

P.B.

Borwein, Pi and the AGM: A Study in the Analytic Number Theory and Computational Complexity, Wiley-Interscience, 1987.

20.

Brattka and

Hertling, Handbook of Computability and Complexity in Analysis, Springer, 2021. doi:10.1007/978-3-030-59234-9.

21.

Caussinus,

McKenzie,

Thérien and

Vollmer, Nondeterministic

{NC}^{1}

computation, Journal of Computer and System Sciences 57 (1998), 200–212. doi:10.1006/jcss.1998.1588.

22.

Chiu,

G.I.

Davida and

B.E.

Litow, Division in logspace-uniform NC¹, RAIRO Theoretical Informatics and Applications 35(3) (2001), 259–275. doi:10.1051/ita:2001119.

23.

Chonev,

Ouaknine and

Worrell, The orbit problem in higher dimensions, in: Proc. Symposium on Theory of Computing Conference (STOC), ACM, 2013, pp. 941–950. doi:10.1145/2488608.2488728.

24.

K.J.

Compton and

Straubing, Characterizations of regular languages in low level complexity classes, in: Current Trends in Theoretical Computer Science, Entering the 21th Century,

Paun,

Rozenberg and

Salomaa, eds, World Scientific, 2001, pp. 235–246.

25.

Datta and

Pratap, Computing bits of algebraic numbers, in: Proc. 9th Theory and Applications of Models of Computation (TAMC), Lecture Notes in Computer Science, Vol. 7287, Springer, 2012, pp. 189–201. doi:10.1007/978-3-642-29952-0_22.

26.

Dietz,

Macarie and

Seiferas, Bits and relative order from residues, space efficiently, Information Processing Letters 50(3) (1994), 123–127. doi:10.1016/0020-0190(94)00021-2.

27.

R.G.

Downey,

D.R.

Hirschfeldt,

Nies and

Stephan, Trivial reals, in: Proceedings of the 7th and 8th Asian Logic Conferences, World Scientific, 2003, pp. 103–131. doi:10.1142/9789812705815_0005.

28.

Edalat and

P.M.

Potts, A new representation for exact real numbers, Electronic Notes in Theoretical Computer Science 6 (1997), 119–132. doi:10.1016/S1571-0661(05)80166-5.

29.

Etessami and

Yannakakis, On the complexity of Nash equilibria and other fixed points, SIAM J. Comput. 39(6) (2010), 2531–2597. doi:10.1137/080720826.

30.

Etessami Probability, Recursion, Games, and Fixed Points, 2013, Talk presented at Horizons in TCS: A Celebration of Mihalis Yannakakis’ 60th Birthday.

31.

J.D.

Faires and

R.L.

Burden, Numerical Methods, PWS Publishing, Boston, 1993. ISBN 0-534-93136-7.

32.

Freivalds, Hartmanis–Stearns conjecture on real time and transcendence, in: Computation, Physics and Beyond – International Workshop on Theoretical Computer Science, WTCS 2012, Dedicated to Cristian S. Calude on the Occasion of His 60th Birthday, Revised Selected and Invited Papers,

M.J.

Dinneen,

Khoussainov and

Nies, eds, Lecture Notes in Computer Science, Vol. 7160, Springer, 2012, pp. 105–119. doi:10.1007/978-3-642-27654-5_9.

33.

Galby,

Ouaknine and

Worrell, On matrix powering in low dimensions, in: Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, Vol. 30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015, pp. 329–340. doi:10.4230/LIPIcs.STACS.2015.329.

34.

Goldmann and

Karpinski, Simulating threshold circuits by majority circuits, SIAM J. Comput. 27(1) (1998), 230–246. doi:10.1137/S0097539794274519.

35.

Hartmanis and

R.E.

Stearns, On the computational complexity of algorithms, Transactions of the American Mathematical Society 117 (1965), 285–306. doi:10.1090/S0002-9947-1965-0170805-7.

36.

Healy and

Viola, Constant-depth circuits for arithmetic in finite fields of characteristic two, in: Proc. 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Vol. 3884, Springer, 2006, pp. 672–683. doi:10.1007/11672142_55.

37.

Hesse,

Allender and

D.A.M.

Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences 65 (2002), 695–716. doi:10.1016/S0022-0000(02)00025-9.

38.

Hirvensalo,

Karhumäki and

Rabinovich, Computing partial information out of intractable: Powers of algebraic numbers as an example, Journal of Number Theory 130 (2010), 232–253. doi:10.1016/j.jnt.2009.08.009.

39.

Jeřábek, Root finding with threshold circuits, Theoretical Computer Science 462 (2012), 59–69. doi:10.1016/j.tcs.2012.09.001.

40.

Jindal and

Saranurak, Subtraction makes computing integers faster, 2012, CoRR arXiv:1212.2549.

41.

Kayal and

Saha, On the sum of square roots of polynomials and related problems, ACM Transactions on Computation Theory 4(4) (2012), 9:1–9:15. doi:10.1145/2382559.2382560.

42.

Ko, On the definitions of some complexity classes of real numbers, Mathematical Systems Theory 16(2) (1983), 95–109. doi:10.1007/BF01744572.

43.

Ko and

Friedman, Computational complexity of real functions, Theor. Comput. Sci. 20 (1982), 323–352. doi:10.1016/S0304-3975(82)80003-0.

44.

Koiran and

Perifel, The complexity of two problems on arithmetic circuits, Theor. Comput. Sci. 389(1–2) (2007), 172–181. doi:10.1016/j.tcs.2007.08.008.

45.

Koiran and

Perifel, Interpolation in valiant’s theory, Computational Complexity 20(1) (2011), 1–20. doi:10.1007/s00037-011-0002-8.

46.

Lechner,

Ouaknine and

Worrell, On the complexity of linear arithmetic with divisibility, in: 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE Computer Society, 2015, pp. 667–676. doi:10.1109/LICS.2015.67.

47.

R.J.

Lipton and

K.W.

Regan, People, Problems, and Proofs – Essays from Gödel’s Lost Letter: 2010, Springer, 2013. doi:10.1007/978-3-642-41422-0.

48.

Maciel and

Thérien, Threshold circuits of small majority-depth, Inf. Comput. 146(1) (1998), 55–83. doi:10.1006/inco.1998.2732.

49.

Mereghetti and

Palano, Threshold circuits for iterated matrix product and powering, ITA 34(1) (2000), 39–46.

50.

J.S.

Miller, Every 2-random real is Kolmogorov random, Journal of Symbolic Logic 69(3) (2004), 907–913. doi:10.2178/jsl/1096901774.

51.

C.D.

Murray and

R.R.

Williams, Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma, SIAM Journal on Computing 49(5) (2020). doi:10.1137/18M1195887.

52.

Nakanishi and

Villagra, Computational Complexity of Space-Bounded Real Numbers, 2018, CoRR, arXiv:1805.02572.

53.

Nies,

Stephan and

S.A.

Terwijn, Randomness, relativization and Turing degrees, The Journal of Symbolic Logic 70(2) (2005), 515–535. doi:10.2178/jsl/1120224726.

54.

Ouaknine and

Worrell, Positivity problems for low-order linear recurrence sequences, in: Proceedings of the Twenty-Fifth Annual ACM-Siam Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, pp. 366–379.

55.

Ouaknine and

Worrell, On the positivity problem for simple linear recurrence sequences, in: Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part II, Lecture Notes in Computer Science, Vol. 8573, Springer, 2014, pp. 318–329. doi:10.1007/978-3-662-43951-7_27.

56.

P.M.

Potts, Efficient on-line computation of real functions using exact floating point, in: Manuscript, Dept. of Computing, Imperial College, London, 1997.

57.

P.M.

Potts, Exact Real Arithmetic using Möbius Transformations, PhD thesis, Imperial College, University of London, 1999.

58.

A.A.

Razborov, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Matematicheskie Zametki 41 (1987), 598–607, In Russian. English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:333–338, 1987.

59.

J.H.

Reif and

S.R.

Tate, On threshold circuits and polynomial computation, SIAM J. Comput. 21(5) (1992), 896–908, citeseer.nj.nec.com/reif87threshold.html . doi:10.1137/0221053.

60.

K.F.

Roth, Rational approximations to algebraic numbers, Mathematika. A Journal of Pure and Applied Mathematics 2 (1955), 1–20.

61.

A.A.

Sherstov, Powering requires threshold depth 3, Inf. Process. Lett. 102(2–3) (2007), 104–107. doi:10.1016/j.ipl.2006.11.003.

62.

A.B.

Shidlovskii, Transcendental Numbers, de Gruyter, New York, 1989.

63.

K.-Y.

Siu and

V.P.

Roychowdhury, On optimal depth threshold circuits for multiplication and related problems, SIAM J. Discrete Math. 7(2) (1994), 284–292. doi:10.1137/S0895480192228619.

64.

Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proceedings, 19th ACM Symposium on Theory of Computing, 1987, pp. 77–82.

65.

Stark, Introduction to Numerical Methods, Macmillan, 1970.

66.

Tiwari, A problem that is easier to solve on the unit-cost algebraic RAM, J. Complexity 8(4) (1992), 393–397. doi:10.1016/0885-064X(92)90003-T.

67.

Toda, PP is as hard as the polynomial time hierarchy, SIAM J. Comput. 20 (1991), 865–877. doi:10.1137/0220053.

68.

A.M.

Turing, On computable numbers, with an application to the entscheidungsproblem, Proc. London Math. Soc. 2(42) (1936), 230–265.

69.

Vollmer, Introduction to Circuit Complexity, Springer-Verlag, 1999.

70.

Wegener, Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions, Inf. Process. Lett. 46(2) (1993), 85–87. doi:10.1016/0020-0190(93)90202-K.

71.

Weihrauch, Computable Analysis – an Introduction, Texts in Theoretical Computer Science. An EATCS Series, Springer, 2000. doi:10.1007/978-3-642-56999-9.

72.

Yap, Fundamental Problems in Algorithmic Algebra, Oxford University Press, 2000.

73.

Yap, Pi is in Log Space, 2010, manuscript available at: https://cs.nyu.edu/exact/doc/pi-log.pdf.

74.

Yu and

Ko, On logarithmic-space computable real numbers, Theoretical Computer Science 469 (2013), 127–133. doi:10.1016/j.tcs.2012.10.004.

75.

Yu,

Ding and

Downey, The Kolmogorov complexity of random reals, Annals of Pure and Applied Logic 129(1–3) (2004), 163–180. doi:10.1016/j.apal.2004.01.006.

76.

Zeilberger and

Zudilin, The irrationality measure of π is at most 7.103205334137…, Moscow Journal of Combinatorics and Number Theory 9(4) (2020), 407–419. doi:10.2140/moscow.2020.9.407.

On the complexity of algebraic numbers,and the bit-complexity of straight-line programs 1

Abstract

Keywords

1. Introduction

2 It is mistakenly claimed in [25] that these languages lie in PH CH 2 . We do not know how to obtain that stronger upper bound.

3. Overview of the new algorithmic results

Table 1 Prior bounds and new bounds on majority-depth for various problems Problem Nonuniform Majority–Depth [48] Uniform Majority–Depth [This Paper] Iterated multiplication 3 3 Division 2 3 Powering 2 3 CRR-to-binary 1 3 Matrix powering O(1) [37,49] 3

Definition 25 (The Sum-of-Square-Roots Problem).

Theorem 26. SSQRT ∈ PH PP Bit - 2 - MatPow . Our proof makes use of Linear Fractional Transformations (LFTs), which in turn correspond directly to 2-by-2 matrices. We introduce LFTs in the next subsection. 3.7. Linear fractional transformations (LFTs)

3.9. Length of the n th convergent for the square root

4.1. Mathematical preliminaries

Definition 30 (Algebraic number, Minimal Polynomial, Degree).

10 A univariate polynomial p ( x ) = ∑ i = 0 d a i x i is monic if a d = 1 .

Fact 32 (Liouville’s Theorem).

Fact 33 (Roth’s Theorem [60]).

Theorem 44 ([16]).

Footnotes

Acknowledgements

References

²
It is mistakenly claimed in [25] that these languages lie in ${PH}^{{CH}_{2}}$ . We do not know how to obtain that stronger upper bound.

Table 1
Prior bounds and new bounds on majority-depth for various problems

Problem Nonuniform Majority–Depth [48] Uniform Majority–Depth [This Paper]

Iterated multiplication 3 3

Division 2 3

Powering 2 3

CRR-to-binary 1 3

Matrix powering O(1) [37,49] 3

Theorem 26.
$SSQRT \in {PH}^{{PP}^{Bit - 2 - MatPow}}$ .

Our proof makes use of Linear Fractional Transformations (LFTs), which in turn correspond directly to 2-by-2 matrices. We introduce LFTs in the next subsection.
3.7. Linear fractional transformations (LFTs)

3.9. Length of the $n^{th}$ convergent for the square root

¹⁰
A univariate polynomial $p (x) = \sum_{i = 0}^{d} a_{i} x^{i}$ is monic if $a_{d} = 1$ .