Subword complexity and non-automaticity of certain completely multiplicative functions

DOI10.1016/J.AAM.2016.11.002MaRDI QIDQ730313zbMATH OpenOpenAlexFDO

Authors Yining Hu

Publication date 27 December 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.09403

zbMATH Keywords

subword complexitycompletely multiplicative functions\(k\)-automatic sequences

Mathematics Subject Classification ID

Combinatorics on words (68R15) Automata sequences (11B85) Distribution of integers with specified multiplicative constraints (11N25)

Abstract: In this article, we prove that for a completely multiplicative function $f$ from $mathbb{N}^{\ast }$ to a field $K$ such that the set ${\displaystyle }${p ;|; f(p) eq 1_K ;mbox{and }p mbox{ is prime}}${\displaystyle }$ is finite, the asymptotic subword complexity of $f$ is $Theta(n^t)$, where $t$ is the number of primes $p$ that $f(p)eq{0}_K,1_K$. This proves in particular that sequences like $((-1{)}^{v_2(n)+v_3(n)}{)}_n$ are not $k$-automatic for $kgeq2$.

Recommendations

• Multiplicative functions and \(k\)-automatic sequences
• A note on multiplicative automatic sequences. II
• On the joint subword complexity of automatic sequences
• On completely multiplicative automatic sequences
• A note on multiplicative automatic sequences

Cites work

• Automatic Dirichlet series
• Automatic Sequences
• On the base-dependence of sets of numbers recognizable by finite automata
• On the joint subword complexity of automatic sequences
• Uniform tag sequences

Cited in

(8)

• On multiplicative automatic sequences
• Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
• On completely multiplicative automatic sequences
• A note on multiplicative automatic sequences. II
• How to prove that a sequence is not automatic
• On the joint subword complexity of automatic sequences
• A note on multiplicative automatic sequences
• Subword complexity and Laurent series

This page was built for publication: Subword complexity and non-automaticity of certain completely multiplicative functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730313)