Cumulants are universal homomorphisms into Hausdorff groups

This is a contribution to the theory of sums of independent random variables at an algebraico-analytical level: Let Prob denote the convolution semigroup of all probability measures on with all moments finite, topologized by polynomially weighted total variation. We prove that the cumulant sequence regarded as a function from Prob into the additive topological group ofall real sequences, is universal among continuous homomorphisms from Prob into Hausdorff topological groups, in the usual sense that every other such homomorphism factorizes uniquely through . An analogous result, referring to just the first cumulants,holds for the semigroup of all probability measures with existing rth moments. In particular, there is no nontrivial continuous homomorphism from the convolution semigroup of all probability measures, topologized by the total variation metric, into any Hausdorff topological group.Mathematics Subject Classification (2000): 60B15, 60E10, 60G50     

On the Computation of Square Roots in Finite Fields

In this paper, two improvements for computing square roots in finite fields are presented. Firstly, we give a simple extension of a method by O. Atkin, which requires two exponentiations in FM _q , when q9 mod 16. Our second method gives a major improvement to the Cipolla–Lehmer algorithm, which is both easier to implement and also much faster. While our method is independent of the power of 2 in q–1, its expected running time is equivalent to 1.33 as many multiplications as exponentiation via square and multiply. Several numerical examples are given that show the speed-up of the proposed methods, compared to the routines employed by Mathematica, Maple, respectively Magma.     

On the quantifier complexity of Δ<Subscript> n+1</Subscript> (T)– induction

In this paper we continue the study of the theories I _n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class of theories such that I _n+1 (T) is _n+2 –axiomatizable. In particular, I _n+1 (I _n+1 ) gives an axiomatization of Th _n+2 (I _n+1 ) and is not finitely axiomatizable. This fact relates the fragment I _n+1 (I _n+1 ) to induction rule for _n+1 –formulas. Our arguments, involving a construction due to R. Kaye (see [9]), provide proofs of Parsons conservativeness theorem (see [16]) and (a weak version) of a result of L.D. Beklemishev on unnested applications of induction rules for _n+2 and _n+1 formulas (see [2]).Research partially supported by grant PB96–1345 (Spanish Goverment)Mathematics Subject Classification (2000): 03F30, 03H15     

The Brumer-Stark conjecture in some families of extensions of specified degree

As a starting point, an important link is established between Brumer's conjecture and the Brumer-Stark conjecture which allows one to translate recent progress on the former into new results on the latter. For example, if is an abelian extension of relative degree , an odd prime, we prove the -part of the Brumer-Stark conjecture for all odd primes with belonging to a wide class of base fields. In the same setting, we study the -part and -part of Brumer-Stark with no special restriction on and are left with only two well-defined specific classes of extensions that elude proof. Extensive computations were carried out within these two classes and a complete numerical proof of the Brumer-Stark conjecture was obtained in all cases.

     

Network synthesis under survivability constraints

Telecommunication networks are subject to link and equipment failures. Since failures cannot be entirely avoided, networks have to be designed so as to survive failure situations. In this paper, we are interested in designing low cost survivable networks. Given point-to-point traffic demands and a cost/capacity function for each link, we aim at finding the minimum cost capacities satisfying the given demands and survivability requirements. A survivability model that reroutes interrupted traffic using all the available capacities on the network is presented and studied. In the proposed model, capacity and flow assignments for each network operating state are jointly optimized. We prove the -hardness of the optimisation problem defined by dual constraints. Then, we propose a polynomial relaxation along with a fast heuristic to compute a feasible solution of the problem from its relaxed optimal solution. Our solution approaches are tested on a set of problem instances.Received: September 2002, Revised: July 2003, AMS classification: 90C05     

On the Ideals of Secant Varieties of Segre Varieties

We establish basic techniques for determining the ideals of secant varieties of Segre varieties.We solve a conjecture of Garcia, Stillman, and Sturmfels on the generators of the ideal of the first secant variety in the case of three factors and solve the conjecture set-theoretically for an arbitrary number of factors. We determine the low degree components of the ideals of secant varieties of small dimension in a few cases.     

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

Approximation by Algebraic Polynomials on Rectangles

A direct theorem for approximation by algebraic polynomials in two variables with different degrees in each variable in L_p-metric (1 p ) on rectangles is proved, and the dependence of the constants on various parameters is studied.     

Avoidable algebraic subsets of Euclidean space

Fix an integer and consider real -dimensional . A partition of avoids the polynomial , where each is an -tuple of variables, if there is no set of the partition which contains distinct such that . The polynomial is avoidable if some countable partition avoids it. The avoidable polynomials are studied here. The polynomial is an especially interesting example of an avoidable one. We find (1) a countable partition which avoids every avoidable polynomial over , and (2) a characterization of the avoidable polynomials. An important feature is that both the ``master' partition in (1) and the characterization in (2) depend on the cardinality of .