Logic Seminar

We give a completely constructive solution to Tarski's circle squaring problem. More generally, we prove a Borel version of an equidecomposition theorem due to Laczkovich. If k > 0 and A,B \subset R^k are bounded Borel sets with the same positive Lebesgue measure whose boundaries have upper Minkowski dimension less than k, then A and B are equidecomposable by translations using Borel pieces. This answers a question of Wagon. Our proof uses ideas from the study of flows in graphs, and a recent result of Gao, Jackson, Krohne, and Seward on special types of witnesses to the hyperfiniteness of free Borel actions of Z^d. This is joint work with Spencer Unger.