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

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

Thread images: 1

File: tmp_30739-220px-F2_Cayley_Graph-1717580173.png (15 KB, 220x220)
Image search:
[iqdb]
[SauceNao]
[Google]

15 KB, 220x220

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

>>

>>

>>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.

>>

>>

>>7839155

aba repeats a as well. Again, what do you mean by repeating a pattern?

>>

>>

>>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

Thread images: 1

Thread DB ID: 512971

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's