WorksMathematics
An additive-square-free word over an alphabet of size 6
Abstract
An additive square over is two consecutive nonempty blocks of the same length and same sum. For example, 1423 is an additive square, since 14 and 23 both have length 2 and sum 5. Solving a problem that has been open for more than 50 years, we give an example of an infinite word over a 6-letter subset of N that avoids additive squares.
Introduction
A word is a sequence of letters drawn from a set called its alphabet. A block is a finite run of consecutive letters. For integer letters, an additive square consists of two adjacent nonempty blocks with equal lengths and equal sums. For example, 1423 is an additive square because each block has two letters and each sums to five.
Can an infinite word on a finite set of integers avoid every additive square? Justin [3] [3], Brown and Freedman [1] [1], Pirillo and Varricchio [4] [4], and Halbeisen and Hungerbühler [2] [2] each posed the problem in different forms. Brown and Freedman conjectured that every bounded sequence of positive integers contains an additive square.
This note proposes an explicit word on six positive integers that avoids additive squares. The proof has two steps. First we build an auxiliary word by repeatedly replacing each letter by a block of letters. We show that a square in would give a square in with its block length divided by . This rules out a square of least positive block length. We then use a four-symbol construction of Peltomäki and Whiteland [5] to encode as , in such a way that any square in would give a square in $w`.
Positions, cuts, and sums. In a word , position holds the letter . The cut at is the boundary immediately before . The letters before this boundary form the prefix of length . For integer letters its sum is , with . Two adjacent blocks of length starting at position have three boundary cuts, , , . Their sums are equal precisely when
We call the half-length of the square.
The six integers and the word
Set
The alphabet, in increasing order, is
Define the 85-symbol word to be
0120232123203231301020103101213121021232021013010203212320231210212320232132303132120.
For each symbol , let be with added modulo four to each digit. A substitution replaces each letter by its assigned word and joins the resulting words in order. Use this rule to apply eleven times to the two-letter word 01. The result is , of length . This substitution is due to Veikko Keränen, and is given in [5 Section 3].
The integer in the rule below is specified in Section 4 and satisfies . To encode , take one copy of . Label the first zeros in this copy by . Leave the remaining zeros up to and including the -th zero at , then label the next zeros by 1. All later zeros receive . The symbols 1, 2, 3 receive the same labels in every copy.
Equivalently, write the requested position as with . Thus selects the copy and , its offset, counts how many letters precede position within the copy. Let and let count the zeros among the first letters of . The rule for is
For instance, with , the word begins
Each word contains all four symbols. The last substitution step joins such words, so has more than zeros. Because , all three labels for zero occur in the copy encoding . The symbols supply the other three labels. Thus uses all six integers in (1).
Forcing the half-length to be a multiple of
Set and . Our aim is to build a periodic sequence such that the residues of the letters of modulo force the beginning, middle, and end of a square to lie at the same offset in their respective length- blocks.
For a statement , the Iverson bracket is 1 when is true and 0 when is false. Given a residue modulo , take its representative between 0 and . Write this representative in base 8 as , using leading zeros as needed. Each digit belongs to . Define
The first sum records which digits lie in the upper half . The second uses the squares of all twenty digits.
Lemma 1. If and , then in .
Proof. There are twenty digits, each at most 7, so the sum of their squares is at most . The first sum in is less than . Hence . The integer is divisible by and has magnitude less than , so it is zero.
For each digit position , put
Reducing the equality of the -values modulo gives
Here the units coefficient means , the coefficient of in this particular sum. Every other summand is divisible by 3, so 3 divides . Since , we get . Divide by 3 and repeat to get , then , and so on. If , the equation requires both . If , it requires both .
Thus the three digits at position lie in a set of four consecutive integers, and . Apply the same divisibility argument in base 8 to . Each coefficient is zero, giving . The first sums in have already cancelled, so the squared digits must satisfy
Each square in the last sum vanishes. Hence for each , as required.
Let be the representative in of modulo , where the arguments of are read modulo . This makes periodic with period . Consider any integer word satisfying (mod ) for all . Adding these congruences from 0 to gives (mod ), because the intermediate -values cancel. If has an additive square starting at with half-length , apply Lemma 1 to the residues , , modulo . The first congruence holds by equal spacing, and the second follows from equality of the adjacent block sums in . Hence
Building the auxiliary word
Let , . Form the finite set of positive integers
To count the possible values of , add one to the twenty base-8 digits of . The trailing 7s change to zeros, and the first digit to their left increases by one. For instance, the base-8 string 2577 becomes 2600. All unchanged digits cancel from . The number of trailing 7s and the old value of the digit to their left therefore determine . There are choices for these two numbers and one more case, when all twenty digits are 7 and wraps to zero. Thus . Moreover .
Give each its rank in increasing numerical order, starting from 1. Define by reading the binary digits of as base-3 digits. For example, rank receives the numerical label . We call the tag of . The rank fits in nine binary digits, so . The following implication lets us recognize when three letters coincide.
Indeed, write the three tags in base 3. In the difference , the coefficient of each power of 3 lies in . Successive division by 3, as in Lemma 1, shows that each coefficient is zero. The binary digits of the three ranks therefore agree at every position, so their letters coincide.
We give the replacement block two jobs. Its letters must have the prescribed residues modulo , and their sums must retain the value of the original letter . At offset we use . The table specifies the integer at each of the offsets of .
| Number of positions | Values of , from left to right |
| ones, followed by zeros | |
| copies of , followed by zeros | |
| ones, followed by zeros |
Table 1.
The middle region has room for all copies of because and . Every letter in belongs to . The beginning and end of contribute a total of to the sum of its -values, and the middle contributes . Thus
Since , the first letter of every is . Start with and apply repeatedly. Write for the result after substitutions. Because begins with , each is a prefix of . The lengths grow without bound. Define to be the unique infinite word with all these prefixes. Another application of the same substitution gives .
Why a square in would force a shorter square
Write for the sum of the first letters of . The second difference of any sequence , starting at with step , is the number
For the sequence of prefix sums , this is the right block sum minus the left block sum. Thus a square in starting at with half-length is equivalent to .
Claim. The word contains no additive square.
Proof. Suppose contains a square. Choose one whose half-length is as small as possible. Every letter of is congruent to modulo at its position . By (3), for a positive integer . Write the starting cut as , . The other two cuts are and , each at the same offset in its own replacement block.
Fix this . Define , the sum of the first entries of the table in the block . For each block index , write . In function notation denotes the sequence with value at index . Thus , for example, is the partial sum in the block .
Before cut there are complete replacement blocks and the first entries of . By (5) their -values sum to . Since is periodic with period , the two adjacent blocks of length have identical -sums. For the full letter sums to agree, their -sums must therefore agree as well. Take the second difference of at . The term cancels, giving
The first parenthesis in (6) compares two complete length- blocks of . The three -terms account for where the common offset falls inside the replacement blocks.
First region. If , all three partial sums belong to . Hence . The first term in (6) is an integer multiple of , so it must be zero. This gives .
Middle region. If , the first region has contributed and all later contributions so far are multiples of . Thus . Reduce (6) modulo and use (4) to get . Their partial sums are equal, so here as well.
Last region. If , let be the sum of the -values from offset to the end of . Only ones and zeros remain, so . Insert into (6). Since , this gives
The right-hand side has magnitude at most , so . All cases produce a square of half-length in , contradicting minimality.
Why the six-letter encoding preserves avoidance
Two blocks are abelian equivalent if every symbol appears the same number of times in each block. Peltomäki and Whiteland show in the proof of their Theorem 1.2 that, for every , the periodic repetition of has no two adjacent abelian-equivalent blocks of equal length with [5].
First give the symbols of the respective values . Repeat this numerical version of indefinitely to obtain the periodic sequence . Consider two adjacent length- blocks of , where and . Each block sum contains the same contribution from full periods. The two remaining pieces of length begin positions apart modulo , so they are adjacent when read in the periodic repetition of .
If , let count the symbols in one remaining piece. Its numerical sum is . Each count is less than , so these counts are exactly its base- digits. Equal sums would force equal counts of , and the common length would then force equal counts of . The theorem of Peltomäki and Whiteland excludes such a pair. Therefore equality of the two -sums implies , or . For any , both remaining sums belong to , so their difference has magnitude at most .
Next define an integer sequence , the signal, to record which zeros change value in (2). In the copy of encoding , put at the first zeros and at zeros numbered , counting the zeros from one. Put at all other positions. Then
Each complete copy contributes to the signal sum. The sequence locates the block boundaries modulo , and the signal sums over complete copies recover the letters of .
Claim. The word of (2) contains no additive square.
Proof. An additive square in forces the difference of the two -sums to vanish modulo . Its magnitude is strictly less than , so it vanishes, and for a positive integer . Equality of the two -sums now also forces equality of the corresponding -sums. The cuts have a common offset in copies , , of . Suppose first that the first symbols of contain at most zeros. At this offset in copy , let count the positive signals already read. No negative signal has been read. The signal sum up to cut is therefore . The three signal prefix sums have zero second difference. Since , this implies . Each belongs to , so the absolute value of this difference is at most . It must vanish, leaving .
Suppose instead that the first symbols of contain more than zeros. In copy , all positive signals have been read. Let count the negative signals already read. The signal sum up to cut is now
Again the remainder, , belongs to . Its second difference is a multiple of with magnitude at most , so it vanishes and . The two cases give a square in starting at or at , contrary to § 5. This proves the claim for .
Evaluating a specified position
The following procedure evaluates (2) without writing out a length- replacement block or the length- period.
Compute by division of by . To tabulate , evaluate at and at for , , and use the three allowed -values. Sort the distinct letters to obtain their ranks. Start at and read the digits of in base , most significant first. For each digit , replace the current letter by . The result is . This follows from .
Let count the zeros in . With zero substitutions the word is the single letter , so . For higher levels use
Begin with the two blocks , . Skip the blocks preceding offset , subtracting their lengths and accumulating their zero counts. At each remaining level , split the current block into its 85 children of length and repeat. The single symbol reached at level zero and the accumulated count are exactly and in (2).
As checks on indexing, and the first occurrence of the integer 1 is at zero-based index 1,152,921,504,466,744,130, the position of the -st zero of the first copy of .
Optimality
Since an abelian square is an additive square, and since it is impossible to avoid abelian squares over an alphabet of size 3, the optimal alphabet size for an infinite word avoiding additive squares is of size at least 4. The construction in this paper uses an alphabet of size 6. Thus the optimal alphabet size for an additive-square-avoiding word is either 4, 5, or 6. It remains to determine which one is correct.
Statement of AI Usage
This paper was almost entirely written by GPT 6.2 Astra. I added some introductory and material, references, and discussion. I take full responsibility for the correctness.
A Lean verification of the construction, also constructed by GPT 6.2 Astra, is available at https://cs.uwaterloo.ca/~shallit/Papers/additive_square_lean-2.zip.
The main theorem is AddSquare.Six.six_letter_counterexample in AdditiveSquare.lean.
To reproduce the verification, unzip the project and run sh check.sh from the extracted directory.
References
- [1]T. C. Brown and A. R. Freedman, Arithmetic progressions in lacunary sets, Rocky Mountain Journal of Mathematics 17 (1987), 587–596. The conjecture appears on pp. 595–596. doi:10.1216/RMJ-1987-17-3-587.DOI
- [2]L. Halbeisen and N. Hungerbühler. An application of Van der Waerden’s theorem in additive number theory. INTEGERS: Elect. Journ. Comb. Number Theory 0 (2000), #A7 (electronic), http://www.integers-ejcnt.org/vol0.htmlDOI
- [3]J. Justin, Généralisation du théorème de van der Waerden sur les semi-groupes répétitifs, Journal of Combinatorial Theory, Series A 12 (1972), 357–367. doi:10.1016/0097-3165(72)90101-X.DOI
- [4]G. Pirillo and S. Varricchio, On uniformly repetitive semigroups, Semigroup Forum 49 (1994), 125–129. doi:10.1007/BF02573477.DOI
- [5]J. Peltomäki and M. A. Whiteland, Avoiding abelian powers cyclically, Advances in Applied Mathematics 121 (2020), 102095. doi:10.1016/j.aam.2020.102095. arXiv:2006.06307.DOI