On the approximation of permutons
Balázs Maga · 2026
Read On the approximation of permutons by Balázs Maga (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-02298.txt.
Introduction
Balázs Maga studies how well a permuton, a limit object for large permutations, can be approximated by finite permutations under a rectangular discrepancy measure. He transfers bounds from discrepancy theory into this more restricted setting. The question is which permutons admit good finite approximations and which resist them, and at what rate.
Maga shows superlinear approximation can occur only for permutons supported on graphs of measure-preserving functions. The local regularity of that supporting function then obstructs how good an approximation can be. For the biased Brownian separable permuton, he proves a lower bound on approximation error. The argument uses the fact that its supporting function has Lipschitz points almost surely, a subtle regularity trait.
Catalog record
| CREATOR | Balázs Maga |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.02298
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the approximation of permutons Balázs Maga 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. Keywords : permutons, rectangular distance, star discrepancy, self-similarity, Brownian separable permuton 1 Introduction A permuton is a probability measure on the unit square with uniform marginals. Permutons are the natural limit objects of permutations [ 11 ] , where convergence is defined via convergent substructure densities arising from sampling (cf. graphons and graph convergence). Permutons have received much attention in recent years, see for example [ 3 , 5 , 6 ] . We denote the set of permutons by \mathop{\mathrm{Perm}} . The convergence of a sequence of permutations \pi_{n}\in\mathop{\mathrm{Sym}}(n) to \mu\in\mathop{\mathrm{Perm}} is defined using pattern densities. The density t(\sigma,\pi) of a pattern \sigma\in\mathop{\mathrm{Sym}}(k) in \pi\in\mathop{\mathrm{Sym}}(n) for k\leq n is defined as the probability of (\pi(i_{j}))_{j=1}^{k} being order-isomorphic to (\sigma(j))_{j=1}^{k} for a uniform random increasing k -tuple (i_{j})_{j=1}^{k} in [n]=\{1,2,\dots,n\} . For example, in the permutation 15342\in\mathop{\mathrm{Sym}}(5) , five of the ten increasing 3-tuples are order-isomorphic to 132 (153, 154, 152, 132, and 142), hence t(132,15342)=5/10. Analogously, the density t(\sigma,\mu) of \sigma in \mu\in\mathop{\mathrm{Perm}} is defined as follows: taking an i.i.d. k -sample (x_{j},y_{j})_{j=1}^{k} , if (i_{j})_{j=1}^{k} is a permutation of [k] such that (x_{i_{j}})_{j=1}^{k} is an increasing sequence, t(\sigma,\mu) is the probability of (y_{i_{j}})_{j=1}^{k} being order-isomorphic to (\sigma(j))_{j=1}^{k} , see Figure 1 . (A random permutation sampled this way from \mu is called a \mu -random permutation .) (0,0) (1,1) (1/2, 1/2) (0,0) (1,1) (1/2, 1/2) Figure 1: A permuton \mu with two different 3-samples from it. With respect to the Lebesgue measure, \mu 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 \mu -random permutation of length 3 might equal 132: either one point lands in the singular part and the remaining two determine the pattern 21 in the absolutely continuous part, or all of them lands in the absolutely continuous part and determine 132 in there. Writing up the probabilities for both of these outcomes, it is straightforward to check t(132,\mu)=3/16+1/48=5/24 . A sequence of permutations (\pi_{n})_{n=1}^{\infty} is convergent if |\pi_{n}|\to\infty and t(\sigma,\pi_{n}) is convergent for each pattern \sigma . A fundamental result in permuton theory [ 11 ] is that a convergent permutation sequence determines a unique permuton whose pattern densities coincide with the corresponding limit densities. Conversely, we also know that any permuton \mu is the limit of a permutation sequence, conveniently proved by using \mu -random permutations and showing that they are very close to \mu with probability tending rapidly to one. This closeness is appropriately measured by the rectangular distance , defined by \mathop{d_{\square}}(\mu,\nu)=\sup_{R=[a,b]\times[c,d]}|\mu(R)-\nu(R)|, a metric which metrizes the topology induced by convergence in pattern densities and also the topology of weak convergence restricted to permutons. (For permutons, the supremum is actually a maximum.) By [ 11 , Lemma 4.2] a \mu -random permutation of length k (or more precisely, the naturally associated permuton, properly defined in Section 1.1 ) is at most k^{-1/4} apart from \mu in the rectangular distance with high probability. The proof given there actually guarantees distance O((\log k/k)^{1/2}) asymptotically almost surely, already shown in [ 8 , Lemma 4.9] without using the language of permutons. In this paper, we study the following question originally asked by Bálint Virág and communicated to the author by Balázs Ráth: to what extent can the approximation errors coming from random permutations be improved by a more careful choice? In other words, how well a given permuton can be approximated in \mathop{d_{\square}} by finite permutations? This can be thought of as the permuton version of the central question of measure-theoretic discrepancy theory. 1.1 The main results The permuton \widehat{\pi} naturally associated with \pi\in\mathop{\mathrm{Sym}}(n) is defined as the uniform measure on \bigcup_{i=1}^{n}\left[\frac{i-1}{n},\frac{i}{n}\right]\times\left[\frac{\pi(i)-1}{n},\frac{\pi(i)}{n}\right] , see Figure 2 . (We refer to these n grid squares as the base squares of either \pi or \widehat{\pi} .) We put D_{n}(\mu)=\min_{\pi\in\mathop{\mathrm{Sym}}(n)}\mathop{d_{\square}}(\mu,\widehat{\pi}). Figure 2: The permuton \mu from the previous figure approximated by the permuton \widehat{\pi} (shaded blue) for \pi=12348765 . The rectangle witnessing \mathop{d_{\square}}(\mu,\widehat{\pi})=1/8 is shown with green boundary. The best approximation is given by \pi^{\prime}=12345768 , showing D_{8}(\mu)=3/32 . Established results in measure-theoretic discrepancy theory [ 7 , 1 ] (to be explicitly stated in Section 2), partially coming from bounds given to Tusnády’s problem on combinatorial and geometric discrepancy [ 14 ] can be tailored to imply some bounds on D_{n} . Given the aforementioned results, the proofs are very simple: as we will see, approximation with finitely supported measures (as in discrepancy theory) has the same error decay rate as D_{n}(\mu) . We state the following theorem among the main results nevertheless for future reference. Theorem 1.1 . For any permuton \mu , D_{n}(\mu)=O(\log^{3/2}n/n). If \mu is absolutely continuous, D_{n}(\mu)=\Omega(\log^{1/2}n/n). If \mathop{\mathrm{supp}}\mu can be covered by finitely many curves that are monotone in both coordinates, then D_{n}(\mu)=\Theta(1/n). It is worth pointing out that the upper bound in Theorem 1.1 is significantly better than what is guaranteed by the standard approximation via \mu -random permutations discussed in the introduction. The last statement of Theorem 1.1 shows that singular permutons allow better rates of approximation, though as a basic triangle inequality based argument shows error D_{n}(\mu)=o(1/n) can hold along a subsequence at best. (This is sharpened below in Theorem 1.3 .) Such superlinear approximation even along a subsequence is only possible for permutons carried by measure-preserving bijections: Theorem 1.2 . Assume that D_{n}(\mu)=o(1/n) along a subsequence for a permuton \mu . Then there exists a measure-preserving bijection f:[0,1]\to[0,1] defined almost everywhere such that \mu=\mu_{f} , i.e. \mu is the uniform measure on the graph of f . The following theorem further refines the boundary of superlinear approximability and relates it to local regularity properties of f . Theorem 1.3 . Assume \mu=\mu_{f} for an almost everywhere defined measure-preserving bijection. 1. If D_{n}(\mu)=o(1/n) along a subsequence then D_{n}(\mu)=\omega(1/n) along another subsequence. 2. If f is Hölder- \alpha at a point x for some 0<\alpha\leq 1 , then D_{n}(\mu)=\Omega(n^{-1/\alpha}). In particular, if f is Lipschitz at a point x , then no superlinear approximation is possible. 3. The previous statement is sharp up to logarithmic factor: for every 0<\alpha\leq 1 there exists an almost everywhere defined measure-preserving bijection f which is Hölder- \alpha at a dense set of points with Hausdorff dimension 1 and satisfies D_{n}(\mu_{f})=O\left(\frac{\log n}{n^{1/\alpha}}\right) along a subsequence. We remark that for \alpha=1 , the third statement is trivial even without the logarithmic factor, as demonstrated by f(x)=x . We further note that D_{n} can decay arbitrarily fast using similar constructions to what is given in the proof of the third statement of Theorem 1.3 , but of course we