Computational Solutions to Some Challenging Number Theory and Combinatorial Problems

1 online resource (114 pages) : PDF

2017

University of North Carolina at Charlotte

We use computational assist approach to tackle some challenging and interesting problems in number theory and combinatorics, such as Markoff-Hurwitz equations, integer matrix enumeration, integer sequences, and self-avoiding walks. We present the background, what people did in the past, what we have obtained. In the more than 100 years since Markoff-Hurwitz Equations, they play adecisive role, have turned up in an astounding variety of different settings,from number theory to combinatorics, from classical groups and geometry to theworld of graphs and words, from discrete mathematics to scientificcomputation. We will first introduce other people's work in this area. Then wepresent algorithms for searching and generating solutions to the equation$x_{1}^{2}+x_{2}^{2}+...+x_{n}^{2}=kx_{1}x_{2}...x_{n}$. Solutions arereported for n = 2, 3,\ldots, 9. Properties of solutions are discussed. We willprove that the solutions do not exist when n=4 and k=2 or 3; n=5 and k=2 or 3.Conjectures based on computational results are discussed.The enumeration of integer-matrices has been the subject of considerable studyand it is unlikely that a simple formula exists. The number in question can berelated in various ways to the representation theory of the symmetric group orof the complex general linear group, but this does not make their computationany easier. We will discuss the following five problems: (1)\ the number of $m\times n$matrices over $\{0,1\}$ with each row summing to $s$ and each column summingto $t$; (2) the number of $(0,1)$~- matrices with restriction; (3)the number of nonnegative integer matrices of size $m\times n$with each row sum equal to $s$ and each column sum equal to $t$; (4)\ thenumber of $(-1,0,1)$~- matrices of size $n\times n$; (5) the number of nonnegative matrices with restriction. We will present manyconjectures based on our computation.For self-avoiding walks, we will present: A self-avoiding walk (SAW) is a sequence ofmoves on a lattice not visiting the same point more than once. A SAW on thesquare lattice is prudent if it never takes a step towards a vertex it hasalready visited. Prudent walks differ from most sub-classes of SAWs that havebeen counted so far in that they can wind around their starting point. Someproblems and some sequences arising from prudent walks are also discussed.

doctoral dissertations

Computer science

Ph.D.

Enumeration of Integer-Matrices
Integer Sequence
Markoff-Hurwitz Equation

Computer Science

Chen, Keh-Hsun

Ras, Zbigniew
Wang, Yu
Lu, Aidong
Zhang, Yong

Thesis (Ph.D.)--University of North Carolina at Charlotte, 2017.

This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). For additional information, see http://rightsstatements.org/page/InC/1.0/.

Copyright is held by the author unless otherwise indicated.

Gao_uncc_0694D_11353

http://hdl.handle.net/20.500.13093/etd:594