[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vip /vp / vr / w / wg / wsg / wsr / x / y ] [Search | Home]
hello /sci/
If images are not shown try to refresh the page. If you like this website, please disable any AdBlock software!

You are currently reading a thread in /sci/ - Science & Math

hello /sci/

the longest word composed by 'a' and 'b' with no pattern repeated twice in a row has length 3, for instance "aba"
it is pretty clear it cant get any longer

what would be the maximum length with no pattern repeated three times in a row? is it even finite?

it can get pretty long, for instance
aabbaabbaabaabbaabbaabaabbaabbabaabbaabbaabaabbaabbaabaabbaabbabaabbaabbaab...

however, for instance, aabababb is not permitted, since 'ab' is repeated three times in a row
>>
>>7838787
your example has the string "aabbaabbaab" repeat continuously.

what is the minimum number of characters required to be a pattern?
>>
a more technical formulation of my question would be "is the quotient of the free group [math]F_2[/math] by [math]\forall x~x^3=e[/math] finite?"
>>
>>7838797
look again at my example
also, the "..." do not imoly that the pattern is repeating, it means that i could go much further but it gets boring

any repeated sequence of characters is a pattern
>>
>>7838798
>free group
Don't you mean the free monoid? The free group would have 4 generators, including a^-1 and b^-1.
>>
>>7838805
if i state that [math]\forall x~x^3=e[/math] it means that there is no need for [math]a^{-1}[/math] since it is the same as [math]aa[/math]
>>
>>7838811
Yeah, but I meant the object you have before factoring out this relation. You're taking the quotient of the free monoid modulo x^3=e.
>>
>>7838814
it is the exact same thing after the quotient anyway
make it a monoid if you prefer
>>
op here

i am starting to become pretty sure it is infinite
consider the following sequence
[math]x_0=ab[/math]
[math]x_{n+1}=x_n x_n {x_n}^{c} {x_n}^{c}[/math]
where the ^c thing means "swap a and b"

it yields an infinite "word"
at least im pretty sure it does, trying to write a proof
>>
>>7838861

Why do you need to repeat x_n ? It seems like a similar argument could be made for the sequence

x_0 = a
x_{n+1} = (x_n) (x_n)^c
>>
>>7838814
>>7838805
Free group on...
implies an identity and inverse. You can think of it as taking those generators and applying the group axioms to them. You could add generators a^-1 and b^-1, but then it wouldn't be free because you've imposed this extra relation - that a^-1 is the inverse of a.
>>
>>7838931
I worded that a bit poorly. The group would be still be free but it wouldn't be the free group on the set {a,b,a^-1,b^-1}. The free group on that set of generators is isomorphic to the free group on {a,b,c,d},.
>>
>>7838913
please stop writing weeaboo text faces this is a science board
>>
>>7838787
abaa repeats a pattern?

And aabbaabb doesn't repeat "aabb"?

I think you need to define your terms better.
>>
>>7838861
If i got your definition right i get:
ab
ababbaba
ababbabaabab > babababa < abab

what do you mean by swap a and b.
also, this is such a good question.
>>7839119
abaa repeat a.
after that we consider 3 repetition's.
>>
>>7839155
aba repeats a as well. Again, what do you mean by repeating a pattern?
>>
>>7839155
damn youre right
thanks for pointing that out
>>7839172
three consecutive occurence of a "word"
>>
>>7839155
>>7838913
also it seems it doesnt happen with this one
this is no proof though
>>
>>7839214
still op here
i have a sketch of a proof that might work with
[math]x_0=a[/math]
[math]x_{n+1}=x_n {x_n}^c[/math]
which yields abbabaabbaababbabaababbaabbabaab...
(but keep in mind that i was pretty sure my previous solution worked too so there might be some oversights)

lets use a technical lemma:
you can prove by induction that if you only consider the letters in position [math]p_0 + 2^k n[/math] then the pattern is the same as the starting pattern (maybe shifted or "swapped" but that doesnt matter)

then here is the draft of my proof:
first, notice that the letters are grouped by pairs, either 'ab' or 'ba'
therefore, there cant be two consecutive occurences of a pattern of odd length: if the first occurence has k 'a' and k+1 'b', then the next one will have k+1 'a', and k 'b'
(that forbids patterns of length 1, 3, 5,
...)

then we notice that that proof still holds for patterns of length [math]2^k n[/math] (with n odd) if we use our lemma and only consider every 2^k th letter starting with the first one of the supposed pattern

therefore there is no repeating pattern, regardless of length
>>
https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence