Distributions of Ulam Words up to Length 30

#A102 INTEGERS 25 (2025) DISTRIBUTIONS OF ULAM WORDS UP TO LENGTH 30 Paul Adutwum Bates College, Lewiston, Maine [email protected] Hopper Clark Bates College, Lewiston, Maine [email protected] Ro Emerson Bates College, Lewiston, Maine [email protected] Alexandra (Sasha) Sheydvasser University of Massachusetts, Amherst, Massachusetts [email protected] Arseniy (Senia) Sheydvasser Department of Mathematics, Bates College, Lewiston, Maine [email protected] Axelle Tougouma Bates College, Lewiston, Maine [email protected] Received: 10/16/24, Revised: 7/2/25, Accepted: 10/26/25, Published: 11/5/25 Abstract We further explore the notion of Ulam words considered by Bade, Cui, Labelle, and Li, giving some lower bounds on how many there are of a given length. Gaps between words and words of special type also reveal remarkable structure. By substantially increasing the number of computed terms, we are also able to sharpen some of the conjectures made by Bade et al. 1. Introduction In their 2020 paper, Bade, Cui, Labelle, and Li [1] introduced the notion of Ulam words, defined as follows. Consider the free semigroup Srt0,1us on two generators DOI: 10.5281/zenodo.17535327 INTEGERS: 25 (2025) 2 0 and 1. We say that 0 and 1 are Ulam and then define all other Ulam words inductively: a word w‰0,1 is Ulam if and only if there exists exactly one pair of Ulam words u1‰u2such that w“u1 "u2. (Here, "denotes concatenation.) We shall denote the entire set of Ulam words as U, and Ulam words of length nby Un. It is easy to check that: U1“ t0,1uU3“ t001,011,100,110u U2“ t01,10uU4“ t0001,0010,0100,0111,1000,1011,1101,1110u. All Ulam words up to length 24 were computed in [1]; we were able to compute up to length 30. While this might appear as a small improvement at first glance, because the number of Ulam words of length nappears to (almost) double on each iteration, in reality, this represents nearly 60 times as much data. It is an open question whether |Un|(the size of Un) grows exponentially. The best lower bound that we can prove is linear, mainly using explicit constructions of words from [1]. Theorem 1. For all ně6, we have that |Un| ě 2n`4. However, we are able to demonstrate that there is a subsequence of Ulam words that grows exponentially, using a completely different argument. Theorem 2. There exists 1ăα0ď2such that for all 1ăαăα0, we have that lim sup nÑ8 |Un| αn“ 8. Concretely, α0“ˆ101847671 31 ˙1{5 «1.648996 suffices. We give proofs of both of these theorems in Section 3. Unfortunately, both of these results are still quite far from what is conjectured to hold. To wit, define the density ρpnq:“|Un| 2n; It was conjectured in [1] that ρpnq Ñ rfor some 0 ără1 (see Conjecture 3.10 in [1]); with our enlarged data set, we instead posit something a little stranger. Conjecture 1. The density of Ulam words ρpnq “ Θpn´3{10q. This conjecture is supported by the numerical evidence—see Figures 1 and 2 for an example—but it also has ties to another conjecture involving the average gap between Ulam words, which we shall describe below. In any case, observe that if INTEGERS: 25 (2025) 3 5 10 15 20 25 30 n 0.1 0.2 0.3 0.4 δ Figure 1: A plot of the densities ρpnqfor 4 ďnď30, together with a plot of fpnq “ 0.526n´3{10. n|Un| 13 1916 14 3812 15 7772 16 14822 17 29368 18 58478 n|Un| 19 114300 20 225166 21 441724 22 876238 23 1717748 24 3406884 n|Un| 25 6720784 26 13303332 27 26273948 28 52010642 29 102933200 30 203695342 Figure 2: The exact counts for |Un|for 13 ďnď30. either conjecture is correct, the number of Ulam words grows only very slightly slower than 2n. This notion of Ulam words was built on the earlier notion of Ulam sets due to Kravitz and Steinerberger [8], which was itself a generalization of Ulam’s eponymous integer sequence, also defined recursively [13]: the (classical) Ulam sequence begins with 1,2, and then every subsequent term is the next smallest integer that can be written as the sum of two distinct prior terms in exactly one way. Generalizations of Ulam’s classic sequence have become an increasingly popular object of study: in 1972, Queneau did some preliminary work studying generalizations where the initial two terms of the integer sequence are varied [10]; in the 1990s, Cassaigne, Finch, Shmerl, and Spiegel determined some of the families of such sequences such that the consecutive differences are eventually periodic [2, 3, 4, 5, 11]; in 2017, [8] considered generalizing the Ulam condition for abelian groups; in 2020, [1] gave the aforementioned notion of Ulam words with some preliminary results; and in 2021, Sheydvasser showed that there is an analogous notion of Ulam sets for integer polynomials [12] by building off earlier work of Hinman, Kuca, Schlesinger, and Sheydvasser [6, 7]. INTEGERS: 25 (2025) 4 S0S1S2S3 Figure 3: Visual of the first 4 steps of constructing the discrete Sierpi´nski triangle. Earlier work around Ulam words has largely centered around giving simple criteria for when words of some special type are Ulam—for example, [1] showed that a word of the form 0a10bis Ulam if and only if pa`b aqis odd. Similarly, Mandelshtam [9] considered Ulam words of the form 0a10b10cand demonstrated a connection to the Sierpi´nski gasket. We also prove a few such results, such as the following. Theorem 3. Consider the set of points px, yq P Z2 ě1such that 1y0x´yPU. This is the discrete Sierpi´nski triangle, union a point. We will discuss this construction more precisely in Section 4, but briefly, the discrete Sierpi´nski triangle is an approximation to the standard Sierpi´nski triangle. It can be constructed either iteratively (as in Figure 3) or by coloring Pascal’s triangle by parity. On the other hand, we also have a novel way of considering Ulam words by interpreting them as integers. Observe that there exists a natural map π:Srt0,1us Ñ Zě0via interpreting a word as the binary representation of an integer. In general, this map is not injective—for example, πp0q “ πp00q “ πp000q “ 0. However, if we restrict it to words of a fixed length, then it is. In particular, the restrictions π:UnÑZX r0,2n´1sare injective maps. This gives a natural ordering on Unand allows us to ask questions about how Ulam words are distributed. For example, we might ask about the distribution of the gaps—differences between consecutive Ulam words, interpreted as integers. Conjecture 2. Let u1ău2ă. . . ăuknbe the (ordered) elements of πpUnq. Define pn:Zě1Ñ r0,8q gÞÑ ˇˇti|ui`1´ui“guˇˇ kn´1. INTEGERS: 25 (2025) 5 This has a natural interpretation as a probability measure. As nÑ 8, the functions pnconverge pointwise to a probability measure p:Zě1Ñ r0,8q. Furthermore, let µgpnqbe the mean of the probability measure pn. Then µgpnq “ Θpn3{10q—indeed, it may be that there is a constant c«1.9 such that µgpnq “ cn3{10 `op1q. This conjecture is well-supported by our available data—see Section 5 for details, illustrations, and further odd properties of the apparent distribution. What is interesting about this statement about average gaps is that, if true, it immediately implies Conjecture 1. Theorem 4. As nÑ 8, we have that ρpnq´1—µgpnq. Consequently, Conjecture 2 implies Conjecture 1. This is salient, since our numerical evidence for Conjecture 2 is arguably much stronger than for Conjecture 1! Again, see Section 5 for details. Finally, in Section 6, we ask the question of how πpUnqis distributed modulo N. Conjecture 3. For any integer Ną1 and aPZ{NZ, define the relative density ρa,N pnq:“ˇˇtwPUn|πpwq ” amod Nuˇˇ |Un|. Then limnÑ8 ρa,N pnq “ 1{N. Remark 1. As we discuss in Section 6, while this conjecture is consistent with the available data, it is somewhat surprising. For one thing, ρ5,6p1q “ ρ5,6p2q “ ρ5,6p3q “ 0, and it takes some time before it appears to start to converge to 1{6. For another, there is an apparent bias modulo 6 in the distribution of the gaps. Our code and some of our data can be found on GitHub1, but it is far from efficient—as was pointed out to us Tom´as Oliveira e Silva, it is possible to use bitmaps to make these computations much faster; a good implementation should give a Op2nlogpnqq running time. However, we leave this as material for future work. 2. Definitions and Visualizations We start with some basic definitions and constructions. Given a word wPSrt0,1us, we define its complement ˆwto be the word with every instance of 0 replaced with a 1, and vice versa. We also define the reverse w, which is the word obtained by reversing the order of the letters. It was shown in [1] that wPUif and only if ˆwPU, if and only if wPU. 1https://github.com/asheydva/Ulam-Words.git INTEGERS: 25 (2025) 6 Figure 4: All words of length 20 beginning with a zero. To better visualize the set U, we made use of heat maps, which depict each Ulam word as a colored bar and stacks all of the words vertically—that is, for a given word, a 0 corresponds to a rectangle of one color, and a 1 corresponds to a rectangle of a second color. An example is provided in Figure 4. In general, we abridge such diagrams: we created figures only using all the Ulam words that started with zero, since Ulam words are closed under complements. Moreover, we impose the ordering discussed in the introduction, defining wďw1if and only if πpwq ď πpw1q. Using this way of visualizing Ulam words allows us to easily see that there is both a clear binary tree structure that governs the existence of Ulam words, as well as a chaotic element to the set where the binary tree breaks down. We can be more specific about our meaning regarding this breakdown: since Ulam words are preserved under the reverse map, this is equivalent to saying that for any nthere exists nąℓną0 such that all possible subwords of length ℓnoccur as the final ℓncharacters of words in Un. In turn, that is equivalent to saying that the quotient map πpUnq Ñ Z{2ℓnZis surjective. Our observation is that ℓnappears to increase as a function of n, albeit not very quickly—see Figure 5. Assuming that Conjecture 3 is true, then it would follow immediately that ℓnÑ 8 simply by considering the case where N“2ℓn—indeed, the heat maps were the original impetus for our equidistribution conjectures. On the other hand, the “chaotic” latter half of the heat map is more of a mystery. INTEGERS: 25 (2025) 7 n ℓn 1 1 2 1 3 1 4 1 5 3 6 2 n ℓn 7 4 8 4 9 4 10 4 11 4 12 5 n ℓn 13 5 14 5 15 6 16 7 17 7 18 8 n ℓn 19 9 20 9 21 9 22 10 23 10 24 11 n ℓn 25 11 26 11 27 12 28 12 29 13 30 13 Figure 5: Tables of nversus ℓn, where ℓnis the largest integer such that UnÑ Z{2ℓnZis surjective. 3. Lower Bounds on Growth Our goal in this section is to prove our lower bounds on |Un|; we begin with Theorem 1, for which we need some explicit examples of Ulam words. The first three are due to [1]. Theorem 5 ([1]).There are Gpn´1qUlam words of length nof the form 0a10b, where Gpnqis the n-th entry in Gould’s sequence. Remark 2. Gould’s sequence Gpnqis the number of odd entries in the n-th row of Pascal’s triangle; equivalently, Gpnq “ 2#1pnq, where #1pnqis the number of non-zero bits in the binary representation of n. Remark 3. Since wPUif and only if wPU, if and only if ˆwPU, we get analogous results with 1’s replaced with 0’s and the order of the letters reversed. This is true for all the results that we prove here. Theorem 6 ([1]).For any a, b PZě0, the word 0a120bis in Uif and only if the length of the word is odd (that is, a`b”1pmod 2q). Theorem 7 ([1]).For any a, b PZě0such that a`bě2, the word 0a1010bis in Uif and only if the length of the word is even (that is, a`b”1 mod 2). Lemma 1. For any a, b PZě0such that a`bě1, the word 0a140bis in Uif and only if a`b”1pmod 4q. Proof. We will use proof by induction on the length of the word n, where the base cases n“5,6,7,8 can be verified directly. Assume the statement holds for all words of length strictly less than n, and consider the word u“0k140lof length n, where, since ně9, at least one of kand lis at least 3. By applying the reverse map to switch kand lif necessary, we may assume that kě3. Case 1: l“0. The only possible representations are 0"0k´114and 0k13"1. By the inductive hypothesis, the first is valid if and only if n”2pmod 4q. By Lemma INTEGERS: 25 (2025) 8 3, the second is valid if and only if n”1,2pmod 4q. Thus, exactly one of these representations is valid if and only if n”1pmod 4q. Case 2: lě1. There are five potential representations: 1. 0"0k´1140l, 2. 0k1"130l, 3. 0k12"120l, 4. 0k13"10l, and 5. 0k140l´1"0. Observe that by the inductive hypothesis, representations (1) and (5) are valid if and only if n”2pmod 4q, which is to say that k`l”2pmod 4q. By Theorem 8 and Lemma 3, representation (2) is valid if and only if l”0,3pmod 4q; similarly, representation (4) is valid if and only if k”0,3pmod 4q. Finally, by Theorem 6, representation (3) is valid if and only if k”l”1pmod 2q. This allows us to count the number of valid representations in terms of the congruence classes of kand l modulo 4, as seen in Figure 6. In particular, there is a unique representation if and only if n”1pmod 4q. kzl0123 0 2132 1 1302 2 3001 3 2215 Figure 6: Table of number of representations for 0k140lfor values of n“k`l modulo 4. With this, we are ready to give a proof of the general linear bound. Proof of Theorem 1. We consider three cases. Case 1: nis even. By Theorem 7, we know that 0a1010n´a´3PUnfor all 0 ď aďn´3—this yields n´2 Ulam words. By Theorem 5, we also know that there are Gpn´1qUlam words of length nof the form 0a10b. Note that these two sets of Ulam words do not intersect (they have different numbers of ones), and since n´1 is odd, Gpn´1q ě 22“4. In total, this yields n`2 Ulam words. INTEGERS: 25 (2025) 9 Note that { 0a1010n´a´3“1a0101n´a´3“0a110b1if and only if n“3, so the reverses of the constructed Ulam words are also distinct Ulam words. Therefore, we have at least 2n`4 Ulam words in this case. Case 2: n”3pmod 4q. By Theorem 6, we know that 0a120n´a´2PUnfor all 0 ďaďn´2—this yields n´1 Ulam words. Since n´1”2pmod 4q, Gpn´1q ě 22“4, and so we can again use Theorem 5 to conclude that there are at least 4 words 0a10bof the right length. In total, this yields n`3 Ulam words. Note that { 0a120n´a´2“1a021n´a´2“0a110b1if and only if a“0 and a1“2. Therefore, the reverses of our two families of constructed Ulam words intersect, but only in two places; therefore, we have 2pn`3q ´ 2“2n`4 Ulam words. Case 3: n”1pmod 4q. As in the previous case, we have n´1 words of the form 0a120n´a´2, but it is possible that Gpn´1q “ 2, so we have to argue differently: specifically, we use Lemma 1 to conclude that 0a140n´4´aPUfor all 0 ďaďn´4, which yields another n´3 Ulam words, for a total of at least 2n´4. Observe that { 0a120n´a´2‰1a021n´a´2“0a1140n´4´a1ever, so we may simply double our count of Ulam words. In total, we have 4n´8, which is at least 2n`4 if ně6. In each case, we have identified at least 2n`4 distinct Ulam words. Next, we tackle the exponential bound, which we approach in a completely different fashion using the following lemma. Lemma 2. For any nPZě1, |Un|2ď |Un|`|Un`1| ` . . . ` |U2n|. Proof. Consider the set X:“␣pw1, w2q P U2 nˇˇw1‰w2(. For any pw1, w2q P X, either w1 "w2PU2nor there exists v1PUk,v2PU2n´ksuch that w1 "w2“v1 "v2, where kP r1, n´1sYrn`1,2n´1s; of course, if kP r1, n´1s, then 2n´kP rn`1,2n´1s, and so we may conclude that |X|ď|Un`1| ` . . . ` |U2n|. On the other hand, |X|“|Un|2´ |Un|. As a consequence of Lemma 2, we get the following very weak lower bound: for any nPZě1, max nďiď2n|Ui| ě |Un|2 n`1.(1) This is sufficient for our purposes. INTEGERS: 25 (2025) 16 Figure 11: From left to right, top to bottom: bar graphs showing the frequency of gaps of various sizes between consecutive words in Unfor n“13,...,30, shown out to 4 standard deviations. INTEGERS: 25 (2025) 17 6. Modular Distribution Let us now consider the relative density of Ulam words. As we mentioned earlier, the set of Ulam words is preserved under the complement map. This forces a symmetry on congruence classes. Theorem 11. If wPUnthen π´1`2n`1´1´πpwq˘PUn. Consequently, for any positive integer Nand aPZ{NZ, ρa,N pnq “ ρ2n`1´1´a,N paq. Proof. Given wPUn, write x“πpwq “ an2n`. . . `a0in binary. Then πpˆwq “ p1´anq2n`. . . ` p1´a0q “ 2n`1´1´x. But ˆwPUn. Now, observe that if πpwq ” amod N, then 2n`1´1´πpwq ” 2n`1´1´amod N, which forces the equality of the relative densities. For N“2,3, this is particularly simple. Corollary 2. For any positive integer n, we have that ρ0,2pnq “ ρ1,2pnq. Furthermore, for any aPZ{3Z, ρa,3pnq “ #ρ1´a,3pnqif n”0 mod 2 ρ´a,3pnqif n”1 mod 2. Proof. Observe that 2n`1´1´x”x`1 mod 2, from which ρ0,2pnq “ ρ1,2pnq follows immediately. For the second part, observe that 2n`1´1´xmod 3 ”#1´xif n”0 mod 2 ´xif n”1 mod 2. While there must always exist for any ntwo congruence classes a, b PZ{3Zsuch that ρa,3pnq “ ρb,3pnq, there is no reason why the last congruence class cshould be roughly equal. Indeed, for nď5, we see that ρc,3pnq “ 0. However, for larger n, it does appear to be the case that ρc,3pnq Ñ ρa,3pnq “ ρb,3pnq; as we will illustrate presently. To help measure the extent to which words are equidistributing modulo N, we define the modular discrepancy. Definition 1. For any positive integers n, N, the modular discrepancy is dNpnq:“max a,bPZ{NZ|ρa,N pnq ´ ρb,N pnq| . INTEGERS: 25 (2025) 18 Figure 12: A plot of the modular discrepancies for prime power moduli pkă30. Trivially, saying that Ulam words equidistribute modulo Nis equivalent to saying that dNpnq Ñ 0 as nÑ 8. Moreover, by appealing to the Chinese remainder theorem, proving that dNpnq Ñ 0 for all Nis reducible to proving that dpkpnq Ñ 0 for all prime powers pk. To investigate Conjecture 3, we computed dpkpnqfor all prime powers pkă30—as near as we can tell, dpkpnqdecays exponentially as a function of n(see Figure 12). Acknowledgements. Our collaboration was funded by four Bates College grants, all awarded by the Dean of Faculty’s office: a STEM Faculty-Student Summer Research Grant and three Summer Research Fellowships. We would also like to thank Tom´as Oliveira e Silva for confirming our computations of |Un|and giving many helpful suggestions for improving the exposition. References [1] T. Bade, K. Cui, A. Labelle, and D. Li, Ulam sets in new settings, preprint, arXiv: 2008.02762. [2] J. Cassaigne and S. R. Finch, A class of 1-additive sequences and quadratic recurrences, Exp. Math. 4(1995), 49–60. [3] S. R. Finch, Conjectures about s-additive sequences, Fibonacci Quart. 29 (1991), 209–214. [4] S. R. Finch, On the regularity of certain 1-additive sequences, J. Combin. Theory Ser. A 60 (1992), 123–130. [5] S. R. Finch, Patterns in 1-additive sequences, Exp. Math. 1(1992), 57–63. [6] J. Hinman, B. Kuca, A. Schlesinger, and A. Sheydvasser, Rigidity of Ulam sets and sequences, Involve 12 (2019), 521–539. INTEGERS: 25 (2025) 19 [7] J. Hinman, B. Kuca, A. Schlesinger, and A. Sheydvasser, The unreasonable rigidity of Ulam sequences, J. Number Theory 194 (2019), 409–425. [8] N. Kravitz and S. Steinerberger, Ulam sequences and Ulam sets, Integers 18 (2018), A80. [9] A. Mandelshtam, On fractal patterns in Ulam words, preprint, arXiv: 2211.14229. [10] R. Queneau, Sur les suites s-additives, J. Combin. Theory Ser. A 12 (1972), 31–71. [11] J. Schmerl and E. Spiegel, The regularity of some 1-additive sequences, J. Combin. Theory Ser. A 66 (1994), 172–175. [12] A. Sheydvasser, The Ulam sequence of linear integer polynomials, J. Integer Seq. 24 (2021). [13] S. Ulam, Combinatorial analysis in infinite sets and some physical theories, SIAM Rev. 6 (1964), 343–355.