Three Problems in the Asymptotic Order of Group Elements

This thesis investigates three distinct questions concerning the asymptotic average order of certain group theoretic objects. The three main chapters can be read independently. In chapter zero, we give a high level overview of our results. For a polynomial f [is an element of] [finite field]q[x] with nonzero constant term, define the order of f to be the order of x in the quotient ring [finite field]q[x]/(f). In Chapter 1, we consider the average order of several classes of polynomials as the degree n [right arrow] [infinity]. We show that the average order of an irreducible polynomial is asymptotically [theta]([phi](q^n - 1)) with [phi] the Euler Totient function. Building on work of Stong [32], we show that the asymptotic average order of both squarefree and nonsquarefree polynomials is q^n / n^(1+o(1)). As an application we relate this to the expected orbit size of a vector under iteration by a random invertible matrix. In chapter two, we count the number of compositions of n with k parts whose pairwise gcds are coprime to a given finite set P of primes. We obtain asymptotic results when n [right arrow] [infinity], showing that the number of such compositions is ([product](p[is an element of]P|(n)) h[k](p) + (-1)^(k-1)(k-1)/p^(k-1) (1-1/p)) x ([product](p[is an element of P[crossed pipe](n)) h[k](p) + (-1)^k(k-1)/p^k) n^(k-1)/(k-1)! + O(n^(k-2)) where h[k](p) := (1-1/p)^(k-1)(1+(k-1)/p). Building on work of Bubbolini, Luca and Spiga [6], we also consider the set of compositions whose parts are pairwise coprime. We use a geometric argument to strengthen their result when k = 3. We apply their results to obtain bounds on the average order of a permutation with a given number of cycles. Chapter three is joint work with Huseyin Acan, Charles Burnette, Sean Eberhard, and Eric Schmutz. Motivated by a question of Thibault Godin [17], we show that the probability P₁ that two random permutations in the symmetric group S[n] have the same order is asymptotically n^(-2+o(1)). We compare this to the probability P₂ that two permutations are conjugate, showing by construction that lim sup(n) P₁/P₂ = [infinity]. Additionally, we show by more direct methods that with probability O(log log n / log n) there exists some prime dividing the order of one of the permutations but not the other.