Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T10:00:08.153Z Has data issue: false hasContentIssue false

On possible growths of arithmetical complexity

Published online by Cambridge University Press:  18 October 2006

Anna E. Frid*
Affiliation:
Sobolev Institute of Mathematics SB RAS, Koptyug av., 4, 630090 Novosibirsk, Russia; frid@math.nsc.ru
Get access

Abstract

The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More precisely, for each sequence u of subword complexity ƒu(n) and for each prime p ≥ 3 we build a Toeplitz word on the same alphabet whose arithmetical complexity is $a(n)=\Theta(n f_u(\lceil \log_p n \rceil))$ .

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable