arXiv Math @arxiv_math@qoto.org

This paper introduces a novel method for finding integer sets that satisfy the Pythagorean theorem by leveraging the Higher-Order Binary Optimization (HOBO) formulation. Unlike the Quadratic Unconstrained Binary Optimization (QUBO) formulation, which struggles to express complex mathematical equations, HOBO's ability to model higher-order interactions between binary variables makes it well-suited for addressing more complex and expressive problem settings.

We consider stochastic optimization when one only has access to biased stochastic oracles of the objective and the gradient, and obtaining stochastic gradients with low biases comes at high costs. This setting captures various optimization paradigms, such as conditional stochastic optimization, distributionally robust optimization, shortfall risk optimization, and machine learning paradigms, such as contrastive learning. We examine a family of multi-level Monte Carlo (MLMC) gradient methods that exploit a delicate tradeoff among bias, variance, and oracle cost. We systematically study their total sample and computational complexities for strongly convex, convex, and nonconvex objectives and demonstrate their superiority over the widely used biased stochastic gradient method. When combined with the variance reduction techniques like SPIDER, these MLMC gradient methods can further reduce the complexity in the nonconvex regime. Our results imply that a series of stochastic optimization problems with biased oracles, previously considered to be more challenging, is fundamentally no harder than the classical stochastic optimization with unbiased oracles. We also delineate the boundary conditions under which these problems become more difficult. Moreover, MLMC gradient methods significantly improve the best-known complexities in the literature for conditional stochastic optimization and shortfall risk optimization. Our extensive numerical experiments on distributionally robust optimization, pricing and staffing scheduling problems, and contrastive learning demonstrate the superior performance of MLMC gradient methods.

Upper bounds on the minimum Lee distance of codes that are linear over $\mathbb{Z}_q$ are discussed. The bounds are Singleton like, depending on the length, rank, and alphabet size of the code. Codes meeting such bounds are referred to as Maximum Lee Distance (MLD) Codes. We present some new bounds, proved using combinatorial arguments. The new bounds provide improvements over those in the literature.

In recent work of Chan-Huang-Lee, it is shown that if a manifold enjoys uniform bounds on (a) the negative part of the scalar curvature, (b) the local entropy, and (c) volume ratios up to a fixed scale, then there exists a Ricci flow for some definite time with estimates on the solution assuming that the local curvature concentration is small enough initially (depending only on these a priori bounds). In this work, we show that the bound on scalar curvature assumption (a) is redundant. We also give some applications of this quantitative short-time existence, including a Ricci flow smoothing result for measure space limits, a Gromov-Hausdorff compactness result, and a topoligical and geometric rigidity result in the case that the a priori local bounds are strengthened to be global.

A result of Deza, Levin, Meesum, and Onn shows that the problem of deciding if a given sequence is the degree sequence of a 3-uniform hypergraph is NP complete. We tackle this problem in the random case and show that a random integer partition can be realized as the degree sequence of a $3$-uniform hypergraph with high probability. These results are in stark contrast with the case of graphs, where a classical result of Erdős and Gallai provides an efficient algorithm for checking if a sequence is a degree sequence of a graph and a result of Pittel shows that with high probability a random partition is not the degree sequence of a graph. By the same method, we address analogous realizability problems about high-dimensional binary contingency tables. We prove that if $(λ,μ,ν)$ are three independent random partitions then with high probability one can construct a three-dimensional binary contingency table with marginals $(λ,μ,ν)$. Conversely, if one insists that the contingency table forms a pyramid shape, then we show that with high probability one cannot construct such a contingency table. These two results confirm two conjectures of Pak and Panova.

We perform a phase space analysis of evolution equations associated with the Weyl quantization $q^{\mathrm{w}}$ of a complex quadratic form $q$ on $\mathbb{R}^{2d}$ with non-positive real part. In particular, we obtain pointwise bounds for the matrix coefficients of the Gabor wave packet decomposition of the generated semigroup $e^{tq^{\mathrm{w}}}$ if $\mathrm{Re} (q) \le 0$ and the companion singular space associated is trivial, with explicit and sharp exponential time decay rate. This result is then leveraged to achieve a comprehensive analysis of the phase regularity of $e^{tq^{\mathrm{w}}}$ with $\mathrm{Re} (q) \le 0$, hence extending the $L^2$ analysis of quadratic semigroups initiated by Hitrik and Pravda-Starov to general modulation spaces $M^p(\mathbb{R}^d)$, $1 \le p \le \infty$.

We establish a quantitative factorization theorem for the identity operator on $c_0$ via non-compact operators $T: C_0(K) \to X$, where $K$ is a scattered, locally compact Hausdorff space and $X$ is any Banach space not containing a copy of $\ell^1$ or with weak$^*$ sequentially compact dual unit ball. We show the connection between these factorizations and the essential norm of the adjoint operator. As a consequence of our results, we conclude that the essential norm is minimal for the Calkin algebra of these spaces.

We study the behavior of the superperiod map near the boundary of the moduli space of stable supercurves and prove that it is similar to the behavior of periods of classical curves. We consider two applications to the geometry of this moduli space in genus $2$, denoted as $\bar{\mathcal S}_2$. First, we characterize the canonical projection of $\bar{\mathcal S}_2$ in terms of its behavior near the boundary, proving in particular that $\bar{\mathcal S}_2$ is not projected. Secondly, we combine the information on superperiods with the explicit calculation of genus $2$ Mumford isomorphism, due to Witten, to study the expansion of the superstring measure for genus $2$ near the boundary. We also present the proof, due to Deligne, of regularity of the superstring measure on $\bar{\mathcal S}_g$ for any genus.

Recently it has been shown that the property of forward-flatness for discrete-time systems, which is a generalization of static feedback linearizability and a special case of a more general concept of flatness, can be checked by two different geometric tests. One is based on unique sequences of involutive distributions, while the other is based on a unique sequence of integrable codistributions. In this paper, the relation between these sequences is discussed and it is shown that the tests are in fact dual. The presented results are illustrated by an academic example.

In this paper, we compute the expected logarithmic energy of solutions to the polynomial eigenvalue problem for random matrices. We generalize some known results for the Shub-Smale polynomials, and the spherical ensemble. These two processes are the two extremal particular cases of the polynomial eigenvalue problem, and we prove that the logarithmic energy lies between these two cases. In particular, the roots of the Shub-Smale polynomials are the ones with the lowest logarithmic energy of the family.

In this article, we discuss the efficient ways of implementing the transparent boundary condition (TBC) and its various approximations for the free Schrödinger equation on a hyperrectangular computational domain in $\field{R}^d$ with periodic boundary conditions along the $(d-1)$ unbounded directions. In particular, we consider Padé approximant based rational approximation of the exact TBC and a spatially local form of the exact TBC obtained under its high-frequency approximation. For the spatial discretization, we use a Legendre-Galerkin spectral method with a boundary-adapted basis to ensure the bandedness of the resulting linear system. Temporal discretization is then addressed with two one-step methods, namely, the backward-differentiation formula of order 1 (BDF1) and the trapezoidal rule (TR). Finally, several numerical tests are presented to demonstrate the effectiveness of the methods where we study the stability and convergence behaviour empirically.

Given the action of a group $G$ on a set $X$, an endomorphism of $X$ is a function $f:X \rightarrow X$ which is $G$-equivariant, that is, it commutes with the action, i.e., $f(g\cdot x)= g\cdot f(x)$, for all $x\in X$. The set of endomorphisms of a $G$-set $X$ is a monoid, with the composition of functions , which we will denote $\mathrm{End}_{G}(X)$. Given subsets $U,N\subseteq M$, we say that $U$ generates $M$ modulo $N$ if it is satisfied that $M= \langle U \cup N \rangle$. The relative rank of M modulo N is the minimum cardinality of a set $U$ to generate $M$ modulo $N$. In this work we address the particular case in which $G$ and $X$ are finite to calculate the relative rank of the endomorphism monoid $\mathrm{End}_{G}(X)$ modulo its group of units, denoted by $\mathrm{Aut}_{G}(X)$. We also address structure situations, such as isomorphisms of $\mathrm{Aut}_{G}(X)$ and $\mathrm{End}_{G}(X)$ with other known structures.

This paper introduces nonlinear fractional Lane-Emden equations of the form, $$ D^α y(x) + \fracλ{x^β}~ D^β y(x) + f(y) =0, ~ ~1 < α\leq 2, ~~ 0< β\leq 1, ~~ 0 < x < 1,$$ subject to boundary conditions, $$ y'(0) =\mathbf{a} , ~~~ \mathbf{c}~ y'(1) + \mathbf{d}~ y(1) = \mathbf{b},$$ where, $D^α, D^β$ represent Caputo fractional derivative, $\mathbf{a, b,c,d} \in \mathbb{R}$, $ λ= 1, 2$, and $f(y)$ is non linear function of $y.$ We have developed collocation method namely, uniform fractional Haar wavelet collocation method and used it to compute solutions. The proposed method combines the quasilinearization method with the Haar wavelet collocation method. In this approach, fractional Haar integrations is used to determine the linear system, which, upon solving, produces the required solution. Our findings suggest that as the values of $(α, β)$ approach $(2,1),$ the solutions of the fractional and classical Lane-Emden become identical.

The Motsch-Tadmor (MT) model is a variant of the Cucker-Smale model with a normalized communication weight function. The normalization poses technical challenges in analyzing the collective behavior due to the absence of conservation of momentum. We study three quantitative estimates for the discrete-time MT model considering the first-order Euler discretization. First, we provide a sufficient framework leading to the asymptotic mono-cluster flocking. The proposed framework is given in terms of coupling strength, communication weight function, and initial data. Second, we show that the continuous transition from the discrete MT model to the continuous MT model can be made uniformly in time using the finite-time convergence result and asymptotic flocking estimate. Third, we present uniform-in-time stability estimates for the discrete MT model. We also provide several numerical examples and compare them with analytical results.

This paper introduces a memory-reduction third-order compact gas-kinetic scheme (CGKS) for solving compressible Euler and Navier-Stokes equations on 3D unstructured meshes. The scheme utilizes a time-evolution gas distribution function to provide a time-evolution solution at cell interfaces, enabling the implementation of Hermite WENO techniques for high-order reconstruction. However, the HWENO method needs to store a coefficients matrix for the quadratic polynomial to achieve third-order accuracy, resulting in high memory usage. A novel reconstruction method, built upon HWENO reconstruction, has been designed to enhance computational efficiency and reduce memory usage compared to the original CGKS. The simple idea is that the first-order and second-order terms of the quadratic polynomials are determined in a two-step way. In the first step, the second-order terms are obtained from the reconstruction of a linear polynomial of the first-order derivatives by only using the cell-averaged slopes, since the second-order derivatives are nothing but the "derivatives of derivatives". Subsequently, the first-order terms left can be determined by the linear reconstruction only using cell-averaged values. Thus, we successfully split one quadratic least-square regression into several linear least-square regressions, which are commonly used in a second-order finite volume code. Since only a small matrix inversion is needed in a 3-D linear least-square regression, the computational cost for the new reconstruction is dramatically reduced and the storage of the reconstruction-coefficient matrix is no longer necessary. The proposed new reconstruction technique can reduce the overall computational cost by about 20 to 30 percent. The challenging large-scale unsteady numerical simulation is performed, which demonstrates that the current improvement brings the CGKS to a new level for industrial applications.

We present a scalable and efficient framework for the inference of spatially-varying parameters of continuum materials from image observations of their deformations. Our goal is the nondestructive identification of arbitrary damage, defects, anomalies and inclusions without knowledge of their morphology or strength. Since these effects cannot be directly observed, we pose their identification as an inverse problem. Our approach builds on integrated digital image correlation (IDIC, Besnard Hild, Roux, 2006), which poses the image registration and material inference as a monolithic inverse problem, thereby enforcing physical consistency of the image registration using the governing PDE. Existing work on IDIC has focused on low-dimensional parameterizations of materials. In order to accommodate the inference of heterogeneous material propertes that are formally infinite dimensional, we present $\infty$-IDIC, a general formulation of the PDE-constrained coupled image registration and inversion posed directly in the function space setting. This leads to several mathematical and algorithmic challenges arising from the ill-posedness and high dimensionality of the inverse problem. To address ill-posedness, we consider various regularization schemes, namely $H^1$ and total variation for the inference of smooth and sharp features, respectively. To address the computational costs associated with the discretized problem, we use an efficient inexact-Newton CG framework for solving the regularized inverse problem. In numerical experiments, we demonstrate the ability of $\infty$-IDIC to characterize complex, spatially varying Lamé parameter fields of linear elastic and hyperelastic materials. Our method exhibits (i) the ability to recover fine-scale and sharp material features, (ii) mesh-independent convergence performance and hyperparameter selection, (iii) robustness to observational noise.

We consider $k$ square integrable random variables $Y_1,...,Y_k$ and $k$ random (row) vectors of length $p$, $X_1,...,X_k$ such that $X_i(l)$ is square integrable for $1\le i\le k$ and $1\le l\le p$. No assumptions whatsoever are made of any relationship between the $X_i$:s and $Y_i$:s. We shall refer to each pairing of $X_i$ and $Y_i$ as an environment. We form the square risk functions $R_i(β)=\mathbb{E}\left[(Y_i-βX_i)^2\right]$ for every environment and consider $m$ affine combinations of these $k$ risk functions. Next, we define a parameter space $Θ$ where we associate each point with a subset of the unique elements of the covariance matrix of $(X_i,Y_i)$ for an environment. Then we study estimation of the $\arg\min$-solution set of the maximum of a the $m$ affine combinations the of quadratic risk functions. We provide a constructive method for estimating the entire $\arg\min$-solution set which is consistent almost surely outside a zero set in $Θ^k$. This method is computationally expensive, since it involves solving polynomials of general degree. To overcome this, we define another approximate estimator that also provides a consistent estimation of the solution set based on the bisection method, which is computationally much more efficient. We apply the method to worst risk minimization in the setting of structural equation models.

Using the theory of Higgs bundles and their stabitlity properties associated to fibered surfaces and the Viehweg-Zuo characterization of Shimura curves in the moduli space of abelian varieties in terms of Higgs bundles, we prove that there does not exist any non-compact Shimura curves in the Prym locus of totally ramified $\Z_{2p}$- or $\Z_{2p}\times (\Z_{p})^{m-1}$-covers of the projective line in $A_{g}$ for $g\geq 8$, where $p\geq 5$ is a prime number.

Mathematical modelling is a cornerstone of computational biology. While mechanistic models might describe the interactions of interest of a system, they are often difficult to study. On the other hand, abstract models might capture key features but remain disconnected from experimental manipulation. Geometric methods have been useful in connecting both approaches, although they have only been established for specific type of systems. Phenomena of biological relevance, such as limit cycles, are still difficult to study using conventional methods. In this paper, I explore an alternative description of planar dynamical systems and I present an algorithm to compute numerically the geometric structure of planar systems with a limit cycle.

For a measurable space $(X,\mathcal{A})$, let $\mathcal{M}^+(X,\mathcal{A})$ be the commutative semiring of non-negative real-valued measurable functions with pointwise addition and pointwise multiplication. We show that there is a lattice isomorphism between the ideal lattice of $\mathcal{M}^+(X,\mathcal{A})$ and the ideal lattice of its ring of differences $\mathcal{M}(X,\mathcal{A})$. Moreover, we infer that each ideal of $\mathcal{M}^+(X,\mathcal{A})$ is a semiring $z$-ideal. We investigate the duality between cancellative congruences on $\mathcal{M}^{+}(X,\mathcal{A})$ and $Z_{\mathcal{A}}$-filters on $X$. We observe that for $σ$-algebras, compactness and pseudocompactness coincide, and we provide a new characterization for compact measurable spaces via algebraic properties of $\mathcal{M}^+(X,\mathcal{A})$. It is shown that the space of (real) maximal congruences on $\mathcal{M}^+(X,\mathcal{A})$ is homeomorphic to the space of (real) maximal ideals of the $\mathcal{M}(X,\mathcal{A})$. We solve the isomorphism problem for the semirings of the form $\mathcal{M}^+(X,\mathcal{A})$ for compact and realcompact measurable spaces.