pith. sign in

arxiv: 2605.02298 · v1 · submitted 2026-05-04 · 🧮 math.CO · math.PR

On the approximation of permutons

Bal\'azs Maga This is my paper

Pith reviewed 2026-05-08 18:30 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords permutonspermutationsrectangular discrepancyapproximationmeasure-preserving functionsBrownian separable permutondiscrepancy theorycombinatorics
0
0 comments X

The pith

Superlinear approximation of permutons by permutations occurs only when the permuton is supported by the graph of a measure-preserving function.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the optimal approximation of permutons by finite permutations measured in rectangular discrepancy. It transfers general discrepancy bounds to this setting and proves that superlinear rates are possible solely for permutons lying on the graph of a measure-preserving function. The local regularity of that function then creates an obstruction to closer approximation. For the biased Brownian separable permuton the supporting function has Lipschitz points almost surely, which produces an explicit lower bound on the error. This separates structured permutons from generic ones and clarifies which combinatorial objects behave like deterministic functions at large scale.

Core claim

Superlinear approximation can occur only for permutons supported by graphs of measure-preserving functions, and the local regularity of this function obstructs approximability. For the biased Brownian separable permuton the supporting measure-preserving function has Lipschitz points almost surely, yielding a lower bound on approximation error.

What carries the argument

The graph of a measure-preserving function supporting the permuton, whose local regularity controls the rectangular-discrepancy error under approximation by permutations.

If this is right

  • Superlinear rates are confined to permutons supported on graphs of measure-preserving functions.
  • Lipschitz points of the supporting function produce a strictly positive lower bound on approximation error.
  • General discrepancy bounds apply directly once the setting is restricted to permutations.
  • The biased Brownian separable permuton has a concrete, almost-sure lower bound on its approximation error.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Generic permutons without a supporting measure-preserving function are expected to admit only linear approximation rates.
  • The same regularity obstruction may limit approximation for other probability measures on the square with uniform marginals.
  • Explicit constructions of measure-preserving functions with controlled Lipschitz points could produce permutons with tunable approximation rates.

Load-bearing premise

Discrepancy bounds transfer from the general setting to rectangular-discrepancy approximation by permutations without further restrictions on the permuton or the approximating sequence.

What would settle it

A permuton whose support is not the graph of any measure-preserving function that nevertheless admits a sequence of permutations achieving superlinear approximation in rectangular discrepancy.

Figures

Figures reproduced from arXiv: 2605.02298 by Bal\'azs Maga.

Figure 1
Figure 1. Figure 1: A permuton µ with two different 3-samples from it. With respect to the Lebesgue measure, µ has nonzero singular and absolutely continuous parts: mass 1/2 is placed uniformly on the segment ((0, 0), (1/2, 1/2)) and mass 1/2 uniformly on the subsquare shaded in red. The two 3-samples visualize the two essentially different ways a µ-random permutation of length 3 might equal 132: either one point lands in the… view at source ↗
Figure 2
Figure 2. Figure 2: The permuton µ from the previous figure approximated by the permuton πp (shaded blue) for π “ 12348765. The rectangle witnessing d˝pµ,πpq “ 1{8 is shown with green boundary. The best approximation is given by π 1 “ 12345768, showing D8pµq “ 3{32. 1.1 The main results The permuton πp naturally associated with π P Sympnq is defined as the uniform measure on Ťn i“1 “ i´1 n , i n ‰ ˆ ” πpiq´1 n , πpiq n ı , see view at source ↗
Figure 3
Figure 3. Figure 3: The first panel shows a generic point set view at source ↗
Figure 4
Figure 4. Figure 4: A few steps of the described fractal scheme for view at source ↗
Figure 5
Figure 5. Figure 5: The Holder cusp (blue) for ¨ C “ 1,α “ 1{2 and the optimal Rt (red) constructed in the proof in the case when px, fpxqq is the center of Q. It is simple to see that regardless of the location of px, fpxqq in Q, a rectangle of this size can be found in the complement of the Holder cusp. (The worst-case scenario being when ¨ px, fpxqq is the midpoint of a vertical side of Q.) (By C ě 1, this value of t is in… view at source ↗
Figure 6
Figure 6. Figure 6: The construction of µ from three independent permutons distributed like µ. Here β “ 1 and p∆0,∆1,∆2q « p0.4,0.5,0.1q. (Reproduced from [Maa20, view at source ↗
read the original abstract

We study the optimal rectangular-discrepancy approximation of permutons by finite permutations. We transfer bounds from discrepancy theory to this more restricted setup. Moreover, we show that superlinear approximation can occur only for permutons supported by graphs of measure-preserving functions, and demonstrate how the local regularity of this function obstructs approximability. We also consider the biased Brownian separable permuton and prove a lower bound on its approximation error by showing that its supporting measure-preserving function has Lipschitz points almost surely.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper studies the optimal rectangular-discrepancy approximation of permutons by finite permutations. It transfers bounds from discrepancy theory to this restricted setting, proves that superlinear approximation can occur only for permutons supported on the graphs of measure-preserving functions, and shows that the local regularity of such a function obstructs the approximation rate. For the biased Brownian separable permuton, it establishes a lower bound on the approximation error by proving that the supporting measure-preserving function has Lipschitz points almost surely.

Significance. If the results hold, the work provides a useful characterization of when superlinear approximation is possible for permutons and links approximation rates to analytic properties of the supporting measure-preserving map. The transfer of discrepancy bounds and the almost-sure Lipschitz-point result for the Brownian model are concrete contributions that could inform further research on random permutons and their combinatorial approximations.

major comments (1)
  1. The transfer of discrepancy bounds from the unrestricted setting to rectangular-discrepancy approximation by permutations (abstract and the section establishing this transfer): the argument must be verified to hold without additional restrictions on the permuton or the approximating sequence, as this step is load-bearing for all subsequent claims about approximation rates.
minor comments (2)
  1. Clarify the precise definition of rectangular discrepancy early in the introduction to avoid ambiguity when comparing to classical discrepancy measures.
  2. In the section on the biased Brownian separable permuton, ensure that the almost-sure statement about Lipschitz points is accompanied by an explicit reference to the underlying probability space or measure.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, their positive overall assessment, and for identifying the need to confirm the validity of the discrepancy transfer. We address the single major comment below.

read point-by-point responses

  1. Referee: The transfer of discrepancy bounds from the unrestricted setting to rectangular-discrepancy approximation by permutations (abstract and the section establishing this transfer): the argument must be verified to hold without additional restrictions on the permuton or the approximating sequence, as this step is load-bearing for all subsequent claims about approximation rates.

    Authors: We agree that this transfer is foundational. The argument proceeds by observing that every finite permutation corresponds to an n-point set in the unit square with exactly one point in each row and column interval of length 1/n; rectangular discrepancy is defined identically to the classical setting. Consequently, any upper bound proved for arbitrary point sets in the discrepancy literature applies verbatim to this subclass, and any lower bound proved for permutations is automatically a lower bound in the unrestricted setting. No density, continuity, or other regularity assumptions on the target permuton are used, nor are any restrictions imposed on the approximating sequence beyond it consisting of permutations. To make this explicit and remove any ambiguity, we will insert a short clarifying paragraph immediately after the statement of the transfer theorem, spelling out the inclusion of permutation point sets into the general discrepancy framework and confirming that the cited bounds carry over directly. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The manuscript derives its main results on rectangular-discrepancy approximation rates for permutons through explicit transfers of discrepancy bounds, measure-theoretic support restrictions, and almost-sure Lipschitz properties of the supporting function for the biased Brownian separable permuton. These steps rely on standard constructions and independent arguments from discrepancy theory and probability, without reducing any central claim to a self-definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. The abstract and described proofs remain self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, no free parameters, ad-hoc axioms, or invented entities are introduced; the work relies on standard notions from measure theory, discrepancy theory, and probability.

axioms (1)
  • standard math Standard properties of measure-preserving functions and rectangular discrepancy
    Invoked implicitly when transferring bounds and discussing graphs of such functions.

pith-pipeline@v0.9.0 · 5359 in / 1264 out tokens · 35267 ms · 2026-05-08T18:30:18.847001+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Limits of permutation sequences , journal =

    Carlos Hoppen and Yoshiharu Kohayakawa and Carlos Gustavo Moreira and Balázs Ráth and Rudini. Limits of permutation sequences , journal =. 2013 , issn =. doi:https://doi.org/10.1016/j.jctb.2012.09.003 , url =

    work page doi:10.1016/j.jctb.2012.09.003 2013

  2. [2]

    Nonlinearity , abstract =

    Jozef Bobok and Serge Troubetzkoy , title =. Nonlinearity , abstract =. 2020 , month =. doi:10.1088/1361-6544/aba5e6 , url =

    work page doi:10.1088/1361-6544/aba5e6 2020

  3. [3]

    Nonlinearity , abstract =

    Jozef Bobok and Jernej Činč and Piotr Oprocha and Serge Troubetzkoy , title =. Nonlinearity , abstract =. 2022 , month =. doi:10.1088/1361-6544/ac62df , url =

    work page doi:10.1088/1361-6544/ac62df 2022

  4. [4]

    W. M. Schmidt , title =. 1972 , volume =

    work page 1972

  5. [5]

    Universal limits of sunstitution-closed permutation classes , volume =

    Bassino, Frédérique and Bouvel, Mathilde and Féray, Valentin and Gerin, Lucas and Maazoun, Mickaël and Pierrot, Adeline , year =. Universal limits of sunstitution-closed permutation classes , volume =. Journal of the European Mathematical Society , doi =

    work page

  6. [6]

    Combinatorics, Probability and Computing , author=

    On the Brownian separable permuton , volume=. Combinatorics, Probability and Computing , author=. 2020 , pages=. doi:10.1017/S0963548319000300 , number=

    work page doi:10.1017/s0963548319000300 2020

  7. [7]

    The Annals of Probability , number =

    Fr. The Annals of Probability , number =. 2018 , doi =

    work page 2018

  8. [8]

    Colloquium Publications , year=

    Large Networks and Graph Limits , author=. Colloquium Publications , year=

    work page

  9. [9]

    Unbiased Matrix Rounding , journal =

    Tobias Friedrich and Benjamin Doerr and Christian Klein and Ralf Osbild , keywords =. Unbiased Matrix Rounding , journal =. 2007 , note =. doi:https://doi.org/10.1016/j.endm.2007.01.007 , url =

    work page doi:10.1016/j.endm.2007.01.007 2007

  10. [10]

    1992 , isbn =

    Niederreiter, Harald , title =. 1992 , isbn =

    work page 1992

  11. [11]

    Cooper , keywords =

    Joshua N. Cooper , keywords =. Quasirandom permutations , journal =. 2004 , issn =. doi:https://doi.org/10.1016/j.jcta.2004.01.006 , url =

    work page doi:10.1016/j.jcta.2004.01.006 2004

  12. [12]

    On the geometry of the Birkhoff polytope I: the operator ^p_N -norms , journal=

    Bouthat, Ludovick and Mashreghi, Javad and Morneau-Gu. On the geometry of the Birkhoff polytope I: the operator ^p_N -norms , journal=. 2025 , month=. doi:10.1007/s44146-024-00152-8 , url=

    work page doi:10.1007/s44146-024-00152-8 2025

  13. [13]

    On the geometry of the Birkhoff polytope II: the Schatten p-norms , journal=

    Bouthat, Ludovick and Mashreghi, Javad and Morneau-Gu. On the geometry of the Birkhoff polytope II: the Schatten p-norms , journal=. 2025 , month=. doi:10.1007/s44146-024-00153-7 , url=

    work page doi:10.1007/s44146-024-00153-7 2025

  14. [14]

    The runsort permuton , journal =

    Noga Alon and Colin Defant and Noah Kravitz , abstract =. The runsort permuton , journal =. 2022 , issn =. doi:https://doi.org/10.1016/j.aam.2022.102361 , url =

    work page doi:10.1016/j.aam.2022.102361 2022

  15. [15]

    Scaling limits of permutation classes with a finite specification: A dichotomy , journal =

    Frédérique Bassino and Mathilde Bouvel and Valentin Féray and Lucas Gerin and Mickaël Maazoun and Adeline Pierrot , keywords =. Scaling limits of permutation classes with a finite specification: A dichotomy , journal =. 2022 , issn =. doi:https://doi.org/10.1016/j.aim.2022.108513 , url =

    work page doi:10.1016/j.aim.2022.108513 2022

  16. [16]

    Finitely forcible graphons and permutons , journal =

    Roman Glebov and Andrzej Grzesik and Tereza Klimošová and Daniel Král' , keywords =. Finitely forcible graphons and permutons , journal =. 2015 , issn =. doi:https://doi.org/10.1016/j.jctb.2014.07.007 , url =

    work page doi:10.1016/j.jctb.2014.07.007 2015

  17. [17]

    Tusn \'a dy's Problem, the Transference Principle, and Non-uniform QMC Sampling

    Aistleitner, Christoph and Bilyk, Dmitriy and Nikolov, Aleksandar. Tusn \'a dy's Problem, the Transference Principle, and Non-uniform QMC Sampling. Monte Carlo and Quasi-Monte Carlo Methods. 2018

    work page 2018

  18. [18]

    Mathematika , volume =

    Nikolov, Aleksandar , title =. Mathematika , volume =. doi:https://doi.org/10.1112/S0025579317000250 , url =. https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/S0025579317000250 , abstract =

    work page doi:10.1112/s0025579317000250

  19. [19]

    Chen, W. W. L. , title =. The Quarterly Journal of Mathematics , volume =. 1985 , month =. doi:10.1093/qmath/36.2.173 , url =

    work page doi:10.1093/qmath/36.2.173 1985

  20. [20]

    and Pixton, D

    Beck, Matthias and Pixton, Dennis , title=. Discrete. 2003 , month=. doi:10.1007/s00454-003-2850-8 , url=

    work page doi:10.1007/s00454-003-2850-8 2003

  21. [21]

    Convex polyhedra of doubly stochastic matrices

    Richard A Brualdi and Peter M Gibson , abstract =. Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function , journal =. 1977 , issn =. doi:https://doi.org/10.1016/0097-3165(77)90051-6 , url =

    work page doi:10.1016/0097-3165(77)90051-6 1977

  22. [22]

    , address =

    Folland, G.B. , address =. Real analysis : modern techniques and their applications , url =. Real analysis : modern techniques and their applications , edition =

    work page

  23. [23]

    Permuton limit of a generalization of the Mallows and k-card-minimum models , volume =

    Jasińska, Joanna and Ráth, Balázs , year =. Permuton limit of a generalization of the Mallows and k-card-minimum models , volume =. Electronic Communications in Probability , doi =

    work page

  24. [24]

    Geometry of Permutation Limits , journal=

    Rahman, Mustazee and Vir. Geometry of Permutation Limits , journal=. 2019 , month=. doi:10.1007/s00493-019-3817-6 , url=

    work page doi:10.1007/s00493-019-3817-6 2019

  25. [25]

    Ueber die kleinste Kugel, die eine räumliche Figur einschliesst

    Jung, Heinrich , journal =. Ueber die kleinste Kugel, die eine räumliche Figur einschliesst. , url =

    work page

  26. [26]

    Dekster, B. V. , title=. Acta Mathematica Hungarica , year=. doi:10.1007/BF01874495 , url=

    work page doi:10.1007/bf01874495

  27. [27]

    An efficient algorithm for the smallest enclosing ball problem in high dimensions , journal =

    Shaohua Pan and Xingsi Li , keywords =. An efficient algorithm for the smallest enclosing ball problem in high dimensions , journal =. 2006 , issn =. doi:https://doi.org/10.1016/j.amc.2005.01.127 , url =

    work page doi:10.1016/j.amc.2005.01.127 2006

  28. [28]

    Optimization Letters , year=

    Mordukhovich, Boris and Nam, Nguyen Mau and Villalobos, Cristina , title=. Optimization Letters , year=. doi:10.1007/s11590-012-0483-7 , url=

    work page doi:10.1007/s11590-012-0483-7

  29. [29]

    Halton, J. H. , title=. Numerische Mathematik , year=. doi:10.1007/BF01386213 , url=

    work page doi:10.1007/bf01386213

  30. [30]

    2002 , eprint=

    Quasirandom Permutations , author=. 2002 , eprint=

    work page 2002

  31. [31]

    Confluentes Mathematici , volume =

    F\'eray, Valentin and Rivera-Lopez, Kelvin , title =. Confluentes Mathematici , volume =. 2023 , pages =

    work page 2023

  32. [32]

    2025 , eprint=

    On the sampling entropy of permutons , author=. 2025 , eprint=

    work page 2025

  33. [33]

    Combinatorics, Probability and Computing , author=

    Record-biased permutations and their permuton limit , DOI=. Combinatorics, Probability and Computing , author=. 2026 , pages=

    work page 2026

  34. [34]

    Journal of the European Mathematical Society , year =

    Borga, Jacopo and Gwynne, Ewain and Sun, Xin , title =. Journal of the European Mathematical Society , year =

    work page