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

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.

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.

### Organisations

- University College London, United Kingdom (Fellow, Lead Research Organisation)
- University of Oxford, United Kingdom (Collaboration)
- German Research Foundation (Collaboration)
- Charles III University of Madrid (Collaboration)
- Liaoning Normal University (Collaboration)
- University of Regina, Canada (Collaboration)
- Dalian University of Technology, China (Collaboration)
- College of William and Mary, United States (Collaboration)
- Jiangsu Normal University (Collaboration)
- University of Melbourne, Australia (Collaboration)
- Qufu Normal University (Collaboration)
- Claude Bernard University Lyon 1 (UCBL) (Collaboration)

## People |
## ORCID iD |

Alan David Sokal (Principal Investigator / Fellow) |

### Publications

Elvey Price A
(2020)

*Phylogenetic Trees, Augmented Perfect Matchings, and a Thron-type Continued Fraction (T-fraction) for the Ward Polynomials*in The Electronic Journal of Combinatorics
Elvey Price Andrew
(2020)

*Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials*in arXiv e-prints
Fallat S
(2017)

*Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples*in Linear Algebra and its Applications
Fallat S
(2021)

*Corrigendum to "Total positivity of sums, Hadamard products and Hadamard powers: Results and counterexamples" [Linear Algebra Appl. 520 (2017) 242-259]*in Linear Algebra and its Applications
Lv J
(2018)

*Duality and the universality class of the three-state Potts antiferromagnet on plane quadrangulations*in Physical Review E
Pétréolle M
(2021)

*Lattice paths and branched continued fractions II. Multivariate Lah polynomials and Lah symmetric functions*in European Journal of Combinatorics
Salas J
(2021)

*The Graham--Knuth--Patashnik recurrence: Symmetries and continued fractions*in Electronic Journal of Combinatorics
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
Sokal A
(2022)

*Total positivity of some polynomial matrices that enumerate labeled trees and forests I: forests of rooted labeled trees*in Monatshefte für MathematikDescription | 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 |