Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to place numbers $1$ to $n^3$ in the unit cubes so that the numbers in any two adjacent  unit cubes  are co-prime? (Two unit cubes are called adjacent if they have a  common face). What about the two dimensional version of this problem in an $n\times n$ square ?
 A: Here is a proof that for any fixed dimension $d$, there is a computable $n_0(d)$ such that for all $n\ge n_0(d)$ we can place the numbers $1, ..., n^d$ in a $d$-dimensional cube of side length $n$ such that any two adjacent numbers are coprime.
The main idea is to use the following lemma:
Lemma 1. If $G = (V,E)$ is a graph with maximum degree $2d$, then for any partition of the vertex set $V$ into parts $V_1, ..., V_m$ such that for each $i$ we have $|V_i| \ge 4ed$, where $e$ is the base of the natural logarithm, we can pick one vertex $v_i$ from each $V_i$ such that for $i\ne j$ vertices $v_i$ and $v_j$ are not adjacent in $G$.
Proof. This is a direct consequence of the Lovász Local Lemma. First assume WLOG that each $V_i$ contains exactly $\lceil 4ed\rceil$ elements. Suppose we randomly select one vertex $v_i$ from each set $V_i$, and for each edge $e_j = (a,b) \in E$ let $A_j$ be the event that both $a,b$ were selected. The probability of $A_j$ occurring is at most $\frac{1}{\lceil 4ed\rceil^2}$, and each event $A_j$ is dependent on at most $2(2d\lceil 4ed\rceil-1)$ other events $A_k$, so in order to apply the Local Lemma we just need to check that $e\cdot \frac{1}{\lceil 4ed\rceil^2}\cdot 2(2d\lceil 4ed\rceil-1) \le 1$, which is obvious. Thus there is a positive probability that none of the events $A_j$ occur.
Next we make a few natural definitions. From here on we set $N = n^d$.
Definition. Let $p_1, ..., p_i$ be the first $i$ prime numbers. We say that a number $v$ has $i$-type $m$ if $\text{gcd}(v,\prod_{j\le i}p_j) = m$. We'll write $\#_N^i(m)$ for the number of numbers $v$ between $1$ and $N$ with $i$-type $m$.
Definition. An $i$-type coloring of the graph $G = (V,E)$ with $|V| = N$ is an assignment of a number $m(v)$ dividing $\prod_{j\le i}p_j$ to each vertex $v$, such that for any adjacent vertices $v,w$ we have $\text{gcd}(m(v),m(w)) = 1$, and for any $m \ne 1$ the number of vertices $v$ with $m(v) = m$ is at least $\#_N^i(m)$.
The idea is to inductively convert an $(i-1)$-type coloring to an $i$-type coloring for sufficiently large $i$ using Lemma 1. To that end, we need the following lemma.
Lemma 2. There is a computable index $i_0$, depending only on $d$, such that for any $i\ge i_0$ and any $N,m$, we have $\#_N^i(mp_i) \le \max(1, \frac{1}{\lceil 4ed\rceil}\#_N^{i-1}(m))$.
Proof. If $\#_N^i(mp_i) \ge 2$, then $N/m \ge 2p_i$. If $2p_i \le N/m < p_i^3$ then we use Chebyshev's weak form of the prime number theorem to see that
$\#_N^{i-1}(m) \ge \pi(N/m) - \pi(p_i) \ge \frac{1}{\log(p_i)}\frac{N}{m}\left(\frac{7}{8}\frac{\log(p_i)}{\log(N/m)}-\frac{9}{8}\frac{p_i}{N/m}\right) \ge \frac{1}{4\log(p_i)}\frac{N}{m},$
while we trivially have $\#_N^i(mp_i) \le \frac{1}{p_i}\frac{N}{m}$. Thus if $N/m < p_i^3$ and $p_i \ge 4\lceil 4ed\rceil\log(p_i)$ then we are done.
If $N/m \ge p_i^3$, then we can, to within a constant factor, estimate the sizes of $\#_N^{i-1}(m)$ and $\#_N^i(mp_i)$ using the fundamental lemma of sieve theory, and for $i_0$ sufficiently large the first will be larger than the second by more than a factor of $\lceil 4ed\rceil$. I'll leave the details to the reader...
Now the inductive step doesn't quite work because of the existence of certain "bad pairs" $(m,p_i)$.
Definition. We call the pair $(m,p_i)$ bad if $\#_N^{i-1}(m) < \lceil 4ed\rceil$ and $\#_N^i(mp_i) = 1$ and $i \ge i_0$ and $p_i < N/2$.
We will fix this problem by taking primes between $N/2$ and $N$ and letting them pretend to be multiples of $m$ but not of $mp_i$. In order for this to work, we need to show that there are not too many bad pairs $(m,p_i)$.
Bad pairs need to satisfy all of the following constraints:


*

*$m$ can't have more than $\lceil 4ed\rceil-2$ prime factors: for any prime factor $q$ of $m$, $mq$ has $i$-type $m$.

*no prime factor $q$ of $m$ can be below $p_i^{\frac{1}{\lceil 4ed\rceil}}$: otherwise, all of $m, mq, mq^2, ..., mq^{\lceil 4ed\rceil}$ would have $i$-type $m$ and be below $mp_i \le N$.

*the number of primes between $p_i$ and $N/m$ must be bounded above by $\lceil 4ed\rceil$: for any prime $q$ between $p_i$ and $N/m$, $mq$ has $i$-type $m$ and is below $N$.


By the first bullet point, we see that we must have $p_i \ge N^{\frac{1}{\lceil 4ed\rceil}}$, and then by the second bullet point we see that each prime factor of $m$ must be at least $N^{\frac{1}{\lceil 4ed\rceil^2}}$. By the third bullet point and the prime number theorem, $mp_i$ must be between $N(1-O(1/\log(N)^2))$ and $N$ (in fact we can get better bounds here).
Putting this all together, we see that the number of bad pairs is at most $O(N/\log(N)^2)$, where the implied constant depends only on $d$.
For the precise description of how we artificially inflate the number of multiples of $m$ for bad pairs $(m,p_i)$, we can invent a pretending function $F_N^i(m)$ for $p_i < N/2$ satisfying the following constraints:


*

*$F_N^{i-1}(m) = F_N^i(m) + F_N^i(mp_i)$

*$F_N^{i-1}(m) \ge \lceil 4ed\rceil F_N^i(mp_i)$ for $i\ge i_0$.

*$F_N^i(m) \ge \#_N^i(m)$ for $m \ne 1$, $F_N^i(1) \ge 0$.


You can easily check (using the fact that $m$ has at most $\lceil 4ed\rceil$ prime factors if $m$ is part of a bad pair) that such a pretending function exists as long as $\lceil 4ed\rceil^{\lceil 4ed\rceil}$ times the number of bad pairs is at most the number of primes between $N/2$ and $N$, and for $N$ sufficiently large this will be the case. Then you can define a strong $i$-type coloring to be a coloring in which the number of vertices colored with the color $m$ is at least $F_N^i(m)$, and inductively use Lemma 1 to prove strong $i$-type colorings exist.
In order to start the inductive process, we need to come up with an $i_0$-type coloring of our hypercube (note that for $N$ large, a strong $i_0$-type coloring is the same as an ordinary $i_0$-type coloring, since there will be no bad pairs $(m,p_i)$ where $m$ has a prime factor below $p_{i_0}$). This is fairly easy as long as $n$ is large compared to $2^{i_0}$. Basically, one can start with something like this (if $n$ was $11$ and $i_0$ was 3):
$\begin{array}{ccccccccccc} 30 & 1 & 2 & 15 & 2 & 1 & 10 & 3 & 2 & 5 & 6\\ 1 & 30 & 1 & 2 & 15 & 2 & 3 & 10 & 1 & 6 & 5\\ 30 & 1 & 2 & 15 & 2 & 1 & 10 & 3 & 2 & 5 & 6\\ \vdots & & & & & & & & & & \vdots\\ 1 & 30 & 1 & 2 & 15 & 2 & 3 & 10 & 1 & 6 & 5\\ 30 & 1 & 2 & 15 & 2 & 1 & 10 & 3 & 2 & 5 & 6\end{array}$
and then fix it so there aren't quite so many $30$s, etc.
A: One strategy would be to prove that from solutions to the cases $m$ and $n$ which are coprime, one can produce a solution for $m\cdot n$, and to construct solutions for prime power cases (maybe using a solution for $p^{k-1}$ to construct the solution for $p^k$). Then the following is one step of the solution:
Solution for the 2D case and $n=p$ an odd prime:
Start with the "standard" enumeration
$\begin{matrix}  1&2&3&4&...&p\\
p+1&p+2&p+3&...&... &2p\\
2p+1&...&...&...&...&3p\\
...&...&...&...&...&4p\\
...&...&...&...&...&...\\
...& ... & ...&...&...& p^2
\end{matrix}$
The problem is only the last column where
every entry is divisible by $p$. Now one can put "half"
of the multiples of $p$ in the first row:
$\begin{matrix}  1&2p&3&4p&...&(p-1)p&p\\
p+1&p+2&p+3&...&...&... &2\\
...&...&...&...&...&...&3p\\
...&...&...&...&...&...&4\\
...&...&...&...&...&...&...\\
...& ... & ...&...&...&...& p^2
\end{matrix}$
The only problem remaining is the last two entries of the first line. 
It suffices now to choose a prime number $q$ such that $2p<q<p^2$ and switch the positions of $p$ and $q$. 
A: This is not an answer, but a braindump of things that came up today (mainly focussing on the two-dimensional case, but most of it generalises to higher dimensions):


*

*In a random configuration approximately $\frac{6}{\pi^2} \approx 61\%$ of the adjacent cubes are coprime.


One can consider groups that naturally act on the set $C$ of configurations (such that they respect the property of a configuration being correct).


*

*Obviously the symmetry group of the square ($D_{4}$) acts on this set $C$.

*If $P$ denotes the set of primes $p$ such that $\frac{1}{2}n^{2} < p < n^{2}$, then $\mathrm{Sym}(P \cup \{1\})$ acts on $C$. (All numbers $1, \ldots, n^{2}$ are coprime to elements of $P \cup \{1\}$; hence we can permute this elements in a given solution.)

*Let $\mathrm{rad} \colon \{1, \ldots, N\} \to \mathbb{N}$ denote the radical function, taking $\prod_{i} p_{i}^{e_{i}}$ to $\prod_{i: e_{i}>0} p_{i}$. This function defines a partition on $\{1, \ldots, N\}$. Let $\mathrm{R}^N_{r} = \mathrm{rad}^{-1}(r)$ denote such a partition. Then $\mathrm{Sym}(\mathrm{R}^{n^2}_{r})$ acts on $C$. (This is because to numbers are coprime iff their radicals are coprime.)


I do not know a good way of estimating the size of $\mathrm{R}^{N}_{r}$, or more precisely:

Given $N$, what is (approximately) the size of the largest $\mathrm{R}^{N}_{r}$?

These groups show that there is essentially a unique solution are essentially $4$ solutions (thanks @Carl!) for the $3 \times 3$ problem. One has:


*

*$P \cup \{1\} = \{1,5,7\}$

*$\mathrm{R}_{2} = \{2,4,8\}$

*$\mathrm{R}_{3} = \{3,9\}$.


*

*By the parity condition mentioned in the comments, $6$ has to be at the middle of an edge, First consider the case that $6$ is at the middle of an edge, and by the $D_{4}$-action, it does not matter which edge we choose.
Next, we place $2,4,8$ on the other middles of edges. Then, $3,9$ go in the corners not adjacent to $6$. Finally $P \cup \{1\}$ is placed in the remaining squares.

*Next, observe that $6$ cannot be in the middle of the $3 \times 3$ square. After all, $\mathrm{R}_{2} \cup \mathrm{R}_{3}$ cannot be adjacent to $6$, but we can't fit those $5$ elements in the $4$ corners.

*This leaves us with the case that $6$ is in a corner, say $(1,1)$. Observe that we cannot place an element of $\mathrm{R}_{2}$ in $(2,3)$ or $(3,2)$. Up to the aforementioned symmetries, this leaves us with $3$ possible configurations to place $\mathrm{R}_{2}$ in the squares $\{ (1,3), (2,2), (3,1), (3,3) \}$. In all cases $\mathrm{R}_{3}$ have to be placed in the squares $\{ (2,3), (3,2) \}$. The remaining squares are filled with $P \cup \{1\}$.

Ok, got to leave now. Hope this helps someone.
