35
$\begingroup$

Recently, a variant of electronic currency, based on prime sextuplets, broke the record in generating the largest known set of six primes, packed as closely as possible, that is, a sextuple $(p,p+4,p+6,p+10,p+12,p+16)$ such that all numbers are prime.

I am not certain how significant this is to the mathematical community, but there are always a need for more data, which can be used to formulate conjectures.

So, if the mathematical community had access to a large amount of computer power, what would be worthwhile compute, and why? Ignoring details about how to make the computation run in parallel and all that.

Personally, I would like to see the Ehrhart series for the Birkhoff polytopes, these are only known up to $n=10$.

Another series that would be nice to know some more entries of are the number of 1324-avoiding permutations in $S_n$ for larger $n$, (record from 2013 2014 is for $n=36$). This is the smallest instance of enumerating pattern avoiding permutations where no formula is known.

Finding more Mersenne primes is also quite interesting. I wonder if I will see the 100th Mersenne prime in my lifetime.

$\endgroup$
11
  • 8
    $\begingroup$ I suggest reading Atkin's 1968 paper "On Feasible Computation" chilton-computing.org.uk/acl/applications/number/p003.htm "Each new generation of machines makes feasible a whole new range of computations; provided mathematicians pursue these rather than merely break old records for old sports, computation will have a significant part to play in the development of mathematics." "In every attempt to discover the infinite by inspecting the finite, we have to decide when to stop computing and start thinking; this is a decision where the computer cannot replace the mathematician." $\endgroup$ Nov 27, 2014 at 22:37
  • 8
    $\begingroup$ Could you please ask something less personal than "what would you compute?" For example "which computation could be worthwhile to be performed, and why" or something like that. This is I think the spirit of the question. But as is somebody looking for fun could answer whatever. And do not say it will not happen. mathoverflow.net/a/31300 mathoverflow.net/a/54306 $\endgroup$
    – user9072
    Nov 27, 2014 at 23:18
  • 9
    $\begingroup$ Finite projective planes of orders 12 and up. Of course, that is my personal taste, but it is a clear finite problem that shows how ridiculously helpless our computers currently are when it comes to serious mathematical questions about small integers. $\endgroup$
    – fedja
    Nov 27, 2014 at 23:25
  • 3
    $\begingroup$ Perhaps the question could be rephrased: what computation for which we already have a decent algorithm would you like to see run on some massive computer? This would make it more clear that you are not asking for what new computational horizons might become feasible from hardware advances, but rather which old computations are worth extending. Eg, at his retirement ("40 years on") talk, Birch said in 1960 they could barely think of computing with elliptic curves, whilst he fully expected people to routinely compute with motives by 2040. EC computations are still of interest, of course. $\endgroup$ Nov 28, 2014 at 0:24
  • 6
    $\begingroup$ Personally, I would rather see computing power itself treated as a currency. "Hey, I have this computation to make, can you make it? It'll cost 1$ per Tera-operation." Current cryptocurrencies are the computational equivalent of a one-trick pony; there is one single operation to perform, and hardware specialization is encouraged, rather than the use of general-purpose massively parallel computing machines. $\endgroup$ Nov 28, 2014 at 10:45

7 Answers 7

33
$\begingroup$

I'd choose $R(5,5)$ and other unknown Ramsey numbers, since

"Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of $R(5, 5)$ or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for $R(6, 6)$. In that case, he believes, we should attempt to destroy the aliens." Joel Spencer

$\endgroup$
0
11
$\begingroup$

In Conways game of life, there is a the concept of an orphan pattern.

Basically, an orphan is a finite pattern such that each configuration containing that pattern is a Garden of Eden (a pattern that cannot have a predecessor).

The smallest such pattern has not been found yet. A computer search 2011, restricted to symmetric orphans gave a pattern that fits in a 10x11 rectangle.

Thus, the smallest orphan will fit in a 10x11 rectangle, but it is probably smaller. Note that there are roughly $2^{10 \times 11}$ possible configurations that fit within these bounds.

$\endgroup$
10
$\begingroup$

Maybe finding good error-correcting codes. For instance, given $q, n, M$, search for a set of $M$ strings, each of length $n$ from a $q$-sized alphabet, with largest $d$, where $d =$ minimum pairwise Hamming distance.

My understanding is that it would be useful to know these optimal parameters in order to guide theory (can an expert comment?), and that it seems hard to do better than random guessing except in very special cases.

$\endgroup$
10
$\begingroup$

Homotopy groups of spheres. We know far too little about them!

It can be made computationally feasible by choosing finite simplicial complexes and allowing subdivision. Maps of simplicial complexes are just list correspondences, and homotopic maps can be detected by certain "moves" of such correspondences.

Call it HomotopyCoin or something.

$\endgroup$
1
  • $\begingroup$ How are you proposing to find non-trivial classes this way? $\endgroup$
    – HJRW
    Jan 6, 2018 at 12:02
9
$\begingroup$

Apologies if this answer is nitpicky and diverges slightly from the questions intent, but this particular soft question appears to warrant a soft answer.

Implicit in your term "mathcoin" are assumptions that the problem:

  1. Allows new solutions to be found in regular tunable time intervals,
  2. Is memory hard so that specialized ASICs cannot speed up the computations, and
  3. Any significantly faster algorithms represent the sort of dramatic advancement that it'd emerge from across the mathematical community simultaneously and not from a secret project.

Of course, collisions in cryptographic hashed satisfies 1 and 3, while a memory hard cryptographic hash like scrypt or argon2 satisfies 2 as well.

Almost all the answers proposed here thus far fail even 1 and maybe all here fail 2. Worse, there are probably no calculations that both pass 3 and represent useful mathematical (resp. scientific) research, at least not for 2 (resp. 10) years.

In short, a naive "mathcoin" as suggested here sounds impossible to do correctly. There might be less naive approaches where perhaps any problem goes and the problem's difficulty is established by previous attempts, but that's actually solving a social problem to achieve 1 with widely varied math problems as simply a source of randomness that defeats ASICs.

As an aside, there are proof-of-useful-work systems that could possibly support a bitcoin like currency without wasting resources, but again they all provide useful social services like file storage (filecoin) or anonymity via onion routing.

Update 2018: There is still no evidence of any suitable mathcoin problem but there are seemingly suitable science and engineering problems. Examples:

Proof-of-moon: All miners must buy telescope arrays to explore the night sky looking for specific astronomical events. If you find one, then reporting it in a canonical way and hashing the report with a nonce can win a block, with the difficulty possibly adjusted by the event.

Proof-of-vulnerability: All miners run advanced static analysis tools on software to discover vulnerabilities in published software. A miner wins the block with the hash specific characteristics of a vulnerability plus a nonce, so once a vulnerability is found the miner will eventually win a block. There are several challenges though: First, you must prevent a vulnerability from being used twice, potentially this could be done by resolving to a particular point in the code, but then projects with more releases become better targets. Second, static analysis tools have false positives, so you might need to test consequences somehow. Third, you'll likely need some sort of proof-of-stake system to permit humans to ultimately arbitrate the vulnerabilities. Forth, you want to tackle closed source software too, so the definition of published becomes tricky. Fifth, developers might get annoyed with vulnerabilities being posted to some blockchain without even attempting to warn them first.

$\endgroup$
2
  • 1
    $\begingroup$ The mathcoin is just to illustrate vast computational power - the question is in italics in the middle of the post: "So, if the mathematical community had access to a large amount of computer power, what would be worthwhile compute, and why?" with the implied specification that it is a community computation, rather than a single super-computer.... $\endgroup$ Feb 15, 2016 at 3:52
  • $\begingroup$ Mathcoin mining problems also need to be easy to solve but difficult to verify. $\endgroup$ May 14, 2017 at 18:40
6
$\begingroup$

I would like to like to run Siemion Fajtlowicz's program Graffiti, or variants of it, to discover new conjectures, and accumulate more empirical evidence for its existing conjectures.

$\endgroup$
2
4
$\begingroup$

A semi-magic square is a square matrix with integer entries and all row and column sums equal. Every semi-magic square can be expressed as a linear combination, with integer coefficients, of permutation matrices. Indeed, every $n\times n$ semi-magic square needs no more than $n^2-2n+2$ permutation matrices. Moreover, there is a precise sense in which almost every $n\times n$ semi-magic square needs $n^2-2n+2$ permutation matrices; despite this, it is not easy to find examples, with $n\ge4$, of "small" $n\times n$ semi-magic squares that need $n^2-2n+2$ permutation matrices.

So, my question is, find the "smallest" $4\times4$ semi-magic square that can't be expressed as an integer linear combination of 9 or fewer permutation matrices. "Smallest" could be interpreted as minimizing the absolute value of the largest entry in the matrix, or minimizing the $\ell_1$-norm of the matrix.

If it makes life easier, restrict to the case where the matrix entries are nonnegative. The coefficients in the linear combination must in all cases be allowed to be negative.

$\endgroup$
5
  • 1
    $\begingroup$ That is cool! This is also connected to the Birkhoff polytope in some sense. I guess the coefficients can be rational, and not only integer? $\endgroup$ Nov 28, 2014 at 7:00
  • $\begingroup$ Yes, one can ask the same question allowing rational coefficients. Another computational task is to find a semi-magic square that requires more permutation matrices when you restrict to integer coefficients than when you allow rational ones. It can't happen for $n\le3$; I don't think it can happen for $n=4$; I think it does happen for $n\ge5$. $\endgroup$ Nov 28, 2014 at 8:07
  • $\begingroup$ Ah. But since the Birkhoff polytope is compressed, every integer semi-magic square can be written as a sum of permutation matrices (coefficient 1). However, it doesn't tell how many different matrices which are needed; I wonder if the bound is worse if the coefficients are always non-negative integers. Your comment tells that the bound gets worse when $n\geq 5$. $\endgroup$ Nov 28, 2014 at 8:28
  • $\begingroup$ I'm not sure I understand. If the entries are nonnegative integers, then the bound on the worst-case number of permutation matrices is $n^2-2n+2$, no matter whether the coefficients are rational or integral, positive or general. On the other hand, there are examples, even for $n=3$, where you need fewer permutation matrices if you allow all integer coefficients than if you restrict to positive integer coefficients. What happens at 5 --- I think --- is that there are examples where you need fewer permutations if you allow rational coefficients than if you insist on integers. $\endgroup$ Nov 28, 2014 at 8:34
  • $\begingroup$ yes, that was what i meant; rational numbers sometimes allow fewer matrices in the representation. $\endgroup$ Nov 28, 2014 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.