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 ?



Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime
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.


