Borel circle squaring

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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document &. 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] Go to document 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] Go to document 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},
      }
  • [K] Go to document A. S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, New York, 1995, vol. 156.
    @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] Go to document 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] Go to document 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] Go to document 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] Go to document 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] Go to document Á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},
      }
  • [W] Go to document S. Wagon, The Banach-Tarski Paradox, Cambridge University Press, Cambridge, 1985, vol. 24.
    @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},
      }

Authors

Andrew S. Marks

University of California at Los Angeles, Los Angeles, CA

Spencer T. Unger

University of California at Los Angeles, Los Angeles, CA