-
Notifications
You must be signed in to change notification settings - Fork 7
/
P2-Comonoids.tex
10766 lines (9747 loc) · 602 KB
/
P2-Comonoids.tex
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
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% !TeX root = P2-Comonoids.tex
\documentclass[Book-Poly]{subfiles}
\begin{document}
%
\setcounter{chapter}{5}%Just finished 5.
\part{A different category of categories}\label{part.comon}
\Opensolutionfile{solutions}[solution-file6]
%------------ Chapter ------------%
\chapter{The composition product}\label{ch.comon.comp}
\index{monoidal structure!substitution|see{composition product}}
\index{composition product|(}\index{interface!changing}
We have seen that the category $\poly$ of polynomial functors has quite a bit of well-interoperating mathematical structure. Further, it is an expressive way to talk about dynamical systems that can change their interfaces and wiring patterns based on their internal states.
But we touched upon one thing---what in some sense is the most interesting part of the story---only briefly. That thing is quite simple to state, and yet has profound consequences. Namely, polynomials can be composed:
\[
\yon^\2\circ(\yon+\1)=(\yon+\1)^\2\iso\yon^\2+\2\yon+\1.
\]
In other words, $(\yon+\1)$ is \emph{substituted in} for the variable $\yon$ in $\yon^\2$. What could be simpler?
\index{polynomial functor, substitution of polynomials|see{polynomial functor!composition of polynomials}}
\index{polynomial functor!composition of polynomials}
It turns out that this operation, which we will soon see is a monoidal product, has a lot to do with time.
\index{time!composition product and}
There is a strong sense---made precise in \cref{prop.poly_closed_comp}---in which the polynomial $p\circ q$ represents ``starting at a position $i$ in $p$, choosing a direction in $p[i]$, landing at a position $j$ in $q$, choosing a direction in $q[j]$, and then landing... somewhere.''
This is exactly what we need to run through multiple steps of a dynamical system, the very thing we didn't know how to do in \cref{ex.do_nothing}.
We'll continue that story in \cref{subsec.comon.comp.def.dyn_sys}.
The composition product has many surprises up its sleeve, as we'll see throughout the rest of the book.%
\footnote{Some authors refer to $\tri$ as the \emph{substitution} product, rather than the composition product. We elected to use the composition product terminology because it provides a good noun form ``the composite'' for $p\tri q$, whereas ``the substitute'' is somehow strange in English.}
%-------- Section --------%
\section{Defining the composition product}\label{sec.comon.comp.def}
We begin with the definition of the composition product in terms of polynomials as functors.
\subsection{Composite functors}\label{subsec.comon.comp.def.functor}
\begin{definition}[Composition product] \label{def.comp}
Given polynomial functors $p, q$, we let $p \circ q$ denote their \emph{composition product}, or their composite as functors.
That is, $p \circ q \colon \smset \to \smset$ sends each set $X$ to the set $p(q(X))$.
\end{definition}
\index{composition product!as composition of functors}
Functor composition gives a monoidal structure on the category $\smset^\smset$ of functors $\smset\to\smset$, but to check that the full subcategory $\poly$ of $\smset^\smset$ inherits this monoidal structure, we need to verify that the composite of two functors in $\poly$ is still a functor in $\poly$.
\begin{proposition}\label{prop.poly_closed_comp}
Suppose $p,q\in\poly$ are polynomial functors $p,q\colon\smset\to\smset$. Then their composite $p\circ q$ is again a polynomial functor, and we have the following isomorphism:
\begin{equation} \label{eqn.composite_formula_circ}
p\circ q\iso\sum_{i\in p(\1)}\prod_{a\in p[i]}\sum_{j\in q(\1)}\prod_{b\in q[j]}\yon.
\end{equation}
\end{proposition}
\begin{proof}
We can rewrite $p$ and $q$ as
\[
p\iso\sum_{i\in p(\1)}\yon^{p[i]}\iso\sum_{i\in p(\1)}\prod_{a\in p[i]}\yon
\qqand
q\iso\sum_{j\in q(\1)}\yon^{q[j]}\iso\sum_{j\in q(\1)}\prod_{b\in q[j]}\yon.
\]
For any set $X$ we have $(p\circ q)(X)=p(q(X))=p(\sum_j\prod_b X)=\sum_i\prod_a\sum_j\prod_bX$, so \eqref{eqn.composite_formula_circ} is indeed the formula for the composite $p \circ q$.
To see this is a polynomial, we use \eqref{eqn.push_prod_sum_set_indep}, which says we can rewrite the $\prod\sum$ in \eqref{eqn.composite_formula_circ} as a $\sum\prod$ to obtain
\begin{align}\label{eqn.composite_formula_sums_first_circ}
p\circ q\iso
\scalebox{1.3}{$\displaystyle
\sum_{i\in p(\1)} \; \sum_{\ol{j}\colon p[i]\to q(\1)}\yon^{\sum_{a\in p[i]}q[\ol{j}(a)]}$}
\end{align}
(written slightly bigger for clarity), which is clearly a polynomial.
\end{proof}
\index{composition product!formula for}
\begin{corollary} \label{cor.comp_monoidal}
The category $\poly$ has a monoidal structure $(\yon,\circ)$, where $\yon$ is the identity functor and $\circ$ is given by composition.
\end{corollary}
\index{composition product!unit of}
Because we may wish to use $\circ$ to denote composition in arbitrary categories, we use a special symbol for polynomial composition, namely
\[
p\tri q\coloneqq p\circ q.
\]
The symbol $\tri$ looks a bit like the composition symbol in that it is an open shape, and when writing quickly by hand, it's okay if it morphs into a $\circ$.
But $\tri$ highlights the asymmetry of composition, in contrast with the other monoidal structures on $\poly$ we've encountered.
Moreover, we'll soon see that $\tri$ is quite evocative in terms of trees.
For each $n\in\nn$, we'll also use $p\tripow{n}$ to denote the $n$-fold composition product of $p$, i.e.\ $n$ copies of $p$ all composed with each other.\footnote{When we say ``the $n$-fold composition product of $p$,'' we mean $n$ copies of $p$ all composed with each other; but when we discuss an ``$n$-fold composition product'' in general, we refer to an arbitrary composition product of $n$ polynomials that may or may not all be equal to each other. This will apply to composition products of lenses as well, once we define those.}
In particular, $p\tripow0=\yon$ and $p\tripow1=p$.
We repeat the important formulas from \cref{prop.poly_closed_comp} and its proof in the new notation:
\begin{equation}\label{eqn.composite_formula}
p\tri q\iso\sum_{i\in p(\1)}\prod_{a\in p[i]}\sum_{j\in q(\1)}\prod_{b\in q[j]}\yon.
\end{equation}
\begin{align}\label{eqn.composite_formula_sums_first}
p\tri q\iso
\scalebox{1.3}{$\displaystyle
\sum_{i\in p(\1)} \; \sum_{\ol{j}\colon p[i]\to q(\1)}\yon^{\sum_{a\in p[i]}q[\ol{j}(a)]}$}
\end{align}
% \[
% \begin{tikzpicture}[polybox, baseline=(helper)]
% \node[poly] (p) {$a:p[i]$\at$i:p(\1)$};
% \node[poly, above=of p] (q) {$b:q[j]$\at$j:q(\1)$};
% \coordinate (helper) at ($(p.north)!.5!(q.south)$);
% \end{tikzpicture}
% \quad\cong\quad
% \begin{tikzpicture}[polybox, baseline=(p.east)]
% \node[poly] (p) {$(a:p[i], b:q[j(a)]$)\at$(i:p(1), j: p[i]\to q(\1))$};
% \end{tikzpicture}
% \]
\begin{exercise}
Let's consider \eqref{eqn.composite_formula_sums_first} piece by piece, with concrete polynomials $p\coloneqq\yon^\2+\yon^\1$ and $q\coloneqq \yon^\3+\1$.
\begin{enumerate}
\item What is $\yon^\2\tri q$?
\item What is $\yon^\1\tri q$?
\item What is $(\yon^\2+\yon^\1)\tri q$? This is what $p\tri q$ ``should be.''
\item How many functions $\ol{j_1}\colon p[1]\to q(\1)$ are there?
\item For each function $\ol{j_1}$ as above, what is $\sum_{a\in p[1]} q[\ol{j_1}(a)]$?
\item How many functions $\ol{j_2}\colon p[2]\to q(\1)$ are there?
\item For each function $\ol{j_2}$ as above, what is $\sum_{a\in p[2]} q[\ol{j_2}(a)]$?
\item Write out \[\sum_{i\in p(\1)}\;\sum_{\ol{j}\colon p[i]\to q(\1)}\yon^{\sum_{a\in p[i]}q[\ol{j}(a)]}.\]
Does the result agree with what $p\tri q$ should be?
\qedhere
\end{enumerate}
\begin{solution}
We are given $p\coloneqq\yon^\2+\yon^\1$ and $q\coloneqq \yon^\3+\1$.
\begin{enumerate}
\item By standard polynomial multiplication, we have that $\yon^\2 \tri q \iso q \times q \iso \yon^\6 + \2\yon^\3 + \1$.
\item We have that $\yon^\1 \tri q \iso q \iso \yon^\3 + \1$.
\item Combining the previous parts, we have that $(\yon^\2 + \yon^\1) \tri q \iso q \times q + q \iso \yon^\6 + \3\yon^\3 + \2$.
\item Since $p[1] \iso \2$ and $q(\1) \iso \2$, there are $2^2 = 4$ functions $p[1] \to q(\1)$.
\item When $\ol{j_1} \colon p[1] \to q(\1)$ is one of the two possible bijections, we have that
\[
\sum_{a \in p[1]} q[\ol{j_1}(a)] \iso q[1] + q[2] \iso \3 + \0 \iso \3.
\]
When $\ol{j_1} \colon p[1] \to q(\1)$ sends everything to $1 \in q(\1)$, we have that
\[
\sum_{a \in p[1]} q[\ol{j_1}(a)] \iso q[1] + q[1] \iso \3 + \3 \iso \6.
\]
Finally, when $\ol{j_1} \colon p[1] \to q(\1)$ sends everything to $2 \in q(\1)$, we have that
\[
\sum_{a \in p[1]} q[\ol{j_1}(a)] \iso q[2] + q[2] \iso \0 + \0 \iso \0.
\]
\item Since $p[2] \iso \1$ and $q(\1) \iso \2$, there are $2^1 = 2$ functions $p[2] \to q(\1)$.
\item When $j_2 \colon p[2] \to q(\1)$ maps to $1 \in q(\1)$, we have that $\sum_{a \in p[2]} q[\ol{j_2}(a)] \iso q[1] \iso \3$, and when $\ol{j_2} \colon p[2] \to q(\1)$ maps to $2 \in q(\1)$, we have that $\sum_{a \in p[2]} q[\ol{j_2}(a)] \iso q[2] \iso \0$.
\item From the previous parts, we have that
\[
\sum_{i\in p(\1)}\;\sum_{\ol{j}\colon p[i]\to q(\1)}\yon^{\sum_{a\in p[i]}q[j_i(a)]} \iso (\2\yon^\3 + \yon^\6 + \yon^\0) + (\yon^\3 + \yon^\0) \iso \yon^\6 + \3\yon^\3 + \2,
\]
which agrees with what $p \tri q$ should be.
\end{enumerate}
\end{solution}
\end{exercise}
\index{composition product!of special polynomials}
\begin{exercise}\label{exc.composites_of_specials}
\begin{enumerate}
\item If $p$ and $q$ are representable, show that $p\tri q$ is too. Give a formula for it.
\item If $p$ and $q$ are linear, show that $p\tri q$ is too. Give a formula for it.
\item If $p$ and $q$ are constant, show that $p\tri q$ is too. Give a formula for it.
\qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item Given representable polynomials $p \coloneqq \yon^A$ and $q \coloneqq \yon^B$, we have that $p \tri q \iso \left(\yon^B\right)^A \iso \yon^{AB}$, which is also representable.
\item Given linear polynomials $p \coloneqq A\yon$ and $q \coloneqq B\yon$, we have that $p \tri q \iso A(B\yon) \iso AB\yon$, which is also linear.
\item Given constant polynomials $p \coloneqq A$ and $q \coloneqq B$, we have that $p \tri q \iso A$, which is also constant (see also \cref{exc.composing_with_constants}).\index{constant polynomial}
\end{enumerate}
\end{solution}
\end{exercise}
\begin{exercise}
Recall the closure operation $\ihom{-,-}\colon\poly\op\times\poly\to\poly$ for $\otimes$ from \eqref{eqn.par_hom}.
Show that for all $A\in\smset$ and $q\in\poly$, there is an isomorphism
\[
\yon^A\tri q\iso\ihom{A\yon,q}.
\]
\begin{solution}
Given $A\in\smset$ and $q\in\poly$, we have
\begin{align*}
\yon^A\tri q &\iso
\sum_{\ol{j}\colon A\to q(\1)}\yon^{\sum_{a\in A}q[\ol{j}(a)]}
\tag*{\eqref{eqn.composite_formula_sums_first}} \\ &\iso
\sum_{\varphi\colon A\yon\to q}\yon^{\sum_{a\in A}q[\varphi_\1(a)]} \\&\iso
\ihom{A\yon,q},
\tag*{\eqref{eqn.par_hom_sum}}
\end{align*}
for a lens $\varphi\colon A\yon\to q$ has an on-positions function $A\to q(\1)$ and uniquely determined on-directions functions.
\end{solution}
\end{exercise}
We know how $\tri$ acts on the objects in $\poly$, but what does it do to the morphisms between them?
For any pair of natural transformations $f\colon p\to p'$ and $g\colon q\to q'$ between polynomial functors, their composite $f\tri g\colon p\tri q\to p'\tri q'$ is given by \emph{horizontal composition}.
\index{composition product!on morphisms|see{composition product, on lenses}}
\index{composition product!on lenses|(}
\begin{definition}[Horizontal composition of natural transformations]\label{def.horiz_comp_nat_trans}
Let $f\colon p\to p'$ and $g\colon q\to q'$ be two natural transformations between (polynomial) functors $p,p',q,q'\colon\smset\to\smset$.
Then the \emph{horizontal composite} of $f$ and $g$, denoted $f\tri g$, is the natural transformation $p\tri q\to p'\tri q'$ whose $X$-component for each $X\in\smset$ is the function
\begin{equation} \label{eqn.horiz_comp_nat_trans_comp}
p(q(X)) \To{f_{q(X)}} p'(q(X)) \To{p'(g_X)} p'(q'(X))
\end{equation}
obtained by composing the $q(X)$-component of $f$ with the functor $p'$ applied to the $X$-component of $g$.
\end{definition}
\begin{exercise}
Show that we could have replaced the composite function \eqref{eqn.horiz_comp_nat_trans_comp} in \cref{def.horiz_comp_nat_trans} with the function
\begin{equation} \label{eqn.horiz_comp_nat_trans_comp2}
p(q(X)) \To{p(g_X)} p(q'(X)) \To{f_{q'(X)}} p'(q'(X))
\end{equation}
obtained by composing $p$ applied to the $X$-component of $g$ with the $q'(X)$-component of $f$, without altering the definition.
\begin{solution}
We wish to show that \eqref{eqn.horiz_comp_nat_trans_comp2} could replace \eqref{eqn.horiz_comp_nat_trans_comp} in \cref{def.horiz_comp_nat_trans}.
We claim that \eqref{eqn.horiz_comp_nat_trans_comp} and \eqref{eqn.horiz_comp_nat_trans_comp2} are in fact the same function; that is, that the following square commutes:
\[
\begin{tikzcd}
p(q(X)) \ar[r, "f_{q(X)}"]\ar[d, "p(g_X)"'] & p'(q(X)) \ar[d, "p'(g_X)"] \\
p(q'(X)) \ar[r, "f_{q'(X)}"'] & p'(q'(X))
\end{tikzcd}
\]
Indeed it does, by the naturality of $f$.
\end{solution}
\end{exercise}
\index{natural transformation!horizontal composition}
\index{natural transformation!vertical composition}
\begin{remark}
There are two very different notions of lens composition floating around, so we'll try to mitigate confusion by standardizing terminology here.
We'll reserve the term \emph{composite lens} for lenses $h\then j\colon r\to t$ obtained by composing a lens $h\colon r\to s$ with a lens $j\colon s\to t$, according to the composition rule of the category $\poly$.
This corresponds to \emph{vertical composition} of natural transformations.
This is also the kind of composition we will mean whenever we use the verb ``\emph{compose},'' if the objects of that verb are lenses.
Meanwhile, we'll use the term \emph{composition product (of lenses)} for lenses $f\tri g\colon p\tri q\to p'\tri q'$ obtained by applying the monoidal product functor $\tri\colon\poly\times\poly\to\poly$ on the lenses $f\colon p\to p'$ and $g\colon q\to q'$.
This corresponds to \emph{horizontal composition} of natural transformations.
In this case, we'll use the verb phrase ``\emph{taking the monoidal product}.''
On the other hand, we'll use the terms ``composite'' and ``composition product'' interchangeably to refer to polynomials $p\tri q$, obtained by composing $p,q\in\poly$ as functors or, equivalently, applying the monoidal product functor $\tri$ on them---as there is no risk of confusion here.%
%\footnote{Some authors refer to $\tri$ as the \emph{substitution} product, rather than the composition product. We elected to use the composition product terminology because it provides a good noun form ``the composite'' for $p\tri q$, whereas ``the substitute'' is somehow strange in English.}
This is another reason we tend to avoid the symbol $\circ$, preferring to use $\then$ for vertical composition and $\tri$ for horizontal composition.
Of course, if you're ever confused, you can always check whether the codomain of the first lens matches up with the domain of the second.
If they don't, we must be taking their monoidal product.
\end{remark}
The composition product of polynomials and lenses will be extremely important in the story that follows.
However, we only sometimes think of it as the composition of functors and the horizontal composition of natural transformations; more often we think of it as certain operations on positions and directions or on corolla forests.
\index{composition product!on lenses|)}\index{natural transformation!horizontal composition}
\subsection{Composite positions and directions}\label{subsec.comon.comp.def.arena}
\index{composition product!positions and directions}
Let us interpret our formula \eqref{eqn.composite_formula_sums_first} for the composition product of two polynomials in terms of positions and directions.
The position-set of $p \tri q$ is
\begin{equation} \label{eqn.comp_pos}
(p \tri q)(\1) \iso \sum_{i \in p(\1)} \; \sum_{\ol{j} \colon p[i] \to q(1)} \1 \iso \sum_{i \in p(\1)} \smset(p[i], q(\1)).
\end{equation}
In other words, specifying a position of $p \tri q$ amounts to first specifying a $p$-position $i$, then specifying a function $\ol{j} \colon p[i] \to q(\1)$, i.e.\ a $q$-position $\ol{j}(a)$ for each $p[i]$-direction $a$.
Given such a position $(i, \ol{j})$ of $p \tri q$, the direction-set of $p \tri q$ at $(i, \ol{j})$ is
\begin{equation} \label{eqn.comp_dir}
(p \tri q)[(i, \ol{j})] \iso \sum_{a \in p[i]} q[\ol{j}(a)].
\end{equation}
So a direction of $p \tri q$ at $(i, \ol{j})$ consists of a $p[i]$-direction $a$ and a $q[\ol{j}(a)]$-direction.
While this description completely characterizes $p \tri q$, it may be a bit tricky to wrap your head around.
Here is an alternative perspective that can help us get a better intuition for what's going on with the composition product of polynomials.
Back in \cref{sec.poly.rep-sets.sum-prod-set}, we saw how to write the instructions for choosing an element of a sum or product of sets.
For instance, given a polynomial $p$ and a set $X$, the instructions for choosing an element of
\[
p\tri X=p(X)\iso\sum_{i\in p(\1)}\prod_{a\in p[i]}X
\]
would be written as follows.
\begin{quote}
To choose an element of $p(X)$:
\begin{enumerate}
\item choose an element $i\in p(\1)$;
\item for each element $a\in p[i]$:
\begin{enumerate}[label*=\arabic*.]
\item choose an element of $X$.
\end{enumerate}
\end{enumerate}
\end{quote}
But say we hadn't picked a set $X$ yet; in fact, say we might replace $X$ with a general polynomial instead.
We'll replace ``an element of $X$'' with a placeholder---the words ``a future''---that indicates that we don't yet know what will go there. It depends on what has come before.%
\footnote{In a significant sense, the composition product should be thought of as being about dependency.}
Furthermore, to highlight that these instructions are associated with some polynomial $p$, we will use our familiar positions and directions terminology.
\begin{quote}
The instructions associated with a polynomial $p$ are:
\begin{enumerate}
\item choose a $p$-position $i$;
\item for each $p[i]$-direction $a$:
\begin{enumerate}[label*=\arabic*.]
\item choose a future.
\end{enumerate}
\end{enumerate}
\end{quote}
\index{future!as placeholder for dependency}
\index{composition product!as dependency}
If we think of polynomials in terms of their instructions, then \eqref{eqn.composite_formula} tells us that the composition product simply nests one set of instructions within another, as follows.
\begin{quote}
The instructions associated with a polynomial $p\tri q$ are:
\begin{enumerate}
\item choose a $p$-position $i$;
\item for each $p[i]$-direction $a$:
\begin{enumerate}[label*=\arabic*.]
\item choose a $q$-position $j$;
\item for each $q[j]$-direction $b$:
\begin{enumerate}[label*=\arabic*.]
\item choose a future.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{quote}
Similarly, we could write down the instructions associated with any $n$-fold composition product by nesting even further.
We might think of such instructions as specifying some sort of length-$n$ \emph{strategy}, in the sense of game theory, for picking positions given any directions---except that the opponent is somehow abstract, having no positions of its own.
\index{composition product!$n$-fold}
\index{composition product!positions as strategies}
When we rewrite \eqref{eqn.composite_formula} \eqref{eqn.composite_formula_sums_first}, we are collapsing the instructions down into the following, highlighting the positions and directions of $p\tri q$.
\begin{quote}
The instructions associated with a polynomial $p\tri q$ are:
\begin{enumerate}
\item choose a $p$-position $i$ and, for each $p[i]$-direction $a$, a $q$-position $\ol{j}_i(a)$;
\item for each $p[i]$-direction $a$ and each $q[\ol{j}_i(a)]$-direction $b$:
\begin{enumerate}[label*=\arabic*.]
\item choose a future.
\end{enumerate}
\end{enumerate}
\end{quote}
We will see in \cref{subsec.comon.comp.def.corolla} that these instructions have a very natural interpretation when we depict these polynomials as corolla forests.
\index{future!as placeholder for dependency}
\begin{exercise}
\begin{enumerate}
\item Let $p$ be an arbitrary polynomial. Write out the (uncollapsed) instructions associated with $p\tripow3=p\tri p\tri p$.
\item Write out the (uncollapsed) instructions for choosing an element of $p\tri p\tri\1$, but where you would normally write ``choose an element of $\1$,'' just write ``done.'' \qedhere
\end{enumerate}
\begin{solution}
\begin{longenum}
\item The instructions associated with a polynomial $p\tri p\tri p$ are:
\begin{enumerate}
\item choose a $p$-position $i$;
\item for each $p[i]$-direction $a$:
\begin{enumerate}[label*=\arabic*.]
\item choose a $p$-position $i'$;
\item for each $p[i']$-direction $a'$:
\begin{enumerate}[label*=\arabic*.]
\item choose a $p$-position $i''$;
\item for each $p[i'']$-direction $a''$:
\begin{enumerate}[label*=\arabic*.]
\item choose a future.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{enumerate}
\item To choose an element of $p\tri p\tri\1$:
\begin{enumerate}
\item choose a $p$-position $i$;
\item for each $p[i]$-direction $a$:
\begin{enumerate}[label*=\arabic*.]
\item choose a $p$-position $i'$;
\item for each $p[i']$-direction $a'$:
\begin{enumerate}[label*=\arabic*.]
\item done.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{longenum}
\end{solution}
\end{exercise}
\index{future!as placeholder for dependency}
But how does the composition product act on lenses?
Given lenses $f\colon p\to p'$ and $g\colon q\to q'$, we can translate them to natural transformations, take their horizontal composite, then translate this back to a lens.
The following exercise guides us through this process.
\index{composition product!on lenses}
\begin{exercise}[The composition product of lenses] \label{exc.comp_prod_lens}
Fix lenses $f\colon p\to p'$ and $g\colon q\to q'$.
We seek to characterize their composition product $f\tri g\colon p\tri q\to p'\tri q'$.
\begin{enumerate}
\item\label{exc.comp_prod_lens.1} Use \cref{prop.morph_arena_to_func} to compute the $q(X)$-component of $f$ as a natural transformation.
\item\label{exc.comp_prod_lens.2} Use \cref{prop.poly_on_functions,prop.morph_arena_to_func} to compute $p'$ applied to the $X$-component of $g$ as a natural transformation.
\item\label{exc.comp_prod_lens.3} Combine \cref{exc.comp_prod_lens.1} and \cref{exc.comp_prod_lens.2} using \cref{def.horiz_comp_nat_trans} to compute the horizontal composite $f\tri g$ of $f$ and $g$ as natural transformations.
\item Use \cref{cor.morph_func_to_arena} to translate the natural transformation $f\tri g$ obtained in \cref{exc.comp_prod_lens.3} to a lens $p\tri q\to p'\tri q'$.
Verify that for each $(i,\ol{j}_i)$ in $(p\tri q)(\1)$ (see \eqref{eqn.comp_pos}), its on-positions function sends
\begin{equation} \label{eqn.comp_lens_pos}
(i,\ol{j}_i)\Mapsto{(f\:\tri\:g)_\1}\left(f_\1(i), f^\sharp_i\then\ol{j}_i\then g_\1\right);
\end{equation}
while for each $(a',b')$ in $(p'\tri q')[(f_\1(i), f^\sharp_i\then\ol{j}_i\then g_\1)]$ (see \eqref{eqn.comp_dir}), its on-directions function sends
\begin{equation} \label{eqn.comp_lens_dir}
(a',b')\Mapsto{(f\:\tri\:g)^\sharp_{(i,\ol{j}_i)}}\left(f^\sharp_i(a'), g^\sharp_{\ol{j}_i(f^\sharp_i(a'))}(b')\right).
\end{equation}
\qedhere
\end{enumerate}
\begin{solution}
We have lenses $f\colon p\to p'$ and $g\colon q\to q'$.
\begin{enumerate}
\item By \cref{prop.morph_arena_to_func}, the $q(X)$-component of $f$ is a function $f_{q(X)}\colon p(q(X))\to p'(q(X))$ that sends every $(i,h)$ with $i\in p(\1)$ and $h\colon p[i]\to q(X)$ to $(f_\1(i),f^\sharp_i\then h)$.
We can think of the function $h\colon p[i]\to q(X)$ equivalently as a function $\ol{j}_i\colon p[i]\to q(\1)$ and, for each $a\in p[i]$, a function $h_a\colon q[\ol{j}_i(a)]\to X$.
So $f_{q(X)}\colon (p\tri q)(X)\to (p'\tri q)(X)$ sends \[(i,\ol{j}_i,(h_a)_{a\in p[i]})\mapsto\left(f_\1(i),f^\sharp_i\then\ol{j}_i,\left(h_{f^\sharp_i(a')}\right)_{a'\in p'[f_\1(i)]}\right).\]
\item By \cref{prop.morph_arena_to_func}, the $X$-component of $g$ is a function $g_X\colon q(X)\to q'(X)$ that sends every $(j,k)$ with $j\in q(\1)$ and $k\colon q[j]\to X$ to $(g_\1(j),g^\sharp_j\then k)$ in $q'(X)$.
Then by \cref{prop.poly_on_functions}, applying $p'$ to this $X$-component yields a function $p'(q(X))\to p'(q'(X))$ that sends every $(i',\ol{j'}_{i'},(h'_{a'})_{a'\in p'[i']})$ with $i'\in p'(\1)$ as well as $\ol{j'}_{i'}\colon p'[i']\to q(\1)$ and $h'_{a'}\colon q[\ol{j'}_{i'}(a')]\to X$ to \[\left(i',\ol{j'}_{i'}\then g_\1,\left(g^\sharp_{\ol{j'}_{i'}(a')}\then h'_{a'}\right)_{a'\in p'[i']}\right).\]
\item By \cref{def.horiz_comp_nat_trans}, the horizontal composite of $f$ and $g$ is the natural transformation $f\tri g\colon p\tri p'\to q\tri q'$ whose $X$-component is the composite of the answers to \cref{exc.comp_prod_lens.1} and \cref{exc.comp_prod_lens.2}, sending
\begin{align*}
(i,\ol{j}_i,(h_a)_{a\in p[i]})&\mapsto\left(f_\1(i),f^\sharp_i\then\ol{j}_i,\left(h_{f^\sharp_i(a')}\right)_{a'\in p'[f_\1(i)]}\right)\\
&\mapsto\left(f_\1(i),f^\sharp_i\then\ol{j}_i\then g_\1, \left(g^\sharp_{\ol{j}_{i}(f^\sharp_i(a'))}\then h_{f^\sharp_i(a')}\right)_{a'\in p'[f_\1(i)]}\right).
\end{align*}
\item We use \cref{cor.morph_func_to_arena} to translate the answer to \cref{exc.comp_prod_lens.3} into a lens $f\tri g\colon p\tri q\to p'\tri q'$, as follows.
Its on-positions function is the $\1$-component $(f\tri g)_\1$, which sends every $(i,\ol{j}_i)$ with $i\in p(\1)$ and $\ol{j}_i\colon p[i]\to q(\1)$ to
\[
(f_\1(i),f^\sharp_i\then\ol{j}_i\then g_\1).
\]
Then for each such $(i,\ol{j}_i)$, if we apply the $(p\tri q)[(i,\ol{j}_i)]$-component of $f\tri g$ to the element $(i,\ol{j}_i,(\iota_d)_{a\in p[i]})$, where $\iota_d\colon q[\ol{j}_i(a)]\to(p\tri q)[(i,\ol{j}_i)]\iso\sum_{a\in p[i]}q[\ol{j}_i(a)]$ is the canonical inclusion, then take the last coordinate of the result, we obtain for each $a'\in p'[f_\1(i)]$ the function
\[
q'[g_\1(\ol{j}_i(f^\sharp_i(a')))] \To{g^\sharp_{\ol{j}_{i}(f^\sharp_i(a'))}} q[\ol{j}_i(f^\sharp_i(a'))] \To{\iota_{f^\sharp_i(a')}} \sum_{a\in p[i]}q[\ol{j}_i(a)] \iso (p\tri q)[(i,\ol{j}_i)].
\]
These can equivalently be thought of as a single function from
\[
\sum_{a'\in p'[f_\1(i)]} q'[g_\1(\ol{j}_i(f^\sharp_i(a')))] \iso (p'\tri q')[(f\tri g)_\1(i,\ol{j}_i)]
\]
which \cref{cor.morph_func_to_arena} tells us is the on-directions function of $f\tri g$ at $(i,\ol{j}_i)$, that sends every $(a',b')$ with $a'\in p'[f_\1(i)]$ and $b'\in q'[g_\1(\ol{j}_i(f^\sharp_i(a')))]$ to
\[
\left(f^\sharp_i(a'), g^\sharp_{\ol{j}_i(f^\sharp_i(a'))}(b')\right).
\]
\end{enumerate}
\end{solution}
\end{exercise}
So what does \cref{exc.comp_prod_lens} tell us about the behavior of $f\tri g\colon p\tri q\to p'\tri q'$?
By \eqref{eqn.comp_lens_pos}, on positions, $f\tri g$ takes a $p$-position $i$ and sends it to the $p'$-position $f_\1(i)$; then for each direction $a'$ at this position, the associated $q'$-position is obtained by sending $a'$ back to a $p[i]$-direction via $f^\sharp_i$, checking what $q$-position is associated to that $p[i]$-direction via some $\ol{j}_i$, then sending that $q$-position forward again to a $q'$-position via $g_\1$.
Then by \eqref{eqn.comp_lens_pos}, on directions, $f\tri g$ sends a direction of $p'$ back to a direction of $p$ via an on-directions function of $f$, then sends a direction of $q'$ back to a direction of $q$ via an on-directions funtion of $g$.
We'll get a better sense of what's happening when we see this drawn out as corolla forests in \cref{ex.comp_prod_trees}.
\subsection{Composition product on corolla forests} \label{subsec.comon.comp.def.corolla}
\index{composition product!grafting corollas}
It turns out that the forest of $p\tri q$ is given by grafting $q$-corollas onto the leaves of $p$-corollas in every possible way.
We will demonstrate this using an example.
Let's say $p\coloneqq\yon^\2+\yon$ and $q\coloneqq\yon^\3+\1$, whose corolla forests we draw as follows:\index{tree!depiction of}
\begin{equation}\label{eqn.pq_misc39}
\begin{tikzpicture}[rounded corners]
\node (p1) [draw, blue!50!black, "\color{blue!50!black} $p$" above] {
\begin{tikzpicture}[trees, sibling distance=2.5mm]
\node["\tiny 1" below] (1) {$\bullet$}
child {}
child {};
\node[right=.5 of 1,"\tiny 2" below] (2) {$\bullet$}
child {};
\end{tikzpicture}
};
%
\node (p2) [draw, red!75!black, right=2 of p1, "\color{red!75!black} $q$" above] {
\begin{tikzpicture}[trees, sibling distance=2.5mm]
\node["\tiny 1" below] (1) {$\bullet$}
child {}
child {}
child {};
\node[right=.5 of 1,"\tiny 2" below] (4) {$\bullet$}
;
\end{tikzpicture}
};
\end{tikzpicture}
\end{equation}
By \eqref{eqn.comp_pos}, choosing a position of $p \tri q$ amounts to first choosing a $p$-root $i$, then choosing a $q$-root for every $p[i]$-leaf.
So we may depict $(p \tri q)(\1)$ by grafting roots from the corolla forest of $q$ to leaves in the corolla forest of $p$ in every possible way, as follows:
\begin{equation}\label{eqn.comp_pos_forest}
\begin{tikzpicture}[rounded corners]
\node (p1) [draw, "``$(${\color{blue!50!black} $p$}$\:\tri\:${\color{red!75!black}$q$}$)(\1)$''" above] {
\begin{tikzpicture}[trees,
level 1/.style={sibling distance=8mm},
blue!50!black]
\node[blue!50!black, "\tiny 1" below] (1) {$\bullet$}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 1" above] {$\bullet$}}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 1" above] {$\bullet$}};
%
\node[blue!50!black, right=1.5 of 1, "\tiny 1" below] (2) {$\bullet$}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 1" above] {$\bullet$}}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 2" above] {$\bullet$}};
%
\node[blue!50!black, right=1.5 of 2, "\tiny 1" below] (3) {$\bullet$}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 2" above] {$\bullet$}}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 1" above] {$\bullet$}};
%
\node[blue!50!black, right=1.5 of 3, "\tiny 1" below] (4) {$\bullet$}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 2" above] {$\bullet$}}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 2" above] {$\bullet$}};
%
\node[blue!50!black, right=1.2 of 4, "\tiny 2" below] (5) {$\bullet$}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 1" above] {$\bullet$}};
%
\node[blue!50!black, right=1 of 5, "\tiny 2" below] (6) {$\bullet$}
child[blue!50!black] {node[red!75!black, "\color{red!75!black} \tiny 2" above] {$\bullet$}};
\end{tikzpicture}
};
\end{tikzpicture}
\end{equation}
Now fix one of the positions of $p \tri q$ drawn above: a $p$-root $i$ and a $q$-root grafted to every $p[i]$-leaf.
By \eqref{eqn.comp_dir}, a direction of $p \tri q$ at that position consists of a $p[i]$-leaf $a$ and a second leaf emanating from the $q$-root that has been grafted on to $a$.
In other words, in the following picture, where we have grafted not just $q$-roots but entire $q$-corollas onto leaves in $p$, the directions of $p \tri q$ at the position corresponding to each tree are the rooted paths\footnote{A \emph{rooted path} of a rooted tree is a path up the tree that starts from the root.} of that tree of length $2$ (we omit the labels):
\begin{equation}\label{eqn.prefered_composite}
\begin{tikzpicture}[rounded corners]
\node (p1) [draw, "``{\color{blue!50!black} $p$}$\:\tri\:${\color{red!75!black}$q$}''" above] {
\begin{tikzpicture}[trees,
level 1/.style={sibling distance=8mm},
level 2/.style={sibling distance=2.5mm},
blue!50!black]
\node[blue!50!black] (1) {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black]
child[red!75!black]
child[red!75!black]
}
child {node[red!75!black] {$\bullet$}
child[red!75!black]
child[red!75!black]
child[red!75!black]
};
%
\node[blue!50!black, right=1.7 of 1] (2) {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black]
child[red!75!black]
child[red!75!black]
}
child {node[red!75!black] {$\bullet$}
};
%
\node[blue!50!black, right=1.5 of 2] (3) {$\bullet$}
child {node[red!75!black] {$\bullet$}
}
child {node[red!75!black] {$\bullet$}
child[red!75!black]
child[red!75!black]
child[red!75!black]
};
%
\node[blue!50!black, right=1.5 of 3] (4) {$\bullet$}
child {node[red!75!black] {$\bullet$}
}
child {node[red!75!black] {$\bullet$}
};
%
\node[blue!50!black, right=1.2 of 4] (5) {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black]
child[red!75!black]
child[red!75!black]
};
%
\node[blue!50!black, right=1 of 5] (6) {$\bullet$}
child {node[red!75!black] {$\bullet$}
};
\end{tikzpicture}
};
\end{tikzpicture}
\end{equation}
Equivalently, we can think of the directions in the picture above as the leaves at the second level of each tree.
So $p \tri q$ has six positions; the first has six directions, the second, third, and fifth have three directions, and the fourth and sixth have no directions.
In total, we can read off that $p\tri q$ is isomorphic to $\yon^\6+\3\yon^\3+\2$.
\index{tree!multi-level}
We put the $p\tri q$ in scare quotes above \eqref{eqn.prefered_composite} because, to be pedantic, the corolla forest of $p \tri q$ has the two levels smashed together as follows:
\begin{equation}\label{eqn.actual_composite}
\begin{tikzpicture}[rounded corners]
\node (p1) [draw, "$p\tri q$" above] {
\begin{tikzpicture}[trees, sibling distance=2.5mm]
\node (1) {$\bullet$}
child {}
child {}
child {}
child {}
child {}
child {};
\node[right=1 of 1] (2) {$\bullet$}
child {}
child {}
child {};
\node[right=1 of 2] (3) {$\bullet$}
child {}
child {}
child {};
\node[right=1 of 3] (4) {$\bullet$};
\node[right=1 of 4] (5) {$\bullet$}
child {}
child {}
child {};
\node[right=1 of 5] (6) {$\bullet$};
\end{tikzpicture}
};
\end{tikzpicture}
\end{equation}
Usually, we will prefer the style of \eqref{eqn.prefered_composite} rather than the more pedantic style of \eqref{eqn.actual_composite}.
We have now seen how to draw a single polynomial as a corolla forest, with height-$1$ leaves as directions; as well as how to draw a two-fold composite of polynomials as a forest of trees, with height-$2$ leaves as directions.
Note that drawing a corolla of $p$ or a tree of $p\tri q$ is just a graphical way of following the instructions associated with the polynomial $p$ or $p\tri q$ that we saw in \cref{subsec.comon.comp.def.arena}, where the arrows---the top-level leaves---are where the ``futures'' would go.
Similarly, we could depict any $n$-fold composite as a forest with height-$n$ leaves as directions.
You'll have an opportunity to try this in the following exercise.
\index{future!as placeholder for dependency}
\begin{exercise}
Use $p,q$ as in \eqref{eqn.pq_misc39} and $r\coloneqq \2\yon+\1$ in the following.
\begin{enumerate}
\item Draw $q\tri p$.
\item Draw $p\tri p$.
\item Draw $p\tri p\tri \1$.
\item Draw $r\tri r$.
\item Draw $r\tri r\tri r$.
\qedhere
\end{enumerate}
\begin{solution}
We have $p \coloneqq \yon^\2 + \yon$ and $q \coloneqq \yon^\3 + \1$ as in \eqref{eqn.pq_misc39}.
\begin{enumerate}
\item Here is a picture of $q\tri p$, where each tree is obtained by taking a $q$-corolla and grafting $p$-corollas to every leaf:
\[
\begin{tikzpicture}[rounded corners]
\node (p1) [draw] {
\begin{tikzpicture}[trees,
level 1/.style={sibling distance=4mm},
level 2/.style={sibling distance=2.5mm},
red!75!black]
\node (1) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
};
%
\node[right=1.2 of 1] (2) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
};
%
\node[right=1.2 of 2] (3) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
};
%
\node[right=1.2 of 3] (4) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
};
\node[right=1.2 of 4] (5) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
};
\node[right=1.2 of 5] (6) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
};
\node[right=1.2 of 6] (7) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
child[blue!50!black]
};
%
\node[right=1.2 of 7] (8) {$\bullet$}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
child {node[blue!50!black] {$\bullet$}
child[blue!50!black]
};
%
\node[right=1 of 8] (9) {$\bullet$};
\end{tikzpicture}
};
\end{tikzpicture}
\]
\item Here is a picture of $p\tri p$:
\[
\begin{tikzpicture}[rounded corners]
\node (p1) [draw] {
\begin{tikzpicture}[trees,
level 1/.style={sibling distance=8mm},
level 2/.style={sibling distance=3mm},
blue!50!black]
\node[blue!50!black] (1) {$\bullet$}
child {node {$\bullet$}
child
child
}
child {node {$\bullet$}
child
child
};
%
\node[blue!50!black, right=1.5 of 1] (2) {$\bullet$}
child {node {$\bullet$}
child
child
}
child {node {$\bullet$}
child
};
%
\node[blue!50!black, right=1.5 of 2] (3) {$\bullet$}
child {node {$\bullet$}
child
}
child {node {$\bullet$}
child
child
};
%
\node[blue!50!black, right=1.5 of 3] (4) {$\bullet$}
child {node {$\bullet$}
child
}
child {node {$\bullet$}
child
};
%
\node[blue!50!black, right=1.2 of 4] (5) {$\bullet$}
child {node {$\bullet$}
child
child
};
%
\node[blue!50!black, right=1 of 5] (6) {$\bullet$}
child {node {$\bullet$}
child
};
\end{tikzpicture}
};
\end{tikzpicture}
\]
\item To obtain a picture of $p\tri p\tri\1$, we take our picture of $p\tri p$ and graft the single, leafless $\1$-root onto every (height-$2$) leaf:
\[
\begin{tikzpicture}[rounded corners]
\node (p1) [draw] {
\begin{tikzpicture}[trees,
level 1/.style={sibling distance=8mm},
level 2/.style={sibling distance=3mm},
blue!50!black]
\node[blue!50!black] (1) {$\bullet$}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
child {node[black] {$\bullet$}}
}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
child {node[black] {$\bullet$}}
};
%
\node[blue!50!black, right=1.5 of 1] (2) {$\bullet$}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
child {node[black] {$\bullet$}}
}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
};
%
\node[blue!50!black, right=1.5 of 2] (3) {$\bullet$}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
child {node[black] {$\bullet$}}
};
%
\node[blue!50!black, right=1.5 of 3] (4) {$\bullet$}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
};
%
\node[blue!50!black, right=1.2 of 4] (5) {$\bullet$}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
child {node[black] {$\bullet$}}
};
%
\node[blue!50!black, right=1 of 5] (6) {$\bullet$}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
};
\end{tikzpicture}
};
\end{tikzpicture}
\]
\end{enumerate}
Now $r\coloneqq \2\yon+\1$. Before we draw the composites, here's a picture of $r$ itself, with different colors to distinguish the different positions:
\[
\begin{tikzpicture}[rounded corners]
\node (p1) [draw] {
\begin{tikzpicture}[trees, sibling distance=2.5mm]
\node[blue!50!black] (1) {$\bullet$}
child[blue!50!black];
%
\node[right=.5 of 1, red!75!black] (2) {$\bullet$}
child[red!75!black];
%
\node[right=.5 of 2] (3) {$\bullet$};
\end{tikzpicture}
};
\end{tikzpicture}
\]
\begin{enumerate}[resume]
\item Here is a picture of $r\tri r$:
\[
\begin{tikzpicture}[rounded corners]
\node (p1) [draw] {
\begin{tikzpicture}[trees,
level 1/.style={sibling distance=8mm},
level 2/.style={sibling distance=2.5mm},
blue!50!black]
\node (1) {$\bullet$}
child {node {$\bullet$}
child
};
%
\node[right=.5 of 1] (2) {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black]
};
%
\node[right=.5 of 2] (3) {$\bullet$}
child {node[black] {$\bullet$}};
%
\node[right=.5 of 3, red!75!black] (4) {$\bullet$}
child[red!75!black] {node {$\bullet$}
child};
%
\node[right=.5 of 4, red!75!black] (5) {$\bullet$}
child[red!75!black] {node[red!75!black] {$\bullet$}
child[red!75!black]
};
%
\node[right=.5 of 5, red!75!black] (6) {$\bullet$}
child[red!75!black] {node[black] {$\bullet$}};
%
\node[right=.5 of 6, black] (7) {$\bullet$};
\end{tikzpicture}
};
\end{tikzpicture}
\]
\item Here is a picture of $r\tri r\tri r$:
\[
\begin{tikzpicture}[rounded corners]
\node (p1) [draw] {
\begin{tikzpicture}[trees,
level 1/.style={sibling distance=8mm},
level 2/.style={sibling distance=2.5mm},
blue!50!black]
\node (1) {$\bullet$}
child {node {$\bullet$}
child {node {$\bullet$}
child
}
};
%
\node[right=.5 of 1] (2) {$\bullet$}
child {node {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black]
}
};
%
\node[right=.5 of 2] (3) {$\bullet$}
child {node {$\bullet$}
child {node[black] {$\bullet$}}
};
%
\node[right=.5 of 3] (4) {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black] {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
};
%
\node[right=.5 of 4] (5) {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black] {node[red!75!black] {$\bullet$}
child[red!75!black]
}
};
%
\node[right=.5 of 5] (6) {$\bullet$}
child {node[red!75!black] {$\bullet$}
child[red!75!black] {node[black] {$\bullet$}}
};
%
\node[right=.5 of 6] (7) {$\bullet$}
child {node[black] {$\bullet$}};
%
\node[right=.5 of 7, red!75!black] (8) {$\bullet$}
child[red!75!black] {node[blue!50!black] {$\bullet$}
child[blue!50!black] {node[blue!50!black] {$\bullet$}
child[blue!50!black]
}
};
%
\node[right=.5 of 8, red!75!black] (9) {$\bullet$}
child[red!75!black] {node[blue!50!black] {$\bullet$}
child[blue!50!black] {node[red!75!black] {$\bullet$}
child[red!75!black]
}
};
%
\node[right=.5 of 9, red!75!black] (10) {$\bullet$}
child[red!75!black] {node[blue!50!black] {$\bullet$}
child[blue!50!black] {node[black] {$\bullet$}}
};
%