Computational Solutions to Some Challenging Number Theory and Combinatorial Problems

Search for this publication on Google Scholar
Gao, S. (2017). Computational Solutions to Some Challenging Number Theory and Combinatorial Problems. Unc Charlotte Electronic Theses And Dissertations.
Download PDF

Analytics

170 views ◎
141 downloads ⇓


Abstract

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.

Details
Author

Gao, Shanzhen

Title

Computational Solutions to Some Challenging Number Theory and Combinatorial Problems

Physical Description

1 online resource (114 pages) : PDF

Date

2017

Degree Granting Institution

University of North Carolina at Charlotte

Abstract

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.

Genre

doctoral dissertations

Subjects--Topics

Computer science

Degree

Ph.D.

Keywords

Enumeration of Integer-Matrices
Integer Sequence
Markoff-Hurwitz Equation

Subject Area

Computer Science

Advisor(s)

Chen, Keh-Hsun

Committee Members

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

Degree Note

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

Rights Statement

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/.

Rights Holder Information

Copyright is held by the author unless otherwise indicated.

Identifier

Gao_uncc_0694D_11353

Permalink

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