Mathematics - Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

Constructions of APN permutations

Author: 
File(s): 
Date created: 
2021-12-15
Supervisor(s): 
Petr Lisonek
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Abstract: 

APN functions defined on finite fields of characteristic two provide the best protection against differential cryptanalysis. They are used extensively in modern symmetric block ciphers. It is beneficial when APN functions are permutations. EA-equivalence and more generally CCZ-equivalence preserves the APN property. Only one example of APN permutations is known in even dimensions and its generalizations are called Kim-type functions. Our first result proves that all Kim-type APN functions in even dimensions greater than six are EA-equivalent to Gold functions. Combined with a previous result this shows that Kim-type APN functions are never CCZ-equivalent to permutations, except for dimension six. Our second result provides several theoretical constructions of Walsh zero spaces for Gold APN functions in odd dimensions. This allows one to construct new APN permutations that are CCZ-equivalent to Gold functions, but they are not EA-equivalent to them or their inverses.

Document type: 
Thesis

The endomorphism ring problem and supersingular isogeny graphs

Author: 
File(s): 
Date created: 
2021-08-06
Supervisor(s): 
Imin Chen
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Abstract: 

Supersingular isogeny graphs, which encode supersingular elliptic curves and their isogenies, have recently formed the basis for a number of post-quantum cryptographic protocols. The study of supersingular elliptic curves and their endomorphism rings has a long history and is intimately related to the study of quaternion algebras and their maximal orders. In this thesis, we give a treatment of the theory of quaternion algebras and elliptic curves over finite fields as these relate to supersingular isogeny graphs and computational problems on such graphs, in particular, consolidating and surveying results in the research literature. We also perform some numerical experiments on supersingular isogeny graphs and establish a number of refined upper bounds on supersingular elliptic curves with small non-integer endomorphisms.

Document type: 
Thesis

Effective population size in infectious disease models

Author: 
File(s): 
Date created: 
2021-07-28
Supervisor(s): 
Caroline Colijn
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Abstract: 

The effective population size Ne was introduced by geneticist Sewall Wright to describe idealized populations. Ne has been a research interest because of its mathematical theory and population management utility. Inspired by such potential, we (re)-introduce the notion of the effective population size N∗ in mathematical epidemiology. Our aim is to see if a simple model with the population size as a variable N∗ can capture disease dynamics in various data types. We introduce a simple SIR model and derive methods of estimating N∗. We apply our methods to both simulated and real outbreak data. We compare N∗ to N and look at how corresponding solution curves match data. We identify preferable methods and settings where these methods are applicable. We state possible implementations of N∗ in public health management as well as extensions and limitations of our methodology.

Document type: 
Thesis

Among graphs, groups, and latin squares

Author: 
File(s): 
Date created: 
2021-08-18
Supervisor(s): 
Luis Goddyn
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.
Abstract: 

A latin square of order n is an n × n array in which each row and each column contains each of the numbers {1, 2, . . . , n}. A k-plex in a latin square is a collection of entries which intersects each row and column k times and contains k copies of each symbol. This thesis studies the existence of k-plexes and approximations of k-plexes in latin squares, paying particular attention to latin squares which correspond to multiplication tables of groups. The most commonly studied class of k-plex is the 1-plex, better known as a transversal. Although many latin squares do not have transversals, Brualdi conjectured that every latin square has a near transversal—i.e. a collection of entries with distinct symbols which in- tersects all but one row and all but one column. Our first main result confirms Brualdi’s conjecture in the special case of group-based latin squares. Then, using a well-known equivalence between edge-colorings of complete bipartite graphs and latin squares, we introduce Hamilton 2-plexes. We conjecture that every latin square of order n ≥ 5 has a Hamilton 2-plex and provide a range of evidence for this conjecture. In particular, we confirm our conjecture computationally for n ≤ 8 and show that a suitable analogue of Hamilton 2-plexes always occur in n × n arrays with no symbol appearing more than n/√96 times. To study Hamilton 2-plexes in group-based latin squares, we generalize the notion of harmonious groups to what we call H2-harmonious groups. Our second main result classifies all H2-harmonious abelian groups. The last part of the thesis formalizes an idea which first appeared in a paper of Cameron and Wanless: a (k,l)-plex is a collection of entries which intersects each row and column k times and contains at most l copies of each symbol. We demonstrate the existence of (k, 4k)-plexes in all latin squares and (k, k + 1)-plexes in sufficiently large latin squares. We also find analogues of these theorems for Hamilton 2-plexes, including our third main result: every sufficiently large latin square has a Hamilton (2,3)-plex.

Document type: 
Thesis

Boussinesq dynamics at a cloud edge: Theory and simulation

Author: 
File(s): 
Date created: 
2021-12-15
Supervisor(s): 
David Muraki
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.
Abstract: 

A consequence of air becoming increasingly less dense with altitude is that the vertical displacement of air against gravity results in up and down oscillatory motion -- much like the restoring force of a spring trying to maintain its equilibrium. This gravity-driven buoyancy effect is what sustains the vertical atmospheric motions known as gravity waves. Just as density decreases with height, the atmosphere is also stratified in its other thermodynamic properties. It becomes lower in pressure and generally cooler with height. When air is displaced vertically, with respect to this stratification, it alters the local thermodynamic state. Additionally, when moisture is included it can exist in either its vapour phase or as suspended liquid water droplets, the latter of which defines the presence of cloud. Altering the moist thermodynamic state can lead to the condensation and evaporation of water. In this way, gravity waves can impact the formation and dynamics of cloud. In this thesis, a simplified model is developed extending the classical Boussinesq approximation for gravity waves to include the effects of vapour-liquid phase change. The result is a mathematical framework that couples the fluid dynamics of gravity waves to the thermodynamics of moisture giving a theory that describes the geometrical evolution of cloud. From this model a particular wave-cloud interaction is identified which has a gravity wave trapped in the clear region below a cloud layer. This is commonly known as a waveguide or wave duct. In this setting, vertical motions of the wave lead to the phase change of water at the cloud-edge boundary resulting in a newly identified mechanism for wave propagation on the edge of cloud. This dynamical solution is constructed within the full physics numerical model ``cm1.'' This represents a first analytically derived moist dynamical solution realized within a numerical weather model. A quantitative comparison of the cm1 computed and approximate Boussinesq solutions show a high degree of agreement in the dynamics. This validates that the moist physics of cm1 are true to the Boussinesq dynamical analysis and illustrates that the cloud-trapped wave-duct solution is achievable in idealized atmospheric conditions.

Document type: 
Thesis

Combinatorial methods for integer partitions

Author: 
File(s): 
Date created: 
2021-08-20
Supervisor(s): 
Amarpreet Rattan
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.
Abstract: 

Integer partitions, while simply defined, are associated with some of the most celebrated results in mathematics. Despite their simple definition, many results on integer partitions can be shockingly difficult to obtain. In this thesis, we use elementary and combinatorial methods to make progress on some fundamental problems related to linear Diophantine equations and integer partitions. We find an efficient method for finding the number of nonnegative integer solutions (x,y,z) of the equation ax+by+cz=n for given positive integers a, b, c, and n. Our formula involves summations of floor functions of fractions. To quickly evaluate these sums, we find a reciprocity relation that generalizes a well-known reciprocity relation of Gauss related to the law of quadratic reciprocity. Furthermore, we use our result for the number of solutions to a particular equation to prove that the above result of Gauss is equivalent to a well-known result of Sylvester related to the Frobenius Coin Problem. Moreover, using this equivalence and our generalization of the reciprocity relation of Gauss, we obtain a nice generalization of Sylvester's result. In a different problem, we prove four conjectures of Berkovich and Uncu regarding some inequalities about relative sizes of two closely related sets consisting of integer partitions whose parts lie in the interval {s,...,L+s}. Further restrictions are placed on the sets by specifying impermissible parts as well as a minimum part. Our methods consist of constructing injective maps between the relevant sets of partitions. We obtain a very natural combinatorial proof of Euler's recurrence for integer partitions using the principle of inclusion and exclusion. Using our approach, we are able to generalize Euler's recurrence in the sense that for sufficiently large n, we can express p(n) explicitly as an integer linear combination of p(n-k), p(n-k-1),... etc. Using such recurrences, we obtain results related to Ramanujan's congruences. For example, if p_m(n) denotes the number of partitions of n that have largest part at most m, we show that for m > 5, the numbers p_m(5n+4) are not divisible by 5 for infinitely many values of n.

Document type: 
Thesis

On the volume of the Birkhoff polytope

File(s): 
Date created: 
2021-04-15
Supervisor(s): 
Marni Mishna
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Abstract: 

The Birkhoff polytope was introduced in 1946 to facilitate the study of doubly stochastic matrices. The volume of the n-th Birkhoff polytope is an essential characteristic but methods to compute this are computationally complex and the volume is only known up to n = 10. In this thesis, we apply a novel automated method to calculate the relative volume using analytic combinatorics in several variables. An implementation using Maple and Sage computes this volume up to n = 6 and we compare to existing methods including interpolation, Euler’s generating function, complex analytic techniques, and Barvinok’s Algorithm (LattE). The key advantage of this method is its robustness and adaptability to variants of the initial problem.

Document type: 
Thesis

On the cogrowth series of free products of finite groups

Author: 
File(s): 
Date created: 
2021-04-19
Supervisor(s): 
Marni Mishna
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Abstract: 

Given a group G with a finite set of generators, S, it is natural to ask if the product of n generators from S evaluate to the identity. The enumerative version of this problem, known as the cogrowth problem, counts the number of such products and studies the associated counting sequence. Many cogrowth sequences are known. This thesis focuses on the free products of finite groups: Specifically, cyclic and dihedral groups. Such groups have the property that their cogrowth generating functions are algebraic functions, and thus, are solutions to implicit polynomial equations. Using algebraic elimination techniques and free probability theory, we establish upper bounds on the degrees of the polynomial equations that they satisfy. This has implications for asymptotic enumeration, and makes it theoretically possible to determine the functions explicitly.

Document type: 
Thesis

The minimax linear fractional programming problem with binary variables

Author: 
File(s): 
Date created: 
2020-08-14
Supervisor(s): 
Abraham Punnen
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Abstract: 

The single ratio linear fractional programming problem when the denominator of the objective function ratio is non-negative is solvable in polynomial time. This result extends to several classes of optimization problems with binary variables. However, when the denominator is allowed to take both positive and negative values, even the unconstrained problem with binary variables is NP-hard. Generalization of this problem where a sum of ratios is also well studied. Experimental results on this however are restricted to non-negative denominators. In this thesis we consider the minimax version of the multi-ratio problem with binary variables. The continuous version of the minimax problem is also well-studied but to the best of our knowledge not much research work has been done on the binary version. We present various mathematical programming formulations of the problem for the case of non-negative denominators as well as arbitrary denominators. We also present algorithms to overcome some of the computational difficulties. Extensive computational analysis has been carried under the scenarios of unconstrained problems, problems with a knapsack constraint, and problems with assignment constraints to assess the relative merits of the models. The analysis disclosed some interesting insights into the structure of the problems.

Document type: 
Thesis

From eigenbeauty to large-deformation horror

File(s): 
Date created: 
2020-08-14
Supervisor(s): 
Nilima Nigam
James Wakeling
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.
Abstract: 

In this thesis we investigate eigenproblems arising in spectral geometry and in the theory of linear elasticity, and numerically study the mechanics of skeletal muscles in three dimensions. We first introduce a novel framework based on a combined finite element-Bayesian optimization strategy to tackle problems in spectral optimization. This method is used to investigate the Pólya-Szegö conjecture for the Dirichlet eigenvalues of the Laplacian on polygons and a similar conjecture for the Steklov eigenvalues for the Laplacian is proposed. We next explore four different eigenproblems for the Lamé operator in linear elasticity. For each we establish the existence of a countable (finite or infinite) set of eigenpairs. The first one relates to Steklov eigenpairs for elasticity where the spectral parameter appears on a Robin type boundary condition. The second eigenproblem concerns eigenmodes whose tangential traction and normal displacement on the boundary are constrained. The third eigenproblem refers to eigenmodes whose normal traction and tangential displacement are fixed on the boundary. We finally consider the Jones eigenvalue problem: elastic modes are assumed to be traction free on the boundary with the extra condition that they must be purely tangential to the boundary. For each eigenproblem, new versions of Korn’s inequalities are proven to establish the existence of a point spectrum. Finally, we present a new numerical framework to computationally simulate the large deformations of skeletal muscles in three dimensions. A semi-implicit method in time and finite element method in space are coupled to approximate the solutions of the nonlinear dynamic system that governs the deformation of these tissues. This framework is later utilized to explore questions on the effects of density and inertia in muscle performance, to investigate the energy distribution in muscle during isometric contractions, and to study the energetics of muscles during compression tests on the surface of the tissues.

Document type: 
Thesis