PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotic completions of preordered semirings

Péter Vrana

arXiv:2609.31021v1math.RAcs.ITmath.COmath.IT

TL;DR

Many applications use geometric sequences, yet other relevant sequences need not be geometric. The paper completes preordered semirings so approximately geometric sequences become equivalent to geometric ones, extends asymptotic-preorder characterizations, and applies the framework to composite Markov hypothesis testing.

  • Problem

    The framework centers on geometric sequences, but relevant sequences arising in applications need not be geometric.

    Source: §1 · p. 2

  • Method

    The paper constructs an asymptotic completion in which approximately geometric sequences become equivalent to geometric ones and extends asymptotic-preorder characterizations to that completion.

    Source: §1.1 · p. 3

  • Results

    The completion extends spectrum characterizations to approximately geometric sequences and yields an optimization over Rényi divergence rates for the strong converse exponent with composite Markov hypotheses.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    For the stated majorization semirings, Rényi divergence rates give necessary and sufficient asymptotic-preorder conditions and express the strong converse exponent.

    Source: §1.1 · p. 4

    The paper does not characterize triples (A, x, y) for which a_n = x^T A^n y is approximately geometric.

    Source: §5.2 · p. 33

Abstract

from arXiv · show

The study of preordered semirings is motivated by applications in computer science, graph theory, and information theory, and provides tools for understanding the asymptotic preorder, which compares large powers of a pair of elements. This paper studies sequences which behave approximately as sequences of powers, but are not necessarily equivalent to geometric sequences. Our main result is that preordered semirings admit completions where such sequences, that we call approximately geometric, become equivalent to geometric sequences, and that existing characterizations of the asymptotic preorder extend to the completion. We provide several classes of examples of approximately geometric sequences in the semiring of tensors, and in the semiring of graphs. As a concrete application, we determine the strong converse exponent for binary hypothesis testing with composite Markov hypotheses.

1 Introduction

The introduction develops a framework for comparing sequences in preordered semirings, from the asymptotic preorder on geometric sequences to approximately geometric sequences and their completions. It reviews characterizations via monotone homomorphisms and derivations, and introduces types and entropy estimates for applications to tensors and graphs.

1 Introduction

  • The asymptotic preorder compares powers up to a sublinear power-universal factor, and the paper generalizes geometric-sequence methods to intermediate sequences arising in applications.The motivation includes tensor sequences that need not be Kronecker-power families, correlated samples or channel uses, and non-geometric intermediate sequences in complexity and graph theory.Source: §1 · pp. 1–2

1.1 Results

  • Approximately geometric sequences are closed under elementwise multiplication, binomial convolution, and asymptotic equivalence, with distributivity holding up to asymptotic equivalence.Canonical extensions of suitable test homomorphisms characterize the order on the completion; regular upper and lower functionals also extend under Strassen’s conditions.Source: §1.1 · p. 3
  • Every semiring can be almost embedded into an asymptotically complete preordered semiring, with an essentially unique minimal completion satisfying a universal property.Its elements are asymptotic-equivalence classes of approximately geometric sequences, with induced operations and preorder.Source: §1.1 · p. 3
  • The framework covers non-integer-power sequences, suitable linear recursions, tensor sequences, graph sequences, and correlated composite hypothesis-testing sequences.Examples include primitive-matrix recursions, tensors with Kronecker scaling, graph sequences from type classes and spectrum-distance limits, and Markov-chain tuples yielding a single-letter strong-converse exponent.Source: §1.1 · pp. 3–4
  • For majorization semirings, asymptotic-preorder characterizations extend to approximately geometric sequences through Rényi divergence rates, including a strong-converse exponent for composite correlated hypotheses.Tuples of Markov chains with strictly positive transition probabilities are approximately geometric, giving single-letter expressions for the divergence rates and exponent.Source: §1.1 · p. 4

1.2 Preliminaries

  • The asymptotic preorder is defined for semirings of polynomial growth by comparing a^n with u^k_n b^n for a sublinear sequence k_n.Here u is a power-universal element, meaning 1 ≤ u and every nonzero ordered pair x ≤ y satisfies y ≤ u^k x for some k.Source: §1.2 · pp. 5–6
  • Duality theorems characterize asymptotic inequalities through monotone homomorphisms into test objects, with Fritz’s generalizations extending Strassen’s result.The section also describes a Fritz criterion that, under additional norm conditions, uses monotone homomorphisms and monotone derivations.Source: §1.2 · pp. 6–7
  • Types partition finite-alphabet sequence sets into type classes, whose cardinalities can be estimated using Shannon entropy.The section introduces types and type classes for applications to tensors and graphs, and notes that entropy continuity bounds will be used.Source: §1.2 · pp. 7–8

2 Approximately geometric sequences

The section develops operations and asymptotic equivalence for sequences over polynomial-growth preordered semirings, and characterizes approximately geometric sequences, including a convergence criterion for positive real sequences. It also examines how approximate geometricity depends on the preorder and shows that an asymptotically approximately geometric sequence has an asymptotically equivalent substitute that is approximately geometric for the original preorder.

2 Approximately geometric sequences

  • For arbitrary sequences, the defined sum and elementwise product do not generally satisfy distributivity.The failure motivates restricting attention to approximately geometric sequences, where distributivity holds approximately under the stated condition.Source: §2 · pp. 9–10
  • Approximately geometric sequences are nonzero sequences satisfying equivalent conditions that sandwich their terms between geometric sequences with rescaled indices and asymptotically close bounds, or are asymptotically equivalent to G(0).The paper notes that one condition is convenient for abstract constructions, while the sandwiching conditions are intuitive and practical to verify.Source: §2 · p. 10
  • In R≥0, a nonzero sequence is approximately geometric exactly when ln(a_n)/n converges, equivalently when the nth root of a_n converges to a nonzero number.Source: §2 · p. 14
  • Approximately geometric sequences are preserved by asymptotic equivalence, ⊕, ⊙, and monotone semiring homomorphisms; when c is approximately geometric, multiplication by c makes distributivity hold up to asymptotic equivalence.Source: §2 · p. 14
  • The termwise product a ⊙ b of approximately geometric sequences is also approximately geometric.Source: §2 · p. 16
  • The passage also establishes distributivity up to equivalence for (a ⊕ b) ⊙ c and approximate geometricity of ϕ(a) under the stated conditions.Source: §2 · pp. 16–17
  • A sequence approximately geometric for the asymptotic preorder has a substitute that is approximately geometric for ≤ and asymptotically equivalent to it for ≲.The proof constructs a sequence shown to satisfy both properties.Source: §2 · pp. 17, 19

3 Asymptotic completeness

Asymptotic completeness requires every approximately geometric sequence to be equivalent to a geometric one. The paper constructs a completion from equivalence classes of these sequences, with a universal property and extensions of monotone homomorphisms.

3 Asymptotic completeness

  • An asymptotic completion makes every approximately geometric sequence equivalent to a geometric sequence; its closed partial order supports uniqueness.Any monotone homomorphism into an asymptotically complete, closed partially ordered semiring extends uniquely through the completion.Source: §3 · pp. 20–21
  • N is not asymptotically complete: 2^floor(n/2) is approximately geometric but is not equivalent to G(s) for s ≥ 2.Source: §3 · p. 20
  • R≥0, TRop, and D are given as asymptotically complete semirings.Source: §3 · p. 20
  • The canonical map may be non-injective, but it identifies only elements that are asymptotically equivalent.Source: §3 · p. 21
  • The completion is essentially unique, and its canonical map reflects the original asymptotic preorder.Source: §3 · pp. 21–22
  • The completion consists of asymptotic-equivalence classes of approximately geometric sequences, with induced operations and preorder and canonical map s ↦ [G(s)].Source: §3 · p. 22
  • Monotone homomorphisms extend by [a] ↦ [ϕ(a)], compatibly with the canonical maps.Source: §3 · p. 22

4 Spectrum

The section extends spectrum-based characterizations of asymptotic order to the asymptotic completion. Under the stated hypotheses, homomorphisms into suitable test semirings characterize order there, while selected characterizations and functionals extend to the completion.

4 Spectrum

  • Composition with the completion map gives a bijection on homomorphisms into asymptotically complete test semirings, preserving degenerate homomorphisms and associated derivations.The passage also states that interchangeable derivations remain interchangeable under this correspondence.Source: §4 · pp. 24–25
  • When asymptotic order is characterized by homomorphisms into asymptotically closed, partially ordered semirings, the corresponding homomorphisms characterize order on the completion.For approximately geometric sequences, this is the corresponding extension of the asymptotic preorder characterization.Source: §4 · pp. 24–25
  • For a Strassen preorder, a ≤ b exactly when every monotone homomorphism S → R≥0 preserves the inequality.This characterization applies to elements a and b of S.Source: §4 · p. 26
  • For polynomial-growth semirings with 1 ≥ 0, order is characterized by homomorphisms into both R≥0 and TR.The criterion tests all homomorphisms in both stated classes.Source: §4 · p. 26
  • Under the stated surjective norm condition, order is characterized by homomorphisms into R≥0, Rop≥0, TR, and TRop, plus monotone norm-derivations.The derivations are tested componentwise for each of the d norm components.Source: §4 · p. 26
  • Regular lower and upper functionals on a Strassen-preordered semiring each have unique regular extensions to its asymptotic completion.The extensions agree with the original functionals under the completion map.Source: §4 · pp. 26–27

5 Applications

Section 5 applies asymptotic completion methods and approximate geometricity across linear recurrences, tensors, graphs, and majorization. It extends asymptotic characterizations to approximately geometric sequences and applies relative submajorization to composite hypothesis testing, including finite-state Markov hypotheses.

5.1 Powers with real exponents

  • Real powers in an asymptotically complete semiring are defined by geometric equivalence to the sequence of floor-indexed integer powers, and monotone homomorphisms preserve them.For invertible elements the definition extends to negative exponents; in the nonnegative reals it agrees with ordinary exponentiation.Source: §5.1 · pp. 30–31
  • In a closed asymptotically complete semiring, a ≤ b holds exactly when a ≤ u^εb for every ε > 0, and approximate geometricity is characterized by arbitrarily small-u root-power bounds.The latter criterion requires, for every ε > 0, some positive integer m such that the sequence is asymptotically bounded by geometric sequences generated from u^εa^(1/m).Source: §5.1 · p. 32

5.2 Linear recurrences

  • A sufficient finite-window entrywise condition on a matrix recurrence ensures its sequence is approximately geometric, though the paper gives no characterization of all such recurrences.The sufficient condition concerns comparisons for initial terms with indices below 2m; Fibonacci numbers are approximately geometric in N but not in N=.Source: §5.2 · p. 33
  • For primitive matrices over a polynomial-growth preordered semiring with 0 ≤ 1, all sequences xᵀAⁿy are approximately geometric and asymptotically equivalent, defining a common growth-rate element ρ(A).For nonnegative real matrices ρ(A) is the spectral radius; for tropical reals it is the maximum cycle geometric mean.Source: §5.2 · pp. 34–35
  • Monotone homomorphisms preserve ρ(A) for primitive matrices, allowing its computation through the spectral radius or maximum cycle geometric mean in the target semiring.The homomorphism must map into a polynomial-growth preordered semiring with 0 ≤ 1.Source: §5.2 · p. 35

5.3 Tensors

  • The tensor semiring, formed from tensor direct sums and products under restriction, is not asymptotically complete because flattening ranks are N-valued and their images omit (1, ∞).More generally, every element of the tensor asymptotic spectrum has a well-ordered image, which also cannot contain (1, ∞).Source: §5.3 · pp. 35–36
  • Rectangular matrix multiplication motivates the framework because ⌈n^p⌉ is not exactly geometric for noninteger p, although geometric subsequences of n suffice.The associated rectangular multiplication exponent is defined through an O(n^ω(p)+ϵ) arithmetic-operation bound.Source: §5.3 · p. 36
  • Every approximately geometric tensor sequence is almost exponential, and the associated limit is a regular upper functional.The proposition also identifies this limit with the limit of the sequence’s asymptotic ranks.Source: §5.3 · p. 37
  • Every approximately geometric tensor sequence also has the Kronecker scaling property.This connects the paper’s sequence condition to a property studied for tensor sequences behaving like Kronecker powers.Source: §5.3 · p. 38
  • A large class of block-tensor sequences, including the balanced tripartitioning tensors, is proved approximately geometric using a strengthened Steinitz balancing technique.Theorem 5.19 gives a criterion based on support distributions being uniquely determined by their three marginals.Source: §5.3 · pp. 38, 42
  • The balanced tripartitioning tensors arise as t[P] for a three-term tensor and the uniform distribution on its support.The example takes the support to be the three basis terms with one index equal to 1 and the others 0.Source: §5.3 · p. 43
  • With q = 6 and β = 0.048, the tensor application gives ω ≤ 2.39.Source: §5.3 · p. 44

5.4 Graphs

  • For graph type classes, sequences with m_n/n → μ and P_n → P are approximately geometric, with equivalence class represented by G[P]^μ.The result allows arbitrary converging types and linearly growing powers, rather than only fixed rational distributions and arithmetic power sequences.Source: §5.4 · pp. 45, 47, 49
  • A sequence of nonempty graphs is Cauchy in asymptotic spectrum distance exactly when its graph-power sequence is approximately geometric, yielding a geometric-sequence representative for its limit.The represented elements form a proper subsemiring; for each spectrum element, the corresponding value lies in {1} ∪ [2, ∞), although spectrum images are {0} ∪ [1, ∞).Source: §5.4 · pp. 50–51

5.5 Majorization semirings

  • Measure families modulo bijective equivalence form a preordered semiring under majorization, with columnwise direct sum and Kronecker product; probability-measure elements represent statistical experiments.The preorder expresses relative informativeness, while multiplication represents independent experiments with the same unknown parameter.Source: §5.5 · pp. 51–52
  • Under equal-support conditions, an element is power universal exactly when every measure has norm 1 and the measures are pairwise distinct.Source: §5.5 · p. 52
  • Monotone homomorphisms and derivations for majorization semirings admit a unified description using multivariate Rényi divergences, with derivations at norm maps generated by pairwise relative entropies.The divergence quantities and their pointwise limits recover the same functionals up to logarithm and rescaling.Source: §5.5 · p. 52
  • For approximately geometric families of probability distributions, Proposition 5.31 establishes multivariate Rényi divergence rates and extends majorization-power criteria using sublinear power-universal slack.The passage states that the rates exist and gives an equivalent condition involving U^⊗k_n ⊗ P_n ≥ Q_n for a sublinear sequence k_n.Source: §5.5 · pp. 52–53
  • Relative submajorization characterizes achievable randomized-test errors: a bound by constant vectors is equivalent to a test with type-I error at most 1−a and type-II error at most b.Conversely, any test yields the corresponding preorder bound using its type-I and type-II error probabilities.Source: §5.5 · pp. 53–54
  • For approximately geometric sequences in the relative-submajorization semiring, Proposition 5.32 establishes the relevant divergence rates and characterizes the optimal type-I strong-converse exponent as a function of type-II decay rate.The stated scope includes all α in [1, ∞] and indices i and j from the two composite hypotheses.Source: §5.5 · p. 54
  • For composite finite-state Markov hypotheses with full-support initial distributions and strictly positive transitions, Theorem 5.33 gives the type-I strong-converse exponent under type-II error decay 2^-nr+o(n) as a spectral-radius expression.The proof represents the joint distributions through powers of a transition matrix over the relative-submajorization semiring.Source: §5.5 · p. 55
Loading 2609.31021v1…