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}.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:704905 |
| Date | January 2015 |
| Creators | Mohammed, Dilbak |
| Publisher | Cardiff University |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://orca.cf.ac.uk/98161/ |
Page generated in 0.0039 seconds