The construction of torsion-free abelian groups with prescribed endomorphism rings starting with Corner’s seminal work is a well-studied subject in the theory of abelian groups. Usually these construction work by adding elements from a (topological) completion in order to get rid of (kill) unwanted homomorphisms. The critical part is to actually prove that every unwanted homomorphism can be killed by adding a suitable element. We will demonstrate that some of those constructions can be signiﬁcantly simpliﬁed by choosing the elements at random. As a result, the endomorphism ring will be almost surely prescribed, i.e., with probability one.
Keywords: random construction; abelian groups with prescribed endomorphisms; probabilistic method.
Extended formulation is an important tool to obtain compact formulations opolytopes by representing them as projections of higher dimensional ones. It is an importanquestion whether a polytope admits a compact extended formulation, i.e., one of polynomiasize. For the case of symmetric extended formulations (i.e., preserving the symmetries of thpolytope) Yannakakis established a powerful technique to derive lower bounds and rule oucompact formulations. We rephrase the technique of Yannakakis in a group-theoretic frameworkThis provides a diﬀerent perspective on symmetric extensions and considerably simpliﬁes severalower bound constructions.
Keywords: symmetric extended formulation; lower bound; algebraic method.
We develop a framework for unconditional approximation limits of any polynomial-size linear program from lower bounds on the nonnegative ranks of matrices. Using our framework, we prove that O(n^{1/2−ε})-approximations for CLIQUE (with a certain encoding) require linear programs of size 2^{n^{Ω(ε)}}. Moreover, we establish a similar result for approximations of semidefinite programs by linear programs. Our main technical ingredient is a quantitative improvement of Razborov’s rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the non-negative rank of certain perturbations of the unique disjointness matrix.
Keywords: approximate extended formulation; cut polytope; communication complexity; set non-disjointness problem; rectangle corruption lemma.
We show that every torsion-free group representable by a finite automaton is an extension of a finite-rank free group by a direct sum of finitely many Prüfer groups. This builds on a large extent on Tsankov's proof that the group of rational numbers is not representable by a finite automaton.
Keywords: FA-presentable abelian groups; automatic structures; additive combinatorics.
The structure of almost projective modules can be better understood in case the following Condition (P) holds: ‘The union of each countable pure chain of projective modules is projective.’ We prove this condition, and its generalization to pure–projective modules, for all countable rings using the new notion of a strong submodule of the union. However, we also show that Condition (P) fails for all Prüfer domains of finite character with uncountable spectrum; in particular, for the polynomial ring K[x] where K is an uncountable ﬁeld. Moreover, one can even prescribe the Γ–invariant of the union. Our results generalize earlier work of Hill, and complement recent papers by Macías–Díaz, Fuchs, and Rangaswamy.
Keywords: almost projective module; pure chain; strong submodule; Γ–invariant; Prüfer domain.
We provide a surgery formula for the Seiberg–Witten invariants of negative definite plumbed rational homology 3-spheres. The surgery is deleting an arbitrary vertex of the plumbing graph. The formula is additive in nature: the Seiberg–Witten invariant for a c spinorial structure is the sum of correction terms plus the Seiberg–Witten invariants for the restricted c spinorial structure of the manifolds plumbed using the components of the deleted graph. This formula was conjectured by the second author as an analogue of Okuma's additivity formula for splice-quotient singularities. As a by-product, this proves the Seiberg–Witten invariant conjecture for splice-quotient singularities.
Keywords: isolated surface singularity; plumbed 3-manifold; surgery formula for Seiberg–Witten invariants; rational homology sphere; splice-quotient singularity; Seiberg–Witten invariant conjecture.
We will show that random half-integral polytopes contain certain sets with high probability, the sets of k-tuples with entries in {0, 1/2 , 1}, and exactly one entry equal to 1/2. We precisely determine the threshold number k for which the phase transition occurs. Using these random polytopes we show that establishing integer-infeasibility takes Ω(log n/ log log n) rounds of (almost) any cutting-plane procedure with high probability whenever the number of vertices is θ(3^n). As a corollary, a relationship between the number of vertices and the rank of the polytope with respect to (almost) any cutting-plane procedure follows.
Keywords: random 0-1 polytopes; cutting-plane procedure; integer infeasibility.
Let λ be a regular cardinal. An epimorphism between abelian groups is λ-pure if it is projective with respect to abelian groups of size less than λ. We show that every cotorsion group have λ-pure projective dimension greater than 1 if and only if λ is smaller than the torsion-free part of the group. (For larger λ, the groups are λ-pure projective.) This is related to a (hard) problem of Neeman in module theory about writing modules as factors of direct sums of small modules.
Keywords: Direct sums; direct products; mixed abelian groups; cotorsion groups.
Let us take an arbitrary immersion with even codimension. We derive an explicit formula for the characteristic classes of its multiple point manifolds. The main trick is solving a recursion on cohomology classes using power series.
Keywords: multiple-point manifold; immersion; cobordism class; generating function.
We obtain a new important basic result on splice-quotient singularities in an elegant combinatorial-geometric way: every level of the divisorial filtration of the ring of functions is generated by monomials of the defining coordinate functions. The elegant way is the language of of line bundles based on Okuma's description of the function ring of the universal abelian cover. As an easy application, we obtain a new proof of the End Curve Theorem of Neumann and Wahl.
Keywords: splice-quotient singularity; End Curve Theorem; divisorial filtration.
We consider Newton non-degenerate, isolated surface singularities whose link is a rational homology sphere. We provide an algorithm to compute the Newton boundary of such a singularity from its resolution graph.
Keywords: hypersurface singularities; links of singularities; resolution graphs; Newton boundary; Newton polyhedrons.
Remark. Publisher provided doi:10.1112/S0010437X07002941 does not resolve, so it is not linked.
We derive a recursion for the cohomology classes of multiple point manifolds of an arbitrary immersion with even codimension.
Keywords: multiple-point manifold; characteristic number.
A generalized E-algebra is an algebra isomorphic to its own algebra of module endomorphisms. We give examples of such algebras over a Dedekind domain whose torsion part is not cyclic. It is based on earlier construction of torsion-free E-algebras.
Keywords: mixed E-rings; Dedekind domain.
The matrix type of an algebra is an equivalence relation on natural numbers. Two numbers n and m are equivalent if the ring of n × n matrices is isomorphic to the ring of m × m matrices. We prove that matrix types of ultramatricial algebras over any field is in bijection with subgroups of the multiplicative group of positive rational numbers
Keywords: matrix type of a ring; dimension group; ultramtaricial algebra; automorphism group of a dimension group.
Solving a conjecture of Droste and Kuske, we compute the probability that a gambler will play at least a given number of rounds with a given initial wealth in the Gambler's Ruin game with a biased coin. We present several approaches to the problem.
Keywords: gambler's ruin; random linear order.
Higgins conjectured a generalization of two theorems on decomposition of subgroups of free product of groups: Kuroš Theorem and his own generalization of Grušhko's Theorem. We prove this conjecture by improving Higgins's proof of these theorems using groupoids and covers.
Keywords: free product of groups; free product of goupoids; Kuroš's theorem; Higgins's theorem; Gruško's theorem.
The stabiliser group of an automorphism group of a class 2 nilpotent group is the normal subgroup consisting of elements acting trivially on the centre of the group and on the factor gof the group by the centre. We construct torsion-free class 2 nilpotent groups whose automorphism group is the semidirect product of the stabiliser group and an arbitrary group.
Keywords: class 2 nilpotent group; automorphism group.
Every group has a semidirect product with a locally finite p-group such that the result has an arbitrary outer automorphism group.
Keywords: outer automorphism group; locally finite p-group; Black Box.
If the continuum hypothesis holds then there exists a locally finite p-group of cardinality the successor of countably infinite with trivial centre and outer automorphism group. Without any additional set theoretic hypotheses, every group is an outer automorphism group of arbitrary many locally finite p-groups.
Keywords: locally finite p-group; outer automorphism group; Black Box; Continuum Hypothesis.