Polymath Jr. REU
Explore with sequences, patterns, and programming...


My project in Polymath Jr. 2024 will focus on ideas in infinite Skolem sequences. A brief description is found below:

Infinite Skolem sequences
A Skolem sequence for $n\in\mathbb{N}=\{1,2,3,\ldots\}$ is a sequence of $2n$ integers such that every integer $i\in\{1,2,\ldots,n\}$ appears in exactly two positions at a distance $i$. An example for $n=4$ is $1,\ 1,\ 3,\ 4,\ 2,\ 3,\ 2,\ 4$ (the distance between the two copies of an integer is equal to that integer). Skolem sequences exist for $n\equiv 0,1 \pmod{4}$, but they are not trivial to construct. On the other hand, an infinite Skolem sequence, defined as $\{s_i: i\in\mathbb{N}\}$ where every $n\in\mathbb{N}$ appears in exactly two positions at distance $n$, can be obtained easily: Having placed two copies of $1, 2, \ldots, n$, one idea is to place the first copy of $n+1$ in the first available position, and the second at the appropriate distance. This gives the first lexicographic infinite Skolem sequence, where $n$ first appears before $m$ whenever $n\lt m$: $$1,\ 1,\ 2,\ 3,\ 2,\ 4,\ 3,\ 5,\ 6,\ 4,\ 7,\ 8,\ 5,\ 9,\ 6,\ \ldots$$

A visual progression for this construction can be found below, and here's some illustration using Desmos:

For any given $n$, let $a_n$ be the position of the first occurrence of $n$ in the infinite Skolem sequence above. How can we find $a_n$? One could start with a program to generate $s_1, s_2, \ldots, s_k$ in an array for a large enough $k$ and observe when $n$ first shows up. Since we don't know how large $k$ must be, an initial challenge is to work without this knowledge, or using structures that can be extended at run time. Obviously, there is a need for a better algorithm. By observing $a_n$ for different values of $n$, one may be able to conjecture lower and upper bounds on $a_n$. The program (or other types of explorations) can guide us to observe how the sequence $a_1, a_2, a_3, \ldots$ evolves, perhaps by looking at $a_{n}-a_{n-1}$ (see exercise 6 below suggesting a binary pattern). Once patterns emerge, OIES may be used to investigate whether anything is known about such patterns. Eventually, one could develop a better algorithm to compute $a_n$, possibly one that avoids arrays altogether.

The problem can be extended by requiring for each integer $n$ three copies at distance $n$. For instance, if we follow the above strategy, the infinite sequence will begin with: $$1,\ 1,\ 1,\ 2,\ \underline{3?},\ 2,\ \underline{\ \ \ },\ 2,\ \underline{\ \ \ },\ \underline{\ \ \ },\ \underline{\ \ \ },\ \ldots$$ However, by attempting to place 3 starting at the first available position, its second copy will be blocked by the last occurrence of 2! Following this strategy, 4 will have to be placed before 3. But this repeats, and the first occurrence of 3 will have to wait until position 28. Therefore, the first lexicographic infinite Skolem sequence in this case does not have a monotonic $a_n$. In general, if we have $k>2$ copies of each integer, which integers will be blocked, and will they ever find their place in the sequence? What is an algorithm for constructing such an infinite sequence, and how is $a_n$ affected? What if we relax the rules to have $k$ copies of each integer, but require that only two consecutive copies must be at distance $n$? Each choice of the two copies changes the pattern for $a_n$ and defines a separate problem. Here's an example when $k=3$ and the last two copies must be at the correct distance (observe that $a_n-a_{n-1}-2$ is also binary, it is either 0 or 1). $$1,\ 1,\ 1,\ 2,\ 2,\ 3,\ 2,\ 3,\ 4,\ 4,\ 3,\ 5,\ 5,\ 4,\ 6,\ 6,\ 7,\ 5,\ 7,\ 8,\ 8,\ 6,\ 9,\ldots$$

Prerequisites
Experience in discrete math, proofs, algorithms, and programming (not necessarily all).

Mentoring team
The team consists of:

Participating students
Here's a complete list (by email) of participating students. A list with picture and info of those who provided them can also be found here.

Recordings (lectures introducing the subject during the first week)

How to proceed (after lectures)
Here's how to proceed and a Google form to fill.

Weekly meetings (zoom only)
Next meeting (passcode: 1123243564) is Wed. July 31, 2024 at 12:00 PM.

Office hours (zoom only)

Overleaf document (this is where we keep our progress)
Make sure to create an Overleaf account. To access the document, click here. Create a file with your name to report progress, questions, code, etc...

Slack workspace
You can join here.

Some preliminary ideas on this problem

More references related to Skolem sequences (most can be found by a simple search, just cut and paste into Google...)

Warm up exercises (and some useful programming tasks)
Some warm up exercices are added to the Overleaf document (link above in the Overleaf section). As an initial learning component, you will be guided to work on specific exercises based on your interests and the research direction you are involved in. Solutions and answers will eventually be added. Students can also contribute to programming/math solutions if they like... Some of the exercises are reproduced here for those who are interested.

  1. Find (finite) Skolem sequences for $n=1$, $n=4$, $n=5$, and $n=8$.

  2. Consider the following pattern: $f_0=0$, $f_1=01$, and $f_n=f_{n-1}f_{n-2}$ (concatenation). The infinite Fibonacci word is given by the limit of this pattern when $n$ goes to infinity. Generate the first few bits of the infinite Fibanacci word, and use OEIS to verify that your initial few bits are correct.

  3. Start with 01. Scan the pattern starting at the second bit (the 1). If you encounter a 0, append a 01 to the end of the pattern, and if you encounter a 1, append a 0 to the end of the pattern. Verify that this is also equivalent to the definition of the infinite Fibonacci word.

  4. Write a program to generate the first $n$ bits of the infinite Fibonacci word.

  5. Write a program to generate the first $n$ numbers in the infinite Skolem sequence $1, 1, 2, 3, 2, 4, 3, 5, 6, 4, 7, 8, 5, 9, 6, \ldots$.

  6. Consider the infinite Skolem sequene where every integer $n$ appears $k=3$ times, and every consecutive copies of that integer are at distance $n$. Verify that $a_3=28$ if we favor the sequence that comes first in a lexicographic order.

  7. Prove that $\lfloor n\phi^2\rfloor-\lfloor n\phi\rfloor=n$ for $n\in\mathbb{N}$, where $\phi=(1+\sqrt{5})/2$. What is the significance of this in the context of infinite Skolem sequences? Can you revisit exercise 5? Here's an illustration using Desmos.

  8. Would you like to come up with a Skolem-like infinite sequence, or a particular construction of one, using alternative rules? Go for it and share your ideas... For instance, my student Vlad Vostrikov suggested the following variation to the construction of the Skolem sequence with three copies, where 3 is shown to be blocked in the above example: place $n$ in the first available position that does not lead to a block. This makes the sequence not the first in a lexicographic order, leading to $1,\ 1,\ 1,\ 2,\ ? ,\ 2,\ 3,\ 2,\ 7, 3,\, 4,\ 5,\ 3,\ \ldots$ as opposed to $1,\ 1,\ 1,\ 2,\ 4,\ 2,\ 5,\ 2,\ 4,\ 6,\ 7,\ 5,\ 4,\ \ldots$. Initially the question was: will every integer be placed? With the variation the question becomes: will every position be filled?

Some research questions (we will write code to discover patterns and/or explore strategies when the math is too obscure)



The Polymath Jr. website and its wiki.