Automatically generating combinatorial conjectures

Question

It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. Problems of this sort are why the OEIS exists; however, it doesn't enumerate every arithmetical rule, not even all of those $\mathbb{N} \to \mathbb{N}$.

This seems like a problem that's eminently solvable algorithmically―but, before I went iterating through numberings of primitive-recursive functions, I wanted to ask if there's a canonical solution. Is the naïve Boolean satisfiability approach (one constraint for each data point) more sensible? Stuff I'm not thinking about?

For clarity, what I'm looking for is a way to search through the set of (computable) functions $\mathbb{N} \times \cdots \times \mathbb{N} \to \mathbb{N}$ for the simplest nontrivial algorithm consistent with a list of input-output pairs.

Not exactly what you're looking for, but you may be interested in this preprint https://arxiv.org/abs/2111.15161 where the authors try to guess a pattern for a very difficult combinatorial problem coming from representation theory using machine learning. — Sam Hopkins, Jan 28 '23 at 00:04
I guess it is actually this Nature paper that explains how the AI in question was devised/implemented which might be more relevant: https://doi.org/10.1038/s41586-021-04086-x — Sam Hopkins, Jan 28 '23 at 01:01
Check out Sequence Machine project: http://sequencedb.net/about.html — Max Alekseyev, Jan 28 '23 at 11:18
As stated, your question sounds like it's about Kolmogorov complexity, which is notoriously intractable from a computational point of view. But for some preliminary ideas about a general theory, see Harvey Friedman's comments about finite extrapolation and simplicity on the Foundations of Mathematics mailing list. — Timothy Chow, Jan 28 '23 at 14:12
There may be functions that have very simple descriptions in words, but only complicated algorithms to compute them. — Gerry Myerson, Jan 28 '23 at 22:53

Wlod AA · Answer 1 · 2023-01-28T14:27:52.380

Perhaps, the most significant (and first?!) example of such automatically generated combinatorial conjectures was Graffiti created by Siemion Fajtlowicz in 1982/3 or so. Later, he was joined by his student Ermelinda DeLaViña;

see:

Paul Erdos and other mathematicians enjoyed Graffiti.

score 4 · Answer 2 · answered Feb 03 '23 at 04:38

While this may not be exactly what you asked for, it seems close. Thibault Gauthier, Miroslav Olšák, and Josef Urban posted an arXiv preprint (apparently on the same day you posted your question here on MO!), Alien Coding, arXiv:2301.11479. Here is the abstract:

We introduce a self-learning algorithm for synthesizing programs for OEIS sequences. The algorithm starts from scratch initially generating programs at random. Then it runs many iterations of a self-learning loop that interleaves (i) training neural machine translation to learn the correspondence between sequences and the programs discovered so far, and (ii) proposing many new programs for each OEIS sequence by the trained neural machine translator. The algorithm discovers on its own programs for more than 78000 OEIS sequences, sometimes developing unusual programming methods. We analyze its behavior and the invented programs in several experiments.

score 3 · Answer 3 · answered Jan 29 '23 at 01:35

3

Looking into the SAT-solver idea, I noticed many modern solvers have systems for "syntax-guided synthesis:" given a grammar of acceptable primitives, search for a function implemented using those primitives that satisfies some logical specification.

Keep the mathematical ideas coming, but something of this nature with Racket's Rosette is probably what I'm going to pursue for now.

answered Jan 29 '23 at 01:35

Duncan W

341
3
8

1

@: what you are after seems close to the the aims of "program synthesis" and "symbolic regression". Lar's talk here https://www.youtube.com/watch?v=JCsmYvluNjs&ab_channel=SydneyMathematicalResearchInstitute-SMRI provided an excellent introduction for me. Perhaps you might also find his talk useful. – Geordie Williamson Jan 29 '23 at 06:51
1

Though it's not exactly what you asked for, you might also be interested in FindStat, which someone mentioned in response to a related MO question that I asked some time ago. – Timothy Chow Jan 29 '23 at 14:28
"Inductive logic programming" is another term I've run across (for future people's benefit) – Duncan W Jan 30 '23 at 02:29

score 2 · Answer 4 · answered Feb 24 '23 at 03:11

Not sure whether this is exactly what you are looking for or whether you may consider this solution kind of cheating, but you may be interested in the Berlekamp–Massey algorithm, that can be used to find a shortest linear recurrence that generates a given sequence.

Automatically generating combinatorial conjectures

4 Answers4