## Research Publications

1. K.R. Matthews, Polynomials which are near to k-th powers, Proc. Camb. Phil. Soc. 61 (1965) 1-5.
This was a problem Harold Davenport gave me in 1963 and was to be chapter 1 of my PhD thesis. He was a fan of Hilbert's Irreducibility Theorem and recommended I study Karl Dörge's paper on that topic. (At one point in my paper, the use I made of that theorem is in fact unnecessary.) Many years later, R. Dvornicich and U. Zannier, On polynomials taking small values at integral arguments, Acta Arithmetica XLII (1982) 189-196, studied a generalization.
2. ---, R.F.C. Walters, Some properties of the continued fraction expansion of (m/n)e1/q, Proc. Camb. Phil. Soc. 67 (1970) 67-74.
This used the 2x2 matrix point of view that R.F.C. Walters had successfully employed in his novel proofs of the continued fraction expansion of e1/q and e2/q (see R.F.C. Walters, Alternate derivation of some regular continued fractions, J. Austr. Math. Soc 8 (1968), 205-212). We used a result of D.N. Lehmer Arithmetical theory of certain Hurwitzian continued fractions, Amer. J. Math. 40 (1918) 375-390.
While enthused with this area, I wasted much time trying to find closed forms for a ratio of series formula for continued fractions such as [1,1,2,2,3,3,..], whose terms increase rapidly enough to allow applying Tannery's theorem (see §63, page 161, Advanced Calculus by G.A. Gibson, MacMillan 1954; also the February 2002, Volume 109, 196-200 AMM article by Josef Hofbauer) to a limiting form of the Euler-Minding formula (see O. Perron, Kettenbrüche, Seite 9.)
3. --- On an inequality of Davenport and Halberstam, J. Lond. Math. Soc. 4 (1972) 638-642. (See PhD thesis).
(The paper was based on the simple observation (pointed out to me by Barry Jones) that the eigenvalues of PP* and P*P are the same, apart from zeros. The well-spaced numbers property then immediately leads via Gershgorin's theorem, to a Large Sieve estimate previously obtained by K.F. Roth.)
4. --- On a bilinear form associated with the large sieve, J. Lond. Math. Soc. 5 (1972) 567-570.
(Using both of Hilbert's inequalities, the Large Sieve estimate N+4.2Δ-1 is obtained. H.L. Montgomery and R.C. Vaughan used the duality idea and subsequently obtained the estimate N+Δ-1 in The large sieve, Mathematika 20 (1973), 119-134.)
5. --- Hermitian forms and the large and small sieve, J. Number Theory 5 (1973) 16-23.
This was an attempt to extract arithmetic information from the dual form of the Large Sieve inequality. The result was a version of Selberg's upper bound sieve estimate and is also to be found in Duality in Analytic Number Theory, P.D.T.A. Elliot, Cambridge Tracts in Mathematics 122, CUP 1996. The result was also obtained independently by Isamu Kobayashi, A Note on the Selberg Sieve and the Large Sieve, Proc. Japan Acad. 49 No. 1 (1973) 1-5.) Recently it resurfaced at Joni's Math Notes. Also see a more general version in Arithmetical Aspects of the Large Sieve Inequality, Olivier Ramaré, D. Surya Ramana, inequality (11.36), page 104.
6. --- A generalization of Artin's conjecture for primitive roots, Acta Arith. 29 (1976) 113-146. (See PhD thesis below and corrections.)
7. --- An example from power residues of the critical problem of Crapo and Rota, J. Number Theory 9 (1977) 203-208.
In 1973, G.-C. Rota gave a talk at Nottingham University and I realised that a certain density formula that arose in my Artin conjecture work was an example of a chromatic polynomial of a geometric lattice.
8. --- On the Eulericity of a graph, J. Graph Theory 2 (1978) 143-148.
(The above power residues problem led me to study the Crapo-Rota formulation of the 4 colour problem and its dual. I wasted some time trying to prove the four colour problem. I did stumble on the above graph theory result, however. It gets a mention in the book Integer Flows and Cycle Covers of Graphs, Cun-Quan Zhang, Monographs and Textbooks in Pure and Applied Mathematics 205, Marcel Dekker 1997
The eulericity e(G) of a bridgeless graph G is the least number of eulerian subgraphs of G which together cover the edges of G. A 1-1 correspondence is shown to exist between the k-tuples of eulerian subgraphs of G and the proper flows mod 2k on a given network based on G. The inequality e(G) ≤ 3 then follows from a result of F. Jaeger. A planar bridgeless graph G is 4-colourable if and only if e(G) ≤ 2.)
9. ---, A.M. Watts, A generalization of Hasse's generalization of the Syracuse algorithm, Acta Arith. 43 (1984) 167-175.
(On reading P. Billingsley's Ergodic Theory and Information Theory, I noticed some ergodic similarity between the 3x+1 type mappings and the continued fraction algorithm. Tony Watts introduced me to exact integer programming in HPL Basic.)
10. ---, A.M. Watts, A Markov approach to the generalized Syracuse algorithm, Acta Arith. 45 (1985) 29-42.
(We realized that the observed frequencies of occupation of congruence classes (mod m) by apparently divergent trajectories, were components of stationary vectors of certain Markov matrices Q(m) associated with T. The general case was subsequently investigated by G.M. Leigh, A Markov process underlying the generalized Syracuse algorithm, Acta Arith. 46 (1985) 125-143.)
11. ---, G.M. Leigh, A generalization of the Syracuse Algorithm in Fq[x], J. Number Theory 25 (1987) 274-278.
Two nontrivial 3x+1 type mappings on 2[x] revealed that the conjectural situation is more complicated than for .
12. --- Computing m-th roots, The College Mathematics Journal 19 (1988) 174-176.
(A discrete version of Newton's method which gives the integer part of (p/q)1/m . Also in H. Lüneburg's book On the Rational Normal Form of Endomorphisms 1987, B.I. Wissenschaftsverlag, Mannheim/Wien/Zürich. See BCMATH program. It was Harley Flanders who supplied the idea of using equation (4).)
13. R.N. Buttsworth, K.R. Matthews, On some Markov matrices arising from the generalized Collatz mapping, Acta Arith. 55 (1990) 43-57.
(Bob Buttsworth proved my conjecture that the irreducible parts of the Markov matrices Q(m) arising from the 3x+1 mapping were primitive. The method was capable of generalisation and allowed us to get detailed information about the ergodic sets for T of relatively prime type.)
14. K.R. Matthews, Some Borel measures associated with the generalized Collatz mapping, Colloquium Math. LXIII (1992) 191-202.
(This paper describes the structure of ergodic sets for mappings T of relatively prime type. Measures corresponding to observed frequencies of occupation of congruence classes by iterates of T, are constructed on the polyadic numbers, with T being ergodic with respect to each measure.)
15. K.R. Matthews, A rational canonical form algorithm, Math. Bohemica 117 (1992) 315-324. (This is an easy to implement algorithm. I discovered the Jordan form version of it in 1978. H. Väliaho discovered the same algorithm: An elementary approach to the Jordan canonical form of a matrix, Amer. Math. Monthly 93 (1986) 711-714. Also see A Simple Jordan Canonical Form Algorithm.)
16. K.R. Matthews, Minimal multipliers for consecutive Fibonacci numbers, Acta Arith. 75 (1996) 205-218.
(This work would not have been done without the help of my CALC and gnubc programs. These strongly suggested that the smallest multipliers for the extended gcd problem of consecutive Fibonacci numbers were unique and explicitly describable by formulae involving the integer part symbol.)
Correction: page 206, line -5, the last minus sign should be (-1)m-1.
17. G. Havas, B.S. Majewski, K.R. Matthews, Extended gcd and Hermite normal form algorithms via lattice basis reduction, Experimental Mathematics, Vol 7 (1998) 125-136,
Our aim was (a) getting small multipliers for the extended gcd problems and more generally (b) unimodular transformation matrices with small entries for the Hermite normal form of an mxn integer matrix A. The algorithms were arrived at by studying limiting versions of LLL applied to [Im|NnA1|···|NAn] as N gets large. Our algorithm is mentioned in the recent book Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications, Murray R. Bremner, CRC Press 2011.
18. K.R. Matthews, The diophantine equation x2-Dy2=N, D > 1, in integers, Expositiones Mathematicae, 18 (2000), 323-331 corrected version (also see slides). We describe a neglected algorithm, in essence due to Lagrange, based on simple continued fractions, for deciding the solubility of x2-Dy2=N, with gcd(x,y)=1, where D > 0 and is not a perfect square. In the case of solubility, the fundamental solutions are also constructed. Unfortunately the original paper was full of errors.
Also see the generalization to the equation Ax2-By2=N in integers, where A > 0, B > 0 and D=AB is not a perfect square and gcd(A,B)=gcd(A,N)=1.
19. K.R. Matthews, Thue's theorem and the diophantine equation x2-Dy2 = ±N, Mathematics of Computation 71 (2002), 1281-1286
A constructive version of a theorem of Thue is used to provide representations of certain integers as x2-Dy2, where D=2,3,5,6,7.
1. I omitted to say on page 1284 that in Case 1 (i), we also have " ".
2. On line -15, "1(a)(2)"" should read "1(i)(a)(2), 1(ii)(b)". Also insert " " before the last "and".
20. K.R. Matthews, The Diophantine equation ax2+bxy+cy2=N, D=b2-4ac > 0, Journal de Théorie des Nombres de Bordeaux, 14 (2002) 257-270. This gives an account of a neglected algorithm of Lagrange, generalising my earlier Expos. Math. paper on x2-Dy2=N, with an unexpected twist when D=5 and aN<0.
1. In the statement of Theorem 1(i), Page 263, line -2:
Replace "X/y is a convergent to ω"
by "X/y is a convergent Ai-1/Bi-1 to ω and Qi=(-1)i2N/|N|;"
2. In the statement of Theorem 1(ii)(a), Page 264, line 1:
Replace "X/y is a convergent to ω*;"
by "X/y is a convergent Ai-1Bi-1to ω* and Qi=(-1)i+12N/|N|;"
3. In the "conversely" part of statement of Theorem 1, Page 264, lines 11,12:
Replace "will be a solution to (4.1), possibly imprimitive"
by "will be a primitive solution to (4.1)."
4. I didn't emphasise that if D=5 and aN < 0, there is always an exceptional solution.
For, from page 269, we have QX2+(2P+1)Xy+Ry2=(-1)r-1
and from page 270, (-1)r-1Q < 0, ie. (-1)r-1a|N| < 0.
So if aN < 0, we have (-1)r-1N/|N| > 0 and consequently (-1)r-1=N/|N|.
Hence QX2+(2P+1)Xy+Ry2=N/|N|, which implies that ax2+bxy+cy2=N, where x=y\theta+|N|X.
5. On page 264, replace "possibly primitive" by "which is primitive".
6. On page 265, delete the sentence "If ω or ω* is purely periodic, we must examine Q2, which corresponds to the third period."
21. T.H. Jackson, K.R. Matthews, On Shanks' algorithm for computing the continued fraction of logba, Journal of Integer Sequences 5 (2002) article 02.2.7. Also see the online BCMath program.
We give a more practical variant of Shanks' 1954 algorithm for computing the continued fraction of logba, for integers a > b > 1, using the floor and ceiling functions and an integer parameter c > 1. The variant, when repeated for a few values of c = 10r, enables one to guess if logba is rational and otherwise find approximately r partial quotients. Here are the first 1000 partial quotients of the continued fraction expansion of log23.
22. John P. Robertson, Keith R. Matthews, A continued fractions approach to a result of Feit, The American Mathematical Monthly 115 April (2008), 346-349.
23. Keith R. Matthews, John P. Robertson, Jim White, Corrigenda to `Calculation of the regulator of Q(√D) by use of the nearest integer continued fraction algorithm', Mathematics of Computation 78 (2009) 615-616.
24. Keith R. Matthews, Unisequences and nearest integer continued fraction midpoint criteria for Pell's equation, Journal of Integer Sequences, Vol. 12 (2009), Article 09.6.7.
Mid-point criteria for solving Pell's equation in terms of the nearest integer continued fraction expansion of √D were derived by H.C. Williams using properties of singular continued fractions. We derive these criteria without the use of singular continued fractions.
25. Keith R. Matthews, John P. Robertson, Jim White, Midpoint criteria for solving Pell's equation using the nearest square continued fraction, Mathematics of Computation 79 (2010) Number 269, 485-499. (Corrected version)
We derive midpoint criteria for Pell's equation x2-Dy2=±1, using the nearest square continued fraction expansion of √D. The period of the expansion is on average 70% that of the regular continued fraction. We also derive similar criteria for the diophantine equation x2-xy-((D-1)/4)y2=±1, where D ≡ 1 (mod 4). We also present some numerical results and conclude with a comparison of the computational performance of the regular, nearest square and nearest integer continued fraction algorithms

(i) Misprint: the second equation in equation (2.1), page 486 should read: instead of .

(ii) In Lemma 2, page 490, ξv+1 should be ξv-1.

26. Keith R. Matthews, John P. Robertson, Purely Periodic Nearest Square Continued Fractions, Journal of Combinatorics and Number Theory, 2, issue 3 (2010) 239-244.
We present a test for determining whether a real quadratic irrational has a purely periodic nearest square continued fraction expansion. This test is somewhat more explicit than the standard test and simplifies the programming of the algorithm.
27. Keith R. Matthews, John P. Robertson, Period length equality for the nearest integer and nearest square continued fraction expansions of a quadratic surd, Glasnik Matematički, 46.2, 269-282, December 2011.
We prove equality of the period-lengths of the nearest integer continued fraction and the nearest square continued fraction, for arbitrary real quadratic irrationals, using inequalities for approximation constants Θn due to Bosma and Kraaikamp.
28. Keith R. Matthews, On the optimal continued fraction expansion of a quadratic surd, J. Austr. Math Soc., 93 (2012), issue 1-2, 133-156.
We describe the period structure of the optimal continued fraction expansion of a quadratic surd, in terms of the period of the nearest square continued fraction expansion. The analysis results in a faster algorithm for determining the optimal continued fraction expansion of a quadratic surd and has been implemented in a BCMATH program.
29. K.R. Matthews, J.P. Robertson, J. White, On a diophantine equation of Andrej Dujella, Math. Glasnik, 48, number 2 (2013) 265-289.
We investigate positive solutions (x,y) of the Diophantine equation x2 – (k2+1)y2 = k2 which satisfy y < k-1, where k ≥ 2. It has been conjectured by Andrej Dujella in 2009 that there is at most one such solution for each k. See slidetalk given at the ANU on 30th November 2012.
30. Keith R. Matthews, Lagrange's Algorithm Revisited: Solving at2+btu+cu2=n in the Case of Negative Discriminant, Journal of Integer Sequences, Vol. 17 (2014), Article 14.11.1. This finds the primitive solutions of the diophantine equation, using a neglected continued fraction method of Lagrange. See Oeuvres de Lagrange, 725-726.

31. K.R. Matthews, J.P. Robertson and A. Srinivasan, On fundamental solutions of binary quadratic form equations, Acta Arith. 169 (2015), 291-299. Nagell gave upper bound estimates for the fundamental solutions of x2-dy2=N, where d > 1 is nonsquare and N ≠ 0. These were generalized by Bengt Stolt to the diophantine equation Ax2 + Bxy + Cy2=N, D = B2 - 4AC > 1 and nonsquare, A > 0, N ≠ 0. Our paper gives a refinement of Stolt's estimates, which results in a characterization of the fundamental solutions.

### Theses

• M.Sc. (University of Queensland) Waring's theorem for polynomials over a field (1966).
(The problem was suggested to me by H. Davenport in 1963 and would have been Chapter 2 of my PhD thesis. My work was never published, as Davenport informed me that R.M. Kubota, Waring's problem for Fq[x], Dissertationes Math. 117, 1974, had independently solved the problem around the same time, but with a less restrictive condition on the characteristic p; also there was no improvement on the corresponding integer case. Subsequently W.A. Webb, Waring's problem in GF[q,x], Acta Arith. 22 (1973) 207-220 and M. Car, Le problème de Waring pour l'anneaux de polynômes sur un corps fini, C.R.A.S., 273, (1971) 141-144, also solved the same problem. More recently, the simplest outstanding case of cubes and p=2 was solved by J. Cherly, Sommes d'exponentielles cubiques dans l'anneau des polynômes en une variable sur le corps à deux éléments, et application au problème de Waring, Astérisque, 198-200, (1991), 83-96.) Luis Gallardo, On the restricted Waring problem over GF(2n)[t], Acta Arith. XCII.2 (2000), 109-113, proved that all polynomials in GF(2n)[t], n > 2, are sums of 9 cubes (10 cubes over GF(16)), thereby improving on old results that treated only polynomials of sufficiently large degree.
• Ph.D. (University of Queensland) An investigation of the Davenport-Halberstam inequality and a generalization of Artin's conjecture for primitive roots (1974).
The Davenport-Halberstam section was based on the simple observation (pointed out to me by Barry Jones) that the eigenvalues of PP* and P*P are the same, apart from zeros. P.D.T.A. Elliot and I. Kobayashi also discovered the same idea. The idea was taken up by H. Montgomery and R.C. Vaughan, Hilbert's Inequality, J. Lond. Math. Soc. (2) 8 (1974) 73-82, who found the best Large Sieve constant.
The Artin Conjecture problem was communicated to me by C. Hooley, via H. Halberstam, on my first sabbatical, at Nottingham in 1972. D.A. Burgess helped me over some hurdles and John Campbell provided the proof that a crucial finite sum was positive. Subsequently H.W. Lenstra Jr., On Artin's Conjecture and Euclid's Algorithm in Global Fields, Inventiones Mathematicae, 42 (1977) 201-224, gave a method which dealt with a general class of similar problems.

Following a suggestion of Martin Huxley, Bob Buttsworth applied the above formula to investigate the conjectural density H(t) of primes p for which a given positive integer t, not a perfect power, is g(p), the least primitive root mod p. Bob attacked the explicit formula for H(t) directly and showed that it was positive. The proof of the general case was never published, partly on account of its complexity. However the method involved some results concerning the inclusion-exclusion principle and these were published. (See R.N. Buttsworth, An Inclusion-Exclusion Transform, Ars Combinatoria 15, 279-300, 1983. The formula for H(t), t prime, is included in this paper.)
In a letter to me dated July 1977, Hendrik Lenstra sketched a short proof of the positivity of H(t) in the general case, using the results of his paper quoted above. This proof did not use the explicit formula for H(t).

L. Murata, On the Magnitude of the Least Primitive Root, Astérisque, 198-199-200, (1991) 253-257, mentions another application of my paper to the conjectural density of primes p such that g(p) > C.
P.D.T.A. Elliot and L. Murata, On the Average of the Least Primitive Root modulo p, J. London Math. Soc. 56 (1997) 435-454, use some of my formulae to extend the results of the previous paper.
A. Paszkiewicz and A. Schinzel also use my work as a basis for their papers Numerical calculation of the density of prime numbers with a given least primitive root, Math. Comp. 71 (2002) 1781-1797 and On the least prime primitive root modulo a prime, Math. Comp. 71 (2002) 1307-1321.

R. Balasubramanian, F. Luca and R. Thangadurai, On the exact degree of ℚ(√a1,√a2 , . . . , √al ) over ℚ, Proc. Amer. Math. Soc. 138 (2010), no. 7, 2283-2288 (see review) give another proof of formula (9.2) of my Acta Arith. paper for the case k=2.

A. Schinzel, Primitive roots and quadratic non-residues, Acta Arith. 149 (2011), no. 2, 16-170, also uses my work.

### In preparation

• Finding the Stolt fundamental solutions of x2 - dy2 = 4n using continued fractions, K.R. Matthews, J.P. Robertson