Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$17,000.00

Research in universal algebra: constraint satisfaction and residual properties

FY 2019-20

Summary
Ordinary algebra studies the laws of addition, subtraction, multiplication and division of ordinary numbers. Modern algebra studies ""nonstandard"" systems of algebra which arise in various contexts. A simple example is Boolean algebra, which is the system of laws modeled by the logical operators AND, OR, and NOT as they operate on the two truth values 0 (“false”) and 1 (“true”). Much more complicated systems of algebra, many of them bizarre, some of them useful in physics, chemistry, theoretical computer science and engineering, can be invented, studied, and modeled. Universal algebra is the general study of patterns in, and the limits of, nonstandard laws of algebra and their models.******The research to be funded by this proposal has three major parts. First, my team and I will study and reformulate the solutions, announced independently in 2017 by Andrei Bulatov at Simon Fraser University and Dmitriy Zhuk at Lomonosov Moscow State University, of a 20-year-old conjecture in theoretical computer science. This conjecture, called the Constraint Satisfaction Problem Dichotomy Conjecture, asserts that, for a certain class of computational problems, each problem in the class is either computationally easy, or is impossibly hard (in a precise sense); in other words, no problem in the class has intermediate difficulty. The tools of universal algebra were especially useful in proving this conjecture. The goal of this part of my research will be to develop new theories within universal algebra to better explain the discoveries of Bulatov and Zhuk.******In the second part, my team and I will work on two 40-year-old unsolved conjectures concerning patterns involving nonstandard laws of algebra and their finite models. The first conjecture describes circumstances which (it is believed) should imply that the laws of a nonstandard system of algebra will all be deducible from some fixed, finite set of basic laws. This conjecture is known to be true in a very large number of cases; our research will aim to extend the domain in which the conjecture is known to be true. The second conjecture concerns the distribution of certain “irreducible” models of a nonstandard system of algebra. Under rather weak assumptions, when an algebraic system has no irreducible models of infinite size, the irreducible models of the system of finite size seem to obey certain patterns of regularity that we currently cannot explain. My team and I hope to shed light on these mysteries by finding reasons to justify the observed patterns.******The final part of this project involves exploratory investigations of two additional open problems in universal algebra.******This research will serve the world-wide community of pure mathematicians and theoretical computer scientists who seek to understand abstract mathematical phenomena modeled by algebra. It will serve Canada by training students in cutting-edge research, and in bringing prestige to Canada through the solution to high-profile problems.**
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2019-03931
Name nom
Willard, Ross
Department département
Pure Mathematics
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2019
Award amount
17000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
Research in universal algebra: constraint satisfaction and residual properties
Keyword
NSERC
Application summary
Ordinary algebra studies the laws of addition, subtraction, multiplication and division of ordinary numbers. Modern algebra studies ""nonstandard"" systems of algebra which arise in various contexts. A simple example is Boolean algebra, which is the system of laws modeled by the logical operators AND, OR, and NOT as they operate on the two truth values 0 (“false”) and 1 (“true”). Much more complicated systems of algebra, many of them bizarre, some of them useful in physics, chemistry, theoretical computer science and engineering, can be invented, studied, and modeled. Universal algebra is the general study of patterns in, and the limits of, nonstandard laws of algebra and their models.******The research to be funded by this proposal has three major parts. First, my team and I will study and reformulate the solutions, announced independently in 2017 by Andrei Bulatov at Simon Fraser University and Dmitriy Zhuk at Lomonosov Moscow State University, of a 20-year-old conjecture in theoretical computer science. This conjecture, called the Constraint Satisfaction Problem Dichotomy Conjecture, asserts that, for a certain class of computational problems, each problem in the class is either computationally easy, or is impossibly hard (in a precise sense); in other words, no problem in the class has intermediate difficulty. The tools of universal algebra were especially useful in proving this conjecture. The goal of this part of my research will be to develop new theories within universal algebra to better explain the discoveries of Bulatov and Zhuk.******In the second part, my team and I will work on two 40-year-old unsolved conjectures concerning patterns involving nonstandard laws of algebra and their finite models. The first conjecture describes circumstances which (it is believed) should imply that the laws of a nonstandard system of algebra will all be deducible from some fixed, finite set of basic laws. This conjecture is known to be true in a very large number of cases; our research will aim to extend the domain in which the conjecture is known to be true. The second conjecture concerns the distribution of certain “irreducible” models of a nonstandard system of algebra. Under rather weak assumptions, when an algebraic system has no irreducible models of infinite size, the irreducible models of the system of finite size seem to obey certain patterns of regularity that we currently cannot explain. My team and I hope to shed light on these mysteries by finding reasons to justify the observed patterns.******The final part of this project involves exploratory investigations of two additional open problems in universal algebra.******This research will serve the world-wide community of pure mathematicians and theoretical computer scientists who seek to understand abstract mathematical phenomena modeled by algebra. It will serve Canada by training students in cutting-edge research, and in bringing prestige to Canada through the solution to high-profile problems.**