Equidistribution on the Sphere.
A concept of generalized discrepancy, which involves pseudodifferential operators to give a criterion of equidistributed pointsets, is developed on the sphere. A simply structured formula in terms of elementary functions is established for the computation of the generalized discrepancy. With the help of this formula five kinds of point systems on the sphere, namely lattices in polar coordinates, transformed two-dimensional  sequences,  rotations on the sphere, triangulations, and "sum of three squares sequence," are investigated. Quantitative tests are done, and the results are compared with one another. Our calculations exhibit different orders of convergence of the generalized discrepancy for different types of point systems.
Introduction
Of practical importance is the problem of generating equidistributed pointsets on the
sphere. For that reason a concept of generalized discrepancy, which involves pseudodifferential
operators to give a quantifying criterion of equidistributed pointsets, is of great
interest. In this paper an explicit formula in terms of elementary functions is developed
for the generalized discrepancy. Essential tools are Sobolev space structures and
pseudodifferential operator techniques. It is mentioned that an optimal pointset may
be obtained by minimizing the generalized discrepancy. But, in spite of the elementary
representation of the generalized discrepancy, this is a non-linear optimization problem
which will not be discussed here. Our investigations, however, show that there are
many promising ways to generate point systems on the sphere such that the discrepancy
becomes small. To be specific, we distinguish five kinds of point systems on the
sphere: lattices in polar coordinates, transformed 2-dimensional sequences, rotations on
the sphere, triangulations, and "sum of three squares sequence". By use of our developed
formulas, the five classes of point systems are described, and their discrepancies are
explicitly calculated for increasing numbers of points. The results show different orders
of convergence indicated by the generalized discrepancy. Furthermore, our computations
enable us to give a quantitative comparison between the different point systems. It is
somehow surprising that certain types of transformed sequences yield the best results.
Nevertheless, there are special other pointsets which provide us with better results for
comparable numbers of points. For instance, the soccer ball (C us to the best
result in all our considered pointsets of about 60 points.
The problem of generating a large number of "equidistributed points" on the sphere
has many applications in various fields of computation, particularly in geoscience, medicine.
The advantage of equidistributed point systems lies in the fact that relatively few sampling
of the data is needed, and approximate integration can be simply performed by
computation of a mean value, i.e., the arithmetical mean.
The outline of the paper is as follows: Section 2 begins with a discussion of Sobolev
spaces and (invariant) pseudodifferential operators on the sphere. The generalized discrepancy
is developed in Section 3. The announced point systems are studied in Section
4. The low discrepancy method, also called quasi-Monte-Carlo method, for numerical
integration on the sphere is discussed in Section 5 for three types of test examples

Operators
on the Sphere
Let IR 3 denote the three-dimensional Euclidean space. We use x; to represent the
elements of IR 3 and the Greek alphabet to represent the vectors of the unit sphere
\Omega in IR 3 . \Delta   denotes the Beltrami operator on the unit sphere. A function F
possessing k continuous derivatives
on\Omega is said to be of class C
is the class of real continuous scalar-valued functions on \Omega\Gamma By L
2(\Omega\Gamma we denote the
space of Lebesgue square-integrable scalar functions on \Omega\Gamma The spherical harmonics of
degree n are defined as the everywhere
on\Omega infinitely differentiable eigenfunctions of the
Beltrami-operator \Delta   corresponding to the eigenvalues (\Delta
As it is well-known (cf. e.g. [14]), the linear space Harm n of all spherical harmonics of
degree n is of dimension 2n+1. We denote fY n;j (); to
be an orthonormalized basis of L
2(\Omega\Gamma4 where n is called degree and j order of the spherical
harmonics. The space Harm 0;:::;m of all spherical harmonics of degree  m possesses
the dimension (m . The Legendre polynomials P n are the infinitely differentiable
eigenfunctions of the Legendre operator, satisfying the normalization condition P n
1. It should be noted that jP n (t)j  1 and jP 0
. The well-known addition theorem of spherical harmonics states (cf. [5], [14])
Y n;j ()Y n;j
In particular, we have
s
For s 2 IR consider the space
where F n;j are the spherical harmonic coefficients of F and by definition,
elsewhere:
On
(\Omega\Gamma we are able to impose an inner product as follows:
The Sobolev space H s
(\Omega\Gamma is the completion of E
with respect to the topology k \Delta kH
(\Delta; \Delta) 1=2
. The following relationships between Sobolev spaces are valid: H s
spaces and classical function spaces C
are related via
imbedding theorems.
Lemma 2.1 (Imbedding Theorem). H
s(\Omega\Gamma is a subspace of C
Proof. It is sufficient to prove Lemma 2.1 for the case applying the
Cauchy-Schwarz inequality we obtainX
From the addition theorem of the spherical harmonics it follows that
4"n 2s
provided that s ? 1. Therefore the series is absolutely convergent. But this means that
the F corresponds to a continuous function on \Omega\Gamma
From Lemma 2.1 (Imbedding Theorem) we are able to conclude that the spherical harmonic
expansion of any function in H
converges uniformly provided that s ? 1.
This is of significance, since there are functions in
C(\Omega\Gamma which do not allow a uniformly
convergent spherical harmonic expansion (cf. [7]).
By aid of the Sobolev space structure introduced above we make some comments
on (invariant) pseudodifferential operators on the sphere, since these operators do not
belong to the traditional equipment.
Definition 2.1 (Pseudodifferential Operator on the Sphere). Let fA n g, be a
sequence of real numbers A n satisfying
lim
const
for some t 2 IR. Then the operator A : H
defined by
is called pseudodifferential operator of order t. fA n g is called spherical symbol of A.
Moreover, if
lim
for all t 2 IR, then the operator A:H
1(\Omega\Gamma is called pseudodifferential operator
of order -1 (note that the equation (6) is understood in H
The spherical symbol has many appealing properties. For example, it is readily seen that
n for every choice of pseudodifferential operators
Obviously we have
(i.e. all pseudodifferential operators considered here are invariant operators). Using the
kernel
AF is obtainable by convolution as follows
Z\Omega
F (j)K A
The kernel satisfies the property KA 2 H
\Gamma(t+ffl)(\Omega\Gamma for all ffl ? 0 provided that t ? \Gamma1.
In the case
In the sequel we list some particularly important pseudodifferential operators:
(1) The Beltrami operator \Delta   is not invertible, since (\Delta   but the
operator 1has the symbol f(n and, hence, has an
inverse which is a pseudodifferential of order \Gamma2. More generally,
is a pseudodifferential operator of order 2s and has the spherical symbol
Using the kernel K
Z
\Omega
for all F 2 H s
(\Omega\Gamma and  2 \Omega\Gamma This is easily seen by the Parseval identity for the
system of L 2
spherical harmonics.
(2) The integral operator of the single layer potential
on\Omega given by
Z
is a pseudodifferential operator of order -1 possessing the symbol fA n g with A
. This can be seen by inserting the expansion of
of Legendre polynomials. A consequence is that A is invertible. Other types of
geodetically relevant integral operators can be found in [17].
(3) The operator
2 has the symbol fA n g, where A n is given by
A is not invertible, but the related operator
B with symbol fB n g given by
is invertible. Since (cf. e.g. [12])X
s
we find
s
A
pseudodifferential operators
of order \Gamma1.
To show the relationship between the pseudodifferential operators and the Sobolev
spaces we give an equivalent reformulation of the Sobolev space H
s(\Omega\Gamma2 Let A be a
pseudodifferential operator of order s. Then, the Sobolev space H
s(\Omega\Gamma can be equivalently
expressed in the following form:
3 Equidistribution on the Sphere
In this section we discuss the problem of equidistribution. This problem can be stated
as follows: find a pointset such that the remainder term
Z
for any function G 2 H s
(\Omega\Gamma converges to 0 as N !1.
Let us begin the discussion with an a priori estimate of the remainder. The result is
an analogue to the Koksma-Hlawka inequality in Euclidean spaces (see also, [8,9,10] and
many other references therein).
Theorem 3.1 . Let A be a pseudodifferential operator of order s, s ? 1, with symbol
satisfying A n 6= 0 n  1. Then, for any function AG 2 L
, we have the
estimate
Z\Omega
Proof. From (8) we know that AG 2 L
2(\Omega\Gamma is equivalent to G 2 H
s(\Omega\Gamma2 Because of the
assumption s ? 1 it follows from Lemma 2.1 (Imbedding Theorem) that the spherical
harmonic expansion
converges absolutely and uniformly. We rewrite the spherical harmonic expansion of G
as follows:
Z\Omega
Z\Omega AG(j)Y n;j (j)
A n
d!(j)Y n;j ():
By setting taking the sum over all indices
Z\Omega
Z\Omega AG(j)Y n;j (j)
A n
Hence, the integral error can then be estimated as follows
Z
A n
Z
\Omega AG(j)Y n;j (j)d!(j)
Z
\Omega AG(j)X
Y n;j (j i )Y n;j (j)
A n
By using the Cauchy-Schwarz inequality and the addition theorem of the spherical harmonics
we get
Z
Z
Y n;j (j i )Y n;j (j)
A nAd!(j)7 52
kAGk
A n
kAGk L 24 N
This completes the proof.
Theorem 3.1 extends a result given for the Beltrami operator (cf. [5]) to the general
context of pseudodifferential operators. It is obvious that the right-hand side of the
estimate (10) consists of two parts. The first part depends only on the pointset, while
the second part depends merely on the function G under consideration. This gives rise
to the definition of generalized discrepancy.
Definition 3.1 (Generalized discrepancy). Let A be a pseudodifferential operator of
1. Then the generalized discrepancy
associated to a pseudodifferential operator A is defined by
The generalized discrepancy characterizes "how well a pointset is equidistributed".
This can be explained by a heuristic geometrical interpretation as follows: for any subset
of\Omega and any pointset fj
on\Omega we define the counting function,
where B is the characteristic function of B. Thus #B indicates the number n,
N , of points j i contained in B. Let  ffl
approximation of the
characteristic function B . Then, for any non-empty Lebesgue-measurable subset B of
\Omega\Gamma we have an integral inequality of the following form
\Gamma4
Z
Z\Omega
jN
Z
\Omega  ffl
Therefore, the generalized discrepancy gives a quantitative description of how well a
pointset is equidistributed.
Remark. It is also worth to translate the Wozniakowski idea of averaging the integration
error (cf. [13]) into the spherical context. But this is a challenge for future work.
For different pseudodifferential operators we have different generalized discrepancies.
It is of interest to understand the relationship between different generalized discrepancies
associated to different pseudodifferential operators.
Lemma 3.1 . Let A, B be two pseudodifferential operators of order s 1 , s 2 ,
satisfying A n 6=
Then, the following relations are valid for the generalized discrepancies associated to the
pseudodifferential operators A and B:
1) If the two pseudodifferential operators A and B are of the same order, i.e. s
then there exist two positive constants C 1 and C 2 such that
there exists a constant C 3 such that
Proof. Applying the addition theorem of spherical harmonics we have
A n
Thus the generalized discrepancy can be rewritten as follows:
A n
it follows from our definition of pseudodifferential operators that there
exist two constants C 1 and C 2 such that
A n
A n
Therefore it is clear that
The part (2) can be proved in the same manner.
From Lemma 3.1 we deduce that the generalized discrepancy is dependent only on
the order of the pseudodifferential operators. Using the generalized discrepancy we can
study the property of point systems in quantitative way.
Definition 3.2 (Equidistribution in H
N
is called A-equidistributed in H
the generalized discrepancy associated to
a pseudodifferential operator A of order s, s ? 1, satisfies
lim
It should be noted that if a point system is equidistributed in H s
the point system is equidistributed in H
This shows us that we should use
small as possible for our quantitative investigations. However, in order to
compute the generalized discrepancy as illustrated above, one has to evaluate a series
expansion in terms of Legendre polynomials. This summation is very time consuming, in
particular, for relatively small s. Therefore it is not advisable to use this series expansion
for the computation of the generalized discrepancy. Fortunately, for certain pseudo-differential
operators, the series is representable in terms of elementary functions. One
example should be discussed in more detail. Consider the pseudodifferential operator
4 . Its symbol is fD n g with D
is 3. Thus, the condition DG 2 L
2(\Omega\Gamma is equivalent to G 2 H 3
more precisely,
H 3. It is worth noting that the functions in the Sobolev space H 3
are "slightly smoother" than the continuous functions, and its elements generally are
not Lipschitz-continuous. Observing our particular choice the generalized discrepancy is
then given by
As mentioned above, the series on the right hand side is expressible in terms of elementary
functions
s
To keep an appropriate balance between computation and the requirement that the order
should be as small as possible, we simply speak in the following of equidistribution on
the sphere, when fj N
lim
In connection with Theorem 3.1 we then obtain
Z
D) is given by (17) and G 2 H 3
To get an optimal point system on the sphere we have to minimize the expression
within a set of N points on \Omega\Gamma This is unfortunately
a non-linear optimization problem. It is a challenge for further investigation. Another
possibility for construction of pointsets is to require that sum of some low degree spherical
harmonics vanish, that is to say, moments up to a particular order should vanish.
Definition 3.3 (m-design). A pointset is called an m-design if the so-called
Weyl sums
m. To be specific,
Equivalently a pointset is an m-design if and only if4
Z\Omega
holds for all spherical harmonics Y n of degree n  m. It can be shown that a pair
of antipodal points, the vertices of a regular tetrahedron, the regular octahedron, and
the regular icosahedron give 1-,2-,3-,and 5-designs, respectively. In [15] the existence
of spherical m-designs is proved, but only for sufficiently large N. A construction of m-
designs with number of points can be found in [2]. In this paper we only deal
with the possibility of an estimate of the generalized discrepancy in case of an m-design
g.
Lemma 3.2 . Let A be a pseudodifferential operator of order s, s ? 1, with symbol
fA n g, A n 6= 0 for n  1. If a pointset is an m-design, then the generalized
discrepancy satisfies
where the constant C depends only on s.
Proof. From the definitions of m-design and generalized discrepancy it follows that
By using the well-known inequalityX
C z;s
where the Zeta constant is given by C
, we have the desired estimate.
For large values s the m-design gives a good rate of convergence. Suppose that the
number of points is we know the existence of an m-design, but
the minimal value of t is unknown), then the rate of convergence amounts to N (s\Gamma1)=t .
However, for a rate of convergence of order N 1
2 . Therefore
this type of an m-design does not seem to be well-suited.
4 Point Systems on the Sphere and Their Discrep-
ancy
Of practical importance is the basic problem of generating a large number of points
on the sphere having a small generalized discrepancy. The geometrical interpretation
of a pointset with small generalized discrepancy means that the points in the set are
in a well-separated and distributed manner. A point system is called hierarchical, if
N+1 g for all N. In our approach we distinguish five kinds
of point systems on the sphere: lattices in polar coordinates, transformed 2-dimensional
sequences, rotations on the sphere, triangulations, and the "sum of three squares se-
quence". In this section briefly describe how these point systems are generated. Then
we numerically compute the generalized discrepancies and compare their values. To
investigate the order of convergence in quantative way a parameter fi determined by
log
log N
is introduced, where D(fj D) is given by (17). A large number of fi means
that the point system is well-structured. The results of computation exhibit the different
orders of convergence for different point systems.
4.4.1 Conventional Polar Coordinate Lattices
The lattices are generated by taking an equidistant division of the latitude and the lon-
gitude. Two examples are considered:
(a) The "simple lattice" f('
This is the most well-known point system in geosciences. Unfortunately, for large numbers
P and Q, there is strong concentration of points near the poles. Table 1 gives the
computed values of the generalized discrepancy and the factor fi for this "simple lattice".
As expected the point system does not give good results.
Tab.1: The generalized discrepancy of "simple lattices"
No. of Pts. D(fj
(b) To avoid the concentration of points near the poles we keep equidistant laterals
and divide each lateral circle into
parts, i.e.
Hence, this "improved lattice" does not show strong concentration of points near the
poles, since the division of lateral circles depends on the variable '. The total number
of points in the set f(' amounts to

Table

2 gives the computed values of the generalized discrepancy and the factor fi for
the "improved lattices". Actually the rate of improvement is slow.
Tab.2 Generalized discrepancy of "improved lattice"
No. of Pts. D(fj
4.4.2 Transformed Sequences
We again follow the strategy: (i) consider equidistributed pointsets on the rectangle
system via the mapping
(t; OE) 7!
to the unit
As a matter of fact, there are many ways to generate equidistri-
butions in a rectangle (for example, see [8,9,10,13] and many other references).
(a) Hammersley system: the p-adic Van der Corput sequence is defined by
x (p)
with
where p is an integer greater than or equal 2.
n be the Van der Corput sequence with basis p=2 and OE
. Then,
the Hammersley system on the sphere is defined by (t . The Hammersley
system is not hierarchical. A hierarchical point system can be generated by
two p-adic Van der Corport sequences
different
prime numbers p 1 and p 2 .

Table

3 gives the computed values of the generalized discrepancy and the factor fi
for the Hammersley system. The values of fi show a significant improvement compared
with the former pointsets.
Tab.3: Generalized discrepancy of Hammersley systems
No. of Pts. D(fj
(b) Uniformly pseudo-random generation: we use the one-dimensional pseudo-random
number generator to dertermine two sequences For example, we
choose a classical congruential generator, x

Table

4 gives the computed values of the generalized discrepancy and the factor fi for
the pseudo-random sequence on the sphere.
Tab.4: Generalized discrepancy of pseudo-random sequences
No. of Pts. D(fj
22
4.4.3 Rotations on the Sphere
This so-called operator sequence is described in [11]. Let A, B, and C be rotations
(orthogonal transformations), respectively, about the X, Y and Z-axes, each through an
angle. Let R s be the set of non-trivial reduced words in A, B, C, A
length less than or equal to s (by reduced we mean all the obvious cancellations such as
carried out), i.e.
R s contains 2N= 3(5 s \Gamma 1) elements of rotations. A stereographic projection can be
used to relate points in the complex plane C to points on the sphere. To every point
on the unit sphere, except the North pole (0; 0; 1) T , we associate a
complex number
Under this stereographic projection the fractional linear transformations in the complex
plane correspond to rotations on the sphere. Taking this into account it is convenient
to actually compute with points in C and fractional linear transformations instead of
rotations. In particular, we consider the following fractional linear transformations
A =p0

Table

5 gives the computed values of the generalized discrepancy and the factor fi
with initial complex number i as starting point for rotations.
Tab.5: Generalized discrepancy of rotations
No. of Pts. D(fj
4.4.4 Triangulations
One can generate point systems on the sphere by triangulation: the triangulation
are initiated with well-known polyhedral corner points of number 4, 8 or 20, which are,
respectively, tetrahedron, octahedron, or icosahedron. To refine the triangulation we
proceed as follows: connect the midpoints of sides of each triangle, then project the
midpoints on the sphere in radial direction, this will form four new triangular elements.
The points are taken by the centre of each new triangular elements. Table 6,7,8 give the
computed values of the generalized discrepancy and the factor fi for triangulations. To
our surprise the results are not very convincing for larger pointsets.
Generalized discrepancy of tetrahedral tringulation
No. of Pts. D(fj
Tab.7: Generalized discrepancy of octahedral tringulation
No. of Pts. D(fj
Tab.8: Generalized discrepancy of icosahedral triangulation
No. of Pts. D(fj
4.4.5 Sum of Three Squares Sequence
This sequence arises in Number Theory, and a description can be found in the paper
[1]. Taking the projection of the integer solutions of the equations x 2
on the unit sphere, we are led to sets of type
Removing the redundancy in the set "
XN we obtain the so-called "sum of three squares
sequence", denoted by XN . This point system is hierarchical, since XN ' XN+1 for all
N.

Table

9 gives the computed values of the generalized discrepancy and the factor fi for
the sum of three squares sequence.
Tab.9: Generalized discrepancy of sum of three squares sequence
No. of Pts. D(fj
4.4.6 Conclusion
The results of the generalized discrepancy for different types of point systems on the
sphere will be plotted below. It is surprising that certain types of transformed sequences
yield the best results in our computation. It is also worth mentioning that the triangulations
do not take an exceptional role in equidistribution on the sphere. Furthermore
it should be noted that there exist some well-distributed pointsets with special number
of points on the unit sphere. For example, the soccer ball (the carbon-60 molecule) has
the smallest generalized discrepancy (=0.0012.) compared with all our pointsets with
about
4500.0050.0150.0250.0350.045Number of Points
generalized
discrepancy
Rotations
Sum of Three Squares
Simple Lattice
Improved Lattice
Random
Hammersley
5 Low Discrepancy Method
The Monte-Carlo method is very simple, namely the integral is replaced by its arithmetic
mean value over a finite set of points. The quasi-Monto-Carlo method, sometimes
called low discrepancy method, is understood to be a Monte-Carlo method, but based
on pointsets forming an equidistribution. The proper justification of the low discrepancy
method must not be based on the randomness of the procedure, which is spurious,
but on equidistribution of the sets of points at which the values of the integrand are
computed. Besides the simplicity, the other advantage of the low discrepancy method
is its flexibility of adaptive increasing number of points in order to guarantee a given
accuracy. The transition from N points to N+1 points for a hierachical system needs
only one further operation. The drawback of the low discrepancy method is that quite a
large number of sampling may be needed, since the convergence tends to be quite slow.
From Section 4, we know empirically the factor fi. In the following test, the Hammersley
point system is used, which turned out in our study to have a good value of fi.
Example 1: firstly we discuss the integration of a discontinuous function, namely the
characteristic function given by
for fixed  0 2 \Omega\Gamma The exact value of the integral is easily calculable:
Z
For our tests we choose the parameter , the exact value
of the integral is equal to 0.30752.
Example 2: the second problem deals with integration of the function (cf. [5])
Z
sin(r)
r
This function is smooth for small r. For the numerical tests,
are taken, therefore we obtain
Example 3: the third problem is concerned with the computation of a highly oscillating
integrand. We choose the square of a spherical harmonic with degree
course, the integral value of this square of the spherical harmonic is equal to
1.
Absolute Error of Low Discrepancy Method
No. of Points Example 1 Example 2 Example 3
100 5.6194e-002 4.3443e-004 2.4112e-002
500 5.9281e-003 3.2776e-005 3.5989e-002
700 2.3377e-003 1.4992e-005 2.5217e-003
900 3.4303e-004 1.1899e-005 3.2383e-003
1300 1.8051e-003 4.1731e-006 1.9815e-003
1500 2.4495e-003 3.8074e-006 1.9823e-003



--R

Uniform Distribution of Integral Points on 3-Dimensional Sphere via Modular Forms
Construction of Design on 2-Sphere
Finite Pointset Methods on the Sphere and Their Application in Physical Geodesy
Spherical Codes and Design
On Integral Formulas of the Unit Sphere and Their Application to Numerical Computation of Integrals
Spherical Designs
On the Degree of Convergence of Laplace's Series.
Gleichverteilung auf Produkten von Spharen.
Application of Number Theory to Numerical Analysis
Uniform Distribution of Sequences
Hecke Operators and Distributing Points on the Sphere I
Formulas and Theorems for the Special Functions of Mathematical Physics

Spherical Harmonics
Averaging Set: a Generalization of Mean Values and Spherical Designs
Encrypting by Random Rotations
Pseudodifferential Operators - A New Approach to the Boundary Problems of Physical Geodesy
Random Points in the Cube and on the Sphere with Applications to Numerical Analysis
Spline Interpolation and Smoothing on the Sphere
--TR

--CTR
Q. T. Le Gia, Galerkin approximation for elliptic PDEs on spheres, Journal of Approximation Theory, v.130 n.2, p.125-149, October 2004
M. Gtz, On the Riesz energy of measures, Journal of Approximation Theory, v.122 n.1, p.62-78, May
low discrepancy quasi-Monte-Carlo method;pointsets;sphere;approximate integration;equidistribution;pseudodifferential operators;generalized discrepancy