The probability that a linear system is consistent

Pertaining to his work on cryptography, Jack Levine recently asked the following question. If one randomly chooses a system of 10 equations and 4 unknowns with coefficients from the integers modulo n, then what is the probability that one has chosen a consistent system? This paper answers this question. Counting arguments involving elementary linear algebra are the only tools needed.     

Probability that the commutator of two group elements is equal to a given element

In this paper we study the probability that the commutator of two randomly chosen elements in a finite group is equal to a given element of that group. Explicit computations are obtained for groups G which |G^′| is prime and G^′≤Z(G) as well as for groups G which |G^′| is prime and G^′∩Z(G)=1. This paper extends results of Rusin [see D.J. Rusin, What is the probability that two elements of a finite group commute? Pacific J. Math. 82 (1) (1979) 237-247].     

The probability that a slightly perturbed numerical analysis problem is difficult

We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of -tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius . Besides and , this bound depends only on the dimension of the sphere and on the degree of the defining equations.

     

Sets of elements that pairwise generate a linear group

Let G be any of the groups (P)GL(n,q), (P)SL(n,q). Define a (simple) graph Γ=Γ(G) on the set of elements of G by connecting two vertices by an edge if and only if they generate G. Suppose that n is at least 12. Then the maximum size of a complete subgraph in Γ is equal to the chromatic number of Γ if , or if , q is odd and G=(P)SL(n,q). This work was motivated by a question of Blackburn.     

The probability of generating a classical group

We show that a countable totally and discretely ordered set with first element inherently carries the structure of an ordered commutative euclidean monoid, provided its order type is of a certain kind. As an application we specify the order types of all discretely ordered sets which can be expanded to ordered commutative euclidean monoids.     

The probability of generating a permutation group

It is well known that a permutation group of degree can be generated by elements. In this paper we study the asymptotic behavior of the probability of generating a permutation group of degree n with elements. In particular we prove that if n is large enough and elements generate a permutation group G of degree n modulo G G ², then almost certainly these elements generate G itself. Received: 2 January 2002     

Generation of a finite group with Hall maximal subgroups by a pair of conjugate elements

For a finite group G, the set of all prime divisors of |G| is denoted by π(G). P. Shumyatsky introduced the following conjecture, which was included in the “Kourovka Notebook” as Question 17.125: a finite group G always contains a pair of conjugate elements a and b such that π(G) = π(〈a, b〉). Denote by \(\mathfrak{Y}\) the class of all finite groups G such that π(H) ≠ π(G) for every maximal subgroup H in G. Shumyatsky’s conjecture is equivalent to the following conjecture: every group from \(\mathfrak{Y}\) is generated by two conjugate elements. Let \(\mathfrak{V}\) be the class of all finite groups in which every maximal subgroup is a Hall subgroup. It is clear that \(\mathfrak{V} \subseteq \mathfrak{Y}\). We prove that every group from \(\mathfrak{V}\) is generated by two conjugate elements. Thus, Shumyatsky’s conjecture is partially supported. In addition, we study some properties of a smallest order counterexample to Shumyatsky’s conjecture.     

The probability of generating a finite classical group

In this paper generalized Fischer spaces are defined and some results on their classification are obtained.     

The probability of generating a finite simple group

We show that two random elements of a finite simple groupG generateG with probability 1 as |G| . This settles a conjecture of Dixon.     

The probability of generating a finite simple group

We study the probability of generating a finite simple group, together with its generalisation P _G,socG (d), the conditional probability of generating an almost simple finite group G by d elements, given that these elements generate G/socG. We prove that P _G,socG (2) ? 53/90, with equality if and only if G is A₆ or S₆, and establish a similar result for P _G,socG (3). Positive answers to longstanding questions of Wiegold on direct products, and of Mel’nikov on profinite groups, follow easily from our results.     

The probability of generating a finite linear group

We study the asymptotic behavior of the probability of generating a finite completely reducible linear group G of degree n with [ n] elements. In particular we prove that if 3/2 and n is large enough then [ n] randomly chosen elements that generate G modulo O²(G) almost certainly generate G itself.Received: 13 February 2003     

How many elements are needed to generate a finite group with good probability?

We prove that for any real number 0<α<1, there exists a constantc _α such that the probability of generating a finite groupG with [d(G)+c _α log log |G| log log log |G|] elements is at least α.     

Theorem of conflicts for a pair of probability measures

We develop mathematical tools suitable for the construction of conflict models with non-annihilating adversaries. In a set of probability measures we introduce a non-commutative conflict composition and consider the associated dynamical system. We prove that for each couple of non-identical mutually nonsingular measures, the corresponding trajectory of the dynamical system converges to an invariant point represented by a pair of mutually singular measures. The disjoint supports of the limiting measures determine the final re-distribution of the starting area of conflict as a result of an infinite war for existence space (the pure repelling effect).Acknowldegements. The author would like to express the deep thank to the referee for valuable remarks.     

Autocommuting probability of a finite group

Let G be a finite group and Aut(G) the automorphism group of G. The autocommuting probability of G, denoted by Pr(G,Aut(G)), is the probability that a randomly chosen automorphism of G fixes a randomly chosen element of G. In this paper, we study Pr(G,Aut(G)) through a generalization. We obtain a computing formula, several bounds and characterizations of G through Pr(G,Aut(G)). We conclude the paper by showing that the generalized autocommuting probability of G remains unchanged under autoisoclinism.     

The probability of generating a soluble subgroup of a finite group

It is proved that for finite groups G, the probability thattwo randomly chosen elements of G generate a soluble subgrouptends to zero as the index of the largest soluble normal subgroupof G tends to infinity.     

The probability of generating a nilpotent subgroup of a finite group

It is proved that for finite groups G the probability that tworandomly chosen elements of G generate a nilpotent subgrouptends to 0 as the index of the Fitting subgroup of G tends toinfinity.     

The existence of invariant probability measures for a group of transformations

SupposeG is a group of measurable transformations of aσ-finite measure space (X,A, m). A setA ∈A is weakly wandering underG if there are elementsg _n ∈G such that the setsg _nA, n=0, 1,…, are pairwise disjoint. We prove that the non-existence of any set of positive measure which is weakly wandering underG is a necessary and sufficient condition for the existence of aG-invariant, probability measure defined onA and dominating the measurem in the sense of absolute continuity. This paper was written while the author was visiting the Technische Universitat Berlin as a research fellow of the Alexander von Humboldt Foundation.