-2
$\begingroup$

Let $A$ be a finite subset of an additive group $G$, with no pair of its elements being inverses. I would like to prove/disprove the existence of an infinite word over $A$ (treated now as an alphabet) that is free of "square-sums"--words of the form $CD$, where the sum of the letters of $C$ equals the sum of the letters of $D$ in $G$. Note that such a word would necessarily be square-free in the normal sense.

I've constructed some infinite square-free words using standard methods for some small values of $|A|$, and I suspect that such a word that is also square-sum-free cannot exist. Within these infinite words, I've been finding repeat sums for words of length $|A|$ or longer.

Example: The "Leech" square-free word

0121021201210120210201202120102101201021202102012021...

repeats 3 over and over via words of length 3, and I'm guessing it does so arbitrarily many times as the sequence progresses.

Addition:

I am especially interested in the situation where the sequence has a "tolerance" for repeat letters (but not repeat sums involving words consisting of more than one letter). That is, there exists at least one $a$ so that the words $aa, aaa$ are not considered squares/square-sums (but $aaaa$ is). Note that technically, such a sequence would no longer be square-free in the exact sense. For example, if $G=\mathbb{Z}$, then $6,6,6$ could be allowed but not $6,6,6,18$.

$\endgroup$
7
  • $\begingroup$ Welcome to Mathematics SE. Take a tour. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. $\endgroup$
    – Shaun
    Commented May 26, 2023 at 17:51
  • $\begingroup$ Can you provide some examples of what you're thinking of? For example, if $A = \{a \}$, what is the infinite word? $\quad$ Or maybe you think that there is never such an infinite word? $\endgroup$
    – Calvin Lin
    Commented May 26, 2023 at 17:52
  • $\begingroup$ @CalvinLin I'm thinking there is never such a word. I think it's probably reasonable to look at $A$ with cardinality 3 or greater, as this is when it is possible to have square-free words. $\endgroup$
    – user1181358
    Commented May 26, 2023 at 18:05
  • $\begingroup$ It would be helpful for you to state that in the problem itself. I'm guessing you're getting close votes because you've not provided information about what you've been working on, even if there is no useful result. Maybe show the longest square-sum-free on $\{a, b, c\}$ you can find, and why you can't extend it further. $\endgroup$
    – Calvin Lin
    Commented May 26, 2023 at 18:12
  • 2
    $\begingroup$ Your latest edits means that the last sentence of your first paragraph is no longer true. You should also indicate that this last addition is an addition, as it makes the already-posted answer seem "wrong". $\endgroup$ Commented May 26, 2023 at 20:39

1 Answer 1

1
$\begingroup$

(Note: This answer was posted before the OP said that they are willing to "allow" words that contain subwords of the form $aa$ or $aaa$; i.e., that the "no consecutive subwords have the same sum" would require those consecutive subwords to have length $2$ or larger.)


Too long for a comment. I suspect there is a cleverer way of doing this, but here is a way to show that $A$ would have to have at least four elements.

Say $A=\{a,b,c\}$ and we had such a word. Any set of four consecutive letters must use all three elements of $A$ (otherwise you will have either two consecutive letters the same, or a subword of the form $xyxy$, giving a square). In particular, whenever we have a pattern of the form $xyx$, the next letter must be the missing one. E.g., if we have $aba$, the next letter must be $c$.

I claim that our putative infinite word cannot have a pattern of the form $xyzx$ in four consecutive letters. Say, without loss of generality, that we have $abca$.

Case 1. Next letter is $b$, so we have $abcab$. Then the next letter cannot be $b$ or $c$ to avoid squares, so we must continue $abcaba$. Then the next letter must be a $c$ so the last four cover all three letters, but that gives $abcabac$, and then the second through fourth letters are the same as the fifth through seventh (one each). Thus, we end up with two consecutive sub-words that have the same totals for $a$, $b$, and $c$.

Case 2. The next letter is $c$, so we have $abcac$. The next letter must be a $b$ so that the last four cover all letters, so we get $abcacb$, but now we have the first three and last three letters are one each.

Thus, we cannot have $abca$ anywhere in the word, or more generally any four letters in the pattern $xyzx$.

So our initial pattern must be of the form $xyzy$ or $xyxz$.

In the latter case, say we have $abac$; then the next letter cannot be $b$ (that would give the pattern $xyzx$ in the last four), so we would have to have $abaca$. Then the last four letter have the pattern $xyzy$. So we can concentrate on that pattern.

Thus, say we have $abcb$. Then the next letter needs to be an $a$, to give $abcba$. If the next letter is $c$, we get the pattern $xyzx$ in the last four letters. So the next letter is $b$, to give $abcbab$. Then the next letter must be a $c$ so that the last four cover all three letters, giving $abcbabc$. The next letter cannot be $a$ (to avoid the $xyzx$ pattern), so it must be $b$, giving $abcbabcb$. Then looking at the $bcb$ end, we have that the next one must be $a$, giving $abcbabcba$; but this gives $bcba$ repeated at the end.

Thus, we must have $|A|\geq 4$.

$\endgroup$

You must log in to answer this question.