Lawrence S Moss

Simple Equational Specifications of Rational Arithmetic

Keywords: equational specification, hidden function symbols, rational numbers

Introduction

This paper is a comment on the use of hidden functions in a well-studied example in the field of abstract data types. We are concerned with the rational numbers, considered as an algebra Q with the constants 0 and 1 and the operations of addition, subtraction, and multiplication, greatest integer function ⌊x⌋ and absolute value function |x|. To specify Q using initial algebra semantics means coming up with a possibly bigger signature Σ, writing a finite set E of equations in Σ, and then showing that the initial Σ-model of E is an expansion of Q.

This particular example of rational arithmetic (without ⌊x⌋ and |x|) seems to have been important historically, and a number of sources mention it. It is problematic because one cannot take a specification of the integers and add an inverse function inv(x). (The natural equation to add would be x × inv(x) = 1. But there is no way to equip the rationals with such an operation; there is no inverse of 0.) It is well-known that Q can be specified in some version of many-sorted equational logic. For example, Ehrig and Mahr [START_REF] Ehrig | Fundamentals of Algebraic Specifications I: Equations and Initial Semantics[END_REF] has a specification using "hidden" sorts of integers and booleans and also an error constant. This raises the issue of whether the error constant is necessary, and indeed it also raises the same issue about the use of more than one sort. It is also not hard to give a specification avoiding the error constant and using conditional equations and two sorts (see [START_REF] Meseguer | Review of[END_REF]). But then this raises the same question about conditional equations.

Ehrig and Mahr were also of the opinion (see p. 150 of [START_REF] Ehrig | Fundamentals of Algebraic Specifications I: Equations and Initial Semantics[END_REF]) that "Similar to other examples . . ., there seems to be also in this example no way around hidden function symbols." It is not clear whether they mean that hidden sorts were needed, but one senses that they were. Meseguer's review [START_REF] Meseguer | Review of[END_REF] of [START_REF] Ehrig | Fundamentals of Algebraic Specifications I: Equations and Initial Semantics[END_REF] interprets their comment by saying, "the authors conclude in 6.10 that there is no way around heavily using hidden functions and error constants to get the rational numbers." Again, it is not clear what would constitute a "heavy" use, but one senses that it would be the use of an additional sort. For it had been known from the work of Thatcher et al. [START_REF] Thatcher | Data type specification: parameterization and the power of specification techniques[END_REF] (following earlier results of Majster) that there are examples where hidden sorts are indeed necessary. And since rational arithmetic was not easily specifiable without hidden sorts, one might think that it was impossible to do so.

The goal of this note is to clear up the situation with regard to Q. Neither extra sorts nor error constants are needed to specify Q. Moreover, one can get by with just one hidden function, and that function can be taken to be unary. The key to our work is a recent result of Calkin and Wilf [START_REF] Calkin | Recounting the Rationals[END_REF] which shows that there is a bijection g : N → Q + which is definable by a very simple set of equations.

We should mention that the fact that Q has a finite specification with no hidden sorts follows immediately from the main theorem of Bergstra and Tucker [START_REF] Bergstra | Equational specifications, complete term rewriting systems, and computable and semicomputable algebras[END_REF]. Indeed, [START_REF] Bergstra | Equational specifications, complete term rewriting systems, and computable and semicomputable algebras[END_REF] has the stronger result that a minimal computable algebra has a specification which may be taken to a finite complete rewriting system. We shall have more to say on the "complete rewriting system" part at the very end of our note. For now, here is an explanation of how Bergstra and Tucker's theorem implies that Q has an equational specification. Since the rationals are countable, there are functions α, β, and γ such that Q, 0, 1, +, -, × ∼ = N, 0, 1, α, β, γ . Moreover, α, β, and γ may be taken to be primitive recursive. Now "minimal" means that every element of the carrier set should be the denotation of some term. This is not the case with Q, 0, 1, +, -, × , so not with N, 0, 1, α, β, γ either. But if we add to our signature a symbol s and interpret it by the successor function s on N, then N ′ = N, 0, 1, α, β, γ, s is minimal (and computable). So by the main theorem of [START_REF] Bergstra | Equational specifications, complete term rewriting systems, and computable and semicomputable algebras[END_REF], there is a bigger signature (but without new sorts) and a set of equations in it specifying Q ′ .

However, if one follows the method of [START_REF] Bergstra | Equational specifications, complete term rewriting systems, and computable and semicomputable algebras[END_REF], the specification of N ′ that one would get would be large. (The exact size would depend on the exact build up of α, β, γ as primitive recursive functions. My guess is that the actual specification would be too large for many people to ever write explicitly.) Our purpose is to exhibit small specifications which can be understood from first principles. These should be interesting to people who have worked in the area, and it would be suitable for classroom or textbook presentation.

The easiest way to get a one-sorted specification of Q is to begin with a specification for Z (any one will do, for example the laws of commutative rings with 1). Then add a function symbol f of arity 4, with the equation:

f(w, x, y, z) × (1 + w 2 + x 2 + y 2 + z 2 ) = 1.
The intended semantics is f (w, x, y, z) = (1 + w 2 + x 2 + y 2 + z 2 ) -1 . The point is that this f is total function on the rationals, and moreover, for every natural number n ≥ 1, there are natural numbers w, x, y, and z so that f (w, x, y, z) = 1/n. This uses the classical result of Lagrange that every natural number is the sum of four squares. It is not hard to check that this gives a specification of Q. We omit the details here since similar ones will be presented in Section 2 for a different set of equations below. The reason that we want to consider a different specification is that there does not seem to be a way to add other interesting functions, such as absolute value or greatest integer, on top of this specification. Another reason is that I could not see a way to reduce the arity of f . Perhaps a unary function like f (x) = (1 + x + x 2 ) -1 would work, but the matter is open. (As Ignacio Viglizzo pointed out to me, f (x) = (1 + x 2 ) -1 does not work because the smallest subring of Q closed under this operation does not contain 1/3.)

Our results are summarized in the table below. Each line represents a specification. The result that Q, 0, 1, +, -, ×, ⌊ ⌋ can be specified with one hidden symbol which is unary is probably the most important of this paper.

Structure Hidden symbols Number of Hidden Equations

Q, 0, 1, +, -, × one 4-ary 1 Q, 0, 1, +, -, × two unary 21 Q, 0, 1, +, -, ×, ⌊ ⌋ one unary 18 Q, 0, 1, +, -, ×, ⌊ ⌋, | | one unary 18 2 A Specification of Q, 0, 1, +, -, ×, ⌊ ⌋
We begin with the following result:

Proposition 1 There is a unique f : Z → Z so that for all n ∈ Z:

f (4n) = 1 f (1 + 4n) = f (n) f (2 + 4n) = f (n) + f (1 + n) f (3 + 4n) = f (1 + n) Moreover, 1. For all n ∈ Z, f (n) ≥ 1.
2. For all a, gcd(

f (a), f (1 + a)) = 1.

If a and b are positive integers

such that gcd(a, b) = 1, then there is some c ≥ 0 so that f (c) = a and f (1 + c) = b.
Proof For the uniqueness, note that for all integers n, |1 + 4n| > n and |2 + 4n| > n + 1. This implies that for all n except 0, the values of the left sides of the recursion equations for f are always greater in absolute value than those on the right. This, together with the fact that f (0) = 1, means that f is specified uniquely on all integers. Parts (1) and ( 2) are an easy induction on n. Our f is not the only function with the properties of Proposition 1, of course. For our purposes, the only facts we need are those of the proposition, together with the facts that some natural functions related to f are equationally specifiable. We turn to these matters shortly.

But first, we should mention that this function f is based on a function from Calkin and Wilf's article [START_REF] Calkin | Recounting the Rationals[END_REF]. That paper considers the following simpler version which we call f 0 : f 0 (0) = 1, f 0 (2n + 1) = f 0 (n), and f 0 (2n + 2) = f 0 (n) + f 0 (n + 1). Then [START_REF] Calkin | Recounting the Rationals[END_REF] shows that for all n ≥ 0, f 0 (n) and f 0 (n + 1) are relatively prime, and that for all relatively prime a and b there is a unique n so that f 0 (n) = a and f 0 (n+1) = b.

In other words, if we define g : N → Q + by g(n) = f 0 (n)/ f 0 (n + 1), then g is a bijection. This leads to a rather explicit proof of Cantor's theorem that the rationals are countable.

The problem for us about f 0 is that the equation f 0 (2n + 2) = f 0 (n) + f 0 (n + 1) implies that f 0 (-1) = 0. We needed to modify f 0 to obtain a function on Z all of whose values are positive. We lose the uniqueness assertion, but this is not a big problem.

Returning to our development, we extend f to a function which we also call f in the following way: f (x) = f (⌊x⌋). (Here ⌊x⌋ is the greatest integer ≤ x; for example ⌊-1/2⌋ = -1.) This is one natural way to extend f . There are other ways, and they would lead to other sets of equations. We chose this way because the details are the simplest that we could find, and because the resulting set of equations is the smallest. Once again, we use f (x) = f (⌊x⌋). This determines f :

Q → Q. Next, let g : Q → Q be given by g(x) = f (x)/ f (1 + x). Then again g(x) = g(⌊x⌋)
. The point about g is that for every positive rational number m/n in lowest terms, there is some natural number a so that g(a) = m/n.

We need the following equations involving g and ⌊x⌋:

⌊g(4n)⌋ = h(n) ⌊g(1 + 4n)⌋ = 0 ⌊g(2 + 4n)⌋ = 1 + ⌊g(n)⌋ ⌊g(3 + 4n)⌋ = f (1 + n) ⌊-g(4n)⌋ = -1 ⌊-g(1 + 4n)⌋ = -1 ⌊-g(2 + 4n)⌋ = -1 + ⌊-g(n)⌋ ⌊-g(3 + 4n)⌋ = -f (1 + n)
Note that here n is an integer. We can obtain equations valid for all rational x by replacing n by ⌊x⌋ throughout. The function h : Z → Z which figures into g is given by

h(4n) = 1 h(1 + 4n) = h(n) h(2 + 4n) = 0 h(3 + 4n) = h(1 + n)
As with g, h extends naturally to a function on Q by h(x) = h(⌊x⌋). The point is that for all n, h(n

) = 1 iff f (n) = 1, and h(n) = 0 iff f (n) > 1.
So ⌊g(4n)⌋ = 0 iff h(1 + 4n) = 0, and ⌊g(4n

)⌋ = 1 iff h(1 + 4n) = 1.
It follows that for all x ∈ Q, ⌊g(4n)⌋ = h(1 + 4n) = h(n). As we have seen, the extended h is equationally specifiable.

The specification

We take our signature Σ to consist of the symbols 0, 1, + , -, × , ⌊, f, g, h, where 0 and 1 are 0-ary (i.e., constants); -, ⌊, f, g, and h are 1-ary; and + and × are binary. As we have already been doing, we use a different font to distinguish syntax from semantics. Our set E of equations is listed in the box below. Of course, the main example of a Σ-algebra satisfying E is

Q = Q, 0, 1, +, -, ×, ⌊ ⌋, f , g, h ,
where all of the interpretations shown are the ones we have already considered. That is, henceforth Q denotes the rationals equipped with all of the functions above.

Here are a few comments on our notation and equations: In general, we omit the parentheses on ⌊(x), and we sometimes omit other parentheses for readability. We use 2 as an abbreviation for 1 + 1, and similarly for 3 and 4. Further, 4⌊x abbreviates 4 × ⌊x. In the invariance equation (3), we do not need

The set E of equations for Q, 0, 1, +, -, ×, ⌊ ⌋ using hidden functions f, g, and h

1. The equational laws of commutative rings with 1.

Concerning

⌊: ⌊0 = 0, ⌊(1 + x) = 1 + ⌊x, and ⌊(-1 + x) = -1 + ⌊x.
3. The laws that ⌊ is invariant for f and h: fx = f⌊x and hx = h⌊x.

The connection of g and f

: g(x) × f(1 + x) = f(x).
5. The recursion equations for f, h, ⌊g and ⌊-g:

f(4⌊x) = 1 f(1 + 4⌊x) = f(x) f(2 + 4⌊x) = f(x) + f(1 + x) f(3 + 4⌊x) = f(1 + x) ⌊g(4⌊x) = h(x) ⌊g(1 + 4⌊x) = 0 ⌊g(2 + 4⌊x) = 1 + ⌊g(x) ⌊g(3 + 4⌊x) = f(1 + x) h(4⌊x) = 1 h(1 + 4⌊x) = h(x) h(2 + 4⌊x) = 0 h(3 + 4⌊x) = h(1 + x) ⌊-g(4⌊x) = -1 ⌊-g(1 + 4⌊x) = -1 ⌊-g(2 + 4⌊x) = -1 + ⌊-g(x) ⌊-g(3 + 4⌊x) = -f(1 + x)
gx = g⌊x; the ground instances of this turn out to be derivable. For the same reason, we do not need ⌊⌊x = ⌊x in (2). Concerning [START_REF] Meseguer | Review of[END_REF], note that earlier we had the same laws but for integers n. The important point is that since f (x) = f (⌊x⌋) for all x, the laws in (5) are valid in Q.

Finally, notice that E has 2 + 1 + 16 = 19 equations that use the hidden symbols.

Proof of correctness

As usual, we let T Σ be the set of (ground) Σ-terms, and T Σ /E the quotient of T Σ by the smallest Σcongruence including the substitution instances of E. Let ε : T Σ → Q be the unique Σ-homomorphism.

We write E ⊢ t = u to mean that t = u is derivable from E in equational logic. (This is the logical system whose axioms are the substitution instances of the equations in E ∪ {x = x} and whose rules of inference correspond to the symmetric and transitive properties of equality and to the substitution of equals for equals in functions.) We shall only be interested in this when t and u are ground terms, and then it also means that

[t] = [u] in T Σ /E.
We prove that T Σ /E ∼ = Q. The idea is that every term is provably equal, mod E, to a special kind of term which we call normal. To state the definition, and for our future work, we associate with each integer n a term n in the following way. For n = 0, we set n to be 0;

for n = 1 + • • • + 1, we set n to be 1 + • • • + 1; and for n = -(1 + • • • + 1), we use -(1 + • • • + 1
). Now we can say that our normal terms are 0, g(n) for n ≥ 1, and -g(n) for n ∈ Z. 1) is an easy consequence of the initiality of Z among commutative rings with 1. Part ( 2) is an easy induction on |a|, as is (3). In addition, (3) uses the invariance laws for ⌊ with f and h, and also parts ( 1) and [START_REF] Calkin | Recounting the Rationals[END_REF]. It is essentially an elaboration of the proof of Proposition 1.

⊣

Lemma 3 If t ∈ T Σ is such that E ⊢ t × f(1 + n) = f(n), then E ⊢ t = g(n)
.

Proof Let m = 1 + 4(1 + n), so that f (m) = 1, f (1 + m) = f (1 + n), and g(m) = 1/ f (1 + n). Then E ⊢ g(m) × f(1 + m) = 1. And by Lemma 2(3), E ⊢ f(1 + n) = f(1 + m).
From these facts and the commutative, associative, and unit laws, we deduce according to E that We also use Lemma 3 to check part (3). We know that

t = t × 1 = t × f(1 + m) × g(m) = t × f(1 + n) × g(m) = f(n) × g(m) = g(n) × f(1 + n) × g(m) = g(n) × f(1 + m) × g(m) = g(n) ⊣ Lemma 4 Let a, b ∈ Z. Then 1. E ⊢ ga = g⌊a.
f (a) f (1 + b) + f (1 + a) f (b) f (1 + a) f (1 + b) = f (c) f (1 + c) .
Moreover, the second fraction is reduced. Let m be such that m

• f (c) = f (a) f (1 + b) + f (1 + a) f (b) and m • f (1 + c) = f (1 + a) f (1 + b). Let n be such that f (n) = 1 and f (1 + n) = m. So g(n) = 1/m. Using Lemma 2, parts (1)
and ( 3), we see that

E ⊢ f(1 + n) × f(c) = (f(a) × f(1 + b)) + (f(1 + a) × f(b)),
and also that

E ⊢ f(n) = 1 and that E ⊢ f(1 + n) × f(1 + c) = f(1 + a) × f(1 + b). So modulo E, (g(a) + g(b)) × f(1 + c) = (g(a) + g(b)) × f(1 + c) × f(1 + n) × g(n) = (g(a) + g(b)) × f(1 + a) × f(1 + b) × g(n) = (g(a)f(1 + a)f(1 + b) + g(b)f(1 + a)f(1 + b)) × g(n) = (f(a)f(1 + b) + f(1 + a)f(b)) × g(n) = f(c) × f(1 + n) × g(n) = f(c) × f(n) = f (c)
(We have omitted some × signs for readability.) Part ( 4) is similar, and ( 5) is the easiest to check. ⊣

In the next lemma, recall that the normal terms are 0 and also gn and -gn for n ∈ Z.

Lemma 6 For every t ∈ T Σ there is some normal u ∈ T Σ such that E ⊢ t = u.

Proof By induction on t. Obviously 0 is normal, and as for 1, E ⊢ 1 = g(0) by a calculation involving Lemma 3. Assuming the lemma for t and u, we easily get it for t + u, -t and t × u. The routine details use Lemma 5.

Concerning ⌊t, we argue as follows: By induction hypothesis, t is normal. If E ⊢ t = 0, then E ⊢ ⌊t = ⌊0 = 0. Suppose, for example, that E ⊢ t = -g(n). Then E ⊢ ⌊t = ⌊-g(n). Now ⌊-g(n)⌋ is some natural number b, and by Lemma 5(2), E ⊢ ⌊-g(n) = b. If b = 0, then b is normal and we are done. Otherwise, let a be so that g(a) = b. Then by Lemma 5 [START_REF] Calkin | Recounting the Rationals[END_REF] we see that

E ⊢ ⌊t = ⌊-g(n) = g(a).
The argument for f(t) is similar:

If E ⊢ t = 0, then E ⊢ f(t) = f(0) = 1 = g(0). Suppose again that E ⊢ t = -g(n). Then E ⊢ f(t) = f(-g(n)) = f⌊-g(n)
. This uses the invariance law for ⌊ and f. Now ⌊-g(n)⌋ is some natural number b, and by Lemma 5( 2), E ⊢ ⌊-g(n) = b. Let a and c be natural numbers such that c = f (b) and g(a

) = c, so that E ⊢ f(b) = c = g(a). Then E ⊢ f(t) = g(a).
The same argument works for h(t). For g(t), the argument is slightly easier: as soon as we know

E ⊢ ⌊-g(n) = b, we then have E ⊢ g⌊-g(n) = g(b). This last term is normal. ⊣ Theorem 7 T Σ /E ∼ = Q.
Proof Let ϕ : T Σ /E → Q be the unique Σ-homomorphism, by initiality. Explicitly, ϕ([t]) = ε(t). Then ϕ is surjective, since ϕ(0) = 0, and for every positive rational r there is some n so that ε(g(n)) = g(n) = r (and hence also ε(-g(n)) = -r).

We conclude by showing that ϕ is injective. Let ε(t) = ε(u). We assume first that this number is positive, say ε(t) = g(n). Then there are normal terms t ′ and u ′ so that E ⊢ t = t ′ and E ⊢ u = u ′ . Since ε(t ′ ) = ε(t) = g(n) > 0, t ′ must be of the form g(m) for some m. Similarly, u ′ must be of the form g(p)

for some p. But now g(m) = g(n) = g(p). So by Lemma 5(1), we see that E ⊢ g(m) = g(n) = g(p). And from this we see that E ⊢ t = g(n) = t ′ . This concludes the argument when ε(t) > 0. Of course, the same reasoning applies when ε(t) < 0. If ε(t) = 0 = ε(t ′ ), then again we have normal u and u ′ as above. We have ε(u) = ε(t) and ε(u ′ ) = ε(t ′ ). By normality, u and u ′ must both be the term 0. And so E ⊢ t = 0 = t ′ . ⊣

One hidden function

We promised at the outset to get things down to one hidden function symbol which is unary. Currently we have three hidden symbols, f, g, and h. To combine them into one, say i, we first describe the intended semantic function i. On integers, i is given by i(3n) = f (n), i(1 + 3n) = g(n), and i(2 + 3n) = h(n). Then we extend this to all rationals by i(x) = i(⌊x⌋). Let Q * = Q, 0, 1, +, -, ×, i . Let Σ be our old signature, and let Σ * = (Σ \ {f, g, h}) ∪ {i}. There is a translation t → t * of T Σ to T Σ * given as follows: x * = x for variables, 0 * = 0, 1 * = 1, (⌊t) * = ⌊t * , (t + u) * = t * + u * , and similarly forand × , (ft) * = i(3⌊t * ), (gt) * = i(1 + 3⌊t * ), (ht) * = i(2 + 3⌊t * ). For example, n * = n for all n ∈ Z. And the translations of the normal terms of T Σ are just those of the form i(1 + 3n), where n ∈ Z. We get a set E * of Σ * -equations by

E * = {t * = u * : t = u is an axiom of E}. Theorem 8 T Σ * /E * ∼ = Q * .
Proof The translation map commutes with substitution in the appropriate sense. Using this, we prove by an easy induction on derivations that if E ⊢ t = u, then E * ⊢ t * = u * .

The crux of the proof is the analog of Lemma 6: for every term t ∈ T Σ * there is some normal u ∈ T Σ such that E * ⊢ t = u * . Just as in Theorem 7, this implies that T Σ * /E * ∼ = Q * .

We argue by induction on t. The only interesting case is for i. Assuming that E * ⊢ t = u * , we consider i(t). Since the case that u is 0 is easy, we consider only the case when u is gn. Then E * ⊢ i(t) = i⌊t = i⌊(gn) * = i(⌊gn) * . Let m = ⌊g(n)⌋, so E ⊢ ⌊gn = m by Lemma 4(2). Thus E * ⊢ i(t) = i(m). Now we argue by cases on m. If m is of the form 3p or 2 + 3p for some positive integer p, then im is (fp) * or (hp) * . Both situations are similar. In the first, let q be such that g(q) = f (p). Then E ⊢ fp = gq, and so

E * ⊢ i(t) = (gq) * . If m is of the form 1 + 2p, then i(m) is (gp) * . So E * ⊢ i(t) = (gp) * . ⊣
At this point, E * has 19 equations involving i. The translations of f⌊x = fx and h⌊x = hx can be replaced by i⌊x = ix. So we are left with a specification with i as the one and only hidden function symbol, and 18 equations using i.

Additional remarks

More operations We also promised to specify Q with the absolute value function |x|. Here we would add |0| = 0, |g(x)| = g(x), and |-g(x)| = g(x).

We could also consider a function inv on Q defined by inv(0) = 0 and inv(m/n) = n/m. We specify this using inv(0) = 0, inv(gx) × gx = 1, and inv(-gx) × (-gx) = 1.

Fewer operations Suppose one wants to drop ⌊x⌋ and specify the ring Q, 0, 1, +, -, × with as few hidden symbols as possible. Our work gives this with two hidden unary symbols, ⌊ and i. Since ⌊ is hidden, we now have 18 + 3 = 21 hidden equations. We do not know how to specify this structure with just one unary hidden symbol, though we believe that this should be possible. As we mentioned early on, one 4-ary symbol suffices.

Rewriting Specifications of Q We conclude with a remark on rewriting presentations for Q, as studied in Contejean et al [START_REF] Contejean | Rewrite systems for natural, integral, and rational arithmetic[END_REF]. Their paper is really about getting a rewriting presentation suitable for efficient computation. Our work does not address that important issue. In any case, the paper gives a threesorted presentation of rational arithmetic using a complete rewrite system. The three sorts are the natural numbers, the non-zero natural numbers, and the rationals. Moreover, the addition and multiplication on the natural number sort are associative and commutative. A complete rewrite system obtained by the methods of [START_REF] Bergstra | Equational specifications, complete term rewriting systems, and computable and semicomputable algebras[END_REF] should be neither associative nor commutative. It is still open to get a rewrite presentation with addition and multiplication on the rational number sort being associative and commutative.

Our approach cannot directly give a complete rewrite system for two reasons. First and foremost, the connection law g(x) × f(1 + x) = f(x) leads to a non-confluent system. The same is true of the distributive law, which we have used in a few places. (However, [START_REF] Contejean | Rewrite systems for natural, integral, and rational arithmetic[END_REF] show how to use a positional notation for integers to get around this.) We believe it is likely that our work could be combined with that of [START_REF] Contejean | Rewrite systems for natural, integral, and rational arithmetic[END_REF] to get a two-sorted presentation of rational arithmetic, again with addition and multiplication on integers to be associative and commutative.

For ( 3 )

 3 , we argue by induction on max(a, b). If a = b = 1, we take c = 0. In case a > b > 1, we consider ab and b. Clearly gcd(ab, b) = 1. (This is just the argument behind the Euclidean algorithm for the gcd .) And max(ab, b) < max(a, b). By our induction hypothesis, let c be so that f (c) = ab and f (1 + c) = b. Then f (2 + 4c) = a and f (3 + 4c) = b. In case 1 < a < b, we consider ba and b. Again, gcd(a, ba) = 1, and max(ba, a) < max(a, b). By our induction hypothesis, let c be so that f (c) = a and f (1 +c) = b -a. Then f (1 +4c) = a and f (2 +4c) = b. ⊣

Lemma 2

 2 Let a, b, and c ∈ Z. 1. If a + b = c, then E ⊢ a + b = c, and similarly for × and -.2. E ⊢ a = ⌊a.

3 .

 3 If f (a) = b, then E ⊢ f(a) = b, and similarly for h and h. Proof Part (

2 .Lemma 5

 25 If ⌊g(a)⌋ = b, then E ⊢ ⌊ga = b, and if ⌊-g(a)⌋ = b, then E ⊢ ⌊-ga = b.Proof The first part is an easy calculation using Lemma 3, and the second is an induction on |a| using the first and Lemma 2(3).⊣ Let a, b, and c ∈ Z. 1. If g(a) = g(b), then E ⊢ g(a) = g(b).

2 .

 2 If g(a) = b, then E ⊢ g(a) = b.

3 .

 3 If g(a) + g(b) = g(c), then E ⊢ g(a) + g(b) = g(c).

4 .

 4 If g(a)g(b) = g(c), then E ⊢ g(a) + (-g(b)) = g(c).

5 .

 5 If g(a) × g(b) = g(c), then E ⊢ g(a) × g(b) = g(c). Proof For part (1), note that since f (a) and f (1 + a) are relatively prime, and similarly for f (b) and f (1 + b), we have f (a) = f (b) and f (1 + a) = f (1 + b). Now our result follows easily from Lemma 3. Part (2) is similar. If g(a) is the natural number b, then f (a) = b and f (1 + a) = 1. Then since E ⊢ b × f(1 + a) = f(a), we see that E ⊢ g(a) = b.


Jessica H Fong
email: jfong@cs.princeton.edu

Martin Strauss
email: mstrauss@research.att.com

An Approximate L p -Difference Algorithm for Massive Data Streams

Several recent papers have shown how to approximate the difference ∑ i |a ib i | or ∑ |a ib i | 2 between two functions, when the function values a i and b i are given in a data stream, and their order is chosen by an adversary. These algorithms use little space (much less than would be needed to store the entire stream) and little time to process each item in the stream. They approximate with small relative error. Using different techniques, we show how to approximate the L p -difference ∑ i |a ib i | p for any rational-valued p ∈ (0, 2], with comparable efficiency and error. We also show how to approximate ∑ i |a ib i | p for larger values of p but with a worse error guarantee. Our results fill in gaps left by recent work, by providing an algorithm that is precisely tunable for the application at hand. These results can be used to assess the difference between two chronologically or physically separated massive data sets, making one quick pass over each data set, without buffering the data or requiring the data source to pause. For example, one can use our techniques to judge whether the traffic on two remote network routers are similar without requiring either router to transmit a copy of its traffic. A web search engine could use such algorithms to construct a library of small "sketches," one for each distinct page on the web; one can approximate the extent to which new web pages duplicate old ones by comparing the sketches of the web pages. Such techniques will become increasingly important as the enormous scale, distributional nature, and one-pass processing requirements of data sets become more commonplace.

Introduction

[Some of the following material is excerpted from [START_REF] Feigenbaum | An Approximate L 1 -Difference Algorithm for Massive Data Streams[END_REF], with the authors' permission. Readers familiar with [START_REF] Feigenbaum | An Approximate L 1 -Difference Algorithm for Massive Data Streams[END_REF] may skip to Section 1. 1.] Massive data sets are becoming more and more important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network operations, raw data typically arrive in streams, and decisions must be made by algorithms that make one pass over each stream, throw much of the raw data away, and produce "synopses" or "sketches" for further processing. Moreover, network-generated massive data sets are often distributed. Several different, physically separated network elements may receive or generate data streams that, together, comprise one logical data set. To be of use in operations, the streams must be analyzed locally and their synopses sent to a central operations facility. The enormous scale, distributed nature, and one-pass processing requirement on the data sets of interest must be addressed with new algorithmic techniques.

In [AMS96, KOR98, AGMS99, FKSV99], the authors presented a new technique: a space-efficient, one-pass algorithm for approximating the

L 1 difference ∑ i |a i -b i | or L 2 difference ‡ ∑ i |a i -b i | 2 1/2
between two functions, when the function values a i and b i are given as data streams, and their order is chosen by an adversary. Here we continue that work by showing how to compute ∑ i |a ib i | p for any rational-valued p ∈ (0, 2]. These algorithms fit naturally into a toolkit for Internet-traffic monitoring. For example, Cisco routers can now be instrumented with the NetFlow feature [CN98]. As packets travel through the router, the NetFlow software produces summary statistics on each flow. § Three of the fields in the flow records are source IP-address, destination IP-address, and total number of bytes of data in the flow. At the end of a day (or a week, or an hour, depending on what the appropriate monitoring interval is and how much local storage is available), the router (or, more accurately, a computer that has been "hooked up" to the router for monitoring purposes) can assemble a set of values (x, f t (x)), where x is a source-destination pair, and f t (x) is the total number of bytes sent from the source to the destination during a time interval t. The L p difference between two such functions assembled during different intervals or at different routers is a good indication of the extent to which traffic patterns differ.

Our algorithm allows the routers and a central control and storage facility to compute L p differences efficiently under a variety of constraints. First, a router may want the L p difference between f t and f t+1 . The router can store a small "sketch" of f t , throw out all other information about f t , and still be able to approximate f tf t+1 p from the sketch of f t and (a sketch of) f t+1 .

The functions f (i)

t assembled at each of several remote routers R i at time t may be sent to a central tape-storage facility C. As the data are written to tape, C may want to compute the L p difference between f

(1) t and f

(2) t , but this computation presents several challenges. First, each router R i should transmit its statistical data when R i 's load is low and the R i -C paths have extra capacity; therefore, the data may arrive at C from the R i 's in an arbitrarily interleaved manner. Also, typically, the x's for which f (x) = 0 constitute a small fraction of all x's; thus, R i should only transmit (x, f

(i) t (x)) when f (i) t (x) = 0.
The set of transmitted x's is not predictable by C. Finally, because of the huge size of these streams, ¶ the central facility will not want to buffer them in the course of writing them to tape (and cannot read from one part of the tape while writing to another), and telling R i to pause is not always possible. Nevertheless, our algorithm supports approximating the L p difference between f

(1) t and f

(2) t at C, because it requires little workspace, requires little time to process each incoming item, and can process in one pass all the values of both functions {(x, f

(1)

t (x))} ∪ {(x, f
(2) t (x))} in any permutation. Our L p -difference algorithm achieves the following performance for rational p ∈ (0, 2]: Consider two data streams of length at most n, each representing the non-zero points on the graph of an integer-valued function on a domain of size n. Assume that the maximum value of either function on this domain is M. Then a one-pass streaming algorithm can compute with probability 1 -δ an approximation A to the L p -difference B of the two functions, such that |A -B| ≤ εB, using total space and per-item processing time (log(M) log(n) log(1/δ)/ε) O(1) . The input streams may be interleaved in an arbitrary (adversarial) order.

L p -Differences for p other than 1 or 2

While the L 1 -and L 2 -differences are most commonly used, the L p -differences for other p, say the L 1.5difference, provide additional information. In particular, there are a i , b i , a ′ i , and b ′ i such that

∑ |a i -b i | = ∑ |a ′ i -b ′ i | and ∑ |a i -b i | 2 = ∑ |a ′ i -b ′ i | 2 but ∑ |a i -b i | 1.5 and ∑ |a ′ i -b ′ i | 1.5 are different. As p increases, the measure ∑ |a i -b i | p attributes more significance to a large individual difference |a i 0 -b i 0 |,
while reducing the significance of a large number of differences, |{i : |a ib i | > 0}|. By showing how to compute the L p difference for varing p, we provide an approximate difference algorithm that is precisely tunable for the application at hand.

We also give an algorithm for p > 2, though with an error guarantee somewhat worse than the guarantee available for the p ≤ 2 cases. Still, that result is a randomized algorithm with the correct mean, which is an advantage in some situtations.

Organization

The rest of this paper is organized as follows. In Section 2, we describe precisely our model of computation and its complexity measure. We present our main technical results in Section 3. We discuss the relationship of our algorithm to other recent work and present some open problems, in Section 4.

Proofs of lemmas end with a and other proofs and definitions terminate with a .

Background

We describe the details of our algorithm in terms of the streaming model used in [START_REF] Feigenbaum | An Approximate L 1 -Difference Algorithm for Massive Data Streams[END_REF]. This model is closely related to that of [START_REF] Henzinger | Computing on data streams[END_REF].

Model of Computation

A data stream is a sequence of data items σ 1 , σ 2 , . . . , σ n such that, on each pass through the stream, the items are read once in increasing order of their indices. We assume the items σ i come from a set of size M, so that each σ i has size log M. In the computational model, we assume that the input is one or more data streams. We focus on two resources-the workspace required in words and the time to process an item in the stream, but disregard pre-and post-processing time.

It is immediate to adapt our algorithm to the sketch model of [START_REF] Feigenbaum | An Approximate L 1 -Difference Algorithm for Massive Data Streams[END_REF][START_REF] Broder | Min-wise independent permutations[END_REF]. The latter used sketches to check whether two documents are nearly duplicates. A sketch can also be regarded as a synopsis data structure [START_REF] Gibbons | Synopsis Data Structures for Massive Data Sets[END_REF].

Medians and Means of Unbiased Estimators

We now recall a general technique of randomized approximation schemes.

Lemma 1 Let X be a real-valued random variable such that, for some c, E[X 2 ] ≤ c • var[X]. Then, for any ε, δ > 0, there exists a random variable Z such that Pr

(|Z -E[X]| ≥ εE[X]) ≤ δ. Furthermore, Z is a function of O(log(1/δ)/ε 2 ) independent samples of X.
Proof. Let Y be the average of 8c/ε 2 independent copies of X.

Then E[Y ] = E[X] and var[Y ] ≤ ε 2 E 2 [X]/8. By the Chebychev inequality, Pr(|Y -E[X]| > εE[X]) ≤ var(Y ) ε 2 E 2 [X] ≤ 1 8 . Let Z be the median of 4 log(1/δ) independent copies of Y . Then |Z -E[X]| ≥ εE[X] iff for at least half the Y i 's, |Y i -E[X]| ≥ εE[X].
Since, for each i, this happens only with probability 1/8, the Chernoff inequality implies that Pr(

|Z -E[X]| ≥ εE[X]) ≤ δ.

The Algorithm

In this section we prove our main theorem:

Theorem 2 For rational p ∈ (0, 2], the L p -difference of two functions a i and b i can be computed in time and space (log(n) log(M) log(1/δ)/ε) O(1) , where (1) the input is a data stream of values a i or b i , 0 ≤ i < n, from a set of size M, (2) one can output a random variable X such that |Xf | < ε f with probability at least 1 -δ, and (3) computation of X can be done by making a single pass over the data.

Intuition

We first give an intuitive overview of the algorithm. Our goal is to approximate

L p = ∑ |a i -b i | p ,
where the values a i , b i ∈ [0, M) are presented in a stream in any order, and the index i runs up to n. We are given tolerance ε and maximum error probability δ.

The input is a stream consisting of tuples of the form (i, c, θ), where 0 ≤ i < n, 0 ≤ c < M, and θ ∈ {±1}. The tuple (i, c, θ) denotes the data item a i with value c if θ = +1 and indicates that b i = c if θ = -1. We wish to output a random variable Z such that Pr(|Z -L p | > εL p ) < δ, using total space and per-item processing time polynomial in (log(n) log(M) log(1/δ)/ε).

In the next few sections, we will construct a randomized function f (r, x) such that

E ( f (r, b) -f (r, a)) 2 ≈ |b -a| p . (1)
In a first reading of the algorithm below, the reader may assume f to be a deterministic function with

( f (b) -f (a)) 2 = |b -a| p .
The algorithm proceeds as in Figure 1.

To see how the algorithm works, first focus on single values for k and ℓ. Let Z be an abbreviation for

Z k,ℓ = ∑ i σ i ( f (a i ) -f (b i )).
We separate the diagonal and off-diagonal terms of Z 2 to simplify,

E Z 2 = E ∑ i σ 2 i ( f (a i ) -f (b i )) 2 + ∑ i =i ′ ±σ i σ i ′ ( f (a i ) -f (b i ))( f (a i ′ ) -f (b i ′ )) ≈ E ∑ i σ 2 i |a i -b i | p + ∑ i =i ′ ±σ i σ i ′ ( f (a i ) -f (b i ))( f (a i ′ ) -f (b i ′ )) (2) = E ∑ i |a i -b i | p .
Initialize: For k = 1 to O(log(1/δ)) do For ℓ = 1 to O(1/ε 2 ) do Z k,ℓ = 0
pick sample points for a family {σ i } of n 4-wise independent ±1-valued random variables and a family { r i } of n 4-wise independent random variables (described further below) Stream processing:

For each tuple

(i, c, θ) in the input stream do For k = 1 to O(log(1/δ)) do For ℓ = 1 to O(1/ε 2 ) do Z k,ℓ += σ i θ f r i (c) Report: Output median k avg ℓ Z 2 k,ℓ .
The result follows since

σ 2 i ≡ 1, E[σ i ] = 0, and σ i and σ i ′ are independent for i = i ′ . Similarly, var(Z 2 ) ≤ O(E 2 [Z 2 ]
). We can apply Lemma 1 and take a median of means of independent copies of Z 2 to get the desired result

∑ |a i -b i | p .

Construction of f

Overview

Construction of f is the main technical content of this paper. We construct a function f : Z → Z such that

E ( f (b) -f (a)) 2 = (1 ± ε)|b -a| p .
We put f r (x) = cφ( r)d(T r (0), T r (x)) (rounding appropriately from reals to integers), defining the component functions as follows. When the choice of r is clear, we drop the subscript. We will come back to f in the overview in the next subsection. The function d(a, b) satisfies

• |d(a, b)| ∈ O(|b -a| p/2
) for all a and b,

• |d(a, b)| ∈ Ω(|b -a| p/2
) for a significant fraction of a and b, and

• d(c, b) -d(c, a) = d(a, b) for all c.
The family {T r } of transformations on the reals, with corresponding inverse scale factors φ( r) are such that:

• the transformation is an approximate isometry, i.e., |a -b| p ≈ c 2 φ 2 ( r)|T r (b) -T r (a)| p , and,

• the distribution on φ( r)d(T r (a), T r (b))/|b -a| p/2 is approximately constant, independent of a and b.

Due to the above properties, our function, acting on parameters a and b, is tightly bounded near |b -a| p . We compute an upper bound of

E r ( f (b) -f (a)) 2 = E r c 2 φ 2 ( r)(d(T r (0), T r (a)) -d(T r (0), T r (b))) 2 = E r c 2 φ 2 ( r)(d(T r (a), T r (b))) 2
(3)

∈ O E r c 2 φ 2 ( r)|T r (a) -T r (b)| p ≈ O(|a -b| p ). Because |d(α, β)| ∈ Ω |β -α| p/2
for a significant fraction of α, β (according to the distribution (α, β) = (T r (a), T r (b))), the Markov inequality gives

E r d(T r (a), T r (b)) 2 ≥ Ω (|T r (a) -T r (b)| p ) .
We get the lower bound similarly as above.

It follows that E r ( f (b) -f (a)) 2 ∈ Θ (|b -a| p ).
We then show that the distribution on φ

( r)d(T r (a), T r (b))/|b -a| p/2 is approximately independent of a and b, thus E r ( f (b) -f (a)) 2 ≈ c ′ (1 ± ε)|b -a| p ,
for c ′ independent of a and b. By choosing c appropriately, we can arrange that c ′ = 1. Finally, we address the issue of precision.

We now proceed with a detailed construction of f .

Construction of d

The function d(a, b) takes the form d(a, b) = ∑ a≤ j<b π j , where π j is a ±1-valued function of j, related to a function described in [START_REF] Feigenbaum | An Approximate L 1 -Difference Algorithm for Massive Data Streams[END_REF]. This function is selected to fulfil the properties listed in the overview. First, find integers u, v such that log(v-u) log(v+u) = p/2, and, for technical reasons, vu ≥ 17 and u ≥ 2. To do this, find integers α > 1 and β > 1 with p/2 = α/β (by hypothesis, a rational number). Put

v = 2 β-1 + 2 α-1 and u = 2 β-1 -2 α-1 ; thus log(v-u) log(v+u) = p/2. If v -u < 17 or u = 1, then (repeatedly, if necessary) replace v by v 2 + u 2 and replace u by 2uv. Observe that log(v 2 +u 2 -2uv) log(v 2 +u 2 +2uv) = log(v-u) log(v+u) and the new value v 2 + u 2 -2uv = (v -u) 2 is greater than the old value v -u. Also note that (v + u) p/2 = v -u.
Now, we define a sequence π as a string of +1's and -1's, as follows. Let π = lim i→∞ π (i) where π (i) is defined recursively for i ≥ 1 as

π (1) = (+1) u (-1) v (4) π (i+1) = π u (i) π v (i) , (5)
and π (i) denotes π (i) with all +1's replaced by -1's and all -1's replaced by +1's. Note that π (i) is a prefix of π (i+1) . For example, a graph of π with u = 1 and v = 3 is given in Figure 2 (Figure 2 also describes sets S s,t , to be defined later).

Let π j (differentiate this from π ( j) ) denote the j'th symbol of π. Now d(a, b) = ∑ b-1 j=a π j is the discrepancy between +1's and -1's in the interval [a, b). The self-similarity of π allows the value of d, applied on random transformations of the parameters a and b to have the desired expected value. Note that d and π depend on u and v, which, in turn, depend on p. We only consider one set of values for u, v at a time and drop them from the notation.

Adding randomness

We now define the transformation T r () and the reconstruction φ( r).

Definition 3 Set u, v : integers such that log(v -u) log(v + u) = p/2 c 1 = min 1 2 , 3v 4(v -u) c 2 = 3u + 3v η = log(v -6/8) -log(v -10/8) log(v + u) • 5/8 -3/8 v + u N 1 = log(8)/ log(u + v) N 2 = N 1 + 8c 2 log(M)/c 1 ηε N 3 = least power of (u + v) such that N 3 ≥ (u + v)MN 2 .
These values are motivated by several subsequent proofs, particularly those for Lemma 12 and (average); we state them now for clarity. Let r be (u + v) s , where s is chosen uniformly at random from the real interval [N 1 , N 2 ]. Let r ′ be an integer chosen uniformly at random from [0, N 3 ). Put T r (a) = ra + r ′ and put φ( r) = r -p/2 . Let d(a, b) denote φ( r)d(T r (a), T r (b)), i.e., d acting in the transformed domain, rounding the arguments of d appropriately from reals to integers (we will specify the rounding precisely below).

Expectation of d(a, b)

We now prove that |d(a, b)| has tight upper and lower bounds. (More precisely, we show the lower bound for d as defined above.) This utilizes a succession of properties about π, d, T r , and φ( r). Some of the following assume that vu ≥ 17. The constants γ 0 , γ 1 , γ 2 below may depend on p, M, and ε, but are bounded uniformly in M and ε. The dependence of γ 0 , γ 1 , γ 2 on p, M, and ε is hard to find analytically; in Section 4.3 we discuss in more detail a method for determining the gammas.

d((u + v)a, (u + v)b) = -(v -u)d(a, b). (homogeneity) For all r, all a ≤ b < (u + v) r and all x, |d(a, b)| = |d(a + x(u + v) r , b + x(u + v) r )|.
(periodicity)

For some c 2 , |d(a, b)| ≤ c 2 (b -a) p/2 . (upper bound)
For some c 1 > 0 and some η > 0, Pr

r d(a, b) ≥ c 1 |b -a| p/2 > η.
(averaged lower bound)

For some γ 0 > 0, E r d(a, b) = γ 0 |(b -a)| p/2 (1 ± ε).
For some

γ 1 > 0, E r d2 (a, b) = γ 1 |(b -a)| p (1 ± ε).
For some

γ 2 > 0, E r d4 (a, b) = γ 2 |(b -a)| 2p (1 ± ε).        (average) Claim 4
The sequence π (i+1) can be obtained by starting with π (i) and replacing each +1 with π (1) and each -1 with π (1) .

Proof. Consider a top-down rather than a bottom-up recursive definition of π.

Proof. [(homogeneity) and (periodicity)] The homogeneity and periodicity properties are immediate from the definition of π and from Claim 4.

Proof. [(upper bound)]

Next, consider the upper bound property. Note that (homogeneity) implies (upper bound) infinitely often, i.e., for bounded a and b, we have

|d(a(u + v) s , b(u + v) s )| = (v -u) s d(a, b) = (v + u) sp/2 d(a, b) (6) = d(a, b) |b -a| p/2 (b(u + v) s -a(u + v) s ) p/2 Intuitively, since d(a, b) ≈ d(a ′ , b ′ ) for a ≈ a ′ and b ≈ b ′ , the result follows.
Formally, assume by induction that, for all a and b with 0 r+1 . Let a ′ be the smallest multiple of (u + v) that is at least a and let b ′ be the largest multiple of (u + v) that is at most b. Then |d(a ′ , b ′ )| ≤ q r (b ′a ′ ) p/2 by homogeneity and by induction. Also,

≤ b -a ≤ (u + v) r , we have |d(a, b)| ≤ q r |b -a| p/2 . Now assume that (u + v) r < b -a ≤ (u + v)
|d(a, b) -d(a ′ , b ′ )| ≤ 2(u + v). Thus |d(a, b)| ≤ q r (b ′ -a ′ ) p/2 + 2(u + v). Let q r+1 be the maximum over (u + v) r < b -a ≤ (u + v) r+1 of |d(a, b)|/|b -a| p/2 ; then q r+1 ≤ q r + 2(u + v)|b -a| -p/2 ≤ q r + 2(u + v)(u + v) -rp/2 (7) = q r + 2(u + v)(v -u) -r Similarly, q r ≤ q r-1 + 2(u + v)(v -u) -(r-1) .
S 1,0 S 1,1 S 1,2
Unwinding the recursion, we have

q r+1 = q 1 + 2(u + v) (v -u) -r + (v -u) -(r-1) + • • • + (v -u) -1 ≤ q 1 + 2(u + v), ( 8
)
where q 1 is such that d(a, b) ≤ q 1 |b -a| p/2 for all 0 < ba ≤ v + u. Since, for these a and b, we have d(a, b) ≤ v + u and |b -a| p/2 ≥ 1, we can take q 1 = v + u, and so we can take c 2 = 3u + 3v.

Proof. [(averaged lower bound)]

The proof consists of two lemmas. We identify a set S of (a, b) values. We then show in Lemma 6 that |d(a, b)| is large on S and we show in Lemma 7 that the set S itself is big. The result follows.

Definition 5 Fix u and v. We define a set S of (a, b) values as follows. For each integer s and t, let S s,t consist of the pairs (a, b) such that

t(u + v) s+1 + u(u + v) s ≤ a < t(u + v) s+1 + (u + 1)(u + v) s t(u + v) s+1 + (u + v -1)(u + v) s < b ≤ (t + 1)(u + v) s+1
Let S be the (disjoint) union of all S s,t . Geometrically speaking, s adjusts the size of the set and t linearly translates the range of the set. Note that S 0,0 is the singleton (u, u + v), i.e., the endpoints of the interval of v -1's (the interval of maximum discrepancy in π (1) ). Elements of S s,0 are close to analogs of S 0,0 = {(u, u + v)}, scaled-up (by (u + v) s ). Elements of S s,t are analogs of elements of S s,0 , translated (by t(u + v) s+1 ).

Figure 2 shows the case of u = 1 and v = 3. Here,

π (2) = +1-1-1-1 -1+1+1+1 -1+1+1+1 -1+1+1+1.
The component S 0,2 is the singleton {(9, 12)}. The component S 1,0 is {4, 5, 6, 7} × {13, 14, 15, 16}. The element (a, b) = (5, 14) ∈ S 1,0 leads to d(5, 14) which is the sum of the 9 symbols

+1+1+1 -1+1+1+1 -1+1.
It has a relatively high discrepancy.

Lemma 6 For some constant c 1 , for each (a, b) ∈ S, we have

|d(a, b)| ≥ c 1 |b -a| p/2 .
Proof. We show the lemma for (a, b) ∈ S s,0 . The general result follows immediately from (periodicity).

One can easily show that the lower bound property is satisfied if u = 0. We now assume u > 0.

For each s, we define close to maximal q s such that for all a, b as defined in Definition 5 (i.e. with u(v + u) s ≤ a < (u + 1)(v + u) s and

(v + u -1)(v + u) s < b ≤ (v + u) s+1 ), we have |d(a, b)| ≥ q s (b -a).
(Recall t = 0.) We will consider q s for s = 0, show that q s-1q s drops exponentially in s, then bound the sum of |q s-1q s |. We consider two cases, depending on whether or not u ≤ v/2. s+1 . Define a ′ to be the greatest multiple of (v + u) that is at most a and define b ′ to be the smallest multiple of (v + u) that is at least b.

First, suppose u ≤ v/2. Note that π (1) = u +1 + 1 • • • + 1 v -1 -1 • • • -1. If s = 0, we have a = u and b = v + u. The discrepancy d(a, b) consists of the sum of v copies of -1, so |d(a, b)| = v = b -a, and we want v ≥ q 0 v p/2 . Since v ≥ v p/2 , we can put q 0 = 1. Consider s ≥ 1. Suppose a, b are such that u(v + u) s ≤ a < (u + 1)(v + u) s and (v + u -1)(v + u) s < b ≤ (v + u)
Using the homogeneity property and induction,

|d(a ′ , b ′ )| = (v -u) d a ′ v + u , b ′ v + u ≥ q s-1 (v -u) b ′ -a ′ v + u p/2 (11) ≥ q s-1 (b ′ -a ′ ) p/2 ≥ q s-1 (b -a) p/2 . It follows that |d(a, b)| ≥ q s-1 (b -a) p/2 -2v.
Therefore we want to define q s such that |d(a, b)| ≥ q s-1 (ba) p/2 -2v ≥ q s (ba) p/2 , i.e., such that

q s ≤ q s-1 -2v(b -a) -p/2 . ( 12
) Note that v -u ≥ 17 implies (v -2) ≥ v+u 2 and u ≤ v/2 implies 2(v -u) ≥ v. Also, note that b -a ≥ (v -2)(u + v) s . We have q s-1 -2v(b -a) -p/2 ≥ q s-1 -2v ((v -2)(v + u) s ) -p/2 ≥ q s-1 -2v (v + u) s+1 /2 -p/2 ≥ q s-1 -4v(v -u) -(s+1) (13) ≥ q s-1 -8(v -u)(v -u) -(s+1) = q s-1 -8(v -u) -s .
Thus it suffices to make q s ≤ q s-1 -8(vu) -s , for s ≥ 1. Since

8 ∑ s≥1 (v -u) -s ≤ 8 ∑ s≥1
we can make all q s = q 0 -1/2 = 1/2. Now, assume u ≥ v/2. When s = 0, so that a = u and b

= v + u, then d(a, b) = -v and we need |d(a, b)| ≥ q 0 v p/2 . Since v v p/2 ≥ v (v + u) p/2 = v v -u , (15)
We can put q 0 = v v-u . Now consider s ≥ 1 when u ≥ v/2. As in (12), we want to define q s such that

q s ≤ q s-1 -2v(b -a) -p/2 . Since b -a ≥ (v -2)(v + u) s ≥ 1/2(v + u) s+1 , we have (b -a) -p/2 ≤ 2 p/2 (v + u) -(p/2)(s+1) ≤ 2(v -u) -(s+1) . Thus q s-1 -2v(b -a) -p/2 ≥ q s-1 -4v(v -u) -(s+1) ,
and it suffices to make

q s ≤ q s-1 -4v(v -u) -(s+1) .
Unwinding the recursion, this becomes

q s ≤ q 0 -4v ∞ ∑ s=2 (v -u) -s .
We get

q 0 -4v ∞ ∑ s=2 (v -u) -s = v v -u -4v ∞ ∑ s=2 (v -u) -s = v v -u - 4v (v -u) 2 1 1 -1/(v -u) = v v -u 1 - 4 (v -u) 1 1 -1/(v -u) (16) = v v -u 1 - 4 v -u -1 ≥ 3v 4(v -u) ,
using the fact that vu ≥ 17 in the last line. It suffices to put q s = 3v 4(v-u) . We can make c 1 in (averaged lower bound) be the minimum of 1/2 and 3v 4(v-u) . We now return to the proof of (averaged lower bound) by showing that S has positive probability.

Lemma 7 Let a, b < M be arbitrary. Then for any u, v there exists η > 0 such that Pr (T r (a), T r (b)) ∈ S ≥ η.

Proof.

With probability log(v-6/8)-log(v-10/8) log(v+u)

, we have

log(v -10/8) ≤ log(r(b -a)) mod log(v + u) < log(v -6/8),
i.e., for some integer s,

(v -10/8)(u + v) s ≤ r(b -a) < (v -6/8)(u + v) s . ( 17
)
Find the integer t with t(u + v) s+1 ≤ ra + r ′ < (t + 1)(u + v) s+1 . With probability 5/8-3/8 v+u ,

t(u + v) s+1 + (u + 3/8)(u + v) s ≤ ra + r ′ < t(u + v) s+1 + (u + 5/8)(u + v) s . ( 18
)
If both ( 17) and ( 18) hold, then the following also holds:

t(u + v) s+1 + (v + u -7/8)(u + v) s ≤ rb + r ′ < t(u + v) s+1 + (v + u -1/8)(u + v) s .
It follows that

t(u + v) s+1 + (u + 3/8)(u + v) s ≤ ra + r ′ ≤ t(u + v) s+1 + (u + 5/8)(u + v) s t(u + v) s+1 + (v + u -7/8)(u + v) s ≤ rb + r ′ ≤ t(u + v) s+1 + (v + u -1/8)(u + v) s , (19)
whence

(T r (a), T r (b)) ∈ S s,t ⊆ S, with positive probability. If N 1 ≥ log(8)/ log(u + v), then (u + v) s /8 ≥ 1.
It follows that (T r (a) ± 1, T r (b) ± 1) ∈ S s,t ⊆ S with positive probability. (The ±1's allow us to round T r () to a nearby integer in an arbitrary way.)

Let η > 0 denote the probability that ra + r ′ and rb + r ′ are as above. (This concludes the proof of (averaged lower bound).)

Proof. [(average)]

We show E d(a 1 , b 1 ) ≈ γ 0 (b 1a 1 ) p/2 . The other conditions are similar. From property (upper bound), we conclude that

E d(a 1 , b 1 ) ≤ c 2 (b 1 -a 1 ) p/2 . ( 20
)
Similarly, from property (averaged lower bound) and the Markov inequality, we conclude

E d(a 1 , b 1 ) ≥ ηc 1 (b 1 -a 1 ) p/2 . ( 21
)
Equations 20 and 21 indicate that some multiple of E[ d(a, b)] gives a c 2 /(ηc 1 )-factor approximation to |b -a| p/2 . The equations leave open the possibility, however, that

E d(a 1 , b 1 ) = ηc 1 (b 1 -a 1 ) p/2 while E d(a 2 , b 2 ) = c 2 (b 2 -a 2 ) p/2 ,
where c 2 /(ηc 1 ) > (1 + ε). If that were the case, no multiple of E d(a 2 , b 2 ) would be a (1 ± ε)-factor approximation. Fortunately, as we show, a (1 ± ε)-approximation does result from our algorithm. Our proof proceeds by showing that

d(a 1 , b 1 ) |b 1 -a 1 | p/2 and d(a 2 , b 2 ) |b 2 -a 2 | p/2
have approximately the same distribution. It follows that these distributions have approximately the same expectancy, γ 0 , whence it follows that, for this universal γ 0 ,

E d(a, b) ≈ γ 0 (b -a) p/2
for all a and b.

Note that, if a = b, then d(a, b) = d(a, b) = |b -a| p/2 = 0, identically. Thus, in approximating ∑ i |b i - a i | p by ∑ i d(a i , b i ),
we may restrict attention only to i such that a i = b i .

Definition 8

The randomized rounding [x] ρ of a real number x by a (random) real ρ ∈ [0, 1] is defined by

[x] ρ = ⌈x⌉ , x ≥ ρ + ⌊x⌋ ⌊x⌋ , otherwise Note that E([x] ρ ) = x.
Lemma 9 For any real numbers a ≤ b, the distribution on [ba] ρ is the same as the distribution on

[b] ρ ′ -[a] ρ ′ .
Note that it is not the case that, for all a, b, ρ,

[b -a] ρ = [b] ρ -[a] ρ .
Proof. (Tedious, straightforward, omitted.) Note that the expected values of [ba] ρ and [b] ρ ′ -[a] ρ ′ are the same. One can show that these random variables take on the same two values, ⌊b -a⌋ and ⌈b -a⌉. The result follows.

We now clarify the definition of d and indicate how to do rounding.

Definition 10 Let r = (r, r ′ , ρ). Define d( r, a, b) by r -p/2 d([ra] ρ + r ′ , [rb] ρ + r ′ ).
Lemma 11 For all a < b and for all i

∈ [M(u + v) N 1 , (u + v) N 2 ], the probability Pr r,ρ ([rb] ρ -[ra] ρ = i)
does not depend on a or b.

Proof. By Lemma 9, for each fixed r,

Pr ρ ([rb] ρ -[ra] ρ = i) = Pr ρ ([r(b -a)] ρ = i). It follows that Pr r,ρ ([rb] ρ -[ra] ρ = i) = Pr r,ρ ([r(b -a)] ρ = i).
Next, for each fixed ρ,

Pr r ([r(b -a)] ρ = i) = Pr r (i -1 + ρ ≤ r(b -a) < i + ρ) = Pr r log i -1 + ρ b -a ≤ log(r) < log i + ρ b -a (22) = log i + ρ i -1 + ρ . Thus Pr r,ρ ([rb] ρ -[ra] ρ = i) = Pr r,ρ ([r(b -a)] ρ = i) = 1 0 log i + ρ i -1 + ρ dρ,
and, in any case, this probability does not depend on a or b.

Note that if i ∈ [M(u + v) N 1 , (u + v) N 2 ], then Pr ([rb] ρ -[ra] ρ = i) > 0.
Lemma 12 For all distinct a and b, the probability

Pr [rb] ρ -[ra] ρ ∈ [M(u + v) N 1 , (u + v) N 2 ] is at most 2 log(M)/(N 2 -N 1 ).
Proof. Immediate from the definition of r and the fact that 0 ≤ ba ≤ M.

Put N 2 -N 1 = 8c 2 log(M)/(c 1 ηε). Then Pr([rb] ρ -[ra] ρ ∈ [M(u + v) N 1 , (u + v) N 2 ]) ≤ c 1 ηε/(4c 2 ). Lemma 13 For i ∈ [M(u + v) N 1 , (u + v) N 2 ], given that [rb] ρ -[ra] ρ = i, the conditional expectation of | d( r, a, b)| |b -a| p/2 = φ( r)d([ra] ρ + r ′ , [rb] ρ + r ′ ) |b -a| p/2
is independent of a and b.

Proof. Follows from (periodicity), using the fact that u ≥ 2.

We return to the proof of (average

). Fix a 2 , b 2 , a 1 , b 1 , such that E d( r, a, b)/|b -a| p/2 is minimized at (a, b) = (a 1 , b 1 ) and maximized at (a 2 , b 2 ). Write E d( r, a, b)/|b -a| p/2 = ∑ i E d( r, a, b)/|b -a| p/2 [rb] ρ -[ra] ρ = i • Pr([rb] ρ -[ra] ρ = i).
Using Lemmas 11, 12, and 13, we have

E d( r, a 2 , b 2 )/|b 2 -a 2 | p/2 -E d( r, a 1 , b 1 )/|b 1 -a 1 | p/2 = ∑ i Pr [rb 2 ] ρ -[ra 2 ] ρ = i E d( r, a 2 , b 2 ) [rb 2 ] ρ -[ra 2 ] ρ = i /|a 2 -b 2 | p/2 -∑ i Pr [rb 1 ] ρ -[ra 1 ] ρ = i E d( r, a 1 , b 1 ) [rb 1 ] ρ -[ra 1 ] ρ = i /|a 1 -b 1 | p/2 ≤ ∑ i∈[M(u+v) N 1 ,(u+v) N 2 ] Pr [rb 2 ] ρ -[ra 2 ] ρ = i E d( r, a 2 , b 2 ) [rb 2 ] ρ -[ra 2 ] ρ = i |a 2 -b 2 | p/2 - E d( r, a 1 , b 1 ) [rb 1 ] ρ -[ra 1 ] ρ = i |a 1 -b 1 | p/2 (23) + ∑ i ∈[M(u+v) N 1 ,(u+v) N 2 ] Pr [rb 2 ] ρ -[ra 2 ] ρ = i + Pr [rb 1 ] ρ -[ra 1 ] ρ = i • E d( r, a 2 , b 2 ) [rb 2 ] ρ -[ra 2 ] ρ = i |a 2 -b 2 | p/2 + E d( r, a 1 , b 1 ) [rb 1 ] ρ -[ra 1 ] ρ = i |a 1 -b 1 | p/2 ≤ 2 max r d( r, a 2 , b 2 )/|a 2 -b 2 | p/2 • ∑ i ∈[M(u+v) N 1 ,(u+v) N 2 ] Pr [rb 2 ] ρ -[ra 2 ] ρ = i + Pr [rb 1 ] ρ -[ra 1 ] ρ = i ≤ 2c 2 • (c 1 ηε/(4c 2 )) ≤ εE d( r, a 1 , b 1 )/|b 1 -a 1 | p/2 .
It follows that

E d( r, a 2 , b 2 )/|b 2 -a 2 | p/2 = (1 ± ε)E d( r, a 1 , b 1 )/|b 1 -a 1 | p/2 , (24)
so that for γ 0 equal to the (approximate) common value (24), for all a, b,

E d( r, a, b) = γ 0 |b -a| p/2 (1 ± ε). ( 25
)

Precision

Last, we look at the precision needed to implement our solution. Above, r and ρ were specified as real numbers, but, in practice, they are limited-precision floating point numbers. Let r and ρ denote the floating point equivalents of r and ρ.

Note that the proofs of (upper bound) and Lemma 6 hold for any r and any ρ. The proof of Lemma 7 works provided [ra] ρ = ra ±1 and [rb] ρ = rb±1; this is the case if r -r < O(1/M), i.e., if r has O(log(M)) bits of precision to the right of the radix point.

The proof of (average) requires that Pr [rb 1 ] ρ -[ra 1 ] ρ = i be close to Pr [rb 1 ] ρ -[ra 1 ] ρ = i , in several places-in Lemma 11, in (23) directly, and in (23) buried in the conditional expectation (in the numerator and denominator). It is tedious but straightforward to check that the required number of bits of precision to the right of the radix point is within the overall space bound claimed. To get an approximation of Pr [rb 1 ] ρ -[ra 1 ] ρ = i to within some error ζ, one needs to maintain ρ and r(ba) to within ζ, i.e., maintain r to within ζ/M. This requires log(M) + log(1/ζ) bits of precision to the right of the radix point. The total error in the sum of n terms may be n times as much, so we need to maintain ρ to within Ω(δ/n) and r to within Ω(δ/(Mn)). This requires O(log(M) + log(n) + log(1/δ)) bits of precision to the right of the radix point. Analysis of the expectancy in ( 23) is slightly more involved, but similar.

A completely analogous argument shows that, for k = 2, 4, E[ dk (a, b)]/|b -a| kp/2 is the same, up to the factor (1 ± ε), for all values of a and b.

Top Level Algorithm, Correctness

We now revisit the overall algorithm in detail, thereby proving Theorem 2. Proof.

(of Theorem 2) Put f (x) = γ -1/2 1 d(0, x). ( 26
) Then E ( f (b) -f (a)) 2 = (b -a) p (1 ± ε), (27)
and, similarly,

E ( f (b) -f (a)) 4 = γ 2 γ 2 1 (b -a) 2p (1 ± ε). ( 28
) Thus var ( f (b) -f (a)) 2 ≤ O(E 2 ( f (a) -f (b)) 2 ) (29)
and, similarly, var

( f (a) -f (b)) 4 ≤ O(E 2 ( f (a) -f (b)) 4 ). (30)
Choose families of 4-wise independent random variables {r i }, {r ′ i }, and {ρ i } such that each r, r ′ is distributed as in Definition 3 and ρ i is uniformly distributed in [0, 1]. Also choose a 4-wise independent family {σ i } of ±1-valued random variables. The 4-wise independence is needed below to bound Z 4 , i.e., to bound var(Z 2 ).

Each parallel repetition of the algorithm computes

Z = ∑ i σ i ( f (a i ) -f (b i )). Then E[Z 2 ] = ∑ i σ 2 i ( f (a i ) -f (b i )) 2 + ∑ i =i ′ σ i σ i ′ ( f (a i ) -f (b i ))( f (a i ′ ) -f (b i ′ )) = ∑ i |b i -a i | p (1 ± ε). (31)
Here we used the fact that σ 2 i ≡ 1 and E[σ i σ i ′ ] = 0 for i = i ′ .

• A program P that is guaranteed to compute f correctly only on 3/4 of the inputs to x can be made to compute f correctly, with high probability, on all inputs. That is, P has a self-corrector. (On input x, repeatedly run P on σ(r, x) (using independent r's), then output the majority of (φ(r, P(σ(r, x)))).)

• If Alice has x and Bob can compute f (), then Alice can get Bob to compute f (x) without Bob learning x. (Alice gives Bob σ(r, x), which is uncorrelated with x. She receives f (σ(r, x)) and then computes φ(r, f (σ(r, x))).)

In [START_REF] Feigenbaum | An Information-Theoretic Treatment of Random-Self-Reducibility[END_REF], the authors generalized existing notions of random-self-reducibility to include transformations σ that are slightly correlated with x, but the correlation is tightly bounded. They called such randomself-reductions "leaky."

Our construction involves producing a form of self-corrector for programs for a function, L p , that have a sort of leaky random-self-reduction. The function L p of two streams is random-self-reducible in the sense that

|a i -b i | p = 1 r p (ra i + r ′ ) -(rb i + r ′ ) p ,
where the distribution (ra i + r ′ , rb i + r ′ ) is only weakly dependent on (a i , b i ). We present a deterministic function, d(a, b), that produces a result guaranteed to be correct only up to a large constant factor and only on a set S that is small but has non-negligible probability η; from that, we produce the function, r -p/2 d(T r (a), T r (b)), that produces a correct result with high probability, on all inputs. It is easiest to present our current work without invoking random-self-reducibility machinery. We hope to investigate further the random-self-reducibility issues for massive data streams, for sketches, and for real-valued functions. A theory of random-self-reducibility for streams may make it easier to produce streaming algorithms, to give performance guarantees for heuristics thought to work in many cases, and to characterize functions that have or do not have efficient streaming algorithms.

Determination of Constants

Our function f involves some constant c, such that E[( f (a)f (b)) 2 ] ≈ c|b -a| p , but we do not explicitly provide the constant c. This needs to be investigated further. We give a few comments here.

One can approximate c using a randomized experiment. Due to our fairly tight upper and lower bounds for c, we can, using Lemma 1, estimate c reliably as d(a, b) • |b -a| -p/2 . At worst, this occurs once for each p, M, n, and ε; it is not necessary to do this once for each item or even once for each stream. Furthermore, one can fix generously large M and n and generously small ε to avoid repeating the estimation of c for changes in these values.

In some practical cases, not knowing c may not be a drawback. In practice, as in [START_REF] Broder | Min-wise independent permutations[END_REF], one may use the measure ∑ |a ib i | p to quantify the difference between two web pages, where a i is the number of occurrences of feature i in page A and b i is the number of occurrences of feature i in page B. For example, one may want to keep a list of non-duplicate web pages, where two web pages that are close enough may be deemed to be duplicates. According to this model, there are sociological empirical constants ĉ and p such that web pages with ĉ ∑ |a ib i | p < 1 are considered to be duplicates. To apply this model, one must estimate the parameters ĉ and p by doing sociological experiments, e.g., by asking human subjects whether they think pairs of webpages, with varying measures of ĉ ∑ |a ib i | p for various values of ĉ and p, are or are not duplicates. If one does not know c, one can simply estimate ĉ/c at once by a single sociological experiment.

Non-grouped Input Representation

Often, in practice, one wants to compare a i and b i when the values a i and b i are represented differently. For example, suppose there are two grocery stores, A and B, that sell the same type of items. Each time either store sells an item it sends a record of this to headquarters in an ongoing stream. Suppose item i sells a i times in store A and b i times in store B. Then headquarters is presented with two streams, A and B, such that i appears a i times in A and b i times in B; ∑ |a ib i | p measures the extent to which sales differ in the two stores. Unfortunately, we don't see how to apply our algorithm in this situation. Apparently, in order to use our algorithm, each store would have to aggregate sales data and present a i or b i , rather than present a i or b i non-grouped occurrences of i. The algorithm of [AMS96, AGMS99] solves the p = 2 case in the non-grouped case, but the problem for other p is important and remains open.

We have recently learned of a solution the non-grouped problem [I00]. Note that, in general, a solution A in the non-grouped representation yields a solution in the function-value representation, since, on input a i , an algorithm can simulate A on a i occurrences of i; this simulation takes time exponential in the size of a i to process a i . The proposed solution, however, appears to be of efficiency comparable to ours in the function-value representation, at least in theory, but there may be implementation-related reasons to prefer our algorithm in the grouped case.

Fig. 1 :

 1 Fig. 1: Main algorithm, intuition

  Geometric view of π (continuous polygonal curve) for u = 1 and v = 3. The sets S s,t are indicated by segments with vertical ticks. Each element of S s,t is a pair (α, β), indicated in the diagram by two of the vertical ticks near opposite ends of the interval labeled S s,t . The discrepancy of π is relatively high over intervals with endpoints in S s,t .

	Fig. 2: 0 1 2 3 4 5	6	7	8	9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
	S 0,0	S 0,1			S 0,2	S 0,3	S 0,4	S 0,5	S 0,6	S 0,7	S 0,8	S 0,9	S 0,10	S 0,11

Similarly,

where A and B are nonzero constants. Thus var(Z 2 ) ≤ O(E 2 [Z 2 ]), and we can apply Lemma 1. We conclude that

where X is a median of means of independent copies of Z 2 .

Algorithm in the Sketch Model

We can apply this algorithm to the sketching model, also. Perform O(log(1/d)/ε 2 ) parallel repetitions of the following. Given one function a i , construct the small sketch ∑ i σ i f (a i ). Later, given two sketches

Cost

We first consider the space. The algorithm needs to store seeds for families of random variables and values of the Z's. Each family is of size n, so requires space O(log n) times the number of bits in a single random variable [START_REF] Alon | The Probabilistic Method[END_REF]. The variables r and r ′ each require O(log(M)/ε) bits to the left of the radix point. We need O(log(1/d)/ε 2 ) parallel repetitions of the random variables, so the total space for random variables is (log(M) log(n) log(1/d)/ε) O(1) . The counters Z are bounded by M O(1/ε) , so they also require comparable space.

In [START_REF] Feigenbaum | An Approximate L 1 -Difference Algorithm for Massive Data Streams[END_REF], the authors show that, for M = 2, any randomized algorithm that approximates ∑ |a ib i | to within the factor (1 ±ε) uses more than ω(log α (n)/ε 1-β ) space, for any (large) α and any (small) β > 0. A similar argument applies here, too. Thus the space used by our algorithm is within a constant power of optimal.

We now consider the time to process an item in the stream. To process (i, c, θ), the algorithm first produces values for the random variables, which is quick. The algorithm then needs to compute ∑ C j=0 π j , where C ≤ cM O(1/ε) . From the recursive structure of π, it is clear that this computation requires time at most log O(1) (cM) 1/ε , i.e., polynomial in the size of (i, c, θ).

Top Level Algorithm, 2 ≤ p ≤ 4

We can also approximate

though with worse error. The algorithm should use 8-wise independent random variables instead of 4-wise independent random variables.

. This approximation will have small relative error, i.e., error small compared with the larger term,

and solve for ∑ i |a ib i | p , getting error that is small compared with ∑ i |b ia i | p/2 2 . Thus we cannot, by this method, approximate ∑ i |a ib i | p with small relative error, for p > 2.

We now analyze this error guarantee compared with error guarantees of related work. In previous work, there are three types of error guarantees given. In typical sampling arguments, using resources (log(n) log(M)/ε) O(1) , an error is produced which is bounded by εn or even εMn. The techniques of [START_REF] Broder | Min-wise independent permutations[END_REF] can be used to approximate ∑ |a ib i | when a i , b i ∈ {0, 1}. In this case, the error is bounded by ε ∑ |a i + b i |-already a substantial improvement over error εn and the best possible in the original context of [START_REF] Broder | Min-wise independent permutations[END_REF]. Relative error, i.e., error smaller than ε times the returned value, is better still, and is achievable for p ∈ (0, 2]. Our error guarantee for p > 2 falls between relative error and O(∑ |a i + b i |). In particular, our error in approximating

so our error gets small as the returned value ∑ |a ib i | p gets small-this is not true for an error bound of, say,

Since

one could also approximate

. This will be correct to within the factor ∑ |a ib i | p/2 1/2 . Note that our algorithm is an unbiased estimator, i.e., it has the correct mean-an advantage in some contexts; this is not true of ∑ |a ib i | p/2 3/2 . Furthermore, our algorithm provides a smooth trade-off between guaranteed error and cost, which is not directly possible with the trivial solution.

We hope that, in some applications, our approximation to

We conjecture that one can approximate ∑ |a ib i | p for any p this way. To do this, one needs to show that

with nonzero coefficient. The algorithm may be quite expensive in p.

Discussion

Relationship with Previous Work

We give an approximation algorithm for, among other cases, p = 1 and p = 2. The p = 1 case was first solved in [START_REF] Feigenbaum | An Approximate L 1 -Difference Algorithm for Massive Data Streams[END_REF], using different techniques. Our algorithm is less efficient in time and space, though by no more than a power. The case p = 2 was first solved in [AMS96, AGMS99], and it is easily seen that our algorithm for the case p = 2 coincides with the algorithm of [AMS96, AGMS99].

Our algorithm is similar to [AMS96, FKSV99] at the top level, using the strategy proposed by [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF].

Random-Self-Reducibility

Our proof technique can be regarded as exploitation of a random-self-reduction [F93] of the L p difference. Roughly, a function f (x) is random-self-reducible via (σ, φ) if, for random r, f (x) = φ(r, f (σ(r, x))), where the distribution σ(•, x) does not depend on x. That is, to compute f (x), one can transform x to a random y = σ(r, x), compute f (y), then transform f (y) back to f (x) = φ(r, f (y)). If one can show that a function f is random-self-reducible then one can show

• The function f is hard on average (with respect to σ) if it is hard in worse case. Average-case hard functions are useful in cryptography.