Search

Without using the classification of finite simple groups (CFSG), we show that the probability that two random elements of Sn$$ {S}_n $$ generate a primitive group smaller than An$$ {A}_n $$ is at most exp(−c(nlogn)1/2)$$ \exp \left(-c{\left(n\log n\right)}^{1/2}\right) $$. As a corollary we get Dixon's asymptotic expansion 1−1/n−1/n2−4/n3−23/n4−⋯$$ 1-1/n-1/{n}^2-4/{n}^3-23/{n}^4-\cdots $$for the probability that two random elements of Sn$$ {S}_n $$ (or An$$ {A}_n $$) generate a subgroup containing An$$ {A}_n $$. [ABSTRACT FROM AUTHOR]

For G a finite group, let d 2 (G) denote the proportion of triples (x , y , z) ∈ G 3 such that [ x , y , z ] = 1 . We determine the structure of finite groups G such that d 2 (G) is bounded away from zero: if d 2 (G) ≥ ϵ > 0 , G has a class-4 nilpotent normal subgroup H such that [G : H] and | γ 4 (H) | are both bounded in terms of ϵ . We also show that if G is an infinite group whose commutators have boundedly many conjugates, or indeed if G satisfies a certain more general commutator covering condition, then G is finite-by-class-3-nilpotent-by-finite. [ABSTRACT FROM AUTHOR]

A transversal in an n×n$n \times n$ latin square is a collection of n$n$ entries not repeating any row, column, or symbol. Kwan showed that almost every n×n$n \times n$ latin square has (1+o(1))n/e2n$\bigl ((1 + o(1)) n / e^2\bigr)^n$ transversals as n→∞$n \rightarrow \infty$. Using a loose variant of the circle method we sharpen this to (e−1/2+o(1))n!2/nn$(e^{-1/2} + o(1)) n!^2 / n^n$. Our method works for all latin squares satisfying a certain quasirandomness condition, which includes both random latin squares with high probability as well as multiplication tables of quasirandom groups. [ABSTRACT FROM AUTHOR]

We describe primitive association schemes X of degree n such that Aut (X) is imprimitive and | Aut (X) | ≥ exp (n 1 / 8) , contradicting a conjecture of Babai. This and other examples we give are the first known examples of nonschurian primitive coherent configurations (PCC) with more than a quasipolynomial number of automorphisms. Our constructions are "Hamming sandwiches", association schemes sandwiched between the dth tensor power of the trivial scheme and the d-dimensional Hamming scheme. We study Hamming sandwiches in general, and exhaustively for d ≤ 8 . We revise Babai's conjecture by suggesting that any PCC with more than a quasipolynomial number of automorphisms must be an association scheme sandwiched between a tensor power of a Johnson scheme and the corresponding full Cameron scheme. If true, it follows that any nonschurian PCC has at most exp O (n 1 / 8 log n) automorphisms. [ABSTRACT FROM AUTHOR]

Form an n × n matrix by drawing entries independently from {±1} (or another fixed nontrivial finitely supported distribution in Z) and let φ be the characteristic polynomial. We show, conditionally on the extended Riemann hypothesis, that with high probability φ is irreducible and Gal(φ) ≥ An. [ABSTRACT FROM AUTHOR]

Let G = SCl n (q) be a quasisimple classical group with n large, and let x 1 , ... , x k ∈ G be random, where k ≥ q C . We show that the diameter of the resulting Cayley graph is bounded by q 2 n O (1) with probability 1 - o (1) . In the particular case G = SL n (p) with p a prime of bounded size, we show that the same holds for k = 3 . [ABSTRACT FROM AUTHOR]

A family of vectors in [k]n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [k]n invariant under a transitive group of symmetries is o(kn), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets. [ABSTRACT FROM AUTHOR]

Let ${\mathbb{P}}(ord\pi = ord\pi ')$ be the probability that two independent, uniformly random permutations of [n] have the same order. Answering a question of Thibault Godin, we prove that ${\mathbb{P}}(ord\pi = ord\pi ') = {n^{ - 2 + o(1)}}$ and that ${\mathbb{P}}(ord\pi = ord\pi ') \ge {1 \over 2}{n^{ - 2}}lg*n$ for infinitely many n. (Here lg*n is the height of the tallest tower of twos that is less than or equal to n.) [ABSTRACT FROM AUTHOR]

Define (X n) on Z / q Z by X n + 1 = 2 X n + b n , where the steps b n are chosen independently at random from - 1 , 0 , + 1 . The mixing time of this random walk is known to be at most 1.02 log 2 q for almost all odd q (Chung, Diaconis, Graham in Ann Probab 15(3):1148–1165, 1987), and at least 1.004 log 2 q (Hildebrand in Proc Am Math Soc 137(4):1479–1487, 2009). We identify a constant c = 1.01136 ⋯ such that the mixing time is (c + o (1)) log 2 q for almost all odd q. In general, the mixing time of the Markov chain X n + 1 = a X n + b n modulo q, where a is a fixed positive integer and the steps b n are i.i.d. with some given distribution in Z , is related to the entropy of a corresponding self-similar Cantor-like measure (such as a Bernoulli convolution). We estimate the mixing time up to a 1 + o (1) factor whenever the entropy exceeds (log a) / 2 . [ABSTRACT FROM AUTHOR]

It is well known that the proportion of pairs of elements of SL(n,q) which generate the group tends to 1 as qn → ∞. This was proved by Kantor and Lubotzky using the classification of finite simple groups. We give a proof of this theorem which does not depend on the classification. An essential step in our proof is an estimate for the average of (ord g)−1 when g ranges over GL (n,q), which may be of independent interest. We prove that this average is exp(−(2−o(1)) √n log n log q). [ABSTRACT FROM AUTHOR]

We consider the probability p(Sn) that a pair of random permutations generates either the alternating group An or the symmetric group Sn. Dixon (1969) proved that p(Sn) approaches 1 as n→∞ and conjectured that p(Sn) = 1 − 1/n+o(1/n). This conjecture was verified by Babai (1989), using the Classification of Finite Simple Groups. We give an elementary proof of this result; specifically we show that p(Sn) = 1 − 1/n+O(n−2+ε). Our proof is based on character theory and character estimates, including recent work by Schlage-Puchta (2012). [ABSTRACT FROM AUTHOR]

We prove an asymptotic for the number of additive triples of bijections (1,...,n) → ℤ/nℤ, that is, the number of pairs of bijections π1,π2:(1,...n) → ℤ/nℤ such that the pointwise sum π1 + π2 is also a bijection. This problem is equivalent to counting the number of orthomorphisms or complete mappings of ℤ/nℤ, to counting the number of arrangements of n mutually nonattacking semiqueens on an n x n toroidal chessboard, and to counting the number of transversals in a cyclic Latin square. The method of proof is a version of the Hardy-Littlewood circle method from analytic number theory, adapted to the group (ℤ /nℤ)n. [ABSTRACT FROM AUTHOR]

Let i(n, k) be the proportion of permutations π ∊ Sn having an invariant set of size k. In this note, we adapt arguments of the second author to prove that i(n, k) ≍k-δ(1 + log k) -3/2 uniformly for 1 ≤ k≤ n/2, where δ =1 - 1+log log 2/log 2. As an application, we show that the proportion of π ∊ Sn contained in a transitive subgroup not containing An is at least n-δ+o(1) if nis even. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to establish a method of obtaining closed-form solutions in isotropic hyperelasticity using the complementary energy, the Legendre transform of the strain energy function. Using the complementary energy, the stress becomes the independent variable and the strain the dependent variable. Some of the implications of this formulation of the equations are explored and illustrative examples of solutions for spherical and cylindrical inflation for several forms of the complementary energy are presented. [ABSTRACT FROM AUTHOR]

Here is a simplified proof that every sharply transitive subset of PGL2(K) is a coset of a subgroup, for every finite field K. [ABSTRACT FROM AUTHOR]

The commuting probability of a finite group is defined to be the probability that two randomly chosen group elements commute. Let P ⊂ (0,1] be the set of commuting probabilities of all finite groups. We prove that every point of P is nearly an Egyptian fraction of bounded complexity. As a corollary, we deduce two conjectures of Keith Joseph from 1977: all limit points of P are rational, and P is well ordered by >. We also prove analogous theorems for bilinear maps of abelian groups. [ABSTRACT FROM AUTHOR]

Folkman's theorem asserts that for each [ABSTRACT FROM AUTHOR]

We generalise an argument of Leader, Russell, and Walters to show that almost all sets of $d+ 2$ points on the $(d- 1)$-sphere ${S}^{d- 1} $ are not contained in a transitive set in some ${\mathbf{R} }^{n} $. [ABSTRACT FROM PUBLISHER]