The last line is very humorous "Jäkel said he would have written up his thesis two years ago if not for the distraction of d(9). “I think I need a break,” he said."
If there are any mathematicians in the comments I'd love some layman's insight into why solving this problem is not itself worthy of a doctoral thesis in Maths.
The dissertation is the core of your doctoral degree and the most important piece of work you will produce for this degree. It is usually written as a monograph which is a comprehensive, self-contained treatment of a research topic.
[…]
Alongside the monographic dissertation, more and more faculties are offering the possibility of submitting a publication-based dissertation, known as a cumulative dissertation. This consists of several shorter pieces of work which are thematically linked.
The totality of the written doctoral works must satisfy the requirements of a monographic dissertation. Faculties which allow cumulative dissertations may have very different requirements, for example in relation to:
• The type of publication (book, journals, manuscript)
• The current status of the publications (published, submitted, in preparation)
• The scope of the publications and the results they contain, etc.
If you wish to write a cumulative dissertation, you should find out at an early stage whether this option is available at your faculty and if so, what requirements apply.
Even if his university allows such a bundling of papers chances are he still would have to write the texts that describe how they’re linked thematically, and possibly a layman’s description of the work, etc.
The phrase “written up” here means that he had already done the core part of his thesis work two years ago, even before starting on this problem: he had already proved enough results, possibly major parts of which had already even been published as papers, and it only remained to put them together in the coherent form of a thesis, schedule a thesis defence, etc. But this writing work was interrupted by the challenge of computing d(9), and he's describing starting/resuming the work of “just writing” as a break, from the harder work he has been doing on d(9).
He might have meant that there were lower-hanging fruits with which he could have written his theses much earlier and he got distracted by a more complex challenge.
It might have involved little novel work, "just" a lot of high quality programming, and access to a decent amount of CPU power. That is a problem I've seen with some similar results, can't comment how much was novel here in detail of course.
Not mathematician, but often one plans for their thesis one or two years before they think of graduation, and at that point thesis topic is kind of "fixed" so you need to execute ~70% of it. Anything risky you don't plan into the thesis
I appreciate the insert explaining monotone functions, and the coloring connects it back to the cube example.
However, they don't say which exact function was used to color the outputs in the example, so it doesn't really give you a picture of what these sorts of monotone functions look like.
Can someone reverse engineer a possible function for that example?
The colouring is the function: the 16 nodes 0000…1111 are the inputs, and their colours (blue for False and white for True) are the respective outputs. So you can read the function off the picture: it's the function that maps 0000 to False, 0110 to True, etc. (And as @teraflop replied, this is the majority function on the last three bits of the input.)
God I love weird mathematical constructs like this. There's something very arcane about the idea that on a notebook or blackboard you can concisely articulate universal mysteries of reality.
TLDR it's 286,386,577,668,298,411,128,469,151,667,598,498,812,366 — there, saved you a click.
[The above is a parody of a kind of HN comment common on long articles (that wants an article to simply "answer" the headline), but this case—the numerical answer being not at all illuminating in comparison to actually reading the article—is also a clear illustration of this point from the Fields medalist William Thurston's very insightful "On Proof and Progress in Mathematics" (https://arxiv.org/abs/math/9404236):
> They might print out a table of the first 10,000 primes, only to find that their printout isn’t something they really wanted after all. They discover by this kind of experience that what they really want is usually not some collection of “answers”—what they want is understanding.
This is because knowledge is related to its application. It never stands for itself. The reason why we research something is because it helps us to solve a problem or do something, and thus the context is important.
I quite like the definition of understanding as knowing what is possible and what is not.
All monotone functions can be represented as a tree of threshold gates (or, more extreme, as a tree of and & or gates-- themselves just the extreme cases for thresholds). But this doesn't result in useful way of counting the monotone functions due to duplicates.
A great many monotone functions have a very natural representation as a threshold gate or a simple composition of threshold gates-- like a majority of three majorities. But I wonder what monotone functions are the least threshold-like. Unfortunately I don't know of a useful way to ask the question because at the extreme they can all be constructed from threshold gates, so it's not useful e.g. to ask for monotone functions that can't be constructed from them.
A related question might be what are the N monotone functions that can be combined to most efficiently represent all monotone functions up to size M? Does the selection of these best basis functions change for different sizes? (or fall into a finite set of groups like odd and even M?).
What about a monotonix function that has the keast duplicates when shown as a tree of thresholds? Or one that has the deepest tree? Or the least balanced tree? Those feel likely to have an alternative definition that is more elegant.
This discussion is about monotone Boolean functions. That is, functions from {0,1}^N → N, such that "flipping" any input from 0 to 1 never causes the output to go from 1 to 0.
I can't think of any way to to write a prime-counting function as an interesting monotone Boolean function. If you represent the numbers in binary, it's not monotone. If you write them in unary, with a separate function for each bit, then each bit's function (taken by itself) is just a near-trivial threshold function.
No worries, I got that. Boolean came before programming for me by way of electronics. Which is what I thought was interesting about this article, to imagine the algorithm but as discrete logic.
The interpretation with the cube on the corner seems pretty intuitive - the cube essentially becomes a stack of layers. For every coloring of the cube there is one layer where the transition from white to blue happens, all layers below are completely white, all layers above are completely blue. A layer with n vertices can be colored in 2^n ways.
So we just have to start in the bottom layer of an all blue cube, go through all colorings of the current layer until we get to all white, then move one layer up and repeat until we reach the top layer. When we move to the next layer up, we have to color at least one vertex white or else the coloring would not change, so there are only 2^n - 1 relevant colorings in each layer. In the end we also have to add one for the all blue cube.
1, 1-1, 1-2-1, 1-3-3-1 are the layers in dimensions zero to three. The number of relevant colorings per layer are 1, 1-1, 1-3-1, 1-7-7-1, their sum plus one are 2, 3, 6, 17. So this worked for dimensions zero to two but gives the wrong answer for three which should be 20, not 17 according to the article. Where did I make the mistake? Was the visualization with the cube oversimplifying the problem?
For dimensions four I would guess the layer structure 1-4-6-4-1 which yields 96 which also does not match 168.
"Below" in this context means "directly below and connected by a line" (the lines are the edges of the cube). So you can have a blue vertex that is vertically below a white vertex, so long as they are not connected by an edge. The first time this can happen is for a 3 dimensional cube. You can have blue at the top, then 2 blue and 1 white below that, and then 1 blue (under and between the 2 blues in the layer above) and 2 white in the layer below that, and then white for the bottom vertex. This configuration can be rotated 3 ways and this takes us from 17 to 20.
There needn't be a layer such that all layers below are completely white and all layers above are completely blue.
For example, consider a cube. It has four layers. We could say the bottom-most layer is the one with (0, 0, 0).
Above that, there's a layer which contains (0, 0, 1), (0, 1, 0), and (1, 0, 0) [the entries with a single 1].
Above that, there's a layer which contains (1, 1, 0), (1, 0, 1), and (0, 1, 1) [the entries with two 1s].
Above that, there's a layer which contains (1, 1, 1).
We could make (0, 0, 0), (0, 0, 1), (0, 1, 0) and (0, 1, 1) white, while making (1, 0, 0), (1, 1, 0), (1, 0, 1), and (1, 1, 1) blue.
Note that all the blue values will have a 1 in the first position, while all the white values will have a 0 in the first position, ensuring monotonicity.
But both the "single 1" and the "double 1" layers have a mix of blue and white within them. So there's no single transition layer, as you put it.
You are right, I also just figured that out. They did not simply mean above in the sense of higher above the table but taking into account the edge structure, should have though about it in terms of monotone functions.
Yeah I've always found these examples are kind of a Sorting Hat for math students. I find the monotone functions definition much more intuitively graspable but a lot of people find the N-cube definition or the subset definition much more amenable.
the layers of the cube are just the number of elements in the set, for the cube on 4 elements 1,2,3,4, we have the coloring where every set containing 1 is blue. certainly there is a blue one element set {1} so by your intuition, every three element set must be blue, but {2,3,4} does not contain 1, so it is white.
I'm not the sharpest math person here, and I can not prove this...but...after spending a few hours looking at this, I call BS. There are no such things as Dedekind numbers. This is an April Fools Day joke that got out of hand.
If there are any mathematicians in the comments I'd love some layman's insight into why solving this problem is not itself worthy of a doctoral thesis in Maths.