by Xiao-Qing Jin. / Thesis (M.Ph.)--Chinese University of Hong Kong, 1986 / Bibliography: leaves 47-48

Thesis (Ph. D.)--University of Oregon, 2000. / Typescript. Includes vita and abstract. Includes bibliographical references (leaves 89-93). Also available for download via the World Wide Web; free to University of Oregon users. Address: http://wwwlib.umi.com/cr/uoregon/fullcit?p9955920.

This thesis deals with the behaviour modulo n of linear recurring sequences of integers with characteristic polynomial ƒ ( x ) where n is a positive integer and ƒ ( x ) is a monic polynomial of degree k. Let α [subscript 1], α [subscript 2],...,α [subscript k] be the zeros of ƒ ( x ) and D ( ƒ ) ≠ 0 its discriminant. We focus on the v-sequence ( v [subscript j] ), defined by v [subscript j] = α[superscript j] over [subscript 1] + α [superscript j] over [subscript 2] + ... + α [superscript j] over [subscript k] for j ≥ 0. Our main interest is in algebraic congruences modulo n which hold when n is a prime and which involve only terms of the sequence and rational integers. For k = 1,2 such results have been used extensively in primality testing and have led to the study of various types of pseudoprimes. For k = 3, such results have been studied by Adams and Shanks ( 1 ) under the further assumption ƒ ( 0 ) = - 1. For general k, quite different approaches have been taken by Gurak ( 2 ) and Szekeres ( 3 ). The infinite test matrix modulo n is the infinite matrix M with rows and columns numbered 0,1,2 ... whose ( i, j ) entry is m [subscript ij], the least residue modulo n of v [subscript in + j] - v [subscript i + j] for i ≥ 0 and j ≥ 0. We study the congruence properties of M and especially of the k x k submatrix M ( [superscript k] ) determined by rows and columns 0 to k - 1. Chapters 1 and 2 introduce the thesis and summarise auxiliary results. Chapter 3 presents background on linear recurring sequences with an emphasis on the matrix approach, including the v - sequence and the k " u - sequences " ( whose initial vectors are the rows of Ik ). Chapter 4 comprises theoretical study of the properties of M for a general k, both when n is a prime and for general n, together with investigation of the condition of Gurak ( 2 ). For ( n, k!D ( ƒ ) ) = 1, we show that the condition of Szekeres is equivalent to the condition that m [subscript i0] = 0 for 1 ≤ i ≤ k and also to certain permutation conditions. Gurak ' s condition is then described using these conditions. Chapter 5 assumes k = 3. For this case we study congruences modulo n satisfied by the m [subscript ij] when n is a prime, and hence develop a combination of tests on M ( [superscript 3] ) which are passed by all primes. We report on extensive computer investigation of composites passing these tests. Such composites are found to be rare. Investigation of the relevant work of Adams and Shanks and colleagues, together with use of the permutation condition of Chapter 4, leads to a modification of the earlier tests on M ( [superscript 3] ). Under suitable assumptions we show that the new modified condition is equivalent to the basic condition of Adams and Shanks and also to that of Gurak but has significant advantages over both. References ( 1 ) Adams, W. and Shanks, D. Strong primality tests that are not sufficient, Math. Comp., 39, 1982, 255-300. ( 2 ) Gurak, S. Pseudoprimes for higher - order linear recurrence sequences, Math. Comp., 55, 1990, 783-813. ( 3 ) Szekeres, G., Higher order pseudoprimes in primality testing, pp 451-458, in Combinatorics, Paul Erdos is eighty, Vol. 2 ( Jesztgektm 1993 ), Bolyai Soc. Math. Stud., 2, Jnos Bolyai Math. Soc. Budapest, 1996. / Thesis (M.Sc.)--School of Mathematical Sciences, 2006.

This thesis deals with the behaviour modulo n of linear recurring sequences of integers with characteristic polynomial ƒ ( x ) where n is a positive integer and ƒ ( x ) is a monic polynomial of degree k. Let α [subscript 1], α [subscript 2],...,α [subscript k] be the zeros of ƒ ( x ) and D ( ƒ ) ≠ 0 its discriminant. We focus on the v-sequence ( v [subscript j] ), defined by v [subscript j] = α[superscript j] over [subscript 1] + α [superscript j] over [subscript 2] + ... + α [superscript j] over [subscript k] for j ≥ 0. Our main interest is in algebraic congruences modulo n which hold when n is a prime and which involve only terms of the sequence and rational integers. For k = 1,2 such results have been used extensively in primality testing and have led to the study of various types of pseudoprimes. For k = 3, such results have been studied by Adams and Shanks ( 1 ) under the further assumption ƒ ( 0 ) = - 1. For general k, quite different approaches have been taken by Gurak ( 2 ) and Szekeres ( 3 ). The infinite test matrix modulo n is the infinite matrix M with rows and columns numbered 0,1,2 ... whose ( i, j ) entry is m [subscript ij], the least residue modulo n of v [subscript in + j] - v [subscript i + j] for i ≥ 0 and j ≥ 0. We study the congruence properties of M and especially of the k x k submatrix M ( [superscript k] ) determined by rows and columns 0 to k - 1. Chapters 1 and 2 introduce the thesis and summarise auxiliary results. Chapter 3 presents background on linear recurring sequences with an emphasis on the matrix approach, including the v - sequence and the k " u - sequences " ( whose initial vectors are the rows of Ik ). Chapter 4 comprises theoretical study of the properties of M for a general k, both when n is a prime and for general n, together with investigation of the condition of Gurak ( 2 ). For ( n, k!D ( ƒ ) ) = 1, we show that the condition of Szekeres is equivalent to the condition that m [subscript i0] = 0 for 1 ≤ i ≤ k and also to certain permutation conditions. Gurak ' s condition is then described using these conditions. Chapter 5 assumes k = 3. For this case we study congruences modulo n satisfied by the m [subscript ij] when n is a prime, and hence develop a combination of tests on M ( [superscript 3] ) which are passed by all primes. We report on extensive computer investigation of composites passing these tests. Such composites are found to be rare. Investigation of the relevant work of Adams and Shanks and colleagues, together with use of the permutation condition of Chapter 4, leads to a modification of the earlier tests on M ( [superscript 3] ). Under suitable assumptions we show that the new modified condition is equivalent to the basic condition of Adams and Shanks and also to that of Gurak but has significant advantages over both. References ( 1 ) Adams, W. and Shanks, D. Strong primality tests that are not sufficient, Math. Comp., 39, 1982, 255-300. ( 2 ) Gurak, S. Pseudoprimes for higher - order linear recurrence sequences, Math. Comp., 55, 1990, 783-813. ( 3 ) Szekeres, G., Higher order pseudoprimes in primality testing, pp 451-458, in Combinatorics, Paul Erdos is eighty, Vol. 2 ( Jesztgektm 1993 ), Bolyai Soc. Math. Stud., 2, Jnos Bolyai Math. Soc. Budapest, 1996. / Thesis (M.Sc.)--School of Mathematical Sciences, 2006.

No description available.

[Truncated abstract] A matrix is said to be cyclic if its characteristic polynomial is equal to its minimal polynomial. Cyclic matrices play an important role in some algorithms for matrix group computation, such as the Cyclic Meataxe of Neumann and Praeger. In 1999, Wall and Fulman independently proved that the proportion of cyclic matrices in general linear groups over a finite field of fixed order q has limit [formula] as the dimension approaches infinity. First we study cyclic matrices in maximal reducible matrix groups, that is, the stabilisers in general linear groups of proper nontrivial subspaces. We modify Wall’s generating function approach to determine the limiting proportion of cyclic matrices in maximal reducible matrix groups, as the dimension of the underlying vector space increases while that of the invariant subspace remains fixed. This proportion is found to be [formula] note the change of the exponent of q in the leading term of the expansion. Moreover, we exhibit in each maximal reducible matrix group a family of noncyclic matrices whose proportion is [formula]. Maximal completely reducible matrix groups are the stabilisers in a general linear group of a nontrivial decomposition U1⊕U2 of the underlying vector space. We take a similar approach to determine the limiting proportion of cyclic matrices in maximal completely reducible matrix groups, as the dimension of the underlying vector space increases while the dimension of U1 remains fixed. This limiting proportion is [formula]. ... We prove that this proportion is[formula] provided the dimension of the fixed subspace is at least two and the size q of the field is at least three. This is also the limiting proportion as the dimension increases for separable matrices in maximal completely reducible matrix groups. We focus on algorithmic applications towards the end of the thesis. We develop modifications of the Cyclic Irreducibility Test - a Las Vegas algorithm designed to find the invariant subspace for a given maximal reducible matrix algebra, and a Monte Carlo algorithm which is given an arbitrary matrix algebra as input and returns an invariant subspace if one exists, a statement saying the algebra is irreducible, or a statement saying that the algebra is neither irreducible nor maximal reducible. The last response has an upper bound on the probability of incorrectness.

Thesis (Ph.D.)--University of Western Australia, 2006.

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2004. / Includes bibliographical references (leaves 75-76). Also available in electronic version. Access restricted to campus users.

Thesis (M.S.)--Brigham Young University. Dept. of Mathematics, 2005. / Includes bibliographical references (p. 98-99).

Part I of this thesis presents methods for finding the primitive permutation groups of degree d, where 2500 ≤ d < 4096, using the O'Nan-Scott Theorem and Aschbacher's theorem. Tables of the groups G are given for each O'Nan-Scott class. For the non-affine groups, additional information is given: the degree d of G, the shape of a stabiliser in G of the primitive action, the shape of the normaliser N in S[subscript(d)] of G and the rank of N. Part II presents a new algorithm NormaliserGL for computing the normaliser in GL[subscript(n)](q) of a group G ≤ GL[subscript(n)](q). The algorithm is implemented in the computational algebra system MAGMA and employs Aschbacher's theorem to break the problem into several cases. The attached CD contains the code for the algorithm as well as several test cases which demonstrate the improvement over MAGMA's existing algorithm.