A combinatorial characterization of (t,m,s)-nets in base b

We consider (t,m,s)-nets in base b, which were introduced by Niederreiter in 1987. These nets are highly uniform point distributions in s-dimensional unit cubes and have applications in the theory of numerical integration and pseudorandom number generation. A central question in their study is the determination of the parameter values for which these nets exist. Niederreiter has given several methods for their construction, all of which are based on a general construction principle from his 1987 paper. We define a new family of combinatorial objects, the so-called “generalized orthogonal arrays,” and then discuss a combinatorial characterization of (t.m.s)-nets in base b in terms of these generalized orthogonal arrays. Using this characterization, we describe a new method for constructing (t.m.s)-nets in base b that is not based on the aforementioned construction principle. This method gives rise to some very general conditions on the parameters (involving a link with the theory of orthogonal arrays) that are sufficient to ensure the existence of a (t.m.s)-net in base b. In this way we construct many nets that are new. © 1996 John Wiley & Sons, Inc.     

Calculation of the Quality Parameter of Digital Nets and Application to Their Construction

In quasi-Monte Carlo methods, point sets of low discrepancy are crucial for accurate results. A class of point sets with low theoretic upper bounds of discrepancy are the digital point sets known as digital (t, m, s)-nets which can be implemented very efficiently. The parameter t is indicative of the quality; i.e., small values of t lead to small upper bounds of the discrepancy. We introduce an effective way to establish this quality parameter t for digital nets constructed over arbitrary finite fields and give an application to the construction of digital nets of high quality.     

Combinatorial methods in the construction of point sets with uniformity properties

It is well known that (t, m, s)-nets are useful in numerical analysis. Many of the constructions of such nets arise from number theoretic or algebraic constructions. Less well known is the fact that combinatorial constructions also yield nets with very good and in many cases, optimal parameters. In this paper, we provide a survey of such combinatorial constructions of (t, m, s)-nets.     

Scrambling Sobol' and Niederreiter–Xing Points

Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. In particular, randomized (0, m, s)-nets in basebproduce unbiased estimates of the integral, have a variance that tends to zero faster than 1/nfor any square integrable integrand and have a variance that for finitenis never more thane?2.718 times as large as the Monte Carlo variance. Lower bounds thaneare known for special cases. Some very important (t, m, s)-nets havet>0. The widely used Sobol' sequences are of this form, as are some recent and very promising nets due to Niederreiter and Xing. Much less is known about randomized versions of these nets, especially ins>1 dimensions. This paper shows that scrambled (t, m, s)-nets enjoy the same properties as scrambled (0, m, s)-nets, except the sampling variance is guaranteed only to be belowb^t[(b+1)/(b−1)]^stimes the Monte Carlo variance for a least-favorable integrand and finiten.     

Bounds for the Quality Parameter of Digital Shift Nets over Z2

Until now, the concept of digital (t,m,s)-nets is the most powerful concept for the construction of low-discrepancy point sets in the s-dimensional unit cube. In this paper we consider a special class of digital nets over $\text{Z}$₂, the so-called shift nets introduced by W. Ch. Schmid, and give bounds for the quality parameter t of such nets.     

Scrambling non-uniform nets

In this paper, we consider Owen’s scrambling of an (m−1, m, d)-net in base b which consists of d copies of a (0, m, 1)-net in base b, and derive an exact formula for the gain coefficients of these nets. This formula leads us to a necessary and sufficient condition for scrambled (m − 1, m, d)-nets to have smaller variance than simple Monte Carlo methods for the class of L ₂ functions on [0, 1] ^d . Secondly, from the viewpoint of the Latin hypercube scrambling, we compare scrambled non-uniform nets with scrambled uniform nets. An important consequence is that in the case of base two, many more gain coefficients are equal to zero in scrambled (m − 1, m, d)-nets than in scrambled Sobol’ points for practical size of samples and dimensions.      

Star discrepancy estimates for digital (t, m, 2)-nets and digital (t, 2) -sequences over Z2

Summary We prove upper bounds on the star discrepancy of digital (t, m, 2)-nets and (t, 2)-sequences over Z₂. The main tool is a decomposition lemma for digital (t, m, 2)-nets, which states that every digital (t, m, 2)-net is just the union of 2^tdigitally shifted digital (0, m - t, 2)-nets. Using this result we generalize upper bounds on the star discrepancy of digital (0, m, 2) -nets and (0, 2) -sequences.     

Point sets and sequences with small discrepancy

A systematic theory of a class of point sets called (t, m, s)-nets and of a class of sequences called (t, s)-sequences is developed. On the basis of this theory, point sets and sequences in thes-dimensional unit cube with the smallest discrepancy that is currently known are constructed. Various connections with other areas arise in this work, e.g. with orthogonal latin squares, finite projective planes, finite fields, and algebraic coding theory. Applications of the theory of (t, m, s)-nets to two methods for pseudorandom number generation, namely the digital multistep method and the GFSR method, are presented. Several open problems, mostly of a combinatorial nature, are stated.The author wants to thank the Universität Hannover (West Germany) for its hospitality during the period when most of this research was carried out. The results of this paper were presented at the Colloquium on Irregularities of Partitions at Fertöd (Hungary), July 7–11, 1986.     

Particle simulations of the Kac model of the Boltzmann equation

We consider a simplified mathematical model of the Boltzmann equation which was introduced by Kac. A quasi-Monte-Carlo particle simulation using (t, m, s)-nets is described. The particle movement is shown to be an evaluation of the volume of a subset of I⁴=[0,1)⁴. An error bound for quasi-Monte-Carlo approximation of the volume of a generalized quadrant set is derived, when a (t, m, s)-net is used. Convergence of the simulation is proved when the particles are reordered according to their velocity in every time step. Quasi-Monte-Carlo and Monte-Carlo particle simulations are compared in computational experiments. The results indicate that quasi-Monte-Carlo simulation outperforms standard Monte-Carlo approaches.     

On the L p discrepancy of two-dimensional folded Hammersley point sets

We give an explicit construction of two-dimensional point sets whose L _p discrepancy is of best possible order for all \({1 \le p \le \infty}\) . It is provided by folding Hammersley point sets in base b by means of the b-adic baker’s transformation which has been introduced by Hickernell (Monte Carlo and quasi-Monte Carlo methods. Springer, Berlin, 274–289, 2002) for b =  2 and Goda, Suzuki, and Yoshiki (The b-adic baker’s transformation for quasi-Monte Carlo integration using digital nets. arXiv:1312.5850 [math:NA], 2013) for arbitrary \({b \in \mathbb{N}}\) , \({b \ge 2}\) . We prove that both the minimum Niederreiter–Rosenbloom–Tsfasman weight and the minimum Dick weight of folded Hammersley point sets are large enough to achieve the best possible order of L _p discrepancy for all \({1 \le p \le \infty}\) .     

Cubic and higher degree bounds for codes and (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">s</Emphasis>)-nets

The Plotkin bound and the quadratic bound for codes and (t, m, s)-nets can be obtained from the linear programming bound using certain linear and quadratic polynomials, respectively. We extend this approach by considering cubic and higher degree polynomials to find new explicit bounds as well as new non-existence results for codes and (t, m, s)-nets.     

Point sets with uniformity properties and orthogonal hypercubes

The theory of (t, m, s)-nets is useful in the study of sets of points in the unit cube with small discrepancy. It is known that the existence of a (0, 2,s)-net in baseb is equivalent to the existence ofs–2 mutually orthogonal latin squares of orderb. In this paper we generalize this equivalence by showing that fort0 the existence of a (t, t+2,s)-net in baseb is equivalent to the existence ofs mutually orthogonal hypercubes of dimensiont+2 and orderb. Using the theory of hypercubes we obtain upper bounds ons for the existence of such nets. Forb a prime power these bounds are best possible. We also state several open problems.This author would like to thank the Mathematics Department of the University of Tasmania for its hospitality during his sabbatical when this paper was written. The same author would also like to thank the NSA for partial support under grant agreement # MDA904-87-H-2023.This author's research was supported by a grant from the Commonwealth of Australia through the Australian Research Council.     

On the existence of Hadamard matrices

Given any natural number q > 3 we show there exists an integer t ? [2log₂(q ? 3)] such that an Hadamard matrix exists for every order 2^sq where s > t. The Hadamard conjecture is that s = 2.This means that for each q there is a finite number of orders 2^υq for which an Hadamard matrix is not known. This is the first time such a statement could be made for arbitrary q.In particular it is already known that an Hadamard matrix exists for each 2^sq where if q = 2^m ? 1 then s ? m, if q = 2^m + 3 (a prime power) then s ? m, if q = 2^m + 1 (a prime power) then s ? m + 1.It is also shown that all orthogonal designs of types (a, b, m ? a ? b) and (a, b), 0 ? a + b ? m, exist in orders m = 2^t and 2^t+2 · 3, t ? 1 a positive integer.     

Integral circulant graphs of prime power order with maximal energy

The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. We study the energy of integral circulant graphs, also called gcd graphs, which can be characterized by their vertex count n and a set D of divisors of n in such a way that they have vertex set Z_n and edge set {{a,b}:a,b∈Z_n,gcd(a-b,n)∈D}. Using tools from convex optimization, we analyze the maximal energy among all integral circulant graphs of prime power order p^s and varying divisor sets D. Our main result states that this maximal energy approximately lies between s(p-1)p^s-1 and twice this value. We construct suitable divisor sets for which the energy lies in this interval. We also characterize hyperenergetic integral circulant graphs of prime power order and exhibit an interesting topological property of their divisor sets.     

A Family of Binary (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">m</Emphasis>,<Emphasis Type="Italic">s</Emphasis>)-Nets of Strength 5

(t,m,s)-Nets were defined by Niederreiter [Monatshefte fur Mathematik, Vol. 104 (1987) pp. 273–337], based on earlier work by Sobol’ [Zh. Vychisl Mat. i mat. Fiz, Vol. 7 (1967) pp. 784–802], in the context of quasi-Monte Carlo methods of numerical integration. Formulated in combinatorial/coding theoretic terms a binary linear (m−k,m,s)₂-net is a family of ks vectors in F₂^m satisfying certain linear independence conditions (s is the length, m the dimension and k the strength: certain subsets of k vectors must be linearly independent). Helleseth et al. [5] recently constructed (2r−3,2r+2,2^r−1)₂-nets for every r. In this paper, we give a direct and elementary construction for (2r−3,2r+2,2^r+1)₂-nets based on a family of binary linear codes of minimum distance 6.Communicated by: T. Helleseth     

Counting subsets of the random partition and the ‘Brownian Bridge’ process

Let Ω_m be the set of partitions, ω, of a finite m-element set; induce a uniform probability distribution on Ω_m, and define X_ms(ω) as the number of s-element subsets in ω. We alow the existence of an integer-valued function n=n^(m)(t), t?[0, 1], and centering constants b_ms, 0?s? m, such that

$\text{Z}{}^{\mathrm{(m)}}\text{(t)=}\text{∑}\text{s=0}\text{n(m)(t)}\text{(X}{}_{\mathrm{ms}}\text{?b}{}_{\mathrm{ms}}\text{)}\text{√}\text{∑}\text{s=0}\text{m}\text{b}{}_{\mathrm{ms}}$

converges to the ‘Brownian Bridge’ process in terms of its finite-dimensional distributions.     

Scrambled Geometric Net Integration Over General Product Spaces

Quasi-Monte Carlo (QMC) sampling has been developed for integration over \([0,1]^s\) where it has superior accuracy to Monte Carlo (MC) for integrands of bounded variation. Scrambled net quadrature allows replication-based error estimation for QMC with at least the same accuracy and for smooth enough integrands even better accuracy than plain QMC. Integration over triangles, spheres, disks and Cartesian products of such spaces is more difficult for QMC because the induced integrand on a unit cube may fail to have the desired regularity. In this paper, we present a construction of point sets for numerical integration over Cartesian products of s spaces of dimension d, with triangles (\(d=2\)) being of special interest. The point sets are transformations of randomized (t, m, s)-nets using recursive geometric partitions. The resulting integral estimates are unbiased, and their variance is o(1 / n) for any integrand in \(L^2\) of the product space. Under smoothness assumptions on the integrand, our randomized QMC algorithm has variance \(O(n^{-1 - 2/d} (\log n)^{s-1})\), for integration over s-fold Cartesian products of d-dimensional domains, compared to \(O(n^{-1})\) for ordinary MC.     

On solutions of “equations in symmetric groups”

Let x?S_n, the symmetric group on n symbols. Let θ? Aut(S_n) and let the automorphim order of x with respect to θ be defined by

$\text{γθ(x)=}\text{min}\text{{k:x xθ xθ}{}^2\text{? xθ}{}^{\mathrm{k?1}}\text{=1}}$

where xθ is the image of x under θ. Let α_g? Aut(S_n) denote conjugation by the element g?S_n. Let where s and k are positive integers and $\text{a}\text{b}$ denotes a divides b. Further h(s, k : n) ≡ b(1; s, k : n), where 1 denotes the identity automorphim. If g?S_n let c = f(g, s) denote the number of symbols in g which are in cycles of length not dividing the integer s, and let g_s denote the product of all cycles in g whose lengths do not divide s. Then g_s moves c symbols. The main results proved are: (1) recursion: if n ? c + 1 and t = n ? c ? 1 then $\text{b(g; s, 1:n)=∑}{}_{\mathrm{<mtext>i</mtext><mtext>s</mtext>}}\text{b(g; s, 1:n?1)(}{}^{\mathrm{t}}{}_{\mathrm{i?1}}\text{(i?1)!}$ (2) reduction: b(g; s, 1 : c)h(s, 1 : i) = b(g; s, 1 : i + c); (3) distribution: let D(θ, n) ≡ {(k, b) : k?Z⁺ and b = b(θ; 1, k : n) ≠ 0}; then D(θ, m) = D(φ, m) ∨ m ? N = N(θ, φ) iff θ is conjugate to φ; (4) evaluation: the number of cycles in g_s^s of any given length is smaller than the smallest prime dividing s iff b(g_s; s, 1 : c) = 1. If g = (12 … p^m)^t and $\text{sk}\text{p}{}^{\mathrm{m}}$ then $\text{b(g;s,k:p}{}^{\mathrm{m}}\text{) {}{}^0{}_{\mathrm{\pm 1}}\text{(}\text{mod}\text{p)}$.     

An invariance of the geometric mean with respect to Stolarsky mean-type mappings

We determine all pairs of Stolarsky means (E _r,s , E _k,m ) such that G o (E _r,s , E _k,m ) = G, where G = E _0,0 is the geometric mean. The convergence of the sequences of iterates of the mean-type mapping (E _r,s , E _k,m ) to the mapping (G, G) is considered. An application to a functional equation is given.     

Dirichlet series related to the Riemann zeta function

A study is made of the function H(s, z) defined by analytic continuation of the Dirichlet series H(s, z) = Σ_n=1^∞n^?sΣ_m=1ⁿm^?z, where s and z are complex variables. For each fixed z it is shown that H(s, z) exists in the entire s-plane as a meromorphic function of s, and its poles and residues are determined. Also, for each fixed s ≠ 1 it is shown that H(s, z) exists in the entire z-plane as a meromorphic function of z, and again its poles and residues are determined. Two different representations of H(s, z) are given from which a reciprocity law, H(s, z) + H(z, s) = ζ(s) ζ(z) + ζ(s + z), is deduced. For each integer q ≥ 0 the function values H(s, ?q) and H(?q, s) are expressed in terms of the Riemann zeta function. Similar results are also obtained for the Dirichlet series T(s, z) = Σ_n=1^∞n^?sΣ_m=1ⁿm^?z (m + n)^?1. Applications include identities previously obtained by Ramanujan, Williams, and Rao and Sarma.