More Like this

1. Almost all orbits of the Collatz map attain almost bounded values

   https://doi.org/10.1017/fmp.2022.8  

   Tao, Terence (January 2022, Forum of Mathematics, Pi)

   Abstract Define theCollatz map$${\operatorname {Col}} \colon \mathbb {N}+1 \to \mathbb {N}+1$$on the positive integers$$\mathbb {N}+1 = \{1,2,3,\dots \}$$by setting$${\operatorname {Col}}(N)$$equal to$$3N+1$$whenNis odd and$$N/2$$whenNis even, and let$${\operatorname {Col}}_{\min }(N) := \inf _{n \in \mathbb {N}} {\operatorname {Col}}^n(N)$$denote the minimal element of the Collatz orbit$$N, {\operatorname {Col}}(N), {\operatorname {Col}}^2(N), \dots $$. The infamousCollatz conjectureasserts that$${\operatorname {Col}}_{\min }(N)=1$$for all$$N \in \mathbb {N}+1$$. Previously, it was shown by Korec that for any$$\theta> \frac {\log 3}{\log 4} \approx 0.7924$$, one has$${\operatorname {Col}}_{\min }(N) \leq N^\theta $$for almost all$$N \in \mathbb {N}+1$$(in the sense of natural density). In this paper, we show that foranyfunction$$f \colon \mathbb {N}+1 \to \mathbb {R}$$with$$\lim _{N \to \infty } f(N)=+\infty $$, one has$${\operatorname {Col}}_{\min }(N) \leq f(N)$$for almost all$$N \in \mathbb {N}+1$$(in the sense of logarithmic density). Our proof proceeds by establishing a stabilisation property for a certain first passage random variable associated with the Collatz iteration (or more precisely, the closely related Syracuse iteration), which in turn follows from estimation of the characteristic function of a certain skew random walk on a$$3$$-adic cyclic group$$\mathbb {Z}/3^n\mathbb {Z}$$at high frequencies. This estimation is achieved by studying how a certain two-dimensional renewal process interacts with a union of triangles associated to a given frequency. 

   more » « less
2. Better Hardness Results for the Minimum Spanning Tree Congestion Problem

   https://doi.org/10.1007/s00453-024-01278-5  

   Luu, Huong; Chrobak, Marek (January 2025, Algorithmica)

   Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ $NP$-hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$, we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 8$$ $K\ge 8$, and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ $3-\mathrm{STC}$can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ $K\in \left(4,,,5,,,6,,,7\right)$remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 5$$ $K\ge 5$. This leaves only the case$$K=4$$ $K=4$open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for all$$K\ge 6$$ $K\ge 6$. 

   more » « less
3. Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game

   https://doi.org/10.1145/3732787  

   Maiti, Arnab; Boczar, Ross; Jamieson, Kevin; Ratliff, Lillian (April 2025, ACM Transactions on Economics and Computation)

   We study the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in two-player zero-sum matrix games. Fearnley and Savani [18] showed that for any randomized algorithm, there exists ann×ninput matrix where it needs to queryΩ(n²) entries in expectation to compute asingleNash equilibrium. On the other hand, Bienstock et al. [5] showed that there is a special class of matrices for which one can queryO(n) entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in terms of the number of rowsnof the input matrix\(A \in \mathbb {R}^{n \times n} \), row support size\(k_1 := |\bigcup \limits _{x \in \mathcal {X}_\ast } \text{supp}(x)| \), and column support size\(k_2 := |\bigcup \limits _{y \in \mathcal {Y}_\ast } \text{supp}(y)| \). We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)by querying at mostO(nk⁵· polylog(n)) entries of the input matrix\(A \in \mathbb {R}^{n \times n} \)in expectation, wherek≔ max{k₁,k₂}. This upper bound is tight up to a factor of poly(k), as we show that for any randomized algorithm, there exists ann×ninput matrix with min {k₁,k₂} = 1, for which it needs to queryΩ(nk) entries in expectation in order to find the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \). 

   more » « less
4. $L^p$ regularity of the Bergman projection on the symmetrized polydisc

   https://doi.org/10.4153/S0008414X24000634  

   Huo, Zhenghui; Wick, Brett D (October 2024, Canadian Journal of Mathematics)

   Abstract We study the$$L^p$$regularity of the Bergman projectionPover the symmetrized polydisc in$$\mathbb C^n$$. We give a decomposition of the Bergman projection on the polydisc and obtain an operator equivalent to the Bergman projection over antisymmetric function spaces. Using it, we obtain the$$L^p$$irregularity ofPfor$$p=\frac {2n}{n-1}$$which also implies thatPis$$L^p$$bounded if and only if$$p\in (\frac {2n}{n+1},\frac {2n}{n-1})$$. 

   more » « less
5. Construction of a Dirichlet form on Metric Measure Spaces of Controlled Geometry

   https://doi.org/10.1007/s11118-024-10144-6  

   Butaev, Almaz; Luo, Liangbing; Shanmugalingam, Nageswari (June 2024, Potential Analysis)

   Abstract Given a compact doubling metric measure spaceXthat supports a 2-Poincaré inequality, we construct a Dirichlet form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$that is comparable to the upper gradient energy form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$. Our approach is based on the approximation ofXby a family of graphs that is doubling and supports a 2-Poincaré inequality (see [20]). We construct a bilinear form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$using the Dirichlet form on the graph. We show that the$$\Gamma $$ $\Gamma$-limit$$\mathcal {E}$$ $E$of this family of bilinear forms (by taking a subsequence) exists and that$$\mathcal {E}$$ $E$is a Dirichlet form onX. Properties of$$\mathcal {E}$$ $E$are established. Moreover, we prove that$$\mathcal {E}$$ $E$has the property of matching boundary values on a domain$$\Omega \subseteq X$$ $\Omega \subseteq X$. This construction makes it possible to approximate harmonic functions (with respect to the Dirichlet form$$\mathcal {E}$$ $E$) on a domain inXwith a prescribed Lipschitz boundary data via a numerical scheme dictated by the approximating Dirichlet forms, which are discrete objects. 

   more » « less