Fewest required values in magic square?

Solution 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$?