An official website of the United States government
Abstract A subsetSof an integral domainRis called a semidomain provided that the pairs and are semigroups with identities. The study of factorizations in integral domains was initiated by Anderson, Anderson, and Zafrullah in 1990, and this area has been systematically investigated since then. In this paper, we study the divisibility and arithmetic of factorizations in the more general context of semidomains. We are specially concerned with the ascent of the most standard divisibility and factorization properties from a semidomain to its semidomain of (Laurent) polynomials. As in the case of integral domains, here we prove that the properties of satisfying the ascending chain condition on principal ideals, having bounded factorizations, and having finite factorizations ascend in the class of semidomains. We also consider the ascent of the property of being atomic and that of having unique factorization (none of them ascends in general). Throughout the paper, we provide several examples aiming to shed some light upon the arithmetic of factorizations of semidomains.
more »
« less
On the Subatomicity of Polynomial Semidomains
A semidomain is an additive submonoid of an integral domain that is closed under multiplication and contains the identity element. Although factorizations and divisibility in atomic domains have been systematically investigated for more than 30 years, the same aspects in the more general context of atomic semidomains have been considered just recently. Here we study subatomicity in the context of semidomains; that is, we study semidomains satisfying divisibility properties weaker than atomicity. We mostly focus on the Furstenberg property, which is due to P. Clark and motivated by the work of H. Furstenberg on the infinitude of primes, and the almost atomic and quasi-atomic properties, introduced by J. G. Boynton and J. Coykendall in the context of divisibility in integral domains. We investigate these three properties in the context of semidomains, paying special attention to whether they ascend from a semidomain to its polynomial and Laurent polynomial extensions.
more »
« less
- Award ID(s):
- 2213323
- PAR ID:
- 10577640
- Editor(s):
- Chabert, JL; Fontana, M; Frisch, S; Glaz, S; Johnson, K
- Publisher / Repository:
- Springer, Cham
- Date Published:
- ISBN:
- 978-3-031-28846-3
- Page Range / eLocation ID:
- 197–212
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the natural problem of Triplet Reconstruction (also known as Rooted Triplets Consistency or Triplet Clustering), originally motivated by applications in computational biology and relational databases (Aho, Sagiv, Szymanski, and Ullman, 1981) [2]: given n datapoints, we want to embed them onto the n leaves of a rooted binary tree (also known as a hierarchical clustering, or ultrametric embedding) such that a given set of m triplet constraints is satisfied. A triplet constraint i j · k for points i, j, k indicates that 'i, j are more closely related to each other than to k,' (in terms of distances d(i, j) ≤ d(i, k) and d(i, j) ≤ d(j, k)) and we say that a tree satisfies the triplet i j · k if the distance in the tree between i, j is smaller than the distance between i, k (or j, k). Among all possible trees with n leaves, can we efficiently find one that satisfies a large fraction of the m given triplets? Aho et al. (1981) [2] studied the decision version and gave an elegant polynomial-time algorithm that determines whether or not there exists a tree that satisfies all of the m constraints. Moreover, it is straightforward to see that a random binary tree achieves a constant 13-approximation, since there are only 3 distinct triplets i j|k, i k| j, j k · i (each will be satisfied w.p. 13). Unfortunately, despite more than four decades of research by various communities, there is no better approximation algorithm for this basic Triplet Reconstruction problem.Our main theorem-which captures Triplet Reconstruction as a special case-is a general hardness of approximation result about Constraint Satisfaction Problems (CSPs) over infinite domains (CSPs where instead of boolean values {0,1} or a fixed-size domain, the variables can be mapped to any of the n leaves of a tree). Specifically, we prove that assuming the Unique Games Conjecture [57], Triplet Reconstruction and more generally, every Constraint Satisfaction Problem (CSP) over hierarchies is approximation resistant, i.e., there is no polynomial-time algorithm that does asymptotically better than a biased random assignment.Our result settles the approximability not only for Triplet Reconstruction, but for many interesting problems that have been studied by various scientific communities such as the popular Quartet Reconstruction and Subtree/Supertree Aggregation Problems. More broadly, our result significantly extends the list of approximation resistant predicates by pointing to a large new family of hard problems over hierarchies. Our main theorem is a generalization of Guruswami, Håstad, Manokaran, Raghavendra, and Charikar (2011) [36], who showed that ordering CSPs (CSPs over permutations of n elements, e.g., Max Acyclic Subgraph, Betweenness, Non-Betweenness) are approximation resistant. The main challenge in our analyses stems from the fact that trees have topology (in contrast to permutations and ordering CSPs) and it is the tree topology that determines whether a given constraint on the variables is satisfied or not. As a byproduct, we also present some of the first CSPs where their approximation resistance is proved against biased random assignments, instead of uniformly random assignments.more » « less
-
Summary form only given. We are developing a scanning tunneling microscope that is portable and optimized for scanning frequency comb microscopy (SFCM) as one part of our effort to complete a prototype for the carrier profiling of semiconductors by SFCM. Conventional integral or integral plus proportion feedback control of the tunneling current in a scanning tunneling microscope (STM) is satisfactory once tunneling has been established but may cause tip-crash by integral windup during coarse approach. In tip-sample contact images with atomic-resolution may be obtained but the microwave frequency comb ceases because there is no optical rectification and scanning tunneling spectroscopy also fails. We are studying a new control algorithm based on approximating the tunneling current as a polynomial in the bias voltage where the coefficients in this polynomial are not required. It is noted that hanges in the apparatus, as well as the algorithms used for feedback control in the STM, are required to optimize this instrument for measuring the microwave frequency comb.more » « less
-
We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search ([Formula: see text]; i.e., the intersection of polynomial local search ([Formula: see text]) and polynomial parity arguments on directed graphs ([Formula: see text])). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to [Formula: see text]. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1].more » « less
-
Trinucleotide repeat (TNR) sequences widely exist in nature and their overgrowth is associated with two dozen neurodegenerative diseases in humans. These sequences have a unique helical flexibility, which affects their biophysical properties. A number of biophysical properties of these sequences have been studied in the past except their surface-tethered monolayers. To address the effect of sequence context and the associated helical flexibility on TNR monolayers, disease-relevant TNRs from three flexibility groups were surface-assembled on gold surfaces. The properties of the TNR films were studied, including charge transfer resistance ( R ct ) by electrochemical impedance spectroscopy (EIS), surface density by chronocoulometry (CC), surface topography by atomic force microscopy (AFM), and electrical conductivity by conducting atomic force microscopy (C-AFM). We found that the TNR film properties are characteristically sequence dependent rather than being dependent on their flexibility rank reported in the literature. The characteristic properties of TNR films studied here may be used for engineering label-free biosensors to detect neurological disorders and build DNA bioelectronics.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Proceeding:
- The DOI is not currently available.
