Positivity problems at the boundary between combinatorics and analysis

Lead Research Organisation: University College London
Department Name: Mathematics

Abstract

Combinatorics is the branch of mathematics concerned with counting finite
structures of various types (permutations, graphs, etc.); it has
applications in computer science, statistical physics, molecular biology,
and many other fields. Analysis, by contrast, is the branch of mathematics
concerned with continuous variation (i.e. functions of real or complex
numbers); it has applications in nearly all fields of science and engineering.
The proposed research lies at the interface between combinatorics and
analysis: it involves using combinatorial tools to study analytic problems,
and vice versa. More specifically, the proposed research comprises
three themes, all of which are aimed at exploring novel positivity properties
that arise at the interface between combinatorics and analysis.
The first theme involves studying situations in which inverse powers
of combinatorially important polynomials have Taylor expansions with
positive coefficients. The second theme involves studying situations
in which certain matrices formed from sequences of combinatorially
important polynomials have a property called "total positivity".
The third theme involves studying situations in which certain power
series formed from combinatorially important polynomials (for example,
the counting polynomials of connected graphs) have positive coefficients.
This latter property was discovered empirically by the PI in many
situations, but most of these have not yet been proven, and their deeper
meaning remains to be elucidated.

Planned Impact

Economic and Societal Impacts:

The nature of research in pure mathematics is that it is traditionally
somewhat removed from direct commercial and governmental usage.
But since combinatorics is fundamental to computer science
and in particular to the study of algorithmic complexity,
advances in combinatorics can have unforeseen implications and applications
over the longer term.
For instance, the development of randomised algorithms
--- inspired in part by Monte Carlo algorithms from statistical physics ---
has radically altered the landscape of computational complexity,
because some problems that are intractable for exact computation (NP-hard)
can be tractable for approximate computation by a randomised algorithm (fpras).
In a similar way, ideas from the statistical mechanics
of phase transitions have clarified the distinction
between "difficult'' and "less-difficult'' instances
of NP-complete problems such as Boolean satisfiability (SAT).
Though it would be foolhardy to confidently predict similar practical
spin-offs from this (or any other) pure mathematical research,
it is not unreasonable to imagine that
the research programme proposed here could contribute in the long run,
in probably unpredictable ways, to EPSRC's Digital Economy strategic priority.
Over the shorter term it could very well also contribute to
EPSRC's priority area of New Connections between the Mathematical
and Computer Sciences, in such areas as
deterministic and random algorithms, computational complexity,
symbolic computation, and applications of graph theory and combinatorics.
In order to facilitate these potential spin-offs,
I propose to begin by giving seminars to computer scientists
on various aspects of this work:
for instance, at the annual Analysis of Algorithms (AofA) meeting,
at which my collaborator on theme #3, Jim Fill, is a regular participant.


Public Engagement:

Over the past two decades I have given numerous talks for the general public
--- in the UK, USA, Canada, and a dozen European and Latin American countries ---
aimed at raising public understanding of scientific methodology and scientific results.
I now propose to carry this experience over to popularisation
of my own (and my colleagues') mathematical research.
In fact, combinatorics is a subject area within mathematics
that is perhaps easier to popularise than other fields,
because many of its definitions are elementary and easily visualizable.
I have already given several such talks aimed at undergraduates,
so adaptation for a general educated public curious about mathematics
ought not be too difficult.

In addition, Alex Scott and I wrote a semi-popular article on the
mathematics of phase transitions, aimed at British high-school students
considering university study in mathematics;
this article was later translated into French and published in the magazine Quadrature.
I propose to write further articles of a similar nature, on subjects related to this research.

Publications

10 25 50

publication icon
Salas J (2021) The Graham--Knuth--Patashnik recurrence: Symmetries and continued fractions in Electronic Journal of Combinatorics

publication icon
Salas J (2022) Ergodicity of the Wang-Swendsen-Kotecký algorithm on several classes of lattices on the torus in Journal of Physics A: Mathematical and Theoretical

 
Description This project is intradisciplinary research that lies at the interface between several areas of mathematics: notably enumerative combinatorics, analysis, and linear algebra.

Combinatorics is the branch of mathematics concerned with studying discrete structures of various types (permutations, graphs, etc.); enumerative combinatorics is the subfield devoted to counting these objects. Combinatorics has applications in computer science, statistical physics, molecular biology, and many other fields.

Analysis, by contrast, is the branch of mathematics concerned with continuous variation (i.e. functions of real or complex numbers); it has applications in nearly all fields of science and engineering.

Algebra (in the specialised sense employed in this project) is concerned with manipulating algebraic expressions such as polynomials, formal power series, and continued fractions; linear algebra is concerned with matrices.

This research project involves using combinatorial and linear-algebraic tools to study analytic problems, and vice versa. More specifically, we are concerned with a property of matrices called "total positivity", and we apply it to matrices that enumerate combinatorial objects such as permutations, set partitions, and graphs.

At the most fundamental level, we have introduced a new property called "coefficientwise Hankel-total positivity", and we have shown that a large number of combinatorially natural sequences of polynomials are coefficientwise Hankel-totally positive. To do this, we have developed a variety of new methods for proving total positivity, notably continued fractions and production matrices.

Our most innovative contribution is the development of a new tool called "branched continued fractions": our long (150-page) treatise on this method has been accepted for publication in the Memoirs of the American Mathematical Society. In this paper we generalise the "classical" continued fractions of Euler, Jacobi and Stieltjes to "branched" continued fractions indexed by a parameter m >= 1 (where m=1 is the classical case) and we prove total-positivity results for all of them. We show that many simple Stieltjes moment sequences, such as (n!)^2 and (2n)!, that have ugly classical continued fractions -- for which no explicit formula is known -- nevertheless have extremely simple branched continued fractions, from which their total-positivity properties can be immediately deduced. We also generalise Gauss' famous continued fraction for ratios of contiguous hypergeometric series 2F1 to branched continued fractions for ratios of contiguous hypergeometric series rFs for all r,s. Using these tools (in the Memoirs paper and in subsequent work), we apply branched continued fractions to prove coefficientwise Hankel-total positivity for many sequences of combinatorial polynomials that were not amenable to treatment by earlier methods. We are continuing to develop and apply this powerful tool.

We also discovered a surprising connection between branched continued fractions and multiple orthogonal polynomials (MOPs). The latter have been developed over the last 20-30 years by mathematicians working with "special functions", but the link with branched continued fractions was completely unexpected. We think that this connection will be useful in both directions -- using combinatorial methods to study MOPs, and using MOP ideas to study combinatorial polynomials -- and we are now working to develop it.
Exploitation Route The outcomes of this work will be of direct use to mathematicians and computer scientists working in enumerative combinatorics, and also to mathematicians working in special functions, linear algebra, and several fields of analysis. Most importantly, the new _tools_ we have developed -- notably branched continued fractions and production matrices -- can be taken forward and put to use for attacking a variety of problems beyond those we ourselves have studied.
Sectors Digital/Communication/Information Technologies (including Software)

 
Description Combinatorial problems from an analytical point of view -- Alex Dyachenko 
Organisation German Research Foundation
Country Germany 
Sector Charity/Non Profit 
PI Contribution I have discovered the phenomenon of coefficientwise Hankel-total positivity in many sequences of combinatorial polynomials, and I am trying to devise methods for proving it.
Collaborator Contribution Alexander Dyachenko received a fellowship from the German Research Foundation (Deutsche Forschungsgemeinschaft) to spend 2 years working with me at University College London. Dr. Dyachenko brings a background in analysis, and in particular a familiarity with moment problems, that will be very useful in our applications to combinatorial problems.
Impact None yet, but we have several projects in preparation.
Start Year 2018
 
Description Continued fractions and linear recurrences -- Jesus Salas 
Organisation Charles III University of Madrid
Country Spain 
Sector Academic/University 
PI Contribution I provided questions and methods concerning continued fractions and total positivity.
Collaborator Contribution Professor Jesus Salas provided expertise in computer algebra.
Impact None yet, but we have a paper in progress.
 
Description Continued fractions for combinatorial polynomials -- JIang Zeng 
Organisation Claude Bernard University Lyon 1 (UCBL)
Department Camille Jordan Institute
Country France 
Sector Academic/University 
PI Contribution I found empirically some new continued fractions for multivariate combinatorial polynomials.
Collaborator Contribution Jiang Zeng (Univ Lyon) contributed the methods that have allowed us to prove some of these continued fractions.
Impact None yet -- work still in progress. But one of our long articles is close to being finished.
Start Year 2014
 
Description Positivity for fractional powers of formal power series -- Alex Scott 
Organisation University of Oxford
Department Nuffield Department of Medicine
Country United Kingdom 
Sector Academic/University 
PI Contribution Alex Scott (Oxford) and I have continued our work on positivity for fractional powers of formal power series. We are currently proving positivity for some multivariate formal power series arising as fractional powers of determinants.
Collaborator Contribution We work together on all aspects, and it is difficult to disentangle our contributions.
Impact Paper still in preparation.
 
Description Total positivity and Hadamard products -- Shaun Fallat and Charles Johnson 
Organisation College of William & Mary
Country United States 
Sector Academic/University 
PI Contribution Shaun Fallat (U Regina), Charles Johnson (William and Mary) and I worked together to prove theorems about the total positivity of Hadamard products. I provided the initial conjecture, and I provided many counterexamples (found by computer search).
Collaborator Contribution Johnson contributed an important idea to the proof (the idea of using contiguous minors). Fallat and Johnson contributed other useful ideas as well.
Impact Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples, Linear Algebra and Its Applications 520, 242--259 (2017)
Start Year 2014
 
Description Total positivity and Hadamard products -- Shaun Fallat and Charles Johnson 
Organisation University of Regina
Country Canada 
Sector Academic/University 
PI Contribution Shaun Fallat (U Regina), Charles Johnson (William and Mary) and I worked together to prove theorems about the total positivity of Hadamard products. I provided the initial conjecture, and I provided many counterexamples (found by computer search).
Collaborator Contribution Johnson contributed an important idea to the proof (the idea of using contiguous minors). Fallat and Johnson contributed other useful ideas as well.
Impact Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples, Linear Algebra and Its Applications 520, 242--259 (2017)
Start Year 2014
 
Description Total positivity and combinatorics -- Andrew Elvey Price 
Organisation University of Melbourne
Country Australia 
Sector Academic/University 
PI Contribution I am providing ideas concerrning total positivity, and conjectures and open questions.
Collaborator Contribution Andrew Elvey Price (a PhD student of Professor Tony Guttmann) has already made several important contributions, concerning a T-fraction for the Ward polynomials and concerning functional equations for generalizations of the Bell polynomials.
Impact https://arxiv.org/abs/2001.01468
Start Year 2017
 
Description Total positivity and combinatorics -- Bao-Xuan Zhu 
Organisation Jiangsu Normal University
Country China 
Sector Academic/University 
PI Contribution Bao-Xuan Zhu is visiting me at UCL for approximately 12 months (September 2017 - August 2018) to collaborate on problems related to total positivity and combinatorics. This visit is partly funded by the China Scholarship Council and partly by this EPSRC grant. I am contributing many ideas concerning total positivity, and many conjectures and open problems.
Collaborator Contribution Professor Zhu is contributing his expertise in combinatorics, especially continued fractions, recurrences, etc.
Impact https://arxiv.org/abs/1807.03271 and other articles in progress
Start Year 2017
 
Description Total positivity and combinatorics -- Lili Mu 
Organisation Liaoning Normal University
Country China 
Sector Academic/University 
PI Contribution I provided questions and methods concerning total positivity.
Collaborator Contribution Dr. Lili Mu provided additional expertise concerning combinatorics, especially Riordan arrays.
Impact None yet, but we have some projects in progress.
Start Year 2019
 
Description Total positivity and combinatorics -- Lily Liu 
Organisation Qufu Normal University
Country China 
Sector Academic/University 
PI Contribution Professor Lily Li Liu (Qufu Normal University, China) was a visitor in my research group at UCL for 5 months (Sept 2018 - Jan 2019). We worked together on various problems related to combinatorics and total positivity.
Collaborator Contribution Professor Liu has an excellent facility for devising complicated algebraic proofs.
Impact We are currently working on a joint paper concerning linear transformations that preserve strong log-convexity or strong log-concavity.
Start Year 2018
 
Description Total positivity and combinatorics -- Xi Chen 
Organisation Dalian University of Technology
Country China 
Sector Academic/University 
PI Contribution I provided ideas and methods concerning total positivity.
Collaborator Contribution Dr. Chen provided expertise in combinatorics, especially concerning exponential Riordan arrays,
Impact None yet, but we have several projects in progress.
Start Year 2019