2018 Mathematical Sciences Publications and Grants

Aksoy, Asuman Güven. “Extensions of Bernstein’s Lethargy Theorem.” Springer Proceedings in Mathematics & Statistics: Algebra, Complex Analysis, and Pluripotential Theory, 2018, pp. 13-29.

Abstract: In this paper, we examine the aptly-named “Lethargy Theorem” of Bernstein and survey its recent extensions. We show that one of these extensions shrinks the interval for best approximation by half while the other gives a surprising connection to the space of bounded linear operators between two Banach spaces.

Aksoy, Asuman. Review of “The Marcinkiewicz-Type Discretization Theorems” by Vladimir N. Temlyakov. American Mathematical Society MathSciNet Mathematical Reviews, 2018, MR3848042.

Aksoy, Asuman. Review of “Metric Entropy of q-Hulls in Banach Spaces of Type-p” by James Cockreham and Fuchang Gao. American Mathematical Society MathSciNet Mathematical Reviews, 2018, MR3717949.

Aksoy, Asuman Güven, Zair Ibragimov, and Wesley Whiting. “Averaging One-Point Hyperbolic-Type Metrics.” Proceedings of the American Mathematical Society, vol. 146, 2018, pp. 5205-5218.

Abstract: It is known that the J-metric, the half-Apollonian metric, and the scale-invariant Cassinian metric are not Gromov hyperbolic. These metrics are defined as a supremum of one-point metrics (i.e., metrics constructed using one boundary point), and the supremum is taken over all boundary points. The aim of this paper is to show that taking the average instead of the supremum yields a metric that is Gromov hyperbolic. Moreover, we show that the Gromov hyperbolicity constant of the resulting metric does not depend on the number of boundary points used in taking the average. We also provide an example to show that the average of Gromov hyperbolic metrics is not, in general, Gromov hyperbolic.

Aksoy, Asuman Güven and Qidi Peng. “Constructing an Element of a Banach Space with Given Deviation from Its Nested Subspaces.” Khayyam Journal of Mathematics, vol. 4, issue 1, 2018, pp. 59-76.

Abstract: This paper contains two improvements on a theorem of S. N. Bernstein for Banach spaces. We show that if X is an arbitrary infinite-dimensional Banach space, {Y_n} is a sequence of strictly nested subspaces of X and if {d_n} is a non-increasing sequence of non-negative numbers tending to 0, then for any c ∈(0,1] we can find x_c ∈ X such that the distance ρ(x_c, Y_n) from x_c to Y_n satisfies

cd_n ≤ ρ(x_c, Y_n) ≤ 4 cd_n, for all n ∈ ℕ.

We prove the above inequality by first improving Borodin (2006)’s result for Banach spaces by weakening his condition on the sequence {d_n}. The weakened condition on em>d_n requires refinement of Borodin’s construction to extract an element in X, whose distances from the nested subspaces are precisely the given values d_n.

Böttcher, Albrecht, Lenny Fukshansky, Stephan Ramon Garcia, and Hiren Maharaj. “Lattice Theory and Toeplitz Determinants.” Operator Theory: Advances and Applications, vol. 262, 2018, pp. 117-138.

Abstract: This is a survey of our recent joint investigations of lattices that are generated by finite Abelian groups. In the case of cyclic groups, the volume of a fundamental domain of such a lattice is a perturbed Toeplitz determinant with a simple Fisher-Hartwig symbol. For general groups, the situation is more complicated, but it can still be tackled by pure matrix theory. Our main result on the lattices under consideration states that they always have a basis of minimal vectors, while our results in the other direction concern exact and asymptotic formulas for perturbed Toeplitz determinants. The survey is a slightly modified version of the talk given by the first author at the Humboldt Kolleg and the IWOTA in Tbilisi in 2015. It is mainly for operator theorists and therefore also contains an introduction to the basics of lattice theory.

Fukshansky, Lenny and Nikolay Moshchevitin. “On an Effective Variation of Kronecker's Approximation Theorem Avoiding Algebraic Sets.” Proceedings of the American Mathematical Society, vol. 146, no. 10, 2018, pp. 4151-4163.

Abstract: The classical Kronecker's approximation theorem asserts that the image of an integer lattice under a linear map is dense in the multiplicative torus in every dimension. We prove an effective version of this statement for algebraic lattices, as well as a variation of this result for points of the lattice avoiding a fixed algebraic set.

Fukshansky, Lenny and Ahmad A. Shaar. “A New Family of One-Coincidence Sets of Sequences with Dispersed Elements for Frequency Hopping CDMA Systems.” Advances in Mathematics of Communications, vol. 12 no. 1, 2018, pp. 181-188.

Abstract: We present a new family of one-coincidence sequence sets suitable for frequency hopping code division multiple access (FH-CDMA) systems with dispersed (low density) sequence elements. These sets are derived from one-coincidence prime sequence sets, such that for each one-coincidence prime sequence set there is a new one-coincidence set comprised of sequences with dispersed sequence elements, required in some circumstances, for FH-CDMA systems. Getting rid of crowdedness of sequence elements is achieved by doubling the size of the sequence element alphabet. In addition, this doubling process eases control over the distance between adjacent sequence elements. Properties of the new sets are discussed.

Banks, Jacqueline, Scott M. Garrabrant, Mark L. Huber, and Anne Perizzolo. “Using TPA to Count Linear Extensions.” Journal of Discrete Algorithms, vol. 51, 2018, pp. 1-11.

Abstract: A linear extension of a poset P is a permutation of the elements of the set that respects the partial order. Let L(P) be the set of linear extensions. It is a #P complete problem to determine the size of L(P) exactly for an arbitrary poset, and so randomized approximation algorithms are used that employ samples that are uniformly drawn from the set of linear extensions. In this work, a new randomized approximation algorithm is proposed where the linear extensions are not uniformly drawn, but instead come from a distribution indexed by a continuous parameter β. The introduction of β allows for the use of a more efficient method for approximating #L(P) called TPA. Our primary result is that it is possible to sample from this continuous embedding in time that as fast or faster than the best known methods for sampling uniformly from linear extensions. For a poset containing n elements, this means we can approximate L(P) to within a factor of 1+ϵ with probability at least 1−δ using O(n ³(ln n)(ln # L(P))² ϵ⁻² lnδ⁻¹) expected number of random uniforms and comparisons.

Feng, J., M. Huber, and Y. Ruan*. “Monte Carlo with User-Specified Relative Error.” Springer Proceedings in Mathematics & Statistics, Monte Carlo and Quasi-Monte Carlo Methods, vol. 241, edited by Art B. Owen and Peter W. Glynn. Springer, 2018, pp. 235-248.

Abstract: Consider an estimate b for a with the property that the distribution of the relative error (b/a) - 1 does not depend upon a, but can be chosen by the user ahead of time. Such an estimate will be said to have user-specified relative error (USRE). USRE estimates for continuous distributions such as the exponential have long been known, but only recently have unbiased USRE estimates for Bernoulli and Poisson data been discovered. In this work, biased USRE estimates are examined, and it is shown how to precisely choose the bias in order make the chance that the absolute relative error lies above a threshold decay as quickly as possible. In fact, for Poisson data this decay (on average) is slightly faster than if the CLT approximation is used.

Huber, Mark. “Adaptive Monte Carlo Integration.” Wiley StatsRef: Statistics Reference Online, 2018.

Abstract: Adaptive Monte Carlo algorithms use randomness to approximate integrals and sums. They adapt in two ways. Some use a number of samples that automatically adjust themselves based on the problem under consideration. Others change the domain from which the sample is taken based on previous samples. Both kinds of methods typically have robust guarantees on the relative error of the resulting estimates.

Aksoy, Asuman Güven, Zair Ibragimov, and Wesley Whiting. “Averaging One-Point Hyperbolic-Type Metrics.” Proceedings of the American Mathematical Society, vol. 146, 2018, pp. 5205–5218.

Abstract: It is known that the J-metric, the half-Apollonian metric, and the scale-invariant Cassinian metric are not Gromov hyperbolic. These metrics are defined as a supremum of one-point metrics (i.e., metrics constructed using one boundary point), and the supremum is taken over all boundary points. The aim of this paper is to show that taking the average instead of the supremum yields a metric that is Gromov hyperbolic. Moreover, we show that the Gromov hyperbolicity constant of the resulting metric does not depend on the number of boundary points used in taking the average. We also provide an example to show that the average of Gromov hyperbolic metrics is not, in general, Gromov hyperbolic.

External Grant: Kao, Chiu-Yen (PI). National Science Foundation Grant DMS 1818948, “Numerical Spectral Study of Elliptic Operators,” June 1, 2018-May 31, 2021.

Abstract: Since Lord Rayleigh conjectured more than a century ago that the disk should minimize the first Laplace-Dirichlet eigenvalue among all shapes of equal area, spectral study of elliptic operators has been an active research topic with applications including mechanical vibration, optical resonators, photonic crystals, and population dynamics. In mechanical vibration, for example, it is interesting to explore what shapes or what density distributions can generate minimal fundamental frequency; in photonic crystals, one seeks to design semiconductor structures with a periodic variation of refractive index to maximize photonic bandgap in which the propagation of light is forbidden. This project aims to advance numerical approaches to these kinds of questions for classes of eigenvalue problems that arise in design of containers to minimize fluid sloshing and in vibration control. Researchers have turned their attention to these questions with a renewed interest due to surprising recent discoveries, which include symmetry structure found in the optimizer of Steklov eigenvalue problems, optimal density arrangements in thin plates, and localization of vibration induced by interior clamped points. The project will explore a range of related open questions and aims to develop numerical approaches to solve them. The project also provides opportunities for mentoring students and engaging interested scientists, including those from underrepresented groups. Results are expected to have important potential application in systems that reduce liquid sloshing in missiles and other vessels, in noise and vibration control, and in medical and geophysical imaging. This project aims to develop numerical approaches to solve Steklov and biharmonic eigenvalue problems and study their related shape and topology optimization problems. The forward solvers for this project are based on boundary integral methods, finite element methods, and spectral methods. The optimization solvers are based on shape/topology derivatives and rearrangement methods. The investigator will study a wide range of problems arising from applications in liquid sloshing and plate vibrations, including (1) computation of the k-th Steklov eigenvalue problem and its optimization among star-shaped domains in three dimensions, (2) computation of principal eigenvalue of mixed Steklov eigenvalue problems and its related shape optimization, (3) Steklov eigenvalue problems on general manifolds, (4) spectral study of buckled plate eigenvalue problems, (5) localization of eigenfunctions induced by clamped points, and (6) multiphase shape optimization problems involving biharmonic operators.

Azimipour, Sanaz and Pavel Naumov. “Lighthouse Principle for Diffusion in Social Networks.” Journal of Applied Logics-IfCoLoG Journal of Logics and Their Applications, vol. 5, issue 1, 2018, pp. 97-120.

Abstract: The article investigates an influence relation between two sets of agents in a social network. It proposes a logical system that captures propositional properties of this relation valid in all threshold models of social networks with the same structure. The logical system consists of Armstrong axioms for functional dependence and an additional Lighthouse axiom. The main results are soundness, completeness, and decidability theorems for this logical system.

Deuser, Kaya and Pavel Naumov. “Armstrong’s Axioms and Navigation Strategies.” Proceedings of 32nd AAAI Conference on Artificial Intelligence, AAAI-18, 2018, pp. 6343-6350.

Abstract: The paper investigates navigability with imperfect information. It shows that the properties of navigability with perfect recall are exactly those captured by Armstrong's axioms from database theory. If the assumption of perfect recall is omitted, then Armstrong's transitivity axiom is not valid, but it can be replaced by a weaker principle. The main technical results are soundness and completeness theorems for the logical systems describing properties of navigability with and without perfect recall.

Deuser, Kaya and Pavel Naumov. “Navigability with Bounded Recall.” Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR-18, 2018, pp. 635-636.

Abstract: The paper studies navigability by machines with bounded recall in mazes with imperfect information. The main result is a sound and complete logical system for the relation “there is a machine with at most n states that can navigate from a set of classes of indistinguishable rooms X to a set of classes of indistinguishable rooms Y ”. The axioms of the system generalize Armstrong’s axioms of functional dependency from database theory.

Deuser, Kaya and Pavel Naumov. “Navigability with Intermediate Constraints.” Journal of Logic and Computation, vol. 28, issue 7, 2018, pp. 1647-1670.

Abstract: The article studies navigability of an autonomous agent in a maze where some rooms may be indistinguishable. In a previous work the authors have shown that the properties of navigability in such a setting depend on whether an agent has perfect recall. Navigability by strategies with perfect recall is a transitive relation and navigability by memoryless strategies is not. Independently, Li and Wang proposed a notion of navigability with intermediate constraints for linear navigation strategies. Linear strategies are different from both perfect recall and memoryless strategies. This article shows that a certain form of transitivity, expressible in the language with intermediate constraints, holds for memoryless strategies. The main technical result is a sound and complete logical system describing the properties of memoryless strategies in the language with intermediate constraints.

Naumov, Pavel and Kevin Ros. “Strategic Coalitions in Systems with Catastrophic Failures.” Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR-18, 2018, pp. 659-660.

Abstract: The paper introduces a notion of a transition system with catastrophic failures where in each state and under each action profile of the agents the system might either transition to a next state or fail with a given probability. The main technical result is a sound and complete axiomatization of modality “coalition has a strategy to survive with a given probability while achieving a given goal.”

Naumov, Pavel and Jia Tao. “Second-Order Know-How Strategies.” Proceedings of the Seventeenth International Conference on Autonomous Agents and Multiagent Systems, AAMAS-18, 2018, pp. 390-398.

Abstract: The fact that a coalition has a strategy does not mean that the coalition knows what the strategy is. If the coalition knows the strategy, then such a strategy is called a know-how strategy of the coalition. The paper proposes the notion of a second-order know-how strategy for the case when one coalition knows what the strategy of another coalition is. The main technical result is a sound and complete logical system describing the interplay between the distributed knowledge modality and the second-order coalition know-how modality.

Naumov, Pavel and Jia Tao. “Strategic Coalitions with Perfect Recall.” Proceedings of the 32^nd AAAI Conference on Artificial Intelligence, AAAI-18, 2018, pp. 4702-4709.

Abstract: The paper proposes a bimodal logic that describes an interplay between distributed knowledge modality and coalition know-how modality. Unlike other similar systems, the one proposed here assumes perfect recall by all agents. Perfect recall is captured in the system by a single axiom. The main technical results are the soundness and the completeness theorems for the proposed logical system.

Naumov, Pavel and Jia Tao. “Together We Know How to Achieve: An Epistemic Logic of Know-How.” Artificial Intelligence, vol. 262, 2018, pp. 279-300.

Abstract: The existence of a coalition strategy to achieve a goal does not necessarily mean that the coalition has enough information to know how to follow the strategy. Neither does it mean that the coalition knows that such a strategy exists. The article studies an interplay between the distributed knowledge, coalition strategies, and coalition “know-how” strategies. The main technical result is a sound and complete trimodal logical system that describes the properties of this interplay.

Elhamdadi, Mohamed, Minghui Liu, and Sam Nelson. “Quasi-Trivial Quandles and Biquandles, Cocycle Enhancements and Link-Homotopy of Pretzel Links.” Journal of Knot Theory and Its Ramifications, vol. 27, no. 11, 2018, 1843007.

Abstract: We investigate some algebraic structures called quasi-trivial quandles and we use them to study link-homotopy of pretzel links. Precisely, a necessary and sufficient condition for a pretzel link with at least two components being trivial under link-homotopy is given. We also generalize the quasi-trivial quandle idea to the case of biquandles and consider enhancement of the quasi-trivial biquandle cocycle counting invariant by quasi-trivial biquandle cocycles, obtaining invariants of link-homotopy type of links analogous to the quasi-trivial quandle cocycle invariants in Inoue's paper.

Ho, Melinda and Sam Nelson. “Symmetric Enhancements of Involutory Virtual Birack Counting Invariants.” Journal of Knot Theory and Its Ramifications, vol. 27, no. 5, 2018, 1850032.

Abstract: We consider involutory virtual biracks with good involutions, also known as symmetric involutory virtual biracks. Any good involution on an involutory virtual birack defines an enhancement of the counting invariant. We provide examples demonstrating that the enhancement is stronger than the unenhanced counting invariant.

Kim, Jieon and Sam Nelson. “Biquasile Colorings of Oriented Surface-Links.” Topology and Its Applications, vol. 236, 2018, pp. 64-76.

Abstract: We introduce colorings of oriented surface-links by biquasiles using marked graph diagrams. We use these colorings to define counting invariants and Boltzmann enhancements of the biquasile counting invariants for oriented surface-links. We provide examples to show that the invariants can distinguish both closed surface-links and cobordisms and are sensitive to orientation.

External Grant: Wong, Helen (PI). National Science Foundation Standard Grant, DMS-1841221. RUI: “Skeins on Surfaces,” July 1, 2018-May 31, 2019, $50,998.

Abstract: On the main, this research project lies in the broad interdisciplinary area between geometric topology and quantum physics. Many of the motivating conjectures come from physics, and their mathematical solutions would be of interest to theoretical physicists. A second part of the project concerns the topological characteristics of biopolymers like DNA and proteins. This can be important from a pharmaceutical perspective, as some drugs can be designed to target topological characteristics which affect specific biological functions. Besides its research goals, the project has a strong educational component. Many of the proposed problems are intended for research with undergraduate students. Through her research, teaching and other outreach activities, the PI intends to expand the reach of mathematics, for example to historically under-represented groups and to other audiences not usually exposed to cutting edge mathematics. This project will explore the extent to which the Kauffman skein algebra and its generalizations can serve as intermediaries between quantum topology and hyperbolic geometry. The PI will study the representation theory of the Kauffman skein algebra, paying particular attention to the representation coming from the Witten-Reshetikhin-Turaev theory. The long-term, overarching goal is to construct and classify all representations of the Kauffman skein algebra, a goal which this project will advance. The project considers the algebraic structure of the Kauffman skein algebra and of its generalizations (e.g., ones that allow arcs on the surface). In addition, the project includes problems investigating which types of topologically complex structures, like knots, links, and non-planar graphs, are possible in biopolymers like DNA and proteins.