22
$\begingroup$

Question: I wonder what are the open problems , where computational experiments might me helpful? (Setting some bounds, excluding some cases, shaping some expectations ).

Grant program: The context of the question is the following - in some sense there is a way to crowdsource some (quite specific, but still) computational experiments - the platform for data science challenges Kaggle (Google's subsidiary) - offers grants to researchers in various fields to organize the challenges. Properly organized it might attract thousands participants, some of whom are extremely skilled in solving computational challenges (like NVIDIA grandmaster's team - 6 super-skillful guys who are payed by NVIDIA just to participate in challenges (and promote some NVIDIA tools) - kind of profi-sportsmen). There already many research oriented challenges took place - mainly around in bioinformatics (e.g. CAFA5, Stanford-Ribonanza, Single Cell Perturbations, etc.. ).

Example: The one quite related to mathematics - is ongoing challenge on finite permutation groups - the task is to find as short paths as possible for sets of given points on Cayley graphs. The groups include N-dimensional Rubik's cube and other puzzle motivated groups like "Globe". For example even the diameters of the N-dimensional Rubik's cube are still unknown, so computational experiments may shed light on these questions. The other questions - like better understanding of the random walks, growth patterns, patterns of mixing, fast scrambling algorithms - seems to be of interest from both sides - machine learning and mathematical. So fruitful ideas exchange and interconnections might be possible. It would be great if some mathoverflow colleagues experienced in such kind of permutation group questions may share experience - please post on forum e.g. here or/and contact e.g. me.

PS

I am a kind of fan of many sides of Kaggle - it managed to create community of people who not only competing but sharing lots of experience. Gamified "reputation" scores - similar to mathoverflow - play a role, moreover Kaggle rankings are appreciated in data science world, so can help to find a better job - another stimulus for many to participate, in addition to networking. Many people think that the best way to learn practical data science - participate in Kaggle challenges. It is not only for competition, but a free cloud service - like Google Colab, but more devoted to team work - offering free computing power, storage, sharing, version control, team work. Would be great to have something similar for mathematical community or to use Kaggle itself for mathematical community - one may think of a competition as a kind of mini-"Polymath" project. Where all the infrastructure - is ready - forum, community, free computing power - the only thing one needs - is to create a challenge. Kaggle offers everybody to create a challenge for free, but only "official" challenges attract most attention.

$\endgroup$
5

4 Answers 4

7
$\begingroup$

I have mentioned before the possibility of automated search for bijective proofs. At the time I asked the question, I was imagining a general tool that researchers could apply to any problem of interest. For your question, however, it is probably more appropriate to pick a specific challenge problem. One possibility is searching for a bijection between Gog and Magog trapezoids. Finding such a bijection would likely shed some light on some of the most amazing identities in all of enumerative combinatorics, namely those concerning alternating sign matrices and plane partitions with various symmetry properties.

If Gog and Magog triangles don't catch your fancy, you can find many other candidates in Richard Stanley's list or Section 3.6 of Igor Pak's survey.

There are different sorts of computational experiments one might try. One could try to strengthen the conjecture, by identifying "features" of the objects in question, and showing that (for example) not only do Type I and Type II objects appear to be equinumerous, but the number of objects of Type I and size $n$ with $k$ features appears to be equal to the number of objects of Type II and size $n$ with $k$ features. Or one could explore different types of transformations of the objects into other types of objects that appear to be more "similar" to each other. A lot of what human combinatorialists do when trying to find bijections is to explore various possibilities experimentally and look for patterns, and this is the sort of thing that AI is getting increasingly better at.

$\endgroup$
6
$\begingroup$

Maybe this can be considered a minor open problem, but you can try to take a look at this Question.
Furthermore, in Section 4 of this preprint of mine Preprint with the general conjecture, I added my thoughts about a rough algorithm to search for the solution of the fundamental case $(n=4, k=3)$... I think that it would not be out of reach to improve at least the upper bound from $23$ to $22$. Who knows?

A few years ago, I proposed a similar challenge based on a set of open problems of the same kind... I made everything by hand, but I think that it could be very interesting to recycle as a team game by allowing the use of any software (since at the time nobody was able to improve my answers).
Here it is Dots Rev (Challenge). Have fun!

$\endgroup$
6
$\begingroup$

DeepMind recently announced that their FunSearch methodology was successful at advancing the state of the art of the cap set problem and the online bin packing problem. Under the hood, the code used LLMs to help search for short snippets of computer code that accomplished a well-defined task in unexpected ways.

The general task of searching for powerful but unexpected short snippets of code seems like a good candidate for your project. For example, I'm reminded of the fast inverse square root implementation from Quake III Arena and Alman and Rao's $\frac{23}{24} N\log N$ Walsh–Hadamard transform. Could one rediscover—or even improve—these algorithms via computational search? Another arena might be quantum algorithms; despite decades of research, only a handful of ("useful") problems are known to have a significantly superior quantum algorithm. Perhaps a guided computational search might uncover new quantum algorithms.

$\endgroup$
5
$\begingroup$

This answer is similar in style to Marco Ripa's concerning a specific preprint. In this preprint by me and Tim McCormack, Weighted Versions of the Arithmetic-Mean-Geometric Mean Inequality and Zaremba's Function, one thing we looked at was strongly pseudoperfect numbers. These are numbers $n$ with a subset of its divisors $S$ such that the sum of all elements in $S$ is $2n$, and also where $d \in S$ if and only if $n/d \in S$. Strongly pseudoperfect numbers form an intermediate family between pseudoperfect numbers (where there are a lot, almost too many to say a lot interesting things about), and perfect numbers which are very restrictive. The vast majority of strongly pseudoperfect numbers turn out to even, and we have only a handful of odd examples, and we don't know if there are infinitely many or not. But the existence of odd ones is nice at two levels. First, it gives us some guidance to prove things about odd perfect numbers, because they behave similarly to how those should behave (but are actual examples). Second, if we prove things about these, we know we're at least proving about numbers that actually exist. Third, they also provide us an obstruction to proving things about odd perfect numbers, in that since strongly pseudoperfect numbers exist, anything one has proven that is true for them cannot by itself answer whether any odd perfect numbers exist. In this context, these numbers are very closely related to the similar idea of "spoof perfect numbers" which are essentially numbers which are perfect if we pretend some numbers are primes.

So, a substantial computation finding all the odd examples under some big bound would be helpful for understanding these better.

$\endgroup$

You must log in to answer this question.

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