Scattered Factor Universality -- The Power of the Remainder

• URL: http://arxiv.org/abs/2104.09063v1
• Date: Mon, 19 Apr 2021 05:45:44 GMT
• Title: Scattered Factor Universality -- The Power of the Remainder
• Abstract summary: Scattered factor (circular) was firstly introduced by Barker et al. in 2020. We prove two problems, namely a generalisation of one of their main theorems to arbitrary alphabets and a slight modification of another theorem.
• Score: 1.8065361710947976
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Scattered factor (circular) universality was firstly introduced by Barker et al. in 2020. A word $w$ is called $k$-universal for some natural number $k$, if every word of length $k$ of $w$'s alphabet occurs as a scattered factor in $w$; it is called circular $k$-universal if a conjugate of $w$ is $k$-universal. Here, a word $u=u_1\cdots u_n$ is called a scattered factor of $w$ if $u$ is obtained from $w$ by deleting parts of $w$, i.e. there exists (possibly empty) words $v_1,\dots,v_{n+1}$ with $w=v_1u_1v_2\cdots v_nu_nv_{n+1}$. In this work, we prove two problems, left open in the aforementioned paper, namely a generalisation of one of their main theorems to arbitrary alphabets and a slight modification of another theorem such that we characterise the circular universality by the universality. On the way, we present deep insights into the behaviour of the remainder of the so called arch factorisation by Hebrard when repetitions of words are considered.

Related papers

• $R$-equivalence on Cubic Surfaces I: Existing Cases with Non-Trivial Universal Equivalence [2.809000787228893]
  We consider all surfaces $V$ currently known to have non-trivial $R$-equivalence.<n>By devising new methods to study $R$-equivalence, we prove that for 2-adic surfaces with all-Eckardt reductions, $R$-equivalence is trivial or of exponent 2.
  arXiv  Detail & Related papers  (2026-03-19T17:57:38Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Non-representable quantum measures [55.2480439325792]
  Grade-$d$ measures on a $sigma$-algebra $mathcalAsubseteq 2X$ over a set $X$ are generalizations of measures satisfying one of a hierarchy of weak additivity-type conditions.<n>Every signed polymeasure $lambda$ on $(X,mathcalA)d$ produces a grade-$d$ measure as its diagonal $widetildelambda(A):=lambda(A,cdots,A)$.
  arXiv  Detail & Related papers  (2025-08-20T00:47:24Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
  Universal hash functions map the output of a source to random strings over a finite alphabet. We show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy.
  arXiv  Detail & Related papers  (2024-10-21T19:37:35Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Some new infinite families of non-$p$-rational real quadratic fields [0.0]
  We give a simple methodology for constructing an infinite family of simultaneously non-$p_j$-rational real fields, unramified above any of the $p_j$. One feature of these techniques is that they may be used to yield fields $K=mathbbQ(sqrtD)$ for which a $p$-power cyclic component of the torsion group of the Galois groups of the maximal abelian pro-$p$-extension of $K$ unramified outside primes above $p$, is of size $pa
  arXiv  Detail & Related papers  (2024-06-20T18:00:51Z)
• Almost-idempotent quantum channels and approximate $C^*$-algebras [0.03922370499388702]
  We prove that any finite-dimensional $varepsilon$-$C*$ algebra $A$ is $O(varepsilon)$-isomorphic to some genuine $C*$ algebra $B$. When $A$ comes from a finite-dimensional $eta$-idempotent UCP map $Phi$, the $O(eta)$-isomorphism and its inverse can be realized by UCP maps.
  arXiv  Detail & Related papers  (2024-05-03T18:59:50Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence [1.5935205681539144]
  In 1991 H'ebrard introduced a factorization of words that turned out to be a powerful tool for the investigation of a word's scattered factors. Based on this, first Karandikar and Schnoebelen introduced the notion of $k$-richness and later on Barker et al. the notion of $k$-universality. In 2022 Fleischmann et al. presented a generalization of the arch factorization by intersecting the arch factorization of a word and its reverse.
  arXiv  Detail & Related papers  (2023-06-25T10:16:49Z)
• Constructions of $k$-uniform states in heterogeneous systems [65.63939256159891]
  We present two general methods to construct $k$-uniform states in the heterogeneous systems for general $k$. We can produce many new $k$-uniform states such that the local dimension of each subsystem can be a prime power.
  arXiv  Detail & Related papers  (2023-05-22T06:58:16Z)
• m-Nearly k-Universal Words -- Investigating Simon Congruence [1.3229510087215552]
  Two words $u$ and $v$ are called Simon congruent if they have the same set of scattered factors. We show some results if in addition $w$ is $(k-1)$-universal as well as some further insights for different $m$.
  arXiv  Detail & Related papers  (2022-02-16T10:45:10Z)
• Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
  A set of $k$ orthonormal bases of $mathbb Cd$ is called mutually unbiased $|langle e,frangle |2 = 1/d$ whenever $e$ and $f$ are basis vectors in distinct bases. We exploit this symmetry (analytically) to reduce the size of the semidefinite programs making them tractable.
  arXiv  Detail & Related papers  (2021-11-10T14:14:53Z)
• Gray Cycles of Maximum Length Related to k-Character Substitutions [0.0]
  Given a word binary relation $tau$ we define a $tau$-Gray cycle over a finite language $X$ to be a permutation $left(w_[i]right)_0le ile |X|-1$ of $X$. We compute the bound $lambda(n)$ for all cases of the alphabet cardinality and the argument $n$.
  arXiv  Detail & Related papers  (2021-08-31T07:49:15Z)
• A Note on Rough Set Algebra and Core Regular Double Stone Algebras [0.0]
  In our Main Theorem we show $R_theta$ with $|theta_u| > 1 forall u in U$ to be isomorphic to $TP_E$ and $C_3E$, and that the three CRDSA's are complete and atomic. In our Main Corollary we show explicitly how we can embed such $R_theta$ in $TP_U$, $C_3U$, respectively, $phicirc alpha_r:R_thetahookright
  arXiv  Detail & Related papers  (2021-01-07T00:32:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.