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≥2m,n≥2 and real matrices A∈Rm×nA∈Rm×n there is an integer matrix B∈Zm×nB∈Zm×n such that |∑i∈I∑j∈J(aij−bij)|<4log2(min{m,n}) holds for all intervals I⊆[m]I⊆[m], J⊆[n]J⊆[n]. Such a matrix can be computed in time O(mnlog(min{m,n}))O(mnlog(min{m,n})). The result remains true if we add the requirement |aij−bij|<2|aij−bij|<2 for all i∈[m],j∈[n]i∈[m],j∈[n]. This is surprising, as the slightly stronger requirement |aij−bij|<1|aij−bij|<1 makes the problem equivalent to Tusnády’s problem.