What problem would you base your mathcoin on?

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.