Skip to main content
1 of 2
Anthony Quas
  • 23.2k
  • 5
  • 63
  • 98

You can give a negative answer to Q3 basically by compactness. This is a standard argument in "ergodic optimization". In fact you can do slightly better than what you ask for. You can achieve the maximal density not only in a $\limsup$ sense, but actually in a limit sense. That is, if $\rho$ is the maximal $\limsup$ density, you can produce a point where for every $\epsilon>0$, there is an $N$ such that every $N\times N$ block has density at least $\rho-\epsilon$.

Proof: Let $F$ be the collection of forbidden all-one configurations and suppose these have maximum diameter $K$. Let $\xi_N$ be a legal configuration on $[1,N]^2$ with the maximal number of 1's. Let $\rho_N$ be the density of 1's in $\xi_N$ (the number of 1's divided by $N^2$). Let $\xi$ be any limit point of these configurations.

Claim 1: $\rho_N$ is a convergent sequence.

Proof: For $0\le k<N$, we have $(mN+k)^2\rho_{mN+k}\le (m+1)^2\rho_N N^2$ as if not, $\xi_{mN+k}$ contains an $N\times N$ sub-region with density exceeding $\rho_N$. We therefore obtain $\rho_{mN+k}\le (m+1)^2/m^2\rho_N$, so that $\limsup\rho_n\le \rho_N$. Hence $\lim\rho_n=\inf\rho_n$.

Now let $\epsilon>0$. Let $N$ be such that $(N+2K)^2/N^2<1+\epsilon$.

Claim 2: The restriction of $\xi$ to any $N\times N$ subregion has density at least $\rho-\epsilon$ of 1's.

Proof: Suppose not. Suppose that the restriction of $\xi$ to an $N\times N$ subregion $R$ has density less than $\rho-\epsilon$. Then since $\xi$ is the limit of a subsequence of $\xi_n$, there is a $\xi_n$, such that the restriction of $\xi_n$ to $R$ matches $\xi$. We now modify $\xi_n$: delete the $(N+2K)\times (N+2K)$ region surrounding $R$ and paste a copy of $\xi_N$ into the middle to produce $\tilde\xi_n$. This is a legal configuration. The number of 1's that have been removed is at most $(\rho-\epsilon)N^2+((N+2K)^2-N^2)<\rho N^2$. The number of 1's that have been added is $\rho_N N^2\ge \rho N^2$. Hence $\tilde\xi_n$ has greater density than $\xi_n$. This is a contradiction.

Anthony Quas
  • 23.2k
  • 5
  • 63
  • 98