Approximate Radical for Clusters: A Global Approach Using Gaussian Elimination or SVD

We introduce a matrix of traces, attached to a zero dimensional ideal . We show that the matrix of traces can be a useful tool in handling systems of polynomial equations with clustered roots. We present a method based on Dickson’s lemma to compute the “approximate radical” of in which has zero clusters: the approximate radical ideal has exactly one root in each cluster for sufficiently small clusters. Our method is “global” in the sense that it works simultaneously for all clusters: the problem is reduced to the computation of the numerical nullspace of the matrix of traces, a matrix efficiently computable from the generating polynomials of . To compute the numerical nullspace of the matrix of traces we propose to use Gaussian elimination with pivoting or singular value decomposition. We prove that if has k distinct zero clusters each of radius at most ɛ in the ∞-norm, then k steps of Gaussian elimination on the matrix of traces yields a submatrix with all entries asymptotically equal to ɛ². We also show that the (k + 1)-th singular value of the matrix of traces is proportional to ɛ². The resulting approximate radical has one root in each cluster with coordinates which are the arithmetic mean of the cluster, up to an error term asymptotically equal to ɛ². In the univariate case our method gives an alternative to known approximate square-free factorization algorithms which is simpler and its accuracy is better understood. This work was completed with the support of NSF grants CCR-0306406 and CCR-0347506 and OTKA grants T42481 and T42706 and NK63066.     

A new approximate functional equation for Hurwitz zeta function for rational parameter

For Hurwitz zeta function ζ(s, (a/k)) witha = 1,2,3,…,k, we obtain a new simple approximate functional equation (uniform ink andt) in critical strip. Our method should prove to be an alternative approach to Atkinson’s method in dealing with , whereL(s, x) is Dirichlet L-series moduloq and s = σ +it.     

Quadratic transformations for a function that generalizes 2F1 and the Askey-Wilson polynomials

In previous papers we introduced and studied a ‘relativistic’ hypergeometric function R(a ₊, a ₋, c; v, ) that satisfies four hyperbolic difference equations of Askey-Wilson type. Specializing the family of couplings c∊ to suitable two-dimensional subfamilies, we obtain doubling identities that may be viewed as generalized quadratic transformations. Specifically, they give rise to a quadratic transformation for ₂ F ₁ in the ‘nonrelativistic’ limit, and they yield quadratic transformations for the Askey-Wilson polynomials when the variables v or are suitably discretized. For the general coupling case, we also study the bearing of several previous results on the Askey-Wilson polynomials. Dedicated to Richard Askey on the occasion of his 70th birthday. 2000 Mathematics Subject Classification Primary—33D45, 39A70     

The Effect of Corners on the Complexity of Approximate Range Searching

Given an n-element point set in ℝ ^d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε ^d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)^(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)^(d−1)/2). This bound is in the decision-tree model and holds irrespective of space. A preliminary version of this paper appeared in the Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 11–20, 2006. The research of S. Arya was supported by the Research Grants Council, Hong Kong, China under project number HKUST6184/04E. The research of D.M. Mount was partially supported by the National Science Foundation under grant CCR-0635099 and the Office of Naval Research under grant N00014-08-1-1015.     

Simplicity of principal eigenvalue for p-Laplace operator with singular indefinite weight

Given a connected open set and a function w ∈L^N/p(Ω) if 1 < p < N and w ∈L^r (Ω) for some r ∈(1, ∞) if p ≧ N, with we prove that the positive principal eigenvalue of the problem

Riesz Idempotent and Algebraically M-hyponormal Operators

Let T be an M-hyponormal operator acting on infinite dimensional separable Hilbert space and let be the Riesz idempotent for λ₀, where D is a closed disk of center λ₀ which contains no other points of σ (T). In this note we show that E is self-adjoint and As an application, if T is an algebraically M-hyponormal operator then we prove : (i) Weyl’s theorem holds for f(T) for every (ii) a-Browder’s theorem holds for f(S) for every and f ∈ H(σ(S)); (iii) the the spectral mapping theorem holds for the Weyl spectrum of T and for the essential approximate point spectrum of T.     

Classification of infinitely differentiable periodic functions

The set of infinitely differentiable periodic functions is studied in terms of generalized -derivatives defined by a pair of sequences ψ ₁ and ψ ₂. In particular, we establish that every function f from the set has at least one derivative whose parameters ψ ₁ and ψ ₂ decrease faster than any power function. At the same time, for an arbitrary function f ∈ different from a trigonometric polynomial, there exists a pair ψ whose parameters ψ ₁ and ψ ₂ have the same rate of decrease and for which the -derivative no longer exists. We also obtain new criteria for 2π-periodic functions real-valued on the real axis to belong to the set of functions analytic on the axis and to the set of entire functions. Deceased. (A. I. Stepanets) Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 12, pp. 1686–1708, December, 2008.     

Uniform Mixed Hypergraphs: The Possible Numbers of Colors

For a mixed hypergraph , where and are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every meets some class in more than one vertex, and every has a nonempty intersection with at least two classes. The feasible set of , denoted , is the set of integers k such that admits a coloring with precisely k nonempty color classes. It was proved by Jiang et al. [Graphs and Combinatorics 18 (2002), 309–318] that a set S of natural numbers is the feasible set of some mixed hypergraph if and only if either or S is an ‘interval’ for some integer k ≥ 1. In this note we consider r-uniform mixed hypergraphs, i.e. those with |C| = |D| = r for all and all , r ≥ 3. We prove that S is the feasible set of some r-uniform mixed hypergraph with at least one edge if and only if either for some natural number k ≥ r − 1, or S is of the form where S′′ is any (possibly empty) subset of and S′ is either the empty set or {r − 1} or an ‘interval’ {k, k + 1, ..., r − 1} for some k, 2 ≤ k ≤ r − 2. We also prove that all these feasible sets can be obtained under the restriction , i.e. within the class of ‘bi-hypergraphs’. Research supported in part by the Hungarian Scientific Research Fund, OTKA grant T-049613.     

The ratio of the extreme to the sum in a random sequence

For X ₁ , X ₂ , ..., X _n a sequence of non-negative independent random variables with common distribution function F(t), X _(n) denotes the maximum and S _n denotes the sum. The ratio variate R _n  = X _(n) / S _n is a quantity arising in the analysis of process speedup and the performance of scheduling. O’Brien (J. Appl. Prob. 17:539–545, 1980) showed that as n → ∞, R _n →0 almost surely iff is finite. Here we show that, provided either (1) is finite, or (2) 1 − F (t) is a regularly varying function with index ρ < − 1, then . An integral representation for the expected ratio is derived, and lower and upper asymptotic bounds are developed to obtain the result. Since is often known or estimated asymptotically, this result quantifies the rate of convergence of the ratio’s expected value. The result is applied to the performance of multiprocessor scheduling.      

Versal deformations and versality in central extensions of Jacobi schemes

Let be the scheme of the laws defined by the Jacobi identities on with a field. A deformation of , parametrized by a local ring A, is a local morphism from the local ring of at ϕ _m to A. The problem of classifying all the deformation equivalence classes of a Lie algebra with given base is solved by “versal” deformations. First, we give an algorithm for computing versal deformations. Second, we prove there is a bijection between the deformation equivalence classes of an algebraic Lie algebra ϕ _m = R ⋉ φ _n in and its nilpotent radical φ _n in the R-invariant scheme with reductive part R, under some conditions. So the versal deformations of ϕ _m in are deduced from those of φ _n in , which is a more simple problem. Third, we study versality in central extensions of Lie algebras. Finally, we calculate versal deformations of some Lie algebras. Supported by the EC project Liegrits MCRTN 505078.     

On some new criteria for infinite differentiability of periodic functions

We study the set of infinitely differentiable periodic functions in terms of generalized -derivatives defined by a pair of sequences ψ ₁ and ψ ₂. It is shown that every function ƒ from the set has at least one derivative whose parameters ψ ₁ and ψ ₂ decrease faster than any power function and, at the same time, for any function ƒ ∈ different from a trigonometric polynomial, there exists a pair ψ whose parameters ψ ₁ and ψ ₂ have the same rate of decrease and for which the -derivative no longer exists. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 10, pp. 1399–1409, October, 2007.     

On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix

Let $ \tilde \lambda Let be an approximate eigenvalue of multiplicity m _c = n − r of an n × n real symmetric tridiagonal matrix T having nonzero off-diagonal entries. A fast algorithm is proposed (and numerically tested) for deleting m _c rows of T− I so that the condition number of the r × n matrix B formed of the remaining r rows is as small as possible. A special basis of m _c vectors with local supports is constructed for the subspace kerB. These vectors are approximate eigenvectors of T corresponding to . Another method for deleting m _c rows of T− I is also proposed. This method uses a rank-revealing QR decomposition; however, it requires a considerably larger number of arithmetic operations. For the latter algorithm, the condition number of B is estimated, and orthogonality estimates for vectors of the special basis of kerB are derived. Original Russian Text ? S.K. Godunov, A.N. Malyshev, 2008, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2008, Vol. 48, No. 7, pp. 1156–1166.     

Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

Quelques Résultats sur les Algèbres Flexibles Préhilbertiennes sans Diviseurs de Zéro Vérifiant ∥a 2∥ = ∥a∥2

Résumé. Soit A une algèbre réelle. On suppose que l’espace vectoriel A est muni d’une norme ∥.∥ préhilbertienne vérifiant ∥a ²∥ = ∥a∥² pour tout . Si A est flexible, sans diviseurs de zéro et de dimension ≤ 4, alors A est isomorphe à ou , ce qui généralise un théorème d’El-Mallah [1]. Si A est flexible, sans diviseurs de zéro, contenant un idempotent central et vérifiant la propriété d’Osborn, alors A est de dimension finie et isomorphe à , ou . Enfin nous montrons qu’une algèbre normée préhilbertienne unitaire d’unité e telle que ∥e∥ = 1 est flexible et vérifie ∥a ²∥ = ∥ a∥².

---

Let A be a real algebra. Assuming that a vector space A is endowed with a pre-Hilbert norm ∥.∥ satisfying ∥a ²∥ = ∥a∥² for all . If A is flexible, without divisor of zero and of a dimension ≤ 4, then A is isomorphic to or , which generalize El-Mallah’s theorem [1]. If A is flexible, without divisor of zero, containing a central idempotent and satisfying Osborn’s properties, then A is finite dimensional and isomorphic to , or . Finally we prove that a normed pre-Hilbert algebra with unit e such that ∥e∥ = 1 is flexible and satisfies ∥a ²∥ = ∥a∥².

     

Two-side estimates for sums of absolute values of Fourier coefficients of functions from Hω(Tm)

The class of functions H ^ω is considered, where ω(t) is a continuity modulus monotone in the sense of Hardy and satisfying some condition C. The behavior of the value is obtained, where is the sum of absolute values of Fourier coefficients of a function f ∈ L(T ^m ) in pth power. Original Russian Text ? D.M. D’yachenko, 2008, published in Vestnik Moskovskogo Universiteta, Matematika. Mekhanika, 2008, Vol. 63, No. 3, pp. 19–26.     

Duality of chordal SLE

We derive some geometric properties of chordal SLE(κ;) processes. Using these results and the method of coupling two SLE processes, we prove that the outer boundary of the final hull of a chordal SLE(κ;) process has the same distribution as the image of a chordal SLE(κ’;’) trace, where κ>4, κ’=16/κ, and the forces and ’ are suitably chosen. We find that for κ≥8, the boundary of a standard chordal SLE(κ) hull stopped on swallowing a fixed is the image of some SLE(16/κ;) trace started from x. Then we obtain a new proof of the fact that chordal SLE(κ) trace is not reversible for κ>8. We also prove that the reversal of SLE(4;) trace has the same distribution as the time-change of some SLE(4;’) trace for certain values of and ’.     

Arithmetical properties of some series with logarithmic coefficients

We prove approximation formulas for the logarithms of some infinite products, in particular, for Euler’s constant γ, log and log σ, where σ is Somos’s quadratic recurrence constant, in terms of classical Legendre polynomials and partial sums of their series expansions. We also give conditional irrationality and linear independence criteria for these numbers. The main tools are Euler-type integrals, hypergeometric series, and Laplace method.     

Small gaps between primes

Combining Goldston-Yildirim’s method on k-correlations of the truncated von Mangoldt function with Maier’s matrix method, we show that for all r ≧ 1 where p _n denotes the nth prime number and γ is Euler’s constant. This is the best known result for any r ≧ 11.      

Volume Distortion for Subsets of Euclidean Spaces

In Rao (Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300–306, 1999), it is shown that every n-point Euclidean metric with polynomial aspect ratio admits a Euclidean embedding with k-dimensional distortion bounded by , a result which is tight for constant values of k. We show that this holds without any assumption on the aspect ratio and give an improved bound of . Our main result is an upper bound of independent of the value of k, nearly resolving the main open questions of Dunagan and Vempala (Randomization, Approximation, and Combinatorial Optimization, pp. 229–240, 2001) and Krauthgamer et al. (Discrete Comput. Geom. 31(3):339–356, 2004). The best previous bound was O(log n), and our bound is nearly tight, as even the two-dimensional volume distortion of an n-vertex path is . This research was done while the author was a postdoctoral fellow at the Institute for Advanced Study, Princeton, NJ.     

On the Scope of Averaging for Frankl’s Conjecture

Let be a union-closed family of subsets of an m-element set A. Let . For b ∈ A let w(b) denote the number of sets in containing b minus the number of sets in not containing b. Frankl’s conjecture from 1979, also known as the union-closed sets conjecture, states that there exists an element b ∈ A with w(b) ≥ 0. The present paper deals with the average of the w(b), computed over all b ∈ A. is said to satisfy the averaged Frankl’s property if this average is non-negative. Although this much stronger property does not hold for all union-closed families, the first author (Czédli, J Comb Theory, Ser A, 2008) verified the averaged Frankl’s property whenever n ≥ 2 ^m  − 2 ^m/2 and m ≥ 3. The main result of this paper shows that (1) we cannot replace 2 ^m/2 with the upper integer part of 2 ^m /3, and (2) if Frankl’s conjecture is true (at least for m-element base sets) and then the averaged Frankl’s property holds (i.e., 2 ^m/2 can be replaced with the lower integer part of 2 ^m /3). The proof combines elementary facts from combinatorics and lattice theory. The paper is self-contained, and the reader is assumed to be familiar neither with lattices nor with combinatorics. This research was partially supported by the NFSR of Hungary (OTKA), grant no. T 049433, T 48809 and K 60148.