On the distribution of the summands of partitions in residue classes

Summary It is proved that the summands of almost all partitions of nare well-distributed modulo dfor dup to d= n^1/2-ε.     

Gaussian partitions

Let V=V(n,q) denote the finite vector space of dimension n over the finite field with q elements. A subspace partition of V is a collection Π of subspaces of V such that each 1-dimensional subspace of V is in exactly one subspace of Π. In a recent paper, we proved some strong connections between the lattice of the subspace partitions of V and the lattice of the set partitions of n={1,…,n}. We now define a Gaussian partition of [n] _q =(q ⁿ −1)/(q−1) to be a nonincreasing sequence of positive integers formed by ordering all elements of some multiset {dim(W):W∈Π}, where Π is a subspace partition of V. The Gaussian partition function gp(n,q) is then the number of all Gaussian partitions of [n] _q , and is naturally analogous to the classical partition function p(n). In this paper, we initiate the study of gp(n,q) by exhibiting all Gaussian partitions for small n. In particular, we determine gp(n,q) as a polynomial in q for n≤5, and find a lower bound for gp(6,q).     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

Degree-uniform lower bound on the weights of polynomials with given sign function

A Boolean function f: {0, 1} ⁿ → {0, 1} is called the sign function of an integer polynomial p of degree d in n variables if it is true that f(x) = 1 if and only if p(x) > 0. In this case the polynomial p is called a threshold gate of degree d for the function f. The weight of the threshold gate is the sum of the absolute values of the coefficients of p. For any n and d ≤ D ≤ $\frac{{\varepsilon n^{1/5} }} {{\log n}} $\frac{{\varepsilon n^{1/5} }} {{\log n}} we construct a function f such that there is a threshold gate of degree d for f, but any threshold gate for f of degree at most D has weight 2^{(dn)d /D4d} 2^{(\delta n)^d /D^{4d} } , where ɛ > 0 and δ > 0 are some constants. In particular, if D is constant, then any threshold gate of degree D for our function has weight 2^{W(nd )}2^{\Omega (n^d )} . Previously, functions with these properties have been known only for d = 1 (and arbitrary D) and for D = d. For constant d our functions are computable by polynomial size DNFs. The best previous lower bound on the weights of threshold gates for such functions was 2^Ω(n). Our results can also be translated to the case of functions f: {−1, 1} ⁿ → {−1, 1}.     

Worst-case minimum rectilinear steiner trees in all dimensions

It is proved that the length of the longest possible minimum rectilinear Steiner tree ofn points in the unitd-cube is asymptotic toβ _dn^(d−1)/d , whereβ _d is a constant that depends on the dimensiond≥2. A method of Chung and Graham (1981) is generalized to dimensiond to show that 1≤β _d≤d4^(1−d)/d . In addition to replicating Chung and Graham's exact determination ofβ ₂=1, this generalization yields new bounds such as 1≤β ₃<1.191 and .     

Analysis of some new partition statistics

We study several statistics for integer partitions: for a random partition of an integer n we consider the average size of the smallest gap (missing part size), the multiplicity of the largest part, and the largest repeated part size. Furthermore, we estimate the number of gap-free partitions of n. 2000 Mathematics Subject Classification Primary—05A17; Secondary—11P82 Dedicated to Helmut Prodinger on the occasion of his 50th birthday P.J. Grabner is supported by the START-project Y96-MAT of the Austrian Science Fund. This material is based upon work supported by the National Research Foundation under grant number 2053740.     

Structure Theorem for (d, g, h)-Maps

The (3x + 1)-Map, T, acts on the set, Π, of positive integers not divisible by 2 or 3. It is defined by , where k is the largest integer for which T (x) is an integer. The (3x + 1)-Conjecture asks if for every x ε Π there exists an integer, n, such that T ⁿ (x) = 1. The Statistical (3x + 1)-Conjecture asks the same question, except for a subset of Π of density 1. The Structure Theorem proven in [𝕊] shows that infinity is in a sense a repelling point, giving some reasons to expect that the (3x + 1)-Conjecture may be true. In this paper, we present the analogous theorem for some generalizations of the (3x + 1)-Map, and expand on the consequences derived in [𝕊]. The generalizations we consider are determined by positive coprime integers, d and g, with g > d ≥ 2, and a periodic function, h (x). The map T is defined by the formula , where k is again the largest integer for which T (x) is an integer. We prove an analogous Structure Theorem for (d, g, h)-Maps, and that the probability distribution corresponding to the density converges to the Wiener measure with the drift and positive diffusion constant. This shows that it is natural to expect that typical trajectories return to the origin if and escape to infinity otherwise. Received: 18 April 2002     

Arithmetic Properties of Summands of Partitions II

Let d∈ℕ, d ≥ 2. We prove that a positive proportion of partitions of an integer n satisfies the following : for all 1≤ a < b≤ d, the number of the parts congruent to a (mod d) is greater than the number of the parts congruent to b (mod d). We also show that for almost all partitions the rate of the number of square free parts is . 2000 Mathematics Subject Classification: Primary—11P82     

Stabbing Simplices by Points and Flats

The following result was proved by Bárány in 1982: For every d≥1, there exists c _d >0 such that for every n-point set S in ℝ ^d , there is a point p∈ℝ ^d contained in at least c _d n ^d+1−O(n ^d ) of the d-dimensional simplices spanned by S. We investigate the largest possible value of c _d . It was known that c _d ≤1/(2 ^d (d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c _d ≤(d+1)^−(d+1), and we conjecture that this estimate is tight. The best known lower bound, due to Wagner, is c _d ≥γ _d :=(d ²+1)/((d+1)!(d+1) ^d+1); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than γ _d n ^d+1+O(n ^d ) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved.     

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 .     

On the distribution of the summands of unequal partitions in residue classes

Summary It is proved that the summands of almost all unequal partitions of nare well-distributed modulo dfor d=o(n^1/2).     

Irreducible characters of the group S n that are semiproportional on A n

Previously, we dubbed the conjecture that the alternating group A_n has no semiproportional irreducible characters for any natural n [1]. This conjecture was then shown to be equivalent to the following [3]. Let α and β be partitions of a number n such that their corresponding characters χ^α and χ^β in the group S_n are semiproportional on A_n. Then one of the partitions α or β is self-associated. Here, we describe all pairs (α, β) of partitions satisfying the hypothesis and the conclusion of the latter conjecture. Supported by RFBR (grant No. 07-01-00148) and by RFBR-NSFC (grant No. 05-01-39000). __________ Translated from Algebra i Logika, Vol. 47, No. 2, pp. 135–156, March–April, 2008.     

On the generation of clones containing near-unanimity operations

It is a well-known consequence of the Baker-Pixley-Theorem that any clone containing a near-unanimity operation is finitely generated, leading to the question what arity the generating functions must have. In this paper, we show that, for arbitrary d ≥ 2 and large enough n, (n − 1) ^d − 1 is the smallest integer k such that, for every clone C on an n-element set that contains a (d + 1)-ary near-unanimity operation, C ^(k) generates C.     

New Combinatorial Descriptions of the Triangulations of Cyclic Polytopes and the Second Higher Stasheff–Tamari Posets

This paper is concerned with the d-dimensional cyclic polytope with n vertices, C(n,d), and the set of its triangulations, S(n,d). We show that there is a bijection between S(n,d) and certain partitions of the set of increasing d-tuples on the integers 1 to n–1. We give a combinatorial characterization of the second higher Stasheff–Tamari poset, which is a partial ordering of S(n,d), and we determine its 2-dimension. There is a well-known representation of triangulations of an n-gon by right bracket vectors. We generalize this to cyclic polytopes of higher dimensions.     

A Note About Critical Percolation on Finite Graphs

In this note we study the geometry of the largest component C₁\mathcal {C}_{1} of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. (Random Struct. Algorithms 27:137–184, 2005). There it is shown that this component is of size n ^2/3, and here we show that its diameter is n ^1/3 and that the simple random walk takes n steps to mix on it. By Borgs et al. (Ann. Probab. 33:1886–1944, 2005), our results apply to critical percolation on several high-dimensional finite graphs such as the finite torus \mathbbZ_n^d\mathbb{Z}_{n}^{d} (with d large and n→∞) and the Hamming cube {0,1} ⁿ .     

Q 2-free Families in the Boolean Lattice

For a family F{{\cal F}} of subsets of [n] = {1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that F{{\cal F}} is P-free if it does not contain a subposet isomorphic to P. Let ex(n, P) be the largest size of a P-free family of subsets of [n]. Let Q ₂ be the poset with distinct elements a, b, c, d, a < b,c < d; i.e., the 2-dimensional Boolean lattice. We show that 2N − o(N) ≤ ex(n, Q ₂) ≤ 2.283261N + o(N), where N = \binomn?n/2 ?N = \binom{n}{\lfloor n/2 \rfloor}. We also prove that the largest Q ₂-free family of subsets of [n] having at most three different sizes has at most 2.20711N members.     

Diophantine approximation generalized

In this paper we study the set of x ∈ [0, 1] for which the inequality |x − x _n | < z _n holds for infinitely many n = 1, 2, .... Here x _n ∈ [0, 1) and z _n s> 0, z _n → 0, are sequences. In the first part of the paper we summarize known results. In the second part, using the theory of distribution functions of sequences, we find the asymptotic density of n for which |x − x _n | < z _n , where x is a discontinuity point of some distribution function of x _n . Generally, we also prove, for an arbitrary sequence x _n , that there exists z _n such that the density of n = 1, 2, ..., x _n → x, is the same as the density of n = 1, 2, ..., |x − x _n | < z _n , for x ∈ [0, 1]. Finally we prove, using the longest gap d _n in the finite sequence x ₁, x ₂, ..., x _n , that if d _n ≤ z _n for all n, z _n → 0, and z _n is non-increasing, then |x − x _n | < z _n holds for infinitely many n and for almost all x ∈ [0, 1].     

MAXIMAL CALDERON-ZYGMUND SINGULAR INTEGRAL ON RBMO

Given a positive Radon measure μ on R^d satisfying the linear growth condition μ（B（x,r））≤C0r^n,x∈R^d,r〉0,（1） where n is a fixed number and O〈n≤d. When d-1〈n,it is proved that if Tt,N1=0,then the corresponding maximal Calderon-Zygmund singular integral is bounded from RBMO to itself only except that it is infinite μ-a. e. on R^d.     

An Elementary Deduction of the Topological Radon Theorem from Borsuk–Ulam

The Topological Radon Theorem states that, for every continuous function from the boundary of a (d+1)-dimensional simplex into ℝ ⁿ , there exists a pair of disjoint faces in the domain whose images intersect in ℝ ⁿ . The similarity between that result and the classical Borsuk–Ulam Theorem is unmistakable, but a proof that the Topological Radon Theorem follows from Borsuk–Ulam is not immediate. In this note we provide an elementary argument verifying that implication.