Fewest required values in magic square?

Question

A magic square of order $n$ is an $n \times n$ grid containing each of the numbers $1,2,\dots,n^2$, so that the numbers in each row, column, and diagonal sum to the same number $n(n^2+1)/2$.

This question follows on from Is half-filled magic square problem NP-complete? about completing a partially filled magic square.

For $n=3$ the middle square must be $5$, so if the middle square is set to another value then there is no way to complete the magic square. On the other hand, if $n=4$ and a single number is specified (anywhere in the grid), then there is always a way to complete the magic square. This can be checked by inspection of the list of order-4 magic squares, from the site of Harvey Heinz.

Let $f(n)$ be the smallest number of values that when placed in an $n\times n$ grid, results in an pattern that cannot be completed to form a magic square. By the previous two examples, $f(3) = 1$ and $f(4) \ge 2$. The value $f(n)$ can also be thought of as the least number of values required in a partial $n \times n$ magic square for the decision problem to be interesting.

This motivates the question:

What is the asymptotic behaviour of $f(n)$ as $n$ tends to infinity?

I would be especially interested in knowing whether $f(n) = O(\log n)$, or if $f(n) = \Omega(n)$ (using big-O notation).

Consider the $k$ smallest numbers specified together with the $n-k$ largest numbers in the same row. This will fail to reach $n^2(n-1)/2$ when $k \gt n/2$. It then follows that $1 \le f(n) \le \lceil (n+1)/2 \rceil$. Are there sharper upper and lower bounds on $f(n)$, perhaps by distinguishing the case of $n$ even from $n$ odd?

Answer 1

I have an idea which may lead to a proof that $f(n) = \Omega(\sqrt{n})$, but it would require quite a bit of work to flesh out.

Here is the idea: Take $n = m^2$. We are going to try to divide the n x n magic square into $m^2$ smaller m x m squares in such a way that each of our m clues lies in a different square. (Or as close to that as we can get).

Specifically, we are looking for a permutation $\pi \in S_n$ such that $\pi(n-k) = n - \pi(k)$. We then define the (a,b)-subsquare to be the subset $[\pi(ma),\pi(ma+1)...\pi(ma+m-1)]$ x $[\pi(mb),\pi(mb+1),...\pi(mb+m-1)]$ of our original square for $a,b \in [0,...m-1]$. We point out that the numbers on the $x=y$ diagonal of the (a,a)-subsquare all came from the corresponding diagonal of the main square. Likewise, the numbers on the $x=m-1-y$ diagonal of the (a,m-1-a)-subsquare came from the other diagonal of the main square.

We next look for a way to divide the numbers from 1 to $n^2 = m^4$ in such a way as to make all $m^2$ subsquares into magic squares with the same sum. This is not possible for m even, but may be possible for m odd. We don't actually need that they have the same sum, just that the m x m matrix of sums is itself a magic square, with non-distinct entries -- this may help us in the case of even m. Once we've done this, we've solved the original magic square.

1) For any m-point subset S of $[0,...,n-1]^2$, is there a permutation $\pi$ such that $(\pi(a),\pi(b))$ is not in the same subsquare as $(\pi(c),\pi(d))$ for $(a,b),(c,d) \in S$?

2) Given such a permutation, is there a way to complete the $m^2$ subsquares into magic squares with the same sum using the numbers from 1 to $m^4$?