Polynomials and spatial Pick-type theorems

Pick's theorem about the area of a simple lattice planar polygon has many extensions and generalizations even in the planar case. The theorem has also higher-dimensional generalizations, which are not as commonly known as the 2-dimensional case. The aim of the paper is, on one hand, to give a few new higher-dimensional generalizations of Pick's theorem and, on the other hand, collect known ones. We also study some relationships between lattice points in a lattice polyhedron which lead to some new Pick-type formulae. Another purpose of this paper is to pose several problems related to the subject of higher-dimensional Pick-type theorems. We hope that the paper may popularize the idea of determining the volume of a lattice polyhedron P by reading information contained in a lattice and the tiling of the space generated by the lattice.     

数论及其应用 献给陈省身先生九十大寿

众所周知 ,数论是数学中最古老最纯粹最优美的一个学科 .不过鲜为人知的还是 ,数论同时也是一门应用性极强的应用数学学科 .著名国际数学大师陈省身教授早在 1 992年精辟地指出 :“数学中我愿意把数论看作应用数学”,“我想数学中有两个很重要的数学部门 ,一个是数论 ,另一个是理论物理”.在本文中 ,我们将先扼要介绍一下数论中的一些基本概念、几个主要难题 ,紧接着我们要介绍数论 (尤其是数论中的难题 )在现代密码学 (包括网络与信息安全 )与计算机科学 (尤其是快速并行计算 )中的应用     

The simultaneous packing and covering constants in the plane

In 1950, C.A. Rogers introduced and studied two simultaneous packing and covering constants for a convex body and obtained the first general upper bound. Afterwards, these constants have attracted the interests of many authors because, besides their own geometric significance, they are closely related to the packing densities and the covering densities of the convex body, especially to the Minkowski-Hlawka theorem. However, so far our knowledge about them is still very limited. In this paper we will determine the optimal upper bound of the simultaneous packing and covering constants for two-dimensional centrally symmetric convex domains, and characterize the domains attaining this upper bound.     

Rep-tiling Euclidean space

Summary Arep-tiling is a self replicating, lattice tiling ofR ⁿ .Lattice tiling means a tiling by translates of a single compact tile by the points of a lattice, andself-replicating means that there is a non-singular linear mapø: R ⁿ Rⁿ such that, for eachT , the imageø(T) is, in turn, tiled by . This topic has recently come under investigation, not only because of its recreational appeal, but because of its application to the theory of wavelets and to computer addressing. The paper presents an exposition of some recent results on rep-tiling, including a construction of essentially all rep-tilings of Euclidean space. The construction is based on radix representation of points of a lattice. One particular radix representation, called thegeneralized balanced ternary, is singled out as an example because of its relevance to the field of computer vision.     

On the Packing Densities and the Covering Densities of the Cartesian Products of Convex Bodies

In this article we study the following problem: Is the covering (packing) density of a Cartesian product of two convex bodies always equal to the product of their corresponding covering (packing) densities? For the covering case we get a negative answer. For the packing case we get a combinatorial version which seems to be important for its own interest.     

A primer of substitution tilings of the Euclidean plane

This paper is intended to provide an introduction to the theory of substitution tilings. For our purposes, tiling substitution rules are divided into two broad classes: geometric and combinatorial. Geometric substitution tilings include self-similar tilings such as the well-known Penrose tilings; for this class there is a substantial body of research in the literature. Combinatorial substitutions are just beginning to be examined, and some of what we present here is new. We give numerous examples, mention selected major results, discuss connections between the two classes of substitutions, include current research perspectives and questions, and provide an extensive bibliography. Although the author attempts to represent the field as a whole, the paper is not an exhaustive survey, and she apologizes for any important omissions.     

Simultaneous Packing and Covering in the Euclidean Plane

 In this article we study the simultaneous packing and covering constants of two-dimensional centrally symmetric convex domains. Besides an identity result between translative case and lattice case and a general upper bound, exact values for some special domains are determined. Similar to Mahler and Reinhardt’s result about packing densities, we show that the simultaneous packing and covering constant of an octagon is larger than that of a circle. (Received 17 January 2001; in revised form 13 July 2001)     

Some remarks concerning kissing numbers,blocking numbers and covering numbers

This article shows an inequality concerning blocking numbers and Hadwiger's covering numbers and presents a strange phenomenon concerning kissing numbers and blocking numbers. As a simple corollary, we can improve the known upper bounds for Hadwiger's covering numbers ford-dimensional centrally symmetric convex bodies to 3 ^d –1.     

Partially finite convex programming,Part I: Quasi relative interiors and duality theory

We study convex programs that involve the minimization of a convex function over a convex subset of a topological vector space, subject to a finite number of linear inequalities. We develop the notion of the quasi relative interior of a convex set, an extension of the relative interior in finite dimensions. We use this idea in a constraint qualification for a fundamental Fenchel duality result, and then deduce duality results for these problems despite the almost invariable failure of the standard Slater condition. Part II of this work studies applications to more concrete models, whose dual problems are often finite-dimensional and computationally tractable.     

Rhombus filtrations and Rauzy algebras

Peach introduced rhombal algebras associated to quivers given by tilings of the plane by rhombi. We develop general techniques to analyze rhombal algebras, including a filtration by what we call rhombus modules. We introduce a way to relate the infinite-dimensional rhombal algebra corresponding to a complete tiling of the plane to finite-dimensional algebras corresponding to finite portions of the tiling. Throughout, we apply our general techniques to the special case of the Rauzy tiling, which is built in stages reflecting an underlying self-similarity. Exploiting this self-similar structure allows us to uncover interesting features of the associated finite-dimensional algebras, including some of the tree classes in the stable Auslander-Reiten quiver.     

THE BIOGENETIC LAW AND ITS INFLUENCE ON THEORIES OF LEARNING MATHEMATICS

Reference to the history of mathematics has been widely used in discussions of the development of curricula, the problems students have in learning mathematics, and the development of concepts in the individual. This paper examines the background to the "Biogenetic Law" [1] which has influenced so much thinking in educational theory, and the use of the "principle of parallelism" where individual development is claimed to mirror the historical development of the subject matter. Interpretations of the history of mathematics which are used to justify these claims are examined, and the universality of the supposed concepts is challenged. Questions are raised about some of the fundamental tenets of Piagetian epistemology.     

A note on powers in finite fields

The study of solutions to polynomial equations over finite fields has a long history in mathematics and is an interesting area of contemporary research. In recent years, the subject has found important applications in the modelling of problems from applied mathematical fields such as signal analysis, system theory, coding theory and cryptology. In this connection, it is of interest to know criteria for the existence of squares and other powers in arbitrary finite fields. Making good use of polynomial division in polynomial rings over finite fields, we have examined a classical criterion of Euler for squares in odd prime fields, giving it a formulation that is apt for generalization to arbitrary finite fields and powers. Our proof uses algebra rather than classical number theory, which makes it convenient when presenting basic methods of applied algebra in the classroom.     

π1-classification of real arrangements with up to eight lines

One of the open questions in the geometry of line arrangements is to what extent does the incidence lattice of an arrangement determine its fundamental group. Line arrangements of up to 6 lines were recently classified by K.M. Fan (Michigan Math. J. 44(2) (1997) 283), and it turns out that the incidence lattice of such arrangements determines the projective fundamental group. We use actions on the set of wiring diagrams, introduced in (Garber et al. (J. Knot Theory Ramf.), to classify real arrangements of up to 8 lines. In particular, we show that the incidence lattice of such arrangements determines both the affine and the projective fundamental groups.     

Fractal tiles associated with shift radix systems

Shift radix systems form a collection of dynamical systems depending on a parameter r which varies in the d-dimensional real vector space. They generalize well-known numeration systems such as beta-expansions, expansions with respect to rational bases, and canonical number systems. Beta-numeration and canonical number systems are known to be intimately related to fractal shapes, such as the classical Rauzy fractal and the twin dragon. These fractals turned out to be important for studying properties of expansions in several settings.In the present paper we associate a collection of fractal tiles with shift radix systems. We show that for certain classes of parameters r these tiles coincide with affine copies of the well-known tiles associated with beta-expansions and canonical number systems. On the other hand, these tiles provide natural families of tiles for beta-expansions with (non-unit) Pisot numbers as well as canonical number systems with (non-monic) expanding polynomials.We also prove basic properties for tiles associated with shift radix systems. Indeed, we prove that under some algebraic conditions on the parameter r of the shift radix system, these tiles provide multiple tilings and even tilings of the d-dimensional real vector space. These tilings turn out to have a more complicated structure than the tilings arising from the known number systems mentioned above. Such a tiling may consist of tiles having infinitely many different shapes. Moreover, the tiles need not be self-affine (or graph directed self-affine).     

Lattice translates of a polytope and the Frobenius problem

This paper considers the Frobenius problem: Givenn natural numbersa ₁,a ₂,...a _n such that their greatest common divisor is 1, find the largest natural number that is not expressible as a nonnegative integer combination of them. This problem can be seen to be NP-hard. For the casesn=2,3 polynomial time algorithms, are known to solve it. Here a polynomial time algorithm is given for every fixedn. This is done by first proving an exact relation between the Frobenius problem and a geometric concept called the covering radius. Then a polynomial time algorithm is developed for finding the covering radius of any polytope in a fixed number of dimensions. The last algorithm relies on a structural theorem proved here that describes for any polytopeK, the setK+ ^h ={xx ⁿ ;x=y+z;yK;z ⁿ } which is the portion of space covered by all lattice translates ofK. The proof of the structural theorem relies on some recent developments in the Geometry of Numbers. In particular, it uses a theorem of Kannan and Lovász [11], bounding the width of lattice-point-free convex bodies and the techniques of Kannan, Lovász and Scarf [12] to study the shapes of a polyhedron obtained by translating each facet parallel, to itself. The concepts involved are defined from first principles. In a companion paper [10], I extend the structural result and use that to solve a general problem of which the Frobenius problem is a special case.Supported by NSF-Grant CCR 8805199     

Asymptotic arc-components of unimodal inverse limit spaces

We consider the inverse limit space (I,f) of a unimodal bonding map f as fixed bonding map. If f has a periodic turning point, then (I,f) has a finite non-empty set of asymptotic arc-components. We show how asymptotic arc-components can be determined from the kneading sequence of f. This gives an alternative to the substitution tiling space approach taken by Barge and Diamond [Ergodic Theory Dynamical Systems 21 (2001) 1333].     

Thue type problems for graphs, points, and numbers

A sequence S=s₁s₂…s_n is said to be nonrepetitive if no two adjacent blocks of S are the same. A celebrated 1906 theorem of Thue asserts that there are arbitrarily long nonrepetitive sequences over the set {0,1,2}. This result is the starting point of Combinatorics on Words—a wide area with many deep results, sophisticated methods, important applications and intriguing open problems.The main purpose of this survey is to present a range of new directions relating Thue sequences more closely to Graph Theory, Combinatorial Geometry, and Number Theory. For instance, one may consider graph colorings avoiding repetitions on paths, or colorings of points in the plane avoiding repetitions on straight lines. Besides presenting a variety of new challenges we also recall some older problems of this area.     

A Minkowski-type theorem for covering minima in the plane

For a convex bodyKE ² and a latticeLE ² let _i (K, L),i=1, 2, denote its covering minima introduced by Kannan and Lovasz. We show ₁(K, L) ₂(K, L)V(K)3/4 det(L), whereV denotes the area. This inequality is tight and there are five different cases of equality.     

An ‘odd’ formula for the volume of three-dimensional lattice polyhedra

Let be the tiling of R ³ with unit cubes whose vertices belong to the fundamental lattice L ₁ of points with integer coordinates. Denote by L _n the lattice consisting of all points x in R ³ such that nx belongs to L ₁. When the vertices of a polyhedron P in R ³ are restricted to lie in L ₁ then there is a formula which relates the volume of P to the numbers of all points of two lattices L ₁ and L _n lying in the interior and on the boundary of P. In the simplest case of the lattices L ₁ and L ₂ there are 27 points in each cube from whose relationships to the polyhedron P must be examined. In this note we present a new formula for the volume of lattice polyhedra in R ³ which involves only nine points in each cube of : one from L ₂ and eight belonging to L ₄. Another virtue of our formula is that it does not employ any additional parameters, such as the Euler characteristic.