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 | ∑ i ∈ I ∑ j ∈ J ( a i j − b i j ) | < 4 log 2 ( 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.