Repository navigation
Expand file tree
/
Copy pathpower-draft.html
More file actions
570 lines (570 loc) · 29.7 KB
/
Copy pathpower-draft.html
File metadata and controls
570 lines (570 loc) · 29.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<meta name="author" content="Ioannis Konstantoulas" />
<title>Digits of rational power sequences</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
/* The extra [class] is a hack that increases specificity enough to
override a similar rule in reveal.js */
ul.task-list[class]{list-style: none;}
ul.task-list li input[type="checkbox"] {
font-size: inherit;
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
</style>
<link rel="stylesheet" href="styles/texstyle.css" />
<script
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml-full.js"
type="text/javascript"></script>
</head>
<body>
<header id="title-block-header">
<h1 class="title">Digits of rational power sequences</h1>
<p class="author">Ioannis Konstantoulas</p>
<div class="abstract">
<div class="abstract-title">Abstract</div>
<p>In this note we study the digits of <span
class="math inline">\(\left(\frac{3}{2}\right)^n\xi\)</span> for
arbitrary <span class="math inline">\(\xi>0\)</span> and show that in
the dyadic decomposition of <span class="math inline">\([0,1]\)</span>
into <span class="math inline">\(2^n\)</span> intervals, at least <span
class="math inline">\(\frac{1}{2}\sqrt{n}\)</span> distinct ones contain
a limit point of the sequencce. Our methods are combinatorial and
exploit the shift-and-add interpretation of the sequence.</p>
</div>
</header>
<nav id="TOC" role="doc-toc">
<ul>
<li><a href="#introduction" id="toc-introduction"><span
class="toc-section-number">1</span> Introduction</a></li>
<li><a href="#notation-and-toolbox" id="toc-notation-and-toolbox"><span
class="toc-section-number">2</span> Notation and toolbox</a>
<ul>
<li><a href="#word-combinatorics" id="toc-word-combinatorics"><span
class="toc-section-number">2.1</span> Word combinatorics</a></li>
<li><a href="#the-digraphs-g_n" id="toc-the-digraphs-g_n"><span
class="toc-section-number">2.2</span> The digraphs <span
class="math inline">\(G_n\)</span></a></li>
</ul></li>
<li><a href="#lower-bounds-for-patterns-in-a-window"
id="toc-lower-bounds-for-patterns-in-a-window"><span
class="toc-section-number">3</span> Lower bounds for patterns in a
window</a></li>
</ul>
</nav>
<h1 data-number="1" id="introduction"><span
class="header-section-number">1</span> Introduction</h1>
<p>Let <span class="math inline">\(r_n(\xi) =
\left(\frac{3}{2}\right)^n\xi\)</span>. The main result states:</p>
<div id="main_simple" class="main">
<p><strong>Theorem 1</strong>. <em>Let <span class="math inline">\(\xi
>0\)</span>, <span class="math inline">\(N\)</span> a natural number
greater than <span class="math inline">\(5\)</span> and <span
class="math inline">\(f_n:= \{r_n(\xi)\}\)</span>. Consider the dyadic
decomposition of <span class="math inline">\([0,1]\)</span> up to depth
<span class="math inline">\(N\)</span>: <span
class="math display">\[[0,1] =
\bigcup_{i=0}^{N-1} [\frac{i}{2^{N}},\frac{i+1}{2^{N}}].\]</span> At
least <span class="math inline">\(\frac{1}{2}\sqrt{N}\)</span> intervals
in this decomposition contain a limit point of <span
class="math inline">\((f_n)\)</span>.</em></p>
</div>
<p>We deduce this theorem from a combinatorial statement about words
associated to digits of <span class="math inline">\(r_n\)</span>.</p>
<div class="defin">
<p><strong>Definition 1</strong>. For <span
class="math inline">\(l<r\)</span> let <span
class="math inline">\(w_n(l,r)\)</span> denote the block of digits of
<span class="math inline">\(r_n\xi\)</span> starting <span
class="math inline">\(|l|\)</span> places from zero and ending <span
class="math inline">\(|r|\)</span> places away; the signs of <span
class="math inline">\(l\)</span> and <span
class="math inline">\(r\)</span> indicate sides.</p>
</div>
<p>We have (suppressing the dependence on <span
class="math inline">\(\xi\)</span>):</p>
<div id="prop" class="mainc">
<p><strong>Proposition 2</strong>. <em>For any window <span
class="math inline">\(w_n(l,r)\)</span> with <span
class="math inline">\(l<r\)</span>, at least <span
class="math inline">\(\frac{1}{2}\sqrt{r-l+1}\)</span> of the <span
class="math inline">\(2^{r-l+1}\)</span> possible binary strings appear
infinitely often as <span
class="math inline">\(n\rightarrow\infty\)</span>.</em></p>
</div>
<h1 data-number="2" id="notation-and-toolbox"><span
class="header-section-number">2</span> Notation and toolbox</h1>
<p>In this section we lay down some notation and describe the auxiliary
concepts that will be used to study the sequence <span
class="math inline">\(r_n(\xi)\)</span>. We begin with definitions
related to binary words.</p>
<h2 data-number="2.1" id="word-combinatorics"><span
class="header-section-number">2.1</span> Word combinatorics</h2>
<div class="def-rn">
<p><strong>Definition 3</strong>. <em>For <span
class="math inline">\(\xi>0\)</span> define <span
class="math display">\[r_n(\xi) := \left(\frac{3}{2}\right)^n\cdot
\xi;\]</span> in any discussion where <span
class="math inline">\(\xi\)</span> is fixed, we will suppress the
dependence on <span class="math inline">\(\xi\)</span> and simply write
<span class="math inline">\(r_n\)</span>.</em></p>
</div>
<div class="def-dig">
<p><strong>Definition 4</strong>. <em>The digits in the binary expansion
of <span class="math inline">\(r_n(\xi)\)</span> will be labeled as
<span class="math display">\[r_n(\xi) = \sum_{k=m(n)}^{M(n)}
d^n_k(\xi)\,2^k.\]</span> As in the previous definition, we will
normally suppress the dependence on <span
class="math inline">\(\xi\)</span>.</em></p>
<p><em>The operation <span class="math inline">\(r_{n+1} =
(1+1/2)r_n\)</span> produces a carry through the addition <span
class="math inline">\(d^n_k+d^n_{k+1}\)</span>. This carry is denoted by
<span class="math inline">\(c^n_k\)</span>.</em></p>
</div>
<p>Using the notation we established, we see that the action of <span
class="math inline">\(\frac{3}{2}\cdot\)</span> on digits is <span
class="math display">\[\label{digit}
d^{n+1}_k= d^n_k+d^n_{k+1} + c^n_{k-1} \pmod{2}\]</span> where <span
class="math inline">\(c^n_{k-1}\)</span> is the carry that has come from
the previous operation. Observe that the carry produced in this
operation is <span class="math inline">\(1\)</span> precisely when two
or more of the three terms in <a href="#digit"
data-reference-type="eqref" data-reference="digit">[digit]</a> are <span
class="math inline">\(1\)</span>. This fact can be expressed using the
relation <span class="math display">\[\label{carry}
c^n_k =
d^n_kd^n_{k+1}+d^n_{k+1}c^n_{k-1}+c^n_{k-1}d^n_k\pmod{2}\]</span>
Together, <a href="#digit" data-reference-type="eqref"
data-reference="digit">[digit]</a> and <a href="#carry"
data-reference-type="eqref" data-reference="carry">[carry]</a> give us
the digital evolution of <span class="math inline">\(r_n\)</span>: <span
class="math display">\[\begin{aligned}
d^{n+1}_k &=& L(d^n_k,d^n_{k+1}, c^n_{k-1}) \pmod{2}\\
c^n_k &=& Q(d^n_k,d^n_{k+1}, c^n_{k-1})\pmod{2}
\end{aligned}\]</span> where <span class="math inline">\(L(x,y,z) =
x+y+z\)</span> and <span class="math inline">\(Q(x,y,z) =
xy+yz+zx\)</span>.</p>
<p>The next concept is that of a window; all our work will take place in
windows.</p>
<div class="def-win">
<p><strong>Definition 5</strong>. <em>For any <span
class="math inline">\(n\geq 0\)</span> and <span
class="math inline">\(l\leq r\)</span> we define the time-<span
class="math inline">\(n\)</span> <span
class="math inline">\((l,r)\)</span>-window <span
class="math inline">\(w_n(l,r)\)</span> to be the binary string <span
class="math inline">\(d^n_l\cdots d^n_r\)</span>. The <span
class="math inline">\((l,r)\)</span>-window of <span
class="math inline">\(r_n(\xi)\)</span>, denoted <span
class="math inline">\(w_*(l,r)\)</span>, is the sequence of strings
<span class="math inline">\(\left(w_n(l,r)\right)_{n\geq 0}\)</span>.
The strings corresponding to the left and right tails <span
class="math display">\[\sum_{k=0}^\infty d^n_{k_0\pm k}\, 2^{k_0\pm
k}\]</span> are denoted by <span
class="math inline">\(w_n(\infty,k_0)\)</span> and <span
class="math inline">\(w_n(k_0,\infty)\)</span> respectively.</em></p>
</div>
<figure id="evol">
<div class="center">
<img src="images/trans_evolution.png" />
</div>
<figcaption>The transition <span class="math inline">\(\tau\)</span> in
a fixed window.</figcaption>
</figure>
<p>We will need to refer to the action of multiplication by <span
class="math inline">\((3/2)\)</span> on a window and more generally on
strings.</p>
<div class="def-mul">
<p><strong>Definition 6</strong>. <em>Define <span
class="math display">\[\tau(w_n(l,r)):=\frac{3}{2}\cdot w_n(l,r) :=
w_{n+1}(l,r);\]</span> more generally, for a <span
class="math inline">\(k\)</span>-digit string <span
class="math inline">\(s=d_k\cdots d_1\)</span> and two binary digits
<span class="math inline">\((d,c)\)</span> define <span
class="math inline">\(\tau(d,c)(s)\)</span> to be the binary string
<span class="math inline">\(s' = d_k'\cdots d_1'\)</span>
where <span class="math display">\[d_i'
= d_i+d_{i+1} +c_{i-1}\pmod{2}\quad \textrm{for }k\geq i\geq 1\]</span>
with <span class="math inline">\(d_{k+1}=d\)</span> and <span
class="math inline">\(c_0=c\)</span>. We will consider binary strings as
abstract windows in this context. The <span
class="math inline">\(j\)</span>-th digit of a string <span
class="math inline">\(s\)</span> will be denoted naturally by <span
class="math inline">\(s_j\)</span> in the numbering illustrated
above.</em></p>
</div>
<p>The most basic fact about the transition is the following lemma:</p>
<div id="trans" class="lemma-trans">
<p><strong>Lemma 7</strong>. <em>Fix <span class="math inline">\(k\geq
2\)</span>. For any two <span class="math inline">\(k\)</span>-digit
strings <span class="math inline">\(s\)</span> and <span
class="math inline">\(s'\)</span>, there is at most one pair <span
class="math inline">\((d,c)\)</span> such that <span
class="math inline">\(\tau(d,c)(s)=s'\)</span>.</em></p>
</div>
<div class="proof">
<p><em>Proof.</em> Assume <span
class="math inline">\(\tau(d,c)(s)=s'\)</span>; if <span
class="math inline">\(c\)</span> is switched, the least significant
digit of the result of the operation changes and cannot agree with that
of <span class="math inline">\(s'\)</span> (since the string has at
least two digits, the incoming <span class="math inline">\(d\)</span>
does not affect the least significant one); thus <span
class="math inline">\(c\)</span> cannot be switched. If <span
class="math inline">\(d\)</span> is switched, then since <span
class="math inline">\(c\)</span> is not, the most significant digit will
change, again leading to a contradiction. ◻</p>
</div>
<p>The next lemma shows aperiodicity of string transitions in a given
window of <span class="math inline">\(r_n(\xi)\)</span>:</p>
<div id="per" class="non-per">
<p><strong>Lemma 8</strong>. <em>For any <span
class="math inline">\(l< r\)</span>, the sequence <span
class="math inline">\(w_n(l,r)\)</span> is not eventually
periodic.</em></p>
</div>
<div class="proof">
<p><em>Proof.</em> Fix <span class="math inline">\(l<r\)</span>.
Suppose that for <span class="math inline">\(n\geq n_0\)</span>, the
sequence <span class="math inline">\(w_n(l,r)\)</span> is periodic. By
Lemma <a href="#trans" data-reference-type="ref"
data-reference="trans">7</a>, the pairs <span
class="math inline">\((d,c)_n\)</span> involved in the transition <span
class="math inline">\(\tau(d,c)_n(w_n(l,r))=w_{n+1}(l,r)\)</span> are
determined by the sequence, and since this is periodic, so is the
sequence <span class="math inline">\((d,c)_n\)</span>. However, the
<span class="math inline">\(d\)</span>-part of the pair <span
class="math inline">\((d,c)_n\)</span> is precisely the most significant
digit of <span class="math inline">\(w_n(l-1,r)\)</span>. Therefore the
sequence <span class="math inline">\(w_n(l-1,r)\)</span> is periodic,
starting with <span class="math inline">\(n=n_0\)</span>. Continuing
this way, we see that for <span class="math inline">\(n\geq
n_0\)</span>, the sequence <span class="math inline">\(w_n(\infty,
r)\)</span> is periodic. This contradicts the fact that the position of
the most significant digit <span class="math inline">\(M(n)\)</span> of
<span class="math inline">\(r_n\)</span> is monotonically
increasing. ◻</p>
</div>
<p>Finally, we need a small lemma on the behavior of the <span
class="math inline">\(k\)</span>-digit strings <span
class="math inline">\(0\bar{1}\)</span> and <span
class="math inline">\(1\bar{0}\)</span>.</p>
<div id="zeroone" class="one">
<p><strong>Lemma 9</strong>. <em>Consider a sequence of pairs <span
class="math inline">\((d_n,c_n)\)</span> and denote by <span
class="math inline">\([01^{k-1}]\)</span> the string with <span
class="math inline">\(k\)</span> digits, the most significant equal to
<span class="math inline">\(0\)</span> and all others equal to <span
class="math inline">\(1\)</span>. The sequence <span
class="math inline">\(\tau(d_n,c_n)\bar{1}\)</span> has at least <span
class="math inline">\(\lfloor\frac{k}{2}\rfloor-1\)</span> consecutive
distinct elements. The same is true for the sequence <span
class="math inline">\([10^{k-1}]\)</span>.</em></p>
</div>
<div class="proof">
<p><em>Proof.</em> Applying <span
class="math inline">\(\tau(d_n,c_n)[01^{k-1}]\)</span> gives <span
class="math inline">\([?01^{k-3}?]\)</span> where the question marks are
unknown and depend on <span class="math inline">\((d_n,c_n)\)</span>.
Iterating this we get <span
class="math display">\[\tau(d_{n+l},c_{n+l})[01^{k-1}] =
[?^l01^{k-2l-1}?^l]\]</span> which evidently gives the required number
of distinct elements. The same proof works for the other sequence. ◻</p>
</div>
<h2 data-number="2.2" id="the-digraphs-g_n"><span
class="header-section-number">2.2</span> The digraphs <span
class="math inline">\(G_n\)</span></h2>
<p>In this section we give for the abstract window of length <span
class="math inline">\(n\)</span> a digraph <span
class="math inline">\(G_n\)</span> illustrating all possible string
transitions under <span class="math inline">\(\tau\)</span>. We will use
the word metric of these digraphs and some basic properties for our main
combinatorial arguments. Figure <a href="#g7" data-reference-type="ref"
data-reference="g7">2</a> shows the underlying graph of <span
class="math inline">\(G_7\)</span>.</p>
<figure id="g7">
<div class="center">
<img src="images/trans_limit.png" />
</div>
<figcaption>The graph underlying <span
class="math inline">\(G_7\)</span>.</figcaption>
</figure>
<div class="def-G">
<p><strong>Definition 10</strong>. <em>Let <span
class="math inline">\(G_n = (V_n,E_n)\)</span> be the digraph with
vertex set <span class="math inline">\(V_n\)</span> equal to the set of
all binary strings of length <span class="math inline">\(n\)</span>
(abstract windows) and such that there is a directed edge <span
class="math inline">\((s,s')\)</span> between two strings <span
class="math inline">\(s\)</span> and <span
class="math inline">\(s'\)</span> if there exists a pair <span
class="math inline">\((d,c)\)</span> such that <span
class="math inline">\(s' = \tau(d,c)(s)\)</span>.</em></p>
</div>
<p>Now let us describe some properties of the <span
class="math inline">\(G_n\)</span> that we will need.</p>
<div class="G-structure">
<p><strong>Lemma 11</strong>. <em>The digraphs <span
class="math inline">\(G_n\)</span> have the following
properties:</em></p>
<ol>
<li><p><em>They are <span class="math inline">\(4\)</span>-biregular,
i.e. each vertex has four out-edges and four in-edges and no multiple
directed edges.</em></p></li>
<li><p><em>There are exactly four vertices with loops.</em></p></li>
<li><p><em>They are strongly connected, i.e. for any two vertices there
is a directed path joining them.</em></p></li>
</ol>
</div>
<div class="proof">
<p><em>Proof.</em> Assume <span
class="math inline">\(\tau(d,c)(s)=s'\)</span> for two <span
class="math inline">\(k\)</span>-digit strings <span
class="math inline">\(s,s'\)</span>. Then <span
class="math inline">\(d,c\)</span> are uniquely determined by this
equation by lemma <a href="#trans" data-reference-type="ref"
data-reference="trans">7</a>, showing that there are no multiple
directed edges. From this we also conclude that if <span
class="math inline">\(s\)</span> is given, then different choices for
<span class="math inline">\((d,c)\)</span> lead to different <span
class="math inline">\(s'\)</span>, i.e. the out-degree is four.</p>
<p>Now suppose <span class="math inline">\(s'\)</span> is given. We
will show there are precisely four distinct strings <span
class="math inline">\(s\)</span> such that <span
class="math inline">\(\tau(d,c)(s)=s'\)</span>. Begin to construct
<span class="math inline">\(s\)</span> by choosing its first two digits
<span class="math inline">\(s_2s_1\)</span> in an arbitrary way. This
allows four distinct choices which determine uniquely the rest of the
data: for each of these choices there is a unique pair <span
class="math inline">\((d,c)\)</span> and a unique extension <span
class="math inline">\(s_k\cdots
s_2s_1\)</span> such that <span
class="math inline">\(\tau(d,c)(s)=s'\)</span>. To see this, look at
the effect on digits: we need <span class="math display">\[s'_1=
s_1+s_2+c\]</span> which holds for a unique <span
class="math inline">\(c\)</span>; this also determines the carry <span
class="math inline">\(c_1\)</span> to be used in the next operation. The
next equation reads <span
class="math display">\[s'_2=s_2+s_3+c_1\]</span> which uniquely
determines <span class="math inline">\(s_3\)</span> and therefore also
<span class="math inline">\(c_2\)</span>, and so on. At the last step we
have <span class="math inline">\(s'_k = s_k+d+c_{k-1}\)</span> which
uniquely determines <span class="math inline">\(d\)</span> (<span
class="math inline">\(s_k\)</span> and <span
class="math inline">\(c_{k-1}\)</span> had been determined at the
previous step).</p>
<p>Next we show that precisely four vertices have loops in them. The
tactic is the same as above: we want <span
class="math inline">\(\tau(d,c)(s)=s\)</span> for some <span
class="math inline">\((d,c)\)</span>; we arbitrarily assign the first
two digits of <span class="math inline">\(s\)</span> and show that the
rest of the digits, as well as <span class="math inline">\(d\)</span>
and <span class="math inline">\(c\)</span>, are uniquely determined. The
equation gives <span class="math inline">\(s_1=s_1+s_2+c\)</span> which
determines <span class="math inline">\(c\)</span> . Similarly, at each
step we have <span class="math display">\[s_j=s_j+s_{j+1} +
c_{j-1};\]</span> the carry has been determined by the previous
operation, so <span class="math inline">\(s_{k+1}\)</span> is also
uniquely determined. At the final step we have <span
class="math inline">\(s_k = s_k+d+c_{k-1}\)</span> and this determines
<span class="math inline">\(d\)</span>.</p>
<p>In order to show that the graphs <span
class="math inline">\(G_k\)</span> are strongly connected, we make use
of the metric theory of <span
class="math inline">\(\{r_n(\xi)\}\)</span>. We know that for almost
every <span class="math inline">\(\xi>0\)</span>, the sequence of
fractional parts of <span
class="math inline">\((\frac{3}{2})^n\xi\)</span> is uniformly
distributed in <span class="math inline">\([0,1]\)</span> . In
particular, the limit points of the sequence are dense in <span
class="math inline">\([0,1]\)</span>. This implies that the string
sequence <span class="math inline">\(w_n(-1,-k)(\xi)\)</span> will see
all <span class="math inline">\(2^k\)</span> possible strings since each
string corresponds to one of the <span
class="math inline">\(2^k\)</span> boundaries of dyadic intervals in the
canonical dyadic partition of <span
class="math inline">\([0,1)\)</span>. Therefore, if we choose <span
class="math inline">\(\xi\)</span> such that the sequence has a dense
set of limit points in <span class="math inline">\([0,1]\)</span>, for
any <span class="math inline">\(k\)</span> the string <span
class="math inline">\(w_n(-1,-k)(\xi)\)</span> takes on all <span
class="math inline">\(2^k\)</span> patterns. This sequence is a
realization of a directed walk on <span
class="math inline">\(G_k\)</span> that captures all of the vertices,
showing strong connectivity of <span
class="math inline">\(G_k\)</span>. ◻</p>
</div>
<h1 data-number="3" id="lower-bounds-for-patterns-in-a-window"><span
class="header-section-number">3</span> Lower bounds for patterns in a
window</h1>
<p>Now we turn to the proof of our main results. We fix arbitrary <span
class="math inline">\(\xi>0\)</span> and an arbitrary window sequence
<span class="math inline">\(w_*:=w_*(l,r)\)</span> with at least two
digits, and let <span class="math inline">\(k=r-l\)</span> be the size
of the window. We need the following definitions:</p>
<div class="defin">
<p><strong>Definition 12</strong>. A property of strings in <span
class="math inline">\(w_*\)</span> is said to be persistent if it is
true infinitely often in the given sequence. Similarly, a specific
binary pattern is persistent if it occurs infinitely often in <span
class="math inline">\(w_*\)</span>. Since only finitely many patterns
can occur in <span class="math inline">\(w_*\)</span>, eventually all
such patterns are persistent.</p>
</div>
<div class="defin">
<p><strong>Definition 13</strong>. The natural extension of a window
<span class="math inline">\(w=w_n(l,r)\)</span> is the window <span
class="math inline">\(w_n(l-1,r+2)\)</span> and we denote it <span
class="math inline">\(w^e\)</span>. The <span
class="math inline">\(n\)</span>-th iterated extension is denoted <span
class="math inline">\(w^{e(n)}\)</span>. The windows <span
class="math inline">\(w_*(l-1,l-1)\)</span> and <span
class="math inline">\(w_*(r+1,r+2)\)</span> together form the extension
boundary or just boundary of <span class="math inline">\(w\)</span>. We
call the first (single digit) window the front and the second (digital
pair) the rear.</p>
</div>
<div class="defin">
<p><strong>Definition 14</strong>. A persistent pattern in <span
class="math inline">\(w_*\)</span> is said to trap the boundary if for
all large <span class="math inline">\(n\)</span>, the boundary digits
are determined by the pattern. A persistent pattern is locked if for all
large <span class="math inline">\(n\)</span>, whenever it appears in
<span class="math inline">\(w_n\)</span>, <span
class="math inline">\(w_{n+1}\)</span> is uniquely determined. If a
persistent pattern has at least two distinct persistent extensions in
<span class="math inline">\(w^e\)</span> we call it free, and if it has
at least two persistent extensions in <span
class="math inline">\(w^{e(n)}\)</span> we call it free at spread <span
class="math inline">\(n\)</span>.</p>
</div>
<p>Note that trapping means the pattern extends uniquely in the lateral
direction; locking means the pattern has a unique vertical transition.
The interplay between the two is crucial for us.</p>
<div id="free_pat" class="lemma">
<p><strong>Lemma 15</strong>. <em>For any given <span
class="math inline">\(w_*\)</span> there exists at least one unlocked
persistent pattern.</em></p>
</div>
<div class="proof">
<p><em>Proof.</em> If all persistent patterns were locked, the sequence
<span class="math inline">\(w_*\)</span> would be eventually periodic,
contradicting Lemma <a href="#per" data-reference-type="ref"
data-reference="per">8</a>. ◻</p>
</div>
<p>Observe that if a pattern traps the boundary into the digit patterns
<span class="math inline">\(*\underline{\quad}00\)</span> and <span
class="math inline">\(*\underline{\quad}11\)</span> then it is locked;
in all four cases the pair <span class="math inline">\((d,c)\)</span> is
determined by the boundary, and thus the transition is determined by the
pattern. On the other hand, a pattern can possibly trap a boundary
pattern of the forms <span
class="math inline">\(*\underline{\quad}01\)</span> or <span
class="math inline">\(*\underline{\quad}10\)</span> but not be locked;
in this latter case the pattern can be free due to the carry.</p>
<p>With these preliminaries, we can give a first uniform lower bound for
the number of patterns in any window, and thus get our first
quantitative density statement for limit points of <span
class="math inline">\(r_n(\xi)\)</span>.</p>
<div class="prop">
<p><strong>Proposition 16</strong>. <em>For any <span
class="math inline">\(k\geq 2\)</span> the minimum number of distinct
persistent strings in a window of size <span
class="math inline">\(k\)</span> is bounded below by <span
class="math inline">\(\frac{1}{2}\sqrt{k}\)</span>.</em></p>
</div>
<div class="proof">
<p><em>Proof.</em> Let <span class="math inline">\(p_k\)</span> be the
minimum number of persistent strings over all windows of size <span
class="math inline">\(k\)</span> (for a fixed <span
class="math inline">\(\xi\)</span>; we will give a uniform lower bound
for <span class="math inline">\(p_k\)</span> over <span
class="math inline">\(\xi\)</span>). Start with an arbitrary window
<span class="math inline">\(w_*\)</span> of size <span
class="math inline">\(k_0\geq 2\)</span>. We know <span
class="math inline">\(w_*\)</span> is not eventually periodic so <span
class="math inline">\(p_2\geq 2\)</span>. Furthermore there exists an
unlocked pattern in <span class="math inline">\(w_*\)</span>. If for all
windows the pattern is free, then <span
class="math inline">\(p_{k_0+3}\geq p_{k_0} +1\)</span>. Otherwise, for
some <span class="math inline">\(w_*\)</span> an unlocked pattern <span
class="math inline">\(P\)</span> must trap one of the boundary forms
<span class="math inline">\(*\underline{\quad}01\)</span> or <span
class="math inline">\(*\underline{\quad}10\)</span> by the remarks
above.</p>
<p>Now extend the window one digit to the left and then start extending
it by pairs of digits to the right only; at each step either the
extended pattern becomes free or it keeps trapping the same form as
before: it cannot end on a locked pattern because then the transition
would be forced in the extended pattern, and thus also in the original
(recall that <span class="math inline">\(P\)</span> is unlocked but not
free). It also cannot switch between the two possible forms because that
would lead to a <span class="math inline">\(00\)</span> or <span
class="math inline">\(11\)</span> pair; these forms determine uniquely
the carry to the left and since the leftmost extended digit is also
trapped, the enclosed string (and thus the original) has a unique
transition contradicting unlockedness.</p>
<p>Thus we end up with the following situation: after <span
class="math inline">\(l\)</span> extensions, we get a pattern of the
form <span class="math display">\[*P0101\cdots 01 \mbox{ }\textrm{ or
}\mbox{ }*P10\cdots
10.\]</span> In both cases, after the transition we end up with a
pattern that contains the pattern <span
class="math inline">\(0\overline{1}^{2l-1}\)</span> (i.e. there are at
least <span class="math inline">\(2l-1\)</span> digits equal to <span
class="math inline">\(1\)</span> followed by an inevitable leading <span
class="math inline">\(0\)</span>) or the pattern <span
class="math inline">\(1\overline{0}^{2l-1}\)</span>. We claim that the
leading zero/one persistently lies within the window <span
class="math inline">\(w_*\)</span>, that is <span
class="math inline">\(P\)</span> does not always transit to the pattern
<span class="math inline">\(\overline{1}^k\)</span> or always to <span
class="math inline">\(\overline{0}^k\)</span>. This is because <span
class="math inline">\(P\)</span> is unlocked in the first place, so it
cannot determine uniquely the transition. To conclude, starting with an
arbitrary window <span class="math inline">\(w_*\)</span> of length
<span class="math inline">\(k_0\)</span> without a free pattern, we
found <span class="math inline">\(l-1\)</span> distinct persistent
patterns (by lemma <a href="#zeroone" data-reference-type="ref"
data-reference="zeroone">9</a>) in the extension <span
class="math inline">\(*w_***\cdots**\)</span> of length <span
class="math inline">\(1+k_0+2l\)</span>.</p>
<p>Now suppose every string of length <span
class="math inline">\(k_0\)</span> has at least <span
class="math inline">\(l_0>1\)</span> distinct persistent strings.
Applying the above to <span class="math inline">\(l=l_0+2\)</span> we
have shown that every string of length <span
class="math inline">\(k_1=k_0+2l_0+5\)</span> has at least <span
class="math inline">\(l_1=l_0+1\)</span> distinct persistent strings
(either by at least one of the <span class="math inline">\(l_0\)</span>
strings freely extending to two distinct ones before we reach <span
class="math inline">\(k_0+2l_0+5\)</span>, or by the trapped string
argument), and we can iterate this procedure to show that <span
class="math inline">\(k_n
= k_{n-1}+2l_{n-1}+5\)</span> length strings have at least <span
class="math inline">\(l_n = l_{n-1}+1\)</span> distinct strings. Setting
<span class="math inline">\(k_0=2\)</span>, <span
class="math inline">\(l_0=2\)</span>, and solving the congruence, we see
that <span class="math inline">\(p_{(n+2)^2-2}\geq n+2\)</span>. To
simplify, by monotonicity <span class="math inline">\(p_{(n+2)^2}\geq
n+2\)</span> so <span class="math inline">\(p_{n^2}\geq n\)</span> for
<span class="math inline">\(n\geq 2\)</span>. Further interpolating, we
get the result. ◻</p>
</div>
<p>As a corollary of this proposition (applied to <span
class="math inline">\(w_n(1,r)\)</span> for arbitrary <span
class="math inline">\(r\)</span>) we get the infinitude of limit points
in the quantitative manner claimed in Theorem <a href="#main_simple"
data-reference-type="ref" data-reference="main_simple">1</a>.</p>
</body>
</html>