Problem 1984

The answer is the following:
* If $\gcd(m, n) > 1$, then Freyja cannot win.
* If $\gcd(m, n) = 1$, then Freyja can win in a minimum of $(m-1)^2 + (n-1)^2$ questions.

First, we dispose of the case where $\gcd(m, n) > 1$. Write $d = \gcd(m, n)$. The idea is that any labeling where each $1 \times d$ rectangle has sum zero is valid. Thus, to learn the labeling, Freyja must ask at least one question in every row, which is clearly not possible in a finite number of questions.

Now suppose $\gcd(m, n) = 1$. We split the proof into two halves.

¶ Lower bound
Clearly, any labeling where each $m \times 1$ and $1 \times m$ rectangle has sum zero is valid. These labelings form a vector space with dimension $(m-1)^2$, by inspection. (Set the values in an $(m-1) \times (m-1)$ square arbitrarily and every other value is uniquely determined.)

Similarly, labelings where each $n \times 1$ and $1 \times n$ rectangle have sum zero are also valid, and have dimension $(n-1)^2$.

It is also easy to see that no labeling other than the all-zero labeling belongs to both categories; labelings in the first space are periodic in both directions with period $m$, while labelings in the second space are periodic in both directions with period $n$; and hence any labeling in both categories must be constant, ergo all-zero.

Taking sums of these labelings gives a space of valid labelings of dimension $(m-1)^2 + (n-1)^2$. Thus, Freyja needs at least $(m-1)^2 + (n-1)^2$ questions to win.

¶ Proof of upper bound using generating functions, by Ankan Bhattacharya
We prove:

Claim (Periodicity) — Any valid labeling is doubly periodic with period $mn$.

*Proof.* By Chicken McNugget, there exists $N$ such that $N$ and $N+1$ are both nonnegative integer linear combinations of $m$ and $n$.

Then both $mn \times N$ and $mn \times (N + 1)$ rectangles have zero sum, so $mn \times 1$ rectangles have zero sum. This implies that any two cells with a vertical displacement of $mn$ are equal; similarly for horizontal displacements. $\square$

With that in mind, consider a valid labeling. It naturally corresponds to a generating function
$$f(x, y) = \sum_{a=0}^{mn-1} \sum_{b=0}^{mn-1} c_{a,b} x^a y^b$$
where $c_{a,b}$ is the number in $(a, b)$.

The generating function corresponding to sums over $n \times m$ rectangles is
$$f(x, y)(1 + x + \cdots + x^{m-1})(1 + y + \cdots + y^{n-1}) = f(x, y) \cdot \frac{x^m - 1}{x - 1} \cdot \frac{y^n - 1}{y - 1}.$$
Similarly, the one for $m \times n$ rectangles is
$$f(x, y) \cdot \frac{x^n - 1}{x - 1} \cdot \frac{y^m - 1}{y - 1}.$$
Thus, the constraints for $f$ to be valid are equivalent to
$$f(x, y) \cdot \frac{x^m - 1}{x - 1} \cdot \frac{y^n - 1}{y - 1} \quad \text{and} \quad f(x, y) \cdot \frac{x^n - 1}{x - 1} \cdot \frac{y^m - 1}{y - 1}$$
being zero when reduced modulo $x^{mn} - 1$ and $y^{mn} - 1$, or, letting $\omega = \exp(2\pi i/m)$, both terms being zero when powers of $\omega$ are plugged in.

To restate the constraints one final time, we need
$$f(\omega^a, \omega^b) \cdot \frac{\omega^{am} - 1}{\omega^a - 1} \cdot \frac{\omega^{bn} - 1}{\omega^b - 1} = f(\omega^a, \omega^b) \cdot \frac{\omega^{an} - 1}{\omega^a - 1} \cdot \frac{\omega^{bm} - 1}{\omega^b - 1} = 0$$
for all $a, b \in \{0, \dots, mn - 1\}$.

This implies $f(\omega^a, \omega^b) = 0$ for most choices of $(a, b)$. If it does not, we need
$$\frac{\omega^{am} - 1}{\omega^a - 1} \cdot \frac{\omega^{bn} - 1}{\omega^b - 1} = \frac{\omega^{an} - 1}{\omega^a - 1} \cdot \frac{\omega^{bm} - 1}{\omega^b - 1} = 0.$$
This happens when (at least) one fraction in either product is zero.
* If the first fraction is zero, then either $n \mid a$ and $a > 0$, or $m \mid b$ and $b > 0$.
* If the second fraction is zero, then either $m \mid a$ and $a > 0$, or $n \mid b$ and $b > 0$.

If the first condition holds in both cases, then $mn \mid a$, but $0 < a < mn$, a contradiction. Thus if $n \mid a$, then we must have $n \mid b$, and similarly if $m \mid a$ then $m \mid b$.

The former case happens $(m - 1)^2$ times, and the latter case happens $(n - 1)^2$ times. Thus, at most $(m - 1)^2 + (n - 1)^2$ values of $f(\omega^a, \omega^b)$ are nonzero. It follows that the dimension of the space of valid labelings is at most $(m - 1)^2 + (n - 1)^2$, as desired.

Let Freyja ask about all cells $(x, y)$ in the two squares
$$\begin{aligned} S_1 &= [1, m-1] \times [1, m-1] \\ S_2 &= [m, m+n-2] \times [1, n-1]. \end{aligned}$$

In the beginning, one by one, Freyja determines all values inside of the rectangle $Q := [1, m-1] \times [m, n-1]$. To that end, on each step she considers some rectangle with $m$ rows and $n$ columns such that its top left corner is in $Q$ and all of the other values in it have been determined already. In this way, Freyja uncovers all of $Q$, starting with its lower right corner and then proceeding upwards and to the left.

Thus Freyja can learn all numbers inside of the rectangle
$$R := [1, m+n-2] \times [1, n-1] = Q \cup S_1 \cup S_2.$$

See the figure below for an illustration for $(m, n) = (5, 8)$. The first cell of $Q$ is uncovered using the dotted green rectangle.

We need one lemma:
Lemma
Let $m$ and $n$ be positive integers with $\gcd(m, n) = 1$. Consider an unknown sequence of real numbers $z_1, z_2, \dots, z_s$ with $s \ge m+n-2$. Suppose that we know the sums of all contiguous blocks of size either $m$ or $n$ in this sequence. Then we can determine all individual entries in the sequence as well.

*Proof.* By induction on $m+n$. Suppose, without loss of generality, that $m \le n$. Our base case is $m=1$, which is clear. For the induction step, set $\ell = n-m$. Each contiguous block of size $\ell$ within $z_1, z_2, \dots, z_{s-n}$ is the difference of two contiguous blocks of sizes $m$ and $n$ within the original sequence. By the induction hypothesis for $\ell$ and $m$, it follows that we can determine all of $z_1, z_2, \dots, z_{s-n}$. Then we determine the remaining $z_i$ as well, one by one, in order from left to right, by examining on each step an appropriate contiguous block of size $m$. $\square$

Let $T$ be the rectangle $[1, m+n-2] \times \{n\}$. By looking at appropriate rectangles of sizes $m \times n$ and $n \times m$ such that their top row is contained within $T$ and all of their other rows are contained within $R$, Freyja can learn the sums of all contiguous blocks of values of sizes $m$ and $n$ within $T$. By the Lemma, it follows that Freyja can uncover all of $T$.

In this way, with the help of the Lemma, Freyja can extend her rectangular area of knowledge both upwards and downwards. Once its height reaches $m+n-2$, by the same method she will be able to extend it to the left and right as well. This allows Freyja to determine all values in the grid. Therefore, $(m-1)^2 + (n-1)^2$ questions are indeed sufficient.