Abstract
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 \geq 1$ and $A, B \subset \mathbb{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 $\mathbb{Z}^d$.
-
[ABGPS]
R. Aharoni, E. Berger, A. Georgakopoulos, A. Perlstein, and P. Sprüssel, "The max-flow min-cut theorem for countable networks," J. Combin. Theory Ser. B, vol. 101, iss. 1, pp. 1-17, 2011.
@ARTICLE{ABGPS,
author = {Aharoni, Ron and Berger, Eli and Georgakopoulos, Agelos and Perlstein, Amitai and Sprüssel, Philipp},
title = {The max-flow min-cut theorem for countable networks},
journal = {J. Combin. Theory Ser. B},
fjournal = {Journal of Combinatorial Theory. Series B},
volume = {101},
year = {2011},
number = {1},
pages = {1--17},
issn = {0095-8956},
mrclass = {05C82 (05C21 05C63)},
mrnumber = {2737175},
mrreviewer = {Farhad Shahrokhi},
doi = {10.1016/j.jctb.2010.08.002},
url = {http://dx.doi.org/10.1016/j.jctb.2010.08.002},
zblnumber = {1221.05186},
} -
[BJ]
C. M. Boykin and S. Jackson, "Borel boundedness and the lattice rounding property," in Advances in Logic, Amer. Math. Soc., Providence, RI, 2007, vol. 425, pp. 113-126.
@INCOLLECTION{BJ,
author = {Boykin, Charles M. and Jackson, Steve},
title = {Borel boundedness and the lattice rounding property},
booktitle = {Advances in Logic},
series = {Contemp. Math.},
volume = {425},
pages = {113--126},
publisher = {Amer. Math. Soc., Providence, RI},
year = {2007},
mrclass = {03E15 (52C20)},
mrnumber = {2322367},
mrreviewer = {Miroslav RepickÂ${}^1\!/\!_2$},
doi = {10.1090/conm/425/08121},
url = {http://dx.doi.org/10.1090/conm/425/08121},
zblnumber = {1129.03026},
} -
[D] R. Diestel, Graph Theory, Fourth ed., Springer-Verlag, Heidelberg, 2010, vol. 173.
@BOOK{D,
author = {Diestel, Reinhard},
title = {Graph {T}heory},
series = {Grad. Texts in Math.},
volume = {173},
edition = {Fourth},
publisher = {Springer-Verlag, Heidelberg},
year = {2010},
pages = {xviii+437},
isbn = {978-3-642-14278-9},
mrclass = {05-01 (05Cxx)},
mrnumber = {2744811},
zblnumber = {1204.05001},
} -
[DHK]
L. Dubins, M. W. Hirsch, and J. Karush, "Scissor congruence," Israel J. Math., vol. 1, pp. 239-247, 1963.
@ARTICLE{DHK,
author = {Dubins, Lester and Hirsch, Morris W. and Karush, Jack},
title = {Scissor congruence},
journal = {Israel J. Math.},
fjournal = {Israel Journal of Mathematics},
volume = {1},
year = {1963},
pages = {239--247},
issn = {0021-2172},
mrclass = {52.30},
mrnumber = {0165424},
mrreviewer = {Victor Klee},
doi = {10.1007/BF02759727},
url = {http://dx.doi.org/10.1007/BF02759727},
zblnumber = {0171.43002},
} -
[G]
R. J. Gardner, "Convex bodies equidecomposable by locally discrete groups of isometries," Mathematika, vol. 32, iss. 1, pp. 1-9, 1985.
@ARTICLE{G,
author = {Gardner, R. J.},
title = {Convex bodies equidecomposable by locally discrete groups of isometries},
journal = {Mathematika},
fjournal = {Mathematika. A Journal of Pure and Applied Mathematics},
volume = {32},
year = {1985},
number = {1},
pages = {1--9},
issn = {0025-5793},
mrclass = {52A20 (51M20)},
mrnumber = {0817100},
mrreviewer = {Stan Wagon},
doi = {10.1112/S0025579300010780},
url = {http://dx.doi.org/10.1112/S0025579300010780},
zblnumber = {0574.52015},
} -
[GJ]
S. Gao and S. Jackson, "Countable abelian group actions and hyperfinite equivalence relations," Invent. Math., vol. 201, iss. 1, pp. 309-383, 2015.
@ARTICLE{GJ,
author = {Gao, Su and Jackson, Steve},
title = {Countable abelian group actions and hyperfinite equivalence relations},
journal = {Invent. Math.},
fjournal = {Inventiones Mathematicae},
volume = {201},
year = {2015},
number = {1},
pages = {309--383},
issn = {0020-9910},
mrclass = {03E15 (20K99)},
mrnumber = {3359054},
mrreviewer = {Barbara Majcher-Iwanow},
doi = {10.1007/s00222-015-0603-y},
url = {http://dx.doi.org/10.1007/s00222-015-0603-y},
zblnumber = {06468727},
} -
[GJKS] S. Gao, S. Jackson, E. Krohne, and B. Seward, Forcing constructions and countable Borel equivalence relations, 2015.
@MISC{GJKS,
author = {Gao, Su and Jackson, Steve and Krohne, E. and Seward, B.},
title = {Forcing constructions and countable {B}orel equivalence relations},
year = {2015},
arXiv = {1503.07822},
zblnumber = {},
} -
[GMP]
&. Grabowski, A. Máthé, and O. Pikhurko, "Measurable circle squaring," Ann. of Math. (2), vol. 185, iss. 2, pp. 671-710, 2017.
@ARTICLE{GMP,
author = {Grabowski, {\L}ukasz and Máthé, András and Pikhurko, Oleg},
title = {Measurable circle squaring},
journal = {Ann. of Math. (2)},
fjournal = {Annals of Mathematics. Second Series},
volume = {185},
year = {2017},
number = {2},
pages = {671--710},
issn = {0003-486X},
mrclass = {28A75 (51M25 52B45)},
mrnumber = {3612006},
zblnumber = {06701141},
doi = {10.4007/annals.2017.185.2.6},
} -
[JKL]
S. Jackson, A. S. Kechris, and A. Louveau, "Countable Borel equivalence relations," J. Math. Log., vol. 2, iss. 1, pp. 1-80, 2002.
@ARTICLE{JKL,
author = {Jackson, S. and Kechris, A. S. and Louveau, A.},
title = {Countable {B}orel equivalence relations},
journal = {J. Math. Log.},
fjournal = {Journal of Mathematical Logic},
volume = {2},
year = {2002},
number = {1},
pages = {1--80},
issn = {0219-0613},
mrclass = {03E15 (22A05)},
mrnumber = {1900547},
mrreviewer = {Otmar Spinas},
doi = {10.1142/S0219061302000138},
url = {http://dx.doi.org/10.1142/S0219061302000138},
zblnumber = {1008.03031},
} -
[NW]
H. Niederreiter and J. M. Wills, "Diskrepanz und Distanz von Ma\ss en bezüglich konvexer und Jordanscher Mengen," Math. Z., vol. 144, iss. 2, pp. 125-134, 1975.
@ARTICLE{NW,
author = {Niederreiter, Heiner and Wills, Jörg M.},
title = {Diskrepanz und {D}istanz von {M}a\ss en bezüglich konvexer und {J}ordanscher {M}engen},
journal = {Math. Z.},
fjournal = {Mathematische Zeitschrift},
volume = {144},
year = {1975},
number = {2},
pages = {125--134},
issn = {0025-5874},
mrclass = {10K05},
mrnumber = {0376588},
mrreviewer = {L. Kuipers},
doi = {10.1007/BF01190941},
url = {http://dx.doi.org/10.1007/BF01190941},
zblnumber = {0295.28028},
} -
@BOOK{K,
author = {Kechris, A. S.},
title = {Classical Descriptive Set Theory},
series = {Graduate Texts in Mathematics},
volume = {156},
publisher = {Springer-Verlag, New York},
year = {1995},
zblnumber = {0819.04002},
mrnumber = {1321597},
doi = {10.1007/978-1-4612-4190-4},
} -
[KM] A. S. Kechris and A. S. Marks, Descriptive graph, 2016.
@MISC{KM,
author = {Kechris, A. S. and Marks, A. S.},
title = {Descriptive graph},
year={2016},
note={preprint},
zblnumber = {},
} -
[KST] A. S. Kechris, S. Solecki, and S. Todorcevic, "Borel chromatic numbers," Adv. Math., vol. 141, iss. 1, pp. 1-44, 1999.
@ARTICLE{KST,
author = {Kechris, A. S. and Solecki, S. and Todorcevic, S.},
title = {Borel chromatic numbers},
journal = {Adv. Math.},
volume = {141},
number = {1},
year = {1999},
pages = {1--44},
zblnumber = {0918.05052},
mrnumber = {1667145},
} -
[L88]
M. Laczkovich, "Closed sets without measurable matching," Proc. Amer. Math. Soc., vol. 103, iss. 3, pp. 894-896, 1988.
@ARTICLE{L88,
author = {Laczkovich, M.},
title = {Closed sets without measurable matching},
journal = {Proc. Amer. Math. Soc.},
volume = {103},
year = {1988},
number = {3},
pages = {894--896},
zblnumber = {0668.28002},
mrnumber = {0947676},
doi = {10.2307/2046871},
} -
[L90]
M. Laczkovich, "Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem," J. Reine Angew. Math., vol. 404, pp. 77-117, 1990.
@ARTICLE{L90,
author = {Laczkovich, Miklós},
title = {Equidecomposability and discrepancy; a solution of {T}arski's circle-squaring problem},
journal = {J. Reine Angew. Math.},
fjournal = {Journal für die Reine und Angewandte Mathematik. [Crelle's Journal]},
volume = {404},
year = {1990},
pages = {77--117},
issn = {0075-4102},
mrclass = {51M25 (11K06 28A99 51M20)},
mrnumber = {1037431},
mrreviewer = {Stan Wagon},
doi = {10.1515/crll.1990.404.77},
url = {http://dx.doi.org/10.1515/crll.1990.404.77},
zblnumber = {0748.51017},
} -
[L92]
M. Laczkovich, "Decomposition of sets with small boundary," J. London Math. Soc. (2), vol. 46, iss. 1, pp. 58-64, 1992.
@ARTICLE{L92,
author = {Laczkovich, Miklós},
title = {Decomposition of sets with small boundary},
journal = {J. London Math. Soc. (2)},
fjournal = {Journal of the London Mathematical Society. Second Series},
volume = {46},
year = {1992},
number = {1},
pages = {58--64},
issn = {0024-6107},
mrclass = {11K38 (04A20 11K36 28D20)},
mrnumber = {1180882},
mrreviewer = {Rita Giuliano Antonini},
doi = {10.1112/jlms/s2-46.1.58},
url = {http://dx.doi.org/10.1112/jlms/s2-46.1.58},
zblnumber = {0776.11041},
} -
[S]
W. M. Schmidt, "Metrical theorems on fractional parts of sequences," Trans. Amer. Math. Soc., vol. 110, pp. 493-518, 1964.
@ARTICLE{S,
author = {Schmidt, Wolfgang M.},
title = {Metrical theorems on fractional parts of sequences},
journal = {Trans. Amer. Math. Soc.},
fjournal = {Transactions of the American Mathematical Society},
volume = {110},
year = {1964},
pages = {493--518},
issn = {0002-9947},
mrclass = {10.33 (10.30)},
mrnumber = {0159802},
mrreviewer = {H. Kesten},
doi = {10.2307/1993695},
url = {http://dx.doi.org/10.2307/1993695},
zblnumber = {0199.09402},
} -
[SS] S. Schneider and B. Seward, Locally nilpotent groups and hyperfinite equivalence relations.
@MISC{SS,
author = {Schneider, S. and Seward, B.},
title = {Locally nilpotent groups and hyperfinite equivalence relations},
note = {preprint},
zblnumber = {},
} -
[T] A. Tarski, "Probléme 38," Fund. Math., vol. 7, p. 381, 1925.
@ARTICLE{T,
author = {Tarski, A.},
title = {Probléme 38},
journal = {Fund. Math.},
volume = {7},
year = {1925},
pages = {381},
zblnumber = {},
} -
[Ti]
Ádám. Timár, "Boundary-connectivity via graph theory," Proc. Amer. Math. Soc., vol. 141, iss. 2, pp. 475-480, 2013.
@ARTICLE{Ti,
author = {Timár, Ádám},
title = {Boundary-connectivity via graph theory},
journal = {Proc. Amer. Math. Soc.},
fjournal = {Proceedings of the American Mathematical Society},
volume = {141},
year = {2013},
number = {2},
pages = {475--480},
issn = {0002-9939},
mrclass = {05C10 (05C63 20F65 60K35)},
mrnumber = {2996951},
mrreviewer = {W. Mader},
doi = {10.1090/S0002-9939-2012-11333-4},
url = {http://dx.doi.org/10.1090/S0002-9939-2012-11333-4},
zblnumber = {1259.05049},
} -
@BOOK{W,
author = {Wagon, S.},
title = {The Banach-Tarski Paradox},
series = {Encyclopedia of Mathematics and its Applications},
volume = {24},
note = {With a forward by Jan Mycielski},
publisher = {Cambridge University Press, Cambridge},
year = {1985},
zblnumber = {0569.43001},
doi = {10.1017/CBO9780511609596},
}