Can we arrange $\{1,...,16\}$ in $4\times 4$-grid so {products of rows} = {products of columns}?

Question

My motivation is the following question asked by Jacob Steiner, which he then deleted. For which $n\in\Bbb N$ is it possible to arrange $\{1,\ldots,n^2\}$ in an $n\times n$-grid so that the set of products of columns equals the set of products of rows?

The answer for $n=2$ is clearly No, since the only possibility, up to a transposition and a permutation of rows and columns, is

1 2 
3 4 

Since the set of products of rows are $\{2,12\}$ and the set of products of columns are $\{3,8\}$, this arrangement does not work. So for $n=2$, it is not possible to make such an arrangement.

Answer 1

Here's a solution for $n=3$, with products 30, 56, and 216:

5 2 3 
1 7 8 
6 4 9 

$n=4$, with products 6240, 672, 2520, and 1980:

13 16  3 10 
 4  6 14  2 
 8  7  5  9 
15  1 12 11 

$n=5$:

17  2  7 15 20 
14 25  9 11 16 
 6 21 13  3 12 
10 22 18 23  1 
 5 24  4  8 19 

$n=6$:

34 10  5 30 27 14 
25 19 36 11  7  2 
18 33 29  4 20  8 
 3 35 22 31 32  9 
15 12 16 21 17 26 
28  1  6 24 13 23 

$n=7$:

 5 38  1 26 40 44 24 
19 29 22 28  6 20 35 
10 11 31 36 46  3  2 
32 42 18 37 39  7 21 
13 25 23  9 41 34 48 
33 14  4 12 17 43 45 
16  8 30 49 15 27 47 

$n=8$:

37  8  5 63 24 18 31 30 
12 38 19 48 58  3 15 39 
 2 57 41 14 44 51 10 60 
 7  6 45 43 40  9 49 22 
50 29 11 33 47 46 56 64 
54 27 32  1 23 53 17 13 
62 20 34 21 28  4 59 35 
36 26 42 25 55 52 16 61 

$n=9$: infeasible

$n=10$:

53  46  45  31  68  24  20  72  18  65 
78  89  64  69  33  75  57  14   8  49 
93 100  67  81  32  41   4  94  98  74 
15  91  62  83  90  10  84  11   6  23 
34  66  21  26  79  86  12  13  36  60 
30   1  82  70  43  59  88  50  99  17 
40  56  63   2   9  44  97  38  95  58 
16  76  47  25  52  77  87  71  48   3 
27  54  80  28   7  51  19  96  73  55 
92  42  37  22  39   5  35  29  85  61

$n\in\{11,12,13\}$: infeasible

---

I used the following integer linear programming formulation. Let binary decision variable $x_{i,j,k}$ indicate whether cell $(i,j)$ has value $k$. You can use any objective function, and the constraints are: \begin{align} \sum_k x_{i,j,k} &= 1 &&\text{for all $i, j$} \tag1\label1 \\ \sum_{i,j} x_{i,j,k} &= 1 &&\text{for all $k$} \tag2\label2 \\ \sum_{j,k} \log(k) x_{t,j,k} &= \sum_{i,k} \log(k) x_{i,t,k} &&\text{for all $t$} \tag3\label3 \end{align} Constraint \eqref{1} forces each cell to contain exactly one value. Constraint \eqref{2} forces each value to appear in exactly one cell. Constraint \eqref{3} forces row $t$ and column $t$ to have the same product.

---

A numerically preferable alternative (with integer coefficients) to \eqref{3} is to let $P$ be the set of primes smaller than $n^2$, let $$k = \prod_{p\in P} p^{m_{k,p}}$$ be the prime factorization of $k$, and impose linear constraints \begin{align} \sum_{j,k} m_{k,p} x_{t,j,k} &= \sum_{i,k} m_{k,p} x_{i,t,k} &&\text{for all $t$ and $p$} \tag4\label4 \end{align} The idea is that row $t$ and column $t$ have the same product iff, for all $p$, prime $p$ appears with the same multiplicity in that row and column.

Answer 2

RobPratt has answered the question for all $n\le 13$. I shall prove in this answer that when $n\ge 11$, there is no solution.

Let $\pi$ be the prime counting function. I claim is impossible to form a grid whenever $$ \pi(n^2)-\pi(\lfloor n^2/2\rfloor )>n\tag1 $$ For any $n$ such that the above is true, there are at least $n+1$ primes in the range $\{1,\dots,n^2\}$ which are more than half of $n^2$. This means for any placement of $\{1,\dots,n^2\}$ in an $n\times n$ grid, there will exist two such "big" primes, $p$ and $q$, which are in the same row. The product of that row is a multiple of $pq$. But then none of the column products can be a multiple of $pq$, so no solution exists.

Since $\pi(n)\sim n/\log n$ as $n\to\infty$, by the prime number theorem, the LHS of $(1)$ grows faster than the RHS, so $(1)$ holds when $n$ is sufficiently large. Specifically, I can prove:

Claim: $(1)$ holds whenever $n\ge e^5\approx 148.4$.

My proof uses two numerical inequalities.

1. For all $n\ge 17$, we have from the Wikipedia article on $\pi(n)$ that $$\frac{n}{\log n}\le \pi(n)\le \frac43\cdot \frac{n}{\log n}$$

2. For all $n\ge 10$, we have $$\lfloor n^2/2\rfloor \ge n^2/2-1\ge n^{3/2}.$$ The first inequality is obvious; you can check that the second inequality is true when $n=10$, and by taking the derivative with respect to $n$, you can see that the function $n^2/2-1-n^{3/2}$ is increasing for $n\in [10,\infty)$.

Proof of Claim: $$ \begin{align} \pi(n^2)-\pi(\lfloor n^2/2\rfloor ) &\stackrel{1.}\ge \frac{n^2}{\log n^2}-\frac43\cdot \frac{\lfloor n^2/2\rfloor }{\log\lfloor n^2/2\rfloor} \\&\stackrel{2.}\ge \frac{n^2}{\log n^2}- \frac43\cdot \frac{ n^2/2}{\log n^{3/2}} =\frac{n^2}{18\log n} \end{align} $$ In order to have $\frac{n^2}{18\log n}>n$, it suffices to have $\frac{n}{\log n}>18$. It is easy to check that $\frac{n}{\log n}>18$ holds when $n= e^5$. Since $\frac{n}{\log n}$ is increasing for $n>e$, it holds whenever $n\ge e^5$ as well. $\square$

Finally, you can check with the help of a computer that $(1)$ holds for all $n$ in the range $[11,148]$. Combined with my claim, this completes the proof that no solution exists when $n\ge 11$. For example, the following Mathematica code returns True:

NoCounterExamples = True;

For[n = 11, n <= 150, n++,
    If[PrimePi[n^2] - PrimePi[Floor[n^2/2]] <= n, 
        NoCounterExamples = False]
];

Print[NoCounterExamples]

Answer 3

Not an answer, but pointing out a flaw in the OP logic.

If a prime factor appears singly (i.e. not squared) an odd number of times (like $5$ appearing as $\{5, 10, 15\}$ in the $4\times 4$ grid), that does not imply one of the appearances must be along the diagonal. E.g.

* 10  *  *
*  * 15  *
5  *  *  *
*  *  *  *

would meet the requirement as far as factors of $5$ are concerned: the first $3$ rows and the first $3$ columns each has exactly one factor of $5$ (and the last row and last column has no factor of $5$).

(These positions represent a (fixed-point-free) permutation in the $3 \times 3$ submatrix.)

UPDATE: Indeed Rob Pratt found such a matrix:

$$ \begin{matrix} 9 &15 &12 &1\\ 3 &11 &14 &5\\ 6 &7 &13 &16\\ 10 &2 &4 &8\end{matrix} $$

where the positions of the multiples of $5$ represent a fixed-point-free permutation of the $3\times 3$ submatrix after deleting the $3$rd row & column.

So the OP claim that the $4\times 4$ grid must have a factor of $5$ along the diagonal is wrong, and similarly, it is still unproven that $8 \times 8$ cannot be filled because that last $X$ does not need to be any multiple of $11, 17, 19$.