Generalised Frobenius numbers: geometry of upper bounds, Frobenius graphs and exact formulas for arithmetic sequences

Mohammed, Dilbak 2017. Generalised Frobenius numbers: geometry of upper bounds, Frobenius graphs and exact formulas for arithmetic sequences. PhD Thesis, Cardiff University. Item availability restricted.

Preview	PDF - Accepted Post-Print Version Download (1MB) | Preview
	PDF - Supplemental Material Restricted to Repository staff only Download (326kB)

Abstract

Given a positive integer vector ${\ve a}=(a_{1},a_{2}\dots,a_k)^t$ with \bea 1< a_{1}<\cdots<a_{k}\, \quad \text{and}\quad \gcd(a_{1},\ldots,a_{k})=1 \,. \eea The Frobenius number of the vector ${\ve a}$, $\frob_k({\ve a})$, is the largest positive integer that cannot be represented as $\sum\limits_{i=1}^{k}a_{i}x_{i}$, where $x_{1},\ldots,x_{k}$ are nonnegative integers. We also consider a generalised Frobenius number, known in the literature as the $s$-Frobenius number, $\frob_{s}(a_{1},a_{2},\ldots,a_{k})$, which is defined to be the largest integer that cannot be represented as $\sum\limits_{i=1}^{k}a_{i}x_{i}$ in at least $s$ distinct ways. The classical Frobenius number corresponds to the case $s=1$. The main result of the thesis is the new upper bound for the $2$-Frobenius number, \be \label{equ:UB} \frob_2(a_{1},\ldots,a_{k})\leq \frob_1(a_{1},\ldots,a_{k}) +2\left(\frac {(k-1)!}{{2(k-1) \choose k-1}}\right)^{1/(k-1)} \left(a_{1}\cdots a_{k}\right)^{1/(k-1)}\,, \ee that arises from studying the bounds for the quantity $ \big(\frob_s({\ve a})-\frob_1({\ve a})\big)\left(a_{1}\cdots a_{k}\right)^{-1/(k-1)}\,. $ The bound (\ref{equ:UB}) is an improvement, for $s=2$, on a bound given by Aliev, Fukshansky and Henk \cite{aliev2011generalized}. Our proofs rely on the geometry of numbers. By using graph theoretic techniques, we also obtain an explicit formula for the $2$-Frobenius number of the arithmetic progression $a,a+d,\ldots a+nd$ (i.e. the $a_{i}$'s are in an arithmetic progression) with $\gcd(a,d)=1$ and $1\leq d<a$. \be \label{2} \frob_{2}(a,a+d,\ldots a+nd)=a\left\lfloor\frac{a}{n}\right\rfloor+d(a+1)\,, \quad n \in \{2,3\}. \ee % This result generalises Roperts's result \cite{Roberts} for the Frobenius number of general arithmetic sequences. In the course of our investigations we derive a formula for the shortest path and the distance between any two vertices of a graph associated with the positive integers $a_{1},\ldots,a_{k}$. Based on our results, we observe a new pattern for the $2$-Frobenius number of general arithmetic sequences $a,a+d,\dots,a+nd$, $\gcd(a,d)=1$, which we state as a conjecture. Part of this work has appeared in \cite{Alievdistance}.

Item Type:	Thesis (PhD)
Date Type:	Completion
Status:	Unpublished
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Date of First Compliant Deposit:	21 February 2017
Last Modified:	19 Apr 2021 09:54
URI:	https://orca.cardiff.ac.uk/id/eprint/98161

Actions (repository staff only)

Edit Item