A “Generalized Trace Formula” for Bell numbers

The nth Bell number B_n is the number of ways to partition a set of n elements into nonempty subsets. We generalize the “trace formula” of Barsky and Benzaghou [1], which asserts that for an odd prime p and an appropriate constant τ_p, the relation B_n=-Tr(^n-1-τ_p)B_τp holds in , where is a root of and is the trace form. We deduce some new interesting congruences for the Bell numbers, generalizing miscellaneous well-known results including those of Radoux [4].     

Diameter of a direct power of a finite group

We present two conjectures concerning the diameter of a direct power of a finite group. The first conjecture states that the diameter of Gⁿ with respect to each generating set is at most n(|G|?rank(G)); and the second one states that there exists a generating set 𝒜, of minimum size, for Gⁿ such that the diameter of Gⁿ with respect to 𝒜 is at most n(|G|?rank(G)). We will establish evidence for each of the above mentioned conjectures.     

Analysis of the Herlestam and Johannesson discrete logarithm scheme inGF(2 N ) for largeN

The Herlestam and Johannesson algorithm for computing discrete logarithms inGF(2 ⁿ ) requires the precomputation of logarithms for a target set consisting of all field elements of Hamming weight less than some predetermined value. The procedure, both in precomputation and at run-time, selects elements of lowest weight from large sets of elements. These sets are not randomly chosen but their minimum weight statistics parallel those for sets of equal size chosen entirely at random. By analyzing the statistics for randomly chosen sets, we show that the target set must contain all elements up to about weightn/3–8. This is clearly impractical for even moderately large values ofn.This work was supported by MITRE Corp. IR & D funds.Dr. Berkovits was on leave from the University of Lowell, Lowell, MA, 01854.     

The Parallel Simplicity of Compaction and Chaining

Given a set of values x₁, x₂,..., x_n, of which k are nonzero, the compaction problem is the problem of moving the nonzero elements into the first k consecutive memory locations. The chaining problem asks that the nonzero elements be put into a linked list. One can in addition require that the elements remain in the same order, leading to the problems of ordered compaction and ordered chaining, respectively. This paper introduces a technique involving perfect hash functions that leads to a deterministic algorithm for ordered compaction running on a CRCW PRAM in time O(log k/log log n) using n processors. A matching lower bound for unordered compaction is given. The ordered chaining problem is shown to be solvable in time O(α(k)) with n processors (where α is a functional inverse of Ackermann′s function) and unordered chaining is shown to he solvable in constant time with n processors when k < n^{1/4− ε}.     

Some (n − 1)-dimensional rigid sets inR n

We prove that a rigid set inR ⁿ remains rigid if we remove a countable subset of its interior. This gives us a method of obtaining (n – 1)-dimensional rigid sets inR ⁿ .Recently V. A. Aleksandrov announced that he had found a 1-dimensional rigid set inR ². Our method is quite different and more general (for arbitrary dimensionn).     

Improved random graph isomorphism

Canonical labeling of a graph consists of assigning a unique label to each vertex such that the labels are invariant under isomorphism. Such a labeling can be used to solve the graph isomorphism problem. We give a simple, linear time, high probability algorithm for the canonical labeling of a G(n,p) random graph for p[ω(ln⁴n/nlnlnn),1−ω(ln⁴n/nlnlnn)]. Our result covers a gap in the range of p in which no algorithm was known to work with high probability. Together with a previous result by Bollobás, the random graph isomorphism problem can be solved efficiently for p[Θ(lnn/n),1−Θ(lnn/n)].     

Smooth Quasiregular Maps with Branching in R n

According to a theorem of Martio, Rickman and Väisälä, all nonconstant C^n/(n-2)-smooth quasiregular maps in Rⁿ, n≥3, are local homeomorphisms. Bonk and Heinonen proved that the order of smoothness is sharp in R³. We prove that the order of smoothness is sharp in R⁴. For each n≥5 we construct a C^1+ε(n)-smooth quasiregular map in Rⁿ with nonempty branch set.     

Off-line dynamic maintenance of the width of a planar point set

Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1990) 65-78. In this paper we present an efficient algorithm for the off-line dynamic maintenance of the width of a planar point set in the following restricted case: We are given a real parameter W and a sequence Σ=(σ₁,...,σ_n) of n insert and delete operations on a set S of points in ², initially consisting of n points, and we want to determine whether there is an i such that the width of S the ith operation is less than or equal to W. Our algorithm runs in time O(nlog³n) and uses O(n) space.     

On closures of joint similarity orbits

For an n-tuple T=(T₁,..., T_n) of operators on a Hilbert spacexxHx, the joint similarity orbit of T isxxSx(T)={VTV^–1 =(VT₁V^–1,...,VT_nV^–1): V is invertible onxxHx}. We study the structure of the norm closure ofxxSx, both in the case when T is commutative and when it is not. We first develop a Rota-model for the Taylor spectrum and use it to study n-tuples with totally disconnected Taylor spectrum, in particular quasinilpotent ones. We then consider limits of nilpotent n-tuples, and of normal n-tuples. For noncommuting n-tuples, we present a number of surprising facts relating the closure ofxxSx(T) to the Harte spectrum of T and the lack of commutativity of T. We show that a continuous function which is constant onxxSx(T) for all T must be constant. We conclude the paper with a detailed study of closed similarity orbits.Research partially supported by grants from the National Science Foundation.     

Linear Optimization Queries

Let Γ₀ be a set of n halfspaces in E^d (where the dimension d is fixed) and let m be a parameter, n ≤ m ≤ n^d/2. We show that Γ₀ can be preprocessed in time and space O(m^1+δ) (for any fixed δ > 0) so that given a vector c E^d and another set Γ_q of additional halfspaces, the function c · x can be optimized over the intersection of the halfspaces of Γ₀ Γ_q in time O((n/m^1/d/2 + |Γ_q|)log^4d+3n). The algorithm uses a multidimensional version of Megiddo′s parametric search technique and recent results on halfspace range reporting. Applications include an improved algorithm for computing the extreme points of an n-point set P in E^d, improved output-sensitive computation of convex hulls and Voronoi diagrams, and a Monte-Carlo algorithm for estimating the volume of a convex polyhedron given by the set of its vertices (in a fixed dimension).     

On the Average Running Time of Odd–Even Merge Sort

This paper gives an upper bound for the average running time of Batcher's odd–even merge sort when implemented on a collection of processors. We consider the case wheren, the size of the input, is an arbitrary multiple of the numberpof processors used. We show that Batcher's odd–even merge (for two sorted lists of lengthneach) can be implemented to run in timeO((n/p)(log(2 + p²/n))) on the average,¹and that odd–even merge sort can be implemented to run in timeO((n/p)(log n + log p log(2 + p²/n))) on the average. In the case of merging (sorting), the average is taken over all possible outcomes of the merge (all possible permutations ofnelements). That means that odd–even merge and odd–even merge sort have an optimal average running time ifn ≥ p². The constants involved are also quite small.     

An extension of the Erdős–Ginzburg–Ziv Theorem to hypergraphs

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct with the result that they can be considered as sets. For a sequence S, subsequence S^′, and set T, |T∩S| denotes the number of terms x of S with xT, and |S| denotes the length of S, and SS^′ denotes the subsequence of S obtained by deleting all terms in S^′. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A=A₁,…,A_n, such that

then there exists a subsequence S^′ of S, with length |S^′|≤max{|S|−n+1,2n}, and with an n-set partition, , such that . Furthermore, if ||A_i|−|A_j||≤1 for all i and j, or if |A_i|≥3 for all i, then .(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a,bG such that . If |S|≥2m−1, then there exists an m-term zero-sum subsequence S^′ of S with or .Let be a connected, finite m-uniform hypergraph, and be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group ) of the vertices of the complete m-uniform hypergraph , there exists a subhypergraph isomorphic to such that every edge in is monochromatic (such that for every edge e in the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph of contains an edge with at least half of its vertices monovalent in , or if consists of two intersecting edges, then . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when is a single edge.     

Incremental and Decremental Maintenance of Planar Width

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^ε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^ε).     

Interpolation by Convex Algebraic Hypersurfaces

LetΣbe the set of vertices of a convex non-degenerate polyhedron inRⁿ,n2. We suggest an algorithm to construct smooth convex algebraic hypersurfaces of degree as small as possible, going throughΣ.     

The Linear Part of a Discontinuously Acting Euclidean Semigroup

Let ⁿ be a Euclidean space and let S be a Euclidean semigroup, i.e., a subsemigroup of the group of isometries of ⁿ. We say that a semigroup S acts discontinuously on ⁿ if the subset {s  S:sK ∩ K ≠ } is finite for any compact set K of ⁿ. The main results of this work areTheorem.If S is a Euclidean semigroup which acts discontinuously on ⁿ, then the connected component of the closure of the linear part ℓ(S) of S is a reducible group.Corollary.Let S be a Euclidean semigroup acting discontinuously on ⁿ; then the linear part ℓ(S) of S is not dense in the orthogonal group O(n).These results are the first step in the proof of the followingMargulis' Conjecture.If S is a crystallographic Euclidean semigroup, then S is a group.     

Distribution of exponential functions with k-full exponent modulo a prime

For a real x -1 we denote by S_k[X] the set of k-full integers n x, that is, the set of positive integers n x such that ℓ^k|n for any prime divisor ℓ|n. We estimate exponential sums of the form where is a fixed integer with gcd (, p) = 1, and apply them to studying the distribution of the powers ⁿ, n S_k[x], in the residue ring modulo p 1.     

Routing through a generalized switchbox

We present an algorithm for the routing problem for two-terminal nets in generalized switchboxes. A generalized switchbox is any subset R of the planar rectangular grid with no nontrivial holes, i.e., every finite face has exactly four incident vertices. A net is a pair of nodes of nonmaximal degree on the boundary of R. A solution is a set of edge-disjoint paths, one for each net. Our algorithm solves standard generalized switchbox routing problems in time O(n(log n)²) where n is the number of vertices of R, i.e., it either finds a solution or indicates that there is none. A problem is standard if deg(ν) + ter(ν) is even for all vertices ν where deg(ν) is the degree of ν and ter(ν) is the number of nets which have ν as a terminal. For nonstandard problems we can find a solution in time O(n(log n)² + |U|²) where U is the set of vertices ν with deg(ν) + ter(ν) is odd.     

A faster strongly polynomial time algorithm for submodular function minimization

We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n ⁵EO  +  n ⁶) time, where EO is the time to evaluate f(S) for some . This improves the previous best strongly polynomial running time by more than a factor of n. We also extend our result to ring families.     

Ramsey-Type Results for Unions of Comparability Graphs

 It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least . In this note we show that any graph of n vertices which is the union of two comparability graphs on the same vertex set, contains either a clique or an independent set of size at least . On the other hand, there exist such graphs for which the size of any clique or independent set is at most n ^0.4118. Similar results are obtained for graphs which are unions of a fixed number k comparability graphs. We also show that the same bounds hold for unions of perfect graphs. Received: November 1, 1999 Final version received: December 1, 2000     

Batched dynamic solutions to decomposable searching problems

The batched static version of a searching problem asks for performing a given set of queries on a given set of objects. All queries are known in advance. The batched dynamic version of a searching problem is the following: given a sequence of insertions, deletions, and queries, perform them on an initially empty set. We will develop methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems. The techniques show that batched static (dynamic) versions of searching problems can often be solved more efficiently than by using known static (dynamic) data structures. In particular, a technique called “streaming” is described that reduces the space requirements considerably. The methods have also a number of applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel hyper-rectangles in d dimensions can be reported in O (nlog^d−1n + k) time using only O(n) space.