# WIP: A Unit Testing Framework for Self-Guided Personalized Online Robotics
Learning

Ponkoj Chandra Shill David Feil-Seifer This material is based upon work
supported by the National Science Foundation under Grants IIS-2150394,
DUE-2142360. Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation. Computer Science and
Engineering
University of Nevada, Reno,
Reno, NV, USA
<EMAIL_ADDRESS>—<EMAIL_ADDRESS>Jiullian-Lee Vargas Ruiz  Computer Science
University of Puerto Rico, Arecibo,
Arecibo, PR, USA
<EMAIL_ADDRESS>Rui Wu  Computer Science
East Carolina University,
Greenville, NC
<EMAIL_ADDRESS>
###### Abstract

Our ongoing development and deployment of an online robotics education
platform highlighted a gap in providing an interactive, feedback-rich learning
environment essential for mastering programming concepts in robotics, which
they were not getting with the traditional code-simulate-turn in workflow.
Since teaching resources are limited, students would benefit from feedback in
real-time to find and fix their mistakes in the programming assignments. To
address these concerns, this paper will focus on creating a system for unit
testing while integrating it into the course workflow. We facilitate this
real-time feedback by including unit testing in the design of programming
assignments so students can understand and fix their errors on their own and
without the prior help of instructors/TAs serving as a bottleneck. In line
with the framework’s personalized student-centered approach, this method makes
it easier for students to revise, and debug their programming work,
encouraging hands-on learning. The course workflow updated to include unit
tests will strengthen the learning environment and make it more interactive so
that students can learn how to program robots in a self-guided fashion.

###### Index Terms:

Undergraduate Robotics Education, Mini-course, Unit Testing, Personalized
Learning.

##  I Introduction

This paper shows work in progress on a unit-testing framework for programming
assignments in an online robotics education system. This project aims to
increase accessibility to a complete robotics education in remote community
institutions and help boost students’ performance by extending course content,
incorporating mathematical assessments and programming assignments, and, most
importantly, implementing a unit testing framework (Fig. 1). In software
development, unit testing refers to serve the purpose of isolating and testing
individual components like functions, methods, or objects to verify their
performance. Through writing and executing dedicated test cases for each
component, developers can detect and rectify errors at an early stage, thereby
enhancing code quality and reliability [1].

Figure 1: Online Learning Framework: Students can access the learning platform
from anywhere. Content and assignments are hosted in a platform server, where
the unit testing framework is being Implemented and students learn and do
their programming assignments in the platform server as a web-based
application and get feedback, grades, and progress through the platform.

We are elaborating on self-paced online course materials that can be deployed
at community colleges and universities with no robotics-trained experts. This
online content will be offered through a remote learning server where students
can access it through any device. The students can learn their choice of
robotics concepts using an online code editor in a virtual laboratory
environment. A major challenge for robotics courses in general (and for the
online robotics system we are developing, in particular [2]) is the labor- and
skill-intensive grading process. The proposed unit testing framework will
address grading and feedback challenges and assess this framework in our
online robotics course environment.

Student feedback from a prior study [2] with our online robotics education
system indicated that students were dissatisfied with the inability to
properly test their code while doing the assignments or before submission,
which led to increased errors and heightened frustration. Moreover, the
onerous task of manually grading these programming assessments has proven
cumbersome for instructors, creating bottlenecks that delay feedback and
undermine the learning process. Unit tests will allow students to receive
intermediate feedback while working on programming assignments, help them
center their efforts on the graded aspects of the assignments, and give them
the ability to test their code in real-time, which might significantly reduce
errors. This approach could also help automate the grading process, making it
easier for instructors and teaching staff who are less experienced in robotics
to provide timely but technically relevant feedback.

In this paper, we show the unit testing framework that will be integrated with
the programming assessments activities. These programming activities will be
given to the students after completing each module or topic to evaluate their
technical progress on robotics learning. We present two study designs to
examine this framework in student learning contexts.

##  II background

Robotics in education provides potential education benefits, positively
impacting students by enhancing critical thinking and problem-solving skills
[3, 4, 5, 6]. Delivering quality robotics education is challenging,
particularly in community colleges, where a scarcity of qualified robotics
instructors exists. Insufficient funding for specialized hardware and software
exacerbates this issue [7]. Additionally, students interested in robotics may
face financial barriers that prevent them from pursuing this field, given the
substantial costs associated with renting or purchasing robots and training
programs. We are working to bridge that gap through the creation of a self-
directed online robotics learning environment.

A current trend in e-learning is self-directed learning (SDL), where learners
take control over the conceptualization, design, implementation, and
evaluation of their learning. This corresponds with self-determination theory
[8], which emphasizes the importance of autonomy, competence, and relatedness
for continued intention, and has been proven to be productive in learning
environments. Self-direction is dependent on the learners’ motivation, self-
monitoring, and self-control [9]. Students have expressed that the process of
becoming a self-directed learner is difficult, frustrating and confusing.
Therefore, this developmental process should be understood and nurtured;
students need a guide for their learning journey that assists them through the
process, hence improving their experience and performance [10]. A self-
regulated e-learning framework can help reduce participation obstacles and
improve students’ access to quality robotics education.

In our earlier work [2], we introduced a novel strategy to enhance online
robotics education by implementing personalized learning approaches. A
personalized mini-course was designed that adapts content and pace to each
student’s individual needs. The course highlighted hands-on, problem-based
learning to cultivate practical skills, including programming assessments,
mathematical problem-solving, etc. Moreover, a thorough study was conducted to
evaluate the effectiveness of the framework in improving student engagement
and learning outcomes. The findings shed light on the scalability and broader
application potential of the framework in STEM education [2]. However,
students also reported being unsatisfied with the educational tools due to
technical issues and a lack of means to check or test their work during
programming assignments, hence the addition of a TDD-framework for programming
assignments.

Test-Driven Development (TDD) is a software engineering practice that
revolutionizes traditional programming methodologies by enforcing a ‘test-
first’ approach, a concept extensively advocated by Robert C. Martin [11]. In
TDD, developers begin by writing automated tests for a new feature before any
functional code is created. This involves a cycle of writing a test, verifying
that it fails, writing the necessary code to pass the test, and refining the
code to enhance its structure and efficiency. Unit testing is a crucial step
that involves examining individual components, such as methods or object
classes, to guarantee their proper functioning before being incorporated into
larger systems [1], identifying errors early in the development process, which
simplifies debugging and enhances the overall quality of the software. Unit
testing not only promotes rigorous validation of software behavior under
predictable conditions but also under simulated events, utilizing mock objects
when necessary. Automating unit testing through frameworks is particularly
effective, as it enables rapid testing and feedback cycles, thus reducing the
risks associated with integration and helping to maintain high standards of
software reliability and maintainability.

Figure 2: Left- The Prior System Workflow; Right- Proposed Workflow
incorporating Unit Testing Framework, in this system, students can test their
code and get intermediate feedback, which helps them iteratively improve their
robot’s behavior and their programming skills prior to submitting the
assignment

##  III Approach

We designed a test-driven development (TDD) framework to provide students with
predefined unit tests that accompany each programming task for every topic.
These tests will be embedded within our web-based virtual laboratory [12],
integrating into the overall workflow. In this section, we present the current
course module design, as well as our TDD-based changes to this course
workflow, including the feedback that we can provide to students, shown in
Fig. 2.

###  III-A Virtual Laboratory

This module is where students will complete their programming assessments.
After finishing each course topic, students will be redirected to the web-
based application, where they will encounter programming assignments presented
as questions or problems. The platform will feature a split-screen interface,
with the code editor on the left side and a virtual robot or object on the
right, visually simulating or demonstrating the code’s effect in real-time,
shown in Fig. 3.

Figure 3: Prototype of the virtual laboratory interface. The virtual
laboratory includes a code editor on the left, real-time simulation on the top
right, and a feedback window on the bottom right. Students get intermediate
feedback, grades, and real-time simulations in the same terminal.

In this virtual environment simulates real-world robots and their sensors in a
web-based environment. For example, in the programming assignment for the
obstacle avoidance lesson, students can program the robot to navigate through
complex environments, avoiding obstacles and following specified paths. This
includes activities such as maze solving, where the robot must find its way
through a maze using various algorithms, and terrain traversal, where the
robot navigates different types of surfaces and elevations. The virtual robot
will also be capable of performing sensor-based tasks, allowing students to
integrate and process data from virtual sensors like ultrasonic, infrared, or
LIDAR sensors.

For the robot to execute path planning and motion control activities, students
would have to program it to calculate and follow the most efficient route from
one point to another, considering various constraints and dynamic changes in
the environment. This will help students learn about path-finding and motion
control algorithms, such as A* or Dijkstra’s algorithms or bug algorithms. The
virtual laboratory also supports interactive debugging and iterative
development. As students write their code, they will see the robot’s actions
in real time on the simulation screen. If the robot’s behavior deviates from
expectations, students can immediately adjust their code and observe the
changes, fostering a deeper understanding of the relationship between code and
robotic behavior.

###  III-B Assessment

Programming assignment assessments cover theoretical, mathematical, and
practical programming tasks to comprehensively assess students’ understanding.
For example, in the “Obstacle Avoidance” topic, students encounter various
programming assignments. One example is a scenario where they must program a
mobile robot using the Bug algorithm [13] to navigate a 2D environment. The
starting and goal points and the obstacle’s position are provided. The robot
must follow the obstacle’s edge until it can resume its path to the goal. It
always turns right when encountering the obstacle and follows the Bug
algorithm perfectly.

Students need to calculate the total path length the robot takes to reach the
goal, including the detour. They must provide their answer as an expression
that includes the perimeter of the obstacle the robot follows and the
straight-line paths before and after the detour. The major items being
assessed in this assignment include the student’s ability to:

  * •

Implement the bug algorithm correctly to navigate around obstacles.

  * •

Ensure writing code that the robot consistently follows the edge of the
obstacle without collisions.

  * •

Calculate the total path length accurately, including both the detour around
the obstacle and the straight-line paths.

  * •

Apply mathematical concepts to provide a precise expression of the path
length.

  * •

Debug and refine their code based on the real-time feedback provided by the
unit testing framework.

###  III-C Unit testing framework

We modify the above workflow to include a unit testing framework to evaluate
the provided code or programming assignments. We integrate a series of unit
tests conducted at intermediate points and upon submission of the assignment
to evaluate the program’s functionality. This framework will be able to
provide immediate feedback, highlighting errors and offering suggestions as
students write their code. For example, in the obstacle avoidance assignment
using bug algorithm, the unit testing is designed in such a way that it checks
different aspects of the solution to the problem:

  * •

The robot does not hit any obstacles while it moves;

  * •

The robot does not stop at all;

  * •

The robot makes right turns only at the edge of obstacles;

  * •

The robot is moving smoothly; and

  * •

The robot has reached the goal point.

If a coding error induces unwanted behavior, such as the robot hitting an
obstacle or stopping prematurely, the unit test will identify these issues.
For instance, if the robot’s code causes it to collide with an obstacle, the
unit test designed to verify obstacle avoidance will fail. This failure will
be highlighted to the student in the simulation panel and code editor both,
indicating that the robot’s movement logic needs revision. The test results
will show which specific conditions were not met, providing clear indicators
of where the code deviates from expected behavior. This immediate notification
of test failures helps students pinpoint and correct their mistakes,
facilitating a deeper understanding of programming concepts and improving
their coding skills.

###  III-D Feedback System

The unit testing system incorporates with feedback system, which provides
immediate, objective feedback on the assignment goals. This feedback will be
presented in a window that displays the executed tests and indicates which
ones passed or failed, shown in Fig. 4. Students will also have the option to
review the details of each test for further understanding and improvement.
Moreover, the detailed feedback from each test allows students to understand
specific areas of strength and weakness, fostering a deeper comprehension of
programming concepts and improving their ability to write robust code.

Figure 4: Feedback window prototype showing test results. Students can review
the details of the executed tests. The system will show the purpose,
requirements and outputs of the tests. On the other hand, the system provides
feedback on how the student can verify and correct potential errors.

##  IV Proposed Validation and Study

We first plan a formative study to demonstrate the proper operation of the
TDD-based feedback system and its overall utility in the virtual laboratory
environment. We plan to do a between-participants study. The control group
will use the traditional virtual lab environment to complete a programming
assignment; the experimental group will use the test-driven virtual lab
environment. We will compare the resultant programs for each group, looking
at:

  * •

program correctness;

  * •

number of iterations testing code before submission;

  * •

student sentiment with the programming experience; and

  * •

assignment grader ease with grading.

These above items will help assess how well the students perform, how long it
takes them to complete assignments, how students feel about the experience,
and whether graders feel the test-based method is more efficient.

A comprehensive validation of the proposed system, featuring the virtual
laboratory and the integrated unit testing framework, will be conducted with
participants enrolled in a full-semester self-paced robotics course. Prior to
the course, students will undergo a diagnostic test to assess their baseline
knowledge of mathematical concepts and robotics. Additionally, a survey will
be administered to gauge students’ prior experiences and preferences in online
courses.

To assess the effectiveness of the proposed system, a regular class will serve
as a control group to compare the results of students using the proposed
system to those in a traditional linear robotics course. Before the start of
the full course, both groups will take the same diagnostic test and pre-
survey. After the course ends, they will take the same summative assessment
and post-survey. The analysis will assess student satisfaction, subject matter
mastery, and the level of autonomy in learning to gauge the effectiveness of
the proposed approach.

A post-course survey will also include a section to gather feedback on the
effectiveness of the unit testing framework in assisting students with their
assignments. The survey will assess students’ motivation and satisfaction with
the test-driven development (TDD) approach and the virtual lab web-based
application implemented in the self-paced course.

This validation study aims to provide valuable insights into the efficacy of
the self-paced robotics course compared to the traditional linear approach,
based on concrete data and participant feedback. By synchronizing the
evaluation of the TDD approach, we will be able to determine how the
continuous, real-time feedback and iterative problem-solving facilitated by
the unit testing framework impact student learning outcomes and overall course
satisfaction.

##  V Conclusion and Future Direction

This paper demonstrates the development of a unit testing framework within a
self-guided, personalized online robotics learning environment. The
integration with the virtual laboratory addresses significant challenges in
online robotics education, such as providing timely and actionable feedback,
enhancing the learning experience, and reducing the manual grading burden on
instructors. By offering real-time, interactive feedback through the unit
testing framework, students can iteratively debug and refine their code,
leading to a deeper understanding of robotics programming concepts and
improved problem-solving skills.

The proposed system’s effectiveness will be validated through a comprehensive
study comparing the self-paced robotics course with a traditional linear
robotics course. Key factors such as student satisfaction, mastery of the
subject matter, and level of autonomy in learning will be assessed to gauge
the impact of the unit testing framework and the virtual lab on student
learning outcomes. This study aims to provide valuable insights into the
efficacy of the proposed approach, offering concrete data and participant
feedback to support the broader application of such systems in robotics
education.

## References

  * [1] Ian Sommerville,  Software Engineering,  Pearson, Boston, MA, USA, 10 edition, 2015.
  * [2] Ponkoj Chandra Shill, Rui Wu, Hossein Jamali, Bryan Hutchins, Sergiu Dascalu, Frederick C Harris, and David Feil-Seifer,  “Wip: Development of a student-centered personalized learning framework to advance undergraduate robotics education,”  in 2023 IEEE Frontiers in Education Conference (FIE). IEEE, 2023, pp. 1–5.
  * [3] Soumela Atmatzidou and Stavros Demetriadis,  “Advancing students’ computational thinking skills through educational robotics: A study on age and gender relevant differences,”  Robotics and Autonomous Systems, vol. 75, pp. 661–670, 2016.
  * [4] Barbara Ericson and Tom McKlin,  “Effective and sustainable computing summer camps,”  in Proceedings of the 43rd ACM technical symposium on Computer Science Education, 2012, pp. 289–294.
  * [5] Ronald I Greenberg and George K Thiruvathukal,  “Exercises integrating high school mathematics with robot motion planning,”  in 2019 IEEE Frontiers in Education Conference (FIE). IEEE, 2019, pp. 1–5.
  * [6] Juan Fasola, David Feil-Seifer, and Maja Matarić,  “Robotics as a tool for immersive, hands-on freshman engineering instruction,”  in American Society for Engineering Education Proceedings of the ASEE Annual Conference & Exposition, Pittsburgh, PA, July 2008.
  * [7] Mercedes Anderson, Blanca Miller, Adam Kirn, Melissa Jurkiewicz, and David Feil-Seifer,  “Making in the middle: Robots and sequences,”  ScienceScope, February 2019.
  * [8] Edward L Deci and Richard M Ryan,  Intrinsic Motivation and Self-Determination in Human Behavior,  Plenum, 1985.
  * [9] Evren Sumuer,  “Factors related to college students’ self-directed learning with technology,”  Australasian Journal of Educational Technology, vol. 34, no. 4, 2018.
  * [10] Ola I Lunyk-Child, Dauna Crooks, Patricia J Ellis, Cottie Ofosu, Linda O’Mara, and Elizabeth Rideout,  “Self-directed learning: Faculty and student perceptions,” 2001.
  * [11] Robert C. Martin,  The Clean Coder: A Code of Conduct for Professional Programmers,  Prentice Hall, Upper Saddle River, NJ, USA, 2011.
  * [12] Rui Wu, Sergiu Dascalu, Zhen Zhu, Marjorie Campo Ringler, Bryan Hutchins, David Feil-Seifer, Laura Rosof, Ponkoj Chandra Shill, Hossein Jamali, and Frederick C Harris,  “Undergraduate robotics education with general instructors using a student-centered personalized learning framework,”  in 2024 American Society for Engineering Education Annual Conference. June 2024, ASEE.
  * [13] Qi-Lei Xu, Tao Yu, and Jie Bai,  “The mobile robot path planning with motion constraints based on bug algorithm,”  in 2017 Chinese Automation Congress (CAC). IEEE, 2017, pp. 2348–2352.


width $u=O((4k)^{q+1}/\epsilon)$ such that $L_{\infty}{f^{k},g}\leq\epsilon$.
Moreover, if $f=f_{\text{tent},r}$, then there exists $g$ of width
$O((4k)^{q+1})$ with $g=f^{k}$.

###### Proof.

This part follows the bound on monotone pieces of $f^{k}$ given in Proposition
4 and a simple neural network approximation bound.

######  Lemma 8.

Consider some continuous $f:[0,1]\to[0,1]$ with $M(f)\leq m$. For any
$\epsilon\in(0,1)$, there exists $g\in\mathcal{N}(u,2)$ of width
$u=O(\frac{m}{\epsilon})$ such that $L_{\infty}(f,g)\leq\epsilon.$

###### Proof.

A monotone function mapping to $[0,1]$ can be $\epsilon$-approximated by a
piecewise-linear function with $O(\frac{1}{\epsilon})$ pieces, and hence, a
2-layer ReLU network of width $O(\frac{1}{\epsilon})$.

Every monotone piece can be approximated as such, which means that $g$ has
width $O(\frac{m}{\epsilon})$. ∎

For the case where $f=f_{\text{tent},r}$ for some $r$, it is always true that
$\left|\frac{d}{dx}f_{\text{tent},r}^{k}(x)\right|=(2r)^{k}$, except when $x$
is a local maximum or minimum. Thus, every monotone piece of $f^{k}$ is
linear, and $f$ can be exactly expressed with a piecewise linear function with
$O((4q)^{k+1})$ pieces, and also a ReLU neural network of width
$((4q)^{k+1})$. ∎

###  D.5 Proof of Theorem 8, Claim 4

Recall that for unimodal $f:[0,1]\to[0,1]$ and threshold $t\in(0,1)$,

$\mathcal{H}_{f,t}:=\\{[[f^{k}]]_{t}:k\in\mathbb{N}\\}$

is the hypothesis class under consideration.

######  Proposition 7 (Claim 4 of Theorem 8).

Suppose $f$ is a symmetric unimodal mapping whose maximal cycle is of length
$p=2^{q}$. For any $t\in(0,1)$, $\text{VC}(\mathcal{H}_{f,t})\leq 18p^{2}$.

This proof is involved and requires some setup and new definitions.

####  D.5.1 Notation

Let $\\{0,1\\}^{\mathbb{N}}$ represent all countable infinite sequences of
Boolean values, and let $\\{0,1\\}^{*}$ represent all finite sequences
(including the empty sequence).

For $y\in\\{0,1\\}^{\mathbb{N}}$, let
$y_{i:j}=(y_{i},\dots,y_{j})\in\\{0,1\\}^{j-i+1}$ and
$y_{i:}=(y_{i},y_{i+1},\dots)\in\\{0,1\\}^{\mathbb{N}}$. For
$w\in\\{0,1\\}^{n},w^{\prime}\in\\{0,1\\}^{n^{\prime}}$, let
$ww^{\prime}=w\circ w^{\prime}\in\\{0,1\\}^{n+n^{\prime}}$ be their
concatenation. Let $w^{j}=w\circ w\circ\dots\circ w\in\\{0,1\\}^{jn}$.

####  D.5.2 Iterated Boolean-Valued Functions, Regular Expressions, and VC-
Dimension

Before we give the main result, we give a way to upper-bound the VC-dimension
of countably infinite hypothesis classes
$\mathcal{H}=\\{h_{1},h_{2},\dots,\\}\subseteq([0,1]\to\\{0,1\\})$. For some
$x\in\mathcal{X}$, define ${s}_{\mathcal{H}}:[0,1]\to\\{0,1\\}^{\mathbb{N}}$
as ${s}_{\mathcal{H}}(x)=(h_{i}(x))_{i\in\mathbb{N}}$. We by $\mathcal{H}$
over all choices of $x\in[0,1]$:

$\mathcal{S}_{\mathcal{H}}=\\{{s}_{\mathcal{H}}(x):\
x\in[0,1]\\}\subset\\{0,1\\}^{\mathbb{N}}.$

With this notation, $\mathcal{H}$ shatters $d$ points if and only if there
exist $y^{(1)},\dots,y^{(d)}\in\mathcal{S}_{\mathcal{H}}$ such that
$|\\{(y^{(1)}_{j},\dots,y^{(n)}_{j}):j\in\mathbb{N}\\}|=2^{d}$. We
equivalently say that $y^{(1)},\dots,y^{(d)}$ are shattered.

Here’s where the idea of Regular Expressions (Regexes) comes in. If we can
show all elements in $\mathcal{S}_{\mathcal{H}}$ are represented by some
infinite-length Regex, then we can upper-bound the number of points
$\mathcal{H}$ can shatter, which is necessary to bound the expressive capacity
of unimodal functions with recursive properties.

To that end, we first introduce a different notion of shattering. Then, we’ll
give an upper-bound for the VC-dimension of $\mathcal{H}$ when we have a Regex
for $\mathcal{S}_{\mathcal{H}}$.

######  Definition 11.

We say that $\mathcal{H}$ (or $\mathcal{S}_{\mathcal{H}}$) weakly shatters $d$
points if there exist $w^{(1)}\circ y^{(1)},\dots,w^{(d)}\circ
y^{(d)}\in\mathcal{S}_{\mathcal{H}}$ for
$w^{(1)},\dots,w^{(d)}\in\\{0,1\\}^{*}$ such that $y^{(1)},\dots,y^{(d)}$ are
shattered. Let the weak VC-dimension of $\mathcal{H}$ represent the maximum
number of points $\mathcal{H}$ can weakly shatter and denote it
$\text{VC}_{\text{weak}}(\mathcal{H})=\text{VC}_{\text{weak}}(\mathcal{S}_{\mathcal{H}})$.

Using this notation, we can extend our notion of weak VC-dimension to any
subset of $\\{0,1\\}^{\mathbb{N}}$, whether or not it corresponds to a
hypothesis class. If $\mathcal{H}\subset S\subset\\{0,1\\}^{\mathbb{N}}$, then
$\text{VC}_{\text{weak}}(\mathcal{H})\leq\text{VC}_{\text{weak}}(S)$.

Note that if $\mathcal{H}$ shatters $d$ points, then it also trivially weakly
shatters $d$ points. We can get this by taking $w_{1}=\dots,w_{d}$ to be the
empty strings. Thus, the
$\text{VC}(\mathcal{H})\leq\text{VC}_{\text{weak}}(\mathcal{H})$.

A Regex is a recursively defined subset of $\\{0,1\\}^{\mathbb{N}}$ that can
be represented by a string. We describe how a Regex
$R\subseteq\\{0,1\\}^{\mathbb{N}}$ can be defined below.

  * •

One way to define a Regex is with a repeating sequence $w^{\infty}$ for
$w\in\\{0,1\\}^{n}$. That is,

$w^{\infty}=\\{y\in\\{0,1\\}^{\mathbb{N}}:y_{in+1:(i+1)n}=w,\forall
i\in\mathbb{N}\\}.$

For instance, $(011)^{\infty}=\\{(0,1,1,0,1,1,0,1,1,\dots)\\}$.

  * •

For $w\in\\{0,1\\}^{n}$, if $R$ is a Regex, then $wR$ is also a Regex. This
means satisfying sequences must start with $w$ and then the remainder of the
bits must satisfy $R$.

$wR=\\{y\in\\{0,1\\}^{\mathbb{N}}:y_{1:n}=w,y_{n+1:}\in R\\}.$

  * •

$w^{*}R$ is also a Regex, where $w^{*}$ represents any number of recurrences
of the finite sequence $s$. That is,

$w^{*}R=\cup_{j=0}^{\infty}w^{j}R.$

  * •

If $R^{\prime}$ is also a Regex, then so is $R\cup R^{\prime}$.

  * •

If $R^{\prime}$ is also a Regex, then so is $R\oplus R^{\prime}$, where the
odd entries of sequences in $R\oplus R^{\prime}$ concatenated together must be
in $R$ and the even entries must be in $R^{\prime}$.

$R\oplus R^{\prime}=\\{y\in\\{0,1\\}^{\mathbb{N}}:y_{1,3,5,\dots}\in
R,y_{2,4,6,\dots}\in R^{\prime}\\}.$

Now, we can create a recursive upper-bound on the number of points
$\mathcal{H}$ can weakly shatter. To do so, we assume that
$\mathcal{H}\subseteq R$ for some Regex $R$ and bound the weak VC dimension of
$R$.

######  Lemma 9.

Consider infinite-length Regexes $R,R^{\prime},R^{\prime\prime}$ and
$w\in\\{0,1\\}^{n}$.

  1. 1.

If $R=w^{\infty}$, then $\text{VC}_{\text{weak}}(R)\leq\log_{2}n$.

  2. 2.

If $R=wR^{\prime}$, then
$\text{VC}_{\text{weak}}(R)\leq\text{VC}_{\text{weak}}(R^{\prime})+\log_{2}n+1$.

  3. 3.

If $R=w^{*}R^{\prime}$, then
$\text{VC}_{\text{weak}}(R)\leq\text{VC}_{\text{weak}}(R^{\prime})+\log_{2}n+1$.

  4. 4.

If $R=R^{\prime}\cup R^{\prime\prime}$, then
$\text{VC}_{\text{weak}}(R)\leq\text{VC}_{\text{weak}}(R^{\prime})+\text{VC}_{\text{weak}}(R^{\prime\prime})$.

  5. 5.

If $R=R^{\prime}\oplus R^{\prime\prime}$, then $\text{VC}_{\text{weak}}(R)\leq
4\max(\text{VC}_{\text{weak}}(R^{\prime}),\text{VC}_{\text{weak}}(R^{\prime\prime}))+2$.

###### Proof.

  1. 1.

If $R=w^{\infty}$, then the set $Y=\\{y:w\circ y\in
w^{\infty},w\in\\{0,1\\}^{*}\\}$ contains at most $n$ elements. Hence,

$\left|\\{(y^{(1)}_{j},\dots,y^{(d)}_{j}):j\in\mathbb{N}\\}\right|\leq n$

for any fixed $y^{(1)},\dots,y^{(d)}\in Y$, and no more than $d=\log_{2}n$
points can be weakly shattered.

  2. 2.

Suppose $R$ weakly shatters $d$ points, so $y^{(1)},\dots,y^{(d)}$ are
shattered for some $w^{(1)}\circ y^{(1)},\dots,w^{(d)}\circ y^{(d)}\in R$. If
$Y=\\{(y^{(1)}_{j},\dots,y^{(d)}_{j}):j\in\mathbb{N}\\}$ and
$Y_{n}=\\{(y^{(1)}_{j},\dots,y^{(d)}_{j}):j\leq n\\}$, then $|Y|=2^{d}$ and
$|Y_{n}|\leq n$. There exists some $v\in\\{0,1\\}^{1+\log_{2}n}$ such that
$v\circ\sigma\in Y\setminus Y_{n}$ for all
$\sigma\in\\{0,1\\}^{d-1-\log_{2}n}$. Therefore,

$|\\{(y^{(2+\log_{2}n)}_{j},\dots,y^{(d)}_{j}):j>n\\}|=2^{d-1-\log_{2}n},$

and there exist $d-1-\log_{2}n$ points that can be weakly shattered by
$R^{\prime}$, since none of the labelings with $w$ are necessary.

  3. 3.

Once again, suppose $R$ weakly shatters $d$ points, $y^{(1)},\dots,y^{(d)}$
for $w^{(1)}\circ y^{(1)},\dots,w^{(d)}\circ y^{(d)}\in R$. Because each
$w^{(i)}\circ y^{(i)}\in w^{*}R^{\prime}$, there exists an index $\ell_{i}$
such that $(w^{(i)}\circ y^{(i)})_{1:\ell_{i}}=w^{\ell_{i}/n}$ and
$(w^{(i)}\circ y^{(i)})_{\ell_{i}+1:}\in R^{\prime}$. Without loss of
generality, assume $y^{(1)},\dots,y^{(d)}$ are ordered such that
$\ell_{i}-\left|w^{(i)}\right|$ decreases. That is, the first $1+\log_{2}n$
sequences are the ones that “leave $w^{*}$ last.” Let
$\ell^{*}:=\ell_{1+\log_{2}n}-\left|w^{(1+\log_{2}n)}\right|$. Define $Y$ and
$Y_{\ell^{*}}$ analogously to the previous part and note that $|Y|=2^{d}$.
Because $Y_{\ell^{*}}$ corresponds only to labelings where the first
$1+\log_{2}n$ elements come from subsets of $w^{\infty}$, there exists some
$v\in\\{0,1\\}^{1+\log_{2}n}$ such that $v\circ\sigma\in Y\setminus
Y_{\ell^{*}}$ for all $\sigma\in\\{0,1\\}^{d-1-\log_{2}n}$. As before, there
exist $d-1-\log_{2}n$ points that can be weakly shattered by $R^{\prime}$

  4. 4.

There is no set of $\text{VC}_{\text{weak}}(R^{\prime})+1$ and
$\text{VC}_{\text{weak}}(R^{\prime\prime})+1$ points that can be weakly
shattered by $R^{\prime}$ and $R^{\prime\prime}$ respectively. Any
$\text{VC}_{\text{weak}}(R^{\prime})+\text{VC}_{\text{weak}}(R^{\prime\prime})+1$
points in $R$ must have at either $\text{VC}_{\text{weak}}(R^{\prime})+1$
points in $R^{\prime}$ or $\text{VC}_{\text{weak}}(R^{\prime\prime})+1$ points
in $R^{\prime\prime}$. Thus, at least one subset cannot be shattered.

  5. 5.

Suppose without loss of generality that
$d:=\text{VC}_{\text{weak}}(R^{\prime})\geq\text{VC}_{\text{weak}}(R^{\prime\prime})$.
Consider any $w^{(1)}\circ y^{(1)},\dots,w^{(d)}\circ y^{(4d+3)}\in R$. WLOG,
assume that $\left|w^{(1)}\right|,\dots,\left|w^{(2d+2)}\right|$ are even,
which implies that $w^{(1)}_{\text{odd}}\circ y^{(1)}_{\text{odd}},\dots
w^{(2d+2)}_{\text{odd}}\circ y^{(2d+2)}_{\text{odd}}\in R^{\prime}$ and
$w^{(1)}_{\text{even}}\circ y^{(1)}_{\text{even}},\dots
w^{(2d+2)}_{\text{even}}\circ y^{(2d+2)}_{\text{even}}\in R^{\prime\prime}$.
Therefore,

$\displaystyle\left|\\{(y^{(1)}_{j},\dots,y^{(4d+3)}_{j}):j\in\mathbb{N}\\}\right|$
$\displaystyle\leq
2^{2d+1}\left|\\{(y^{(1)}_{j},\dots,y^{(2d+2)}_{j}):j\in\mathbb{N}\\}\right|$
$\displaystyle\leq
2^{2d+1}\left(\left|\\{(y^{(1)}_{j},\dots,y^{(2d+2)}_{j}):j\in\mathbb{N}_{\text{odd}}\\}\right|+\left|\\{(y^{(1)}_{j},\dots,y^{(2d+1)}_{j}):j\in\mathbb{N}_{\text{even}}\\}\right|\right)$
$\displaystyle\leq 2^{2d+1}\cdot 2\sum_{i=0}^{d}{2d+2\choose i}<2^{2d+2}\cdot
2^{2d+1}=2^{4d+3}.$

The last line follows by the Sauer Lemma. Thus, $R$ cannot shatter $4d+3$
points if $R^{\prime}$ and $R^{\prime\prime}$ cannot shatter $d$ points.

∎

Here’s an example of how to apply our regex rules:

$\displaystyle\text{VC}_{\text{weak}}(1^{*}0(01)^{\infty}\cup 10^{\infty})$
$\displaystyle\leq\text{VC}_{\text{weak}}(1^{*}0(01)^{\infty})+\text{VC}_{\text{weak}}(10^{\infty})$
$\displaystyle\leq
1+\text{VC}_{\text{weak}}(0(01)^{\infty})+1+\text{VC}_{\text{weak}}(0^{\infty})$
$\displaystyle\leq 2+1+\text{VC}_{\text{weak}}((01)^{\infty})$
$\displaystyle\leq 3+1=4.$

####  D.5.3 Proof of the Proposition 7

Recall that we consider the hypothesis class

$\mathcal{H}_{f,t}:=\\{[[f^{k}]]_{t}:k\in\mathbb{N}\\}$

for symmetric unimodal $f$ and $t\in(0,1)$.

To build up the argument, we first bound the VC-dimension for two simple
cases.

  * •

First, we consider the case when $f$ has no fixed point. Thus, for all
$x\in(0,1]$, $f(x)<x$, which means that the sequence $f(x),f^{2}(x),\dots$ is
decreasing.

If the threshold $t$ is $0$ or is greater than $f(\frac{1}{2})$, then the
sequence will be all 0’s or 1’s, which will imply that
$\text{VC}(\mathcal{H}_{f,t})=0$. Thus, the only interesting thresholds are
$t\in(0,f(\frac{1}{2})]$. Because the sequence is decreasing,
$\mathcal{S}_{\mathcal{H}_{f,t}}=1^{*}0^{\infty}$. From Lemma 9,
$\text{VC}(\mathcal{H}_{f,t})\leq\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})\leq
1$.

  * •

Let $x_{1}<\dots<x_{m}$ be all the fixed points of $f$. Suppose
$x_{m}\leq\frac{1}{2}$. By symmetry, for all $j\in[m]$, $f(1-x_{j})=x_{j}$.

To analyze this function, we partition $[0,1]$ into $2m+2$ intervals:
$I_{0}=[0,x_{1}),I_{0}^{\prime}=(1-x_{1},1]$, $I_{m}=[x_{m},\frac{1}{2}]$,
$I_{m}^{\prime}=(\frac{1}{2},1-x_{m}]$, $I_{j}=[x_{j},x_{j+1})$, and
$I_{j}^{\prime}=(1-x_{j+1},1-x_{j}]$ for all $j\in\\{1,\dots,m-1\\}$
(visualized in Figure 18).

$x$$f(x)$$x_{1}$$I_{0}$$I_{1}$$I_{0}$$I_{1}$$I_{2}$$x_{2}$$1/2$$1-x_{2}$$1-x_{1}$$I_{2}$$I_{2}^{\prime}$$I_{1}^{\prime}$$I_{0}^{\prime}$$I_{0}^{\prime}$$I_{1}^{\prime}$$I_{2}^{\prime}$
Figure 18: A plot of $f$ with fixed point $m=2$ fixed points—both less than
$\frac{1}{2}$—subdivided into intervals. The relationships of which intervals
$f$ maps onto one another are also visualized.

Because $f$ is unimodal and because the edges of all intervals map to fixed
points, for all $j\in\\{0,\dots,m\\}$, $f(I_{j}^{\prime})=f(I_{j})=I_{j}$. In
this case, it must be the case that $q=0$ because $f$ cannot have a 2-cycle.
Such a cycle is impossible because it would have to be contained entirely in
some $I_{j}$. In those intervals, it must be the case that either $\forall
x\in I_{j}$, $f(x)\geq x$, or $\forall x\in I_{j}$, $f(x)\leq x$ (if this were
not the case, then this would imply the existence of a fixed point other than
$x_{j}$ in $I_{j}$). Thus, cyclic behavior within an interval is impossible.

Thus, we can construct a Regex to represent the itinerary of any $x\in[0,1]$:
$\bigcup_{j=0}^{m}I_{j}^{\infty}$.131313 This is a massive abuse of notation,
but we use the same Regex notation to denote the intervals that are traversed
as we use to denote the values of Boolean sequence. Now, we consider all
possible locations of threshold $t$:

    * –

If $t\in I_{j}$, such that $f(x)\geq x$ for $x\in I_{j}$, then
$\mathcal{S}_{\mathcal{H}_{f,t}}\subseteq 0^{*}1^{\infty}\cup 0^{\infty}\cup
1^{\infty}$. By Lemma 9, $\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})\leq 1$.

    * –

If $t\in I_{j}$, such that $f(x)\leq x$ for $x\in I_{j}$, then
$\mathcal{S}_{\mathcal{H}_{f,t}}\subseteq 1^{*}0^{\infty}\cup 0^{\infty}\cup
1^{\infty}$. By Lemma 9, $\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})\leq 1$.

    * –

If $t\in\bigcup_{j=0}^{m}I_{j}^{\prime}$, then
$\mathcal{S}_{\mathcal{H}_{f,t}}=0^{\infty}$, and
$\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})=0$.

Now, we give a lemma, which relates the VC-dimension of complex functions to
that of simpler ones. Let $\mathcal{F}_{q}$ refer to the family of symmetric
unimodal functions that have a $2^{q}$-cycle but not a $2^{q+1}$-cycle.

######  Lemma 10.

For any $f\in\mathcal{F}_{q}$ with fixed point $x^{*}>\frac{1}{2}$ and any
$t\in[0,1]$,

$\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})\leq
4\max_{g\in\mathcal{F}_{q-1},t^{\prime}\in[0,1]}\text{VC}_{\text{weak}}(\mathcal{H}_{g,t^{\prime}})+10.$

###### Proof.

Consider some such $f$. Let $x_{1}<\dots<x_{m}$ be the fixed points of $f$
where $x_{m}=x^{*}>\frac{1}{2}$. Because $\frac{1}{2}$ maximizes $f$,
$f(\frac{1}{2})\geq x_{m}>\frac{1}{2}$. This fixed point must the only fixed
point no smaller than $\frac{1}{2}$; the existence of another such fixed point
would contradict the fact that $f$ is decreasing on $(\frac{1}{2},1]$. Thus,
$x_{1},\dots,x_{m-1}<\frac{1}{2}$.

We build a recursive relationship by considering $f^{2}$ and relating some its
output on some segments of $[0,1]$ to other maps with smaller $q$. For now, we
instead attempt to upper-bound the VC-dimension of $\mathcal{H}_{f^{2},t}$.

For all $j\in[m]$, unimodality implies that $x_{j}$ and $1-x_{j}$ are the only
points that map to $x_{j}$ and that the following ordering holds.

$0<x_{1}<\dots,<x_{m-1}<1-x_{m}<\frac{1}{2}<x_{m}<1-x_{m-1}<\dots,1-x_{1}<1.$

By the Intermediate Value Theorem, there exists some
$x_{m}^{\prime}\in(x_{m},1-x_{m-1})$ such that
$f(x_{m}^{\prime})=f(1-x_{m}^{\prime})=1-x_{m}$ and
$f^{2}(x_{m}^{\prime})=f^{2}(1-x_{m}^{\prime})=x_{m}$.

We define intervals as follows:

  * •

$I_{0}=[0,x_{1})$ and $I_{0}^{\prime}=(1-x_{1},1]$.

  * •

For all $j\in[m-2]$, $I_{j}=[x_{j},x_{j+1})$ and
$I_{j}^{\prime}=(1-x_{j+1},1-x_{j}]$.

  * •

$I_{m-1}=[x_{m-1},1-x_{m}^{\prime})$ and
$I_{m-1}^{\prime}=(x_{m}^{\prime},1-x_{m-1}]$.

  * •

$I_{m}=[1-x_{m}^{\prime},1-x_{m})$ and
$I_{m}^{\prime}=(x_{m},x_{m}^{\prime}]$.

  * •

$I_{m+1}=[1-x_{m},\frac{1}{2})$, and $I_{m+1}^{\prime}=[\frac{1}{2},x_{m}]$.

For any $j\in\\{0,\dots,m+1\\}$, $f$ is increasing on all intervals $I_{j}$
and decreasing on $I_{j}^{\prime}$. By symmetry, $f(I_{j})=f(I_{j}^{\prime})$.
For all $j\in\\{0,\dots,m-2\\}$, $f(I_{j})=I_{j}$. $f(I_{m-1})=I_{m-1}\cup
I_{m}$, $f(I_{m})=I_{m+1}\cup I_{m+1}^{\prime}$, and $f(I_{m+1})\subseteq
I_{m}^{\prime}$, because $f(\frac{1}{2})\in[x_{m},x_{m}^{\prime})$.141414 This
must be the case for the assumptions to be met. If $f(\frac{1}{2})<x_{m}$,
then $x_{m}$ cannot be a fixed point because $\frac{1}{2}$ maximizes $f$. If
$f(\frac{1}{2})>x_{m}^{\prime}$, then there exists a 3-cycle with points in
$I_{m+1},I_{m-1}^{\prime},I_{m}$, which contradicts the assumption that we
only have power-of-two cycles.

From there, we obtain additional properties for $f^{2}$:
$f^{2}(I_{m-1})=I_{m-1}\cup I_{m}\cup I_{m+1}\cup I_{m+1}^{\prime}$,
$f^{2}(I_{m})\subseteq I_{m}^{\prime}$, and $f^{2}(I_{m+1})\subset I_{m+1}\cup
I_{m+1}^{\prime}$. This suggests that there is recurrent structure that we can
take advantage of to count all of the patterns.

Let $J_{m+1}:=I_{m+1}\cup I_{m+1}^{\prime}$. We create a Regex to track the
behavior of iterates $f^{2}$, which we visualize in Figure 19:

$\bigcup_{j=0}^{m-2}I_{j}^{\infty}\ \cup\
I_{m-1}^{*}I_{m}I_{m}^{\prime\infty}\ \cup\ I_{m}^{\prime\infty}\ \cup\
I_{m-1}^{*}J_{m+1}^{\infty}.$

When an iterate of $f^{2}$ gets “stuck” in one of $I_{0},I_{1},\dots,I_{m-1}$,
it must either be at a fixed point, be strictly increasing, or be strictly
decreasing. To suggest otherwise would imply the existence of another fixed
point in those intervals, because $f^{2}$ is monotonically increasing or
decreasing in all of those and either all $x$ yield $f^{2}(x)\geq x$ or
$f^{2}(x)\leq x$.

For the remaining intervals, one might notice in Figure 19 that zooming in on
the intervals $I_{m}$, $J_{m+1}$, and $I_{m}^{\prime}$ for $f^{2}$ gives what
looks like unimodal maps.151515We use similar techniques here to those used in
Section D.3.2. We take advantage of that structure to bound the complexity of
the 0/1 Regexes for those intervals. We can formalize this by defining
symmetric unimodal mappings $h_{m}$ and $h_{m+1}$ and bijective monotonic
mappings $\phi_{m}:I_{m}^{\prime}\to(0,1]$ (increasing) and
$\phi_{m+1}:J_{m+1}\to[0,1]$ (decreasing) such that:

  * •

For $x\in I_{m}$, $f^{2}(x)=\phi_{m}^{-1}\circ h_{m}\circ\phi_{m}(1-x).$

  * •

For $x\in I_{m}^{\prime}$, $f^{2}(x)=\phi_{m}^{-1}\circ
h_{m}\circ\phi_{m}(x).$

  * •

For $x\in J_{m+1}$, $f^{2}(x)=\phi_{m+1}^{-1}\circ h_{m+1}\circ\phi_{m+1}(x).$

$x$$f(x)$$x_{1}$$I_{0}$$I_{1}$$I_{0}$$I_{1}$$I_{2}$$1/2$$x_{2}$$1-x_{1}$$I_{2}$$I_{2}^{\prime}$$I_{1}^{\prime}$$I_{0}^{\prime}$$I_{0}^{\prime}$$I_{1}^{\prime}$$I_{2}^{\prime}$$1-x_{2}$$x_{2}$$x_{1}$$1-x_{2}$$x_{2}^{\prime}$$1-x_{2}^{\prime}$$I_{3}^{\prime}$$I_{3}$$J_{3}$$J_{3}$${\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02}f}{\color[rgb]{0.25,0.46,0.02}{}^{2}}{\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02}(}{\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02}x}{\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02})}$$1-x_{2}^{\prime}$$\frac{1}{2}$$x_{2}^{\prime}$$f:$$I_{0}$$I_{1}$$I_{2}$$I_{0}^{\prime}$$I_{1}^{\prime}$$I_{2}^{\prime}$$J_{3}$$f:$
Figure 19: Like Figure 18, plot of $f$ and $f^{2}$ with $m=3$ fixed points
with $x_{m}>\frac{1}{2}$ and visualizes the mappings between intervals.

Because $f$ cannot have a cycle of length $2^{q+1}$, $h_{m}$ and $h_{m+1}$ may
not have cycles of length $2^{q}$. Thus, we can reason inductively about how
iterates behave when they’re trapped in those intervals.

We do another case analysis of the 0/1 Regexes induced by different choices of
$t$.

  * •

If $t\in I_{j}$ for $j\in\\{0,\dots,m-1\\}$, then
$\mathcal{S}_{\mathcal{H}_{f^{2},t}}\subseteq 0^{\infty}\cup 1^{\infty}\cup
0^{*}1^{\infty}\cup 1^{*}0^{\infty}$ because a sequence of iterates only
crosses $t$ if it enters the correct interval $I_{j}$, where the iterate then
will be stuck and must monotonically increase or decrease. By Lemma 9,
$\text{VC}_{\text{weak}}(\mathcal{H}_{f^{2},t})\leq 2$.

  * •

If $t\in I_{j}^{\prime}$ for $j\in\\{0,\dots,m-1\\}$, then
$\mathcal{S}_{\mathcal{H}_{f^{2},t}}=0^{\infty}$, and
$\text{VC}_{\text{weak}}(\mathcal{H}_{f^{2},t})=0$.

  * •

If $t\in I_{m}$, then $\mathcal{S}_{\mathcal{H}_{f^{2},t}}=0^{\infty}\cup
1^{\infty}\cup 0^{*}1^{\infty}$. Then,
$\text{VC}_{\text{weak}}(\mathcal{H}_{f^{2},t})\leq 1$.

  * •

If $t\in J_{m+1}$, then $\mathcal{S}_{\mathcal{H}_{f^{2},t}}=0^{\infty}\cup
0^{*}1^{\infty}\cup 0^{*}J_{m+1}^{\infty}$. Because $h_{m+1}$ has at most a
cycle of length $2^{q-1}$, we have that

$\text{VC}_{\text{weak}}(\mathcal{H}_{f^{2},t})\leq
2+\max_{t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{h_{m+1},t^{\prime}}).$

  * •

If $t\in I_{m}^{\prime}$, then
$\mathcal{S}_{{\mathcal{H}}_{f^{2},t}}=0^{\infty}\cup
0^{*}I_{m}^{\prime\infty}$. This gives us that

$\text{VC}_{\text{weak}}(\mathcal{H}_{f^{2},t})\leq
1+\max_{t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{h_{m},t^{\prime}}).$

To get $\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})$, notice that
$\mathcal{S}_{\mathcal{H}_{f,t}}=\mathcal{S}_{\mathcal{H}_{f^{2},t}}\oplus\mathcal{S}_{\mathcal{H}_{f^{2},t}^{\prime}}$,
where $\mathcal{H}_{f^{2},t}^{\prime}$ refers to the outcome of all odd
iterates of $f$. We show that
$\mathcal{S}_{\mathcal{H}_{f^{2},t}^{\prime}}\subseteq\mathcal{S}_{\mathcal{H}_{f^{2},t}}$
because the latter could induce all sequences produced by the former by
starting with some $x^{\prime}$ such that $f^{2}(x^{\prime})=f(x)$. Thus, by
Lemma 9,

$\displaystyle\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})$ $\displaystyle\leq
4\max_{t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{f^{2},t^{\prime}})+2$
$\displaystyle\leq
4\max(2+\max_{t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{h_{m+1},t^{\prime}}),1+\max_{t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{h_{m},t^{\prime}}))+2$
$\displaystyle\leq
4\max_{g\in\mathcal{F}_{q-1},t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{g,t^{\prime}})+10.\qed$

Now, we prove a bound on the VC-dimension for arbitrary $q$ by induction with
Lemma 10 to show that for $\text{VC}(\mathcal{H}_{f,t})\leq 18\cdot 4^{q}$.

This holds when $q=0$. There are two possible cases for the fixed point of
such an $f$. If the the largest fixed point is smaller than $\frac{1}{2}$,
then, by the simple cases explored at the beginning,
$\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})\leq 1$. Otherwise, we apply Lemma
10 along with the the other simple case—which tells us what happens when there
are no fixed point—to get that $\text{VC}_{\text{weak}}(\mathcal{H}_{f,t})\leq
4(1)+10=14$. This trivially satisfies the proposition.

For the inductive step for arbitrary $q$, we iteratively apply Lemma 10 to
obtain the final bound.

$\displaystyle\text{VC}(\mathcal{H}_{f,t})$ $\displaystyle\leq
4\max_{g\in\mathcal{F}_{q-1},t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{g,t^{\prime}})+10$
$\displaystyle\leq
4^{q}\max_{g\in\mathcal{F}_{0},t^{\prime}}\text{VC}_{\text{weak}}(\mathcal{H}_{g,t^{\prime}})+10\sum_{i=0}^{q-1}4^{i}$
$\displaystyle\leq 14\cdot 4^{q}+\frac{10}{3}4^{q}\leq 18\cdot 4^{q}.$

###  D.6 Proof of Theorem 9, Claim 4

######  Proposition 8.

Suppose $f$ is a symmetric unimodal function with a $2^{q}m$-cycle for odd
$m$. Then for

$K=\exp\left(O\left(q+d\log(d+m)\right)\right),$

$\text{VC}(\mathcal{H}_{f,K})\geq d$ for
$\mathcal{H}_{f,K}=\left\\{[[f^{k}]]_{1/2}:k\in[K]\right\\}.$

The claim holds by this proposition, since the VC-dimension of
$\mathcal{H}_{f}$ is larger than every $d$ and hence must be infinite.

###### Proof.

The proof of this claim relies on the existence of a lemma that describes a
characteristic of odd-period cycles of unimodal functions.

######  Lemma 11.

Let $f$ be a symmetric unimodal function with some odd cycle
$x_{1},x_{2},\dots,x_{m}$ of length $m>1$ such that $f(x_{i})=x_{i+1}$ and
$f(x_{m})=x_{1}$. Then, there exists some $i$ such that $x_{i}<\frac{1}{2}$
and $f(x_{i})\geq\frac{1}{2}$.

###### Proof.

To prove the claim, it suffices to show that the following two cases are
impossible: (1) $x_{1},\dots,x_{m}<\frac{1}{2}$ and (2)
$x_{1},\dots,x_{m}\geq\frac{1}{2}$.

  1. 1.

Suppose $x_{1},\dots,x_{m}<\frac{1}{2}$. By unimodality $x_{j}<x_{j^{\prime}}$
implies that $f(x_{j})<f(x_{j^{\prime}})$. If $x_{1}$ is the smallest element
of the cycle, then $f(x_{1})>x_{1}$. For any other $x_{j}$, $f(x_{j})>x_{1}$,
which means that $x_{1}$ cannot be part of a cycle, which contradicts the odd
cycle.

  2. 2.

Suppose instead that $x_{1},\dots,x_{m}\geq\frac{1}{2}$.

For this to be the case, $f(\frac{1}{2})>\frac{1}{2}$ by unimodality. This
fact paired with $f(1)<1$ implies the existence of some
$x^{*}\in(\frac{1}{2},1)$ with $f(x^{*})=x^{*}$. Because $f$ is decreasing on
$[1/2,1]$, $f([1/2,x^{*}))\subseteq(x^{*},1]$ and $f((x^{*},1])=[0,x^{*})$.

If $x_{1}\in[\frac{1}{2},x^{*})$, then $x_{2}\in(x^{*},1]$, and
$x_{3}\in[\frac{1}{2},x^{*})$. If apply this fact repeatedly, the oddness of
$m$ implies that $x_{m}\in[\frac{1}{2},x^{*})$ and $x_{1}\in(x^{*},1]$, a
contradiction.∎

We show that $\text{VC}(\mathcal{H}_{f^{2^{q}},K/2^{q}})>d$. If $f$ has a
cycle of length $2^{q}\cdot m$, then $f^{2^{q}}$ has a cycle of length $m$. By
Sharkovskii’s Theorem, for all odd $m^{\prime}>m$, $f^{2^{q}}$ also has a
cycle of length $m^{\prime}$. Let $p_{1}<\dots<p_{d}$ be the smallest prime
numbers greater than $m$. According to Lemma 12,
$p_{d}\leq\left(\frac{K}{2^{q}}\right)^{1/d}$ for

$K=2^{q}\left(O(\max(d\log
d,m)\right)^{d}=\exp\left(O\left(q+d\log(d+m)\right)\right).$

For $j\in[m]$, let $x^{(j)}$ be the point guaranteed by Lemma 11 with
$f^{2^{q}\cdot p_{j}}(x^{(j)})=x^{(j)}$, $x^{(j)}<\frac{1}{2}$, and
$f^{2^{q}}(x^{(j)})\geq\frac{1}{2}$. Therefore, it follows that
$f^{2^{q}\cdot\ell p_{j}}(x^{(j)})<\frac{1}{2}$ and $f^{2^{q}(\ell
p_{j}+1)}(x^{(j)})\geq\frac{1}{2}$ for all $\ell\in\mathbb{Z}_{\geq 0}$.

To show that $\mathcal{H}_{f^{2^{q}}}$ shatters $x^{(1)},\dots,x^{(d)}$, we
show that for any labeling $\sigma\in\\{0,1\\}^{d}$, there exists
$h\in\mathcal{H}_{f^{2^{q}},K/2^{q}}$ such that $h(x^{(j)})=\sigma_{j}$.

  * •

If $\sigma=(0,\dots,0)$, then consider $f^{2^{q}\cdot k}$, where
$k=\prod_{j=1}^{n}p_{j}$. Then, for all $j$, $f^{2^{q}\cdot
k}(x^{(j)})<\frac{1}{2}$. Because $k\leq p_{d}^{d}\leq\frac{K}{2^{q}}$, there
exists some $h\in\mathcal{H}_{f^{2^{q}},K/2^{q}}$ that assigns zero to every
$x^{(j)}$.

  * •

Similarly, if $\sigma=(1,\dots,1)$, we instead consider $f^{2^{q}\cdot k}$ for
$k=1+\prod_{j=1}^{n}p_{j}$. Now, for all $j$, $f^{2^{q}\cdot
k}(x^{(j)})\geq\frac{1}{2}$, and $k\leq p_{d}^{d}\leq\frac{K}{2^{q}}$, which
means there exists satisfactory $h\in\mathcal{H}_{f^{2^{q}},K/2^{q}}$.

  * •

Otherwise, assume WLOG that $(\sigma_{1},\dots,\sigma_{\ell})=(0,\dots,0)$ and
$(\sigma_{\ell+1},\dots,\sigma_{d})=(1,\dots,1)$ for $\ell\in(1,d)$. We
satisfy the claim for $f^{2^{q}\cdot k}$ if we choose some $k$ with
$k=q_{1}\prod_{i=1}^{\ell}p_{i}=1+q_{2}\prod_{i=\ell+1}^{d}p_{i}$, for some
$q_{1},q_{2}\in\mathbb{Z}_{+}$.

We find $q_{1}\in[\prod_{i=\ell+1}^{d}p_{i}]$ and
$q_{2}\in[\prod_{i=1}^{\ell}p_{i}]$ by choosing them such that:

$\displaystyle q_{1}\prod_{i=1}^{\ell}p_{i}$ $\displaystyle\equiv
1\pmod{\prod_{i=\ell+1}^{d}p_{i}}$ $\displaystyle
q_{2}\prod_{i=\ell+1}^{d}p_{i}$
$\displaystyle\equiv-1\pmod{\prod_{i=1}^{\ell}p_{i}}.$

This is possible because $p_{1},\dots,p_{d}$ are prime, and
$\gcd\left(\prod_{i=1}^{\ell}p_{i},\prod_{i=\ell+1}^{d}p_{i}\right)=1$.

Because $k\leq\prod_{i=1}^{d}p_{i}\leq p_{d}^{d}\leq\frac{K}{2^{q}}$, there
must exist some satisfactory $h\in\mathcal{H}_{f^{2^{q}},K/2^{q}}$.∎

######  Lemma 12.

For $m\geq 3$ and any $d\geq 0$, there exist $d$ primes such that $m\leq
p_{1}<\dots<p_{d}$ for

$p_{d}=O(\max(d\log d,m)).$

###### Proof.

Let $\pi(x)=\left|\\{y\in[x]:y\text{ is prime}\\}\right|$ be the number of
primes no larger than $x$. By the Prime Number Theorem,

$\frac{x}{\log(x)+2}\leq\pi(x)\leq\frac{x}{\log(x)-4},$

for all $x\geq 55$ (Rosser, 1941). Thus, for some $m^{\prime}=O(\max(d\log
d,m))$, the number of prime numbers smaller than $m^{\prime}$ is

$\Omega\left(\frac{d\log d}{\log(d\log d)}+\frac{m}{\log
m}\right)=\Omega\left(d+\frac{m}{\log m}\right),$

and the number between $m$ and $m^{\prime}$ is $\Omega(d).$ Thus, $p_{d}\leq
m^{\prime}$. ∎