Infected cubes puzzle in 3D with threshold 4

Question

(This question was previously posted on Math SE, but received no answers.)

3D infected cubes puzzle with threshold $4$:
On an $n\times n\times n$ cube, some cells are infected; if a cell shares a face with $4$ infected cells, it becomes infected. What's the minimum number of initially infected cells required to infect the whole cube?

The two-dimensional, threshold $2$ version is a classic. The solution to that puzzle (often simply called the "infected squares puzzle") is $n$.

The two-dimensional, threshold $3$ version is more interesting. When $n$ is of the form $2^k-1$, the solution is $\frac{4^k-1}3=\frac13n^2+\frac23n$ with an interesting recursive pattern. When $n$ is not of that form, I believe that the solution is $\lceil\frac13n^2+\frac23n+\frac13\rceil$ for odd $n$ and $\lceil\frac13n^2+\frac23n+\frac43\rceil$ for even $n$. (I don't have a proof but I think someone else does.) In summary: $\frac13n^2+\frac23n+O(1)$.

Up a dimension, the three-dimensional, threshold $3$ version is simple again. The answer is $n^2$. In fact, the $d$-dimensional, threshold $d$ version is solved for all $d$: see here.

The logical next step, then, is the three-dimensional, threshold $4$ version. After some thinking, I have some conjectural upper bounds:

$n=1$ is $1$, trivially.
$n=2$ is $8$. (In fact, for all $n\ge2$, the $8$ vertices must start infected, as they only have three neighbors.)
$n=3$ should be $14$ (corner cells and face cells).
$n=4$ should be $33$.
$n=5$ should be $53$ (on Math SE I originally wrote $52$ but I don't think that works actually).

What more progress can be made? Are the solutions I found for $n\le5$ minimal? Is there a formula (even an asymptotic one) for general $n$?

For what it's worth, I can manage a lower bound of $\frac14n^3+\frac34n^2$. However, given the data above, this doesn't seem to be an especially close bound.

A helpful observation: Consider the $(n+1)^3$ points that are vertices of a cell. I believe that this set ("the grid points") must be connected through the infected cells: that is, the set of these grid points union the set of infected cells must be a connected set. (This observation is true of the two-dimensional, threshold 3 version as well. However, in that case, it was both a necessary and sufficient condition; in our case, this is still necessary but no longer sufficient.)

Answer 1

Small steps by analogy

In the 2D case, given a solution to an NxN board, we can find a solution to (2N+1)x(2N+1) by duplicating the original solution 4 times and filling in the center.

Showing how it works in 2D

This works in 2D, and if we examine it, we can see how it might work in 3D.

The size 2N+1 2D board breaks down into 9 pieces.

• 4 copies of the smaller (size NxN) board
• 4 Nx1 strips
• 1 1x1 center piece

The copies of the original board fill by inductive hypothesis. The cells in the strips are each adjacent to two cells in filled copies - therefore if the center is filled, then the strips will fill from their inside ends (which are adjacent to one filled center cell and 2 filled copy cells), filling the entire square.

Breaking down the 3D case

If we take a NxNxN 3D cube and try the same duplication trick, we get a lot more pieces.

• 8 copies of the original cube
• 12 NxNx1 interface boards between two copies of the original cube
• 6 Nx1x1 pillars between interface boards
• 1 1x1x1 center piece

Let's consider what happens if all of the new created pieces are empty, and what we might have to fill to infect the entire cube.

• The 8 copy-cubes fill by inductive hypothesis
• Everything on the interface board is adjacent to 2 filled cells (from the neighboring two copy-cubes). Some cells are also adjacent to 1 or 2 pillar cells.
• Everything on the pillars is adjacent to 4 cells in interface boards, so if the interface boards fill then the pillars fill
• The center is adjacent to 6 pillars, so if the pillars fill then the center fills.

Upper Bound

I can construct a solution which fill the entire cube, but I do not know if it is optimal: Fill all of the pillars (cost is 6N)

• The 8 copies fill by inductive hypothesis
• The pillars are filled because we filled them.
• The center fills because it is adjacent to 6 filled pillars.
• The interface boards fill out from their pillar-adjacent corners. (Because they're a 2D grid sandwiched between two filled cubes, this is equivalent to an infected grid that requires only 2 neighboring cells to be infected. Because each interface board is adjacent to two pillars, we start with full sides of the board infected.)

Thus, we can get a recursive upper bound.

Given a solution to the infected cube of size N with K initial cells, we can construct a solution for the infected cube of size (2N+1) using 8K + 6N initial cells.

Running the numbers in Excel, it appears that this asymptotically approaches 26.7857143% of the cube needing to be filled, which isn't far off from the theoretical lower bound of O(n^3)/4.

Other Ideas

While writing this answer, it occurred to me that it might be possible to construct a solution out of this breakdown which does not rely on induction. If the interface boards began completely filled (or filled with a checkerboard pattern), there might be a pattern that can be placed in the "cube" components which fills from the interface boards, instead of having the interface boards fill from the cubes. However, I have not found such a pattern.

Answer 2

This answer ends with a disproof of its own conjecture. I think there might be other interesting points related to this line of reasoning, but as-is, this does not advance the theory of the problem.

Extending the connected corners conjecture

From the question, the following quote caught my eye:

A helpful observation: Consider the $(n+1)^3$ points that are vertices of a cell. I believe that this set ("the grid points") must be connected through the infected cells: that is, the set of these grid points union the set of infected cells must be a connected set. (This observation is true of the two-dimensional, threshold 3 version as well. However, in that case, it was both a necessary and sufficient condition; in our case, this is still necessary but no longer sufficient.)

I believe I can explain why this is, and I will use the same strategy as my other answer to demonstrate it - and then extend it into an interesting property we can use to improve our understanding of the 3D case.

Understanding the 2D case

Proving necessity is easy: if a new cell becomes infected through its neighbors, neither the number nor connectedness of infected corners changes. All of the corners were already infected, and they were already connected through infected cells (because the 4 neighbors form a cycle, and removing one of them leaves them connected in a string).

I haven't fully understood what leads to sufficiency, and I will leave the full proof to smarter minds than I (but if anyone has a reference, I'd love to read it).

When we project into 3 dimensions, things change

There are several significant changes when we move from squares to cubes.

• Corners (points) become Edges (pairs of points)
• Each cell has 6 potential neighbors instead of 4
• The number of edges (12) and the number of neighbors (6) no longer match. Each neighbor now connects 4 edges instead of 2 corners.

Extending into 3D, Threshold 5

The easiest analogous property, then, is that in the 3D threshold 5 case, connecting every edge through connected cells is ~~both sufficient and~~ necessary to infect the entire cube. (Thanks Akiva Weinberger for pointing out that the sufficiency claim was incorrect)

I believe it's easy to see the analogy to the 2D3T case. A cell being infected by its neighbors still does not change the connectedness-via-infected-cells property. Since the fully infected cube has all edges infected, this is enough to prove necessity (but not sufficiency).

Note that this is not true of in the 3D threshold 4 case: A cell can be infected by its neighbors can change the connectedness property of edges, because it is possible for a cell to have 4 infected neighbors and still have 1 edge that is not connected to any infected cell.

It is precisely this property (the reason why it doesn't work) which we can use to learn something new about the 3DT4 case.

Extending into 3D, Threshold 4

Infecting a new cell can add at most one edge to the net of edges connected through infected cells. From this, we can prove the following property: The number of edges which do not connect to any infected cells must not exceed the number of uninfected cells.

Making it useful

If that is merely necessary, then this is not very useful. I believe, but have not proven, that this new property is not only necessary, but sufficient: that is to say, if the number of uninfected edges is less than or equal to the number of uninfected cells, then the entire cube will become infected.

(Edit) Proof of Insufficiency

The property: "The number of edges which do not connect to any infected cells must not exceed the number of uninfected cells" is not sufficient.

Counterexample: A 4x4 cube with all outer cells infected and a 2x2 uninfected cavity has 8 uninfected cells but 6 uninfected edges. The number of uninfected edges is less than the number of uninfected cells, but the cube will not be infected.