Growth rates of the power-free languages

edit · history · discussion · files · short url · combinatorics

Numbers

$k$

$\beta$

$\gamma$

$7/3$:

comment: This language has polynomial growth, so $\gamma=1$ [1].

$(7/3)^+$:

1.2206383 +/- 0.00000655 †

$17/7$:

1.22223075 +/- 0.0000073 †

$(17/7)^+$:

1.2287143 +/- 0.00000625 †

$5/2$:

1.2294944 +/- 0.00000735 †

$(5/2)^+$:

1.3662991 +/- 0.00000205

$18/7$:

1.3669574 +/- 0.00000275

$(18/7)^+$:

1.3692807 +/- 0.00000255

$13/5$:

1.3693937 +/- 0.00000255

$(13/5)^+$:

1.37608485 +/- 0.0000028

$8/3$:

1.37626765 +/- 0.0000028

$(8/3)^+$:

1.4508594 +/- 0.00000175

$14/5$:

1.4522664 +/- 0.00000165

$(14/5)^+$:

1.4552336 +/- 0.00000225

$17/6$:

1.4552574 +/- 0.00000225

$(17/6)^+$:

1.4567794 +/- 0.00000215

$3$:

1.457575218462025 +/- 0.000002068462025

$3^+$:

1.7951255 +/- 0.00000095

$13/4$:

1.7957607 +/- 0.00000095

$(13/4)^+$:

1.79728795 +/- 0.0000009

$10/3$:

1.79730965 +/- 0.0000009

$(10/3)^+$:

1.8029869 +/- 0.00000085

$7/2$:

1.8032409 +/- 0.00000005

$(7/2)^+$:

1.8172665 +/- 0.00000005

$11/3$:

1.8174176 +/- 0.00000005

$(11/3)^+$:

1.820496 +/- 0.00000005

$4$:

1.8211 +/- 0.00000005

$4^+$:

1.9208015 +/- 0.00000005

$9/2$:

1.9214442 +/- 0.00000005

$(9/2)^+$:

1.9241348 +/- 0.00000005

$5$:

1.9244437 +/- 0.00000005

$5^+$:

1.9646285 +/- 0.00000005

$6$:

1.9653118 +/- 0.00000005

$6^+$:

1.9832942 +/- 0.00000005

$7$:

1.9834409 +/- 0.00000005

$7^+$:

1.9918972 +/- 0.00000005

$8$:

1.991931 +/- 0.00000005

$8^+$:

1.9960151 +/- 0.00000005

$9$:

1.9960232 +/- 0.00000005

$9^+$:

1.9980255 +/- 0.00000005

$2$:

1.30176076325 +/- 0.00000111325

$2^+$:

2.605879 +/- 0.00000015

$3$:

2.7015615 +/- 0.00000015

$3^+$:

2.9119241 +/- 0.00000015

$4$:

2.9172846 +/- 0.00000005

$4^+$:

2.9737546 +/- 0.00000005

$2$:

2.621508 +/- 0.00000005

$2^+$:

3.7284944 +/- 0.00000005

$3$:

3.7789513 +/- 0.00000005

$3^+$:

3.9487867 +/- 0.00000005

$4$:

3.9507588 +/- 0.00000005

$4^+$:

3.9879972 +/- 0.00000005

$2$:

3.7325386 +/- 0.00000005

$2^+$:

4.7898507 +/- 0.00000005

$3$:

4.8220672 +/- 0.00000005

$3^+$:

4.9662411 +/- 0.00000005

$4$:

4.9671478 +/- 0.00000005

$4^+$:

4.9935251 +/- 0.00000005

$2$:

4.7914069 +/- 0.00000005

$2^+$:

5.8277328 +/- 0.00000005

$3$:

5.8503616 +/- 0.00000005

$3^+$:

5.97601 +/- 0.00000005

$4$:

5.9764861 +/- 0.00000005

$4^+$:

5.996117 +/- 0.00000005

$2$:

5.8284661 +/- 0.00000005

$2^+$:

6.853725 +/- 0.00000005

$3$:

6.8705878 +/- 0.00000005

$3^+$:

6.9820558 +/- 0.00000005

$4$:

6.9823298 +/- 0.00000005

$4^+$:

6.9974912 +/- 0.00000005

$2$:

6.8541173 +/- 0.00000005

$2^+$:

7.8727609 +/- 0.00000005

$3$:

7.8858522 +/- 0.00000005

$3^+$:

7.9860649 +/- 0.00000005

$4$:

7.9862337 +/- 0.00000005

$4^+$:

7.9982866 +/- 0.00000005

$2$:

7.8729902 +/- 0.00000005

$2^+$:

8.8873424 +/- 0.00000005

$3$:

8.8978188 +/- 0.00000005

$3^+$:

8.9888625 +/- 0.00000005

$4$:

8.9889721 +/- 0.00000005

$4^+$:

8.9987785 +/- 0.00000005

$2$:

8.8874856 +/- 0.00000005

$2^+$:

9.8988872 +/- 0.00000005

$3$:

9.9074705 +/- 0.00000005

$3^+$:

9.9908932 +/- 0.00000005

$4$:

9.9909674 +/- 0.00000005

$4^+$:

9.9990989 +/- 0.00000005

$2$:

9.8989813 +/- 0.00000005

$2^+$:

10.9082635 +/- 0.00000005

$3$:

10.9154294 +/- 0.00000005

$3^+$:

10.9924142 +/- 0.00000005

$4$:

10.9924662 +/- 0.00000005

$4^+$:

10.9993163 +/- 0.00000005

$2$:

10.9083279 +/- 0.00000005

$2^+$:

11.9160348 +/- 0.00000005

$3$:

11.9221106 +/- 0.00000005

$3^+$:

11.9935831 +/- 0.00000005

$4$:

11.9936207 +/- 0.00000005

$4^+$:

11.9994691 +/- 0.00000005

$2$:

11.9160804 +/- 0.00000005

$2^+$:

12.9225835 +/- 0.00000005

$3$:

12.9278022 +/- 0.00000005

$3^+$:

12.994501 +/- 0.00000005

$4$:

12.9945288 +/- 0.00000005

$4^+$:

12.9995796 +/- 0.00000005

$2$:

12.9226167 +/- 0.00000005

$2^+$:

13.9281788 +/- 0.00000005

$3$:

13.9327109 +/- 0.00000005

$3^+$:

13.995235 +/- 0.00000005

$4$:

13.995256 +/- 0.00000005

$4^+$:

13.9996615 +/- 0.00000005

$2$:

13.9282035 +/- 0.00000005

$2^+$:

14.9330157 +/- 0.00000005

$3$:

14.9369892 +/- 0.00000005

$3^+$:

14.9958311 +/- 0.00000005

$4$:

14.9958473 +/- 0.00000005

$4^+$:

14.9997234 +/- 0.00000005

Definition

The table stores $\gamma=\alpha(k,\beta)$ for the $k$-ary words whose contiguous factors all have exponent less than $\beta$, where a word's exponent is its length divided by its least period [4]; a $\beta^+$ row also allows exponent $\beta$ [1].

Parameters

$k$

— alphabet size ($k\geq2$)

$\beta$

— avoided exponent (a trailing + means that only factors of exponent strictly greater than $\beta$ are forbidden)

Formulas

(1)

$\alpha(k,\beta)=\lim_{n\to\infty} c_n^{1/n}$, where $c_n$ is the number of $k$-ary words of length $n$ in the indicated power-free language [1].

(2)

If $C(x)=\sum_{n\geq0} c_n x^n$ is the ordinary counting generating function and $\rho$ is its radius of convergence, then $\gamma=\alpha(k,\beta)=1/\rho$.

Comments

(3)

Shur's later tables for $\beta<2$ give one-sided upper bounds and extrapolated estimates [1].

References

[1]

Arseny M. Shur, Numerical values of the growth rates of power-free languages, arXiv preprint, 2010. (arXiv)

[2]

Arseny M. Shur, Two-sided bounds for the growth rates of power-free languages, Developments in Language Theory 2009, Lecture Notes in Computer Science 5583, Springer, 2009, 466-477. (doi)

[3]

Arseny M. Shur, Growth rates of complexity of power-free languages, Theoretical Computer Science 411 (2010), no. 34-36, 3209-3223. (doi)

Links

[4]

Wikipedia: Critical exponent of a word

Similar tables

Capacity of the $(d,k)$ run-length-limited constrained codes — stores logarithmic capacities of regular constrained binary languages rather than raw exponential growth rates of power-free languages

Growth rates of hyperbolic Coxeter triangle groups — stores growth rates of hyperbolic Coxeter triangle groups with respect to reflection generators rather than growth rates of formal languages

Growth rates of hyperbolic Coxeter simplex groups — stores growth rates of hyperbolic Coxeter simplex groups with respect to facet-reflection generators rather than growth rates of formal languages

Entropy constants of lattice models — stores exponential growth constants for lattice-model configuration counts rather than for formal languages

Data properties

Entries are of type: real number

How well the digits are known: assumed-bound

Table is complete: no (it holds the rounded two-sided entries with $\beta\geq2$ in Tables 1 and 2 of [1]: for binary languages, both rows of each exponent $\beta$ in Table 1 at which $\alpha(2,\beta^+)-\alpha(2,\beta)\geq0.001$, and the exponents $2$, $2^+$, $3$, $3^+$, $4$, and $4^+$ for $3\leq k\leq15$; the binary $\beta=2$ language is finite, and the binary $2^+$ language has polynomial growth)

How they were obtained:

The attached generator reproduces the rounded entries of Tables 1 and 2 in [1], specifically arXiv:1009.4415v2. Each printed lower endpoint is decreased by 0.00000005 and each table upper endpoint increased by 0.00000005. A single printed value is treated as rounded, not as an exact decimal. The polynomial-growth entry at alphabet size 2 and exponent 7/3 is exactly 1.

Two upper endpoints use the explicit upper bounds in the introductory prose of that source, not its estimates. For binary cube-free words the printed 1.4575772869240 is increased by 0.00000000000005 to 1.45757728692405. For ternary square-free words the printed 1.301761876 is increased by 0.0000000005 to 1.3017618765. Each additional margin is half a unit in the last displayed place, a conservative allowance for source rounding, not a fresh error-bound computation. The original lower endpoints 1.45757315 and 1.30175965 are retained. All other enclosures are unchanged.

All transcription arithmetic is exact rational arithmetic. Every resulting centre and radius is an exact decimal, and removing trailing zeros changes no interval endpoint. The intervals carry 6 to 9 significant digits under NumberDB's midpoint/radius measure, not 12 or 100 digits. This is not a claim that every digit of a midpoint is a digit of the growth rate.

The rigour level is conservatively assumed-bound: these enclosures rely on the published bounds and the source's nearest-decimal rounding, not a fresh execution of the upper-bound algorithm in [3] or the lower-bound method in [2]. The source cells have been checked individually. Both prose upper bounds have been checked in their named-language context. No extrapolated estimates are substituted.