Matrix approximation and Tusnády's problem

We consider the problem of approximating a given matrix by an integer one such that in all geometric submatrices the sum of the entries does not change by much. We show that for all integers m, n ≥ 2 and real matrices A ∈ R^{m × n} there is an integer matrix B ∈ Z^{m × n} such that | under(∑, i ∈ I) under(∑, j ∈ J) (a_{i j} - b_{i j}) | < 4 log₂ (min {m, n}) holds for all intervals I ⊆ [m], J ⊆ [n]. Such a matrix can be computed in time O (m n log (min {m, n})). The result remains true if we add the requirement | a_{i j} - b_{i j} | < 2 for all i ∈ [m], j ∈ [n]. This is surprising, as the slightly stronger requirement | a_{i j} - b_{i j} | < 1 makes the problem equivalent to Tusnády's problem.