GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

arXiv:1612.06260v2 [math.NT] 28 Jun 2017

ZACHARY CHARLES
Abstract. We present a randomized polynomial-time algorithm to generate an ideal
and its factorization uniformly at random in a given number field. We do this by generating a random integer and its factorization according to the distribution of norms of
ideals at most N in the given number field. Using this randomly generated norm, we can
produce a random factored ideal in the ring of algebraic integers uniformly at random
among ideals with norm up to N , in randomized polynomial time. We also present a
variant of this algorithm for generating random factored ideals in function fields.

1. Introduction
We consider a generalization of the following problem: Given an integer N > 0, generate
an integer in [1, N] uniformly at random, along with its prime factorization, in polynomial
time. Since there are currently no known polyonmial time factorization algorithms, we
cannot simply generate an integer and factor it. Instead, we can generate the prime
factorization uniformly at random.
In his thesis, Bach gave a randomized polynomial time method to uniformly produce
a factored integer in [ N2 , N] [2]. Bach’s method uses only an expected number of log N
primality tests in [1, N] [3]. Since we can test for primality in polynomial time by the
work of Agrawal, Kayal, and Saxena [1], Bach’s algorithm runs in randomized polynomial
time. In 2003, Kalai gave another method for doing this using a conceptually simpler
but slower method. Kalai’s algorithm uses an expected number of O(log(N)2 ) primality
tests [7]. In 2016, Lebowitz-Lockard and Pomerance gave a variant of Kalai’s algorithm
to produce random factored elements on Z[i] with norm at most N [9]. This paper gives
a generalization of these algorithms that will produce random factored ideals in OK for
any number field K. The method given will be polynomial in N and the degree d, where
we fix d and assume N tends to infinity.
We first discuss Kalai’s algorithm and give a brief analysis. We then use these ideas to
generate, in polynomial time, an integer in [1, N] according to the distribution of norms of
ideals in OK . We then discuss how to use this algorithm to produce random factored ideals
2
of OK with norm up to N uniformly at random using O((log N)d +d+1 ) primality tests.
This algorithm is then modified to generate random factored ideals in function fields using
2
O((log N)d +d+1 ) primality tests. While the algorithm described by Agrawal, Kayal, and
Saxena runs in O(log 15/2 N), Lenstra and Pomerance later developed a primality testing
algorithm with run time O(log6 N) [10]. Using the latter algorithm, our algorithms for
generating random factored ideals in number fields and function fields have expected run
2
times that are O((log N)d +d+7 ).
2. Kalai’s Algorithm
In his 2003 paper [7], Kalai presents the following algorithm:
The author would like to thank Eric Bach for his invaluable advice, suggestions, and encouragement.
The author was supported by the National Science Foundation grant DMS-1502553.
1

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

2

Algorithm 1. Input: A positive integer N.
Output: A positive integer r ∈ [1, N] and its prime factorization, produced according to
a uniform distribution.
1. Generate a sequence N ≥ s1 ≥ s2 ≥ . . . ≥ sl = 1 where s1 ∈ {1, . . . , N}, si+1 ∈
{1, . . . , si } are chosen uniformly at random. Stop when sj = 1.
2. Let r be the product of the prime si ’s.
3. If r ≤ N output r with probability Nr .
4. If r > N or we do not accept r ≤ N, return to step 1.
Let p be a prime number. Then there is a first number si produced in the range
{1, 2, . . . , p}. It is chosen uniformly at random, so the probability that si = p is p1 . Generating e factors p then occurs with probability p1e (1 − p1 ). The probability of outputting
a given r is then:
 v (r) 



Y
1
r Y 1 p
r
vp (r)
1−
=
Pr r =
p
N
N
p
p
p≤n
p≤N


r 1Y
1
=
1−
N r p≤n
p
=

MN
N

Q
Here MN = p≤N (1−1/p). Therefore, if the algorithm terminates, it produces r and its
prime factorization with probability N1 . Moreover, the probability that Kalai’s algorithm
terminates after a single round is MN . We therefore expect MN−1 trials before we output
a number.
We now show that the expected number of primality tests is O(log(N)2 ). Note that
given some si > 1, the expected value of si+1 is s2i . Therefore, a given list s1 , . . . , sl has
expected length O(log N). We need an expected number of O(log N) primality tests for
every round of the algorithm. Hence, we do an expected number of O(MN−1 log N) primality tests overall. By Mertens’ theorem, MN−1 = O(log N). Therefore Kalai’s algorithm
uses O(log(N)2 ) primality tests in expectation before the algorithm terminates.
3. Generating Random Factored Norms
We now give a generalization of Kalai’s algorithm that produces a random norm of an
ideal in OK , along with its prime factorization. Let K be a number field of degree d,
and N an integer satisfying d << log(N). The algorithm will use a polynomial number
of primality tests. In order to do so, we need knowledge of how the rational primes
split. In general, this is computationally efficient for primes not dividing the discriminant
of K [11]. If f (x) is the monic irreducible polynomial over Q determining K, then
we can determine how p splits by factoring f (x) modulo Z/pZ. Factoring polynomials
over finite fields can be accomplished in randomized polynomial time [8]. The remaining
prime numbers can be factored using a method of Chistov to factor polynomials in Qp in
polynomial time [4]. We therefore assume we can factor rational primes in K.
For any integer r > 0, let D(r) denote the number
of ideals in K of norm r. Let p ∈ Z
Q
ej
fj
e
be a rational prime with factorization pOK = m
p
j ) = p . Finding D(p )
j=1 j . Let N(p
P
m
can now be reduced to determining the number of solutions to i=1 ci fi = e. This is an
instance of the subset sum problem. We know that e is O(logP
N). Therefore, we can solve
the subset sum problem in O(m log N) operations [5]. Since m
i=1 ei fi = d, we know that

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

3

m ≤ d. The runtime for this becomes O(log N) as a result. Since D(r) is multiplicative,
we can calculate D(r) for any r relatively efficiently (certainly in polynomial time).
We will generate r and keep r with probability proportional to rD(r)
. In order to
N
guarantee a well-defined probability, we need to bound D(r) by a factor that can be
incorporated in to the selection of the factors. We use the following result. Let Ω(r)
denote the number of prime factors of r with multiplicity, and let Ωd (r) be the number of
prime factors (counting multiplicity) of r that are greater than d.
Proposition 1. D(r) ≤ dΩ(r) .
Proof. Note that D(r) is multiplicative. This is because prime ideals in O
norms
QK have
ep
that are powers of prime numbers [11]. Constructing an ideal of norm r = p p amounts
ep
to constructing an
Qmidealei of norm p for each prime p|r.
Say pOK =
⊂ OK prime. The norm is multiplicative, and since
i=1 pi for p P
m
ei
d
= d. Fix e. Note that D(pe ) will be at
N(pOK ) = p , we must have
i=1 N(pi )
its largest when the p are all distinct (ie. ei = 1) and all the pi have norm p. Then D(pe )
will be the number of unordered sets of e elements taken from the d prime ideals. This is
bounded above by the number ordered sets, which is given by de = dΩ(r) .

We now present the main algorithm. For simplicity of analysis, we demonstrate the
case where d is even and N ≡ d − 1 mod d. Let k ∈ Z be such that N = kd + (d − 1).
These assumptions are not necessary, but help simplify minor details.
Algorithm 2. Input: A positive integer N.
Output: A random integer in [1, N]. The integer is generated according to the distribution
of norms of ideals in OK with norm up to N.
1. Generate ⌊ d2 ⌋ lists of integers as follows. For b ∈ {1, 3, 5, . . . , d − 1}, generate a list
N ≥ s1,b ≥ s2,b ≥ . . . ≥ slb ,b = 1. We take s1,b ∈ {1, d + b, 2d + b, . . . , kd + b}, where
d
1
and is any other element with probability
. Take
s1,b = 1 with probability
kd + 1
kd + 1
1
si+1,b in {1, d + b, 2d + b, . . . , si,b} as 1 with probability
and any other element
si,b − b + 1
d
with probability
.
si,b − b + 1
2. Let r be the product of the prime si,b .
3. For all primes p between 1 and d, do the following: Multiply r by p with probability
p−1
, and continue to multiply by p with this probability until your first failure.
p
ψ(r)D(r)
4. If r ≤ N, keep r with probability Md (r) Ω (r) .
d d N
5. If you did not keep r, go to step 1.
If d is odd, then we take b ∈ {1, 3, 5, . . . , d − 2}. This way we ensure that we are only
picking odd numbers. If N is some other value mod d, say N = kd + j for j < d − 1
then we can instead do the following. Let N ′ be the smallest number above N such that
N ′ ≡ d − 1 mod d. Run steps 1-3 of the algorithm above with N ′ substituted for N. Then
run step 4 by rejecting all r > N instead. For simplicity, we will analyze the algorithm
in the case that N ≡ d − 1 mod d.
Let n denote the residue of n mod d. We define ψ(r) as follows. Let ψ(r) have the same
factors as r, except that for any prime p|r, p > d, replace the factor of p with a factor of
p − p + 1. Note that ψ(r) ≤ r and they share the same prime factors, with multiplicity,
for 2 ≤ p < d.

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

4

We define Md (r) by:
vp (r)
1
α
Md (r) =
p−1
2≤p<d
−1

d + ⌊log N⌋ − 1
α=
⌊log N⌋
Y



4. Analysis of the algorithm
We wish to show that the probability of accepting r is a well-defined probability. Let
g(r) be the product of all prime factors p of r, with multiplicity satisfying p > d. Note
that since D(r) is multiplicative, we have
D(r) = D(g(r))

Y

D(pvp (r) )

2≤p≤d


(r)−1
By the discussion in section 3, D(pvp (r) ) ≤ d+vvpp (r)
. This follows from the fact that
vp (r)
D(p
) is maximized when all the primes ideals lying above p are all distinct and have
norm p. Then D(pe ) equals the number of unordered sets of size e taken from the d prime
ideals lying above p.
Using the above we find
ψ(r)D(r)
dΩd (r) N

Y   1 vp (r)
ψ(r) D(g(r))
vp (r)
α
D(p
)
=
p−1
N dΩd (r)
2≤p≤d

Y 
ψ(r) D(g(r))
vp (r)
αD(p
)
≤
N dΩd (r)
2≤p≤d
Y d + ⌊log N⌋ − 1−1 d + vp (r) − 1 ψ(r) D(g(r))
≤
vp (r)
⌊log N⌋
N dΩ(g(r))
2≤p≤d

Md (r)

≤1
Let p > d be an odd prime with p ≡ p mod d. Then we will produce exactly e factors
of p with probability given by:

e 

d
d
1−
p−p+1
p−p+1
Let r be some integer at most N. Recall that ψ(r) is formed from r by replacing all
r and ψ(r) have the same prime
prime factors p|r, p > d by p − p + 1. In particular,

Q
divisors for p ≤ d. Let P r s = d<p≤N pvp (r) denote the probability that after step 2 we
have generated an integer s that is the product of the prime factors of r that are larger

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

5

than d. The probability can be worked out as follows:
vp (r) 



Y 
Y
d
d
vp (r)
1−
=
Pr s =
p
p
−
p
+
1
p−p+1
d<p≤N
d<p≤N
vp (r)  Y 

Y 
d
d
=
1−
p−p+1
p−p+1
d<p≤N
d<p≤N
vp (r) Y 

Y 
1
d
Ωd (r)
=d
1−
p
−
p
+
1
p−p+1
d<p≤N
d<p≤N


dΩd (r) Y vp (r) Y
d
=
1−
p
ψ(r) 2≤p≤d
p−p+1
d<p≤N
Note that this last step used the fact that by definition of ψ(r), we have
vp (r) Q
vp (r)
Y 
1
2≤p≤d p
=
p−p+1
ψ(r)
d<p≤N
Given any r ≤ N, the probability that we generate r after step 3 is then given by:

v (r) 
 Y

Y 
d
p−1 p
p−1
dΩd (r) Y
vp (r)
1−
1−
p
ψ(r) 2≤p≤d
p
p
p−p+1
2≤p≤d
d<p≤N


dΩd (r) Y
d
1 Y
1−
=
(p − 1)vp (r)
ψ(r) 2≤p≤d
p d<p≤N
p−p+1
Finally, the probability that we accept this r is then given by:

Y 
ψ(r)D(r) dΩd (r) Y
d
vp (r) 1
Md (r) Ω (r)
1−
(p − 1)
d d N ψ(r) 2≤p≤d
p d<p≤N
p−p+1

vp (r)

Y 
d
1
D(r) Y
vp (r) 1
1−
α
(p − 1)
=
N 2≤p≤d
p−1
p d<p≤N
p−p+1




Y
D(r) Y α
d
=
1−
N 2≤p≤d p d<p≤N
p−p+1
Note that other than D(r), all terms depend only on d and N. Therefore, this generates
a number with probability proportional to D(r).
We now show that the algorithm above runs in polynomial time, with polynomial many
primality tests and factorizations of rational primes. Summing over all r at most N, the
probability that we generate an ideal is
P

Y α Y 
d
r≤N D(r)
1−
N
p
p−p+1
2≤p<d
d<p≤N

Y 
d
1−
Let Zn =
. By the Wiener-Ikehara Tauberian theorem (see [6]
p−p+1
d<p≤N
P
for reference), r≤N D(r) asymptotically approaches CK N, where CK is the residue of
the DedekindQ
zeta function of K at 1. Asymptotically then, the expected number of trials
−d −1
is O(α ZN
2≤p<d p).

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

6

By direct computation, we have:


d + ⌊log N⌋ − 1
−1
α =
⌊log N⌋
= (d − 1 + ⌊log N⌋)(d − 2 + ⌊log N⌋) . . . (1 + ⌊log N⌋)
≤ (2 log N)d−1
2

We have d factors of α−1 , Q
so this contributes O(log(N)d −d ) to the expected number
of trials. Note that the term 2≤p<d p contributes a term that is bounded by a constant
dd , and is therefore O(1) in terms of N. We now wish to find the contribution of the
remaining term in the probability calculation above.
Simple estimates show:
Y 
ZN ≥
1−

 Y 

d
d
1−
d+1
p−d
d<p≤2d
2d<p≤N

Y 
2d
1−
≥c
p
2d<p≤N


Q
d
Here c = d<p≤2d 1 − d+1 = (d + 1)−d . By standard estimates, such as in [12], we

have:

−1
Y 
2d
1−
= O(log(N)2d )
p

2d<p≤N
2

Hence we need O(log(N)d +d ) trials before success. Since any given list has expected
2
length O(log(N)), this leads to O(log(N)d +d+1 ) primality tests.
We now use the above algorithm to generate random ideals of OK , uniformly at random
among all ideals with norm up to N. As previously stated,
we assume that we for any
Q
ei
fi
p
rational prime p, we can find the factorization pOK = m
i=1 i with N(pi ) = p . To find
an ideal of norm pe , it suffices to solve, as previously discussed, the subset sum problem:
m
X
ci fi = e
i=1

Q
ci
Any solution to this corresponds to the ideal m
i=1 p . Since e ≤ log N and m ≤ d, we
d
can clearly find all solutions in O(log N operations [5]. While this is not optimal, even
the naive approach is dwarfed by the effort needed to generate the norm. After we find all
solutions, we can then choose uniformly at random one of the solutions, which will give
us one of the ideals of the desired norm. Therefore, the algorithm runs in a number of
2
operations that is O(logd +d+1 N) primality tests and factorizations of pOK . The primality
testing is the dominant part of this in terms of run-time. Since we can perform primality
2
tests in O(log6 N), this gives us a run time that is O(logd +d+7 N) overall.
5. Function Fields

The analogy between number fields and function fields suggests that there should be
an analogous algorithm for function fields. In particular, there are well-known randomized polynomial-time algorithms for factoring over Fq [t]. To generate a factored random
polynomial in Fq [t], we could simply generate one at random and then factor it in randomized polynomial time. Much more elegant ways exist that generate the factorization
at random, the same idea used by the methods above.

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

7

Therefore, we would expect the ability to translate the algorithm above to arbitrary
function fields. Fix a function field K of degree d and N > 0. We want to generate
a random ideal I ⊂ OK with norm r(t) ∈ Fq [t] of degree at most N, along with the
factorization of I. We will use the fact that we can perform primality testing over Fq [t]
in polynomial time. We will also assume that for any irreducible polynomial f (t) ∈ Fq [t],
we can factor f (t)OK in polynomial time. Since OK is a Dedekind domain, this holds for
all f (t) not dividing the discriminant, so there are only finitely many f (t) that need to
be factored as a one-time operation.
As in number fields, the main obstacle is generating the norm g(t) of I with probability
proportional to the number of ideals with this norm. Once we can do this, then we can
use our ability to factor g(t) over OK and solve the corresponding subset sum problem to
generate an ideal of OK uniformly at random with its factorization.
Let g ∈ Fq [t]. Then we can consider g to be a number written base q by looking at
its coefficients. Let n(g) denote this number. Let D(g) denote the number of ideals in
OK with norm g. For any number n ∈ Z, using its q-ary expansion, we can form a
corresponding element β(n) ∈ Fq [t].
We present the following algorithm for generating a norm g ∈ Fq [t] with probabiity
proportional to D(g). It is virtually identical to the algorithm above, except that our
concept of primality of a number p is replaced by primality of the corresponding element
β(p) ∈ Fq [t].
Algorithm 3. Input: A positive integer N.
Output: A random element in Fq [t] with degree at most N. The polynomial is generated
according to the distribution of norms of ideals in OK with degree of their norm at most
N.
1. Generate ⌊ d2 ⌋ lists of integers as follows. For b ∈ {1, 3, 5, . . . , d − 1}, generate a list
q N +1 > s1,b ≥ s2,b ≥ . . . ≥ slb ,b = 1. We take s1,b ∈ {1, d + b, 2d + b, . . . , kd + b}, where
1
d
s1,b = 1 with probability
and is any other element with probability
. Take
kd + 1
kd + 1
1
si+1,b in {1, d + b, 2d + b, . . . , si,b} as 1 with probability
and any other element
si,b − b + 1
d
.
with probability
si,b − b + 1
2. Let r be the product of the si,b such that β(si,b ) is prime.
3. For all integers p between 1 and d such that β(p) is prime, do the following: Multiply
p−1
r by p with probability
, and continue to multiply by p with this probability until
p
your first failure.
ψ(r)D(β(r))
4. If r < q N +1 , return β(r) with probability Md (r) Ω (α(r)) N .
d d
q
5. If you did not return β(r), go to step 1.
Let n denote the residue of n mod d. We define ψ(r) as follows. Factor β(r) in to primes
gi . For each gi such that n(gi ) > d, replace the factor of n(gi ) with n(gi ) − n(gi ) + 1. Note
that ψ(r) ≤ r and β(r), β(ψ(r)) share the same factors gi such that 2 ≤ n(gi ) ≤ d.
We define Md (r) by:
vn(f ) (r)

Y
1
α
Md (r) =
n(f ) − 1
f ∈Fq [t], f is prime
2≤n(f )<d

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

8

−1

d + N⌊log q⌋ − 1
α=
N⌊log q⌋
An almost identical argument to the one above shows that this produces r with probability proportional to D(β(r)). Moreover, the algorithm produces a norm with probability
P

g∈Fq [t],deg(g)≤N
qN

D(g)

Y

g∈Fq [t]
2≤n(g)≤d

α
n(g)

Y

g∈Fq [t]
d<n(g)<q N+1


1−

d
n(g) − n(g) + 1



P
+
We first want to analyze g∈Fq ,deg(g)≤N D(g). Let DK
denote the set of effective divisors
of V , where K is the function field of the projective variety V . Note that the zeta function
for K can be written as:
X
1
ζK (s) =
deg(D)s
q
+
D∈DK

If we let an denote the number of g ∈ Fq [t] of degree n, then this becomes:
X an
ζK (s) =
q ns
n≥0
Since ζK (s) converges absolutely for Re(s) > 1 and has a simple pole at s = 1, the
analogue of the Wiener-Ikehara Tauberian theorem for function fields implies that:
X
an = Θ(q N )
n≤N

Let ZN be given by:
ZN =

Y

d<n(g)<q N+1



1−

d
n(g) − n(g) + 1



g prime

Note that the expected number of trials of the algorithm is:
O(α−d ZN−1

Y

n(g))

2≤n(g)≤d
g prime

By an analogous argument to the above, we have at most d factors of α which contribute
at most (2N log(q))d−1 to the expecte number of trials, while the last product in the
estimate contributes an amount bounded by dd . Therefore, it suffices to bound ZN−1 .
Using a version of the prime number theorem for Fq [x], one can prove in an analogous
way to the proof above that ZN−1 contributes O((N log(q))2d ) iterations in expected value.
2
Therefore, we require O((N log q)d +d ) trials before success in expectation. Each of the
2
d
lists has expected length O(N log q), so we require O((N log q)d +d+1 ) primality tests.
2
Note that this gives us a randomized algorithm that is polynomial in the logarithm of the
size of the input (as there are q N possible norms of the ideal to generate). Since primality
testing can be performed in time that is O((N log q)6 ), this gives us an overall runtime
2
that is O((N log q)d +d+7 ).

GENERATING RANDOM FACTORED IDEALS IN NUMBER FIELDS

9

6. Further Work
The algorithm above uses similar ideas to Kalai’s algorithm. Bach’s algorithm for
generating factored integers runs in fewer primality tests, and so one could ask whether the
ideas of Bach could be adapted to this setting in order to reduce the number of primality
tests required. In general, one could determine ways to make the above algorithm run
faster, in particular by reducing the number of primality tests required.
The algorithms above work for a fixed number or function field. In particular, their
runtime is polynomial treating the degree of the field extension as constant. It remains
an open question whether there is an algorithm for generating random factored ideals
that runs in polynomial time, irrespective of the degree of the field. The methods above
would have to be altered significantly to do so, due to their exponential dependence on
the degree d.
There are other generalizations of this problem that could be considered. Due to the
natural way in which principal ideals arise in number fields, one could ask for a variant
of this algorithm that generates principal ideals uniformly at random. Clearly we could
use the above algorithm to generate an ideal uniformly at random, and then only accept
if it is principal. Since this occurs with probability 1/h, where h is the class number, this
would result in a polynomial time algorithm provided we had a polynomial time way to
recognize principal ideals. Unfortunately, this is a difficult question in arbitrary number
fields, as there are no known polynomial time algorithms to detect whether an ideal in an
arbitrary number field is principal.
References
1. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, Primes is in p, Annals of mathematics (2004),
781–793.
2. Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, MIT press
Cambridge, 1985.
3. Eric Bach, How to generate factored random numbers, SIAM Journal on Computing 17 (1988), no. 2,
179–193.
4. Alexandre Chistov, Efficient factoring polynomials over local fields and its applicatons, Proceedings
of the International Congress of Mathematicians, Kyoto, Japan, vol. 2, Springer Verlag, August 1990,
pp. 1509–1519.
5. Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson, Introduction to
algorithms, 2nd ed., McGraw-Hill Higher Education, 2001.
6. Shikao Ikehara, An extension of landau’s theorem in the analytical theory of numbers, Journal of
Mathematics and Physics 10 (1931), no. 1-4, 1–12.
7. Adam Kalai, Generating random factored numbers, easily, J. Cryptology 16 (2003), 287–289.
8. Donald Knuth, Seminumerical algorithms, vol. 2, Addison-Wesley, Reading, MA, 1997.
9. Noah Lebowitz-Lockard and Carl Pomerance, Generating random factored Gaussian integers, easily,
Math. Comp. 85 (2016), 503–516.
10. Hendrik W. Lenstra, Jr., Primality testing with gaussian periods, Proceedings of the 22Nd Conference
Kanpur on Foundations of Software Technology and Theoretical Computer Science (London, UK,
UK), FST TCS ’02, Springer-Verlag, 2002, pp. 1–.
11. James S. Milne, Algebraic number theory, 2013, Available at www.jmilne.org/math/, p. 161.
12. J Barkley Rosser, Lowell Schoenfeld, et al., Approximate formulas for some functions of prime numbers, Illinois Journal of Mathematics 6 (1962), no. 1, 64–94.
University of Wisconsin-Madison, Dept. of Mathematics
E-mail address: zcharles@math.wisc.edu

