On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

On directional convexity

Motivated by problems from calculus of variations and partial differential equations, we investigate geometric properties of D-convexity. A function f: R ^d → R is called D-convex, where D is a set of vectors in R ^d, if its restriction to each line parallel to a nonzero v ∈ D is convex. The D-convex hull of a compact set A ⊂ R ^d, denoted by co^D(A), is the intersection of the zero sets of all nonnegative D-convex functions that are zero on A. It also equals the zero set of the D-convex envelope of the distance function of A. We give an example of an n-point set A ⊂ R ² where the D-convex envelope of the distance function is exponentially close to zero at points lying relatively far from co ^D(A), showing that the definition of the D-convex hull can be very nonrobust. For separate convexity in R ³ (where D is the orthonormal basis of R ³), we construct arbitrarily large finite sets A with co ^D(A) ≠ A whose proper subsets are all equal to their D-convex hull. This implies the existence of analogous sets for rank-one convexity and for quasiconvexity on 3 × 3 (or larger) matrices. This research was supported by Charles University Grants No. 158/99 and 159/99.     

Points surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

On Kalai’s Conjectures Concerning Centrally Symmetric Polytopes

In 1989, Kalai stated three conjectures A, B, C of increasing strength concerning face numbers of centrally symmetric convex polytopes. The weakest conjecture, A, became known as the “3 ^d -conjecture.” It is well known that the three conjectures hold in dimensions d≤3. We show that in dimension 4 only conjectures A and B are valid, while conjecture C fails. Furthermore, we show that both conjectures B and C fail in all dimensions d≥5.     

Geometric progressions in sumsets over finite fields

Given two sets A, B í \Bbb F_q^d{\cal A}, {\cal B}\subseteq {\Bbb F}_q^d , the set of d dimensional vectors over the finite field \Bbb F_q{\Bbb F}_q with q elements, we show that the sumset A+B = {a+b | a ? A, b ? B}{\cal A}+{\cal B} = \{{\bf a}+{\bf b}\ \vert\ {\bf a} \in {\cal A}, {\bf b} \in {\cal B}\} contains a geometric progression of length k of the form vΛ ^j , where j = 0,…, k − 1, with a nonzero vector v ? \Bbb F_q^d{\bf v} \in {\Bbb F}_q^d and a nonsingular d × d matrix Λ whenever # A # B 3 20 q^2d-2/k\# {\cal A} \# {\cal B} \ge 20 q^{2d-2/k} . We also consider some modifications of this problem including the question of the existence of elements of sumsets on algebraic varieties.     

到三定点相对距离的和等于定数的点的轨迹

本文研究了相对测度空间中的距离问题. 利用质点几何的理论方法获得如下结果:对任意给定的实数, 满足条件dT (P,A) + dT (P,B) + dT (P,C) =τ的点P的轨迹是凸十二边形或九边形(其中T:=ABC 是由给定的不同三点A, B, C构成的三角形), 所得结果丰富了相对距离研究领域的内容.     

The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

Symplectic modules over overrings of polynomial rings

Let B be a commutative Noetherian ring of dimension d and let S be a set of all monic polynomials in B[X]. Let A be a subring of S ⁻¹ B[X] which contains B[X]. Let P be a symplectic A-module of rank 2n ≥ d, n > 0. Then we prove that ESp (A ² ⊥ P, 〈,〉) acts transitively on Um (A ² ⊕ P).     

A Sufficient Condition for the Existence of Large Empty Convex Polygons

Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R ^d for each odd d≥ 3 .     

A Sufficient Condition for the Existence of Large Empty Convex Polygons

   Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R ^d for each odd d≥ 3 .     

On Functional Separately Convex Hulls

Let D be a set of vectors in R ^d . A function f: R ^d → R is called D-convex if its restriction to each line parallel to a nonzero vector of D is a convex function. For a set A⊆ R ^d , the functional D-convex hull of A, denoted by co ^D (A) , is the intersection of the zero sets of all nonnegative D -convex functions that are 0 on A . We prove some results concerning the structure of functional D -convex hulls, e.g., a Krein—Milman-type theorem and a result on separation of connected components. We give a polynomial-time algorithm for computing co ^D (A) for a finite point set A (in any fixed dimension) in the case of D being a basis of R ^d (the case of separate convexity). This research is primarily motivated by questions concerning the so-called rank-one convexity, which is a particular case of D -convexity and is important in the theory of systems of nonlinear partial differential equations and in mathematical modeling of microstructures in solids. As a direct contribution to the study of rank-one convexity, we construct a configuration of 20 symmetric 2 x 2 matrices in a general (stable) position with a nontrivial functionally rank-one convex hull (answering a question of K. Zhang on the existence of higher-dimensional nontrivial configurations of points and matrices). Received October 3, 1995, and in revised form June 24, 1996.     

Randomly fractionally integrated processes

Philippe et al. [9], [10] introduced two distinct time-varying mutually invertible fractionally integrated filters A(d), B(d) depending on an arbitrary sequence d = (d _t ) _t∈ℤ of real numbers; if the parameter sequence is constant d _t ≡ d, then both filters A(d) and B(d) reduce to the usual fractional integration operator (1 − L)^−d . They also studied partial sums limits of filtered white noise nonstationary processes A(d)ε _t and B(d)ε _t for certain classes of deterministic sequences d. The present paper discusses the randomly fractionally integrated stationary processes X _t ^A = A(d)ε _t and X _t ^B = B(d)ε _t by assuming that d = (d _t , t ∈ ℤ) is a random iid sequence, independent of the noise (ε _t ). In the case where the mean , we show that large sample properties of X ^A and X ^B are similar to FARIMA(0, , 0) process; in particular, their partial sums converge to a fractional Brownian motion with parameter . The most technical part of the paper is the study and characterization of limit distributions of partial sums for nonlinear functions h(X _t ^A ) of a randomly fractionally integrated process X _t ^A with Gaussian noise. We prove that the limit distribution of those sums is determined by a conditional Hermite rank of h. For the special case of a constant deterministic sequence d _t , this reduces to the standard Hermite rank used in Dobrushin and Major [2]. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 1, pp. 3–28, January–March, 2007.     

Functional BKR Inequalities,and their Duals,with Applications

The inequality conjectured by van den Berg and Kesten (J. Appl. Probab. 22, 556–569, 1985), and proved by Reimer (Comb. Probab. Comput. 9, 27–32, 2000), states that for A and B events on S, a finite product of finite sets, and P any product measure on S,

On Large Deviations of Multivariate Heavy-Tailed Random Walks

Let {S _n ;n=1,2,…} be a random walk in R ^d and E(S ₁)=(μ ₁,…,μ _d ). Let a _j >μ _j for j=1,…,d and A=(a ₁,∞)×⋅⋅⋅×(a _d ,∞). We are interested in the probability P(S _n /n∈A) for large n in the case where the components of S ₁ are heavy tailed. An objective is to associate an exact power with the aforementioned probability. We also derive sharper asymptotic bounds for the probability and show that in essence, the occurrence of the event {S _n /n∈A} is caused by large single increments of the components in a specific way.      

A result about determinantal divisors

Let Rbe a principal ideal ringR_n the ring of n× nmatrices over R, and d_k (A) the kth determinantal divisor of Afor 1 ? k? n, where Ais any element of R_n , It is shown that if A,BεR_n , det(A) det(B:) ≠ 0, then d_k (AB) ≡ 0 mod d_k (A) d_k (B). If in addition (det(A), det(B)) = 1, then it is also shown that d_k (AB) = d_k (A) d_k (B). This provides a new proof of the multiplicativity of the Smith normal form for matrices with relatively prime determinants.     

On the description of overgroups of E(m,R)?E(n,R)

The subgroups E(m,R) ⊗ E(n,R) ≤ H ≤ G = GL(mn,R) are studied under the assumption that the ring R is commutative and m, n ≥ 3. The group GL _m ⊗GL _n is defined by equations, the normalizer of the group E(m,R) ⊗ E(n,R) is calculated, and with each intermediate subgroup H it is associated a uniquely determined lower level (A,B,C), where A,B,C are ideals in R such that mA,A ² ≤ B ≤ A and nA,A ² ≤ C ≤ A. The lower level specifies the largest elementary subgroup satisfying the condition E(m, n,R, A,B,C) ≤ H. The standard answer to this problem asserts that H is contained in the normalizer N _G (E(m,n,R, A,B,C)). Bibliography: 46 titles.     

Arithmetic of Finite Ordered Sets: Cancellation of Exponents,II

Garrett Birkhoff conjectured in 1942 that when A, B, P are finite posets satisfying A ^PB ^P, then AB. We show that this is true. Further, we introduce an operation C(A ^B), related to Garrett Birkhoff's exponentiation, and determine the structure of the algebra of isomorphism types of finite posets under the operations induced by A+B, A×B, and C(A ^B). Every finite +-indecomposable and ×-indecomposable poset A of more than one element is expressible for unique (up to isomorphism) E and P as AC(E ^P) where P is connected and E is indecomposable for all three operations.     

Finite sets which contain their Radon points

A point r is a Radon point of a finite set S if r=conv Aconv B, where A and B are disjoint subsets of S. Two characterizations are given for those finite sets in R ^d which contain their Radon points, and the convex hull of such a set is described.     

Hausdorff measures of different dimensions are not Borel isomorphic

We show that Hausdorff measures of different dimensions are not Borel isomorphic; that is, the measure spaces (ℝ, B, H ^s ) and (ℝ, B, H ^t ) are not isomorphic if s ≠ t, s, t ∈ [0, 1], where B is the σ-algebra of Borel subsets of ℝ and H ^d is the d-dimensional Hausdorff measure. This answers a question of B. Weiss and D. Preiss. To prove our result, we apply a random construction and show that for every Borel function ƒ: ℝ → ℝ and for every d ∈ [0, 1] there exists a compact set C of Hausdorff dimension d such that ƒ(C) has Hausdorff dimension ≤ d. We also prove this statement in a more general form: If A ⊂ ℝⁿ is Borel and ƒ: A → ℝ^m is Borel measurable, then for every d ∈ [0, 1] there exists a Borel set B ⊂ A such that dim B = d·dim A and dim ƒ(B) ≤ d·dim ƒ (A). Partially supported by the Hungarian Scientific Research Fund grant no. T 49786.     

On inhomogeneous diophantine approximation and Hausdorff dimension

Let Γ = Z A + Z ⁿ  ⊂ R ⁿ be a dense subgroup of rank n + 1 and let [^(w)] \hat{w} (A) denote the exponent of uniform simultaneous rational approximation to the generating point A. For any real number v ≥  [^(w)] \hat{w} (A), the Hausdorff dimension of the set B _v of points in R ⁿ that are v-approximable with respect to Γ is shown to be equal to 1/v.