Applications of algebra and algebraic number theory in combinatorics

• Main Author: Do Duc, Tai
• Other Authors: Bernhard Schmidt
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Science::Mathematics::Algebra
• Online Access: https://hdl.handle.net/10356/136727
• Institution: Nanyang Technological University

The aim of this monograph is to demonstrate the application of algebra and algebraic number theory to the study of combinatorics problems. Three problems which will be discussed in this monograph are Group-Invariant Butson Hadamard Matrices, Unique Differences in Symmetric Subsets of Fp and Upper Bounds for Cyclotomic Numbers. The main contribution of this thesis is the construction of new classes of the mentioned objects and better necessary conditions (than the known ones) for their existence. In some cases, our necessary conditions are also sufficient conditions or asymptotically best conditions. A Butson Hadamard matrix is a square matrix whose entries are complex roots of unity such that any two rows of the matrix are orthogonal. We focus on group-invariant Butson Hadamard matrices, that is, Butson Hadamard matrices whose rows and columns are indexed by elements of a group and are invariant under the action of that group. It turns out that the properties of these matrices can be wrapped in a single group-ring equation. By applying appropriate characters to this equation, we can unveil the original object. Using bilinear forms on finite abelian groups and ideas from the theory of relative difference sets, we constructed three new classes of group-invariant Butson Hadamard matrices in this thesis. Furthermore, the tools from algebraic number theory were employed to study necessary conditions for the existence of these matrices. The second problem is unique differences in symmetric subsets of Fp. We say that a subset B of the finite field Fp, where p is a prime, has a unique difference if the reisx∈ Fp such that there is exactly one ordered pair (a, b), a, b∈B, with x=a−b. Otherwise, the set B is said to have no unique difference. Moreover, the subset B is called symmetric if B=−B. Given a prime p, we aim to determine the minimum cardinality g (p) of a symmetric subset of Fp which has no unique difference. Suppose that A is asymmetric subset of Fp which does not contain a unique difference. By studying the Smith Normal Form of the coefficient matrix which corresponds to a linear system that represents the property A containing no unique difference, we find a lower bound for |A|. This is also a lower bound for g(p). Moreover, a known construction by Straus [53] for a symmetric subset of Fp having no unique difference gives us an upper bound for g(p). As these two bounds are asymptotically the same, our lower bound for g(p) is a symptotically best possible. Furthermore, we use our lower bound on g(p) to obtain an improvement over a known result on Weil numbers. The last problem treated in this monograph is upper bounds for cyclotomic numbers. Let q be a power of a prime p, let k be a nontrivial divisor of q−1 and put e= (q−1)/k. We study upper bounds for all cyclotomic numbers (a, b) of order e. The main idea we use is to transform equations over Fq into equations over the field of complex numbers on which we have more information. This can be done if the characteristic p is sufficiently large compared to k. A major tool for the improvements we obtain over known results is new upper bounds on the norm of cyclotomic integers.