More Like this

1. On the Diophantine equations of the form $$\lambda _1U_{n_1} + \lambda _2U_{n_2} +\cdots + \lambda _kU_{n_k} = wp_1^{z_1}p_2^{z_2} \cdots p_s^{z_s}$$

   https://doi.org/10.1007/s40590-024-00669-6  

   Goedhart, Eva ; Ha, Brian ; McBeath, Lily ; Velasco, Luisa ( October 2024 , Boletín de la Sociedad Matemática Mexicana)

   In this paper, we consider the Diophantine equation$$\lambda _1U_{n_1}+\cdots +\lambda _kU_{n_k}=wp_1^{z_1} \ldots p_s^{z_s},$$${\lambda }_1{U}_{n_1}+\cdots +{\lambda }_k{U}_{n_k}=w{p}_1^{z_1}\dots p_s^{z_s},$where$$\{U_n\}_{n\ge 0}$$${\left\{U_n\right\}}_{n\ge 0}$is a fixed non-degenerate linear recurrence sequence of order greater than or equal to 2;wis a fixed non-zero integer;$$p_1,\dots ,p_s$$$p_1,\cdots ,p_s$are fixed, distinct prime numbers;$$\lambda _1,\dots ,\lambda _k$$${\lambda }_1,\cdots ,{\lambda }_k$are strictly positive integers; and$$n_1,\dots ,n_k,z_1,\dots ,z_s$$$n_1,\cdots ,n_k,z_1,\cdots ,z_s$are non-negative integer unknowns. We prove the existence of an effectively computable upper-bound on the solutions$$(n_1,\dots ,n_k,z_1,\dots ,z_s)$$$(n_1,\cdots ,n_k,z_1,\cdots ,z_s)$. In our proof, we use lower bounds for linear forms in logarithms, extending the work of Pink and Ziegler (Monatshefte Math 185(1):103–131, 2018), Mazumdar and Rout (Monatshefte Math 189(4):695–714, 2019), Meher and Rout (Lith Math J 57(4):506–520, 2017), and Ziegler (Acta Arith 190:139–169, 2019).

    

   more » « less
2. On a Traveling Salesman Problem for Points in the Unit Cube

   https://doi.org/10.1007/s00453-024-01257-w  

   Balogh, József ; Clemen, Felix Christian ; Dumitrescu, Adrian ( September 2024 , Algorithmica)

   LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$${[0,1]}^k$where$$k \ge 2$$$k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$$x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$$|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$$c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$$x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$$k\ge 2$and$$n \ge 2$$$n\ge 2$, there existnpoints in$$[0,1]^k$$${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$$c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$$c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$$k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$$c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$$k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$$c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$$c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$$c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$$k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed.

    

   more » « less
3. Perfectly Packing a Square by Squares of Nearly Harmonic Sidelength

   https://doi.org/10.1007/s00454-023-00523-y  

   Tao, Terence ( July 2023 , Discrete & Computational Geometry)

   A well-known open problem of Meir and Moser asks if the squares of sidelength 1/nfor$$n\ge 2$$$n\ge 2$can be packed perfectly into a rectangle of area$$\sum _{n=2}^\infty n^{-2}=\pi ^2/6-1$$${\sum }_{n=2}^{\infty }{n}^{-2}={\pi }^2/6-1$. In this paper we show that for any$$1/2$1/2<t<1$, and any$$n_0$$$n_0$that is sufficiently large depending on t, the squares of sidelength$$n^{-t}$$$n^{-t}$for$$n\ge n_0$$$n\ge n_0$can be packed perfectly into a square of area$$\sum _{n=n_0}^\infty n^{-2t}$$${\sum }_{n=n_0}^{\infty }{n}^{-2t}$. This was previously known (if one packs a rectangle instead of a square) for$$1/2$1/2<t\le 2/3$(in which case one can take$$n_0=1$$$n_0=1$).

    

   more » « less
4. An Allard-type boundary regularity theorem for $2d$ minimizing currents at smooth curves with arbitrary multiplicity

   https://doi.org/10.1007/s10240-024-00144-y  

   De Lellis, Camillo ; Nardulli, Stefano ; Steinbrüchel, Simone ( February 2024 , Publications mathématiques de l'IHÉS)

   We consider integral area-minimizing 2-dimensional currents$T$$T$in$U\subset \mathbf {R}^{2+n}$$U\subset R^{2+n}$with$\partial T = Q\left [\!\![{\Gamma }\right ]\!\!]$$\partial T=Q〚\Gamma 〛$, where$Q\in \mathbf {N} \setminus \{0\}$$Q\in N\setminus \left\{0\right\}$and$\Gamma $$\Gamma$is sufficiently smooth. We prove that, if$q\in \Gamma $$q\in \Gamma$is a point where the density of$T$$T$is strictly below$\frac{Q+1}{2}$$\frac{Q+1}{2}$, then the current is regular at$q$$q$. The regularity is understood in the following sense: there is a neighborhood of$q$$q$in which$T$$T$consists of a finite number of regular minimal submanifolds meeting transversally at$\Gamma $$\Gamma$(and counted with the appropriate integer multiplicity). In view of well-known examples, our result is optimal, and it is the first nontrivial generalization of a classical theorem of Allard for$Q=1$$Q=1$. As a corollary, if$\Omega \subset \mathbf {R}^{2+n}$$\Omega \subset R^{2+n}$is a bounded uniformly convex set and$\Gamma \subset \partial \Omega $$\Gamma \subset \partial \Omega$a smooth 1-dimensional closed submanifold, then any area-minimizing current$T$$T$with$\partial T = Q \left [\!\![{\Gamma }\right ]\!\!]$$\partial T=Q〚\Gamma 〛$is regular in a neighborhood of $\Gamma $$\Gamma$.

    

   more » « less
5. Random Quantum Circuits Transform Local Noise into Global White Noise

   https://doi.org/10.1007/s00220-024-04958-z  

   Dalzell, Alexander M. ; Hunter-Jones, Nicholas ; Brandão, Fernando G. S. L. ( March 2024 , Communications in Mathematical Physics)

   We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the corresponding noiseless output distribution$$p_{\text {ideal}}$$$p_{\text{ideal}}$shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmarkFthat measures this correlation behaves as$$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$$F=\text{exp}(-2sϵ\pm O\left(s{ϵ}^2\right))$, where$$\epsilon $$$ϵ$is the probability of error per circuit location andsis the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the uniform distribution$$p_{\text {unif}}$$$p_{\text{unif}}$decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$$p_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1-F)p_{\text{unif}}$. In other words, although at least one local error occurs with probability$$1-F$$$1-F$, the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$O(F\epsilon \sqrt{s})$$$O\left(Fϵ\sqrt{s}\right)$. Thus, the “white-noise approximation” is meaningful when$$\epsilon \sqrt{s} \ll 1$$$ϵ\sqrt{s}\ll 1$, a quadratically weaker condition than the$$\epsilon s\ll 1$$$ϵs\ll 1$requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$s \ge \Omega (n\log (n))$$$s\ge \Omega (nlog(n\left)\right)$, which corresponds to onlylogarithmic depthcircuits, and if, additionally, the inverse error rate satisfies$$\epsilon ^{-1} \ge {\tilde{\Omega }}(n)$$${ϵ}^{-1}\ge \tilde{\Omega }\left(n\right)$, which is needed to ensure errors are scrambled faster thanFdecays. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexity-theoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.

    

   more » « less