4
$\begingroup$

Regarding a question about proofs-of-work and following up on this answer and the comments therein, I believe we can, at least in theory, come close to having the hashing resources used in cryptocurrencies to show that two knots are in some sense far away from being able to be converted to one another, either because they are actually different knots, or because the knots need to be "complexified" a lot.

In more detail, given a random hash function, along with two random knots $K_1$ and $K_2$ represented as grid diagrams $G_1$ and $G_2$ both of dimension $\bar{D}$, miners could use a merkle root of financial transactions to generate a sequence of random grid moves to be applied to one of $G_1$ or $G_2$, generating another grid diagram $G_3$, all while keeping the dimension, say, $\le\bar{D}+k$ for some small $k$. They then hash $G_3$, and "win" if the hash begins with an appropriate number $d$ of $0$'s.

This may show that $K_1$ is more likely to be different from $K_2$, or at least far away from $K_2$ in some grid-move metric, because if $G_1$ and $G_2$ represent different knots then the space of all grid diagrams equivalent to $G_1$ or $G_2$ is large from an approximate counting perspective. If $G_1$ and $G_2$ can be easily converted to one another, however, then the space may be smaller, and it may become harder to hash on to a long string of $0$'s.

To play with grid diagrams and grid moves, see Marc Culler's gridlink application.

It's an easy combinatorial exercise to show that the number of grid diagrams of dimension $\bar{D}$ is $\bar{D}!\times[\frac{\bar{D}!}{e}]$. However, it's not clear how many different knots or links are encodable in grids of dimension $\le\tilde{D}$.

Do we have any hope of knowing enough about grid diagrams to know any estimates of the probability that two grid diagrams of dimension $\bar{D}$ represent different knots, or equivalent knots that cannot be converted to one another without increasing the grid dimension too much? How about if one of the knots is trivial?

I'm not sure if knowing the above is a necessary condition to knowing how large a string of $0$'s is required, that is, how big $d$ needs to be. Maybe one can at least theoretically use mining resources to say "the number of grid diagrams equivalent to either $K_1$ or $K_2$ without complexifiying by more than $k$ is at least $\ge 2^d$", or something similar, which may be somewhat nontrivial.

$\endgroup$
  • 1
    $\begingroup$ Cantarella, Chapman, and Mastin's Knot Probabilities in Random Diagrams arxiv suggest a power-law/Zipf's distribution for diagrams. With up to 10 crossings, a random knot diagram of the unknot $0_1$ is still dominate. I suspect a similar Zipf's-like behavior for grid diagrams. $\endgroup$ – Mark S Jul 6 '18 at 0:03
  • $\begingroup$ Proof of work is basically proof of carbon pollution. People should be discouraged from doing this sort of environmentally harmful activity, which has no benefit to the planet or the human race. $\endgroup$ – Ben Crowell Jul 6 '18 at 0:50

protected by Todd Trimble Jul 6 '18 at 11:52

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Browse other questions tagged or ask your own question.