Nonlinear growth of the Chebyshev norm of matrices under maximal cross approximation

For the function $g(n)$ describing the maximal possible growth of the Chebyshev norms of maximal cross approximations of an $n\times n$ matrix, the inequality $4g(2k)\leqslant g(7k+3)$ is proved. The bound $g(n)\geqslant Cn^{\log_{7/2}4}$ is established on this basis.