ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

13. Combinatorics

1991 MS Classification: 05, 11, 14, 94 Niederreiter, Harald, Austrian Academy of Sciences, Austria Nets, (t, s)-sequences, and algebraic curves over finite fields with many rational points

Nets and (t, s)-sequences are finite point sets, respectively infinite sequences, satisfying strong uniformity properties with regard to their distribution in the s-dimensional unit cube I^{s} = [0, 1]^{s}. The general theory of these combinatorial objects was first developed by the speaker [2], and they have attracted a lot of interest in recent years because of their applications to difficult problems of scientific computing, such as high-dimensional numerical integration. For a given dimension s ≥ 1 and integers b ≥ 2 and 0 ≤ t ≤ m, a (t, m, s)-net in base b is a point set P consisting of b^{m} points in I^{s} such that every subinterval J of I^{s} of the form J = ∏_{i=1}^{s}[a_{i}b^{−d_{i}}, (a_{i} + 1)b^{−d_{i}}) with integers d_{i} ≥ 0 and 0 ≤ a_{i} < b^{d_{i}} for 1 ≤ i ≤ s and with Vol(J) = b^{t−m} contains exactly b^{t} points of P. Furthermore, a sequence x_{0}, x_{1}, … of points in I^{s} is a (t, s)-sequence in base b if for all integers k ≥ 0 and m > t, the point set consisting of the x_{n} with kb^{m} ≤ n < (k + 1)b^{m} is a (t, m, s)-net in base b. It was realized early on (see [2], [3]) that (t, m, s)-nets are closely linked with classical combinatorial objects such as MOLS and orthogonal arrays. In fact, there is a combinatorial equivalence between (t, m, s)-nets and certain generalized orthogonal arrays. This implies combinatorial obstructions to the existence of (t, m, s)-nets and (t, s)-sequences and leads to the lower bounds in the recent tables [1] for the quality parameter t. Powerful methods of constructing (t, m, s)-nets and (t, s)-sequences can be based on algebraic geometry, and the currently best results are achieved by using algebraic curves over finite fields with many rational points (see [4], [5]). For a prime power q and an integer g ≥ 0, let N_{q}(g) be the maximum number of F_{q}-rational points that a smooth, projective, absolutely irreducible algebraic curve over F_{q} of genus g can have. Then it has been shown, for instance, that for every q and every dimension s ≥ 1 there exists a (V_{q}(s), s)-sequence in base q, where V_{q}(s) = min{g ≥ 0 : N_{q}(g) ≥ s + 1}. In view of this connection, the speaker and C. P. Xing have embarked on a systematic search for algebraic curves over F_{q} with many rational points, in order to obtain good lower bounds for N_{q}(g); upper bounds can be derived by a known technique from Weil’s explicit formula for the number of rational points in terms of the zeta function of an algebraic curve over F_{q}. This research has led to new principles for the construction of algebraic curves over F_{q} with many rational points, among them methods based on Hilbert class fields and Drinfeld modules of rank 1. The full paper will contain an up-to-date table of lower and upper bounds on N_{q}(g) for q = 2, 3, 4, 5, 8, 9, 16, 27 and all g ≤ 50. Related work of the speaker and C. P. Xing [6] used algebraic curves over F_{q} with many rational points, or equivalently global function fields over F_{q} with many rational places, to produce an improvement on the classical Gilbert-Varshamov bound for the existence of good linear codes over F_{q} in the case where q is a sufficiently large composite nonsquare. This extends the well-known result in [7] for squares q.

References

[1] A. T. Clayman, K. M. Lawrence, G. L. Mullen, H. Niederreiter, and N. J. A. Sloane, Updated tables of parameters of (t, m, s)-nets, J. Combinatorial Designs, to appear.

[2] H. Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104, 273–337 (1987).

[3] H. Niederreiter, Orthogonal arrays and other combinatorial aspects in the theory of uniform point distributions in unit cubes, Discrete Math. 106/107, 361–367 (1992).

[4] H. Niederreiter and C. P. Xing, Low-discrepancy sequences and global function fields with many rational places, Finite Fields Appl. 2, 241– 273 (1996).

[5] H. Niederreiter and C. P. Xing, Quasirandom points and global function fields, Finite Fields and Applications (S. Cohen and H. Niederreiter, eds.), pp. 269–296, Cambridge Univ. Press, Cambridge, 1996.

[6] H. Niederreiter and C. P. Xing, Towers of global function fields with asymptotically many rational places and an improvement on the Gilbert-Varshamov bound, Math. Nachr. , to appear.

[7] M. A. Tsfasman, S. G. Vlǎdut, and T. Zink, Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound, Math. Nachr. 109, 21–28 (1982).