Transcript Automated Discovery in Pure Mathematics

Automated Discovery in
Pure Mathematics
Simon Colton
Universities of Edinburgh and York
Overview of Talk
Some example discoveries

ATP, CSP, CAS, ad-hoc methods
The HR system


Automated theory formation
Overview of applications
Application to mathematical discovery

Finite algebras, number theory, refactorables
Demonstration

NumbersWithNames program
Automated Discoveries #1
Robbins algebras are boolean

Automated theorem proving, McCune+Wos
Quasigroup existence problems (QG6.17)

Constraint solvers, John Slaney et al.
Inconsistency in Newton’s Principia

Formal methods (NS-analysis), Fleuriot
Automated Discoveries #2
Mersenne prime: 26972593 – 1

Distributed (internet) search, CAS
New geometry results

Chou using Wu’s method
Simple axiomatisations of algebras


Group: x(y(((zz-1)(uy)-1)x))-1=u
McCune and Kunen, ATP
Automated Discoveries #3
Fajtlowicz’s Graffiti graph theory program


All G, Chrom+Rad < MaxDeg+FreqMaxDeg
60+ papers about it’s conjectures
Bailey’s PSQL algorithm
New formula for :
i (1/16i)(4/(8i+1)-2/(8i+4)-1/(8i+5)-1/(8i+6))
 Easier to calculate nth hex digit of 

Theories in Pure Mathematics
Concepts

Examples and definitions
Statements

Conjectures and theorems
Explanations

Proofs, counterexamples
e.g., pure maths:group theory




Concepts: cyclic groups, Abelian groups
Conjecture: cyclic groups are Abelian
Examples provide empirical evidence
Simple proof for explanation
HR: Theory Formation Cycle
Start with background knowledge

1.
2.
3.
4.
5.
user-supplied axioms + concepts
Invent a new concept (machine learning)
Look for conjectures empirically (d-mining)
Prove the conjectures (theorem proving)
Disprove the conjectures (model generation)
Assess all concepts w.r.t. new concept
1. Invent a new concept

Build it from the most interesting old concepts
Inventing New Concepts
Ten General Production Rules (PR)


Work in all domains (math + non math)
Build new concept from one (or two) old ones
Example: Abelian groups




Given: [G,a,b,c] : a*b=c
Compose PR: [G,a,b,c] : a*b=c & b*a=c
Exists PR: [G,a,b] :  c (a*b=c & b*a=c)
Forall PR: [G] :  a b ( c (a*b=c & b*a=c))
Making Conjectures
Theory formation step

Attempt to invent a new concept
Concept has same examples as previous one

HR makes an equivalence conjecture
Concept has no examples

HR makes a non-existence conjecture
Examples of one concept are all examples of
another concept

HR makes an implication conjecture
Proving Theorems
HR relies on third party theorem provers
Equivalence conjectures:




Sets of implication conjectures
From which prime implicates are extracted
E.g.  a (a*a=a  a=id)
a*a=a  a=id,
a=id  a*a=a
HR uses the Otter theorem prover


William McCune et al.
Only uses this for finite algebras
Disproving Non-Theorems
Any conjectures which Otter can’t prove



HR looks for a counterexample
Using the MACE model generator
Also written by William McCune
Other possibilities:

Computer algebra, constraint satisfaction
Counterexamples are added to the theory

Fewer similar non-theorems are made later
Assessing Interestingness
New concepts from interesting old ones
Concepts measured in terms of:


Intrinsic values, e.g. complexity of definition
Relational values, e.g. novelty of categorisation
Concepts also assessed by conjectures

Quality, quantity of conjectures involving conc.
Conjectures also assessed


Difficulty of proof (proof length from Otter)
Surprisingness (of LHS and RHS definitions)
Bootstrapping ATF Cycle
Applications of HR
Puzzle generation

Next in sequence, odd one out
Automated theorem proving

Discovering useful lemmas
Constraint satisfaction problems

Discovering additional constraints
Machine learning tasks

Puzzle solving, prediction tasks
Studying machine creativity

Multi-agent, cross-domain, meta-level
Application to
Mathematical Discovery
Exploration of algebras using HR


Anti-associative algebras
Quasigroups
Number theory results


Encyclopedia of Integer Sequences
Using HR and NumbersWithNames
Refactorable numbers

Results and open conjectures
Problem solving (Zeitz numbers)
Anti-associative Algebras
(Novel domain to me)
all a,b,c a*(b*c)  (a*b)*c
Used HR with Otter and MACE (2 hours)
34 examples, sizes 2 to 6 (exists each size)
AAAs are not: abelian or quasigroups

Quasigroups must have associative triple
Have two elements on diagonal
Have no identity, or even local identity
Commutative pairs are not co-squares
Quasigroup Results
Part of CSP project
QG3 quasigroups: (a*b)*(b*a)=a
HR conjectured, Otter proved, We interpreted



Diagonal elements are all different
a*a=b  b*b=a
a*b=b  b*a=a
QG3 quasigroups are anti-Abelian


a*b = b*a  a=b
Corollary to one of HR’s results (with our help)
10x speed up over naïve model
Neil Sloane’s Encyclopedia
of Integer Sequences
Large database of sequences

E.g., Primes: 2, 3, 5, 7, 11, 13,…
Contains 67,000+ sequences (36 years)

A new sequence must be novel, infinite, interesting

HR has invented 20 new sequences



All supplied with interesting theorems (our proof)
Datamining the Encyclopedia itself
NumbersWithNames program (details ommitted)
Some Nice Results
Number of divisors, (n), is a prime


2, 3, 4, 5, 7, 9, 11, 13, …
m(n) is prime  (n) is prime
g(n) = #squares dividing n

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, …
numbers setting the record for g(n)


1, 4, 16, 36, 144, 576, …
Squares of the highly composite numbers
Perfect numbers are pernicious
Refactorable Numbers
Number of divisors is itself a divisor



1, 2, 8, 9, 12, 18, 24, 36, 40, …
HR’s first success [not in Encyclopedia]
Turned out to be a re-invention (1990)
Preliminary results (* - made by HR)





Infinitely many refactorables
Odd refactorables are perfect squares *
Congruent to 0, 1, 2 or 4 mod 8 *
Perfect numbers are not refactorable *
m,n relprim and refactorable  mn
refactorable
Refactorables – Deeper Results
Natural density is zero

Kennedy and Cooper 1990
Joshua Zelinsky (hot off the press)



T(n) < 0.5 B(n) with finitely many
counterexamples (max 1013)
T(n) = #refacs < n, B(n) = #primes < n
Assuming Goldbach’s strong conjecture
 Every integer is the sum of 5 or fewer refactorables
Zelinsky uses the results from HR
Refactorables – Questions…..
Numbers n!/3 are refactorable*
Numbers for which ((n))=n are refactorable*
(x) = #integers less than or equal to and coprime to x
There are infinitely many pairs of refactorables

(1,2), (8,9), (1520,1521), (50624,50625), …
There are no triples of refactorables


We know there are no quadruples
And no triples less than 1053
Demonstration – Zeitz numbers
Hungarian maths competition
Multiply four consecutive numbers


n(n+1)(n+2)(n+3)
Never a square number
Demonstration

Using NumbersWithNames
Future Work: HR Project
McCasland?

Use HR to explore Zariski spaces
Colton: Express HR as a ML program

Try domains other than maths (bioinformatics)
Walsh: Integrate HR


With every maths program ever written
In particular Maple computer algebra
Bundy:

Build an automated mathematician
Web Pages
HR:

www.dai.ed.ac.uk/~simonco/research/hr
NumbersWithNames program:

www.machine-creativity.com/programs/nwn
Encyclopedia of Integer Sequences:

www.research.att.com/~njas/sequences