Skew Boolean algebras derived from generalized Boolean algebras

Every skew Boolean algebra S has a maximal generalized Boolean algebra image given by S/ where is the Green’s relation defined initially on semigroups. In this paper we study skew Boolean algebras constructed from generalized Boolean algebras B by a twisted product construction for which . In particular we study the congruence lattice of with an eye to viewing as a minimal skew Boolean cover of B. This construction is the object part of a functor from the category GB of generalized Boolean algebras to the category LSB of left-handed skew Boolean algebras. Thus we also look at its left adjoint functor . This paper was written while the second author was a Visiting Professor in the Department of Education at the University of Cagliari. The facilities and assistance provided by the University and by the Department are gratefully acknowledged.     

Lattice based extended formulations for integer linear equality systems

We study different extended formulations for the set with in order to tackle the feasibility problem for the set Pursuing the work of Aardal, Lenstra et al. using the reformulation , our aim is to derive reformulations of the form with 0  ≤  s ≤ n − m where preferably all the coefficients of P are small compared to the coefficients of A and T. In such cases the new variables μ appear to be good branching directions, and in certain circumstances permit one to deduce rapidly that the instance is infeasible. We give a polynomial time algorithm for identifying such P, T if possible, and for the case that A has one row a we analyze the reformulation when s = 1, that is, one μ-variable is introduced. In particular, we determine the integer width of the extended formulations in the direction of the μ-variable, and derive a lower bound on the Frobenius number of a. We conclude with some preliminary tests to see if the reformulations are effective when the number s of additional constraints and variables is limited. This work was partly carried out within the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract no. MRTN-CT-2003-504438. The first author is financed in part by the Dutch BSIK/BRICKS project. The research was carried out in part while the second author visited CWI, Amsterdam with the support of the NWO visitor grant number B 61-556.     

Weights of twisted exponential sums

Let k be a finite field of characteristic p, l a prime number different from p, a nontrivial additive character, and a character on . Then ψ defines an Artin-Schreier sheaf on the affine line , and χ defines a Kummer sheaf on the n-dimensional torus . Let be a Laurent polynomial. It defines a k-morphism . In this paper, we calculate the weights of under some non-degeneracy conditions on f. Our results can be used to estimate sums of the form

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let and be a finite dimensional real vector space and a symmetric cone embedded in ; examples of and include a pair of the N-dimensional Euclidean space and its nonnegative orthant, a pair of the N-dimensional Euclidean space and N-dimensional second-order cones, and a pair of the space of m × m real symmetric (or complex Hermitian) matrices and the cone of their positive semidefinite matrices. Sums of squares relaxations are further extended to a polynomial optimization problem over , i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region , where b(x) denotes an - valued polynomial in x. It is shown under a certain moderate assumption on the -valued polynomial b(x) that optimal values of a sequence of sums of squares relaxations of the problem, which are converted into a sequence of semidefinite programs when they are numerically solved, converge to the optimal value of the problem. Research supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234.     

Projective re-normalization for improving the behavior of a homogeneous conic linear system

In this paper we study the homogeneous conic system . We choose a point that serves as a normalizer and consider computational properties of the normalized system . We show that the computational complexity of solving F via an interior-point method depends only on the complexity value of the barrier for C and on the symmetry of the origin in the image set , where the symmetry of 0 in is

Existence theory of abstract approximate deconvolution models of turbulence

This report studies an abstract approach to modeling the motion of large eddies in a turbulent flow. If the Navier-Stokes equations (NSE) are averaged with a local, spatial convolution type filter, , the resulting system is not closed due to the filtered nonlinear term . An approximate deconvolution operator D is a bounded linear operator which is an approximate filter inverse

Generalised twists,stationary loops,and the Dirichlet energy over a space of measure preserving maps

Let be a bounded Lipschitz domain and consider the Dirichlet energy functional

Foliations and polynomial diffeomorphisms of $${\mathbb{R}^{3}}$$

Let be a C ² map and let Spec(Y) denote the set of eigenvalues of the derivative DY _p , when p varies in . We begin proving that if, for some ϵ > 0, then the foliation with made up by the level surfaces {k = constant}, consists just of planes. As a consequence, we prove a bijectivity result related to the three-dimensional case of Jelonek’s Jacobian Conjecture for polynomial maps of The first author was supported by CNPq-Brazil Grant 306992/2003-5. The first and second author were supported by FAPESP-Brazil Grant 03/03107-9.     

On the spectrum of lamplighter groups and percolation clusters

Let be a finitely generated group and X its Cayley graph with respect to a finite, symmetric generating set S. Furthermore, let be a finite group and the lamplighter group (wreath product) over with group of “lamps” . We show that the spectral measure (Plancherel measure) of any symmetric “switch–walk–switch” random walk on coincides with the expected spectral measure (integrated density of states) of the random walk with absorbing boundary on the cluster of the group identity for Bernoulli site percolation on X with parameter . The return probabilities of the lamplighter random walk coincide with the expected (annealed) return probabilities on the percolation cluster. In particular, if the clusters of percolation with parameter are almost surely finite then the spectrum of the lamplighter group is pure point. This generalizes results of Grigorchuk and Żuk, resp. Dicks and Schick regarding the case when is infinite cyclic. Analogous results relate bond percolation with another lamplighter random walk. In general, the integrated density of states of site (or bond) percolation with arbitrary parameter is always related with the Plancherel measure of a convolution operator by a signed measure on , where or another suitable group. M. Neuhauser’s research supported by the Marie-Curie Excellence Grant MEXT-CT-2004-517154. The research of W. Woess was partially supported by Austrian Science Fund (FWF) P18703-N18.     

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 ’.     

MIP reformulations of the probabilistic set covering problem

In this paper, we address the following probabilistic version (PSC) of the set covering problem: where A is a 0-1 matrix, is a random 0-1 vector and is the threshold probability level. We introduce the concepts of p-inefficiency and polarity cuts. While the former is aimed at deriving an equivalent MIP reformulation of (PSC), the latter is used as a strengthening device to obtain a stronger formulation. Simplifications of the MIP model which result when one of the following conditions hold are briefly discussed: A is a balanced matrix, A has the circular ones property, the components of are pairwise independent, the distribution function of is a stationary distribution or has the disjunctive shattering property. We corroborate our theoretical findings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances. This test-bed was created using deterministic instances from the literature and consists of probabilistic variants of the set covering model and capacitated versions of facility location, warehouse location and k-median models. Our computational results show that our procedure is orders of magnitude faster than any of the existing approaches to solve (PSC), and in many cases can reduce hours of computing time to a fraction of a second. Anureet Saxena’s research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133. Vineet Goyal’s research was supported in part by NSF grant CCF-0430751 and ITR grant CCR-0122581.     

Corrector–predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path

Two corrector–predictor interior point algorithms are proposed for solving monotone linear complementarity problems. The algorithms produce a sequence of iterates in the neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm can be implemented in arithmetic operations, where n is the dimension of the problems, is a constant, and m is the maximum order of the predictor and the corrector. If then both algorithms have iteration complexity. They are superlinearly convergent even for degenerate problems.      

Intersection homology Künneth theorems

Cohen, Goresky, and Ji showed that there is a Künneth theorem relating the intersection homology groups to and , provided that the perversity satisfies rather strict conditions. We consider biperversities and prove that there is a Künneth theorem relating to and for all choices of and . Furthermore, we prove that the Künneth theorem still holds when the biperversity p, q is “loosened” a little, and using this we recover the Künneth theorem of Cohen–Goresky–Ji.     

On formulas for the index of the circular distributions

A circular distribution is a Galois equivariant map ψ from the roots of unity μ _∞ to an algebraic closure of such that ψ satisfies product conditions, for ϵ ∈ μ _∞ and , and congruence conditions for each prime number l and with (l, s) = 1, modulo primes over l for all , where μ _l and μ _s denote respectively the sets of lth and sth roots of unity. For such ψ, let be the group generated over by and let be , where U _s denotes the global units of . We give formulas for the indices and of and inside the circular numbers P _s and units C _s of Sinnott over . This work was supported by the SRC Program of Korea Science and Engineering Foundation (KOSEF) grant funded by the Korea government (MOST) (No. R11-2007-035-01001-0). This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2006-312-C00455).     

On the symmetry function of a convex set

We attempt a broad exploration of properties and connections between the symmetry function of a convex set S ${S \subset\mathbb{R}^n}We attempt a broad exploration of properties and connections between the symmetry function of a convex set S and other arenas of convexity including convex functions, convex geometry, probability theory on convex sets, and computational complexity. Given a point , let sym(x,S) denote the symmetry value of x in S: , which essentially measures how symmetric S is about the point x, and define x ^* is called a symmetry point of S if x ^* achieves the above maximum. The set S is a symmetric set if sym (S)=1. There are many important properties of symmetric convex sets; herein we explore how these properties extend as a function of sym (S) and/or sym (x,S). By accounting for the role of the symmetry function, we reduce the dependence of many mathematical results on the strong assumption that S is symmetric, and we are able to capture and otherwise quantify many of the ways that the symmetry function influences properties of convex sets and functions. The results in this paper include functional properties of sym (x,S), relations with several convex geometry quantities such as volume, distance, and cross-ratio distance, as well as set approximation results, including a refinement of the L?wner-John rounding theorems, and applications of symmetry to probability theory on convex sets. We provide a characterization of symmetry points x ^* for general convex sets. Finally, in the polyhedral case, we show how to efficiently compute sym(S) and a symmetry point x ^* using linear programming. The paper also contains discussions of open questions as well as unproved conjectures regarding the symmetry function and its connection to other areas of convexity theory. Dedicated to Clovis Gonzaga on the occasion of his 60th birthday.     

Ranks of abelian varieties over infinite extensions of the rationals

Let S be an infinite set of rational primes and, for some p ∈ S, let be the compositum of all extensions unramified outside S of the form , for . If , let be the intersection of the fixed fields by , for i = 1, . . , n. We provide a wide family of elliptic curves such that the rank of is infinite for all n ≥ 0 and all , subject to the parity conjecture. Similarly, let be a polarized abelian variety, let K be a quadratic number field fixed by , let S be an infinite set of primes of and let be the maximal abelian p-elementary extension of K unramified outside primes of K lying over S and dihedral over . We show that, under certain hypotheses, the -corank of sel _p ∞(A/F) is unbounded over finite extensions F/K contained in . As a consequence, we prove a strengthened version of a conjecture of M. Larsen in a large number of cases.     

The Kostant–García quantization of the bundle of connections

We shall call quantum states of a principal bundle π : P → M with structure group a semi-simple Lie group G, the elements of certain space of sections of the adjoint bundle , associated to the G-bundle of connections . An inner product of sections of is defined for which is a Hilbert space such that the Gauge group gau(P) of the given bundle represents in a family of self-adjoint operators. This work crystallizes some heuristic considerations, on the unitary representations of Gauge algebras, of Garcia in the already a classical article (J. Differ. Geom. 12, 209–227, 1977).     

A short proof for the sum formula and its generalization

For positive integers with a _r  = 2, the multiple zeta value or r-fold Euler sum is defined as [2]

Second-order Linearity of Wilcoxon Statistics

The rank statistic , with R _i (t) being the rank of and e ₁ , . . . , e _n being the random sample from a distribution with a cdf F, is considered as a random process with t in the role of parameter. Under some assumptions on c _i , x _i and on the underlying distribution, it is proved that the process converges weakly to the Gaussian process. This generalizes the existing results where the one-dimensional case was considered. We believe our method of the proof can be easily modified for the signed-rank statistics of Wilcoxon type. Finally, we use our results to find the second order asymptotic distribution of the R-estimator based on the Wilcoxon scores and also to investigate the length of the confidence interval for a single parameter β _l .