skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The DOI auto-population feature in the Public Access Repository (PAR) will be unavailable from 4:00 PM ET on Tuesday, July 8 until 4:00 PM ET on Wednesday, July 9 due to scheduled maintenance. We apologize for the inconvenience caused.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Inhomogeneous Diophantine approximation for generic homogeneous functions
This paper is a sequel to [Monatsh. Math. 194 (2021) 523–554] in which results of that paper are generalized so that they hold in the setting of inhomogeneous Diophantine approximation. Given any integers [Formula: see text] and [Formula: see text], any [Formula: see text], and any homogeneous function [Formula: see text] that satisfies a certain nonsingularity assumption, we obtain a biconditional criterion on the approximating function [Formula: see text] for a generic element [Formula: see text] in the [Formula: see text]-orbit of [Formula: see text] to be (respectively, not to be) [Formula: see text]-approximable at [Formula: see text]: that is, for there to exist infinitely many (respectively, only finitely many) [Formula: see text] such that [Formula: see text] for each [Formula: see text]. In this setting, we also obtain a sufficient condition for uniform approximation. We also consider some examples of [Formula: see text] that do not satisfy our nonsingularity assumptions and prove similar results for these examples. Moreover, one can replace [Formula: see text] above by any closed subgroup of [Formula: see text] that satisfies certain integrability axioms (being of Siegel and Rogers type) introduced by the authors in the aforementioned previous paper.  more » « less
Award ID(s):
2155111
PAR ID:
10426091
Author(s) / Creator(s):
;
Date Published:
Journal Name:
International Journal of Number Theory
Volume:
19
Issue:
06
ISSN:
1793-0421
Page Range / eLocation ID:
1269 to 1293
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Mathematics of Operations Research)
    We consider the following general network design problem. The input is an asymmetric metric (V, c), root [Formula: see text], monotone submodular function [Formula: see text], and budget B. The goal is to find an r-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time [Formula: see text]-approximation algorithm for this problem, in which [Formula: see text] is the number of vertices in an optimal solution. As a consequence, we obtain an [Formula: see text]-approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved [Formula: see text]-approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio but improves significantly on the running time. For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are the best possible (up to constant factors). 
    more » « less
  2. ; ; (, Mathematics of Operations Research)
    We study optimal design problems in which the goal is to choose a set of linear measurements to obtain the most accurate estimate of an unknown vector. We study the [Formula: see text]-optimal design variant where the objective is to minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. We introduce the proportional volume sampling algorithm to obtain nearly optimal bounds in the asymptotic regime when the number [Formula: see text] of measurements made is significantly larger than the dimension [Formula: see text] and obtain the first approximation algorithms whose approximation factor does not degrade with the number of possible measurements when [Formula: see text] is small. The algorithm also gives approximation guarantees for other optimal design objectives such as [Formula: see text]-optimality and the generalized ratio objective, matching or improving the previously best-known results. We further show that bounds similar to ours cannot be obtained for [Formula: see text]-optimal design and that [Formula: see text]-optimal design is NP-hard to approximate within a fixed constant when [Formula: see text]. 
    more » « less
  3. ; ; ; (, Mathematics of Operations Research)
    We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SampleGreedy, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-extendible system using [Formula: see text] evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present Sample-Streaming, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and [Formula: see text] evaluation and feasibility queries per element, and m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks. 
    more » « less
  4. ; (, Journal of Algebra and Its Applications)
    Let [Formula: see text] be a residually finite dimensional algebra (not necessarily associative) over a field [Formula: see text]. Suppose first that [Formula: see text] is algebraically closed. We show that if [Formula: see text] satisfies a homogeneous almost identity [Formula: see text], then [Formula: see text] has an ideal of finite codimension satisfying the identity [Formula: see text]. Using well known results of Zelmanov, we conclude that, if a residually finite dimensional Lie algebra [Formula: see text] over [Formula: see text] is almost [Formula: see text]-Engel, then [Formula: see text] has a nilpotent (respectively, locally nilpotent) ideal of finite codimension if char [Formula: see text] (respectively, char [Formula: see text]). Next, suppose that [Formula: see text] is finite (so [Formula: see text] is residually finite). We prove that, if [Formula: see text] satisfies a homogeneous probabilistic identity [Formula: see text], then [Formula: see text] is a coset identity of [Formula: see text]. Moreover, if [Formula: see text] is multilinear, then [Formula: see text] is an identity of some finite index ideal of [Formula: see text]. Along the way we show that if [Formula: see text] has degree [Formula: see text], and [Formula: see text] is a finite [Formula: see text]-algebra such that the probability that [Formula: see text] (where [Formula: see text] are randomly chosen) is at least [Formula: see text], then [Formula: see text] is an identity of [Formula: see text]. This solves a ring-theoretic analogue of a (still open) group-theoretic problem posed by Dixon, 
    more » « less
  5. ; ; ; ; ; ; (, Journal of Mathematical Logic)
    We give examples of (i) a simple theory with a formula (with parameters) which does not fork over [Formula: see text] but has [Formula: see text]-measure 0 for every automorphism invariant Keisler measure [Formula: see text] and (ii) a definable group [Formula: see text] in a simple theory such that [Formula: see text] is not definably amenable, i.e. there is no translation invariant Keisler measure on [Formula: see text]. We also discuss paradoxical decompositions both in the setting of discrete groups and of definable groups, and prove some positive results about small theories, including the definable amenability of definable groups. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email