4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Not exactly what you're looking for, but you may be interested in this preprint 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. $\endgroup$
    – Sam Hopkins
    Commented Jan 28, 2023 at 0:04
  • 1
    $\begingroup$ I guess it is actually this Nature paper that explains how the AI in question was devised/implemented which might be more relevant: doi.org/10.1038/s41586-021-04086-x $\endgroup$
    – Sam Hopkins
    Commented Jan 28, 2023 at 1:01
  • 1
    $\begingroup$ Check out Sequence Machine project: sequencedb.net/about.html $\endgroup$
    – Max Alekseyev
    Commented Jan 28, 2023 at 11:18
  • 1
    $\begingroup$ There is a related MO question about the Ramanujan machine. $\endgroup$
    – Timothy Chow
    Commented Jan 28, 2023 at 14:05
  • 3
    $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Commented Jan 28, 2023 at 14:12

4 Answers 4

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @: what you are after seems close to the the aims of "program synthesis" and "symbolic regression". Lar's talk here youtube.com/… provided an excellent introduction for me. Perhaps you might also find his talk useful. $\endgroup$
    – Geordie Williamson
    Commented Jan 29, 2023 at 6:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Commented Jan 29, 2023 at 14:28
  • $\begingroup$ "Inductive logic programming" is another term I've run across (for future people's benefit) $\endgroup$
    – Duncan W
    Commented Jan 30, 2023 at 2:29
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .